Skip to content

Instantly share code, notes, and snippets.

@BertrandBordage
Created December 24, 2013 17:18
Show Gist options
  • Save BertrandBordage/8115863 to your computer and use it in GitHub Desktop.
Save BertrandBordage/8115863 to your computer and use it in GitHub Desktop.
{
"metadata": {
"name": "Fibonacci"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 1,
"metadata": {},
"source": "Comparison between several implementations of the Fibonacci sequence"
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": "Simple solution"
},
{
"cell_type": "markdown",
"metadata": {},
"source": "First, a basic imperative implementation."
},
{
"cell_type": "code",
"collapsed": false,
"input": "def fib(n):\n a, b = 0, 1\n for i in range(n):\n a, b = a+b, a\n return a",
"language": "python",
"metadata": {
"slideshow": {
"slide_type": "notes"
}
},
"outputs": [],
"prompt_number": 1
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": "Python > 3.2"
},
{
"cell_type": "markdown",
"metadata": {},
"source": "Then a recursive approach, with a Python 3 cache."
},
{
"cell_type": "code",
"collapsed": false,
"input": "from functools import lru_cache\n\n@lru_cache(maxsize=None)\ndef cached_fib(n):\n if n < 2:\n return n\n return cached_fib(n-1) + cached_fib(n-2)",
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 2
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": "Cython"
},
{
"cell_type": "markdown",
"metadata": {},
"source": "Finally, we load Cython and reuse the imperative implementation, but with static typing.\nWe don't even try the recursive implementation as it will lead to a huge overflow."
},
{
"cell_type": "code",
"collapsed": false,
"input": "%load_ext cythonmagic",
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 3
},
{
"cell_type": "code",
"collapsed": false,
"input": "%%cython\n\ndef cython_fib(int n):\n cdef unsigned long long int a, b, i\n a, b = 0, 1\n for i in range(n):\n a, b = a+b, a\n return a",
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 4
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": "Performance test"
},
{
"cell_type": "markdown",
"metadata": {},
"source": "Let's look at the results\u2026"
},
{
"cell_type": "code",
"collapsed": false,
"input": "n = 50\nprint(fib(n))\nprint(cached_fib(n))\nprint(cython_fib(n))",
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": "12586269025\n12586269025\n12586269025\n"
}
],
"prompt_number": 5
},
{
"cell_type": "code",
"collapsed": false,
"input": "%timeit fib(50)",
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": "100000 loops, best of 3: 3.01 \u00b5s per loop\n"
}
],
"prompt_number": 6
},
{
"cell_type": "code",
"collapsed": false,
"input": "%timeit cached_fib(50)",
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": "1000000 loops, best of 3: 739 ns per loop\n"
}
],
"prompt_number": 7
},
{
"cell_type": "code",
"collapsed": false,
"input": "%timeit cython_fib(50)",
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": "10000000 loops, best of 3: 103 ns per loop\n"
}
],
"prompt_number": 8
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": "Warning"
},
{
"cell_type": "markdown",
"metadata": {},
"source": "Unfortunately, when the result exceeds `2**64 - 1` (the maximum value for an `unsigned long long int`), the Cython implementation is broken."
},
{
"cell_type": "code",
"collapsed": false,
"input": "n = 94\nprint(fib(n))\nprint(cached_fib(n))\nprint(cython_fib(n))",
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": "19740274219868223167\n19740274219868223167\n1293530146158671551\n"
}
],
"prompt_number": 9
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": "Conclusion"
},
{
"cell_type": "markdown",
"metadata": {},
"source": "* If you want extreme speed with n < 94, use the Cython implementation.\n* Otherwise, if you're using Python > 3.2, use the simple and mathematical recursive approach with `@lru_cache`.\n* As a last resort, you can use the regular imperative implementation."
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment