[SciPy-Dev] Interest in improvements to the cKDTree codebase?

[Jesse Livezey]

Thanks for the feedback. PR for 'sorted' keyword is here
https://github.com/scipy/scipy/pull/8908

With no sorting, count_ball_point() vs. len(query_ball_point()) is
~3x faster for 1d problems,
~25% faster for 3d problems, and
~10% faster for 7d problems.

import scipy.spatial as ss
>
> x = np.random.randn(10000, 1)
> xtree = ss.cKDTree(x)
>
> %timeit xtree.count_ball_point(x, .02, p=np.inf)
> # 21.8 ms ± 190 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
>
> %timeit [len(q) for q in xtree.query_ball_point(x, .02, p=np.inf)]
> # 66.9 ms ± 967 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
>
>
> x = np.random.randn(10000, 3)
> xtree = ss.cKDTree(x)
>
> %timeit xtree.count_ball_point(x, .2, p=np.inf)
> # 42.3 ms ± 1.4 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
>
> %timeit [len(q) for q in xtree.query_ball_point(x, .2, p=np.inf)]
> # 53.1 ms ± 407 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
>
>
> x = np.random.randn(10000, 7)
> xtree = ss.cKDTree(x)
>
> %timeit xtree.count_ball_point(x, 1., p=np.inf)
> # 537 ms ± 857 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)
>
> %timeit [len(q) for q in xtree.query_ball_point(x, 1., p=np.inf)]
> # 587 ms ± 6.17 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


--
Jesse Livezey
he/him/his

On Sat, Jun 9, 2018 at 1:12 PM, Ralf Gommers <ralf.gommers at gmail.com> wrote:

> Hi Jesse,
>
>
> On Tue, May 22, 2018 at 10:56 AM, Jesse Livezey <jesse.livezey at gmail.com>
> wrote:
>
>> Hi everyone,
>>
>> I'm using cKDTrees for a project and noticed two potential ways to
>> improve the code and have written one additional count method that might be
>> useful to others.
>>
>> I have written code and some tests for all three items and can contribute
>> if there is interest.
>>
>> 1) Allowing an array of rs in cKDTree.query_ball_point(). I started a PR
>> here <https://github.com/scipy/scipy/pull/8818>. In principle, this
>> should speed up multiple queries with different rs, but see 2.
>>
>> 2) I noticed that for the cases when cKDTree.query_ball_point() returns
>> large numbers of points (>100), it is faster to loop over queries in
>> python. This is true both with and without my PR. This is largely because
>> single point queries do not sort the return indices, but multi-point
>> queries DO sort them (see details here
>> <https://github.com/scipy/scipy/issues/8838>). Removing the sorted()
>> leads to considerable speedups, but is not backwards compatible. However,
>> the sorted behavior is not in the method description and is not even
>> internally consistent, so maybe it could just be removed or made optional?
>>
>
> I agree with Sturla's reply on the issue; adding a keyword that defaults
> to the current behavior and allows turning off sorting is probably the way
> to go.
>
>
>> 3) I have written a cKDTree.count_ball_point() method that behaves like
>> query_ball_point() but just returns the number of points rather than their
>> indices. This is much faster than calling len(query_ball_point()).
>>
>
> How much faster is it after adding the keyword for (2)?
>
> Cheers,
> Ralf
>
>
> _______________________________________________
> SciPy-Dev mailing list
> SciPy-Dev at python.org
> https://mail.python.org/mailman/listinfo/scipy-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20180625/56eb0f2f/attachment-0001.html>