Project Euler 4 Attempt to speed up

I played around with the answer code for Project Euler problem 4, which I wrote the other day. http://qiita.com/cof/items/1fa1c2600144520b33f8

problem

The number that gives the same value when read from either the left or right is called the palindromic number..Of the number of palindromes represented by the product of two-digit numbers,The biggest one is 9009=91 x 99.
Then,Find the maximum number of palindromes represented by the product of three-digit numbers.

Code repost Originally written while statement (subtly revised, such as making it a function) The print is commented out because it is executed 100 times to measure the time.

def while1():
    (i,j)=(999,999)
    max=1

    while i>0:
        while j>0:
            k = i*j
            if k <= max: break
            if str(k)==str(k)[::-1]: max=k
            j -= 1
        (i,j)=(i-1,999)
    #print max

At this point, I realized that I could assume i> = j, so I rewrote it accordingly.

def while2():
    (i,j)=(999,999)
    max=1

    while i>0:
        while j>0:
            k = i*j
            if k <= max: break
            if str(k)==str(k)[::-1]: max=k
            j -= 1
        (i,j)=(i-1,i-1) #Only here is different.
    #print max

I tried to make a for statement.

def for1():
    start=999
    max=1
    for i in range(start,0,-1):
        for j in range(i,0,-1):
            k = i*j
            if k <= max: break
            if str(k)==str(k)[::-1]: max=k
    #print max

Here, when measuring the execution time, while2 was the fastest, while1 was next, and for1 was 40% higher than while1, which was a slow explosion. I guessed that calling the range function in the loop was the cause of the delay, and when I wrote the following code, it was a little faster than while1. (Slower than while2)

def for2():
    start=999
    max=1
    L = range(start,0,-1)
    for i in L:
        for j in L[start-i:]:
            k = i*j
            if k <= max: break
            if str(k)==str(k)[::-1]: max=k
    #print max

I changed this to a list comprehension notation.

def for3():
    L=range(999,0,-1)
    ans = max([i*j for i in L for j in L[999-i:] if str(i*j) == str(i*j)[::-1]])
    #print ans

Very simple, but deadly slow. List comprehension is quick to create a list because it can reduce the cost of calling the append () function, but otherwise it seems to be very slow if used as above.

In addition, as an approach different from the above, the following approach was considered. pe04_001.png

I tried to put the above into the code. (Since the above is a basic idea, there are some differences in the details.)

def from999999():
    seed = 999
    max = 999
    min = 99
    ans = 0
    while 1:
        target = seed * 1000 + int(str(seed)[::-1])
        i = max
        while i > min:
            (q, r) =  (target // i, target % i)
            if q > max:
                break
            elif r == 0:
                ans = target
                break
            else:
                i -= 1
        if ans:
            break
        else:
            seed -= 1
    #print ans

As a result, the answer was as large as 900,000 units, and the last code was the fastest. (Run 100 times) pe04_002.png

Today's awareness: Using for in range () in multiple loops seems to increase the cost of calling the range function. Maybe while is faster than for? List comprehension (although it may be badly written) is not suitable for finding sums.

I'm just a Sunday programmer, not an expert, so it's a mystery how correct it is.

Recommended Posts

Project Euler 4 Attempt to speed up
Project Euler 7
Project Euler 47
Project Euler 31
Numba to speed up as Python
Project Euler 38
Project Euler 17
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 32
Project Euler 35
Project Euler 36
Project Euler 46
Project Euler 48
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
How to speed up Python calculations
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
[DRF] Snippet to speed up PrimaryKeyRelatedField
Project Euler 25
How to speed up instantiation of BeautifulSoup
[Project Euler] problem1
How to speed up scikit-learn like conda Numpy
[Python] Do your best to speed up SQLAlchemy
Trial and error to speed up heat map generation
Trial and error to speed up Android screen captures
All up to 775/664, 777/666, 755/644, etc.
Project Euler15 "Lattice Path"
What I did to speed up the string search task
Wrap C/C ++ with SWIG to speed up Python processing. [Overview]
I tried to speed up video creation by parallel processing
Attempt to automatically adjust the speed of time-lapse movies (Part 2)
Mongodb Shortest Introduction (3) I tried to speed up even millions
Part 1 Attempt to code mathematics (∈)
Project Euler Original Method Group 1
Shell to create django project
Deploy django project to heroku
What is Project Euler 3 Acceleration?
Don't write Python if you want to speed it up with Python
[Python] Hit Keras from TensorFlow and TensorFlow from c ++ to speed up execution
Indispensable if you use Python! How to use Numpy to speed up operations!