3 ms·
There are some possibilities with uneven searches for sure. The major issue is that a search is so fast it doesn't leave a lot of room for overhead. For interpo
by mlochbaum 3y ago
There are some possibilities with uneven searches for sure. The major issue is that a search is so fast it doesn't leave a lot of room for overhead. For interpolation search, scheduling out bad cases sounds fine until you have a lot of them: then you have to search them one at a time, and the length's unpredictable, right? Grouping by search length doesn't really sound feasible: you'd have to store element index and value, as well as current search index, for each element that goes the long way.
- moonchild 3y ago> length's unpredictable, right? Grouping by search length doesn't really sound feasible You just have to group by ceillog2, so there aren't many buckets. Can even discretise further (say, one bucket for every two exponents) with likely not too much penalty. Alternately, perhaps restart the search entirely for pathological elements (so don't try to keep around the information gained by the cursory iterations of interpolation search), but if there are too many pathological elements, just do binary search up front for all elements. I expect this would work pretty well in practice. (Maybe with exponential backoff or something, so you don't lose to changes in the distribution of elements being searched for.) (This reminds me, I have a similar problem with adaptive sorting. Having identified a number of presorted runs, it's necessary to merge them in the right order, because if I merge them in the wrong order I get quadratic. Plan is similarly to sort them by lzcnt or some such, which is a curious recursive problem.)