Python in game development? + recFib

[Mike Fletcher]

The problem with that particular implementation (elegant as it is) is that
you wind up creating a cache of potentially hundreds of thousands of
integers when you only need two for the next value (as far as I can see,
anyway) here is a somewhat faster version of the same algorithm when you're
dealing with fairly large numbers (such as fibonacci (100000)).

8<________ fibonacci.py ___________

def fibonacci (n, cache = [0L, 1L]) :
	for i in range (len (cache), n+1) :
		cache.append (cache [i-1] + cache [i-2])
	return cache [n]
def fibonacci2 (n) :
	if n == 0:
		return 0
	elif n == 1:
		return 1
	else:
		first = 0L
		second = 1L
		for i in xrange (2, n+1) :
			current = first + second
			first = second
			second = current
		return current

if __name__ == "__main__":
	import time
	t = time.clock()
	a = fibonacci( 10000 )
	print 'fibonacci', time.clock()-t

##	t = time.clock()
##	a = fibonacci( 100000 )
##	print 'fibonacci', time.clock()-t
	
	t = time.clock()
	b = fibonacci2( 10000 )
	print 'fibonacci2', time.clock()-t
	
	t = time.clock()
	b = fibonacci2( 100000 )
	print 'fibonacci2', time.clock()-t

	print 'a == b', a==b


and a sample run...
p:\>fibonacci
fibonacci 0.250045676184
fibonacci2 0.136871826762
a == b 1
fibonacci2 11.9150154796
1
1
1
1
2
2


Yay! The optimisation threads return to the Python List :o) !
Enjoy,
Mike


-----Original Message-----
From: tanzer at swing.co.at [mailto:tanzer at swing.co.at]
Sent: Thursday, August 31, 2000 2:31 AM
To: python-list at python.org
Subject: Re: Python in game development? + recFib 



"Darrell Gallion" <darrell at dorb.com> wrote:

> Hacked up Christian's code to get past the stack limit.
> Skipped locking on things like the cache since it's a write once kind of
> thing.
> Guess hacking can pay off.

(snip -- 90 lines of code)

There's an easier way:

def fibonacci (n, cache = [0L, 1L]) :
    for i in range (len (cache), n+1) :
        cache.append (cache [i-1] + cache [i-2])
    return cache [n]
# end def fibonacci

And it's more efficient, too (for n=10000, it's 50% faster than
my version with the dict; for n=16383, it's almost 3 times faster
than your version).

Simple-is-often-faster-than-complex ly,
Christian

-- 
Christian Tanzer                                         tanzer at swing.co.at
Glasauergasse 32                                       Tel: +43 1 876 62 36
A-1130 Vienna, Austria                                 Fax: +43 1 877 66 92


-- 
http://www.python.org/mailman/listinfo/python-list