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„ŗ—‘ 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