On 3/24/2011 9:48 AM, Andrea Crotti wrote:
def fib_iter(n):
ls = {0: 1, 1:1}
Storing a linear array in a dict is a bit bizarre
for i in range(2, n+1):
ls[i] = ls[i-1] + ls[i-2]
return ls[max(ls)]
So is using max(keys) to find the highest index, which you already know
(it is n). Actually, fib_iter(0) will return fib_iter(1), and in general
that would be wrong. Above should just be ls[n].
Third, why toss away the array only to recalculate with each call?
Memoizing *is* faster ;-). So do it for the iterative version too.
and what happens is surprising, this version is 20 times slower then the
recursive memoized version.
For the reason Stefan explained and hinted above. Try the following instead:
def fib_iter(n, _cache = [1,1]):
k = len(_cache)
if n >= k:
for i in range(k, n+1):
_cache.append(_cache[i-2] + _cache[i-1])
return _cache[n]
This should be slightly faster than the crazy-key cache for the memoized
recursive version.
--
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
