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

Sean Owen commented on SPARK-21401:
-----------------------------------

What about the time needed to build the queue? insertions are O(log n) instead 
of O(1). quicksort should be nearly optimal when the array is already sorted. 
It just can't be faster to pay the overhead of reheaping to build the queue, 
then to reheap on every poll, vs nearly no copies in quicksort.

As I say, I think you have a bigger optimization here then, which is to avoid 
the queue entirely, if it's just there to collect elements and then traverse 
them in sorted order.

> add poll function for BoundedPriorityQueue
> ------------------------------------------
>
>                 Key: SPARK-21401
>                 URL: https://issues.apache.org/jira/browse/SPARK-21401
>             Project: Spark
>          Issue Type: Improvement
>          Components: ML, MLlib
>    Affects Versions: 2.3.0
>            Reporter: Peng Meng
>            Priority: Minor
>
> The most of BoundedPriorityQueue usages in ML/MLLIB are:
> Get the value of BoundedPriorityQueue, then sort it.
> For example, in Word2Vec: pq.toSeq.sortBy(-_._2)
> in ALS, pq.toArray.sorted()
> The test results show using pq.poll() is much faster than sort the value.
> For example, in PR https://github.com/apache/spark/pull/18624
> We get the sorted value of pq by the following code:
> {quote}
> var size = pq.size
> while(size > 0) {
> size -= 1
> val factor = pq.poll
> }{quote} 
> If using the generally used methods: pq.toArray.sorted() to get the sorted 
> value of pq. There is about 10% performance reduction. 
> It is good to add the poll function for BoundedPriorityQueue, since many 
> usages of PQ need  the sorted value.



--
This message was sent by Atlassian JIRA
(v6.4.14#64029)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@spark.apache.org
For additional commands, e-mail: issues-h...@spark.apache.org

Reply via email to