StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow is Array#sort in Ruby so quick?
text
Body
copied!<p>C# has BitArray, C has bit fields.. I couldn't find an equivalent in the Ruby core. Google showed me a <code>BitField</code> class that Peter Cooper has written for the same.</p> <p>I've been reading Jon Bentley's Programming Pearls and while trying out one of the first examples, which deals with a BitMap sort - I needed a type that is an array of bits. I used Peter's class </p> <pre><code>class BitMapSort def self.sort(list, value_range_max) bitmap = BitField.new(value_range_max) list.each{|x| bitmap[x] = 1 } sorted_list = [] 0.upto(value_range_max-1){ |number| sorted_list << number if (bitmap[number] == 1) } sorted_list end end </code></pre> <p>Running this on a set of 1M unique numbers in the range [0, 10,000,000), produced some interesting results,</p> <pre><code> user system total real bitmap 11.078000 0.015000 11.093000 ( 11.156250) ruby-system-sort 0.531000 0.000000 0.531000 ( 0.531250) quick-sort 21.562000 0.000000 21.562000 ( 21.625000) Benchmark.bm(20){|x| x.report("bitmap"){ ret = BitMapSort.sort(series, 10_000_000);} x.report("ruby-system-sort"){ ret = series.sort; } x.report("quick-sort"){ ret = QuickSort.sort( series, 0, series.length-1); } } </code></pre> <p>How is ruby's default sort 22x faster than 1M BitField.set + 1 loop over a 10M bit vector ? Is there a more efficient bit field / array in Ruby ? How does Ruby's default sort achieve this level of performance.. is it jumping into C to get this done?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload