Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
lru_cache decorator
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "lru_cache decorator",
"version": "0.3.2",
"provenance": [],
"collapsed_sections": [],
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"[View in Colaboratory](https://colab.research.google.com/gist/simecek/61e46b0049a0e4be1c4dba4a3f5c34f8/lru_cache-decorator.ipynb)"
]
},
{
"metadata": {
"id": "UhqKk2m3hAyX",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"## @lru_cache decorator\n",
"\n",
"With a simple decorator, repeated function calls become O(1) table lookups:\n",
"\n",
"https://docs.python.org/3/library/functools.html#functools.lru_cache\n",
"\n",
"Let us demonstrate it "
]
},
{
"metadata": {
"id": "PgsougGdNhYy",
"colab_type": "code",
"colab": {}
},
"cell_type": "code",
"source": [
"from functools import lru_cache\n",
"\n",
"# Compute fibonacci number\n",
"def fib(N):\n",
" if N in [0,1]:\n",
" return N\n",
" else:\n",
" return fib(N-1) + fib(N-2)\n",
" \n",
"# Same, but with @lru_cache decorator\n",
"@lru_cache()\n",
"def fib2(N):\n",
" if N in [0,1]:\n",
" return N\n",
" else:\n",
" return fib2(N-1) + fib2(N-2)\n",
" "
],
"execution_count": 0,
"outputs": []
},
{
"metadata": {
"id": "sSCfj0sFiy2i",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"### Original code"
]
},
{
"metadata": {
"id": "1U1JvA0keiwi",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 68
},
"outputId": "588b0fc3-0079-456d-fe87-dad9776b0c13"
},
"cell_type": "code",
"source": [
"%%time\n",
"fib(35)"
],
"execution_count": 2,
"outputs": [
{
"output_type": "stream",
"text": [
"CPU times: user 4.32 s, sys: 2.75 ms, total: 4.32 s\n",
"Wall time: 4.33 s\n"
],
"name": "stdout"
},
{
"output_type": "execute_result",
"data": {
"text/plain": [
"9227465"
]
},
"metadata": {
"tags": []
},
"execution_count": 2
}
]
},
{
"metadata": {
"id": "udMUTiSEi29J",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"### @lru_cache memoizing"
]
},
{
"metadata": {
"id": "R62pzJ51f7Yg",
"colab_type": "code",
"colab": {
"base_uri": "https://localhost:8080/",
"height": 68
},
"outputId": "d415e03d-11bd-45ad-abad-ac9113e7f986"
},
"cell_type": "code",
"source": [
"%%time\n",
"fib2(35)"
],
"execution_count": 3,
"outputs": [
{
"output_type": "stream",
"text": [
"CPU times: user 52 µs, sys: 3 µs, total: 55 µs\n",
"Wall time: 59.6 µs\n"
],
"name": "stdout"
},
{
"output_type": "execute_result",
"data": {
"text/plain": [
"9227465"
]
},
"metadata": {
"tags": []
},
"execution_count": 3
}
]
},
{
"metadata": {
"id": "ba8YY3NRjFFu",
"colab_type": "text"
},
"cell_type": "markdown",
"source": [
"### Acknowledgement\n",
"\n",
"Original idea found in Jake VanderPlas's tweet: https://twitter.com/jakevdp/status/1027298136178319360"
]
}
]
}
@simecek

This comment has been minimized.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.