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