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

51–60 of 254 posts

Re: Ruby is too slow for programming competitions

#51

Post by nostrademons »

xyzzyz wrote: post #37

Sure, I knew Ruby wasn’t going to be zomg fast, but I always assumed that if I chose the right solution and wrote in an efficient manner (memoizing, storing values/lookups that would be used later, limiting search spaces, etc), my ability to write code quickly and concisely mattered more than sheer processing speed. I was wrong. Sure, the author is wrong, but not because Ruby is slow (it is, though). He's wrong, beca…

One of the points of scripting languages is that you can solve the problem quicker, in terms of developer time, by not having to think about it as much. If you have to think about it more, and come up with clever solutions while a faster language just lets you brute-force it, then they haven't really let you solve the problem more quickly.

(That said, programming competitions are a pretty unrealistic subset of what actual software engineering is like. C++ is a fine language for programming competitions, because it's fast, excels at the sort of numeric manipulation that's common there, has a "good enough" standard library with the STL for common tasks featured there, and the common pitfalls of C++ development - memory management and slow build times, for example - won't bite you in programs of competition-length. That doesn't mean the equation doesn't change if you're, say, building a web app or parsing a simple file format.)

Re: Ruby is too slow for programming competitions

#52

Post by omaranto »

jdotjdot wrote: post #22
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, tho…

What do you mean Python cannot handle large numbers? It has an arbitrary precision integer data type built in:

    >>> 3**1000     132207081948080663689045525975214436596542203275214816767783138506080619639097776968725823559509545821006189118620803878014774228964841274390400117588618041128947815623617812548034440554705439703889581746536825491613622083028969185564040848989376093732421718463599386955167650189414350385648747165832010614366132173102768902855220001

Re: Ruby is too slow for programming competitions

#53

Post by bajsejohannes »

For comparison, I translated it pretty directly to Python:

    import sys
    from math import sqrt
    
    def string_palindrome(num):
        s = str(num)
        return s == s[::-1]
    
    sys.stdin.readline() # throw away first line (number of cases)
    
    for count, line in enumerate(sys.stdin):
        found = 0
        start, finish = [int(num) for num in line.split(" ")]
        sqrt_start  = int(sqrt(start ))
        sqrt_finish = int(sqrt(finish))
    
        for x in xrange(sqrt_start, sqrt_finish+1):
            if string_palindrome(x):
                square = x * x
                if string_palindrome(square) and start
For the first 15 test cases I get the following run times:

    pypy 2.0-beta2: 1.6 seconds
    pypy 1.9:       2.1 seconds
    ruby 1.9.3p194: 3.7 seconds
    python 3.3.0:   5.9 seconds
    python 2.7.1:   6.2 seconds
The integer version for checking palindromes was also much slower in python.

Edit: Even though the interger version of _palindrome is slower in pypy, there's another optimization that works there, but is slow in cpython. It brings the run time down to 0.6 seconds!

    def half_string_palindrome(num):
        num_str = str(num)
        num_len = len(num_str)
    
        for i in xrange(0, num_len // 2):
            if num_str[i] != num_str[num_len - i - 1]:
                return False
    
        return True

Re: Ruby is too slow for programming competitions

#56

Post by Luyt »

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.

Actually, Python is compiled (just like Java, C#, Ruby) to bytecode which is executed in a virtual machine. It is the dynamic nature of certain languages that can make them slower than languages that are statically typed.

Re: Ruby is too slow for programming competitions

#57

Post by masklinn »

jdotjdot wrote: post #22
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, tho…

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

Beg pardon?

    >>> 2**2**2**2**2
    [snipped because HN does not allow 20k comments)

Re: Ruby is too slow for programming competitions

#58

Post by minwcnt5 »

The following site allows you to search for people's solutions by language:

http://www.go-hero.net/jam/13/solutions

There are actually several people who solved this problem (including both large inputs) using Ruby.

And for those asking about Python, most Code Jam problems are apparently calibrated to be solvable using Python. Keep in mind that it's one of the languages Google uses internally and Guido used to work there, so they probably want to support it. From https://code.google.com/codejam/problem-preparation.html:

"Where possible, if you allow multiple programming languages, make it so that all languages are fast enough to solve the problem. Occasionally that's impossible; in Code Jam we generally calibrate by making sure a somewhat optimized Python program can solve a problem. Sometimes, though, there's just no way to have Python succeed with the best algorithm and C++ fail with a worse one. In those cases we'll typically decide that sometimes in life, you just need to use a faster programming language. We try to avoid making that decision if we can."

Re: Ruby is too slow for programming competitions

#59

Post by anonymoushn »

ClifReeder wrote: post #45

Hey everyone, thanks for all the input on this. As I mentioned in the post, programming competitions aren't my forte, and I have a lot to learn in that arena. All the feedback on how this should have been done more efficiently is great. In the future, I obviously need to work on coming up with better algorithms for solving these kinds of problems, but I'll probably continue to try and use Go because it's nice to have…

This is definitely a good idea. As the responses here demonstrate, there are many different and independent optimizations available for solving this problem, so it can be useful to fall back to a faster language if you are having a hard time improving your solution.
Post reply on HN