Re: Is high-speed sorting impossible with Ruby?

On Nov 27, 2011, at 09:51 , Douglas Seifert wrote:

> Feel free to fork and add more.  Below is the result of running all the
> solutions I have up there so far.  My takeaway from all of this: stick with
> normal Ruby idioms (see the standard_ruby.rb solution) and you will get
> pretty close.  The rest of the solutions are just optimizing for the
> specific problem and doing this kind of thing is only necessary when you
> really need the seconds.  Also, compiled languages beat interpreted
> languages, but we all knew that, didn't we? We don't use Ruby for its
> performance after all.
> 
> time ruby standard_ruby.rb < million.txt > million_sorted_3.txt
> 
> real 0m1.260s
> user 0m1.156s
> sys 0m0.101s

I just poked at this. Here's your code:

  GC.disable
  count = STDIN.readline.to_i
  list = []
  while count > 0
    list << STDIN.readline.to_i
    count -= 1
  end
  puts list.sort

Some notes:

1) GC.disable was a good idea here and shaved off a bit (not that much, but a worthwhile amount), but will kill you on some of these problems.

2) You're growing list as you add to it when you know the size from the beginning. Better to do one allocation.

3) the input data seems to be "honest" (in that the count is actually right), so it is ignorable. Knowing this, the real ruby idiomatic way is to read the whole thing in in one go and that is faster than yours by about 13% on the top end:

  $stdin.gets
  puts $stdin.readlines.map(&:to_i).sort

Neither solution seems fast enough to reach their arbritrary deadline of 5 seconds (with their data)... but it is good enough for me. I love the fact that I can write a 1-2 liner and be done and onto the next problem while others are still bit-twiddling in their lower level languages...