Ruby is too slow for programming competitions • Hacker News Board

Re: Ruby is too slow for programming competitions

#141

Post by entropy_ » Sun, Apr 21, 2013, 9:31 PM UTC

jeffwass wrote: post #92

nikic wrote: post #20

I also come to the conclusion that Ruby-like languages are just not the right tool for this kind of problem, but it should be pointed out that you would have been able to solve the 10^14 data set easily, even with Ruby. I was solving that problem with PHP and got it running reasonably fast (1s per range) for ranges up to around 10^60. PHP is probably faster than Ruby, but it's still in the same area. The first trick…

I learned python about a month ago and was able to solve all three parts of this problem correctly (part C was the most difficult). My code was poorly optimized, but with some careful forethought, python's bottlenecks were not too problematic. The first two parts were very easy with only brute force by working thru the square root of the full range once, caching the numbers, and using that cache. I don't see why peop…

I also solved in python, however, my code to pre-generate all "fair and square" numbers in the range 1->10^100 only took 6s to run. Didn't even need optimization. I simply constructed the numbers outright, ie, there was no iteration in my code and trying to see if something fit. I just figured out a rule that would generate all those palindromes with no checking. I think that was what they were looking for in that submission.

If anyone is curious, the rule is as follows. Any palindrome where the sum of the squares of the digits add up to strictly less than 10(9 or less) will be the square root of a "fair and square number". From there, I constructed them using a recursive method which finds the first half of numbers fitting that description and mirrors them to get the palindrome.

I ended up getting an incorrect solution on C-large-2 but that was because I failed to realize that I would lose precision when finding the square roots of the bounds of the range. While integers in python can grow indefinitely math.sqrt() will give you a 32bit floating point number which will represent square roots of 10^14 numbers accurately but not square roots of 10^100 numbers. The diff which turns my program into one that gives correct answers has literally 3 changes lines(to use decimal.Decimal instead of the math library for doing square roots).

Re: Ruby is too slow for programming competitions

#142

Post by jeltz » Sun, Apr 21, 2013, 9:31 PM UTC

lbrandy wrote: post #127

Derbasti wrote: post #84

Earlier quoted context omitted.

> having half your product in Ruby and half in C is awful to have to deal with. Why? In many cases, only a tiny fraction of your code needs to be fast. In my experience, it is very reasonable to code that part in some fast language while delegating the bigger (and often more complex) part in a higher level language such as Ruby.

Everyone always agrees with this and, in my experience, has never really tried it. It works better in theory than in practice (or, at a minimum, it works only on a small subset of the types of problems that a naive view might otherwise lead you to believe). The problem is the data isn't organized in a way to be computation efficient, and all the C code in the world isn't going to make chasing pointers to pointers to…

I have tried it and it was both trivial to do and gave large performance gains. The ruby implementation does not add that many levels of indirection.

Re: Ruby is too slow for programming competitions

#143

Post by bvdbijl » Sun, Apr 21, 2013, 9:33 PM UTC

Radim wrote: post #100

bvdbijl wrote: post #93

Earlier quoted context omitted.

It's why IOI ( http://www.ioi2012.org/competition/rules/ ) doesn't allow interpreted languages, because they are (or at least when the competition was first held were) just too slow. If you have only 1-5 seconds of computations time you're going to choose for a compiled language every time

I thought rules were there to discourage unfair advantage , not disadvantage ? Why would you need a rule for that? In any case, I see both python and ruby on the page you linked to, so perhaps I'm missing something.

Well it's just that to support another language they need to make solutions for every problem in that language to test that it's actually possible and they don't want to do that.

and on that page it says:

    Each submitted source program must be written in C, C++ or Pascal, it must be smaller than 100 KB, the evaluation server must be able to compile it in less than 10 seconds and at most 256 MB of memory. No other extensions different than the ones listed above will be run.

They put Python and Ruby on the machines so you can write a script to generate testcases, you can't submit programs written in those languages

Re: Ruby is too slow for programming competitions

#144

Post by nossralf » Sun, Apr 21, 2013, 9:34 PM UTC

PySlice wrote: post #126

nossralf wrote: post #90

Earlier quoted context omitted.

If the goal of the competition is to slice apples, then a knife is pretty good compared to a gun. Or if the competition takes place under water. Or if you're Steven Seagal and the ship where you work is taken over by a splendidly over-acting Tommy Lee Jones and his gun-wielding minions. Execution speed is nice, I don't disagree. But it's not always the be-all and end-all deciding factor for what tool to use to solve…

> bring a knife to a gun fight > If the goal of the competition is to slice apples What?

I disagree with the premise in a similarly nonsensical fashion. (I mentioned neither execution performance nor weapons in my reply.)

The ultimate goal in a competition is to solve the problem within a fixed amount of time. This requires you to actually implement the solution to be able to run it. If you are able to do that more easily with a language that is inferior in execution speed, that will probably be the best strategy. At least compared to using a really fast language that you are not as comfortable with.

Re: Ruby is too slow for programming competitions

#145

Post by entropy_ » Sun, Apr 21, 2013, 9:36 PM UTC

bvdbijl wrote: post #36

nikic wrote: post #20

I also come to the conclusion that Ruby-like languages are just not the right tool for this kind of problem, but it should be pointed out that you would have been able to solve the 10^14 data set easily, even with Ruby. I was solving that problem with PHP and got it running reasonably fast (1s per range) for ranges up to around 10^60. PHP is probably faster than Ruby, but it's still in the same area. The first trick…

Yep, in a competition you want a language that had as little magic as possible. Languages like Ruby (not necessarily dynamic languages!) are just not really suitable for it

I've been taking part in GCG since ~2008 now. I have only once encountered a problem where my solution in python was too slow but an equivalent one in C would've been fast enough. Though just barely(my python solution ran in ~10min, the C one I wrote later ran in 5min, the time limit was 8min). In that particular case, there was a more efficient algorithm which we were expected to find to solve the problem(ie, my brute force-ish solution was not anticipated and it would've been "cheating" if it had actually worked) and I didn't find it.

In general, I'd much rather be able to implement my solutions as quickly as possible as the challenge is usually in 1) finding the correct algorithm and 2) implementing it correctly and fast. If you can do that, choice of language usually doesn't matter unless in some of the problems you might get in the finals(I've never gotten that far, I usually rank somewhere in the top 2000). Also, for me, the ease with which I get things like arbitrary-size integers, sets and dictionaries far outweighs any speed gains from something like C++.

Re: Ruby is too slow for programming competitions

#146

Post by jonhohle » Sun, Apr 21, 2013, 9:36 PM UTC

lbrandy wrote: post #127

Derbasti wrote: post #84

Earlier quoted context omitted.

> having half your product in Ruby and half in C is awful to have to deal with. Why? In many cases, only a tiny fraction of your code needs to be fast. In my experience, it is very reasonable to code that part in some fast language while delegating the bigger (and often more complex) part in a higher level language such as Ruby.

Everyone always agrees with this and, in my experience, has never really tried it. It works better in theory than in practice (or, at a minimum, it works only on a small subset of the types of problems that a naive view might otherwise lead you to believe). The problem is the data isn't organized in a way to be computation efficient, and all the C code in the world isn't going to make chasing pointers to pointers to…

I agree with it and have implemented it.

After profiling a backfill script which was looking like it was going to take about two weeks to run, I found an area where certain bit-twiddling was being done which was extremely slow in Ruby. I rewrote this section in C, and was able to make this section 1000x faster then the ruby equivalent (this was MRI 1.8.5 several years ago). The total runtime for the script was brought down to about 8 hours (from about 165 TPS to around 7,000 TPS).

Fortunately, I've found that Ruby makes it exceptionally easy to write C extensions, and I often think of reusing C libraries in cases where I'm worried about performance.

Re: Ruby is too slow for programming competitions

#147

Post by jthol » Sun, Apr 21, 2013, 9:36 PM UTC

threeseed wrote: post #139

frehpt wrote: post #128

Earlier quoted context omitted.

Option A: -Write your application in Go Option B: -Write application in Ruby -Profile Ruby application to identify code to be rewritten in C -Learn C if you don't already know it -Rewrite various parts of your application in C -Run Valgrind to search for memleaks -Ensure that your target systems all have required libs installed Option A seems much simpler...

Go does't have 1/100000 the amount of libraries and support that Ruby or C does. Option A only seems simpler because you ignore the time/complexity in coding the task at hand.

... and the Java programmer laughs in the corner (Let's not talk about generics though).

Re: Ruby is too slow for programming competitions

#148

Post by gnuvince » Sun, Apr 21, 2013, 9:38 PM UTC

darkgray wrote: post #117

gnuvince wrote: post #115

Earlier quoted context omitted.

I'm still on Go 1.0.2. However, I strongly doubt that having 1.1 yields the correct result in the amount of time that the article boasts; I rewrote the program in C (direct translation), and with both clang and gcc, I get timings of around 2m05s. It's hard to believe that for a CPU-bound task, a Go program would be 200x faster than a C program.

I'd agree it's dubious, but I was mostly commenting on the "correctness" of the code. It'd work on Go 1.1, so it's technically "correct". Sometimes. :)

Fair enough.

Re: Ruby is too slow for programming competitions

#149

Post by jeffwass » Sun, Apr 21, 2013, 9:42 PM UTC

entropy_ wrote: post #141

jeffwass wrote: post #92

Earlier quoted context omitted.

I learned python about a month ago and was able to solve all three parts of this problem correctly (part C was the most difficult). My code was poorly optimized, but with some careful forethought, python's bottlenecks were not too problematic. The first two parts were very easy with only brute force by working thru the square root of the full range once, caching the numbers, and using that cache. I don't see why peop…

I also solved in python, however, my code to pre-generate all "fair and square" numbers in the range 1->10^100 only took 6s to run. Didn't even need optimization. I simply constructed the numbers outright, ie, there was no iteration in my code and trying to see if something fit. I just figured out a rule that would generate all those palindromes with no checking. I think that was what they were looking for in that su…

You don't need to use Decimals. When you find all square roots of fair and square numbers, don't cache them but their squares (ie, the fair and square numbers themselves).

Then for each of the 1000 inputs, you run through the set of 46k fair and square numbers, counting how many are between A and B. no square roots required.

Re: Ruby is too slow for programming competitions

#150

Post by entropy_ » Sun, Apr 21, 2013, 9:43 PM UTC

georgemcbay wrote: post #107

nossralf wrote: post #90

Earlier quoted context omitted.

If the goal of the competition is to slice apples, then a knife is pretty good compared to a gun. Or if the competition takes place under water. Or if you're Steven Seagal and the ship where you work is taken over by a splendidly over-acting Tommy Lee Jones and his gun-wielding minions. Execution speed is nice, I don't disagree. But it's not always the be-all and end-all deciding factor for what tool to use to solve…

I don't think the parent post (which I totally agree with) was saying that you must always decide by picking an inherently fast language, but rather if you decide to pick one whose execution time is not inherently fast to enter a competition where execution time is factored you will start with a major disadvantage. That doesn't mean you'll lose (ala your Steven Seagal analogy), maybe you're so much better than everyo…

My experience with GCJ has been that raw execution speed almost never matters as long as you have the right algorithm.

In the case of the OP, for example a trivial optimization(the kind you do without even thinking in these competitions) would've brought his execution time down 10000x. Basically, you are asked about the number of "fair and square" numbers in a certain range, over and over again, in 10000 different cases. He could have just taken his solution, pre-generated all those numbers once and then ran all those test cases by counting in that pregenerated list, instead of generating it for every single test case(all 10^5 of them). It turns out, that in the whole span of 1->10^14 there is only 39 such numbers and it would've taken his program probably less than a minute to generate all of them(I'm being generous here, since it ran 10^5 test cases in 53min).

In fact, if you read the problem analysis later provided by google you will see that in fact you were expected to make this optimization to solve the problem. The fact that C-small had 100 test cases, C-large-1 had 10^5 and C-large-2 had 100 should've been a strong hint that C-large-1 required some pre-caching across test cases.