I added a function radix.SortSlice similar to sort.Slice. Instead of a
comparison function, it takes a function that serves the relevant strings:
// SortSlice sorts a slice according to the strings returned by str.
func SortSlice(slice interface{}, str func(i int) string) {
The performance is pretty good for this one as well. Thanks for the idea
Thomas!
Stefan
On Tuesday, June 13, 2017 at 8:47:36 PM UTC+2, Stefan Nilsson wrote:
>
> That's an interesting challenge! What the algorithm really does is to
> first find a permutation that will sort the string slice, and then apply
> this permutation to the slice. Perhaps it would be possible to return this
> permutation in some cheap usable format.
>
> On Tuesday, June 13, 2017 at 7:56:54 PM UTC+2, Thomas Bushnell, BSG wrote:
>>
>> That's really nice!
>>
>> Consider a case where I am sorting a slice of structs, but the underlying
>> sort is based on a string within the structs. Or, with some other radixable
>> datatype besides strings.
>>
>> Can we figure out an interface (similar to sort.Interface) which would
>> permit a solution for either or both of these cases? The former should be
>> fairly simple to do without sacrificing the speedup; the latter might be
>> trickier.
>>
>> Thomas
>>
>>
>> On Tue, Jun 13, 2017 at 6:20 AM Stefan Nilsson <trollerip...@gmail.com>
>> wrote:
>>
>>> It's well known that radix sort can be faster than comparison-based
>>> methods for string sorting. With that in mind, I wrote this optimized
>>> version of MSD radix sort:
>>>
>>> https://github.com/yourbasic/radix
>>>
>>> It's equivalent to sort.Strings in the standard library and on my
>>> machine it's twice as fast as when sorting King James Bible and four times
>>> as fast for the 1k benchmark in the sort package. Of course I can't promise
>>> similar performance in other settings, but Go get it if you like.
>>>
>>> Stefan
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "golang-nuts" group.
>>> To unsubscribe from this group and stop receiving emails from it, send
>>> an email to golang-nuts...@googlegroups.com.
>>> For more options, visit https://groups.google.com/d/optout.
>>>
>>
--
You received this message because you are subscribed to the Google Groups
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
