[Tutor] global variables & recursion (& stackless)
Gregor Lingl
glingl at aon.at
Tue Feb 24 12:44:17 EST 2004
Karl Pflästerer schrieb:
>ACK. After having looked at your second solution I tried a solution
>which makes it IMO clearer how s and t are found (in the original code
>it was a bit hidden IMO).
>
>def gcd (a, b):
> a, b = abs(a), abs(b)
> rem = []
> while b > 0:
> rem.append((a,b))
> a, b = b, a%b
> return a, rem
>
>def st (a, b):
> gc, rem = gcd(a, b)
> rem.reverse()
> s = t = 1
> for a, b in rem:
> s, t = t, s - (a//b)*t
> return gc, (a, s), (b, t)
>
>
>
>
That's a fine solution....
mine was directly derived from alice's, using her recursive approach
and (intentionally) making only slight modifications. Certainly alice
will be pleased
to see her solution now turned into a iterative one.
>The gcd function is nearly the standard solution (only the rem[] list is
>additional).
>
>The st() function then uses that function to compute s and t.
>
>
>Recursion is a very useful technique but in Python sadly not very
>performant (what about Stackless in that regard?).
>
I'v timed the performance of gcd roughly with:
>>> if 1:
t1 = clock()
for a in range(1,1001):
for b in range(1,a):
x = gcd(a,b)
print clock()-t1
This computes approx 500000 gcds
Results:
function Python2.2 Python2.3.3 Python2.3.3-Stackless3.0
ggt-iterative 2.20 s 2.10 s 1.62 s (!)
ggt-recursive 2.40 s 2.45 s 2.30 s
So in this case the performance issue concerning iterative versus
recursive seems to be of minor importance
Regards, Gregor
P.S. time used by the naked loops + assignment:
if 1:
t1 = clock()
for a in range(1,1001):
for b in range(1,a):
x = b
print clock()-t1
needs approx. 0.2s
>That should be told
>anyone who uses recursive algorithms so they are rewritten iteratively
>(if possible).
>
>
More information about the Tutor
mailing list