Implement Fibonacci with loop, recursion, reduce

fibonacci-python.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fibonacci"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1, 1, 2, 3, 5, 8, 13, 21..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# timer\n",
    "def timer_factory(times=10**3):\n",
    "    def interface(func):\n",
    "        from functools import wraps\n",
    "        from time import perf_counter\n",
    "\n",
    "        @wraps(func)\n",
    "        def timer(*args, **kwargs):\n",
    "            s = perf_counter()\n",
    "            for i in range(times):\n",
    "                result = func(*args, **kwargs)\n",
    "            e = perf_counter()\n",
    "            elapsed = e - s\n",
    "            print('Executed {} times, average took: {:05.3f}us'.format(times, 10**6 * elapsed / times))\n",
    "\n",
    "            return result\n",
    "        return timer\n",
    "    return interface"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### recursion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    if n <= 2:\n",
    "        return 1\n",
    "    return fib(n-1) + fib(n-2)\n",
    "\n",
    "@timer_factory(1000)\n",
    "def fib_run(n):\n",
    "    fib(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Executed 1000 times, average took: 1360.539us\n"
     ]
    }
   ],
   "source": [
    "fib_run(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### loop"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "@timer_factory(1000)\n",
    "def fib_loop(n):\n",
    "    fib_0 = 1\n",
    "    fib_1 = 1\n",
    "    for _ in range(n-1):\n",
    "        fib_0, fib_1 = fib_1, fib_0 + fib_1\n",
    "    return fib_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Executed 1000 times, average took: 1.796us\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6765"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib_loop(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### reduce"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<pre>\n",
    "previous value: (a, b)\n",
    "new value: (a+b, a)\n",
    "</pre>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    "@timer_factory(1000)\n",
    "def fib_reduce(n):\n",
    "    initial = (1, 0)\n",
    "    dummy = range(n - 1)  # make reduce work n times\n",
    "    result = reduce(lambda prev, n: (prev[0] + prev[1], prev[0]), \n",
    "                    dummy,\n",
    "                    initial)\n",
    "    return result[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Executed 1000 times, average took: 6.923us\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6765"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fib_reduce(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## improve resursion using cache"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### native"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    cache = {1: 1, 2: 1}\n",
    "    def inner(n):       \n",
    "        if n not in cache:\n",
    "            cache[n] = inner(n-1) + inner(n-2)\n",
    "        return cache[n]\n",
    "    return inner\n",
    "\n",
    "@timer_factory(1000)\n",
    "def fib_1_test(n):\n",
    "    fib(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Executed 1000 times, average took: 3.708us\n"
     ]
    }
   ],
   "source": [
    "fib_1_test(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### using lru_cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "\n",
    "@lru_cache(maxsize=8)\n",
    "def fib(n):\n",
    "    if n <= 2:\n",
    "        return 1\n",
    "    return fib(n-1) + fib(n-2)\n",
    "\n",
    "@timer_factory(1000)\n",
    "def fib_2_test(n):\n",
    "    fib(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Executed 1000 times, average took: 0.345us\n"
     ]
    }
   ],
   "source": [
    "fib_2_test(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### using custom cache"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def use_cache(fib):\n",
    "    cache = {1: 1, 2: 1}\n",
    "    def interface(n):       \n",
    "        if n not in cache:\n",
    "            cache[n] = fib(n)\n",
    "        return cache[n]\n",
    "    return interface\n",
    "\n",
    "@use_cache\n",
    "def fib(n):\n",
    "    if n <= 2:\n",
    "        return 1\n",
    "    return fib(n-1) + fib(n-2)\n",
    "\n",
    "@timer_factory(1000)\n",
    "def fib_3_test(n):\n",
    "    fib(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Executed 1000 times, average took: 0.435us\n"
     ]
    }
   ],
   "source": [
    "fib_3_test(20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1000 time test conclusion\n",
    "1. recursion with cache\n",
    "2. loop\n",
    "3. reduce\n",
    "4. recursion without cache\n",
    "\n",
    "1 > 2 > 3 >>>> 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Custom Fibonacci Sequence Type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "class Fib:\n",
    "    def __init__(self, n):\n",
    "        self._n = n\n",
    "    \n",
    "    def __len__(self):\n",
    "        return self._n\n",
    "    \n",
    "    def __getitem__(self, s):\n",
    "        if isinstance(s, int):\n",
    "            # single item requested\n",
    "            if s < 0:\n",
    "                s = self._n + s\n",
    "            if s < 0 or s > self._n - 1:\n",
    "                raise IndexError\n",
    "            return self._fib(s)\n",
    "        elif isinstance(s, slice):\n",
    "            # slice being requested\n",
    "            idx = s.indices(self._n)\n",
    "            rng = range(idx[0], idx[1], idx[2])\n",
    "            return [self._fib(n) for n in rng]\n",
    "        else:\n",
    "            raise NotImplementedError\n",
    "\n",
    "    @staticmethod\n",
    "    @lru_cache(2**32)\n",
    "    def _fib(n):\n",
    "        if n < 2:\n",
    "            return 1\n",
    "        else:\n",
    "            return fib(n-1) + fib(n-2)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}