[SciPy-Dev] Enhancements to scipy.spatial.cKDTree

Sturla Molden sturla@molden...
Sat Jul 14 18:29:14 CDT 2012

Den 15.07.2012 00:36, skrev Sturla Molden:
> Thanks. On Windows 64, query_pair returns bad results depending on the 
> size of the tree. I don't know why but Patrick's code hade the same 
> problem.

Which brings me to the other issue I'd like to discuss...

In its current state, Patrick's enhancement to cKDTree (IMHO) is close 
to unmaintainable. It might be 'fast', but it is not estetically nice 
looking code (no pun intended),  about 2500 lines of low-level C 
masquerading as Cython, very difficult to read and follow with respect 
to logic, it was full of bugs (and might still be), and still don't pass 
all the tests on my computer (even though I have been debugging it quite 

Who is going to maintain it? Patrick? Ralph? Anne? (I am not 

On the other hand, Anne's KDTree.py is an example of very beautiful 
Python code, and very easy to read and understand. KDTree is also robust 
and rather bug-free, after having been tested for quite a long time, and 
more or less feature-complete for a KDTree. But it is a bit slow, 
courtesy to Python...

How fast do we need it to be?

I think it might be better to just gently 'Cythonize' out the worst 
bottlenecks in KDTree.py, but leave the rest as it is. It might not be 
equally fast as Patrick's rewrite of cKDTree enhancement, but will be 
100 times easier to maintain, and probably "fast enough" for most usecases.

cKDTree was intended as a very fast kd-tree for nearest-neighbor 
queries. It was never intended as general-purpose kd-tree like, well, 
KDTree. Currently in SciPy master it is very "lean and mean" for its 
particular purpose. (It could still use some minor updating, such as 
64-bit support.)

I think at least this should be discussed before this major rewrite is 
pulled into SciPy master. I am not saying Patrick's rewrite is bad anbs 
should not be pulled into SciPy. But I don't think we should drop code 
into SciPy if it will never be properly maintained. It must be 
maintainable for years ahead.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-dev/attachments/20120715/ef6ab788/attachment-0001.html 

More information about the SciPy-Dev mailing list