Python Geek blog (Graphs)-[:ARE]->(Everywhere)

Python category

Eloquent fibonacci sequences in python

If by chance I have omitted anything more or less proper or necessary, I beg forgiveness, since there is no one who is without fault and circumspect in all matters.”

― Leonardo Bonacci - italian mathematician

Leonardo Bonacci

Quick introduction

The idea of this article to collect eloquent python patterns using well-known Fibonacci sequence.

Recursive approach

cat fibonacci1.py
def fibonacci1(n):
    if n < 2:
        return n
    return fibonacci1(n - 2) + fibonacci1(n - 1)

if __name__ == '__main__':
    from timeit import timeit
    print(timeit("fibonacci1(5)", setup="from __main__ import fibonacci1")) 
$ python3 fibonacci1_bench.py # On my MacBook Pro (Mid 2015) 2.5 GHz Intel Core i7, 16 GB 1600 MHz DDR3
2.0335577040023054

Recursive approach using caching

My favorite advice: you should know you language standard library. You can find lot’s of info under functools module docs. Default maxsize is 128 for lru_cache decorator.

$ cat fibonacci2.py
import functools


@functools.lru_cache()
def fibonacci2(n):
    if n < 2:
        return n
    return fibonacci2(n - 2) + fibonacci2(n - 1)


if __name__ == '__main__':
    from timeit import timeit
    print(timeit("fibonacci2(5)", setup="from __main__ import fibonacci2"))
$ python3 fibonacci2_bench.py # On my MacBook Pro (Mid 2015) 2.5 GHz Intel Core i7, 16 GB 1600 MHz DDR3
0.09731649799505249
$ cat fibonacci_generator.py

Generator approach for using yield

def fibonacci_generator():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

if __name__ == '__main__':
    from timeit import timeit
    print(timeit("list(itertools.islice(fibonacci_generator(), 5))",
                 setup="from __main__ import fibonacci_generator"))
$ python3 fibonacci_generator.py # On my MacBook Pro (Mid 2015) 2.5 GHz Intel Core i7, 16 GB 1600 MHz DDR3
1.1730475709991879

About timeit instead of conclusion.

Also keep in mind:

Note By default, timeit() temporarily turns off garbage collection during the timing. The advantage of this approach is that it makes independent timings more comparable. This disadvantage is that GC may be an important component of the performance of the function being measured. If so, GC can be re-enabled as the first statement in the setup string.

More info about timeit Lib/timeit.py

Can I copy string in Python 3.5? And how?

“Mathematics reveals its secrets only to those who approach it with pure love, for its own beauty.”

― Archimedes

Domenico Fetti Archimedes

Quick introduction

Why do you need to copy a Python strings? It’s interesting question, because Python string is immutable. Also any tries of copy will returns the original string. Python tries to keep just the one copy, as that makes dictionary lookups faster.

May be use slice?

$ python3
Python 3.5.2 (default, Sep 15 2016, 07:38:42)
[GCC 4.2.1 Compatible Apple LLVM 7.3.0 (clang-703.0.31)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> a = 'python'
>>> b = a[:]
>>> b = a[:]
>>> id(a), id(b)
(4400931648, 4400931648)

Add empty string? No!

>>> a = 'python'
>>> id(a)
4400931648
>>> b = a + ''
>>> id(b)
4400931648  

Or use str function?

>>> a = 'python'
>>> id(a)
4400931648
>>> b =str(a)
>>> id(b)
4400931648

Try to use copy?

>>> a = 'python'
>>> id(a)
4400931648
>>> import copy
>>> b = copy.copy(a)
>>> id(b)
4400931648

Let’s do deepcopy!

>>> a = 'python'
>>> id(a)
4400931648
>>> b = copy.deepcopy(a)
>>> id(b)
4400931648
>>> print('No chance!')
No chance!

Another tries with using slice?

>>> a = 'python'
>>> b = (a + '.')[:-1]
>>> id(a)
4400931648
>>> id(b)
4400931760
>>> print('Eureka!')
Eureka!

Last try with encode and decode

>>> a = 'python'
>>> id(a)
4400931648
>>> b = a.encode().decode()
>>> b
'python'
>>> id(b)
4400931984
>>> print('Eureka!')
Eureka!

Conclusion

Try to answer the first question:

Can I copy or clone string in Python?

Answer is: no you can’t.

Every time we create new string, both working examples uses the same idea:

>>> a = 'a' * 1024
>>> b = 'a' * 1024
>>> id(a)
140726834891776
>>> id(b)
140726843315712

P.S. Thanks for ideas from Pavel’s talk from PyCon Russian 2016 and some more info you can find in references.

References

A collection of Python “must reads”

Articles:

Books:

Other python must read lists: