Python in game development? + recFib

[Christian Tanzer]

Mike Fletcher <mfletch at tpresence.com> wrote:

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

Oops. You are right. I didn't test the caching version for 100000. The
result on my machine is:

-------------------------------------------------------------------------------
tanzer [python] 2 $ time /usr/bin/python -S fibonacci.py      
Traceback (innermost last):
  File "fibonacci.py", line 26, in ?
    fibonacci (100000)
  File "fibonacci.py", line 22, in fibonacci
    cache.append (cache [i-1] + cache [i-2])
MemoryError


real    1m47.776s
user    0m15.800s
sys     0m24.490s
-------------------------------------------------------------------------------

(after interrupting the program with Ctrl-C).

The memory consumption seems to grow quite non-linearly with n.

10000 is not visible, 20000 a small spike, 40000 a spike more than
twice as big as 30000, 50000 with a spike 1.5 times higher than 40000
(still not swapping), 60000 filling the swap file with about 100 MB
after the calculation has finished (in Python's cleanup?)!

50000 finishes in 10 seconds, 60000 takes almost 4 minutes -- most of
them in the cleanup.

Odd.

Aha. The problem is not the list -- if it were a list of normal
integers, that is. All the long integers gobble up the memory. 

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

I was in a hurry this morning (like most mornings, when I find 150+
messages in my inbox...). Sorry if I sounded gruff.

So now I have a robust fibonacci function I don't need:

def fibonacci (n, max_cache_size = 30000, cache = [0L, 1L]) :
    if n < max_cache_size :
        for i in range (len (cache), n+1) :
            cache.append (cache [i-1] + cache [i-2])
        return cache [n]
    else :
        f_1, f = cache [-2:]
        for i in range (len (cache), n+1) :
            f_1, f = f, f + f_1
        return f

Wouldn't-have-had-that-problem-in-C, 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