7
\$\begingroup\$

I'm attempting some Project Euler problems in an attempt to learn Python. While I can get the correct answer quite easily, my programs are quite slow. Project Euler, if doing it correctly, specifies that each program should run in <1 minute. Some of mine take 5-10 mins.

Here is one example.

x=1;
terms=0;
maxTerms=0;
maxTermsNum=0;
for x in range(1,1000000):
    i=x;
    while (i!=1):
        terms+=1;
        if (i%2==0):
            i/=2
        else:
            i=3*i+1
    if (terms>maxTerms):
        maxTerms=terms;
        maxTermsNum=x;
        print(x);
    terms=0;
print("Biggest one: is %s." %maxTermsNum)

It produces the correct answer, but it takes a long long time. How can I speed this up? This is also in 32-bit Windows.

\$\endgroup\$
  • 4
    \$\begingroup\$ Yuck, it looks like you are trying to write C in python \$\endgroup\$ – wim Jan 6 '12 at 0:00
  • 1
    \$\begingroup\$ use xrange instead of range \$\endgroup\$ – TJD Jan 6 '12 at 0:02
  • 2
    \$\begingroup\$ @TJD Since the OP is using the print function, they probably are using python 3 where range is fine. Regardless, the range is not the problem, it's the algorithm implementation \$\endgroup\$ – wim Jan 6 '12 at 0:06
  • 11
    \$\begingroup\$ When a project euler problem runs slowly, it is usually a matter of changing the approach to the problem, and the underlying algorithm, rather than optimizing a few lines of the code. \$\endgroup\$ – jsbueno Jan 6 '12 at 0:08
  • 1
    \$\begingroup\$ @user1092865 - Python does not require semi-colons (unless writing multiple statements on the same line, which is rarely necessary). Also, there is no need to put parentheses around conditionals in your if statements. More spacing would also make this look cleaner (i = x instead of i=x), although that is more opinion. Check out Python's style guide for reference. \$\endgroup\$ – F.J Jan 6 '12 at 0:20
25
\$\begingroup\$

While many of the Project Euler problems can be solved by brute force, this often isn't the fastest way to do them. Usually there is some kind of algorithmic insight that you can apply that will make your solution faster. This kind of insight is independent of programming language - simply running your code through a hypothetical "go-fast compiler" still won't match the speed of the correct algorithm.

In your case, here's a hint. Many of the sequences you calculate look the same as ones you've previously done. How could you use that information to speed up your algorithm?

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ You win, take all the upvotes. \$\endgroup\$ – Fabián Heredia Montiel Jan 6 '12 at 0:14
  • \$\begingroup\$ Hmm, looks like I'll have to come back and redo some of my programs. A few of them took longer to run than they did to write... thanks for your help. \$\endgroup\$ – user1092865 Jan 6 '12 at 0:16
  • 1
    \$\begingroup\$ Another thing worth noting is that most problems can be solved using mathematical concepts/theorems/tricks, which is the main point of the project. \$\endgroup\$ – chiurox Jan 6 '12 at 16:52
2
\$\begingroup\$

If you are under Python 2.x use xrange instead of range for loops.[XRange Doc][Xrange vs range]

A good optimization for big cases of this problem is to start mapping them to avoid recalculating every step. So only if it hits an unknown number it will either multiply or divide and continue. Have a look at the Collatz conjecture and its properties: http://en.wikipedia.org/wiki/Collatz_conjecture

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Maybe instead of a modulus use a binary shift and a subtraction to determine if i is even or odd. Also doing a binary shift once and assigning the value to i if it is even would be better than calculating the division twice.

Also use a lookup table for previously traversed solutions to x:

x=1;
terms=0;
maxTerms=0;
maxTermsNum=0;
prevTerms = dict()
for x in range(1,1000000):
    i=int(x)
    while (i!=1):
        if i in prevTerms:
            terms += prevTerms[i]
            break
        terms+=1
        a = i >> 1
        b = i - (a << 1)
        if (b==0):
            i = a
        else:
            i=3*i+1
    if x not in prevTerms:
        prevTerms[x] = terms
    if (terms>maxTerms):
        maxTerms=terms
        maxTermsNum=x
        print(x)
    terms=0;
print("Biggest one: is %s." %maxTermsNum)

This runs in under 10 seconds. Tested in 2.7 on a 2.8 Ghz Windows 7 with 6 cores (not that cores matter here) machine.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Just for the heck of it I ran this program in PyPy and it ran in 1-2 seconds rather than 4-5 seconds. So PyPy is another avenue to speed up Python programs that only run pure Python code. \$\endgroup\$ – Demolishun Jan 14 '12 at 20:11
0
\$\begingroup\$

There are many ways to speed up a program. I've found it really helps to profile it (see: http://docs.python.org/library/profile.html for more information) so you can see which functions are using up the most time. From there, you can work on optimizing the steps that take up the most time. Another awesome resource is the MIT open courseware course on algorithms, which starts you off with a simple text-file comparison exercise which you modify in steps to increase its speed (see: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/).

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.