From: "Gaurav C." <chande.gaurav@...>
Date: 2011-11-27T22:17:40+09:00
Subject: Re: Is high-speed sorting impossible with Ruby?

"Matthias Wächter" <matthias@waechter.wiz.at> wrote in post #1033841:
> On 26.11.2011 17:05, Yong Li wrote:
>> 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.
>
> Well, time saved when reading 100k chunks of input a time (or even the
> whole file into a single string) is spent twice when it comes to parsing
> them in Ruby. You can either parse byte per byte, or split along the
> line endings.
>
>>   l = src[cur..pos]
>>   a[l.to_i] += l
>>   pos +=1
>>   n -=1
>> end
>>
>> STDOUT.print a.join
>
> Iterating takes about 7.5 seconds on my machine. Can this be done
> quicker when trying to avoid copying the whole string around?
>
>>
>> STDOUT.print a.join
>
> Splitting with ruby techniques takes less than 4 seconds, but my
> quickest solution is done in a little more than one third of that.
>
> BTW: Using core methods for iterating on a line-by-line reading doesn

Your solution does look interesting. I tried running it on codechef, but 
it seems it takes in more memory than Douglas' solution. Here 
http://www.codechef.com/status/TSORT,trashedcoder is the list of 
solutions I tried for the sorting.

BTW you said you iterated the code in 7.5 seconds? How are measuring the 
time in seconds on your machine?

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