Home Original page

Speeding up a script -- looking for ideas

Jeff Epler jepler at unpythonic.net
Sun Oct 20 09:29:27 EDT 2002 
On Sun, Oct 20, 2002 at 10:57:54AM +0200, William wrote:
> without looking at your algorithme, it's typical think where psyco will
> help you :
> 
> without psyco :
> 
> [(13832, 2, 24), (13832, 18, 20)]
> 
> Time's up! 16.6103349924 seconds have elapsed
> EEEEEEEEEnnnnnnnnnnddddddddd

Well, looking at the algorithm, there's no reason to loop on values of c,
then loop on values of a, then loop on values of b.  Why not loop on c,
then on a, then find whether there's a value of b that will satisfy the
condition?  

Your program on my system, no psyco:
    Time's up! 6.24721693993 seconds have elapsed
My program on my system, no psyco:
    (13832, [(2, 24), (18, 20)])
    1
    real    0m1.645s
(both on 10000-20000)

from __future__ import generators

r = range
def f(rr, n):
    for c in rr:
	l = []
	for a in r(1, int(c**(1/3.0))+2):
	    a3 = a**3
	    if a3 > c: break
	    b = int((c - a**3)**(1./3)+.5)
	    if b < a: break
	    #print a, b, c
	    if a**3 + b**3 == c:
		l.append((a, b))
		if len(l) == n:
		    yield c, l
		    break

def main():
    count = 0
    for item in f(r(10000, 20000), 2):
	count = count + 1
	print item
    print count

main()
More information about the Python-list mailing list