Adding Radix Sort into Phobos

Andrea Fontana via Digitalmars-d digitalmars-d at puremagic.com
Tue Apr 28 08:29:10 PDT 2015


On Tuesday, 28 April 2015 at 10:32:47 UTC, Per Nordlöw wrote:
> On Monday, 27 April 2015 at 20:54:36 UTC, Andrei Alexandrescu 
> wrote:
>> Yah, these are good angles/ideas. I'm curious, how come 
>> radixSort on long is better than quicksort? Conventional 
>> wisdom has it that quicksort is better for large-ish integral 
>> types. What data distributions did you test on? -- Andrei
>
> Randomized using uniform distributions.
>
> I'm using my own random generator module at
>
> https://github.com/nordlow/justd/blob/master/random_ex.d
>
> for randomization. I would like to see something similar in 
> Phobos aswell :)
>
> Compiled with -release -unittest -noboundscheck
>
> byte n:1000000 sort:46679us radixSort:4326us Speed-Up:10.7903
> byte n:1000000 sort:46679us radixSort:4293us Speed-Up:10.8733
> ubyte n:1000000 sort:50003us radixSort:3980us Speed-Up:12.5636
> ubyte n:1000000 sort:50003us radixSort:4384us Speed-Up:11.4058
> short n:1000000 sort:80287us radixSort:14794us Speed-Up:5.427
> short n:1000000 sort:80287us radixSort:14839us Speed-Up:5.41054
> ushort n:1000000 sort:81647us radixSort:14302us Speed-Up:5.70878
> ushort n:1000000 sort:81647us radixSort:14586us Speed-Up:5.59763
> int n:1000000 sort:83754us radixSort:30590us Speed-Up:2.73795
> int n:1000000 sort:83754us radixSort:30458us Speed-Up:2.74982
> uint n:1000000 sort:82657us radixSort:31570us Speed-Up:2.61821
> uint n:1000000 sort:82657us radixSort:30006us Speed-Up:2.75468
> long n:1000000 sort:82028us radixSort:68955us Speed-Up:1.18959
> long n:1000000 sort:82028us radixSort:68668us Speed-Up:1.19456
> ulong n:1000000 sort:83375us radixSort:68099us Speed-Up:1.22432
> ulong n:1000000 sort:83375us radixSort:67611us Speed-Up:1.23316
> float n:1000000 sort:93002us radixSort:22612us Speed-Up:4.11295
> float n:1000000 sort:93002us radixSort:26618us Speed-Up:3.49395
> double n:1000000 sort:94129us radixSort:58590us Speed-Up:1.60657
> double n:1000000 sort:94129us radixSort:64004us Speed-Up:1.47067

Have you done some tests with sorted-data/almost sorted data/etc?



More information about the Digitalmars-d mailing list