<br><br><div class="gmail_quote">On Thu, May 8, 2008 at 9:55 PM, Robert Kern &lt;<a href="mailto:robert.kern@gmail.com">robert.kern@gmail.com</a>&gt; wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d">On Thu, May 8, 2008 at 10:51 PM, Andrew Straw &lt;<a href="mailto:strawman@astraw.com">strawman@astraw.com</a>&gt; wrote:<br>
&gt; I&#39;ve got a big element array (25 million int64s) that searchsorted()<br>
&gt; takes a long time to grind through. After a bit of digging in the<br>
&gt; literature and the numpy source code, I believe that searchsorted() is<br>
&gt; implementing a classic binary search,<br>
<br>
</div>Yes.<br>
<div class="Ih2E3d"><br>
&gt; which is pretty bad in terms of<br>
&gt; cache misses. There are several modern implementations of binary search<br>
&gt; which arrange items in memory such that cache misses are much more rare.<br>
&gt; Clearly making such an indexing arrangement would take time, but in my<br>
&gt; particular case, I can spare the time to create an index if searching<br>
&gt; was faster, since I&#39;d make the index once but do the searching many times.<br>
&gt;<br>
&gt; Is there an implementation of such an algorithm that works easilty with<br>
&gt; numpy? Also, can you offer any advice, suggestions, and comments to me<br>
&gt; if I attempted to implement such an algorithm?<br>
<br>
</div>I&#39;m no help. You seem to know more than I do. Sadly, the first few<br>
Google hits I get for &quot;binary search minimize cache misses&quot; are<br>
patents. I don&#39;t know what the substantive content of those patents<br>
are; I have a strict policy of not reading patents.<br>
<font color="#888888"></font></blockquote><div><br>I would be interested in adding such a thing if it wasn&#39;t patent encumbered. A good start would be a prototype in python to show how it all went together and whether it needed a separate indexing/lookup function or could be fit into the current setup.<br>
<br>Chuck <br></div><br></div><br>