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

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

Comments

@jordancurve
Copy link

@jordancurve jordancurve commented Oct 8, 2018

"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 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 this to the Unplanned milestone Oct 8, 2018
@vdobler
Copy link
Contributor

@vdobler 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

@gopherbot gopherbot commented Oct 17, 2018

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

@agnivade
Copy link
Contributor

@agnivade 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 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.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants
You can’t perform that action at this time.