How fast does interpolation search converge?
1–10 of 27 posts
Re: How fast does interpolation search converge?
#2Neat trick. Possibly a bit brittle, since you have to maintain your knowledge of the distribution somewhere -- i.e. it's "state you have to update or things might break," which is always worrisome.
I wonder what the worst case performance is -- if your guess is completely wrong, will it still converge in no worse than O(log(N))? Do you guess only once, at the beginning, or do you keep guessing where to go based on the distribution?
If you only guess once, at the beginning, then there's probably no risk. But if you keep trying to aim for the wrong target every iteration, I wouldn't be surprised if you get pathological behavior.
It would be kind of fun to try to calculate or simulate how bad it can get if you keep making incorrect guesses.
Re: How fast does interpolation search converge?
#3Neat trick. Possibly a bit brittle, since you have to maintain your knowledge of the distribution somewhere -- i.e. it's "state you have to update or things might break," which is always worrisome. I wonder what the worst case performance is -- if your guess is completely wrong, will it still converge in no worse than O(log(N))? Do you guess only once, at the beginning, or do you keep guessing where to go based on th…
> if your guess is completely wrong, will it still converge in no worse than O(log(N))?
No, but there's a simple but powerful technique you can use to ensure this from the outside. See if you can figure it out. (If you don't, look up introsort.)
Re: How fast does interpolation search converge?
#4A related technique is generating an index using a machine learned model (well explained here: https://blog.acolyer.org/2018/01/08/the-case-for-learned-ind...). In interpolation search, we just use a simple linear model. Kraska and co. use much more complex models to beat BTree indexes. However, the Recursive Model Indexes (RMIs) that they published (https://github.com/learnedsystems/RMI) use Rust to a C++ model that is exported as a library, so it definitely doesn't seem ready for production yet!
Re: How fast does interpolation search converge?
#5Neat trick. Possibly a bit brittle, since you have to maintain your knowledge of the distribution somewhere -- i.e. it's "state you have to update or things might break," which is always worrisome. I wonder what the worst case performance is -- if your guess is completely wrong, will it still converge in no worse than O(log(N))? Do you guess only once, at the beginning, or do you keep guessing where to go based on th…
> if your guess is completely wrong, will it still converge in no worse than O(log(N))? No, but there's a simple but powerful technique you can use to ensure this from the outside. See if you can figure it out. (If you don't, look up introsort.)
Is the trick quit and start doing a binary search?
Re: How fast does interpolation search converge?
#6Earlier quoted context omitted.
> if your guess is completely wrong, will it still converge in no worse than O(log(N))? No, but there's a simple but powerful technique you can use to ensure this from the outside. See if you can figure it out. (If you don't, look up introsort.)
Is the trick quit and start doing a binary search?
Ooh, or what about alternating interpolation and binary search steps?
Interpolation steps make quick progress if your distribution is correct.
Re: How fast does interpolation search converge?
#7Earlier quoted context omitted.
Is the trick quit and start doing a binary search?
Ooh, or what about alternating interpolation and binary search steps? Interpolation steps make quick progress if your distribution is correct.
That's actually quite clever. I like it.
I can't figure out the puzzle's answer. Hopefully they'll post the solution someday.
Re: How fast does interpolation search converge?
#8As a side note, if you have the possibility to sort data before searching values in it then implement trie:
https://en.wikipedia.org/wiki/Trie
This is the best for data with very few updates/modifications and a lot of queries. One example would be points of interest on a map, like restaurants on google maps. Not like those restaurants gets updated/modified every single day but you do have clients that while using your restaurant finder app they query a lot of them on a given radius around their GPS coordinates.
I had such a project in the past. My client acquired this data, around 3 billion points of interests residing in a PostgreSQL DB that was around 900 GB. While the server was beefed with 128GB RAM, was not nearly enough to have it all in memory and it had a responsiveness of several seconds, way too much for young impatient users and my client was seeing a decline in users. I reorganized data in PGSQL to fit a trie tree and now a query was solved in milliseconds. Accounting all other stuff on top, the app was now able to generate a response under a second. Trie ftw.
Re: How fast does interpolation search converge?
#9Earlier quoted context omitted.
Ooh, or what about alternating interpolation and binary search steps? Interpolation steps make quick progress if your distribution is correct.
That's actually quite clever. I like it. I can't figure out the puzzle's answer. Hopefully they'll post the solution someday.
Yup that was the answer :-) interleaving the two lets you get the best of both worlds at the cost of a constant-factor penalty. This is a pretty clever & general-purpose meta-algorithm that works for pretty much any problem where you have competing algorithms with different strengths.
Quitting and starting over as GGP mentioned is another option that also works for this problem, though it might not work as well for other problems where you can't put a nice bound on the number of steps.
FWIW there's also a very dumb (or smart I guess, depending on your point of view) solution, which is to just have 2 threads run simultaneously, and report the result of the first one. It might make sense for some problems. And in any case, this is basically equivalent to what you're doing on 1 CPU with the previous technique.
Re: How fast does interpolation search converge?
#10I converted his code to python.
https://gist.github.com/brianherman/7e58b48ddbb7060663139416...