[
https://issues.apache.org/jira/browse/ARROW-10899?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17332609#comment-17332609
]
Kirill Lykov edited comment on ARROW-10899 at 4/26/21, 5:17 PM:
----------------------------------------------------------------
I'm continuing experiments with MSD sort. Please ignore code style sine it is
for experiments. I'm using gist as log for optimizations
https://gist.github.com/KirillLykov/c641e63adfd68591bafbdb342f75d141
Each comment in this gist is an iteration of optimization. Please let me know
someone has ideas to try. I was planing try to get rid of recursion by using
stack explicitly. Don't see any other big things to do with it.
!all_random_wholeRange.png!height=350,width=350!
Idea by [~michalno] to use another sorting algorithm if the size of the
subarray to sort is smaller than some level surprisingly doesn't work well on
my array (for now only uniform distribution).
was (Author: klykov):
I'm continuing experiments with MSD sort. Please ignore code style sine it is
for experiments. I'm using gist as log for optimizations
https://gist.github.com/KirillLykov/c641e63adfd68591bafbdb342f75d141
Each comment in this gist is an iteration of optimization. Please let me know
someone has ideas to try. I was planing try to get rid of recursion by using
stack explicitly. Don't see any other big things to do with it.
!all_random_wholeRange.png!
Idea by [~michalno] to use another sorting algorithm if the size of the
subarray to sort is smaller than some level surprisingly doesn't work well on
my array (for now only uniform distribution).
> [C++] Investigate radix sort for integer arrays
> -----------------------------------------------
>
> Key: ARROW-10899
> URL: https://issues.apache.org/jira/browse/ARROW-10899
> Project: Apache Arrow
> Issue Type: Wish
> Components: C++
> Reporter: Antoine Pitrou
> Assignee: Kirill Lykov
> Priority: Major
> Attachments: Screen Shot 2021-02-09 at 17.48.13.png, Screen Shot
> 2021-02-10 at 10.58.23.png, all_random_wholeRange.png,
> all_random_wholeRange.png, all_random_wholeRange.png
>
>
> For integer arrays with a non-tiny range of values, we currently use a stable
> sort. It may be faster to use a radix sort instead.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
