Python in game development? + recFib

[Mike Fletcher]

Actually, the range vs. xrange thing was just a very minor alteration, the
primary change was the use of the "first", "second", and "current" variables
in place of the n-length list cache.  This does make a considerable
difference on my machine, the memory for the list version taking over 155 MB
for a 100,000 run(before bringing my computer to its knees), while the
variable version takes no more than 7.5 MB (before completion).

Strangely, I'm not in the fibonacci-generating business either!  I'm just a
slightly strange designer who jumped at the chance to return the
"optimisation" threads to Python List, and apparently over stepped the
bounds of proper society in doing so.  My apologies.

But in case you're curious, the fibonacci number for 1,000,000 is here (run
time ~24 minutes on a PIII 500):
	http://members.home.com/mcfletch/programming/fibonacci_1000000.txt

Here's the version used for that:
def fibonacci2 (n) :
	if n < 2:
		return n
	else:
		first = 0L
		second = 1L
		for i in xrange (2, n+1) :
			first, second = second, first + second
		return second

Enjoy yourself,
Mike

-----Original Message-----
From: tanzer at swing.co.at [mailto:tanzer at swing.co.at]
Sent: Friday, September 01, 2000 3:07 AM
To: python-list at python.org
Subject: Re: Python in game development? + recFib 



Mike Fletcher <mfletch at tpresence.com> wrote:

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

Well, I'm not in the business of playing with x-large fibonacci
numbers. And sure, one should adapt one's algorithm to the problem
to be solved.

You might overrate the negative effects of using lists of 100000
elements, though. For instance, on my system with 160MB main memory it
hardly makes any visible difference whether you use `xrange (2, n+1)'
or `range (2, n+1)' for n==100000 -- procmeter just shows a tiny
dip in free memory for the `range' version (the speed of your
fibonacci2 is the same for both `range' and `xrange', too).

My-original-point-in-this-thread-wasn't-really-optimization-
of-fibonacci-algorithms, 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