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

Yibo Cai commented on ARROW-7587:
---------------------------------

Did some benchmark again std::sort(), std::partial_sort() and 
std::nth_element().
 Code at [https://github.com/cyb70289/mytests/blob/master/cpp/sort-nth.cc].

Tested sorting 10,000,000 elements, partial_sort first 1/3 elements, and 
nth_element 1/3 element. Below is the result:
 std::sort(): 1.90883 s
 std::partial_sort(): 4.68398 s
 std::nth_element(): 0.114514 s

std::partial_sort is much slower than std::sort when the number of elements to 
be partially sorted is large.
 *std:nth_element() is order faster, should be the best choice.*

PS: why partial_sort can be slow
 
[https://stackoverflow.com/questions/45455345/performance-of-stdpartial-sort-versus-stdsort-when-sorting-the-whole-ran]
 
[https://www.quora.com/Why-is-STLs-partial_sort-slower-than-the-asymptotic-lower-bound]

> [C++][Compute] Add Top-k kernel
> -------------------------------
>
>                 Key: ARROW-7587
>                 URL: https://issues.apache.org/jira/browse/ARROW-7587
>             Project: Apache Arrow
>          Issue Type: New Feature
>          Components: C++ - Compute
>            Reporter: Yibo Cai
>            Assignee: Yibo Cai
>            Priority: Minor
>
> Add a kernel to get top k smallest or largest elements (indices).
> std::paiital_sort should be a better solution than sorting everything then 
> pick top k.



--
This message was sent by Atlassian Jira
(v8.3.4#803005)

Reply via email to