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",
" \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))%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": 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