Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

sort: Strings should use 3-way radix quicksort #28071

Closed
jordancurve opened this issue Oct 8, 2018 · 4 comments
Closed

sort: Strings should use 3-way radix quicksort #28071

jordancurve opened this issue Oct 8, 2018 · 4 comments
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Milestone
Unplanned

Comments

@jordancurve
Copy link

"3-way radix quicksort is the method of choice for sorting strings" – Robert Sedgewick (https://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf , slide 29)

In my tests, 3-way radix quicksort is about twice as fast as Go 1.11's sort.Strings.

Rough demo code: https://play.golang.org/p/KGVIX6Cwha8
@agnivade
Copy link
Contributor

agnivade commented Oct 8, 2018

Please do share your benchmark numbers. We already have tests for those in the standard library. And if you already have a working version, why not send a CL ? ;)

@vdobler @griesemer

@agnivade agnivade changed the title sort.Strings should use 3-way radix quicksort sort: Strings should use 3-way radix quicksort Oct 8, 2018
@agnivade agnivade added Performance NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. labels Oct 8, 2018
@agnivade agnivade added this to the Unplanned milestone Oct 8, 2018
@vdobler
Copy link
Contributor

vdobler commented Oct 8, 2018

@jordancurve Please also pay attention to pathological (or even malicious) inputs. Average runtime is very important but pathological inputs must not result in e.g. quadratic runtime or large space (here stack) overhead.

@gopherbot
Copy link

Change https://golang.org/cl/142797 mentions this issue: sort: use three-way radix quicksort in Strings

@agnivade
Copy link
Contributor

agnivade commented Feb 4, 2019

From the comment in the CL -

I am withdrawing this proposal until the performance regression with sorting long identical strings is resolved. I would like to thank the reviewers for their attention and suggestions. The radix sorting code is available as a stand-alone library at https://github.com/jordancurve/radix.

@agnivade agnivade closed this as completed Feb 4, 2019
@golang golang locked and limited conversation to collaborators Feb 4, 2020
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
4 participants
@vdobler @agnivade @jordancurve @gopherbot