Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ruby is too slow for programming competitions

blog.clifreeder.com

Post reply on HN
Print view View original

21–30 of 254 posts

Re: Ruby is too slow for programming competitions

#21

Post by ClifReeder »

VeejayRampay wrote: post #2

Maybe the result would vary with JRuby or Rubinius (I'd be interested in benchmarks) because not only is Ruby itself not the fastest language, but its main implementation (MRI) is also not the best for speed.

This is a good point that I didn't consider. Running the 'just iterate over the range version' of this code with jruby:

    [master] clifff@fair_and_square: ruby -v
    jruby 1.7.3 (1.9.3p385) 2013-02-21 dac429b on Java HotSpot(TM) 64-Bit Server VM 1.6.0_43-b01-447-11M4203 [darwin-x86_64]
    [master] clifff@fair_and_square: time ruby fair_and_square.rb C-large-1.in.bak

    real	6m39.105s
    user	6m37.762s
    sys	0m19.009s

Re: Ruby is too slow for programming competitions

#22

Post by jdotjdot »

g3rald wrote: post #5

There is a huge difference between Ruby and Go, in terms of performance. I wonder if anyone has any experience with Python, considering that both are interpreted programming languages.

I've has decent experiences with Python in Google Code Jam, with two exceptions. (1) Python can't handle large numbers, so the mere existence of huge integer inputs for the large prime number problem blew up my code since Python could not convert numbers that large. (2) Python is fine with math, but at a certain point of data accumulation, performance just plummets, no matter how good your algorithm is. Overall, though, I haven't had the experience the parent comment did. Either Python works beautifully or it literally just doesn't work, rather than take an hour.

I treat it as a challenge, though, as it forces me to be smarter about my implementation.

Re: Ruby is too slow for programming competitions

#24

Post by macobo »

electrograv wrote: post #8

Wow, 5 minutes in Ruby, and less than a second in Go? I know scripting languages are slow, but it's easy to forget just how much slower. (EDIT: Corrected misread number thanks to dljsjr). I don't want to detract from the article's main point with a cliche "algorithmic optimization beats fine tuning", but I think it's worth mentioning. Unless I'm mistaken, this particular problem can be solved about 10,000,000x more e…

This problem has a quite elegant solution - Suppose you know the fair palindromes (is a palindrome and a root of a palindrome) of length 2*k. Then you can add either a single digit or double that to the center, and test if it's fair. This algorithm generates all the fair palindromes. https://gist.github.com/macobo/5430510

By memory, there were under 50000 such palindromes in range 0..10^100.

Re: Ruby is too slow for programming competitions

#25

Post by schmrz »

hayksaakian wrote: post #7

* competitions based on speed of computation. I'm sure if the competition was based on speed of implementation there would be different conclusions.

Given two developers, one proficient in Ruby and one in Go there would be probably no difference in implementation time for such a trivial problem.

Re: Ruby is too slow for programming competitions

#26

Post by anonymoushn »

macobo wrote: post #24
electrograv wrote: post #8

Wow, 5 minutes in Ruby, and less than a second in Go? I know scripting languages are slow, but it's easy to forget just how much slower. (EDIT: Corrected misread number thanks to dljsjr). I don't want to detract from the article's main point with a cliche "algorithmic optimization beats fine tuning", but I think it's worth mentioning. Unless I'm mistaken, this particular problem can be solved about 10,000,000x more e…

This problem has a quite elegant solution - Suppose you know the fair palindromes (is a palindrome and a root of a palindrome) of length 2*k. Then you can add either a single digit or double that to the center, and test if it's fair. This algorithm generates all the fair palindromes. https://gist.github.com/macobo/5430510 By memory, there were under 50000 such palindromes in range 0..10^100.

This is the real solution and is required for solving the second large.

Re: Ruby is too slow for programming competitions

#27

Post by jt2190 »

mrgordon wrote: post #18
jt2190 wrote: post #10

The article doesn't actually say that performance was one of the judging criteria, and I'm unable to find anything in the code jam rules about this. Can anyone here clarify?

Performance is not technically a criteria but you have eight minutes from the time you download the input data until you have to be done uploading the output data. So if you spend 50 minutes incrementing integers, then you'll get 0 points no matter what :)

Thanks!

Re: Ruby is too slow for programming competitions

#28

Post by mrgordon »

macobo wrote: post #11

In this context, no it's not. One thing that Code Jam does differently (and imho better) is that they give you an input set and you have 8 minutes (or so) to upload the solution. This is expected to give more than enough space for language speed variance. Instead of execution time, coding time is much more precious in such competitions, and Micro-optimizing has it's place, but it's usually not in a programming compet…

Coding time was actually not precious here. They gave about a day to do the qualification round but only eight minutes to run your program once you downloaded the input data, so the round was optimized for writing highly performant code at your leisure and then downloading the data when you are all set to go.

Re: Ruby is too slow for programming competitions

#29

Post by bambax »

I'm not a rubyist but it appears the OP was doing something like this:

  for each range (start to sqr(end))

    for each number in the range

      check if the number is fair and square
If you do this you're checking the same numbers many times (total count of numbers checked is over 3 hundred million calls...)

The right approach is to first compute all fair and square numbers between 0-10^14, store the result, and then simply check how many are found in each range.

It turns out there are only 39 fair and square numbers between 0 and 10^14.

I participated in Code Jam 2013 and passed the qualification round using Python; after precomputing the fair and square numbers, checking ranges was pretty much instantaneous (for large input 1).

Post reply on HN