imglib / imglib2

A generic next-generation Java library for image processing
http://imglib2.net/
Other
302 stars 93 forks source link

Refactor/split kdtree #334

Closed minnerbe closed 6 months ago

minnerbe commented 1 year ago

As discussed in #333, I made some attempt to refactor the implementation of KDTree. In particular:

The benchmarks with 1M points look very similar to those before the refactoring with slightly worse timings. Some of the difference, however, might be explained by my laptop's current temperature and power settings. Unfortunately, I don't have access to a more stable test hardware to do a proper comparison right now.

KDTreeBenchmark.createKDTree            avgt    8  322.834 ± 23.371  ms/op
KDTreeBenchmark.kNearestNeighborSearch  avgt    8   99.910 ±  6.377  ms/op
KDTreeBenchmark.nearestNeighborSearch   avgt    8   64.412 ±  6.320  ms/op
KDTreeBenchmark.radiusNeighborSearch    avgt    8   66.110 ± 11.759  ms/op

Although there are still a few rough edges, I am quite satisfied with how this turned out. In particular, the other searches work without adaptation and for the serialization experiments only very minor and obvious changes are necessary.

What do you think @tpietzsch ?

tpietzsch commented 6 months ago

I like the split of KDTreePositions into a separate class. KDTreeImpl and the searches only needs that, very neat!

I reverted the split of KDTreeValues. It looked weird to me because it doesn't have much to do with KDTree, it's more "1D RAI like thing", and in the end I just put it back into KDTreeData.

tpietzsch commented 6 months ago

I merged this into #333

minnerbe commented 6 months ago

I agree, splitting KDTreeValues out of KDTreeData did look a bit awkward. Thanks for considering this!