<div dir="ltr"><div>Hola!</div><div><br></div><div>Respondo que las tertulias nunca me vienen bien de horario y quería participar de alguna forma, así que allá que voy!</div><div><br></div><div>El artículo es interesante (nunca había visto usar closures así) pero también me ha decepcionado un poco. <br></div><div><br></div><div>Según entiendo, se trata de una forma de implementar una solución iterativa equivalente a previas soluciones recursivas, pero creo que usar closures en este contexto es intentar meterlas con calzador en la discusión "recursivo vs iterativo"... ¿Qué tienen de malo los bucles o los generadores?<br></div><div><br></div><div>Usando closures:</div><div><br></div><div><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">def fib_c():<br> a, b = 0, 1<br> def get_next_number():<br> nonlocal a, b<br> a, b = b, a + b<br> return a<br> return get_next_number<br><br></span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">def fib_closure(n):<br> fib = fib_c()<br> for _ in range(n): <br> num = fib()<br> return num</span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe"><br>>>> timeit.timeit(lambda: fib_closure(1000), number=10000) # Implementación sacada del artículo<br>1.6638641370000187<br><br></span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe"><span style="font-family:arial,sans-serif">Usando generadores:</span><br><br>def fib_l(n):<br> a, b = 0, 1<br> for _ in range(n):<br> a, b = b, a + b<br></span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe"> return a</span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">>>> timeit.timeit(lambda: fib_loop(1000), number=10000)<br>0.7578596280000056</span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe"><br></span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span style="font-family:arial,sans-serif"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">Mis observaciones:<br></span></span></pre><ul><li><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span style="font-family:arial,sans-serif"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">En la solución closure hemos definido 3 funciones distintas y ninguna de ellas tiene un propósito sencillo de explicar. De hecho, fib_c no puede explicarse sin explicar antes get_next_number.<br></span></span></pre></li><li><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span style="font-family:arial,sans-serif"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">La solución con bucles es limpia, sencilla de entender (no necesitas conocimientos de variable scoping ni de closures), pura<br></span></span></pre></li><li><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span style="font-family:arial,sans-serif"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">Ambas son equivalentes, sólo que en la de closures se acceden a variables nonlocal en vez de local como en los bucles. ¿Qué ventajas ofrece usar nonlocal frente a local?<br></span></span></pre></li><li><span style="font-family:arial,sans-serif"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">Usar bucles gana en rendimiento. ¿Será la falta de overhead de invocar a la función get_next_number() constantemente? ¿Variable scoping?<br></span></span></li></ul><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span style="font-family:arial,sans-serif"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe"><br></span></span></pre>De vuelta al artículo, he echado de menos una mayor investigación sobre la recursividad, pego unos links acerca de artículos que creo que pueden ser de interés:</div><div><ul><li><a href="https://htdp.org/2020-8-1/Book/index.html">How to design programs</a>: Libro un pelín largo pero se obtiene la idea de que es la estructura de datos sobre la que trabajamos la que sugiere un approach recursivo.</li><li><a href="https://cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/paper.pdf">Automata via Macros</a>: Paper que toca conceptos de recursividad, así como un buen caso de uso donde la implementación recursiva brilla. Además, se tocan conceptos como TCO.<br></li><li><a href="https://towardsdatascience.com/python-stack-frames-and-tail-call-optimization-4d0ea55b0542">Python Stack Frames and Tail Call Optimization</a>: Post muuuuy completo sobre stack frames, el por qué hacer recursividad causa overflow y métodos (TCO) para solventarlo.<br></li><li><a href="http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html">Tail Recursion Elimination</a>: Post de Guido sobre por qué Python no tiene TCO (ahí lo llama Tail Recursion Elimination pero salvo tecnicismos creo que el "sentimiento" se comparte)</li><li><a href="http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html">Final Words on Tail Calls</a>: Otro post de Guido como seguimiento al anterior post.<br></li></ul></div><div><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span style="font-family:arial,sans-serif"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe"><br></span></span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span style="font-family:arial,sans-serif"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">Ya como bonus y como disculpas por el tochazo, dejo esta <a href="https://addons.mozilla.org/es/firefox/addon/medium-unlimited-read-for-free/">extensión de Firefox</a> que desbloquea el paywall de algunos sitios incluyendo medium y sucedáneos. <br><br></span></span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span style="font-family:arial,sans-serif"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">Un saludo y pasad buena tarde,<br><br></span></span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span style="font-family:arial,sans-serif"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe">Javi Luna <br></span></span></pre><pre class="gmail-nr gmail-ns gmail-nt gmail-nu gmail-nv gmail-nx gmail-ny gmail-nz"><span id="gmail-8dac" class="gmail-ji gmail-oa gmail-mw gmail-il gmail-ob gmail-b gmail-dk gmail-oc gmail-od gmail-s gmail-oe"><br></span></pre></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">El sáb, 2 ene 2021 a las 16:55, Jesus Cea (<<a href="mailto:jcea@jcea.es" target="_blank">jcea@jcea.es</a>>) escribió:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">El artículo requiere autenticarse para leerlo, así que voy a ser pirata <br>
y enviar una transcripción. La técnica me parece muy interesante. <br>
Podemos comentarla en la tertulia del martes próximo.<br>
<br>
<<a href="https://towardsdatascience.com/dont-use-recursion-in-python-any-more-918aad95094c" rel="noreferrer" target="_blank">https://towardsdatascience.com/dont-use-recursion-in-python-any-more-918aad95094c</a>><br>
<br>
Transcripción si no quieres autenticarte. Las imágenes se pierden, pero <br>
espero que se entienda el sentido general:<br>
<br>
"""<br>
Don’t Use Recursion In Python Any More<br>
Python Closure — A Pythonic technique you must know<br>
Christopher Tao<br>
Christopher Tao<br>
Nov 22, 2020·8 min read<br>
<br>
I was such a programmer who likes recursive functions very much before, <br>
simply because it is very cool and can be used to show off my <br>
programming skills and intelligence. However, in most of the <br>
circumstances, recursive functions have very high complexity that we <br>
should avoid using.<br>
<br>
One of the much better solutions is to use Dynamic Planning when <br>
possible, which is probably the best way to solve a problem that can be <br>
divided into sub-problems. One of my previous articles has illustrated <br>
the power of Dynamic Planning.<br>
Using Dynamic Planning to Help Trump Win the Elections<br>
Dynamic Planning in Python for optimising Election Promotion<br>
<a href="http://towardsdatascience.com" rel="noreferrer" target="_blank">towardsdatascience.com</a><br>
<br>
However, in this article, I’m going to introduce another technique in <br>
Python that can be utilised as an alternative to the recursive function. <br>
It won’t outperform Dynamic Planning, but much easier in term of <br>
thinking. In other words, we may sometimes be struggling to make Dynamic <br>
Planning works because of the abstraction of the ideas, but it will be <br>
much easier to use closure.<br>
What is Python Closure?<br>
Image for post<br>
Image for post<br>
Photo by Free-Photos on Pixabay<br>
<br>
First of all, let me use a simple example to demonstrate what is a <br>
closure in Python. Look at the function below:<br>
<br>
def outer():<br>
x = 1<br>
def inner():<br>
print(f'x in outer function: {x}')<br>
return inner<br>
<br>
The function outer is defined with another function inner inside itself, <br>
and the function outer returns the function inner as the “return value” <br>
of the function.<br>
<br>
In this case, the nested function is called a closure in Python. If we <br>
check the “return value” of the outer function, we will find that the <br>
returned value is a function.<br>
Image for post<br>
Image for post<br>
<br>
What does closure do? Because it returned a function, we can run this <br>
function, of course.<br>
Image for post<br>
Image for post<br>
<br>
OK, we can see that the inner function can access variables defined in <br>
the outer function. Usually, we don’t use closure in such a way shown as <br>
above, because it is kind of ugly. We usually want to define another <br>
function to hold the function returned by the closure.<br>
Image for post<br>
Image for post<br>
<br>
Therefore, we can also say that in a Python closure, we defined a <br>
function that defines functions.<br>
Access Outer Variables from the Inner Function<br>
Image for post<br>
Image for post<br>
Photo by igorovsyannykov on Pixabay<br>
<br>
How can we use a closure to replace a recursive then? Don’t be too <br>
hurry. Let’s have a look at another problem here, which is accessing <br>
outer variables from the inner function.<br>
<br>
def outer():<br>
x = 1<br>
def inner():<br>
print(f'x in outer function (before modifying): {x}')<br>
x += 1<br>
print(f'x in outer function (after modifying): {x}')<br>
return inner<br>
<br>
In the closure above-shown, we want to add 1 to the outer variable x in <br>
the inner function. However, this won’t work straightforward.<br>
Image for post<br>
Image for post<br>
<br>
By default, you won’t be able to access the outer variable from the <br>
inner function. However, just like how we define a global variable in <br>
Python, we can tell the inner function of a closure that the variable <br>
should not be considered as a “local variable”, by using the nonlocal <br>
keyword.<br>
<br>
def outer():<br>
x = 1<br>
def inner():<br>
nonlocal x<br>
print(f'x in outer function (before modifying): {x}')<br>
x += 1<br>
print(f'x in outer function (after modifying): {x}')<br>
return inner<br>
<br>
Now, let’s say we want to add the variable x by 1 for five times. We can <br>
simply write a for loop to achieve this.<br>
<br>
f = outer()for i in range(5):<br>
print(f'Run {i+1}')<br>
f()<br>
print('\n')<br>
<br>
Image for post<br>
Image for post<br>
Write a Fibonacci Function Using Closure<br>
Image for post<br>
Image for post<br>
Photo by Free-Photos on Pixabay<br>
<br>
Fibonacci is commonly used as a “hello world” example of recursive <br>
functions. If you don’t remember it, don’t worry, it is pretty simple to <br>
be explained.<br>
<br>
A Fibonacci sequence is a series of numbers that every number is the sum <br>
of the two numbers before it. The first two numbers, X₀ and X₁, are <br>
special. They are 0 and 1 respectively. Since X₂, the patter is as <br>
above-mentioned, it is the sum of X₀ and X₁, so X₂=1. Then, X₃ is X₁ + <br>
X₂ =2, X₄ is X₂ + X₃=3, X₅ is X₃ + X₄ = 5, and so on.<br>
<br>
The recursive function requires us to think reversely from the “current <br>
scenario” to the “previous scenario”, and eventually what are the <br>
terminate conditions. However, by using the closure, we can think about <br>
the problem more naturally.<br>
<br>
See the code below that the Fibonacci function is implemented using a <br>
closure.<br>
<br>
def fib():<br>
x1 = 0<br>
x2 = 1<br>
def get_next_number():<br>
nonlocal x1, x2<br>
x3 = x1 + x2<br>
x1, x2 = x2, x3<br>
return x3<br>
return get_next_number<br>
<br>
We know that the Fibonacci starts with two special number X₀=0 and X₁=1, <br>
so we just simply define them in the outer function. Then, the inner <br>
function get_next_number is simply return the sum of the two numbers it <br>
got from the outer function.<br>
<br>
Additionally, don’t forget to update X₀ and X₁ with X₁ and X₂. In fact, <br>
we can simplify the code:<br>
<br>
...<br>
x3 = x1 + x2<br>
x1, x2 = x2, x3<br>
return x3<br>
<br>
to<br>
<br>
x0, x1 = x1, x0 + x1<br>
return x1<br>
<br>
This is updating the two variables first and then return the second, <br>
which is equivalent to the previous code snippet.<br>
<br>
Then, we can use this closure to calculate Fibonacci numbers. For <br>
example, we want to show the Fibonacci sequence up to the 20th number.<br>
<br>
fibonacci = fib()for i in range(2, 21):<br>
num = fibonacci()<br>
print(f'The {i}th Fibonacci number is {num}')<br>
<br>
Image for post<br>
Image for post<br>
Compare the Performance<br>
Image for post<br>
Image for post<br>
Photo by KahlOrr on Pixabay<br>
<br>
Alright, we knew that we can use closure to replace a recursive function <br>
in the previous section. How about the performance? Let’s compare them!<br>
<br>
Firstly, let’s implement the Fibonacci function using a recursive function.<br>
<br>
def fib_recursion(n):<br>
if n == 0:<br>
return 0<br>
elif n == 1:<br>
return 1<br>
else:<br>
return fib_recursion(n-1) + fib_recursion(n-2)<br>
<br>
We can verify the function by output the 20th number of the Fibonacci <br>
sequence.<br>
Image for post<br>
Image for post<br>
<br>
Then, let’s embed the closure version in a function for comparing purposes.<br>
<br>
def fib_closure(n):<br>
f = fib()<br>
for i in range(2, n+1):<br>
num = f()<br>
return num<br>
<br>
Image for post<br>
Image for post<br>
<br>
Now, let’s compare the speed.<br>
Image for post<br>
Image for post<br>
<br>
2.79ms v.s. 2.75µs. The closure method is 1000x faster than the <br>
recursive! The most intuitive reason is that all the temporary values <br>
for every level of recursion are stored in the memory separately, but <br>
the closure is actually updating the same variables in every loop.<br>
<br>
Also, there is a depth limitation for recursion. For the closure, <br>
because it is basically a for loop, there will not be any constraints.<br>
<br>
Here is an example of getting the 1000th Fibonacci number<br>
Image for post<br>
Image for post<br>
<br>
That’s indeed a huge number, but the closure method can finish the <br>
calculation in about 100 µs, while the recursive function met its <br>
limitation.<br>
Other Use Cases of Closure<br>
Image for post<br>
Image for post<br>
Photo by HarinathR on Pixabay<br>
<br>
Python closures are very useful not only for replacing the recursive <br>
functions. In some cases, it can also replace Python classes with a <br>
neater solution, especially there are not too many attributes and <br>
methods in a class.<br>
<br>
Suppose we have a dictionary of students with their exam marks.<br>
<br>
students = {<br>
'Alice': 98,<br>
'Bob': 67,<br>
'Chris': 85,<br>
'David': 75,<br>
'Ella': 54,<br>
'Fiona': 35,<br>
'Grace': 69<br>
}<br>
<br>
We want to have several functions that help us to filter the students by <br>
marks, to put them into different grade classes. However, the criteria <br>
might change over time. In this case, we can define a Python closure as <br>
follows:<br>
<br>
def make_student_classifier(lower_bound, upper_bound):<br>
def classify_student(exam_dict):<br>
return {k:v for (k,v) in exam_dict.items() if lower_bound <= v <br>
< upper_bound}<br>
return classify_student<br>
<br>
The closure defines a function that defines other functions based on the <br>
parameters passed in dynamically. We will pass the lower bound and upper <br>
bound of the grade class, and the closure will return us a function does <br>
that.<br>
<br>
grade_A = make_student_classifier(80, 100)<br>
grade_B = make_student_classifier(70, 80)<br>
grade_C = make_student_classifier(50, 70)<br>
grade_D = make_student_classifier(0, 50)<br>
<br>
The above code will give us 4 functions that will classify the student <br>
to the corresponding grade classes based on the boundaries we gave. <br>
Please be noted that we can change the boundary any time to make another <br>
function or overwrite current grade functions.<br>
<br>
Let’s verify the functions now.<br>
Image for post<br>
Image for post<br>
<br>
Very neat! Just bear in mind that we still need to define classes when <br>
the case is more complex.<br>
Summary<br>
Image for post<br>
Image for post<br>
Photo by Free-Photos on Pixabay<br>
<br>
In this article, I have introduced a technique called closure in Python. <br>
It can be utilised to rewrite recursive functions in most of the <br>
circumstances and outperform the latter to a huge extent.<br>
<br>
Indeed, closure might not be the best solution for some problems from <br>
the performance perspective, especially when Dynamic Planning is <br>
applicable. However, it is much easier to come up with. Sometimes <br>
Dynamic Planning is a bit overkill when we are not very sensitive to the <br>
performance, but closure might be good enough.<br>
<br>
Closure can also be used to replace some use cases that we may want to <br>
define a class to satisfy. It is much neater and elegant in those cases.<br>
"""<br>
<br>
-- <br>
Jesús Cea Avión _/_/ _/_/_/ _/_/_/<br>
<a href="mailto:jcea@jcea.es" target="_blank">jcea@jcea.es</a> - <a href="https://www.jcea.es/" rel="noreferrer" target="_blank">https://www.jcea.es/</a> _/_/ _/_/ _/_/ _/_/ _/_/<br>
Twitter: @jcea _/_/ _/_/ _/_/_/_/_/<br>
jabber / <a href="mailto:xmpp%3Ajcea@jabber.org" target="_blank">xmpp:jcea@jabber.org</a> _/_/ _/_/ _/_/ _/_/ _/_/<br>
"Things are not so easy" _/_/ _/_/ _/_/ _/_/ _/_/ _/_/<br>
"My name is Dump, Core Dump" _/_/_/ _/_/_/ _/_/ _/_/<br>
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz<br>
<br>
_______________________________________________<br>
Asociación Python España: <a href="http://www.es.python.org/" rel="noreferrer" target="_blank">http://www.es.python.org/</a><br>
Python Madrid: <a href="http://www.python-madrid.es/" rel="noreferrer" target="_blank">http://www.python-madrid.es/</a><br>
Madrid mailing list<br>
<a href="mailto:Madrid@lists.es.python.org" target="_blank">Madrid@lists.es.python.org</a><br>
<a href="https://lists.es.python.org/listinfo/madrid" rel="noreferrer" target="_blank">https://lists.es.python.org/listinfo/madrid</a><br>
</blockquote></div><br clear="all"><br>-- <br><div dir="ltr"><div dir="ltr"><div>
<p>["hip","hip"]</p>
<p>(hip hip array!)</p>
</div></div></div>