Description
The legacy sorting logic in NeighborArray below takes long N^2 in worst case, as it is a simple insertion sort and pushes/copies the rest of the array towards the end for each uncheckedIndex.
|
int[] sort(RandomVectorScorer scorer) throws IOException { |
I think it has a lot of scope for improvement and I'm attaching a PR below and opening a discussion for same.
Description
The legacy sorting logic in NeighborArray below takes long N^2 in worst case, as it is a simple insertion sort and pushes/copies the rest of the array towards the end for each
uncheckedIndex.lucene/lucene/core/src/java/org/apache/lucene/util/hnsw/NeighborArray.java
Line 152 in d87b4f3
I think it has a lot of scope for improvement and I'm attaching a PR below and opening a discussion for same.