sdd / kiddo

Kiddo
Apache License 2.0
87 stars 14 forks source link

Perf: refactor within #70

Closed sdd closed 1 year ago

sdd commented 1 year ago

Previously, within was keeping its results in a BinaryHeap and calling its into_sorted_vec method to, well, return a sorted Vec. Whilst a BinaryHeap is great if you are frequently adding and removing items, if your use case is to gradually add all your items, and then sort them all at once, its quicker to just put things in a Vec and then sort the Vec at the end.

Benchmarking shows that this change improves performance by anything from 5 to 60% in practice.

codecov-commenter commented 1 year ago

Codecov Report

Merging #70 (e6b4c9c) into master (e1489a7) will increase coverage by 2.38%. The diff coverage is 92.50%.

:exclamation: Current head e6b4c9c differs from pull request most recent head ea12547. Consider uploading reports for the commit ea12547 to get more accurate results

@@            Coverage Diff             @@
##           master      #70      +/-   ##
==========================================
+ Coverage   83.91%   86.29%   +2.38%     
==========================================
  Files          29       32       +3     
  Lines        3593     3882     +289     
==========================================
+ Hits         3015     3350     +335     
+ Misses        578      532      -46     
Impacted Files Coverage Δ
src/fixed/kdtree.rs 80.64% <ø> (-1.45%) :arrow_down:
src/float/kdtree.rs 69.11% <ø> (-1.31%) :arrow_down:
src/lib.rs 100.00% <ø> (ø)
src/types.rs 30.76% <ø> (ø)
src/nearest_neighbour.rs 46.15% <33.33%> (ø)
src/best_neighbour.rs 46.15% <46.15%> (ø)
src/fixed/distance.rs 53.57% <53.57%> (+30.31%) :arrow_up:
src/fixed/query/within_unsorted_iter.rs 80.14% <80.14%> (ø)
src/float/query/within_unsorted_iter.rs 93.10% <93.10%> (ø)
src/common/generate_best_n_within.rs 100.00% <100.00%> (ø)
... and 17 more

... and 1 file with indirect coverage changes

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more