Re: Is high-speed sorting impossible with Ruby?

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.

> n = STDIN.gets.to_i
> a = Array.new(1e6+1, "")
>
> src = STDIN.read
> pos=0
> while n > 0
>   cur = pos
>   while src[pos] != "\n"
>     pos +=1
>   end
>   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?

> n = STDIN.gets.to_i
> a = Array.new(1e6+1, "")
>
> src = STDIN.read
>
> while n > 0
>   l, src = src.split("\n",2)
>   a[l.to_i] += l + "\n"
>   n -=1
> end
>
> 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稚 
cost a fortune, it seems to be as quick as my quickest solution with 
single gets calls. It just depends on the assumption that STDIN is 
closed after all lines are fed, as it doesn稚 use the first line telling 
us how many lines are subsequently coming.

> STDIN.gets
> a = Array.new(1e6+1, "")
>
> STDIN.readlines.each do |l|
>   a[l.to_i] += l
> end
>
> STDOUT.print a.join

Matthias