3 ms·

I was inspired by this article[0] to see if I could beat the Python standard library implementation of "bisect_left" using C-extensions. [0] https://probablyda

• cycomanic 3y ago
  > This is the second time that I came across an algorithm in Knuth’s books that is brilliant and should be used more widely but somehow was forgotten. Maybe I should actually read the book… It’s just really hard to see which ideas are good and which ones aren’t. For example immediately after sketching out Shar’s algorithm, Knuth spends far more time going over a binary search based on the Fibonacci sequence. It’s faster if you can’t quickly divide integers by 2, and instead only have addition and subtraction. So it’s probably useless, but who knows? When reading Knuth’s book, you have to assume that most algorithms are useless, and that the good things have been highlighted by someone already. Luckily for people like me, there seem to still be a few hidden gems. Oh the irony, considering that fibonacci hashing is another of those forgotten algorithms, see yesterday's discussion: https://news.ycombinator.com/item?id=35739629 https://news.ycombinator.com/item?id=35739629
• dang 3y ago
  Discussed here a couple days ago: Beautiful branchless binary search - https://news.ycombinator.com/item?id=35737862 https://news.ycombinator.com/item?id=35737862 - April 2023 (143 comments)