Is high-speed sorting impossible with Ruby?

Well, first of all, I’m new to Ruby, and to this forum. So, hello. :slight_smile:

I’ve studied the poignant guide and it really has helped me pick up the
language pretty fast. After that, I started solving some coding puzzles
using Ruby. It just helps a lot to get used to the language I feel.

I’m stuck with one such puzzle. I have solved it very easily since it is
pretty straight-forward, but the solution is being rejected (by the host
website) with the error ‘Time Exceded’! I know that Ruby cannot compete
with the speed of C/C++ but it
has got to be able to answer a tiny puzzle on a website which accepts
solutions in Ruby?

Here’s the link to the puzzle. It’s just a normal sorting.
http://www.codechef.com/problems/TSORT/

And this is my solution
array ||= []
gets.to_i.times do
array << gets
end
puts array.sort

My question is, is there any other way I can achieve high-speed sorting
with Ruby? I’m using the basic Array#sort here, but is there a way to do
it faster (even though it means lot more lines of code)?

Cheers,
Gaurav

Had a quick look at the problem and its comments. It seems that most
time-exceeded solutions are caused by slow i/o instead of sorting.

On Fri, Nov 25, 2011 at 8:06 PM, Gaurav C. [email protected]
wrote:

has got to be able to answer a tiny puzzle on a website which accepts
puts array.sort


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

phone: +86-15021003368
email: [email protected]
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Yong Li wrote in post #1033692:

Had a quick look at the problem and its comments. It seems that most
time-exceeded solutions are caused by slow i/o instead of sorting.

On Fri, Nov 25, 2011 at 8:06 PM, Gaurav C. [email protected]
wrote:

has got to be able to answer a tiny puzzle on a website which accepts
puts array.sort


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

phone: +86-15021003368
email: [email protected]
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Hey Yong Li,

Thanks for the reply. I understand what you said, but could you
elaborate a bit? I mean, has the problem got to do with the host website
or with my code? Should I change anything in my code?

On 25.11.2011 13:06, Gaurav C. wrote:

Here’s the link to the puzzle. It’s just a normal sorting.

You can treat it as a normal sorting puzzle, but you will not be able
to write a good implementation regarding the execution time if you did.

And this is my solution
array ||= []

array is still empty/unassigned, so a direct assignment array = [] would
be sufficient.

gets.to_i.times do
array<< gets
end

well, how about converting the strings returned by gets to integer
first? sorting integers is way faster than sorting strings.

puts array.sort

My question is, is there any other way I can achieve high-speed sorting
with Ruby? I’m using the basic Array#sort here, but is there a way to do
it faster (even though it means lot more lines of code)?

Yes, there is, and I don’t think it requires a lot more code. Think
about sorting the numbers while reading them in, as the quick solutions
tend to approach the problem in this way.

– Matthias

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’?

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

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 S. [email protected]
wrote:

a[i] += 1
end

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: [email protected]
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

On 26.11.2011 16:25, Douglas S. 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’s 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 :slight_smile:

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.

l = STDIN.gets; a[l.to_i] += l

STDOUT.print a * “”

– Matthias

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

“Matthias Wächter” [email protected] 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?

Hi,

Here’s the link to the puzzle. It’s just a normal sorting.
http://www.codechef.com/problems/TSORT/

That has picked up my interest so I’ve used it to create a new project
on GitHub for solving Codechef challenges, starting with the Turbo Sort:

https://github.com/jpedrosa/codechef_takes/tree/master/tsort

To make it more of a challenge I’ve tried to keep the samples more
faithful to the challenge. Beside Ruby I plan to use Dart and Go as well
to practice with them. Dart doesn’t have an optimized I/O yet. :slight_smile:

I’ve gathered some numbers here:

https://github.com/jpedrosa/codechef_takes/blob/master/tsort/notes.md

I also have taken part in another challenge recently and I put Ruby,
Dart and Go fighting one another as well:

https://github.com/jpedrosa/luhnybin/blob/master/notes.md

BTW, I have no idea about the versions used by the Codechef folks to
test the samples sent by the users. Hopefully they are used an
up-to-date version of Ruby. :slight_smile:

Cheers,
Joao

Yong Li wrote in post #1033823:

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.

Exactly! That certainly seems to be the part which needs to be
optimized. Could you share a solution to this? What could we do to avoid
too many calls to STDIN.gets (which is slow)?

On Sun, Nov 27, 2011 at 7:24 AM, Gaurav C. [email protected]
wrote:

Good thing you did, putting it on GitHub. I saw your solution in
‘take.rb’. But currently we need much better algo than that. Because
codechef seems to think that it exceeds ‘5 seconds’. How did you get the
same thing running on GitHub within a second? Also, codechef uses Ruby
1.9. It’s there on their website.


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

I tried playing with Code Chef a few years ago but eventually gave up:

  1. It doesn’t show you a list of what problems you have and haven’t
    solved
  2. I had a lot of trouble getting Ruby to work there
  3. Even getting Java to work was a PITA
  4. The problems are biased for languages like C (data formats, for
    example)
  5. The limits are strict such that you end up having to write bad code
    in
    the name of optimization

Joao P. wrote in post #1033884:

Hi,

Here’s the link to the puzzle. It’s just a normal sorting.
http://www.codechef.com/problems/TSORT/

That has picked up my interest so I’ve used it to create a new project
on GitHub for solving Codechef challenges, starting with the Turbo Sort:

https://github.com/jpedrosa/codechef_takes/tree/master/tsort

To make it more of a challenge I’ve tried to keep the samples more
faithful to the challenge. Beside Ruby I plan to use Dart and Go as well
to practice with them. Dart doesn’t have an optimized I/O yet. :slight_smile:

I’ve gathered some numbers here:

https://github.com/jpedrosa/codechef_takes/blob/master/tsort/notes.md

I also have taken part in another challenge recently and I put Ruby,
Dart and Go fighting one another as well:

https://github.com/jpedrosa/luhnybin/blob/master/notes.md

BTW, I have no idea about the versions used by the Codechef folks to
test the samples sent by the users. Hopefully they are used an
up-to-date version of Ruby. :slight_smile:

Cheers,
Joao

Hi Joao,

Good thing you did, putting it on GitHub. I saw your solution in
‘take.rb’. But currently we need much better algo than that. Because
codechef seems to think that it exceeds ‘5 seconds’. How did you get the
same thing running on GitHub within a second? Also, codechef uses Ruby
1.9. It’s there on their website.

I’ve thrown various solutions up on github here:

https://github.com/seifertd/sort-a-million

Feel free to fork and add more. Below is the result of running all the
solutions I have up there so far. My takeaway from all of this: stick
with
normal Ruby idioms (see the standard_ruby.rb solution) and you will get
pretty close. The rest of the solutions are just optimizing for the
specific problem and doing this kind of thing is only necessary when you
really need the seconds. Also, compiled languages beat interpreted
languages, but we all knew that, didn’t we? We don’t use Ruby for its
performance after all.

$ ./run_all.sh
Generating input file
time ruby count_occurences.rb < million.txt > million_sorted.txt

real 0m1.242s
user 0m1.148s
sys 0m0.088s
time ruby chunked_reads.rb < million.txt > million_sorted_2.txt

real 0m3.484s
user 0m2.703s
sys 0m0.779s
time ruby standard_ruby.rb < million.txt > million_sorted_3.txt

real 0m1.260s
user 0m1.156s
sys 0m0.101s
time ruby build_strings.rb < million.txt > million_sorted_4.txt

real 0m4.431s
user 0m3.834s
sys 0m0.567s
time ruby build_strings_2.rb < million.txt > million_sorted_5.txt

real 0m1.135s
user 0m1.039s
sys 0m0.091s
time sed -n “2,$p” million.txt | sort -n > million_bash.txt

real 0m1.968s
user 0m1.862s
sys 0m0.094s
CONFIRM

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

Douglas S. 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.

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?

Here is the code again. I will put comments inline to try to give
insight
into what I was thinking:

GC.disable

This is a real cheat. By turning off the garbage collector, you don’t
let
the ruby interpreter reclaim memory by deallocating objects that are no
longer used. Normally, the Ruby interpreter periodically runs a garbage
collection loop where it runs through all allocated objects and if they
are
not referenced any more, may free the memory, giving it back to the OS.
During the loop, your code will not run. By turning it off, your
program
can consume lots of memory, especially if it creates many throw away
objects.

n = STDIN.gets.to_i
a = Array.new(1e6+1) {|n| “”}

The above creates an Array of 1,000,001 slots. The block syntax lets
you
provide a default object dynamically. The first time you reference a
particular index in the array, the block is called to allocate the
default
object at that position.

while n > 0
i_str = STDIN.gets
i = i_str.to_i
a[i] << i_str

Here we append a string representation of the value read to string at
the
position in the index. We are creating garbage objects here. Each
string
produced by STDIN.gets, after it is appended (copied) to the string at
position i in the array, is no longer referenced anywhere. Since we
turned
off the garbage collector, the memory used by this string just hangs
around
in the ruby process.

Another interesting thing to note: Thanks to the way we created the
array
above, we start out with a new empty string for each position referenced
in
the array. If we had made the mistake of creating it like this:

a = Array.new(1e6+1, “”)

we would have an array where every position gets the same empty string
as
the default value. We would thus append all values in the input to the
same string … not what we intend.

n -= 1
end

n = 0
while n < 1_000_001
STDOUT.write a[n]
n += 1
end

This just goes through the array and writes out the value at the
position.
If we had used the wrong Array initializer, we would basically be
outputting the entire input set 1,000,000 times.

Hope that helps …

-Doug

Douglas S. wrote in post #1033966:

My takeaway from all of this: stick
with
normal Ruby idioms (see the standard_ruby.rb solution) and you will get
pretty close.

Yea. That really does make sense. The solution in standard_ruby.rb is
clean and simple and by disabling GC, this one was also accepted on
codechef (it showed 13.12 seconds). I also changed ‘readline’ to ‘gets’
and it took 13.00 seconds. :slight_smile:
Maybe ‘gets’ is faster than ‘readline’. Or I think because I changed
‘puts’ to ‘STDOUT.puts’.

On Nov 27, 2011, at 09:51 , Douglas S. wrote:

real 0m1.260s
user 0m1.156s
sys 0m0.101s

I just poked at this. Here’s your code:

GC.disable
count = STDIN.readline.to_i
list = []
while count > 0
list << STDIN.readline.to_i
count -= 1
end
puts list.sort

Some notes:

  1. GC.disable was a good idea here and shaved off a bit (not that much,
    but a worthwhile amount), but will kill you on some of these problems.

  2. You’re growing list as you add to it when you know the size from the
    beginning. Better to do one allocation.

  3. the input data seems to be “honest” (in that the count is actually
    right), so it is ignorable. Knowing this, the real ruby idiomatic way is
    to read the whole thing in in one go and that is faster than yours by
    about 13% on the top end:

$stdin.gets
puts $stdin.readlines.map(&:to_i).sort

Neither solution seems fast enough to reach their arbritrary deadline of
5 seconds (with their data)… but it is good enough for me. I love the
fact that I can write a 1-2 liner and be done and onto the next problem
while others are still bit-twiddling in their lower level languages…

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs