21 Yr Old Disproves 4 Decades Old Belief in Computing

Comments · 751

• TU

  @TuringApp · 3 months ago · pinned

  Listen to 100s of Science Documentaries on Turing for Free. Checkout the App at <br>iOS: <a href="https://apps.apple.com/in/app/the-turing-app/id6752724106">https://apps.apple.com/in/app/the-turing-app/id6752724106 </a><br>Android: <a href="https://play.google.com/store/apps/details?id=com.theturingapp.turing&amp;hl=en">https://play.google.com/store/apps/details?id=com.theturingapp.turing&amp;hl=en </a><br>or listen at <a href="https://theturingapp.com/">https://theturingapp.com</a>

  19

• WP

  @wpherigo1 · 3 months ago (edited)

  Teenager? &nbsp; &nbsp;21 years old. &nbsp;Both guys named “Andrew”? &nbsp; That a hash collision!

  290

• JI

  @Jim1971a · 3 months ago

  “Not knowing the old rules is the way to break through”. &nbsp;That’s a great quote and is applicable to many pursuits.

  288

• TE

  @TerjeMathisen · 3 months ago

  The video did show something important which was omitted in the narrative, and that is that a simpler (greedy) algorithm is in fact significantly faster if you can limit your filling grade to maybe 80 or 90%. So you can trade space for time: Instead of having to extend and rehash when totally full, you do so 10-20% earlier and thereby stay within the near-constant access time regime.<br>Also, 45 years ago when I was at university in Trondheim we already knew that one simple way to avoid bottlenecks was to employ a second (different) hash if the first one collided.<br>The current state of the art does not use this new research, instead it employs SIMD style code to very quickly probe up to 15 entries in the same hash slot, it is used by Google as well as the standard Rust and C++ libraries.<br><br>It is of course still an extremely impressive piece of work, I only wish I could have done the same!

  288

• PE

  @pebbleschan6085 · 3 months ago

  Elastic hashing is a prior art created by nature ; it is exhibited by men going to a mens room and selecting an available urinal or cubicle when the next man always evaluates the current state and chooses the most equally distant one from occupied ones. 😂

  160

• CO

  @colinmaharaj · 3 months ago

  <a href="https://www.youtube.com/watch?v=EdVG5qNm2rY&amp;t=180">3:00</a> In my hash table number 42 is the book Hitchhiker&apos;s Guide to the Galaxy 😂

  159

• CH

  @christophelmjverlinde2117 · 2 months ago

  The phrase &quot;reading rots the mind&quot; is a famous quip originally attributed to the Irish playwright and philosopher George Bernard Shaw. Francis Crick repeated it. The young man in the video had the advantage that he was unaware of previous dogma written up in a paper that he had not read.

  10

• PA

  @paulpinecone2464 · 3 months ago

  This is similar to the bus clumping problem. Why do multiple busses come at once? Because the lead bus keeps stopping to pick up the accumulated passengers. It slows down. The bus in it&apos;s shadow has few passengers to pick up. It speeds up. The two buses clump, the lead one keeping the next one doing nothing. Then the third bus starts coming up.<br><br>The solution is the same as this new hash method: Buses have to ignore passengers when they are behind and leave them to slow down the next bus. Unfortunately, this is so enraging that you can&apos;t do it.

  53

• AL

  @albertussmit4090 · 3 months ago

  If I were Andrew’s supervisor/mentor, I’d have made him first author on the paper.

  93

• LA

  @LabyrinthMike · 3 months ago

  The video did a pretty good job of explaining hash tables until it got to Andrew&apos;s solution, then hand waving.

  34

• MI

  @michaelgreene9889 · 2 months ago

  It&apos;s a very old trade off - memory vs speed. The graph at <a href="https://www.youtube.com/watch?v=EdVG5qNm2rY&amp;t=1111">18:31</a> shows the algorithm is slower in all cases until memory is close to full.

  3

• TH

  @thatpodcastshowforU · 3 months ago

  Such a great explanation. I remember studying hashing, greedy algorithms etc. during college and this feels like such a good refresher of those concepts. It is really important specifically these days when we have AI agents implementing the ideas super quick, the architecture/logic how we want them to solve a problem matters a lot. And that’s why I feel conceptual knowledge is really important.

  9