harrismh777 wrote: > Peter Otten wrote: >> For the record, the one true way to implement the Fibonacci series in >> Python is >> >>>>> >>> def fib(): >> ... a = b = 1 >> ... while True: >> ... yield a >> ... a, b = b, a+b # look ma, no temporary variable > > [snip] > > I created two scripts, stressed them a bit, and then timed: > I called the two scripts fib.py and fib2.py... here they are: > > ==================begin fib.py============================ > #!/home/marcus/bin/python3 > def fib(): > a=b=1 > while True: > yield a > a,b=b,a+b # look ma, no temporary variable > > from itertools import islice > flist=list(islice(fib(), 100000)) > ==================end fib.py============================== > > > ==================begin fib2.py=========================== > #!/home/marcus/bin/python3 > def fib(i=1): > a=b=1;l=[] > for j in range(0,i): > l.append(a) > a,b = b,a+b # look ma, I can do it too.... > return l > > list=fib(100000) > ==================end fib2.py============================= > > [ TIMES ] 1 core, 1.6 Ghz, 3196 bogomips > > marcus@shire:~/Python3$ time ./fib.py > > real 0m2.775s > user 0m1.908s > sys 0m0.820s > > > marcus@shire:~/Python3$ time ./fib2.py > > real 0m2.796s > user 0m1.916s > sys 0m0.824s > > > > You will notice first that the times are *almost* identical. So, > down under the heart of python, something is wrong. (never mind)
Well, fib(10**5)[-1] has over 20000 digits, so I'd expect the runtime to be dominated by long-integer arithmetic. And that is identical for both scripts. You will get some improvement from switching to gmpy. > But the really interesting thing I found is that when I coded away > the temporary reference, 100ms of user time moved over to sys time. doh, > must be that 'somewhere' a 'temporary' reference had to be created... > and it doesn't look like it's optimized very well... > > But, this should also go to show you... that there is *never* just > one obvious way to do anything... contrary to the ZEN of Python... ;-) I take that as an indication that you are not Dutch ;) > On the other hand, I am very much interested in "yield," because of > its obvious persistent state, On the other hand, I don't like you fib() > function because it does not encapsulate the fib generator. I suppose > you are considering whatever module is holding the fib() code as the > encapsulation, but I thought the idea from the OP was to create a > generator that could be called and return a list... this is a little > goofy: > list(islice(fib(), X)) > > when what was wanted is: > > list = fib(X) I would not seriously recommend list(islice(generator, stop)) in that case, either, but I think my fib() is a good building block: >>> from itertools import islice >>> def cached_series(g): ... items = [] ... def f(n): ... if n <= len(items): ... return items[:n] ... items.extend(islice(g, n-len(items))) ... return items[:n] ... return f ... >>> def _fib(): ... a = b = 1 ... while True: ... yield a ... a, b = b, a + b ... >>> def _noisy(): ... for x in _fib(): ... print "calculating", x ... yield x ... >>> fib = cached_series(_noisy()) >>> fib(0) [] >>> fib(1) calculating 1 [1] >>> fib(5) calculating 1 calculating 2 calculating 3 calculating 5 [1, 1, 2, 3, 5] >>> fib(5) [1, 1, 2, 3, 5] >>> fib(6) calculating 8 [1, 1, 2, 3, 5, 8] -- http://mail.python.org/mailman/listinfo/python-list