[Yt-dev] kdTree

Matthew Turk matthewturk at gmail.com
Wed Jun 17 11:22:27 PDT 2009


> 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.

Okay.  I wouldn't worry about it as long as it works for your purposes
(halo searches.)

> 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.

I don't think we'll need >3, and if we do we'll deal with that as it
arises.  I don't mind writing the wrapper code for the C code to
present the full tree as a single object.  I don't think I'm convinced
that exposing each node would be necessary.

For now, putting in the python version and then in the future writing
the wrapper code for the hop kD-tree seems to be to be the best way
forward.

Thanks, Stephen!

-Matt



More information about the yt-dev mailing list