<br><br><div class="gmail_quote">On Tue, Nov 10, 2009 at 10:51 PM, Christopher Barker <span dir="ltr">&lt;<a href="mailto:Chris.Barker@noaa.gov">Chris.Barker@noaa.gov</a>&gt;</span> 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="im">Anne Archibald wrote:<br>
&gt; 2009/11/10 Christopher Barker &lt;<a href="mailto:Chris.Barker@noaa.gov">Chris.Barker@noaa.gov</a>&gt;:<br>
<br>
</div><div class="im">&gt;&gt; I have a bunch of points in 2-d space, and I need to find out which<br>
&gt;&gt; pairs of points are within a certain distance of one-another (regular<br>
&gt;&gt; old Euclidean norm).<br>
&gt;<br>
&gt; This is an eminently reasonable thing to want, and KDTree should<br>
&gt; support it. Unfortunately it doesn&#39;t.<br>
<br>
</div>darn.<br>
<div class="im"><br>
&gt; It&#39;s slow both because you&#39;re using the python implementation rather<br>
&gt; than the C,<br>
<br>
</div>I noticed that.<br>
<div class="im"><br>
&gt; The one good thing about using the python implementation rather than<br>
&gt; the Cython one is that you can subclass it, providing a new method.<br>
&gt; There&#39;s still a certain amount of boilerplate code to write, but it<br>
&gt; shouldn&#39;t be too bad.<br>
<br>
</div>Can you give me a hint as to where to start?  I have no idea how kd<br>
trees work.<br>
<div class="im"><br>
&gt; If this is still too slow, I have no problem incorporating additional<br>
&gt; code into cKDTree; the only reason none of the ball queries are in<br>
&gt; there is because ball queries must return variable-size results, so<br>
&gt; you lose a certain amount of speed because you&#39;re forced to manipulate<br>
&gt; python objects. But if there are relatively few result points, this<br>
&gt; need not be much of a slowdown.<br>
<br>
</div>And certainly in this case, there would not be very many results, and<br>
lists are pretty fast.<br>
<br>
However, this does bring up the need for a growable numpy array. I&#39;ve<br>
been working on one in Python, but it would be really nice to have one<br>
that could be accessed by C (or cython) code.<br>
<br>
It wouldn&#39;t be that hard to do (for someone familiar with the numpy<br>
code, anyway), I don&#39;t think. It is mostly boiler plate in Python. I&#39;m<br>
imagining it would only support contiguous arrays, and could only grow<br>
is the first dimension.<br>
<font color="#888888"><br>
<br></font></blockquote><div><br>I think Python lists are basically just expanding arrays and pointers are cheap. Where you might lose is in creating python objects to put in the list and not having ufuncs and the rest of the numpy machinery. If you don&#39;t need the machinery, lists are probably not a bad way to go.<br>
<br>Chuck<br></div><br></div>