From: Yong Li <gilbertly@...>
Date: 2011-11-27T01:05:27+09:00
Subject: Re: Is high-speed sorting impossible with Ruby?

This counting sort implementation is a great optimization you can do
to solve this particular puzzle. However, many Java implementations of
this still exceeds the time limit.
The solution there is to read in (and write out) in bulks (e.g. in a
100k-byte array), to avoid too many calls to STDIN.gets which is very
slow.


On Sat, Nov 26, 2011 at 11:25 PM, Douglas Seifert <doug@dseifert.net> 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
> a = Array.new(1e6+1, 0)
>
> while n > 0
>  i = STDIN.gets.to_i
>  a[i] += 1
>  n -= 1
> end
>
> n = 0
> while n < 1_000_001
>  times = a[n]
>  n_str = n.to_s
>  while times > 0
>    STDOUT.puts n_str
>    times -= 1
>  end
>  n += 1
> end
>
> -Doug Seifert
>
> On Sat, Nov 26, 2011 at 4:43 AM, Gaurav C. <chande.gaurav@gmail.com> wrote:
>
>> Hi Matthias,
>>
>> Well I tried the tweaks mentioned by you. The sorting is still slow.
>> I'm thinking it's because of the way I'm taking the input? Is there a
>> way to tweak that? Anything faster or better alternative than 'gets'?
>>
>> --
>> Posted via http://www.ruby-forum.com/.
>>
>>
>



-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Li, Yong
Fushan Road 450, Room 9A
Pudong New Area,
Shanghai, 200122
P.R.China

phone: +86-15021003368
email: gilbertly@gmail.com
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=