Language Shootout

[Paul Winkler]

Fredrik Lundh wrote:
> 
> Paul Winkler wrote:
> > Doing it iteratively is much, much faster.
> 
> does your fastest iterative solution beat this one?

That's pretty fast, once I got it to work... but still not as fast as my best
one. 
Yours iis definitely interesting, largely because I don't understand what the
hell it does. If I rename one of the fibs and change the appropriate call to use
the new name, it still computes fibonacci numbers but performance goes way down
as N rises. So you're somehow relying on the duplicated names for speed. That's
a pretty weird optimization technique.

Here's my version:

#!/usr/bin/env python
def fib5(n):
        a, b = 0L, 1L
        for i in range(n):
                a, b = b, a + b
        return b

def main():
        N = int(sys.argv[1])
        print fib5(N)

main()

# end of script


Now let's try them...
first mine:

$ time fibo.py 1000 
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

real    0m0.083s
user    0m0.070s
sys     0m0.010s


Now let's try yours.

$ time fibo_effbot.py 1000
(long traceback snipped)
RuntimeError: maximum recursion depth exceeded

real    0m0.621s
user    0m0.160s
sys     0m0.070s

Not only is mine faster, it computes a result, too. :p
But seriously, let's try yours again, using sys.setrecursionlimit(99999999)

... whoops, now we get OverflowError: integer addition ...
OK, now I've fixed that too like so:
def fib(n):
    if n < 2:
        return 1L # the rest is unchanged...

Let me know if you think there's a better way to let your version handle large
values of N.

Anyway, trying it again with those modifications:

$ time fibo_effbot.py 1000
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

real    0m0.113s
user    0m0.090s
sys     0m0.020s

So that's 33 ms slower than mine for N=1000.
OK, let's try larger values.

$ time fibo.py 10000
(result snipped)
real    0m0.375s
user    0m0.350s
sys     0m0.020s

$ time fibo_effbot.py 10000
(result snipped)
real    0m0.789s
user    0m0.670s
sys     0m0.120s


$ time fibo.py 100000
(result snipped)
real    0m24.663s
user    0m24.370s
sys     0m0.020s

$ time fibo_effbot.py 100000
Segmentation fault (core dumped)



...................    paul winkler   ....................
custom calendars & printing: http://www.calendargalaxy.com
       A member of ARMS:   http://www.reacharms.com
            home page:  http://www.slinkp.com