From: Matthew Kerwin <lists@...>
Date: 2013-06-14T15:00:41+09:00
Subject: Re: Timsort in Ruby

Alphonse 23 wrote in post #1112359:
> Ruby's quicksort function is 207 lines. Timsort is 1301 lines of C.
> http://code.google.com/p/timsort/source/browse/trunk/timsort.c
>
> Shouldn't the Ruby community feel ashamed that Python has a more
> optimized sorting function?

Out of interested, I yanked that C source file from Python, modified
some parameters to fit Ruby's comparison method signature, and built it
into a current ruby-2.1-dev [1].

I then benchmarked it against a bunch of arrays of integers[2], using a
simple `for i in 1..n; array.dup.sort; end` loop.

Note that I tried to MIN_MERGE values, reflecting both the Python and
Java implementations.  These are typical results:

                      ruby_qsort   timsort[32]  timsort[64]
empty                  0.003296     0.003462     0.004511
10, in order           0.008184     0.019551     0.019676
10, reversed           0.010642     0.021260     0.022928
10, random             0.007978     0.024539     0.025238
100, in order          0.018367     0.031840     0.035474
100, reversed          0.018310     0.041987     0.040050
100, random            0.049978     0.141741     0.135564
1,000, in order        0.100423     0.098470     0.101137
1,000, reversed        0.100676     0.130736     0.132880
1,000, random          0.873151     1.997130     2.049663
10,000, in order       0.910810     0.810930     0.860948
10,000, reversed       0.913941     1.109160     1.182836
10,000, random        12.381776    24.416879    24.909807

I know there's object allocation and GC overhead, but it should be the
same for both ruby builds, as they _only_ differ in whether array.c
[line 2313] calls ruby_qsort() or timsort().


[1] https://github.com/phluid61/ruby/compare/timsort
[2] https://gist.github.com/phluid61/5779737

-- 
Posted via http://www.ruby-forum.com/.