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