abscondment/clj-kdtree — pull request #7 by nbeloglazov (2013-08-15 13:33:16+00:00)
Title: Optimization.

I've optimized kd-tree implementation. I compared some functions (especially `nearest-neighbor`) with [Java ML's](http://java-ml.sourceforge.net/) implementation.

### Benchmark
I benchmarked implementations on tree of 5000 random points using
For benchmarking I created a tree with 5000 random points and tested all functions using [Criterium](https://github.com/hugoduncan/criterium). Check `test/kdtree/bench.clj` file. It contains all code I used for benchmarking. From java ml's kdtree I used only `nearest neighbor` function because.

* Java ML implementation doesn't have methods to create tree from collection of points
* Java ML implementation is mutable. Comparison of `insert` and `delete` methods on mutable data structure is unfair.

### Results

| Impl | Nearest neighbor | Build | Find min | Insert | Delete |
| --- | --: | ---: | --: | --: | --: |
| Clojure new | 51.92 µs | 67.66 ms | 79.39 µs | 3.01 µs | 324.74 µs |
| Clojure old | 898.00 µs | 77.18 ms | 351.06 µs | 10.55 µs | 357.78 µs |
| Java ML | 12.85 µs | - | - | - | - |

### What changed

* All points converted to double arrays and arrays methods (`aget`, `alength`) are used to work with them.
* `dist-squared` works only with double arrays now.
* `assoc-in` and `update-in` are slower than creating new Node via constructor `(Node. bla bla bla)` though it much more concise. I switched back to constructor.
* Removed `depth` field from `Node`. I didn't found any usage of it in code.
* Extracted all functions that takes additional `depth` argument to *-internal functions. Internal functions are private. I think API is cleaner this way because user should not used functions with `depth` argument because he doesn't not what is it anyway.
* In `nearest-neighbor` function I used transient vector to collect `n` closest points. it's faster than sorting points and taking n first on each recursive call. It may be improved further: Java ML uses binary heap to collect `n` points. It allows to add new point in `O(log n)` where with transient vector it uses linear search and we get `O(n)`. The problem is that I don't know how to implement efficient binary heap in clojure. I think it must be mutable to achieve good performance. Nevertheless transient vector are pretty good too compared to sorting on each recursive call.
* In `project.clj` I've added depedenency to criterium and java ml lib in `:dev` profile so it can be easily benchmarked by anyone.
* `test/kdtree/bench.clj` contains becnharmk code.