3 ms·
I think I’m missing something. Under what conditions do you want to search through several identically sized lists independently? (I had assumed from the title
by boulos 7y ago
I think I’m missing something. Under what conditions do you want to search through several identically sized lists independently? (I had assumed from the title that this would be about performing many independent queries against the same list, optionally with SIMD, instead of one query against many lists).
It wouldn’t be a huge change to also make the N-value “per query”, but then you get a lot more branches in the inner loop. Even then though, I’m struggling to remember situations where I thought “I have a dozen lists where I need to do binary search for each of them”.
- kjeetgill 7y agoIt definitely comes up in search-index style posting lists. For dense postings you'll usually deal with bitmaps, but you'll have sorted integers for sparse ones and you usually have at least one list per search term. There's all sorts database indexing problems that can use this too, I'm sure.