Re: Is high-speed sorting impossible with Ruby?

On 26.11.2011 16:25, Douglas Seifert wrote:
> Here is a port of the fastest solution on that site in Ruby.  It of course
> underperforms the C# version by a couple of orders of magnitude, but that
> is to be expected, no?  Perhaps it could be tweaked to be faster?
>
>
> n = STDIN.gets.to_i

Great! Using STDIN/STDOUT instead of letting the kernel find them every 
time saves quite some time. Thanks for that hint.

> a = Array.new(1e6+1, 0)
>
> while n > 0

Yeah, sad enough, that’s still way faster than »n.times do« under 1.9.3 …

>    i = STDIN.gets.to_i
>    a[i] += 1
>    n -= 1
> end
>
> n = 0

n is already zero at this point.

> while n < 1_000_001
>    times = a[n]
>    n_str = n.to_s

don’t do n.to_s if times is zero to spare another 20% CPU.

>    while times > 0
>      STDOUT.puts n_str
>      times -= 1
>    end
>    n += 1
> end

My quickest solutions avoid the integer→string conversion in the second 
part at all at the expense of a larger memory footprint and more string 
ops in the first part. More precisely, my first part prepares the array 
such that I don’t even require the loop in the second part. Remember 
that the return value from gets still contains the trailing \n required 
at output time.

> n = STDIN.gets.to_i
> a = Array.new(1e6+1, "")
>
> while n > 0
>   l = STDIN.gets
>   a[l.to_i] += l
>   n -= 1
> end
>
> STDOUT.print a * ""

I am not sure whether I should use a.join instead of a*"", they seem to 
perform similarly on my computer. I used the latter because it looks way 
cooler :)

And, btw, if you want to squeeze out the last 100 msecs of CPU time, 
just throw in some more lines of code and don’t test all the time what 
won’t change anytime soon.

> n = STDIN.gets.to_i
> a = Array.new(1e6+1, "")
>
> while n > 10
>   l = STDIN.gets; a[l.to_i] += l
>   l = STDIN.gets; a[l.to_i] += l
>   l = STDIN.gets; a[l.to_i] += l
>   l = STDIN.gets; a[l.to_i] += l
>   l = STDIN.gets; a[l.to_i] += l
>   l = STDIN.gets; a[l.to_i] += l
>   l = STDIN.gets; a[l.to_i] += l
>   l = STDIN.gets; a[l.to_i] += l
>   l = STDIN.gets; a[l.to_i] += l
>   l = STDIN.gets; a[l.to_i] += l
>   n -= 10
> end
>
> while n > 0
>   l = STDIN.gets; a[l.to_i] += l
>   n -= 1
> end
>
> STDOUT.print a * ""

– Matthias