[Yt-dev] kdTree

[Stephen Skory]

Hi,


> The pure python implementation is fine with me, but keep in mind it
> won't scale to a huge number of points 

I ran some tests and of course you are correct, the Python implementation is vastly slower than the C code in FOF/HOP. I can compile it with Cython, which speeds things up by about 30%, without doing any actual optimization by hand. I'm not sure how much optimization can be done, this kd tree code passes a lot of python objects around.

> Alternatively, the kD trees in HOP
> and FOF could be wrapped, which all-in-all would not be such a bad
> thing.

The only drawback to this is that they are (as coded) explicitly 3D. The python code is not. Do we think that higher dimension kd tree stuff will ever be needed? Another bonus to the python is the kd tree can be kept in memory between searches, while it would be more difficult to do that with a C module. Granted, building the kd tree typically takes less time than the nearest neighbor searches, but it would save some time.

Thanks!

 _______________________________________________________
sskory at physics.ucsd.edu           o__  Stephen Skory
http://physics.ucsd.edu/~sskory/ _.>/ _Graduate Student
________________________________(_)_\(_)_______________