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

151–160 of 254 posts

Re: Ruby is too slow for programming competitions

#151

Post by [deleted] »

ClifReeder wrote: post #32
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…

To clarify, the Go program (which took under a second to run) was doing the same processing as the full Ruby program that took 50 minutes to run.

[deleted]

Re: Ruby is too slow for programming competitions

#152

Post by kgabis »

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.

Why not 1/10e100? Or even less? Go's library support is quite nice already and it's growing really fast.

Re: Ruby is too slow for programming competitions

#153

Post by frehpt »

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.

> Go does't have 1/100000 the amount of libraries and support that Ruby or C does.

That's what they used to say about Java...

Re: Ruby is too slow for programming competitions

#154

Post by entropy_ »

jeffwass wrote: post #149
entropy_ wrote: post #141

Earlier quoted context omitted.

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.

Yes, I could've done that, but my code from C-large-1 already use sqrt() on the bounds of the range and I never thought to change that. Since I was generating the roots instead of the full numbers it seemed natural to iterate over those. If I had thought there might be a problem with sqrt() I might've done that. However, it just never occurred to me. I just ran my C-large-2 solution against C-large-1 and got a correct answer so I assumed I hadn't made mistakes. I only found out about this after the competition was over. Oh well, this was just a qualification round anyway :)

Re: Ruby is too slow for programming competitions

#155

Post by nfm »

frehpt wrote: post #128
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.

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

That's a ridiculous set of alternatives.

Re: Ruby is too slow for programming competitions

#157

Post by vidarh »

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. My MSc dissertation required a lot of computation (weeks of runtime after I'd rewritten critical portions in C++), and I'd do it that way again.

For many types of problems, putting the data into an efficient format before passing it to your C/C++ code is trivial in terms of both difficulty and time spent.

I prototyped everything in Ruby, profiled, and then rewrote a handful of the critical parts in C and C++.

Re: Ruby is too slow for programming competitions

#158

Post by Scaevolus »

pak wrote: post #122
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.

> 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. Agreed. Contrary to what lbrandy said, I've tried it, and it works very well. Writing Ruby extensions in C, or wrapping C libraries for Ruby, is really easy. Wrapping a PNG library for Ruby allowed us to draw about a trillion pixels' worth of images based o…

That's a neat project!

When generating huge numbers of png images, it's worth it to tweak the compression settings. Run png optimizers like optipng/pngcrush on your output, and use the settings it finds.

LodePNG is easy to use, but doesn't let you tweak as many options as libpng.

The tiles I've inspected are 15-30% larger than necessary-- besides using sub-optimal compression heuristics, they include unnecessary metadata (creation/modification time, aspect ratio).

Re: Ruby is too slow for programming competitions

#159

Post by nfm »

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

When you say "magic", what you really mean is "abstraction", which is a more suitable and neutral word to describe the pros and cons of using a higher level language.

Not that I disagree with your premise - if you need to write highly performant code, lower level languages will pretty much always be faster. But abstraction is extremely beneficial in many other circumstances.

Re: Ruby is too slow for programming competitions

#160

Post by vidarh »

jthol wrote: post #147
threeseed wrote: post #139

Earlier quoted context omitted.

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

... of the asylum he's been committed to after having to deal with one too many AbstractFactoryFactory classes.
Post reply on HN