Skip to content

Instantly share code, notes, and snippets.

@razimantv

razimantv/stackify.ipynb

Last active March 30, 2024 08:03
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save razimantv/1b33d4a090a5bc9ed94928012b37c3f0 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save razimantv/1b33d4a090a5bc9ed94928012b37c3f0 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
stackify.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"534400663"
]
},
"execution_count": 1,
"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",
" self.toposort = []\n",
" self.log = False\n",
" self.sort = False\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",
" 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 ' + 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",
" 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",
"@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)"
]
},
{
"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 (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"
]
},
{
"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,
"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
}
@gauthamzz
Copy link
Copy Markdown

gauthamzz commented Feb 26, 2018

👍

@a-huy
Copy link
Copy Markdown

a-huy commented Feb 27, 2018

You might want to define a custom Exception class for this - it looks like the current implementation will confuse KeyboardInterrupt and unrelated functional exceptions as an attempt to recurse.

@progval
Copy link
Copy Markdown

progval commented Feb 28, 2018

Next step: tail-recursion optimization

@petiepooo
Copy link
Copy Markdown

petiepooo commented Feb 28, 2018

Cool hack, but a-huy is right: a naked except clause? Tsk tsk..

@tchoutri
Copy link
Copy Markdown

tchoutri commented Feb 28, 2018

Can't wait for proper recursion now!

@float64co
Copy link
Copy Markdown

float64co commented Feb 28, 2018

👍

@Aristarhys
Copy link
Copy Markdown

Aristarhys commented Feb 28, 2018

🤘

@jasen-b
Copy link
Copy Markdown

jasen-b commented Feb 28, 2018

a custom exception is not needed, the exception problem can be fixed by reducing the scope of the try block and using some messy branching or a tidy little goto.

@skliarpawlo
Copy link
Copy Markdown

skliarpawlo commented Mar 3, 2018

I think you can pass __next_arg via exception params instead of stackify object state.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment