Re: Is high-speed sorting impossible with Ruby?

Douglas Seifert wrote in post #1033963:
> A big gain can be had by disabling the garbage collector.  Here is my
> best
> effort yet (taking into account the ideas so far in the thread):
>
> GC.disable
> n = STDIN.gets.to_i
> a = Array.new(1e6+1) {|n| ""}
>
> while n > 0
>   i_str = STDIN.gets
>   i = i_str.to_i
>   a[i] << i_str
>   n -= 1
> end
>
> n = 0
> while n < 1_000_001
>   STDOUT.write a[n]
>   n += 1
> end

Whoa! This one worked! The solution was accepted on codechef. But the 
time taken is way beyond the limit of '5 seconds' for this problem (9.87 
seconds). I wonder how it accepted :? I even submitted it the second 
time without disabling the garbage collector. It worked again.

I thought maybe they have changed some rules on the website so I 
submitted the old solutions again. But the result was same with them 
'time exceeded'.

So I'm reading your code and trying to figure out what cracked the 
problem. Could you share some insights? Why to disable the GC? What idea 
should one take away from other parts of your code?

Cheers.

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