We explore how to speed up binary search by batching independent searches with NumPy's vectorized operations. We then reformulate the algorithm so all searches progress together with only $O(1)$ additional memory, port it to C++, and achieve up to a 25× speedup over NumPy 2.4's implementation.
Whay I don’t like about presentations like this is that they change the problem statement without saying that they do so. You don’t make binary search 25x faster, you make batched binary search 25x faster. That’s useful! But it’s not the same as making one np.searchsorted call faster.
Exactly! There is also the tension between a simpler title and a super exact one. We could have a title that is “Making np.searchsorted (up to) 25x faster (when querying multiple keys)”.
Whay I don’t like about presentations like this is that they change the problem statement without saying that they do so. You don’t make binary search 25x faster, you make batched binary search 25x faster. That’s useful! But it’s not the same as making one np.searchsorted call faster.
score 1 · canonical
searchsorted()takes an array of needles to search for, as I understand it: https://numpy.org/doc/2.4/reference/generated/numpy.searchsorted.htmlscore 1 · canonical
Exactly! There is also the tension between a simpler title and a super exact one. We could have a title that is “Making np.searchsorted (up to) 25x faster (when querying multiple keys)”.
score 1 · canonical
Oh! I misread that somehow. That explains things. Thank you!
score 1 · canonical