Last active
March 30, 2024 08:03
-
-
Save razimantv/1b33d4a090a5bc9ed94928012b37c3f0 to your computer and use it in GitHub Desktop.
Revisions
-
razimantv revised this gist
Feb 26, 2018 . 1 changed file with 16 additions and 0 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -1,5 +1,21 @@ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Stackify!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Deep recursion will give you stack errors.\n", "\n", "Why change the stack limit when you can decorate the function by abusing exceptions and turn the function iterative instead?" ] }, { "cell_type": "code", "execution_count": 1, -
Feb 1, 2018 . 1 changed file with 63 additions and 121 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -4,21 +4,29 @@ "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "class stackify(object):\n", " \"\"\"Wrapper for stack-based recursion with memoisation\n", " \n", " When the function is called and argument is not in cache, push it to stack\n", " Attempt to call the function on the arguments in the stack such that an\n", " exception is raised if the function tries to recurse. In that case, add the\n", " function argument to the stack and continue\n", " \n", " The order of successful arguments also provides a topological sort\n", "\n", " Warning:\n", " 1. Works only for \"pure\" side-effect-free functions without cycles\n", " 2. Immoral use of exceptions\n", " \n", " Attributes:\n", " __cache: Dictionary to memoise based on string representation of args\n", " __primary: Flag to denote whether we are in a primary function call\n", " toposort: Topological sort of the states of the function\n", " log: Flag whether logging is required. Default: False\n", " sort: Flag whether topological sort is required. Default: False\n", " \"\"\"\n", " def __init__ (self, f):\n", " self.__f = f\n", " self.__cache = {}\n", @@ -28,22 +36,28 @@ " self.sort = False\n", " \n", " def __call__(self, *args):\n", " # Before calling the function, check if the argument is present in cache\n", " key=str(args)\n", " if key in self.__cache:\n", " return self.__cache[key]\n", " \n", " if self.__primary:\n", " # We are in a direct call. Initialise the stack\n", " if self.log: print('Primary call on ' + str(args))\n", " self.__primary = False\n", " self.__stack = [args]\n", " if self.log: print('Push ' + str(args) + ' to stack')\n", " while len(self.__stack) > 0:\n", " # Pop an element from the stack and attempt to call the function\n", " arg = self.__stack.pop()\n", " if self.log: print('Pop ' + str(arg) + ' from stack')\n", " try:\n", " if self.log: print('Attempt to call ' + str(arg))\n", " value = self.__f(*arg)\n", " \n", " # If an exception has not been raised, we have successful evaluation\n", " # We are guaranteed that any state the f(arg) needs is already\n", " # present in toposort[], so add arg to the toposort\n", " if self.sort: self.toposort.append(arg)\n", " if self.log: print('Attempt to call ' + str(arg) + ' successful')\n", " self.__cache[str(arg)] = value\n", @@ -56,20 +70,16 @@ " if self.log: print('Push ' + str(arg) + ' to stack')\n", " if self.log: print('Push ' + str(self.__nextarg) + ' to stack')\n", " self.__primary = True\n", " \n", " # We are guaranteed that the original argument was evaluated last\n", " # So we can just return the value\n", " return value\n", " else:\n", " # Tried to recurse to non-cached value\n", " # Save the argument and crash\n", " if self.log: print('Attempted secondary call on ' + str(args))\n", " self.__nextarg = args\n", " raise Exception()" ] }, { @@ -78,42 +88,23 @@ "metadata": {}, "outputs": [ { "data": { "text/plain": [ "534400663" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@stackify\n", "def fib(N):\n", " if N<2: return 1\n", " return (fib(N-2) + fib(N-1))%1000000007\n", "\n", "# This would crash if we were doing memoised recursion without stackify\n", "fib(1000000)" ] }, @@ -126,25 +117,25 @@ "name": "stdout", "output_type": "stream", "text": [ "Primary call on (1, 4)\n", "Push (1, 4) to stack\n", "Pop (1, 4) from stack\n", "Attempt to call (1, 4)\n", "Attempted secondary call on (1, 3)\n", "Attempt to call (1, 4) failed\n", "Push (1, 4) to stack\n", "Push (1, 3) to stack\n", "Pop (1, 3) from stack\n", "Attempt to call (1, 3)\n", "Attempted secondary call on (1, 2)\n", "Attempt to call (1, 3) failed\n", "Push (1, 3) to stack\n", "Push (1, 2) to stack\n", "Pop (1, 2) from stack\n", "Attempt to call (1, 2)\n", "Attempted secondary call on (1, 1)\n", "Attempt to call (1, 2) failed\n", "Push (1, 2) to stack\n", "Push (1, 1) to stack\n", "Pop (1, 1) from stack\n", "Attempt to call (1, 1)\n", @@ -176,21 +167,6 @@ "Pop (1, 1) from stack\n", "Attempt to call (1, 1)\n", "Attempt to call (1, 1) successful\n", "Pop (1, 2) from stack\n", "Attempt to call (1, 2)\n", "Attempted secondary call on (0, 3)\n", @@ -215,21 +191,6 @@ "Pop (1, 3) from stack\n", "Attempt to call (1, 3)\n", "Attempt to call (1, 3) successful\n", "Pop (1, 4) from stack\n", "Attempt to call (1, 4)\n", "Attempted secondary call on (0, 5)\n", @@ -241,22 +202,7 @@ "Attempt to call (0, 5) successful\n", "Pop (1, 4) from stack\n", "Attempt to call (1, 4)\n", "Attempt to call (1, 4) successful\n" ] }, { @@ -266,17 +212,12 @@ " (1, 0),\n", " (0, 2),\n", " (1, 1),\n", " (0, 3),\n", " (1, 2),\n", " (0, 4),\n", " (1, 3),\n", " (0, 5),\n", " (1, 4)]" ] }, "execution_count": 3, @@ -291,9 +232,10 @@ " if N == 0: return ackermann(M-1,1)\n", " return ackermann(M-1, ackermann(M,N-1))\n", "\n", "# Show call sequence and topological sort of states for Ackermann function\n", "ackermann.log = True\n", "ackermann.sort = True\n", "ackermann(1,4)\n", "ackermann.toposort" ] }, -
Feb 1, 2018 . 1 changed file with 61 additions and 61 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -42,15 +42,15 @@ " arg = self.__stack.pop()\n", " if self.log: print('Pop ' + str(arg) + ' from stack')\n", " try:\n", " if self.log: print('Attempt to call ' + str(arg))\n", " value = self.__f(*arg)\n", " if self.sort: self.toposort.append(arg)\n", " if self.log: print('Attempt to call ' + str(arg) + ' successful')\n", " self.__cache[str(arg)] = value\n", " except:\n", " # Tried to recurse to non-cached value\n", " # Push it to stack after previous argument\n", " if self.log: print('Attempt to call ' + str(arg) + ' failed')\n", " self.__stack.append(arg)\n", " self.__stack.append(self.__nextarg)\n", " if self.log: print('Push ' + str(arg) + ' to stack')\n", @@ -129,134 +129,134 @@ "Primary call on (2, 2)\n", "Push (2, 2) to stack\n", "Pop (2, 2) from stack\n", "Attempt to call (2, 2)\n", "Attempted secondary call on (2, 1)\n", "Attempt to call (2, 2) failed\n", "Push (2, 2) to stack\n", "Push (2, 1) to stack\n", "Pop (2, 1) from stack\n", "Attempt to call (2, 1)\n", "Attempted secondary call on (2, 0)\n", "Attempt to call (2, 1) failed\n", "Push (2, 1) to stack\n", "Push (2, 0) to stack\n", "Pop (2, 0) from stack\n", "Attempt to call (2, 0)\n", "Attempted secondary call on (1, 1)\n", "Attempt to call (2, 0) failed\n", "Push (2, 0) to stack\n", "Push (1, 1) to stack\n", "Pop (1, 1) from stack\n", "Attempt to call (1, 1)\n", "Attempted secondary call on (1, 0)\n", "Attempt to call (1, 1) failed\n", "Push (1, 1) to stack\n", "Push (1, 0) to stack\n", "Pop (1, 0) from stack\n", "Attempt to call (1, 0)\n", "Attempted secondary call on (0, 1)\n", "Attempt to call (1, 0) failed\n", "Push (1, 0) to stack\n", "Push (0, 1) to stack\n", "Pop (0, 1) from stack\n", "Attempt to call (0, 1)\n", "Attempt to call (0, 1) successful\n", "Pop (1, 0) from stack\n", "Attempt to call (1, 0)\n", "Attempt to call (1, 0) successful\n", "Pop (1, 1) from stack\n", "Attempt to call (1, 1)\n", "Attempted secondary call on (0, 2)\n", "Attempt to call (1, 1) failed\n", "Push (1, 1) to stack\n", "Push (0, 2) to stack\n", "Pop (0, 2) from stack\n", "Attempt to call (0, 2)\n", "Attempt to call (0, 2) successful\n", "Pop (1, 1) from stack\n", "Attempt to call (1, 1)\n", "Attempt to call (1, 1) successful\n", "Pop (2, 0) from stack\n", "Attempt to call (2, 0)\n", "Attempt to call (2, 0) successful\n", "Pop (2, 1) from stack\n", "Attempt to call (2, 1)\n", "Attempted secondary call on (1, 3)\n", "Attempt to call (2, 1) failed\n", "Push (2, 1) to stack\n", "Push (1, 3) to stack\n", "Pop (1, 3) from stack\n", "Attempt to call (1, 3)\n", "Attempted secondary call on (1, 2)\n", "Attempt to call (1, 3) failed\n", "Push (1, 3) to stack\n", "Push (1, 2) to stack\n", "Pop (1, 2) from stack\n", "Attempt to call (1, 2)\n", "Attempted secondary call on (0, 3)\n", "Attempt to call (1, 2) failed\n", "Push (1, 2) to stack\n", "Push (0, 3) to stack\n", "Pop (0, 3) from stack\n", "Attempt to call (0, 3)\n", "Attempt to call (0, 3) successful\n", "Pop (1, 2) from stack\n", "Attempt to call (1, 2)\n", "Attempt to call (1, 2) successful\n", "Pop (1, 3) from stack\n", "Attempt to call (1, 3)\n", "Attempted secondary call on (0, 4)\n", "Attempt to call (1, 3) failed\n", "Push (1, 3) to stack\n", "Push (0, 4) to stack\n", "Pop (0, 4) from stack\n", "Attempt to call (0, 4)\n", "Attempt to call (0, 4) successful\n", "Pop (1, 3) from stack\n", "Attempt to call (1, 3)\n", "Attempt to call (1, 3) successful\n", "Pop (2, 1) from stack\n", "Attempt to call (2, 1)\n", "Attempt to call (2, 1) successful\n", "Pop (2, 2) from stack\n", "Attempt to call (2, 2)\n", "Attempted secondary call on (1, 5)\n", "Attempt to call (2, 2) failed\n", "Push (2, 2) to stack\n", "Push (1, 5) to stack\n", "Pop (1, 5) from stack\n", "Attempt to call (1, 5)\n", "Attempted secondary call on (1, 4)\n", "Attempt to call (1, 5) failed\n", "Push (1, 5) to stack\n", "Push (1, 4) to stack\n", "Pop (1, 4) from stack\n", "Attempt to call (1, 4)\n", "Attempted secondary call on (0, 5)\n", "Attempt to call (1, 4) failed\n", "Push (1, 4) to stack\n", "Push (0, 5) to stack\n", "Pop (0, 5) from stack\n", "Attempt to call (0, 5)\n", "Attempt to call (0, 5) successful\n", "Pop (1, 4) from stack\n", "Attempt to call (1, 4)\n", "Attempt to call (1, 4) successful\n", "Pop (1, 5) from stack\n", "Attempt to call (1, 5)\n", "Attempted secondary call on (0, 6)\n", "Attempt to call (1, 5) failed\n", "Push (1, 5) to stack\n", "Push (0, 6) to stack\n", "Pop (0, 6) from stack\n", "Attempt to call (0, 6)\n", "Attempt to call (0, 6) successful\n", "Pop (1, 5) from stack\n", "Attempt to call (1, 5)\n", "Attempt to call (1, 5) successful\n", "Pop (2, 2) from stack\n", "Attempt to call (2, 2)\n", "Attempt to call (2, 2) successful\n" ] }, { -
Feb 1, 2018 . 1 changed file with 193 additions and 9 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -23,6 +23,9 @@ " self.__f = f\n", " self.__cache = {}\n", " self.__primary = True\n", " self.toposort = []\n", " self.log = False\n", " self.sort = False\n", " \n", " def __call__(self, *args):\n", " key=str(args)\n", @@ -31,32 +34,33 @@ " \n", " if self.__primary:\n", " # Direct call. Initialise stack\n", " if self.log: print('Primary call on ' + str(args))\n", " self.__primary = False\n", " self.__stack = [args]\n", " if self.log: print('Push ' + str(args) + ' to stack')\n", " while len(self.__stack) > 0:\n", " arg = self.__stack.pop()\n", " if self.log: print('Pop ' + str(arg) + ' from stack')\n", " try:\n", " if self.log: print('Attempt to call fib' + str(arg))\n", " value = self.__f(*arg)\n", " if self.sort: self.toposort.append(arg)\n", " if self.log: print('Attempt to call fib' + str(arg) + ' successful')\n", " self.__cache[str(arg)] = value\n", " except:\n", " # Tried to recurse to non-cached value\n", " # Push it to stack after previous argument\n", " if self.log: print('Attempt to call fib' + str(arg) + ' failed')\n", " self.__stack.append(arg)\n", " self.__stack.append(self.__nextarg)\n", " if self.log: print('Push ' + str(arg) + ' to stack')\n", " if self.log: print('Push ' + str(self.__nextarg) + ' to stack')\n", " self.__primary = True\n", " return value\n", " else:\n", " # Tried to recurse to non-cached value\n", " # Save the argument and crash\n", " if self.log: print('Attempted secondary call on ' + str(args))\n", " self.__nextarg = args\n", " raise Exception()\n", "\n", @@ -113,6 +117,186 @@ "fib(1000000)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Primary call on (2, 2)\n", "Push (2, 2) to stack\n", "Pop (2, 2) from stack\n", "Attempt to call fib(2, 2)\n", "Attempted secondary call on (2, 1)\n", "Attempt to call fib(2, 2) failed\n", "Push (2, 2) to stack\n", "Push (2, 1) to stack\n", "Pop (2, 1) from stack\n", "Attempt to call fib(2, 1)\n", "Attempted secondary call on (2, 0)\n", "Attempt to call fib(2, 1) failed\n", "Push (2, 1) to stack\n", "Push (2, 0) to stack\n", "Pop (2, 0) from stack\n", "Attempt to call fib(2, 0)\n", "Attempted secondary call on (1, 1)\n", "Attempt to call fib(2, 0) failed\n", "Push (2, 0) to stack\n", "Push (1, 1) to stack\n", "Pop (1, 1) from stack\n", "Attempt to call fib(1, 1)\n", "Attempted secondary call on (1, 0)\n", "Attempt to call fib(1, 1) failed\n", "Push (1, 1) to stack\n", "Push (1, 0) to stack\n", "Pop (1, 0) from stack\n", "Attempt to call fib(1, 0)\n", "Attempted secondary call on (0, 1)\n", "Attempt to call fib(1, 0) failed\n", "Push (1, 0) to stack\n", "Push (0, 1) to stack\n", "Pop (0, 1) from stack\n", "Attempt to call fib(0, 1)\n", "Attempt to call fib(0, 1) successful\n", "Pop (1, 0) from stack\n", "Attempt to call fib(1, 0)\n", "Attempt to call fib(1, 0) successful\n", "Pop (1, 1) from stack\n", "Attempt to call fib(1, 1)\n", "Attempted secondary call on (0, 2)\n", "Attempt to call fib(1, 1) failed\n", "Push (1, 1) to stack\n", "Push (0, 2) to stack\n", "Pop (0, 2) from stack\n", "Attempt to call fib(0, 2)\n", "Attempt to call fib(0, 2) successful\n", "Pop (1, 1) from stack\n", "Attempt to call fib(1, 1)\n", "Attempt to call fib(1, 1) successful\n", "Pop (2, 0) from stack\n", "Attempt to call fib(2, 0)\n", "Attempt to call fib(2, 0) successful\n", "Pop (2, 1) from stack\n", "Attempt to call fib(2, 1)\n", "Attempted secondary call on (1, 3)\n", "Attempt to call fib(2, 1) failed\n", "Push (2, 1) to stack\n", "Push (1, 3) to stack\n", "Pop (1, 3) from stack\n", "Attempt to call fib(1, 3)\n", "Attempted secondary call on (1, 2)\n", "Attempt to call fib(1, 3) failed\n", "Push (1, 3) to stack\n", "Push (1, 2) to stack\n", "Pop (1, 2) from stack\n", "Attempt to call fib(1, 2)\n", "Attempted secondary call on (0, 3)\n", "Attempt to call fib(1, 2) failed\n", "Push (1, 2) to stack\n", "Push (0, 3) to stack\n", "Pop (0, 3) from stack\n", "Attempt to call fib(0, 3)\n", "Attempt to call fib(0, 3) successful\n", "Pop (1, 2) from stack\n", "Attempt to call fib(1, 2)\n", "Attempt to call fib(1, 2) successful\n", "Pop (1, 3) from stack\n", "Attempt to call fib(1, 3)\n", "Attempted secondary call on (0, 4)\n", "Attempt to call fib(1, 3) failed\n", "Push (1, 3) to stack\n", "Push (0, 4) to stack\n", "Pop (0, 4) from stack\n", "Attempt to call fib(0, 4)\n", "Attempt to call fib(0, 4) successful\n", "Pop (1, 3) from stack\n", "Attempt to call fib(1, 3)\n", "Attempt to call fib(1, 3) successful\n", "Pop (2, 1) from stack\n", "Attempt to call fib(2, 1)\n", "Attempt to call fib(2, 1) successful\n", "Pop (2, 2) from stack\n", "Attempt to call fib(2, 2)\n", "Attempted secondary call on (1, 5)\n", "Attempt to call fib(2, 2) failed\n", "Push (2, 2) to stack\n", "Push (1, 5) to stack\n", "Pop (1, 5) from stack\n", "Attempt to call fib(1, 5)\n", "Attempted secondary call on (1, 4)\n", "Attempt to call fib(1, 5) failed\n", "Push (1, 5) to stack\n", "Push (1, 4) to stack\n", "Pop (1, 4) from stack\n", "Attempt to call fib(1, 4)\n", "Attempted secondary call on (0, 5)\n", "Attempt to call fib(1, 4) failed\n", "Push (1, 4) to stack\n", "Push (0, 5) to stack\n", "Pop (0, 5) from stack\n", "Attempt to call fib(0, 5)\n", "Attempt to call fib(0, 5) successful\n", "Pop (1, 4) from stack\n", "Attempt to call fib(1, 4)\n", "Attempt to call fib(1, 4) successful\n", "Pop (1, 5) from stack\n", "Attempt to call fib(1, 5)\n", "Attempted secondary call on (0, 6)\n", "Attempt to call fib(1, 5) failed\n", "Push (1, 5) to stack\n", "Push (0, 6) to stack\n", "Pop (0, 6) from stack\n", "Attempt to call fib(0, 6)\n", "Attempt to call fib(0, 6) successful\n", "Pop (1, 5) from stack\n", "Attempt to call fib(1, 5)\n", "Attempt to call fib(1, 5) successful\n", "Pop (2, 2) from stack\n", "Attempt to call fib(2, 2)\n", "Attempt to call fib(2, 2) successful\n" ] }, { "data": { "text/plain": [ "[(0, 1),\n", " (1, 0),\n", " (0, 2),\n", " (1, 1),\n", " (2, 0),\n", " (0, 3),\n", " (1, 2),\n", " (0, 4),\n", " (1, 3),\n", " (2, 1),\n", " (0, 5),\n", " (1, 4),\n", " (0, 6),\n", " (1, 5),\n", " (2, 2)]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@stackify\n", "def ackermann(M,N):\n", " if M == 0: return N+1\n", " if N == 0: return ackermann(M-1,1)\n", " return ackermann(M-1, ackermann(M,N-1))\n", "\n", "ackermann.log = True\n", "ackermann.sort = True\n", "ackermann(2,2)\n", "ackermann.toposort" ] }, { "cell_type": "code", "execution_count": null, -
Feb 1, 2018 . 1 changed file with 59 additions and 70 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -2,72 +2,16 @@ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "534400663" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } @@ -87,41 +31,86 @@ " \n", " if self.__primary:\n", " # Direct call. Initialise stack\n", " # print('Primary call on ' + str(args))\n", " self.__primary = False\n", " self.__stack = [args]\n", " # print('Push ' + str(args) + ' to stack')\n", " while len(self.__stack) > 0:\n", " arg = self.__stack.pop()\n", " # print('Pop ' + str(arg) + ' from stack')\n", " try:\n", " # print('Attempt to call fib' + str(arg))\n", " value = self.__f(*arg)\n", " # print('Attempt to call fib' + str(arg) + ' successful')\n", " self.__cache[str(arg)] = value\n", " except:\n", " # Tried to recurse to non-cached value\n", " # Push it to stack after previous argument\n", " # print('Attempt to call fib' + str(arg) + ' failed')\n", " self.__stack.append(arg)\n", " self.__stack.append(self.__nextarg)\n", " # print('Push ' + str(arg) + ' to stack')\n", " # print('Push ' + str(self.__nextarg) + ' to stack')\n", " self.__primary = True\n", " return value\n", " else:\n", " # Tried to recurse to non-cached value\n", " # Save the argument and crash\n", " # print('Attempted secondary call on ' + str(args))\n", " self.__nextarg = args\n", " raise Exception()\n", "\n", "@stackify\n", "def fib(N):\n", " if N<2: return 1\n", " return (fib(N-2) + fib(N-1))%1000000007\n", "\n", "fib(1000000)" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "ename": "RecursionError", "evalue": "maximum recursion depth exceeded while calling a Python object", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mRecursionError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m<ipython-input-2-265895ef41c1>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 19\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mfib\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfib\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m%\u001b[0m\u001b[0;36m1000000007\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 20\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 21\u001b[0;31m \u001b[0mfib\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1000000\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;32m<ipython-input-2-265895ef41c1>\u001b[0m in \u001b[0;36m__call__\u001b[0;34m(self, *args)\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__cache\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 11\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m \u001b[0mvalue\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__f\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 13\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__cache\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 14\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;32m<ipython-input-2-265895ef41c1>\u001b[0m in \u001b[0;36mfib\u001b[0;34m(N)\u001b[0m\n\u001b[1;32m 17\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mfib\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 18\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mN\u001b[0m\u001b[0;34m<\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m:\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 19\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mfib\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mfib\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mN\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m%\u001b[0m\u001b[0;36m1000000007\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 20\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 21\u001b[0m \u001b[0mfib\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m1000000\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "... last 2 frames repeated, from the frame below ...\n", "\u001b[0;32m<ipython-input-2-265895ef41c1>\u001b[0m in \u001b[0;36m__call__\u001b[0;34m(self, *args)\u001b[0m\n\u001b[1;32m 10\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__cache\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 11\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 12\u001b[0;31m \u001b[0mvalue\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__f\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m*\u001b[0m\u001b[0margs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 13\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m__cache\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mkey\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 14\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mvalue\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n", "\u001b[0;31mRecursionError\u001b[0m: maximum recursion depth exceeded while calling a Python object" ] } ], "source": [ "class memoize(object):\n", " \n", " def __init__ (self, f):\n", " self.__f = f\n", " self.__cache = {}\n", " \n", " def __call__(self, *args):\n", " key=str(args)\n", " if key in self.__cache:\n", " return self.__cache[key]\n", " \n", " value = self.__f(*args)\n", " self.__cache[key] = value\n", " return value\n", "\n", "@memoize\n", "def fib(N):\n", " if N<2: return 1\n", " return (fib(N-2) + fib(N-1))%1000000007\n", "\n", "fib(1000000)" ] }, { -
Feb 1, 2018 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,156 @@ { "cells": [ { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Primary call on (5,)\n", "Push (5,) to stack\n", "Pop (5,) from stack\n", "Attempt to call fib(5,)\n", "Attempted secondary call on (3,)\n", "Attempt to call fib(5,) failed\n", "Push (5,) to stack\n", "Push (3,) to stack\n", "Pop (3,) from stack\n", "Attempt to call fib(3,)\n", "Attempted secondary call on (1,)\n", "Attempt to call fib(3,) failed\n", "Push (3,) to stack\n", "Push (1,) to stack\n", "Pop (1,) from stack\n", "Attempt to call fib(1,)\n", "Attempt to call fib(1,) successful\n", "Pop (3,) from stack\n", "Attempt to call fib(3,)\n", "Attempted secondary call on (2,)\n", "Attempt to call fib(3,) failed\n", "Push (3,) to stack\n", "Push (2,) to stack\n", "Pop (2,) from stack\n", "Attempt to call fib(2,)\n", "Attempted secondary call on (0,)\n", "Attempt to call fib(2,) failed\n", "Push (2,) to stack\n", "Push (0,) to stack\n", "Pop (0,) from stack\n", "Attempt to call fib(0,)\n", "Attempt to call fib(0,) successful\n", "Pop (2,) from stack\n", "Attempt to call fib(2,)\n", "Attempt to call fib(2,) successful\n", "Pop (3,) from stack\n", "Attempt to call fib(3,)\n", "Attempt to call fib(3,) successful\n", "Pop (5,) from stack\n", "Attempt to call fib(5,)\n", "Attempted secondary call on (4,)\n", "Attempt to call fib(5,) failed\n", "Push (5,) to stack\n", "Push (4,) to stack\n", "Pop (4,) from stack\n", "Attempt to call fib(4,)\n", "Attempt to call fib(4,) successful\n", "Pop (5,) from stack\n", "Attempt to call fib(5,)\n", "Attempt to call fib(5,) successful\n" ] }, { "data": { "text/plain": [ "8" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class stackify(object):\n", " \n", " def __init__ (self, f):\n", " self.__f = f\n", " self.__cache = {}\n", " self.__primary = True\n", " \n", " def __call__(self, *args):\n", " key=str(args)\n", " if key in self.__cache:\n", " return self.__cache[key]\n", " \n", " if self.__primary:\n", " # Direct call. Initialise stack\n", " print('Primary call on ' + str(args))\n", " self.__primary = False\n", " self.__stack = [args]\n", " print('Push ' + str(args) + ' to stack')\n", " while len(self.__stack) > 0:\n", " arg = self.__stack.pop()\n", " print('Pop ' + str(arg) + ' from stack')\n", " try:\n", " print('Attempt to call fib' + str(arg))\n", " value = self.__f(*arg)\n", " print('Attempt to call fib' + str(arg) + ' successful')\n", " self.__cache[str(arg)] = value\n", " except:\n", " # Tried to recurse to non-cached value\n", " # Push it to stack after previous argument\n", " print('Attempt to call fib' + str(arg) + ' failed')\n", " self.__stack.append(arg)\n", " self.__stack.append(self.__nextarg)\n", " print('Push ' + str(arg) + ' to stack')\n", " print('Push ' + str(self.__nextarg) + ' to stack')\n", " self.__primary = True\n", " return value\n", " else:\n", " # Tried to recurse to non-cached value\n", " # Save the argument and crash\n", " print('Attempted secondary call on ' + str(args))\n", " self.__nextarg = args\n", " raise Exception()\n", "\n", "@stackify\n", "def fib(N):\n", " if N<2: return 1\n", " return fib(N-2) + fib(N-1)\n", "\n", "fib(5)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "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 }