Skip to content

Instantly share code, notes, and snippets.

@francois-durand

francois-durand/Presentation.ipynb

Last active March 4, 2019 16:04
Show Gist options
  • Save francois-durand/08590af1228ed5c62adb02cb9ef4b9f4 to your computer and use it in GitHub Desktop.
Save francois-durand/08590af1228ed5c62adb02cb9ef4b9f4 to your computer and use it in GitHub Desktop.
Download ZIP
Some Architectural Considerations for Algorithms in Python
Display the source blob
Display the rendered blob
Raw
Presentation.ipynb
{
"cells": [
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "<center><h1>Some Architectural Considerations for Algorithms in Python<span class=\"tocSkip\"></span></h1><center>"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "<center>François Durand, Nokia Bell Labs France, October 2018<center>"
},
{
"metadata": {
"init_cell": true,
"slideshow": {
"slide_type": "skip"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.692440Z",
"end_time": "2019-03-04T16:04:32.709431Z"
}
},
"cell_type": "code",
"source": "import math\nimport numpy as np\nimport matplotlib.pyplot as plt\n%matplotlib inline\nimport collections",
"execution_count": 104,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"cell_type": "markdown",
"source": "In this talk, we address a very common and practical question for the programmer: what should be the general architecture of our code? In particular, when we plan to implement an algorithm, should we write it as a function that takes arguments and parameters as input, and gives its result as output? Or should we write a dedicated class? If so, how should we organize this class? How to ensure compatibility, easiness to implement and to maintain the code, rapidity to implement new functionalities? How to design the architecture in order to facilitate the composition of several algorithms?\n\nAfter presenting the problem and its challenges, we present an architecture inspired from the package Scikit-learn, then a variant with a more functional-style flavor. Lastly, we show how to use \"properties\" and especially \"cached properties\" to ensure a lazy evaluation while keeping the code very easy to write, maintain and extend."
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
},
"toc": true
},
"cell_type": "markdown",
"source": "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Base-Scenario\" data-toc-modified-id=\"Base-Scenario-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Base Scenario</a></span><ul class=\"toc-item\"><li><span><a href=\"#An-Auxiliary-Algorithm\" data-toc-modified-id=\"An-Auxiliary-Algorithm-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>An Auxiliary Algorithm</a></span></li><li><span><a href=\"#A-&quot;Big&quot;-Algorithm\" data-toc-modified-id=\"A-&quot;Big&quot;-Algorithm-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>A \"Big\" Algorithm</a></span></li><li><span><a href=\"#Vary-the-Auxiliary-Algorithm\" data-toc-modified-id=\"Vary-the-Auxiliary-Algorithm-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Vary the Auxiliary Algorithm</a></span></li></ul></li><li><span><a href=\"#Problems\" data-toc-modified-id=\"Problems-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Problems</a></span><ul class=\"toc-item\"><li><span><a href=\"#Enrich-the-Input:-Add-a-Parameter\" data-toc-modified-id=\"Enrich-the-Input:-Add-a-Parameter-2.1\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>Enrich the Input: Add a Parameter</a></span></li><li><span><a href=\"#Enrich-the-Output\" data-toc-modified-id=\"Enrich-the-Output-2.2\"><span class=\"toc-item-num\">2.2&nbsp;&nbsp;</span>Enrich the Output</a></span></li><li><span><a href=\"#Add-Other-Auxiliary-Algorithms,-with-Different-Parameters\" data-toc-modified-id=\"Add-Other-Auxiliary-Algorithms,-with-Different-Parameters-2.3\"><span class=\"toc-item-num\">2.3&nbsp;&nbsp;</span>Add Other Auxiliary Algorithms, with Different Parameters</a></span></li><li><span><a href=\"#Add-New-Functionalities\" data-toc-modified-id=\"Add-New-Functionalities-2.4\"><span class=\"toc-item-num\">2.4&nbsp;&nbsp;</span>Add New Functionalities</a></span></li></ul></li><li><span><a href=\"#Architecture-in-Scikit-learn-Style\" data-toc-modified-id=\"Architecture-in-Scikit-learn-Style-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>Architecture in Scikit-learn Style</a></span><ul class=\"toc-item\"><li><span><a href=\"#First-Attempt-(Already-with-a-Parameter)\" data-toc-modified-id=\"First-Attempt-(Already-with-a-Parameter)-3.1\"><span class=\"toc-item-num\">3.1&nbsp;&nbsp;</span>First Attempt (Already with a Parameter)</a></span></li><li><span><a href=\"#Enrich-the-Output\" data-toc-modified-id=\"Enrich-the-Output-3.2\"><span class=\"toc-item-num\">3.2&nbsp;&nbsp;</span>Enrich the Output</a></span></li><li><span><a href=\"#Other-Auxiliary-Algorithms,-with-Different-Parameters\" data-toc-modified-id=\"Other-Auxiliary-Algorithms,-with-Different-Parameters-3.3\"><span class=\"toc-item-num\">3.3&nbsp;&nbsp;</span>Other Auxiliary Algorithms, with Different Parameters</a></span></li><li><span><a href=\"#Add-New-Functionalities\" data-toc-modified-id=\"Add-New-Functionalities-3.4\"><span class=\"toc-item-num\">3.4&nbsp;&nbsp;</span>Add New Functionalities</a></span></li><li><span><a href=\"#REFERENCE:-Final-Version-for-Scikit-learn-Style\" data-toc-modified-id=\"REFERENCE:-Final-Version-for-Scikit-learn-Style-3.5\"><span class=\"toc-item-num\">3.5&nbsp;&nbsp;</span>REFERENCE: Final Version for Scikit-learn Style</a></span></li></ul></li><li><span><a href=\"#A-Variant-of-Architecture\" data-toc-modified-id=\"A-Variant-of-Architecture-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>A Variant of Architecture</a></span><ul class=\"toc-item\"><li><span><a href=\"#Call-the-Algorithm-Like-a-Function\" data-toc-modified-id=\"Call-the-Algorithm-Like-a-Function-4.1\"><span class=\"toc-item-num\">4.1&nbsp;&nbsp;</span>Call the Algorithm Like a Function</a></span></li><li><span><a href=\"#Optional-Call-at-Initialization\" data-toc-modified-id=\"Optional-Call-at-Initialization-4.2\"><span class=\"toc-item-num\">4.2&nbsp;&nbsp;</span>Optional Call at Initialization</a></span></li><li><span><a href=\"#REFERENCE:-Final-Version-with-the-Variant-Architecture\" data-toc-modified-id=\"REFERENCE:-Final-Version-with-the-Variant-Architecture-4.3\"><span class=\"toc-item-num\">4.3&nbsp;&nbsp;</span>REFERENCE: Final Version with the Variant Architecture</a></span></li></ul></li><li><span><a href=\"#Intermezzo:-Properties\" data-toc-modified-id=\"Intermezzo:-Properties-5\"><span class=\"toc-item-num\">5&nbsp;&nbsp;</span>Intermezzo: Properties</a></span><ul class=\"toc-item\"><li><span><a href=\"#Property\" data-toc-modified-id=\"Property-5.1\"><span class=\"toc-item-num\">5.1&nbsp;&nbsp;</span>Property</a></span></li><li><span><a href=\"#Cache-a-Property-(&quot;Manually&quot;)\" data-toc-modified-id=\"Cache-a-Property-(&quot;Manually&quot;)-5.2\"><span class=\"toc-item-num\">5.2&nbsp;&nbsp;</span>Cache a Property (\"Manually\")</a></span></li><li><span><a href=\"#Empty-the-cache-manually\" data-toc-modified-id=\"Empty-the-cache-manually-5.3\"><span class=\"toc-item-num\">5.3&nbsp;&nbsp;</span>Empty the cache manually</a></span></li><li><span><a href=\"#&quot;Automatic&quot;-Cached-Properties\" data-toc-modified-id=\"&quot;Automatic&quot;-Cached-Properties-5.4\"><span class=\"toc-item-num\">5.4&nbsp;&nbsp;</span>\"Automatic\" Cached Properties</a></span></li><li><span><a href=\"#Why-Some-Other-Tricks-Would-Fail\" data-toc-modified-id=\"Why-Some-Other-Tricks-Would-Fail-5.5\"><span class=\"toc-item-num\">5.5&nbsp;&nbsp;</span>Why Some Other Tricks Would Fail</a></span><ul class=\"toc-item\"><li><span><a href=\"#PyPI-package-cached_property\" data-toc-modified-id=\"PyPI-package-cached_property-5.5.1\"><span class=\"toc-item-num\">5.5.1&nbsp;&nbsp;</span>PyPI package cached_property</a></span></li><li><span><a href=\"#LRU-Cache\" data-toc-modified-id=\"LRU-Cache-5.5.2\"><span class=\"toc-item-num\">5.5.2&nbsp;&nbsp;</span>LRU Cache</a></span></li></ul></li></ul></li><li><span><a href=\"#Back-to-Business:-Using-Cached-Properties-in-our-Architecture\" data-toc-modified-id=\"Back-to-Business:-Using-Cached-Properties-in-our-Architecture-6\"><span class=\"toc-item-num\">6&nbsp;&nbsp;</span>Back to Business: Using Cached Properties in our Architecture</a></span><ul class=\"toc-item\"><li><span><a href=\"#Use-a-Cached-Property-to-Delay-Computation\" data-toc-modified-id=\"Use-a-Cached-Property-to-Delay-Computation-6.1\"><span class=\"toc-item-num\">6.1&nbsp;&nbsp;</span>Use a Cached Property to Delay Computation</a></span></li><li><span><a href=\"#REFERENCE:-Our-Final-Architecture\" data-toc-modified-id=\"REFERENCE:-Our-Final-Architecture-6.2\"><span class=\"toc-item-num\">6.2&nbsp;&nbsp;</span>REFERENCE: Our Final Architecture</a></span></li></ul></li><li><span><a href=\"#Conclusion\" data-toc-modified-id=\"Conclusion-7\"><span class=\"toc-item-num\">7&nbsp;&nbsp;</span>Conclusion</a></span><ul class=\"toc-item\"><li><span><a href=\"#A-(Simplified)-Real-Example\" data-toc-modified-id=\"A-(Simplified)-Real-Example-7.1\"><span class=\"toc-item-num\">7.1&nbsp;&nbsp;</span>A (Simplified) Real Example</a></span></li><li><span><a href=\"#That's-All-Folks-!\" data-toc-modified-id=\"That's-All-Folks-!-7.2\"><span class=\"toc-item-num\">7.2&nbsp;&nbsp;</span>That's All Folks !</a></span></li></ul></li></ul></div>"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "# Base Scenario"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## An Auxiliary Algorithm"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Say we have a \"little\" algorithm that we want to use later in some \"bigger\" algorithms."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.190457Z",
"end_time": "2019-03-04T16:04:31.217385Z"
}
},
"cell_type": "code",
"source": "def find_zero_dichotomy(f):\n \"\"\"\n Find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param f: the function (assumed to have a zero in [0, 1]).\n :return: the zero.\n \"\"\"\n x, y, z = 0, 1, .5\n while y - x > 1e-6:\n z = (x + y) / 2\n x, y = (z, y) if f(z) < 0 else (x, z)\n return z",
"execution_count": 3,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "-"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.218383Z",
"end_time": "2019-03-04T16:04:31.231348Z"
}
},
"cell_type": "code",
"source": "def some_increasing_function(x):\n return x**2 - .5",
"execution_count": 4,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.232344Z",
"end_time": "2019-03-04T16:04:31.247306Z"
}
},
"cell_type": "code",
"source": "find_zero_dichotomy(f=some_increasing_function)",
"execution_count": 5,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 5,
"data": {
"text/plain": "0.7071065902709961"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## A \"Big\" Algorithm"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Here is an example of a \"big\" algorithm, where we use the auxiliary algorithm `find_zero_dichotomy`."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.248302Z",
"end_time": "2019-03-04T16:04:31.260269Z"
}
},
"cell_type": "code",
"source": "def big_algo(f, translation):\n \"\"\"\n Find the zero of an increasing function [0, 1] -> R, then add a number.\n :param f: the function (assumed to have a zero in [0, 1]).\n :param translation: the number to be added.\n :return: the zero of f, plus translation.\n \"\"\"\n z = find_zero_dichotomy(f)\n return z + translation",
"execution_count": 6,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.263262Z",
"end_time": "2019-03-04T16:04:31.277231Z"
}
},
"cell_type": "code",
"source": "big_algo(f=some_increasing_function, translation=42)",
"execution_count": 7,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 7,
"data": {
"text/plain": "42.707106590270996"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Vary the Auxiliary Algorithm"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "We want to have the possibility to use a different auxiliary algorithm, such as:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.278223Z",
"end_time": "2019-03-04T16:04:31.291188Z"
}
},
"cell_type": "code",
"source": "def find_argmin_golden(f):\n \"\"\"\n Find the argmin of a stricly convex function [0, 1] -> R by a golden-section search.\n :param f: the function (assumed to have a minimum in [0, 1]).\n :return: the argmin.\n \"\"\"\n x, y, z = 0, 1, .5\n while y - x > 1e-6:\n d = (math.sqrt(5) - 1) * (y - x) / 2\n a, b = y - d, x + d\n x, y, z = (x, b, a) if f(b) > f(a) else (a, y, b)\n return z",
"execution_count": 8,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.292185Z",
"end_time": "2019-03-04T16:04:31.305191Z"
}
},
"cell_type": "code",
"source": "def some_convex_function(x):\n return x**2 - .5 * x",
"execution_count": 9,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.307145Z",
"end_time": "2019-03-04T16:04:31.318116Z"
}
},
"cell_type": "code",
"source": "find_argmin_golden(f=some_convex_function)",
"execution_count": 10,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 10,
"data": {
"text/plain": "0.24999986562737506"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "We modify the big algorithm so that it takes an auxiliary algorithm as an argument:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.319112Z",
"end_time": "2019-03-04T16:04:31.330091Z"
}
},
"cell_type": "code",
"source": "def big_algo(f, translation, find_point): # Added the last argument\n \"\"\"\n Find a \"special point\" of a function, then add a number.\n :param f: the function.\n :param translation: the number to be added.\n :param find_point: an algorithm used to find the \"special point\".\n :return: the \"special point\" of f, plus translation.\n \"\"\"\n z = find_point(f) # Modified line\n return z + translation",
"execution_count": 11,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.331080Z",
"end_time": "2019-03-04T16:04:31.346075Z"
}
},
"cell_type": "code",
"source": "big_algo(f=some_convex_function, translation=42, find_point=find_argmin_golden)",
"execution_count": 12,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 12,
"data": {
"text/plain": "42.24999986562737"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "# Problems"
},
{
"metadata": {
"ExecuteTime": {
"end_time": "2018-10-15T14:09:26.194800Z",
"start_time": "2018-10-15T14:09:26.190771Z"
},
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Enrich the Input: Add a Parameter"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Up to now, we used a precision of $10^{-6}$. This should be a parameter. We modify `find_zero_dichotomy`:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.347037Z",
"end_time": "2019-03-04T16:04:31.358043Z"
}
},
"cell_type": "code",
"source": "def find_zero_dichotomy(f, epsilon=1e-6): # Modified line\n \"\"\"\n Find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param f: the function (assumed to have a zero in [0, 1]).\n :param epsilon: the precision desired.\n :return: the zero (up to the precision).\n \"\"\"\n x, y, z = 0, 1, .5\n while y - x > epsilon: # Modified line\n z = (x + y) / 2\n x, y = (z, y) if f(z) < 0 else (x, z)\n return z",
"execution_count": 13,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "We also modify `find_argmin_golden`:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.359005Z",
"end_time": "2019-03-04T16:04:31.369977Z"
}
},
"cell_type": "code",
"source": "def find_argmin_golden(f, epsilon=1e-6): # Modified line\n \"\"\"\n Find the argmin of a stricly convex function [0, 1] -> R by a golden-section search.\n :param f: the function (assumed to have a minimum in [0, 1]).\n :param epsilon: the precision desired.\n :return: the argmin (up to the precision).\n \"\"\"\n x, y, z = 0, 1, .5\n while y - x > epsilon: # Modified line\n d = (math.sqrt(5) - 1) * (y - x) / 2\n a, b = y - d, x + d\n x, y, z = (x, b, a) if f(b) > f(a) else (a, y, b)\n return z",
"execution_count": 14,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Good point: by assigning a default value to parameter `epsilon`, we ensured backward compatibility. Indeed, any call previously written such as `find_argmin_golden(f)` will continue to work."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "Bad point: in the big algo, if we want to allow `epsilon` to vary, we must modify the code, for example as follows."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.370973Z",
"end_time": "2019-03-04T16:04:31.384937Z"
}
},
"cell_type": "code",
"source": "def big_algo(f, translation, find_point, epsilon): # Modified line\n \"\"\"\n Find a \"special point\" of a function, then add a number.\n :param f: the function. \n :param translation: the number to be added.\n :param find_point: an algorithm used to find the \"special point\".\n :param epsilon: the precision desired.\n :return: the \"special point\" of f, plus translation.\n \"\"\"\n z = find_point(f, epsilon) # Modified line\n return z + translation",
"execution_count": 15,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.385933Z",
"end_time": "2019-03-04T16:04:31.394910Z"
}
},
"cell_type": "code",
"source": "big_algo(f=some_increasing_function, translation=42, find_point=find_zero_dichotomy, epsilon=1e-6)",
"execution_count": 16,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 16,
"data": {
"text/plain": "42.707106590270996"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Enrich the Output"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Sometimes, we want to know an secondary result, such as the number of iterations for example (let us say, for logging purpose or whatever). We modify `find_zero_dichotomy`:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.395907Z",
"end_time": "2019-03-04T16:04:31.407875Z"
}
},
"cell_type": "code",
"source": "def find_zero_dichotomy(f, epsilon=1e-6):\n \"\"\"\n Find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param f: the function (assumed to have a zero in [0, 1]).\n :param epsilon: the precision desired.\n :return: the zero (up to the precision).\n \"\"\"\n x, y, z = 0, 1, .5\n number_iterations = 0 # Added line\n while y - x > epsilon:\n number_iterations += 1 # Added line\n z = (x + y) / 2\n x, y = (z, y) if f(z) < 0 else (x, z)\n return z, number_iterations # Modified line",
"execution_count": 17,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "We also modify `find_argmin_golden`:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.410869Z",
"end_time": "2019-03-04T16:04:31.423832Z"
}
},
"cell_type": "code",
"source": "def find_argmin_golden(f, epsilon=1e-6):\n \"\"\"\n Find the argmin of a stricly convex function [0, 1] -> R by a golden-section search.\n :param f: the function (assumed to have a minimum in [0, 1]).\n :param epsilon: the precision desired.\n :return: the argmin (up to the precision).\n \"\"\"\n x, y, z = 0, 1, .5\n number_iterations = 0 # Added line\n while y - x > epsilon:\n number_iterations += 1 # Added line\n d = (math.sqrt(5) - 1) * (y - x) / 2\n a, b = y - d, x + d\n x, y, z = (x, b, a) if f(b) > f(a) else (a, y, b)\n return z, number_iterations # Modified line",
"execution_count": 18,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "Problem: **everywhere** we used these functions, we need to modify the syntax accordingly! In other words, we modified the API of these functions, which is really bad!"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.424830Z",
"end_time": "2019-03-04T16:04:31.436797Z"
}
},
"cell_type": "code",
"source": "def big_algo(f, translation, find_point, epsilon):\n \"\"\"\n Find a \"special point\" of a function, then add a number.\n :param f: the function.\n :param translation: the number to be added.\n :param find_point: an algorithm used to find the \"special point\".\n :param epsilon: the precision desired.\n :return: the \"special point\" of f, plus translation.\n \"\"\"\n z, _ = find_point(f, epsilon) # Modified line\n return z + translation",
"execution_count": 19,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.437795Z",
"end_time": "2019-03-04T16:04:31.449772Z"
}
},
"cell_type": "code",
"source": "big_algo(f=some_increasing_function, translation=42, find_point=find_zero_dichotomy, epsilon=1e-6)",
"execution_count": 20,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 20,
"data": {
"text/plain": "42.707106590270996"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Add Other Auxiliary Algorithms, with Different Parameters"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Consider the following algorithm."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.451758Z",
"end_time": "2019-03-04T16:04:31.461731Z"
}
},
"cell_type": "code",
"source": "def find_zero_affine(f):\n \"\"\"\n Find the zero of a non-constant affine function R -> R.\n :param f: the function.\n :return: the zero.\n \"\"\"\n return - f(0) / (f(1) - f(0))",
"execution_count": 21,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "It is specialized for affine functions, and obviously more efficient and precise in that case than `find_zero_dichotomy`."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.463735Z",
"end_time": "2019-03-04T16:04:31.474698Z"
}
},
"cell_type": "code",
"source": "def some_affine_function(x):\n return 2 * x - .5",
"execution_count": 22,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.476691Z",
"end_time": "2019-03-04T16:04:31.488659Z"
}
},
"cell_type": "code",
"source": "find_zero_affine(f=some_affine_function)",
"execution_count": 23,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 23,
"data": {
"text/plain": "0.25"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "To make its syntax consistent with the other ones, we need to write:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.489656Z",
"end_time": "2019-03-04T16:04:31.500628Z"
}
},
"cell_type": "code",
"source": "def find_zero_affine(f, epsilon=1e-6): # Modified line to introduce a fake parameter\n \"\"\"\n Find the zero of a non-constant affine function R -> R.\n :param f: the function.\n :param epsilon: a useless parameter (here only for stupid compatibility reasons).\n :return: the zero.\n \"\"\"\n return - f(0) / (f(1) - f(0)), 1 # Modified line to return a fake number of iterations",
"execution_count": 24,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "This is obviously silly!"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Add New Functionalities"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "When we apply a \"find special point\" algorithm, we would like to have a convenient way to draw a plot representing what the algo did. With this architecture, it is really a pain to implement!"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "# Architecture in Scikit-learn Style"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## First Attempt (Already with a Parameter)"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Parent class:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.502622Z",
"end_time": "2019-03-04T16:04:31.512596Z"
}
},
"cell_type": "code",
"source": "class FindPoint:\n \"\"\"\n An algorithm to find a \"special point\" of a function.\n \"\"\"\n def run(self, f):\n \"\"\"\n :param f: the function.\n :return: the \"special point\".\n \"\"\"\n raise NotImplementedError",
"execution_count": 25,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "One subclass:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.513592Z",
"end_time": "2019-03-04T16:04:31.525561Z"
}
},
"cell_type": "code",
"source": "class FindZeroDichotomy(FindPoint):\n \"\"\"\n An algorithm to find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param epsilon: the precision desired.\n \"\"\" \n def __init__(self, epsilon=1e-6):\n self.epsilon = epsilon\n \n def run(self, f):\n x, y, z = 0, 1, .5\n while y - x > self.epsilon:\n z = (x + y) / 2\n x, y = (z, y) if f(z) < 0 else (x, z)\n return z",
"execution_count": 26,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.526558Z",
"end_time": "2019-03-04T16:04:31.538526Z"
}
},
"cell_type": "code",
"source": "find_zero = FindZeroDichotomy(epsilon=1e-6)\nfind_zero.run(f=some_increasing_function)",
"execution_count": 27,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 27,
"data": {
"text/plain": "0.7071065902709961"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.539523Z",
"end_time": "2019-03-04T16:04:31.550532Z"
}
},
"cell_type": "code",
"source": "class BigAlgo:\n \"\"\"\n An algorithm to find a \"special point\" of a function, then add a number.\n :param find_point: a :class:`FindPoint` algorithm.\n \"\"\"\n def __init__(self, find_point):\n self.find_point = find_point\n \n def run(self, f, translation):\n \"\"\"\n :param f: the function.\n :param translation: the number to be added.\n :return: the \"special point\", plus translation.\n \"\"\"\n return self.find_point.run(f) + translation",
"execution_count": 28,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.551490Z",
"end_time": "2019-03-04T16:04:31.566452Z"
}
},
"cell_type": "code",
"source": "big_algo = BigAlgo(find_point=FindZeroDichotomy(epsilon=1e-6))\nbig_algo.run(f=some_increasing_function, translation=42)",
"execution_count": 29,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 29,
"data": {
"text/plain": "42.707106590270996"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Or, in one line:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.567447Z",
"end_time": "2019-03-04T16:04:31.579449Z"
}
},
"cell_type": "code",
"source": "BigAlgo(find_point=FindZeroDichotomy(epsilon=1e-6)).run(f=some_increasing_function, translation=42)",
"execution_count": 30,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 30,
"data": {
"text/plain": "42.707106590270996"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Enrich the Output"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "When it is relevant, we want to have access to the number of iterations. But let us not break the API!"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.580413Z",
"end_time": "2019-03-04T16:04:31.610373Z"
}
},
"cell_type": "code",
"source": "class FindZeroDichotomy(FindPoint):\n \"\"\"\n An algorithm to find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param epsilon: the precision desired.\n :attr number_iterations_: number of iterations performed.\n \"\"\"\n def __init__(self, epsilon=1e-6):\n self.epsilon = epsilon\n self.number_iterations_ = None # Trailing underscore is a scikit-learn convention for \"computed variable\"\n \n def run(self, f):\n x, y, z = 0, 1, .5\n self.number_iterations_ = 0 # Added Line\n while y - x > self.epsilon:\n self.number_iterations_ += 1 # Added line\n z = (x + y) / 2\n x, y = (z, y) if f(z) < 0 else (x, z)\n return z",
"execution_count": 31,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.611330Z",
"end_time": "2019-03-04T16:04:31.623330Z"
}
},
"cell_type": "code",
"source": "find_point = FindZeroDichotomy(epsilon=1e-6)\nz = find_point.run(f=some_increasing_function)\nfind_point.number_iterations_",
"execution_count": 32,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 32,
"data": {
"text/plain": "20"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "On previous cell, we just saw:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.624295Z",
"end_time": "2019-03-04T16:04:31.637297Z"
}
},
"cell_type": "code",
"source": "find_point = FindZeroDichotomy(epsilon=1e-6)\nz = find_point.run(f=some_increasing_function)\nfind_point.number_iterations_",
"execution_count": 33,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 33,
"data": {
"text/plain": "20"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Unfortunately, this is not possible as a one-liner! You need to run `find_point` first, and then access `number_iterations_`."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "To allow for such one-liners, let us modify the method `run` so that it returns `self`. In the process, `z_` becomes a computed variable, just like `number_iterations_`. In the parent class:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.638259Z",
"end_time": "2019-03-04T16:04:31.651225Z"
}
},
"cell_type": "code",
"source": "class FindPoint:\n \"\"\"\n An algorithm to find a \"special point\" of a function.\n :attr z_: the special point.\n \"\"\"\n def __init__(self): # Added method\n self.z_ = None\n \n def run(self, f):\n \"\"\"\n :param f: the function.\n :return: itself. # Modified line\n \"\"\"\n raise NotImplementedError",
"execution_count": 34,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "In one subclass:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.654218Z",
"end_time": "2019-03-04T16:04:31.666223Z"
}
},
"cell_type": "code",
"source": "class FindZeroDichotomy(FindPoint):\n \"\"\"\n An algorithm to find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param epsilon: the precision desired.\n :attr z_: the zero.\n :attr number_iterations_: number of iterations performed.\n \"\"\"\n def __init__(self, epsilon=1e-6):\n super().__init__() # Added line\n self.epsilon = epsilon\n self.number_iterations_ = None\n \n def run(self, f):\n x, y, z = 0, 1, .5\n self.number_iterations_ = 0\n while y - x > self.epsilon:\n self.number_iterations_ += 1\n z = (x + y) / 2\n x, y = (z, y) if f(z) < 0 else (x, z)\n self.z_ = z # Added line\n return self # Modified line",
"execution_count": 35,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.667182Z",
"end_time": "2019-03-04T16:04:31.680147Z"
}
},
"cell_type": "code",
"source": "FindZeroDichotomy(epsilon=1e-6).run(f=some_increasing_function).z_",
"execution_count": 36,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 36,
"data": {
"text/plain": "0.7071065902709961"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.682143Z",
"end_time": "2019-03-04T16:04:31.693154Z"
}
},
"cell_type": "code",
"source": "FindZeroDichotomy(epsilon=1e-6).run(f=some_increasing_function).number_iterations_",
"execution_count": 37,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 37,
"data": {
"text/plain": "20"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "We modify the big algorithm accordingly:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.694110Z",
"end_time": "2019-03-04T16:04:31.705080Z"
}
},
"cell_type": "code",
"source": "class BigAlgo:\n \"\"\"\n An algorithm to find a \"special point\" of a function, then add a number.\n :param find_point: a :class:`FindPoint` algorithm.\n :attr translated_point_: the \"special point\", plus translation.\n \"\"\"\n def __init__(self, find_point):\n self.find_point = find_point\n self.translated_point_ = None # Added line\n \n def run(self, f, translation):\n \"\"\"\n :param f: the function.\n :param translation: the number to be added.\n :return: itself.\n \"\"\"\n self.translated_point_ = self.find_point.run(f).z_ + translation # Added line\n return self # Modified line",
"execution_count": 38,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.706078Z",
"end_time": "2019-03-04T16:04:31.718046Z"
}
},
"cell_type": "code",
"source": "BigAlgo(find_point=FindZeroDichotomy(epsilon=1e-6)).run(f=some_increasing_function, translation=42).translated_point_",
"execution_count": 39,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 39,
"data": {
"text/plain": "42.707106590270996"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Other Auxiliary Algorithms, with Different Parameters"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.719044Z",
"end_time": "2019-03-04T16:04:31.730014Z"
}
},
"cell_type": "code",
"source": "class FindZeroAffine(FindPoint):\n \"\"\"\n An algorithm to find the zero of a non-constant affine function R -> R.\n \"\"\"\n def run(self, f):\n self.z_ = - f(0) / (f(1) - f(0))\n return self",
"execution_count": 40,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Everything works as expected:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.731011Z",
"end_time": "2019-03-04T16:04:31.744017Z"
}
},
"cell_type": "code",
"source": "FindZeroAffine().run(f=some_affine_function).z_",
"execution_count": 41,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 41,
"data": {
"text/plain": "0.25"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.744974Z",
"end_time": "2019-03-04T16:04:31.756983Z"
}
},
"cell_type": "code",
"source": "BigAlgo(find_point=FindZeroAffine()).run(f=some_affine_function, translation=42).translated_point_",
"execution_count": 42,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 42,
"data": {
"text/plain": "42.25"
},
"metadata": {}
}
]
},
{
"metadata": {
"ExecuteTime": {
"end_time": "2018-10-15T14:36:23.100719Z",
"start_time": "2018-10-15T14:36:23.096728Z"
},
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Add New Functionalities "
},
{
"metadata": {},
"cell_type": "markdown",
"source": "We introduce a `plot` method. To do this, we need to store the argument `f`."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.757939Z",
"end_time": "2019-03-04T16:04:31.769929Z"
}
},
"cell_type": "code",
"source": "class FindPoint:\n \"\"\"\n An algorithm to find a \"special point\" of a function.\n :attr z_: the special point.\n \"\"\"\n def __init__(self):\n self.f_ = None # Added line\n self.z_ = None\n \n def run(self, f):\n \"\"\"\n :param f: the function.\n :return: itself.\n Must update self.f_ and self.z_. # Added line\n \"\"\"\n raise NotImplementedError\n \n def plot(self): # Added method\n \"\"\"\n Illustrate the method.\n This method must be used after :meth:`run`.\n \"\"\"\n x = np.arange(0.0, 1.0, .01)\n plt.plot(x, self.f_(x), label='y = f(x)')\n plt.plot([0, 1], [0, 0], label='y = 0')\n plt.legend()\n plt.text(self.z_, -.1, 'z')",
"execution_count": 43,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.770905Z",
"end_time": "2019-03-04T16:04:31.783880Z"
}
},
"cell_type": "code",
"source": "class FindZeroAffine(FindPoint):\n \"\"\"\n An algorithm to find the zero of a non-constant affine function R -> R.\n \"\"\"\n def run(self, f):\n self.f_ = f # Added line\n self.z_ = - f(0) / (f(1) - f(0))\n return self",
"execution_count": 44,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.784867Z",
"end_time": "2019-03-04T16:04:31.909535Z"
}
},
"cell_type": "code",
"source": "FindZeroAffine().run(f=some_affine_function).plot()",
"execution_count": 45,
"outputs": [
{
"output_type": "display_data",
"data": {
"text/plain": "<Figure size 432x288 with 1 Axes>",
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAYYAAAD8CAYAAABzTgP2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3Xl8VOXZ//HPRRbCvoSdEAIS2VeHRS0uVBQ3EKVqrYIVRX1qfz4PTyUCKoq1gtpFixtVRFsVNCBExSKyFFwoBJVsbCEsCWFNICxZSDLX748Z+wRIIJDJnMzker9evJg55z6Z74Ek39xzJnOLqmKMMcb8pI7TAYwxxtQsVgzGGGNOYcVgjDHmFFYMxhhjTmHFYIwx5hRWDMYYY05hxWCMMeYUVgzGGGNOYcVgjDHmFKFOB7gQLVq00JiYGKdjGGNMQNmwYcMhVW15rnEBWQwxMTEkJiY6HcMYYwKKiOyqzDh7KskYY8wprBiMMcacworBGGPMKXxyjUFE5gA3AQdUtVc5+68CFgM7vJsWqup0774RwMtACPCWqs64kAzFxcVkZWVRWFh4IYfXChEREURFRREWFuZ0FGNMDeari89zgVnAe2cZs0ZVbyq7QURCgFeB4UAWsF5EElQ17XwDZGVl0ahRI2JiYhCR8z086KkqOTk5ZGVl0alTJ6fjGGNqMJ88laSqq4HcCzh0EJCuqhmqehKYB4y6kAyFhYVERkZaKVRARIiMjLQZlTHmnPx5jeFSEdkoIl+ISE/vtvZAZpkxWd5tZxCRCSKSKCKJBw8eLPcBrBTOzv59jDGV4a9i+B7oqKp9gb8Ci7zby/tOVe5ao6o6W1Vdqupq2fKcv59hjDEBb3dOPr//LA23279LMPulGFT1qKoe995eAoSJSAs8M4QOZYZGAdn+yBQIDh48yODBg+nfvz9r1qxBVRk2bBhHjx496zEjRozwY0pjjK+VupU5X+/gur+sZt76TNIPHvfr4/ulGESkjXifxxCRQd7HzQHWA7Ei0klEwoE7gQR/ZAoEy5cvp1u3bvzwww8MHTqUJUuW0LdvXxo3blzhMS1btqRt27Z88803fkxqjPGV9APHuf3N75j+WRpDOjdn2cQruLh1I79m8EkxiMiHwHdAVxHJEpHxIvKQiDzkHTIGSBGRjcArwJ3qUQI8AiwFNgEfqWqqLzL525NPPsnLL7/8n/tTp07llVdeueCP9+OPPzJp0iSWLFlCv379KCgo4P3332fUKM+1+fXr19OnTx8KCws5ceIEPXv2JCUlBYBbbrmF999/v2onZIzxq5JSN6+v2s4Nr6xh+8Hj/PmOvsy5dyBtm9TzexZR9e9zV77gcrn09PdK2rRpE927dwfgmU9TScuu+OmWC9GjXWOm3dyzwv07d+7k1ltv5fvvv8ftdhMbG8u6deuIjIw8ZdzQoUM5duzYGce/9NJLXHPNNadsmzt3LomJicyaNQuAjh07kpKSQqNGnp8ennjiCQoLCykoKCAqKorJkycDsGfPHkaMGEFycvIZj1P238kYUzNs3neUxz5OInlPHtf3asMzo3rSqlGEzx9HRDaoqutc4wLyTfRqopiYGCIjI/nhhx/Yv38//fv3P6MUANasWXPBj5Gbm/ufUgB46qmnGDhwIBEREafMTlq1akV2tl2qMaamO1ni5tWV6by2Kp0m9cJ47VcDuKF3W6djBWcxnO0n++p0//33M3fuXPbt28d9991X7pjzmTGcLjQ0FLfbTZ06nmcAc3NzOX78OMXFxRQWFtKgQQPA8zsd9er5f/ppjKm8pKwjTIpPYvO+Y9zSrx1P3dyT5g3CnY4FBGkxOGX06NE89dRTFBcX88EHH5Q7piozhq5du5KRkUGXLl0AmDBhAs8++yw7duwgLi7uP085bd26lV69znhnEmNMDVBYXMpfvtrG7NXbadmoLm+NdXFNj9ZOxzqFFYMPhYeHc/XVV9O0aVNCQkJ8/vFvvPFGVq1aRZcuXXjvvfcIDQ3lrrvuorS0lMsuu4wVK1YwbNgwVq5cyY033ujzxzfGVE3izlwmLUgi4+AJ7nB1YMqN3WlSr+a9d1lQXnx2itvtZsCAAXz88cfExsb6/OPv3buXsWPHsmzZsrOOu+KKK1i8eDHNmjU7Y19N+HcyprbJP1nCi0u3MPfbnbRrUo8Zt/VmaKz/f1HXLj77WVpaGjfddBOjR4+ullIAaNu2LQ888ABHjx6t8HcZDh48yMSJE8stBWOM/32bfoi4hUlk5hYw9tKOTBrRjYZ1a/a33pqdLoD06NGDjIyMan+c22+//az7W7ZsyS233FLtOYwxZ3e0sJjnl2zmw3W7iYmsz/wJQxjc+cxXKtZEVgzGGONjK7ccYMrCZPYfLeSBoZ2YOLwr9cJ9f92xulgxGGOMjxzJP8n0z9JY+P0eYls15LWHL6N/dOA9rWvFYIwxPrA0dR9PLEoh98RJfjusC48M60Ld0MCZJZRlxWCMMVVw6HgR0xJS+TxpLz3aNuadewfSq30Tp2NViRVDDVZUVMTYsWPZsGEDkZGRzJ8/n5iYGKdjGWPwLJebsDGbZz5N43hhCb+79mIevPIiwkL8uf5Z9bBiqMHefvttmjVrRnp6OvPmzSMuLo758+c7HcuYWm//0UKmfpLCV5v207dDU14c08fvb41dnQK/2moIX7/tNsDixYsZN24cAGPGjGH58uUE4i8kGhMsVJWPEjO55k//Ys22g0y9oTsLH74sqEoBgnXG8MXjsO/Mt5yukja94foZFe4eP348t956K48++ihut5t58+axbt26M8adz5vo7dmzhw4dPAvchYaG0qRJE3JycmjRokUVT8YYc76yDuczeWEya7YdYlBMc2aO6UOnFg2cjlUtgrMYHFAdb7td3uzAuxCeMcZP3G7l/XW7mbFkEwpMH9WTuwd3pE6d4P1a9EkxiMgc4CbggKqe8baeIvIrIM579zjwsKpu9O7bCRwDSoGSyryPxzmd5Sf76uTrt92OiooiMzOTqKgoSkpKyMvLo3nz5tWS3Rhzpp2HThC3IIl/78jlZ11a8PytvenQvL7Tsaqdr2YMc4FZwHsV7N8BXKmqh0XkemA2MLjM/qtV9ZCPsjjG12+7PXLkSN59910uvfRS4uPjGTZsmM0YjPGDUrfyzjc7eOnLLYTVqcPM23pzu6tDrfn680kxqOpqEYk5y/5vy9xdC0T54nFrGl+/7fb48eO555576NKlC82bN2fevHk+SGmMOZv0A8d4LD6JH3Yf4efdWvHc6N60aeL7ZTZrMieuMYwHvihzX4EvRUSBN1V1dnkHicgEYAJAdHR0tYe8EG63m7Vr1/Lxxx/75ONFRET47GMZY86upNTNm6szePmrbdSvG8LLd/ZjZN92tWaWUJZfi0FErsZTDD8rs/lyVc0WkVbAMhHZrKqrTz/WWxizwbMeg18Cnwd/vO22MaZ6pGUfZdKCjaTsOcoNvdvwzMhetGxU1+lYjvFbMYhIH+At4HpVzflpu6pme/8+ICKfAIOAM4qhpvPX224bY3ynqKSUV1ek89qq7TStH8brvxrA9b3bOh3LcX4pBhGJBhYC96jq1jLbGwB1VPWY9/a1wPQLfRxVrZXTvsqyX44z5v/8mHmESfEb2br/OKP7t+epm3rQrEG407FqBF+9XPVD4CqghYhkAdOAMABVfQN4CogEXvN+4/7pZamtgU+820KBD1T1nxeSISIigpycHCIjI60cyqGq5OTkEBFRuy6iGXO6wuJS/rxsK39bk0GrRhHMudfFsG6tnY5VowTNms/FxcVkZWVRWFjoUKqaLyIigqioKMLCat7i48b4w/qduUyKT2LHoRPcObADU27sTuOI2vP1UOvWfA4LC6NTp05OxzDG1EAnikp4cekW3v1uJ+2b1uMf4wfzs1h7a5mKBE0xGGNMeb5JP0TcgiT2HClg7JCOTBrRjQZ17Vvf2di/jjEmKB0tLOb5JZv4cF0mnVs04KMHL2VgjL2lTGVYMRhjgs6KzfuZsjCFA8cKefCKzvzP8IuJCAvMZTadYMVgjAkaR/JP8synaXzywx4ubt2QN++5nL4dmjodK+BYMRhjgsI/U/byxKJUjuSf5LfDuvDIsC7UDbVZwoWwYjDGBLRDx4uYtjiVz5P30rNdY969byA92zVxOlZAs2IwxgQkVSVhYzZPJ6RyoqiUx67ryoQrOhMWYisWV5UVgzEm4OzLK+SJRcl8tekA/aOb8uKYPnRpFVzrLjvJisEYEzBUlY8SM/n955soLnXzxI3d+fXlnQgJ4mU2nWDFYIwJCJm5+Uz5JJk12w4xuFNzZt7Wh5gWDZyOFZSsGIwxNZrbrfzj37uY8cVmBHj2ll78alA0dWyWUG2sGIwxNdaOQyeIW5DEuh25DI1twfO39iaqWX2nYwU9KwZjTI1T6lbmfL2Dl77cQnhoHV4Y04dfXBJlb6nvJ1YMxpgaZdv+Y/wuPomNmUe4pntrnhvdi9aNbR0Rf7JiMMbUCMWlbt7813ZeWZ5Og7ohvHxnP0b2bWezBAf45DdBRGSOiBwQkZQK9ouIvCIi6SKSJCIDyuwbJyLbvH/G+SKPMSawpGbnMWrWN7z05Vau7dmaZROvZFS/9lYKDvHVjGEuMAt4r4L91wOx3j+DgdeBwSLSHM8yoC5AgQ0ikqCqh32UyxhTgxWVlDJrRTqvr9pOswbhvHH3JYzo1cbpWLWeT4pBVVeLSMxZhowC3lPPOqJrRaSpiLTFs070MlXNBRCRZcAI4ENf5DLG1Fw/Zh5hUvxGtu4/zm0Donjypu40rR/udCyD/64xtAcyy9zP8m6raPsZRGQCMAEgOjq6elIaY6pdYXEpf1q2lbfWZNC6cQTv/HogV3dt5XQsU4a/iqG8Jwr1LNvP3Kg6G5gN4HK5yh1jjKnZ1u3IJW5BEjsOneCuwdFMvr4bjSLCnI5lTuOvYsgCOpS5HwVke7dfddr2VX7KZIzxkxNFJcz852be+24XHZrX44P7B3NZlxZOxzIV8FcxJACPiMg8PBef81R1r4gsBf4gIs28464FJvspkzHGD77edoi4BUlk5xXw68tjeOy6rtQPt1fK12Q++d8RkQ/x/OTfQkSy8LzSKAxAVd8AlgA3AOlAPvBr775cEXkWWO/9UNN/uhBtjAlseQXF/OHzTcxPzKRziwZ8/OCluGKaOx3LVIKvXpX0y3PsV+A3FeybA8zxRQ5jTM2wfNN+pnySzMFjRTx05UX89zWxRITZMpuBwuZzxhifOXziJM98msqiH7Pp2roRfxvrok9UU6djmfNkxWCM8YklyXt5anEKR/KLefTnsfzm6i6Eh9oym4HIisEYUyUHjhUybXEqX6Tso1f7xvx9/GC6t23sdCxTBVYMxpgLoqos+nEPz3yaRv7JUuJGdOOBoZ0IDbFZQqCzYjDGnLe9eQVM/SSFFZsPcEnHZsy8rQ9dWjV0OpbxESsGY0ylqSrz12fy3OebKHa7eeqmHoy7LIYQW2YzqFgxGGMqJTM3n8cXJvFNeg5DOjdn5m196BjZwOlYphpYMRhjzsrtVt77bicvLN1CHRGeG92LXw6Mpo7NEoKWFYMxpkIZB48TtyCJ9TsPc8XFLXn+1t60b1rP6VimmlkxGGPOUFLq5u2vd/CnZVupG1qHl37Rl9sG2IpqtYUVgzHmFFv2HWNS/EY2ZuUxvEdrnrulF60aRzgdy/iRFYMxBoDiUjevr9rOX1dso1FEGH/9ZX9u6tPWZgm1kBWDMYaUPXk8Fp/Epr1HualPW54Z2ZPIhnWdjmUcYsVgTC1WWFzKX1ds441/ZRDZIJzZ91zCtT3bOB3LOMyKwZha6vvdh5kUn0T6geOMuSSKJ2/sQZP6tsym8d1CPSOAl4EQ4C1VnXHa/j8DV3vv1gdaqWpT775SINm7b7eqjvRFJmNM+QpOlvLHL7fw9jc7aNs4gnfvG8SVF7d0OpapQapcDCISArwKDMezhvN6EUlQ1bSfxqjq/5QZ/1ugf5kPUaCq/aqawxhzbt9tz+HxhUnsysnnV4Ojefz6bjSKsFmCOZUvZgyDgHRVzQDwrus8CkirYPwv8Sz9aYzxk+NFJcz8YjN/X7uLjpH1mTdhCEM6Rzody9RQviiG9kBmmftZwODyBopIR6ATsKLM5ggRSQRKgBmqusgHmYwxXqu3HmTywmSy8woY/7NO/O7artQLt2U2TcV8UQzlvchZKxh7JxCvqqVltkWraraIdAZWiEiyqm4/40FEJgATAKKjo6ua2Zigl1dQzHOfp/FRYhYXtWxA/EOXcUnHZk7HMgHAF8WQBXQocz8KyK5g7J3Ab8puUNVs798ZIrIKz/WHM4pBVWcDswFcLldFxWOMAZal7WfqJ8nknDjJw1ddxKM/jyUizGYJpnJ8UQzrgVgR6QTswfPN/67TB4lIV6AZ8F2Zbc2AfFUtEpEWwOXACz7IZEytlHviJE8npJKwMZtubRrx9riB9I5q4nQsE2CqXAyqWiIijwBL8bxcdY6qporIdCBRVRO8Q38JzFPVsj/tdwfeFBE3UAfPNYaKLlobYyqgqnyevJdpi1M5WljMf18Ty39d1YXwUFtm05w/OfX7dGBwuVyamJjodAxjaoQDxwp5clEKS1P30yeqCS+M6UO3No2djmVqIBHZoKquc42z33w2JkCpKgu/38P0z9IoKC4lbkQ3HhjaidAQmyWYqrFiMCYAZR8pYMonyazachBXx2bMHNOHi1o2dDqWCRJWDMYEEFXlw3WZ/GHJJkrdyrSbezDu0hhbZtP4lBWDMQFid04+jy9M4tvtOVx2USQzb+tDh+b1nY5lgpAVgzE1XKlbeffbnby4dAshdYTnb+3NnQM72AI6ptpYMRhTg6UfOE7cgiQ27DrM1V1b8tzo3rRrWs/pWCbIWTEYUwOVlLr525od/PmrrdQLC+FPt/dldP/2NkswfmHFYEwNs3nfUR77OInkPXlc17M1z97Si1aNIpyOZWoRKwZjaoiTJW5eW5XOqyvTaRwRxqt3DeCG3m1slmD8zorBmBogOSuPx+I3snnfMUb1a8e0m3vSvEG407FMLWXFYIyDCotLeXn5NmavziCyQTh/G+tieI/WTscytZwVgzEO2bDrMJPiN7L94Alud0Ux9cYeNKlny2wa51kxGONn+SdLeGnpVt75dgftmtTjvfsGccXFLZ2OZcx/WDEY40ffbc8hbkESu3PzGXtpRyaN6EbDuvZlaGoW+4w0xg+OFRYz44vNvP/v3cRE1mf+hCEM7hzpdCxjymXFYEw1W7XlAFMWJrPvaCEPDO3ExOFdqRduy2yamssnb9wuIiNEZIuIpIvI4+Xsv1dEDorIj94/95fZN05Etnn/jPNFHmNqgiP5J/nfjzZy7zvrqV83lAUPX8bUG3tYKZgar8ozBhEJAV4FhgNZwHoRSShnic75qvrIacc2B6YBLkCBDd5jD1c1lzFOWpq6jycWpZB74iS/HdaFR4Z1oW6oFYIJDL54KmkQkK6qGQAiMg8YBVRm7ebrgGWqmus9dhkwAvjQB7mM8buc40VMS0jls6S9dG/bmHfuHUiv9k2cjmXMefFFMbQHMsvczwIGlzPuNhG5AtgK/I+qZlZwbHsfZDLGr1SVT5P28nRCKscLS/jdtRfz4JUXEWbLbJoA5ItiKO+NXPS0+58CH6pqkYg8BLwLDKvksZ4HEZkATACIjo6+8LTG+NiBo4VMXZTCsrT99O3QlBfH9OHi1o2cjmXMBfNFMWQBHcrcjwKyyw5Q1Zwyd/8GzCxz7FWnHbuqvAdR1dnAbACXy1VueRjjT6pK/IYsnv0sjaISN1Nu6Mb4n3UmxJbZNAHOF8WwHogVkU7AHuBO4K6yA0Skraru9d4dCWzy3l4K/EFEmnnvXwtM9kEmY6rVniMFTF6YzOqtBxkY04yZt/Whc8uGTscyxieqXAyqWiIij+D5Jh8CzFHVVBGZDiSqagLw/0RkJFAC5AL3eo/NFZFn8ZQLwPSfLkQbUxO53coH63Yz44vNuFV5ZmRP7hnSkTo2SzBBRFQD71kZl8uliYmJTscwtcyunBPELUhibUYul3eJZMatfejQvL7TsYypNBHZoKquc42z33w25hxK3crcb3fy4tLNhNWpw8zbenO7q4MtoGOClhWDMWeRfuA4k+I38v3uIwzr1ornRveibZN6TscyplpZMRhTjpJSN7PXZPCXr7ZRPzyEv9zRj1H92tkswdQKVgzGnCYt+yiTFmwkZc9Rru/VhumjetGyUV2nYxnjN1YMxnidLHEza2U6r61Mp2n9MF7/1QCu793W6VjG+J0VgzHAxswjTIpPYsv+Y4zu356nbupBswbhTscyxhFWDKZWKywu5c9fbeVvqzNo1SiCOfe6GNattdOxjHGUFYOptdbvzGVSfBI7Dp3gl4M6MPmG7jSOCHM6ljGOs2Iwtc6JohJeXLqFd7/bSfum9fjH+MH8LLaF07GMqTGsGEyt8m36IeIWJpGZW8DYSzsSN6IbDeral4ExZdlXhKkVjhYW8/ySzXy4bjcxkfWZP2EIgztHOh3LmBrJisEEvZVbDjBlYTL7jxbywNBOTBze1dZdNuYsrBhM0DqSf5Lpn6Wx8Ps9XNy6Ia/ffTn9OjR1OpYxNZ4VgwlK/0zZxxOLUjiSf5LfDuvCI8O6UDfUZgnGVIYVgwkqh44XMS0hlc+T9tKzXWPevW8gPds1cTqWMQHFisEEBVUlYWM2TyekcqKolN9dezEPXnkRYSF1nI5mTMDxSTGIyAjgZTwruL2lqjNO2z8RuB/PCm4HgftUdZd3XymQ7B26W1VH+iKTqT325RXyxKJkvtp0gH4dmvLimD7Etm7kdCxjAlaVi0FEQoBXgeFAFrBeRBJUNa3MsB8Al6rmi8jDwAvAHd59Barar6o5TO2jqny8IYtnP0ujuNTN1Bu6c9/POhFiy2waUyW+mDEMAtJVNQNAROYBo4D/FIOqriwzfi1wtw8e19RiWYfzmbwwmTXbDjG4U3Nm3taHmBYNnI5lTFDwRTG0BzLL3M8CBp9l/HjgizL3I0QkEc/TTDNUdZEPMpkg5XYr7/97FzO+2AzAs6N68qvBHaljswRjfMYXxVDeV6SWO1DkbsAFXFlmc7SqZotIZ2CFiCSr6vZyjp0ATACIjo6uemoTcHYcOkHcgiTW7chlaGwLnr+1N1HN6jsdy5ig44tiyAI6lLkfBWSfPkhErgGmAleqatFP21U12/t3hoisAvoDZxSDqs4GZgO4XK5yi8cEp1K3MufrHfxx2RbCQurwwpg+/OKSKFtm05hq4otiWA/EikgnYA9wJ3BX2QEi0h94ExihqgfKbG8G5KtqkYi0AC7Hc2HaGAC27T/GY/FJ/Jh5hGu6t+K50b1p3TjC6VjGBLUqF4OqlojII8BSPC9XnaOqqSIyHUhU1QTgRaAh8LH3p7yfXpbaHXhTRNxAHTzXGNLKfSBTqxSXupm9OoOXv9pGg7ohvHxnP0b2bWezBGP8QFQD71kZl8uliYmJTscw1SQ1O49J8UmkZh/lht5teGZkL1o2qut0LGMCnohsUFXXucbZbz6bGqOopJRXV6Tz2qrtNK0fzht3D2BEr7ZOxzKm1rFiMDXCj5lHmBS/ka37j3PrgPY8dVMPmtYPdzqWMbWSFYNxVGFxKX9atpW31mTQunEE79w7kKu7tXI6ljG1mhWDccy6HbnELUhix6ET3DU4msnXd6NRRJjTsYyp9awYjN+dKCrhhX9u5t3vdhHVrB7v3z+Yy7u0cDqWMcbLisH41dfbDhG3IInsvALuvSyGx67rSoO69mloTE1iX5HGL44WFvOHzzcxb30mnVs04KMHL2VgTHOnYxljymHFYKrd8k37mfpJCgeOFfLQlRfx39fEEhFmy2waU1NZMZhqc/jESZ75NJVFP2bTtXUj3rznEvp2aOp0LGPMOVgxmGrxRfJenlycwpH8Yh79eSy/uboL4aG2zKYxgcCKwfjUwWNFTEtIYUnyPnq1b8x79w2mR7vGTscyxpwHKwbjE6rKoh/38MynaeQXlTJpRFcmDO1MaIjNEowJNFYMpsr25hUw9ZMUVmw+QP/oprw4pg9dWjVyOpYx5gJZMZgLpqrMX5/Jc59votjt5smbenDvZTGE2DKbxgQ0KwZzQTJz85m8MJmv0w8xuFNzXhjTh46RDZyOZYzxASsGc17cbuXva3cx85+bEeD3t/TirkHR1LFZgjFBwydXBkVkhIhsEZF0EXm8nP11RWS+d/+/RSSmzL7J3u1bROQ6X+Qx1SPj4HHumP0d0xJSccU058uJV3L3kI5WCsYEmSrPGEQkBHgVGA5kAetFJOG0JTrHA4dVtYuI3AnMBO4QkR541ojuCbQDvhKRi1W1tKq5jO+UupW3v87gj19upW5oHV4c04cxl0TZMpvGBClfPJU0CEhX1QwAEZkHjALKFsMo4Gnv7Xhglni+q4wC5qlqEbBDRNK9H+87H+QyPrB1/zEei09iY+YRhvdozXO39KJV4winYxljqpEviqE9kFnmfhYwuKIxqloiInlApHf72tOObe+DTOX74nHYl1xtHz6YuFGyjxRw+HABT9YRYqIaEFkajiywWYIxjmnTG66fUe0P44tiKO87hVZyTGWO9XwAkQnABIDo6OjzyWfO04mTJWw/eJz8k6VENggnJrIBYfaLasbUGr4ohiygQ5n7UUB2BWOyRCQUaALkVvJYAFR1NjAbwOVylVse5+SHpg1kRSWl/HV5Oq//azvNG4Tz+zt6MaRnG6djGWP8zBfFsB6IFZFOwB48F5PvOm1MAjAOz7WDMcAKVVURSQA+EJE/4bn4HAus80Emc55+2H2Yx+KTSD9wnDGXRPHkjT1oUt+W2TSmNqpyMXivGTwCLAVCgDmqmioi04FEVU0A3gb+7r24nIunPPCO+wjPheoS4Df2iiT/KjhZyh+/3MKcb3bQpnEEc389kKu6tnI6ljHGQaJ6Yc/KOMnlcmliYqLTMQLe2owc4hYksSsnn7sGRzP5+m40ijhzlvDGG2/wxhtvAJCXl0dMTAwrV670d1xjTBWJyAZVdZ1rnP3mcy10vKiEmV9s5u9LZPk2AAAMt0lEQVRrdxHdvD4fPDCYyy5qUeH4hx56iIceeoji4mKGDRvGxIkT/ZjWGONvVgy1zOqtB5m8MJnsvAJ+fXkMj13Xlfrhlfs0ePTRRxk2bBg333xzNac0xjjJiqGWyCso5rnP0/goMYvOLRsQ/9ClXNKxeaWPnzt3Lrt27WLWrFnVmNIYUxNYMdQCy9L2M/WTZHJOnOThqy7i0Z/HEhEWUunjN2zYwEsvvcSaNWuoU8d+n8GYYGfFEMRyT5zkmU9TWfxjNt3aNOKtcS76RDU9748za9YscnNzufrqqwFwuVy89dZbvo5rjKkhrBiCkKqyJHkfTy1OIa+gmP++Jpb/uqoL4aEX9tP+O++84+OExpiazIohyBw4VshTi1L5Z+o+erdvwj/uH0z3to2djmWMCSBWDEFCVVn4/R6mf5ZGQXEpcSO68cDQToTaexwZY86TFUMQyD5SwJRPklm15SCXdGzGC2P6cFHLhk7HMsYEKCuGAKaqfLgukz8s2USpW5l2cw/GXhpDiK2oZoypAiuGAJWZm0/cgiS+3Z7DZRdFMuPWPkRH1nc6ljEmCFgxBBi3W3n3u5288M8thNQRnhvdi7sGRdsym8YYn7FiCCDbDx4nLj6JxF2HuaprS/4wujftmtZzOpYxJshYMQSAklI3b329gz8t20q9sBD+dHtfRvdvb7MEY0y1sGKo4TbvO8qk+CSSsvK4rmdrnr2lF60aRTgdyxgTxKwYaqiTJW5eX7WdWSu30TgijFfvGsANvdvYLMEYU+2qVAwi0hyYD8QAO4HbVfXwaWP6Aa8DjYFS4DlVne/dNxe4EsjzDr9XVX+sSqZgkJyVx2PxG9m87xgj+7bj6ZE9ad4g3OlYxphaoqozhseB5ao6Q0Qe996PO21MPjBWVbeJSDtgg4gsVdUj3v2PqWp8FXMEhcLiUl5Zvo03V2cQ2SCcv411MbxHa6djGWNqmaoWwyjgKu/td4FVnFYMqrq1zO1sETkAtASOYP5jw67DTIrfyPaDJ7jdFcXUG3vQpN6Zy2waY0x1q2oxtFbVvQCquldEzrqKvIgMAsKB7WU2PyciTwHLgcdVtaiKmQJKwclSXvpyC3O+2UG7JvV4975BXHlxS6djGWNqsXMWg4h8BbQpZ9fU83kgEWkL/B0Yp6pu7+bJwD48ZTEbz2xjegXHTwAmAERHR5/PQ9dY323P4fGFSezKyeeeIR2Ju74bDeva6wGMMc4653chVb2mon0isl9E2npnC22BAxWMawx8DjyhqmvLfOy93ptFIvIO8Luz5JiNpzxwuVx6rtw12fGiEmZ8sYl/rN1Nx8j6fPjAEC69KNLpWMYYA1T9qaQEYBwww/v34tMHiEg48Anwnqp+fNq+n0pFgFuAlCrmqfH+tfUgUxYmk51XwP0/68T/XtuVeuGVX2bTGGOqW1WLYQbwkYiMB3YDvwAQERfwkKreD9wOXAFEisi93uN+elnq+yLSEhDgR+ChKuapsfLyi/n952l8vCGLLq0asuDhyxgQ3czpWMYYcwZRDbxnZVwulyYmJjodo9K+TN3H1EUp5J44yYNXdOb//TyWiDCbJRhj/EtENqiq61zj7EpnNco5XsTTn6bx6cZsurdtzDv3DqRX+yZOxzLGmLOyYqgGqspnSXuZlpDKscJiJg6/mIevuogwW2bTGBMArBh87MDRQp5YlMKXafvpG9WEF8YMoWubRk7HMsaYSrNi8BFVZcH3e5j+aSpFJW6m3NCN+y7vRKjNEowxAcaKwQf2HClgysJk/rX1IK6OzXhhTB86t2zodCxjjLkgVgxV4HYrH67fzfNLNuNW5ZmRPblnSEfq1LG3xjbGBC4rhgu0K+cEjy9I5ruMHC7vEsmMW/vQoXl9p2MZY0yVWTGcp1K3Mvfbnby4dDNhdeow49be3DGwgy2gY4wJGlYM5yH9wHEmxW/k+91HGNatFc+N7kXbJvWcjmWMMT5lxVAJJaVu3lydwcvLt1EvLIQ/39GXW/q1t1mCMSYoWTGcQ1r2USYt2EjKnqNc36sN00f1omWjuk7HMsaYamPFUIGTJW5eXZnOqyvTaVIvjNd+NYAberd1OpYxxlQ7K4ZyJGUd4bGPk9iy/xij+rVj2s09ad4g3OlYxhjjF1YMZRQWl/KXr7Yxe/V2Wjaqy1tjXVzTo7XTsYwxxq+sGLwSd+YyaUESGQdPcIerA1Nu7E6TemFOxzLGGL+r9cWQf7KEF5duYe63O2nXpB5/Hz+IobEtnY5ljDGOqVIxiEhzYD4QA+wEblfVw+WMKwWSvXd3q+pI7/ZOwDygOfA9cI+qnqxKpvPxbfoh4hYmkZlbwNhLOzJpRDca1q31XWmMqeWq+tafjwPLVTUWWO69X54CVe3n/TOyzPaZwJ+9xx8GxlcxT6UcKyxmyifJ3PXWvwkRYf6EIUwf1ctKwRhjqPpTSaOAq7y33wVWAXGVOVA8vx02DLirzPFPA69XMdNZrdxygCkLk9l/tJAHhnZi4vCu1Au3ZTaNMeYnVS2G1qq6F0BV94pIqwrGRYhIIlACzFDVRUAkcERVS7xjsoD2VcxzVpMXJvPhut3EtmrIaw9fRv/oZtX5cMYYE5DOWQwi8hXQppxdU8/jcaJVNVtEOgMrRCQZOFrOOD1LjgnABIDo6OjzeOj/ExNZn98O68Ijw7pQN9RmCcYYU55zFoOqXlPRPhHZLyJtvbOFtsCBCj5GtvfvDBFZBfQHFgBNRSTUO2uIArLPkmM2MBvA5XJVWCBn8+CVF13IYcYYU6tU9eJzAjDOe3scsPj0ASLSTETqem+3AC4H0lRVgZXAmLMdb4wxxr+qWgwzgOEisg0Y7r2PiLhE5C3vmO5AoohsxFMEM1Q1zbsvDpgoIul4rjm8XcU8xhhjqkg8P7gHFpfLpYmJiU7HMMaYgCIiG1TVda5xVZ0xGGOMCTJWDMYYY05hxWCMMeYUVgzGGGNOYcVgjDHmFAH5qiQROQjsusDDWwCHfBgnENg51w52zsGvqufbUVXPua5AQBZDVYhIYmVerhVM7JxrBzvn4Oev87WnkowxxpzCisEYY8wpamMxzHY6gAPsnGsHO+fg55fzrXXXGIwxxpxdbZwxGGOMOYugLQYRGSEiW0QkXUTOWItaROqKyHzv/n+LSIz/U/pWJc55ooikiUiSiCwXkY5O5PSlc51zmXFjRERFJKBfwVKZ8xWR273/z6ki8oG/M/paJT6vo0VkpYj84P3cvsGJnL4kInNE5ICIpFSwX0TkFe+/SZKIDPBpAFUNuj9ACLAd6AyEAxuBHqeN+S/gDe/tO4H5Tuf2wzlfDdT33n64Npyzd1wjYDWwFnA5nbua/49jgR+AZt77rZzO7Ydzng087L3dA9jpdG4fnPcVwAAgpYL9NwBfAAIMAf7ty8cP1hnDICBdVTNU9SQwDxh12phRwLve2/HAz0VE/JjR1855zqq6UlXzvXfX4lk1L5BV5v8Z4FngBaDQn+GqQWXO9wHgVVU9DKCq5a6qGEAqc84KNPbebsJZVoIMFKq6Gsg9y5BRwHvqsRbPaphtffX4wVoM7YHMMvezvNvKHaOepUXz8CwWFKgqc85ljcfzE0cgO+c5i0h/oIOqfubPYNWkMv/HFwMXi8g3IrJWREb4LV31qMw5Pw3cLSJZwBLgt/6J5qjz/Xo/L+dc8zlAlfeT/+kvv6rMmEBS6fMRkbsBF3BltSaqfmc9ZxGpA/wZuNdfgapZZf6PQ/E8nXQVnhnhGhHppapHqjlbdanMOf8SmKuqfxSRS4G/e8/ZXf3xHFOt37+CdcaQBXQocz+KM6eX/xkjIqF4pqBnm7rVdJU5Z0TkGmAqMFJVi/yUrbqc65wbAb2AVSKyE89zsQkBfAG6sp/Xi1W1WFV3AFvwFEWgqsw5jwc+AlDV74AIPO8pFMwq9fV+oYK1GNYDsSLSSUTC8VxcTjhtTAIwznt7DLBCvVd1AtQ5z9n7tMqbeEoh0J97hnOcs6rmqWoLVY1R1Rg811VGqmqgrgtbmc/rRXheZICItMDz1FKGX1P6VmXOeTfwcwAR6Y6nGA76NaX/JQBjva9OGgLkqepeX33woHwqSVVLROQRYCmeVzXMUdVUEZkOJKpqAvA2nilnOp6Zwp3OJa66Sp7zi0BD4GPvdfbdqjrSsdBVVMlzDhqVPN+lwLUikgaUAo+pao5zqaumkuf8v8DfROR/8Dydcm+A/5CHiHyI5+nAFt5rJ9OAMABVfQPPtZQbgHQgH/i1Tx8/wP/9jDHG+FiwPpVkjDHmAlkxGGOMOYUVgzHGmFNYMRhjjDmFFYMxxphTWDEYY4w5hRWDMcaYU1gxGGOMOcX/B3bQQfTK+WKMAAAAAElFTkSuQmCC\n"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## REFERENCE: Final Version for Scikit-learn Style"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.910531Z",
"end_time": "2019-03-04T16:04:31.914560Z"
}
},
"cell_type": "code",
"source": "class FindPoint:\n \"\"\"\n An algorithm to find a \"special point\" of a function.\n :attr z_: the special point.\n \"\"\"\n def __init__(self):\n self.f_ = None\n self.z_ = None\n \n def run(self, f):\n \"\"\"\n :param f: the function.\n :return: itself.\n Must update self.f_ and self.z_.\n \"\"\"\n raise NotImplementedError\n \n def plot(self):\n \"\"\"\n Illustrate the method.\n This method must be used after :meth:`run`.\n \"\"\"\n x = np.arange(0.0, 1.0, .01)\n plt.plot(x, self.f_(x), label='y = f(x)')\n plt.plot([0, 1], [0, 0], label='y = 0')\n plt.legend()\n plt.text(self.z_, -.1, 'z')",
"execution_count": 46,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.915519Z",
"end_time": "2019-03-04T16:04:31.932507Z"
}
},
"cell_type": "code",
"source": "class FindZeroDichotomy(FindPoint):\n \"\"\"\n An algorithm to find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param epsilon: the precision desired.\n :attr z_: the zero.\n :attr number_iterations_: number of iterations performed.\n \"\"\"\n def __init__(self, epsilon=1e-6):\n super().__init__()\n self.epsilon = epsilon\n self.number_iterations_ = None\n \n def run(self, f):\n self.f_ = f\n x, y, z = 0, 1, .5\n self.number_iterations_ = 0\n while y - x > self.epsilon:\n self.number_iterations_ += 1\n z = (x + y) / 2\n x, y = (z, y) if f(z) < 0 else (x, z)\n self.z_ = z\n return self",
"execution_count": 47,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.933469Z",
"end_time": "2019-03-04T16:04:31.945437Z"
}
},
"cell_type": "code",
"source": "class FindZeroAffine(FindPoint):\n \"\"\"\n An algorithm to find the zero of a non-constant affine function R -> R.\n \"\"\"\n def run(self, f):\n self.f_ = f\n self.z_ = - f(0) / (f(1) - f(0))\n return self",
"execution_count": 48,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.946434Z",
"end_time": "2019-03-04T16:04:31.959435Z"
}
},
"cell_type": "code",
"source": "class FindArgminGolden(FindPoint):\n \"\"\"\n An algorithm to find the argmin of a stricly convex function [0, 1] -> R by a golden-section search.\n :param epsilon: the precision desired.\n :attr z_: the argmin (up to the precision).\n :attr number_iterations_: number of iterations performed.\n \"\"\"\n def __init__(self, epsilon=1e-6):\n super().__init__()\n self.epsilon = epsilon\n self.number_iterations_ = None\n \n def run(self, f):\n self.f_ = f\n x, y, z = 0, 1, .5\n self.number_iterations_ = 0\n while y - x > self.epsilon:\n self.number_iterations_ += 1\n d = (math.sqrt(5) - 1) * (y - x) / 2\n a, b = y - d, x + d\n x, y, z = (x, b, a) if f(b) > f(a) else (a, y, b)\n self.z_ = z\n return self",
"execution_count": 49,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.960397Z",
"end_time": "2019-03-04T16:04:31.971394Z"
}
},
"cell_type": "code",
"source": "class BigAlgo:\n \"\"\"\n An algorithm to find a \"special point\" of a function, then add a number.\n :param find_point: a :class:`FindPoint` algorithm.\n :attr translated_point_: the \"special point\", plus translation.\n \"\"\"\n def __init__(self, find_point):\n self.find_point = find_point\n self.translated_point_ = None\n \n def run(self, f, translation):\n \"\"\"\n :param f: the function.\n :param translation: the number to be added.\n :return: itself.\n \"\"\"\n self.translated_point_ = self.find_point.run(f).z_ + translation\n return self",
"execution_count": 50,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "A few sanity checks:"
},
{
"metadata": {
"slideshow": {
"slide_type": "-"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.972365Z",
"end_time": "2019-03-04T16:04:31.985331Z"
}
},
"cell_type": "code",
"source": "BigAlgo(find_point=FindZeroDichotomy(epsilon=1e-6)).run(f=some_increasing_function, translation=42).translated_point_",
"execution_count": 51,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 51,
"data": {
"text/plain": "42.707106590270996"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.986329Z",
"end_time": "2019-03-04T16:04:31.998335Z"
}
},
"cell_type": "code",
"source": "BigAlgo(find_point=FindZeroAffine()).run(f=some_affine_function, translation=42).translated_point_",
"execution_count": 52,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 52,
"data": {
"text/plain": "42.25"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:31.999293Z",
"end_time": "2019-03-04T16:04:32.010286Z"
}
},
"cell_type": "code",
"source": "BigAlgo(find_point=FindArgminGolden(epsilon=1e-6)).run(f=some_convex_function, translation=42).translated_point_",
"execution_count": 53,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 53,
"data": {
"text/plain": "42.24999986562737"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "# A Variant of Architecture"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Call the Algorithm Like a Function"
},
{
"metadata": {
"slideshow": {
"slide_type": "-"
}
},
"cell_type": "markdown",
"source": "For the moment, we write commands such as:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.011261Z",
"end_time": "2019-03-04T16:04:32.026223Z"
}
},
"cell_type": "code",
"source": "find_zero = FindZeroDichotomy(epsilon=1e-6)\nfind_zero.run(f=some_increasing_function)\nprint('z =', find_zero.z_)\nprint('number_iterations =', find_zero.number_iterations_)",
"execution_count": 54,
"outputs": [
{
"output_type": "stream",
"text": "z = 0.7071065902709961\nnumber_iterations = 20\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "However, `find_zero` is an algorithm that we apply to something. Instead of writing something like `find_zero.run(f=...)`, it would be more natural and convenient to write `find_zero(f=...)`, as if it were a function."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "Solution: replace `run` with `__call__`. In the parent class:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.027220Z",
"end_time": "2019-03-04T16:04:32.039188Z"
}
},
"cell_type": "code",
"source": "class FindPoint:\n \"\"\"\n An algorithm to find a \"special point\" of a function.\n :attr z_: the special point.\n \"\"\"\n def __init__(self):\n self.f_ = None\n self.z_ = None\n \n def __call__(self, f): # Modified line\n \"\"\"\n :param f: the function.\n :return: itself.\n Must update self.f_ and self.z_.\n \"\"\"\n raise NotImplementedError\n \n # Other methods (e.g. \"plot\")...",
"execution_count": 55,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "In one subclass:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.040184Z",
"end_time": "2019-03-04T16:04:32.052153Z"
}
},
"cell_type": "code",
"source": "class FindZeroDichotomy(FindPoint):\n \"\"\"\n An algorithm to find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param epsilon: the precision desired.\n :attr z_: the zero.\n :attr number_iterations_: number of iterations performed.\n \"\"\"\n def __init__(self, epsilon=1e-6):\n super().__init__()\n self.epsilon = epsilon\n self.number_iterations_ = None\n \n def __call__(self, f): # Modified line\n self.f_ = f\n x, y, z = 0, 1, .5\n self.number_iterations_ = 0\n while y - x > self.epsilon:\n self.number_iterations_ += 1\n z = (x + y) / 2\n x, y = (z, y) if f(z) < 0 else (x, z)\n self.z_ = z\n return self",
"execution_count": 56,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.053150Z",
"end_time": "2019-03-04T16:04:32.066147Z"
}
},
"cell_type": "code",
"source": "find_zero = FindZeroDichotomy(epsilon=1e-6)\nfind_zero(f=some_increasing_function)\nprint('z = %s, number_iterations = %s' % (find_zero.z_, find_zero.number_iterations_))",
"execution_count": 57,
"outputs": [
{
"output_type": "stream",
"text": "z = 0.7071065902709961, number_iterations = 20\n",
"name": "stdout"
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.067112Z",
"end_time": "2019-03-04T16:04:32.079081Z"
}
},
"cell_type": "code",
"source": "FindZeroDichotomy(epsilon=1e-6)(f=some_increasing_function).z_",
"execution_count": 58,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 58,
"data": {
"text/plain": "0.7071065902709961"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Optional Call at Initialization"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "This is just a bit a syntactic sugar...\n\nFor the moment, we write things such as:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.080078Z",
"end_time": "2019-03-04T16:04:32.093081Z"
}
},
"cell_type": "code",
"source": "FindZeroDichotomy(epsilon=1e-6)(f=some_increasing_function).z_",
"execution_count": 59,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 59,
"data": {
"text/plain": "0.7071065902709961"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.094040Z",
"end_time": "2019-03-04T16:04:32.106041Z"
}
},
"cell_type": "code",
"source": "FindZeroDichotomy()(f=some_increasing_function).z_",
"execution_count": 60,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 60,
"data": {
"text/plain": "0.7071065902709961"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "The first pair of parentheses is for the `__init__` (taking the parameters of the algorithm) and the second pair of parentheses is for the `__call__` (taking the input of the algorithm). However, it would be nicer to have only one pair of parentheses (especially when one of the pairs above would be empty, as in the last example)."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "Solution: add an optional call at initialization. In the parent class:"
},
{
"metadata": {
"slideshow": {
"slide_type": "-"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.107005Z",
"end_time": "2019-03-04T16:04:32.117976Z"
}
},
"cell_type": "code",
"source": "class FindPoint:\n \"\"\"\n An algorithm to find a \"special point\" of a function.\n :attr z_: the special point.\n The __init__ of this parent class must always be called at the end of a subclass' __init__.\n \"\"\"\n def __init__(self, f=None): # Modified line\n self.f_ = None\n self.z_ = None\n if f is not None: # Added line\n self(f) # Added line\n \n def __call__(self, f):\n \"\"\"\n :param f: the function.\n :return: itself.\n Must update self.f_ and self.z_.\n \"\"\"\n raise NotImplementedError\n \n # Other methods...",
"execution_count": 61,
"outputs": []
},
{
"metadata": {
"ExecuteTime": {
"end_time": "2018-10-16T13:37:44.712486Z",
"start_time": "2018-10-16T13:37:44.706506Z"
},
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "In one subclass:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.118974Z",
"end_time": "2019-03-04T16:04:32.130941Z"
}
},
"cell_type": "code",
"source": "class FindZeroDichotomy(FindPoint):\n \"\"\"\n An algorithm to find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param epsilon: the precision desired.\n :attr z_: the zero.\n :attr number_iterations_: number of iterations performed.\n \"\"\"\n def __init__(self, f=None, epsilon=1e-6): # Modified line\n self.epsilon = epsilon\n self.number_iterations_ = None\n super().__init__(f=f) # Displaced and modified line\n \n def __call__(self, f):\n self.f_ = f\n x, y, z = 0, 1, .5\n self.number_iterations_ = 0\n while y - x > self.epsilon:\n self.number_iterations_ += 1\n z = (x + y) / 2\n x, y = (z, y) if f(z) < 0 else (x, z)\n self.z_ = z\n return self",
"execution_count": 62,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Now we can write commands with only one pair of parentheses:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.131939Z",
"end_time": "2019-03-04T16:04:32.144945Z"
}
},
"cell_type": "code",
"source": "FindZeroDichotomy(f=some_increasing_function, epsilon=1e-6).z_",
"execution_count": 63,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 63,
"data": {
"text/plain": "0.7071065902709961"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "However, it is still possible (as before) to define the algorithm first, then to call it:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.145901Z",
"end_time": "2019-03-04T16:04:32.157909Z"
}
},
"cell_type": "code",
"source": "find_zero = FindZeroDichotomy(epsilon=1e-6)\nfind_zero(f=some_increasing_function).z_",
"execution_count": 64,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 64,
"data": {
"text/plain": "0.7071065902709961"
},
"metadata": {}
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "This is very convenient, especially in cases where:\n* You specify a long list of fine-tuned parameters for your algorithm and you plan to use it several times afterwards;\n* Or you use `find_zero` as a parameter for a \"big algorithm\", like we did before."
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## REFERENCE: Final Version with the Variant Architecture"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.158867Z",
"end_time": "2019-03-04T16:04:32.169839Z"
}
},
"cell_type": "code",
"source": "class FindPoint:\n \"\"\"\n An algorithm to find a \"special point\" of a function.\n :attr z_: the special point.\n The __init__ of this parent class must always be called at the end of a subclass' __init__.\n \"\"\"\n def __init__(self, f=None):\n self.f_ = None\n self.z_ = None\n if f is not None:\n self(f)\n \n def __call__(self, f):\n \"\"\"\n :param f: the function.\n :return: itself.\n Must update self.f_ and self.z_.\n \"\"\"\n raise NotImplementedError\n \n def plot(self):\n \"\"\"\n Illustrate the method.\n This method must be used after :meth:`__call__`.\n \"\"\"\n x = np.arange(0.0, 1.0, .01)\n plt.plot(x, self.f_(x), label='y = f(x)')\n plt.plot([0, 1], [0, 0], label='y = 0')\n plt.legend()\n plt.text(self.z_, -.1, 'z')",
"execution_count": 65,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.170836Z",
"end_time": "2019-03-04T16:04:32.183840Z"
}
},
"cell_type": "code",
"source": "class FindZeroDichotomy(FindPoint):\n \"\"\"\n An algorithm to find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param epsilon: the precision desired.\n :attr z_: the zero.\n :attr number_iterations_: number of iterations performed.\n \"\"\"\n def __init__(self, f=None, epsilon=1e-6):\n self.epsilon = epsilon\n self.number_iterations_ = None\n super().__init__(f=f)\n \n def __call__(self, f):\n self.f_ = f\n x, y, z = 0, 1, .5\n self.number_iterations_ = 0\n while y - x > self.epsilon:\n self.number_iterations_ += 1\n z = (x + y) / 2\n x, y = (z, y) if f(z) < 0 else (x, z)\n self.z_ = z\n return self",
"execution_count": 66,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.184798Z",
"end_time": "2019-03-04T16:04:32.195769Z"
}
},
"cell_type": "code",
"source": "class FindZeroAffine(FindPoint):\n \"\"\"\n An algorithm to find the zero of a non-constant affine function R -> R.\n \"\"\"\n def __call__(self, f):\n self.f_ = f\n self.z_ = - f(0) / (f(1) - f(0))\n return self",
"execution_count": 67,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.196765Z",
"end_time": "2019-03-04T16:04:32.210728Z"
}
},
"cell_type": "code",
"source": "class FindArgminGolden(FindPoint):\n \"\"\"\n An algorithm to find the argmin of a stricly convex function [0, 1] -> R by a golden-section search.\n :param epsilon: the precision desired.\n :attr z_: the argmin (up to the precision).\n :attr number_iterations_: number of iterations performed.\n \"\"\"\n def __init__(self, f=None, epsilon=1e-6):\n self.epsilon = epsilon\n self.number_iterations_ = None\n super().__init__(f=f)\n \n def __call__(self, f):\n self.f_ = f\n x, y, z = 0, 1, .5\n self.number_iterations_ = 0\n while y - x > self.epsilon:\n self.number_iterations_ += 1\n d = (math.sqrt(5) - 1) * (y - x) / 2\n a, b = y - d, x + d\n x, y, z = (x, b, a) if f(b) > f(a) else (a, y, b)\n self.z_ = z\n return self",
"execution_count": 68,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.211726Z",
"end_time": "2019-03-04T16:04:32.222696Z"
}
},
"cell_type": "code",
"source": "class BigAlgo:\n \"\"\"\n An algorithm to find a \"special point\" of a function, then add a number.\n :param find_point: a :class:`FindPoint` algorithm.\n :attr translated_point_: the \"special point\", plus translation.\n \"\"\"\n def __init__(self, f=None, translation=None, find_point=None):\n self.find_point = find_point\n self.translated_point_ = None\n if f is not None:\n self(f=f, translation=translation)\n \n def __call__(self, f, translation):\n \"\"\"\n :param f: the function.\n :param translation: the number to be added.\n :return: itself.\n \"\"\"\n self.translated_point_ = self.find_point(f).z_ + translation\n return self",
"execution_count": 69,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "A few sanity checks:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.223694Z",
"end_time": "2019-03-04T16:04:32.235661Z"
}
},
"cell_type": "code",
"source": "FindZeroDichotomy(f=some_increasing_function, epsilon=1e-6).z_",
"execution_count": 70,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 70,
"data": {
"text/plain": "0.7071065902709961"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.236659Z",
"end_time": "2019-03-04T16:04:32.249625Z"
}
},
"cell_type": "code",
"source": "BigAlgo(f=some_increasing_function, translation=42, find_point=FindZeroDichotomy(epsilon=1e-6)).translated_point_",
"execution_count": 71,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 71,
"data": {
"text/plain": "42.707106590270996"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "# Intermezzo: Properties"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Property"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Assume you want to implement a complicated object that is able to compute a lot of things about itself. As a toy example, consider a class of equilateral triangles that come with a way to access their perimeter."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.250622Z",
"end_time": "2019-03-04T16:04:32.262590Z"
}
},
"cell_type": "code",
"source": "class EquilateralTriangle:\n \"\"\"\n An equilateral triangle.\n :param x: length of a side.\n :attr perimeter: the perimeter.\n \"\"\"\n def __init__(self, x):\n self.x = x\n self.perimeter = 3 * x",
"execution_count": 72,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Problem: each time a triangle is created, its perimeter is computed, even if we do not need it."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "Solution: create a method `perimeter`."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.264585Z",
"end_time": "2019-03-04T16:04:32.275593Z"
}
},
"cell_type": "code",
"source": "class EquilateralTriangle:\n \"\"\"\n An equilateral triangle.\n :param x: length of a side.\n \"\"\"\n def __init__(self, x):\n self.x = x\n\n def perimeter(self): # Added method\n \"\"\"\n :return: the perimeter.\n \"\"\"\n print(\"Computing the perimeter...\")\n return 3 * self.x",
"execution_count": 73,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.276554Z",
"end_time": "2019-03-04T16:04:32.287523Z"
}
},
"cell_type": "code",
"source": "some_triangle = EquilateralTriangle(x=42)\nprint('perimeter =', some_triangle.perimeter())\nprint('perimeter =', some_triangle.perimeter())",
"execution_count": 74,
"outputs": [
{
"output_type": "stream",
"text": "Computing the perimeter...\nperimeter = 126\nComputing the perimeter...\nperimeter = 126\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "* Small annoyance: now, we need to call `perimeter` with parentheses.\n* More serious issue: if we access the perimeter several times, it is computed each time!"
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "Solution to get rid of the parentheses: use the decorator `@property`, which transforms a zero-argument method into an attribute."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.288521Z",
"end_time": "2019-03-04T16:04:32.300489Z"
}
},
"cell_type": "code",
"source": "class EquilateralTriangle:\n \"\"\"\n An equilateral triangle.\n :param x: length of a side.\n \"\"\"\n def __init__(self, x):\n self.x = x\n\n @property # Added line\n def perimeter(self):\n \"\"\"\n :return: the perimeter.\n \"\"\"\n print(\"Computing the perimeter...\")\n return 3 * self.x",
"execution_count": 75,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.301486Z",
"end_time": "2019-03-04T16:04:32.313486Z"
}
},
"cell_type": "code",
"source": "some_triangle = EquilateralTriangle(x=42)\nprint('perimeter =', some_triangle.perimeter)\nprint('perimeter =', some_triangle.perimeter)",
"execution_count": 76,
"outputs": [
{
"output_type": "stream",
"text": "Computing the perimeter...\nperimeter = 126\nComputing the perimeter...\nperimeter = 126\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "But the problem remains: if we access the perimeter several times, it is computed each time!"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Cache a Property (\"Manually\")"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Solution: cache the property. Remark: this trick is very common in Python."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.314451Z",
"end_time": "2019-03-04T16:04:32.325422Z"
}
},
"cell_type": "code",
"source": "class EquilateralTriangle:\n \"\"\"\n An equilateral triangle.\n :param x: length of a side.\n \"\"\"\n def __init__(self, x):\n self.x = x\n self._perimeter = None # Added line\n\n @property\n def perimeter(self): # Rewritten method\n \"\"\"\n :return: the perimeter.\n \"\"\"\n if self._perimeter is None:\n print(\"Computing the perimeter...\")\n self._perimeter = 3 * self.x\n return self._perimeter",
"execution_count": 77,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.326420Z",
"end_time": "2019-03-04T16:04:32.338388Z"
}
},
"cell_type": "code",
"source": "some_triangle = EquilateralTriangle(x=42)\nprint('perimeter =', some_triangle.perimeter)\nprint('perimeter =', some_triangle.perimeter)",
"execution_count": 78,
"outputs": [
{
"output_type": "stream",
"text": "Computing the perimeter...\nperimeter = 126\nperimeter = 126\n",
"name": "stdout"
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "All this is perfectly fine if `x` is defined at the initialization of a triangle and never changes afterwards. But if we want to allow `x` to be modified, there is a bug:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.339386Z",
"end_time": "2019-03-04T16:04:32.351392Z"
}
},
"cell_type": "code",
"source": "some_triangle = EquilateralTriangle(x=42)\nprint('perimeter =', some_triangle.perimeter)\nprint('Changing the value of x...')\nsome_triangle.x = 51\nprint('perimeter =', some_triangle.perimeter)",
"execution_count": 79,
"outputs": [
{
"output_type": "stream",
"text": "Computing the perimeter...\nperimeter = 126\nChanging the value of x...\nperimeter = 126\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "The perimeter is computed once and for all, even if we modify `x` later!"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Empty the cache manually"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Solution: create a \"setter\" for `x` and use it to initialize the cache."
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.352350Z",
"end_time": "2019-03-04T16:04:32.363326Z"
}
},
"cell_type": "code",
"source": "class EquilateralTriangle:\n \"\"\"\n An equilateral triangle.\n :param x: length of a side.\n \"\"\"\n def __init__(self, x):\n self._x = x # Modified line\n self._initialize_cache() # Modified line\n\n def _initialize_cache(self): # Added method\n self._perimeter = None\n\n @property # Added getter for x (this is necessary when we want to have a setter)\n def x(self):\n return self._x\n \n @x.setter # Added setter for x\n def x(self, value):\n self._initialize_cache()\n self._x = value\n \n @property\n def perimeter(self):\n \"\"\"\n :return: the perimeter.\n \"\"\"\n if self._perimeter is None:\n print(\"Computing the perimeter...\")\n self._perimeter = 3 * self.x\n return self._perimeter",
"execution_count": 80,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "It works as expected:"
},
{
"metadata": {
"slideshow": {
"slide_type": "-"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.364318Z",
"end_time": "2019-03-04T16:04:32.376286Z"
}
},
"cell_type": "code",
"source": "some_triangle = EquilateralTriangle(x=42)\nprint('perimeter =', some_triangle.perimeter)\nprint('perimeter =', some_triangle.perimeter)\nsome_triangle.x = 51\nprint('perimeter =', some_triangle.perimeter)",
"execution_count": 81,
"outputs": [
{
"output_type": "stream",
"text": "Computing the perimeter...\nperimeter = 126\nperimeter = 126\nComputing the perimeter...\nperimeter = 153\n",
"name": "stdout"
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "This architecture works fine, but it is heavy. For example, if we want to add the area:"
},
{
"metadata": {
"scrolled": false,
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.378281Z",
"end_time": "2019-03-04T16:04:32.389251Z"
}
},
"cell_type": "code",
"source": "class EquilateralTriangle:\n \"\"\"\n An equilateral triangle.\n :param x: length of a side.\n \"\"\"\n def __init__(self, x):\n self._x = x\n self._initialize_cache()\n\n def _initialize_cache(self):\n self._perimeter = None\n self._area = None # Added line\n\n @property\n def x(self):\n return self._x\n \n @x.setter\n def x(self, value):\n self._initialize_cache()\n self._x = value\n \n @property\n def perimeter(self):\n \"\"\"\n :return: the perimeter.\n \"\"\"\n if self._perimeter is None:\n print(\"Computing the perimeter...\")\n self._perimeter = 3 * self.x\n return self._perimeter\n \n @property\n def area(self): # Added method\n \"\"\"\n :return: the area.\n \"\"\"\n if self._area is None:\n self._area = self.x**2 * math.sqrt(3) / 4 # Only line with some \"real\" information!!!\n return self._area",
"execution_count": 82,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## \"Automatic\" Cached Properties"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Here we provide a decorator `@cached_property`. No need to understand its code!"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.390248Z",
"end_time": "2019-03-04T16:04:32.402217Z"
}
},
"cell_type": "code",
"source": "def _cache(f):\n name = f.__name__\n def _f(*args):\n try:\n return args[0]._cached_properties[name]\n except KeyError:\n # Not stored in cache\n value = f(*args)\n args[0]._cached_properties[name] = value\n return value\n except AttributeError:\n # cache does not even exist\n value = f(*args)\n args[0]._cached_properties = {name: value}\n return value\n return _f\n\ndef cached_property(f):\n \"\"\"\n Decorator used in replacement of @property to put the value in cache automatically.\n \"\"\"\n return property(_cache(f))",
"execution_count": 83,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "We also provide a class `DeleteCacheMixin`. The code is simpler!"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.403214Z",
"end_time": "2019-03-04T16:04:32.414186Z"
}
},
"cell_type": "code",
"source": "class DeleteCacheMixin:\n def delete_cache(self):\n self._cached_properties = dict()",
"execution_count": 84,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Informally, a *mix-in* is a class designed for inheritance that just provides a small feature (here, the function `delete_cache`), but is not morally meant to be *the* parent class. A typical syntax is:\n\n class ChildClass(MixinClass, ParentClass):\n # Definition...\n\nYou should envision `ChildClass` as a subclass of `ParentClass`, with a small feature added by `MixinClass`."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.415181Z",
"end_time": "2019-03-04T16:04:32.433134Z"
}
},
"cell_type": "code",
"source": "class EquilateralTriangle(DeleteCacheMixin):\n \"\"\"\n An equilateral triangle.\n :param x: length of a side.\n \"\"\"\n def __init__(self, x):\n self._x = x\n\n @property\n def x(self):\n return self._x\n \n @x.setter\n def x(self, value):\n self.delete_cache()\n self._x = value\n \n @cached_property # This is the only block to write when adding a new property\n def perimeter(self):\n \"\"\"\n :return: the perimeter.\n \"\"\"\n print(\"Computing the perimeter...\")\n return 3 * self.x",
"execution_count": 85,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Advantages:\n* Adding a new property takes just 3 lines (plus documentation).\n* Everything about a property is in one block of code (much appreciated when the class gets longer!)."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "It works as expected:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.435128Z",
"end_time": "2019-03-04T16:04:32.448095Z"
}
},
"cell_type": "code",
"source": "some_triangle = EquilateralTriangle(x=42)\nprint('perimeter =', some_triangle.perimeter)\nprint('perimeter =', some_triangle.perimeter)\nsome_triangle.x = 51\nprint('perimeter =', some_triangle.perimeter)",
"execution_count": 86,
"outputs": [
{
"output_type": "stream",
"text": "Computing the perimeter...\nperimeter = 126\nperimeter = 126\nComputing the perimeter...\nperimeter = 153\n",
"name": "stdout"
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Why Some Other Tricks Would Fail"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "This section is only here for completeness and can be skipped."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "### PyPI package cached_property"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "There is also a PyPI package called `cached_property` that puts a property in cache. However, there seems to be no way to empty the whole cache of an object, like `DeleteCacheMixin` does."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "### LRU Cache"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.449090Z",
"end_time": "2019-03-04T16:04:32.460065Z"
}
},
"cell_type": "code",
"source": "from functools import lru_cache",
"execution_count": 87,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.461059Z",
"end_time": "2019-03-04T16:04:32.482003Z"
}
},
"cell_type": "code",
"source": "class EquilateralTriangle:\n \"\"\"\n An equilateral triangle.\n :param x: length of a side.\n \"\"\"\n def __init__(self, x):\n self.x = x\n\n @property\n @lru_cache(maxsize=1)\n def perimeter(self):\n \"\"\"\n :return: the perimeter.\n \"\"\"\n print(\"Computing the perimeter...\")\n return 3 * self.x",
"execution_count": 88,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.483001Z",
"end_time": "2019-03-04T16:04:32.494968Z"
}
},
"cell_type": "code",
"source": "small_triangle = EquilateralTriangle(x=42)\nprint('small perimeter =', small_triangle.perimeter)\nprint('small perimeter =', small_triangle.perimeter)\nlarge_triangle = EquilateralTriangle(x=51)\nprint('large perimeter =', large_triangle.perimeter)\nprint('small perimeter =', small_triangle.perimeter)",
"execution_count": 89,
"outputs": [
{
"output_type": "stream",
"text": "Computing the perimeter...\nsmall perimeter = 126\nsmall perimeter = 126\nComputing the perimeter...\nlarge perimeter = 153\nComputing the perimeter...\nsmall perimeter = 126\n",
"name": "stdout"
}
]
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Problem: the small perimeter is computed again. It should not be!\n\nExplanation: there is only one cache for the method `perimeter`, i.e. only one cache for the whole class `EquilateralTriangle`. That is not what we want: we need a cache for each triangle object!"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "# Back to Business: Using Cached Properties in our Architecture"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## Use a Cached Property to Delay Computation"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.496965Z",
"end_time": "2019-03-04T16:04:32.509929Z"
}
},
"cell_type": "code",
"source": "class FindPoint(DeleteCacheMixin):\n \"\"\"\n An algorithm to find a \"special point\" of a function.\n The __init__ of this parent class must always be called at the end of a subclass' __init__.\n \"\"\"\n def __init__(self, f=None):\n self.f_ = None\n if f is not None:\n self(f)\n \n def __call__(self, f): # Now, this method only loads f and empties the cache.\n \"\"\"\n :param f: the function.\n :return: itself.\n \"\"\"\n self.f_ = f\n self.delete_cache()\n return self\n \n @cached_property # We rewritten z_ as a cached property.\n def z_(self):\n \"\"\"\n :return: the \"special point\" of the function.\n \"\"\"\n raise NotImplementedError\n \n @cached_property # Another example of cached property.\n def z_square_(self):\n \"\"\"\n :return: the square of the \"special point\".\n \"\"\"\n return self.z_**2 \n \n def plot(self):\n \"\"\"\n Illustrate the method.\n This method must be used after :meth:`__call__`.\n \"\"\"\n x = np.arange(0.0, 1.0, .01)\n plt.plot(x, self.f_(x), label='y = f(x)')\n plt.plot([0, 1], [0, 0], label='y = 0')\n plt.legend()\n plt.text(self.z_, -.1, 'z')",
"execution_count": 90,
"outputs": []
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Example of subclass:"
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.510926Z",
"end_time": "2019-03-04T16:04:32.522924Z"
}
},
"cell_type": "code",
"source": "class FindZeroAffine(FindPoint):\n \"\"\"\n An algorithm to find the zero of a non-constant affine function R -> R.\n \"\"\"\n @cached_property # Rewritten as a cached property\n def z_(self):\n \"\"\"\n :return: the zero of the function.\n \"\"\"\n return - self.f_(0) / (self.f_(1) - self.f_(0))",
"execution_count": 91,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.523892Z",
"end_time": "2019-03-04T16:04:32.537855Z"
}
},
"cell_type": "code",
"source": "FindZeroAffine(f=some_affine_function).z_square_",
"execution_count": 92,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 92,
"data": {
"text/plain": "0.0625"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## REFERENCE: Our Final Architecture"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.538852Z",
"end_time": "2019-03-04T16:04:32.550821Z"
}
},
"cell_type": "code",
"source": "def _cache(f):\n \"\"\"\n Auxiliary decorator used by ``cached_property``.\n\n :param f: a method with no argument (except ``self``).\n :return: the same function, but with a `caching' behavior.\n \"\"\"\n name = f.__name__\n\n # noinspection PyProtectedMember\n def _f(*args):\n try:\n return args[0]._cached_properties[name]\n except KeyError:\n # Not stored in cache\n value = f(*args)\n args[0]._cached_properties[name] = value\n return value\n except AttributeError:\n # cache does not even exist\n value = f(*args)\n args[0]._cached_properties = {name: value}\n return value\n _f.__doc__ = f.__doc__\n return _f\n\n\ndef cached_property(f):\n \"\"\"\n Decorator used in replacement of @property to put the value in cache automatically.\n\n The first time the attribute is used, it is computed on-demand and put in cache. Later accesses to the\n attributes will use the cached value.\n\n Cf. :class:`DeleteCacheMixin` for an example.\n \"\"\"\n return property(_cache(f))",
"execution_count": 93,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.551818Z",
"end_time": "2019-03-04T16:04:32.564783Z"
}
},
"cell_type": "code",
"source": "class DeleteCacheMixin:\n \"\"\"\n Mixin used to delete cached properties.\n\n Cf. decorator :meth:`cached_property`.\n\n >>> class Example(DeleteCacheMixin):\n ... @cached_property\n ... def x(self):\n ... print('Big computation...')\n ... return 6 * 7\n >>> a = Example()\n >>> a.x\n Big computation...\n 42\n >>> a.x\n 42\n >>> a.delete_cache()\n >>> a.x\n Big computation...\n 42\n \"\"\"\n\n def delete_cache(self) -> None:\n self._cached_properties = dict()",
"execution_count": 94,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.565778Z",
"end_time": "2019-03-04T16:04:32.577748Z"
}
},
"cell_type": "code",
"source": "class FindPoint(DeleteCacheMixin):\n \"\"\"\n An algorithm to find a \"special point\" of a function.\n The __init__ of this parent class must always be called at the end of a subclass' __init__.\n \"\"\"\n def __init__(self, f=None):\n self.f_ = None\n if f is not None:\n self(f)\n \n def __call__(self, f):\n \"\"\"\n :param f: the function.\n :return: itself.\n \"\"\"\n self.f_ = f\n self.delete_cache()\n return self\n \n @cached_property\n def z_(self):\n \"\"\"\n :return: the \"special point\" of the function.\n \"\"\"\n raise NotImplementedError\n \n @cached_property\n def z_square_(self):\n \"\"\"\n :return: the square of the \"special point\".\n \"\"\"\n return self.z_**2\n \n def plot(self):\n \"\"\"\n Illustrate the method.\n This method must be used after :meth:`__call__`.\n \"\"\"\n x = np.arange(0.0, 1.0, .01)\n plt.plot(x, self.f_(x), label='y = f(x)')\n plt.plot([0, 1], [0, 0], label='y = 0')\n plt.legend()\n plt.text(self.z_, -.1, 'z')",
"execution_count": 95,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.578746Z",
"end_time": "2019-03-04T16:04:32.591712Z"
}
},
"cell_type": "code",
"source": "class FindZeroAffine(FindPoint):\n \"\"\"\n An algorithm to find the zero of a non-constant affine function R -> R.\n \"\"\"\n @cached_property\n def z_(self):\n \"\"\"\n :return: the zero of the function.\n \"\"\"\n return - self.f_(0) / (self.f_(1) - self.f_(0))",
"execution_count": 96,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "Remark: for `FindZeroDichotomy` and `FindArgminGolden`, there is a small subtlety because evaluating `number_iterations_` is intertwined with computing `z_`."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.592709Z",
"end_time": "2019-03-04T16:04:32.605673Z"
}
},
"cell_type": "code",
"source": "class FindZeroDichotomy(FindPoint):\n \"\"\"\n An algorithm to find the zero of an increasing function [0, 1] -> R by dichotomy.\n :param epsilon: the precision desired.\n \"\"\"\n def __init__(self, f=None, epsilon=1e-6):\n self.epsilon = epsilon\n self._number_iterations = None\n super().__init__(f=f)\n\n @cached_property\n def z_(self):\n \"\"\"\n :return: the zero of the function.\n \"\"\"\n print(\"Computing z...\")\n x, y, z = 0, 1, .5\n self._number_iterations = 0\n while y - x > self.epsilon:\n self._number_iterations += 1\n z = (x + y) / 2\n x, y = (z, y) if self.f_(z) < 0 else (x, z)\n return z\n \n @property\n def number_iterations_(self):\n \"\"\"\n return: the number of iterations performed.\n \"\"\"\n _ = self.z_\n return self._number_iterations",
"execution_count": 97,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.606670Z",
"end_time": "2019-03-04T16:04:32.619675Z"
}
},
"cell_type": "code",
"source": "class FindArgminGolden(FindPoint):\n \"\"\"\n An algorithm to find the argmin of a stricly convex function [0, 1] -> R by a golden-section search.\n :param epsilon: the precision desired.\n \"\"\"\n def __init__(self, f=None, epsilon=1e-6):\n self.epsilon = epsilon\n self._number_iterations = None\n super().__init__(f=f)\n \n @cached_property\n def z_(self):\n \"\"\"\n :return: the argmin of the function.\n \"\"\"\n print(\"Computing z...\")\n x, y, z = 0, 1, .5\n self._number_iterations = 0\n while y - x > self.epsilon:\n self._number_iterations += 1\n d = (math.sqrt(5) - 1) * (y - x) / 2\n a, b = y - d, x + d\n x, y, z = (x, b, a) if self.f_(b) > self.f_(a) else (a, y, b)\n return z\n \n @property\n def number_iterations_(self):\n \"\"\"\n return: the number of iterations performed.\n \"\"\"\n _ = self.z_\n return self._number_iterations",
"execution_count": 98,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.620632Z",
"end_time": "2019-03-04T16:04:32.633636Z"
}
},
"cell_type": "code",
"source": "class BigAlgo(DeleteCacheMixin):\n \"\"\"\n An algorithm to find a \"special point\" of a function, then add a number.\n :param find_point: a :class:`FindPoint` algorithm.\n :attr translated_point_: the \"special point\", plus translation.\n \"\"\"\n def __init__(self, f=None, translation=None, find_point=None):\n self.find_point = find_point\n if f is not None:\n self(f=f, translation=translation)\n\n def __call__(self, f, translation):\n \"\"\"\n :param f: the function.\n :param translation: the number to be added.\n :return: itself.\n \"\"\"\n self.f_ = f\n self.translation = translation\n self.delete_cache()\n return self\n\n @cached_property\n def translated_point_(self):\n return self.find_point(self.f_).z_ + self.translation",
"execution_count": 99,
"outputs": []
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "A few sanity checks:"
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.635593Z",
"end_time": "2019-03-04T16:04:32.648591Z"
}
},
"cell_type": "code",
"source": "FindZeroDichotomy(f=some_increasing_function, epsilon=1e-6).z_",
"execution_count": 100,
"outputs": [
{
"output_type": "stream",
"text": "Computing z...\n",
"name": "stdout"
},
{
"output_type": "execute_result",
"execution_count": 100,
"data": {
"text/plain": "0.7071065902709961"
},
"metadata": {}
}
]
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.649554Z",
"end_time": "2019-03-04T16:04:32.663551Z"
}
},
"cell_type": "code",
"source": "BigAlgo(f=some_increasing_function, translation=42, find_point=FindZeroDichotomy(epsilon=1e-6)).translated_point_",
"execution_count": 101,
"outputs": [
{
"output_type": "stream",
"text": "Computing z...\n",
"name": "stdout"
},
{
"output_type": "execute_result",
"execution_count": 101,
"data": {
"text/plain": "42.707106590270996"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "# Conclusion"
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## A (Simplified) Real Example"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Plurality voting: each voter casts a ballot for one candidate, and the candidate with most votes wins.\n\nOur goal is to have something like:\n\n >>> plurality = Plurality(['a', 'b', 'b', 'b', 'c', 'c'])\n >>> plurality.scores_\n {'a': 1, 'b': 3, 'c': 2}\n >>> plurality.winner_\n 'b'\n >>> plurality.strict_order_\n ['b', 'c', 'a']\n \nFor the \"real\" example, cf. https://github.com/francois-durand/whalrus."
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
},
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.664514Z",
"end_time": "2019-03-04T16:04:32.676495Z"
}
},
"cell_type": "code",
"source": "class Plurality(DeleteCacheMixin):\n def __init__(self, ballots=None, tie_break_reverse=False):\n self.tie_break_reverse = tie_break_reverse\n if ballots is not None:\n self(ballots)\n \n def __call__(self, ballots):\n self.delete_cache()\n self.ballots_ = ballots\n return self\n \n @cached_property\n def scores_(self):\n return dict(collections.Counter(self.ballots_))\n\n @cached_property\n def best_score_(self):\n return max(self.scores_.values())\n \n @cached_property\n def cowinners_(self):\n return {k for k, v in self.scores_.items() if v == self.best_score_}\n \n @cached_property\n def winner_(self):\n return sorted(self.cowinners_, reverse=self.tie_break_reverse)[0]\n \n @cached_property\n def order_(self):\n return [{k for k in self.scores_.keys() if self.scores_[k] == v} for v in sorted(set(self.scores_.values()), reverse=True)]\n\n @cached_property\n def strict_order_(self):\n return [candidate for tie_class in self.order_ for candidate in sorted(tie_class, reverse=self.tie_break_reverse)]",
"execution_count": 102,
"outputs": []
},
{
"metadata": {
"trusted": true,
"ExecuteTime": {
"start_time": "2019-03-04T16:04:32.677481Z",
"end_time": "2019-03-04T16:04:32.691444Z"
}
},
"cell_type": "code",
"source": "Plurality(['a', 'b', 'b', 'b', 'c', 'c']).winner_",
"execution_count": 103,
"outputs": [
{
"output_type": "execute_result",
"execution_count": 103,
"data": {
"text/plain": "'b'"
},
"metadata": {}
}
]
},
{
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"cell_type": "markdown",
"source": "Dependencies:\n\n scores_ => best_score_ => cowinners_ => winner_\n => order_ => strict_order_\n \nHence, for example: when we access `winner_`, then `order_` and `strict_order_` do not need to be computed."
},
{
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"cell_type": "markdown",
"source": "## That's All Folks !"
},
{
"metadata": {},
"cell_type": "markdown",
"source": "Thanks for your attention!\n\nQuestions?"
},
{
"metadata": {
"trusted": true
},
"cell_type": "code",
"source": "",
"execution_count": null,
"outputs": []
}
],
"metadata": {
"_draft": {
"nbviewer_url": "https://gist.github.com/08590af1228ed5c62adb02cb9ef4b9f4"
},
"celltoolbar": "Slideshow",
"gist": {
"id": "08590af1228ed5c62adb02cb9ef4b9f4",
"data": {
"description": "Some Architectural Considerations for Algorithms in Python",
"public": true
}
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3",
"language": "python"
},
"language_info": {
"name": "python",
"version": "3.6.5",
"mimetype": "text/x-python",
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"pygments_lexer": "ipython3",
"nbconvert_exporter": "python",
"file_extension": ".py"
},
"toc": {
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": false,
"base_numbering": 1,
"title_cell": "Table of Contents",
"title_sidebar": "Contents",
"toc_cell": true,
"toc_position": {
"height": "calc(100% - 180px)",
"left": "10px",
"top": "150px",
"width": "265.6px"
},
"toc_section_display": true,
"toc_window_display": true
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment