[jira] [Commented] (LUCENE-10302) PriorityQueue: optimize where we collect then iterate by using O(N) heapify

["David Smiley (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/LUCENE-10302?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17456441#comment-17456441 ] 

David Smiley commented on LUCENE-10302:
---------------------------------------

As an aside; it's weird/annoying to have to subclass this PriorityQueue just to supply the comparator.  Can't we do a Comparator?

I have the start of some code in progress I can share to anyone interested.  I'm not sure when I'll get back to this.

> PriorityQueue: optimize where we collect then iterate by using O(N) heapify
> ---------------------------------------------------------------------------
>
>                 Key: LUCENE-10302
>                 URL: https://issues.apache.org/jira/browse/LUCENE-10302
>             Project: Lucene - Core
>          Issue Type: Improvement
>            Reporter: David Smiley
>            Priority: Major
>
> Looking at LUCENE-8875 (LargeNumHitsTopDocsCollector.java ) I got to wondering if there was faster-than O(N*log(N)) way of loading a PriorityQueue when we provide a bulk array to initialize the heap/PriorityQueue.  It turns out there is: the JDK's PriorityQueue supports this in its constructors, referring to "This classic algorithm due to Floyd (1964) is known to be O(size)" -- heapify() method.  There's [another|https://www.geeksforgeeks.org/building-heap-from-array/]  that may or may not be the same; I didn't look too closely yet.  I see a number of uses of Lucene's PriorityQueue that first collects values and only after collecting want to do something with the results (typical / unsurprising).  This lends itself to a builder pattern that can look similar to LargeNumHitsTopDocsCollector in terms of first having an array used like a list and then move over to the PriorityQueue if/when it gets full (it may not).



--
This message was sent by Atlassian Jira
(v8.20.1#820001)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org