Ruby is too slow for programming competitions

Re:Ruby is too slow for programming competitions by bambax on Sunday April 21, 2013 @02:26PM (#5585780)

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).

[ Parent | on HN ]

Re:Ruby is too slow for programming competitions by eric970 on Sunday April 21, 2013 @03:12PM (#5585985)

Sounds right to me as well. But hey, isn't it much easier to blame the language and its VM? Or interpreted languages in general?

[ Parent | on HN ]

Re:Ruby is too slow for programming competitions by Luit on Sunday April 21, 2013 @04:20PM (#5586259)

A slightly more interesting approach: find out all non-overlapping ranges you need to test, and then run the fair-and-square generator, testing each to check in which of the ranges it should be put, finally combining the sub-ranges to make the ranges asked for. My (not particularly optimized) Go solution ran through the C-large-1.in set in 3 odd seconds.

[ Parent | on HN ]