Hi Andrew 2008/5/9 Andrew Straw <[EMAIL PROTECTED]>: > I've got a big element array (25 million int64s) that searchsorted() > takes a long time to grind through. After a bit of digging in the > literature and the numpy source code, I believe that searchsorted() is > implementing a classic binary search, which is pretty bad in terms of > cache misses. There are several modern implementations of binary search > which arrange items in memory such that cache misses are much more rare. > Clearly making such an indexing arrangement would take time, but in my > particular case, I can spare the time to create an index if searching > was faster, since I'd make the index once but do the searching many times. > > Is there an implementation of such an algorithm that works easilty with > numpy? Also, can you offer any advice, suggestions, and comments to me > if I attempted to implement such an algorithm?
If found Francesc Altet's Pyrex implementation at http://mail.python.org/pipermail/python-list/2007-November/466503.html I modified it for use with Cython and added some tests: https://code.launchpad.net/~stefanv/+junk/my_bisect That may be a good starting point for further experimentation. As it is, it is already about 10 times faster than the built-in version (since I can assume we're working with int64's, so no special type checking is done). Regards Stéfan _______________________________________________ Numpy-discussion mailing list Numpy-discussion@scipy.org http://projects.scipy.org/mailman/listinfo/numpy-discussion