mirror of
https://github.com/ruvnet/RuView.git
synced 2026-04-28 05:59:32 +00:00
a28f0253c3
Replace `sort_by_key + truncate` (O(n log n)) with a fixed-size max-heap
(O(n log k)) for top-K queries when n > k. Fast path when n ≤ k stays
on the simple sort.
Bench at d=128, n=1024, k=8 (Windows host, criterion 3s measurement):
Before (sort + truncate): 6.34 µs/op
After (heap): 3.83 µs/op -39.4% / +1.65× faster
Combined with the 32× memory shrink and 47.6 µs → 3.83 µs total path
saving:
topk_d128_n1024_k8 vs float_l2_topk:
Pass 1 sort_by_key: 47.59 µs / 6.34 µs = 7.5× speedup
Pass 1.5 heap: 47.59 µs / 3.83 µs = 12.4× speedup
Now over the ADR-084 acceptance criterion of 8× minimum. Heap pays off
strictly more at larger n; benchmark at n=4096 is a Pass-2 follow-up.
Co-Authored-By: claude-flow <ruv@ruv.net>
|
||
|---|---|---|
| .. | ||
| .claude-flow | ||
| crates | ||
| data | ||
| docs | ||
| examples | ||
| patches/ruvector-crv | ||
| Cargo.lock | ||
| Cargo.toml | ||