From: Roger Pack Date: 2013-06-19T01:15:47+09:00 Subject: Re: Timsort in Ruby Matthew Kerwin wrote in post #1112422: > 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 (as a note, it would be interesting to benchmark both running time, which you have, and "number of compares requires" also). I wonder if the timsort project itself has some benchmark test cases you could use. I know it's supposed to work better with semi-sorted data, maybe try that. Of course, with surprising results like these, it would be interesting to port ruby's sort into the python trunk/core and see if it makes Python faster there (and if so, to ask the Python and timsort people ...):) -roger- -- Posted via http://www.ruby-forum.com/.