zijn python lambda's anders geïmplementeerd dan standaardfuncties?

Terwijl ik probeerde een antwoord te schrijven voor een andere ZO-vraag, gebeurde er iets heel eigenaardigs.

I basically came up with a one liner gcd and said it maybe slower because of recursion
gcd = lambda a,b : a if not b else gcd(b, a % b)

hier is een eenvoudige test:

assert gcd(10, 3) == 1 and gcd(21, 7) == 7 and gcd(100, 1000) == 100

hier zijn enkele benchmarks:

timeit.Timer('gcd(2**2048, 2**2048+123)', setup = 'from fractions import gcd').repeat(3, 100)
# [0.0022919178009033203, 0.0016410350799560547, 0.0016489028930664062]
timeit.Timer('gcd(2**2048, 2**2048+123)', setup = 'gcd = lambda a,b : a if not b else gcd(b, a % b)').repeat(3, 100)
# [0.0020480155944824219, 0.0016460418701171875, 0.0014090538024902344]

Nou dat is interessant, ik had verwacht dat het veel langzamer zou zijn, maar de timing is redelijk dichtbij,? misschien is het importeren van de module het probleem ...

>>> setup = '''
... def gcd(a, b):
...     """Calculate the Greatest Common Divisor of a and b.
... 
...     Unless b==0, the result will have the same sign as b (so that when
...     b is divided by it, the result comes out positive).
...     """
...     while b:
...         a, b = b, a%b
...     return a
... '''
>>> timeit.Timer('gcd(2**2048, 2**2048+123)', setup = setup).repeat(3, 100)
[0.0015637874603271484, 0.0014810562133789062, 0.0014750957489013672]

nee, nog steeds redelijk dichtbij timings ok laat grotere waarden proberen.

timeit.Timer('gcd(2**9048, 2**248212)', setup = 'gcd = lambda a,b : a if not b else gcd(b, a % b)').repeat(3, 100) [2.866894006729126, 2.8396279811859131, 2.8353509902954102]
[2.866894006729126, 2.8396279811859131, 2.8353509902954102]
timeit.Timer('gcd(2**9048, 2**248212)', setup = setup).repeat(3, 100)
[2.8533108234405518, 2.8411397933959961, 2.8430981636047363]

interessant Ik vraag me af wat er aan de hand is?
Ik veronderstelde altijd dat recursie langzamer was vanwege de overhead van het aanroepen van een functie, zijn lambda's de uitzondering? en waarom heb ik mijn recursielimiet niet bereikt?
Als het wordt geïmplementeerd met def , raak ik het meteen aan. Als ik de recursiediepte verhoog naar iets als 10 ** 9 krijg ik een segmentatiefout waarschijnlijk een stapeloverloop ...

Bijwerken 

>>> setup = '''
... import sys
... sys.setrecursionlimit(10**6)
... 
... def gcd(a, b):
...     return a if not b else gcd(b, a % b)
... '''
>>> 
>>> timeit.Timer('gcd(2**9048, 2**248212)', setup = 'gcd = lambda a,b:a if not b else gcd(b, a%b)').repeat(3, 100)
[3.0647969245910645, 3.0081429481506348, 2.9654929637908936]
>>> timeit.Timer('gcd(2**9048, 2**248212)', setup = 'from fractions import gcd').repeat(3,   100)
[3.0753359794616699, 2.97499680519104, 3.0096950531005859]
>>> timeit.Timer('gcd(2**9048, 2**248212)', setup = setup).repeat(3, 100)
[3.0334799289703369, 2.9955930709838867, 2.9726388454437256]
>>>

nog meer puzzelen ...

 7
toegevoegd bewerkt
Bekeken: 1
de bron
ja ru fr es de
@FelixBonkoski, Python optimaliseert de staartrecursie niet. Deze code heeft gewoon een beetje stackgebruik :)
toegevoegd de auteur astynax, de bron
@kosii: Schrijf een fibonacci -functie en gebruik vervolgens fibonacci (1200) en fibonacci (1201) . Opeenvolgende Fibonacci-getallen zijn het slechtste geval voor het algoritme van Euclides.
toegevoegd de auteur Mark Dickinson, de bron
@FelixBonkoski: Yep; er is geen tail recursion-optimalisatie in de huidige Python.
toegevoegd de auteur Mark Dickinson, de bron
@MarkDickinson uit nieuwsgierigheid, zullen we het ooit zien?
toegevoegd de auteur Samy Vilar, de bron
@FelixBonkoski Ik denk dat ik beter kan beginnen met de paar eerste paar zinnen, het maakte me wel duidelijk :( bedankt.
toegevoegd de auteur Samy Vilar, de bron
@FelixBonkoski nope timeit heeft geen toegang tot de globale scope :) daarom hebben we setup = Timer was specifiek ontworpen met dergelijke gevallen in gedachten, als je geen setup hebt zal het niet kijken in de wereldwijde scope zelfs als je het daar hebt gedefinieerd.
toegevoegd de auteur Samy Vilar, de bron
@FelixBonkoski kon het niet doen Ik krijg een stapel overloop;) bij het gebruik van grotere waarden ... Ik zou kunnen proberen kleinere waarden te gebruiken, maar dat is een rode vlag die langzamer gaat ...
toegevoegd de auteur Samy Vilar, de bron
recursieve staartaanroepen ja dat is wat ik ook denk, nog steeds kunnen we het altijd toepassen, betekent niet dat recursie iets beter is met lambda dan standaard def het is echt raadselachtig speciaal wanneer je overweeg het geeft prioriteit aan leesbaarheid ten opzichte van snelheid of expressiviteit overgenomen van en.wikipedia.org/wiki/Portal: Python_programming
toegevoegd de auteur Samy Vilar, de bron
@ samy.vilar zullen we het ooit zien? zoals ik eerder heb gelinkt, Guido van Rossum zegt dat TRE "unpythisch" zou zijn
toegevoegd de auteur Felix, de bron
Ik denk dat het zeer waarschijnlijk is dat de Python-interpretator je lambda-expressie optimaliseert tot een loop voor jou (ongeveer zoals een typische Lisp-implementatie recursieve staartoproepen zal optimaliseren). Dit zou echter een implementatiedetail van CPython zijn, wat niet noodzakelijk geldt voor alle Python-tolken.
toegevoegd de auteur Felix, de bron
@MarkDickinson en met die Fib-nummers als voorbeelden, zelfs met de lambda -vorm van de functie gcd , raakte ik de recursielimiet. Verder ondersteunend @ astynax's eerste opmerking over Python dat Tail-recursie niet is geoptimaliseerd, en er is geen verschil in hoe een lambda versus een def fun() TR zou kunnen behandelen.
toegevoegd de auteur Felix, de bron
@samy Je hebt gelijk. Ik zal gewoon zwijgen totdat iemand meer gekwalificeerd is!
toegevoegd de auteur Felix, de bron
@astyntax lijkt correct te zijn over TRE: Guido zegt dit. Echter, This SO answer lijkt te suggereren dat er enig verschil is hoe de interpreter daadwerkelijk wordt uitgevoerd TR-functies. Iemand die meer gekwalificeerd is dan ik moet deze vraag beantwoorden! :)
toegevoegd de auteur Felix, de bron
@MarkDickinson WOW! Dat wist ik niet. Dank je!
toegevoegd de auteur kosii, de bron
kun je me een paar cijfers geven die groot genoeg zijn om de recursielimiet te bereiken?
toegevoegd de auteur kosii, de bron

2 antwoord

counter = 0

def gcd(a, b):
    global counter
    counter += 1
    return a if not b else gcd(b, a % b)

gcd(2**9048, 2**248212)
print counter

Drukt 3 af. Natuurlijk is er niet veel overhead voor een recursie van diepte 3.

6
toegevoegd
de bron
ja ik ben me daar nu behoorlijk van bewust, ik had Fibonacci-nummers moeten gebruiken om mijn tests uit te voeren, om elke dag iets nieuws te leren ...
toegevoegd de auteur Samy Vilar, de bron

Het type van een lambda is precies hetzelfde als het type van een andere functie en in het geval van beide, als ze zijn gedefinieerd in een ander lokaal bereik, vindt omgevingsinvang plaats.

Het enige verschil is dat functies die zijn gedefinieerd met de lambda-syntaxis niet automatisch de waarde van een variabele worden in de scope waarin deze wordt weergegeven, en dat lambda-syntaxis vereist dat het hoofdgedeelte één (mogelijk samengestelde) expressie is, waarvan de waarde wordt geretourneerd van de functie.

Wat betreft de snelheid van recursie - ja er is een lichte overhead, maar blijkbaar niet zo veel. De gesprekskosten lijken vooral te zijn gemaakt van de kosten van toewijzing van het stapelframe.

1
toegevoegd
de bron
@ samy.vilar Lees mijn commentaar zoals het er staat.
toegevoegd de auteur Marcin, de bron
@ samy.vilar U maakt slechts één nieuwe int per stapelframe, dus geheugengebruik is geen probleem. Er is hier geen mysterie. Wat betreft de recursielimiet, waarom zou je verwachten dat je dit met dit voorbeeld zou halen?
toegevoegd de auteur Marcin, de bron
@Marcin: de impact is in feite erg belangrijk. Het grootste deel van de tijd wordt besteed aan het plaatsen van spullen op de stapel, in plaats daarvan kan het in de registers worden bewaard. In dit specifieke voorbeeld maakt dit het algoritme in het slechtste geval ongeveer 100% langzamer.
toegevoegd de auteur Niklas B., de bron
Ah, ja! Ik heb dat niet gezien. Alleen nu, met je reactie en het antwoord van @ Niklas.
toegevoegd de auteur SuperSaiyan, de bron
Recursie is (aanzienlijk) trager hier . Eventuele verklaringen?
toegevoegd de auteur SuperSaiyan, de bron
@Marcin goed na wat fine-tunen en nog een aantal voorbeelden uitvoeren Ik denk dat je gelijk hebt, nog steeds Im aangenaam verrast, recursie is vrij snel in python, wie wist, dank je.
toegevoegd de auteur Samy Vilar, de bron
@Marcin Ik heb ook de niet-recursiefunctie gedefinieerd met behulp van de gewone python en de timings verschillen nog steeds niet, er gebeurt iets merkwaardigs en waarom heb ik de recursielimiet niet bereikt?
toegevoegd de auteur Samy Vilar, de bron
Heb je zelfs gekeken naar de keren dat hij laat zien? U ziet niet het effect zien dat de bibliotheekfunctie fractions.gcd() sneller is. Hij probeert te laten zien dat het een gooi is, en hij is daardoor verbaasd. -1 voor het niet lezen van de vraag.
toegevoegd de auteur Felix, de bron
@Thrustmaster Ja: de recursiediepte van de originele nummers van de OP (2 9048 en 2 248212) was slechts 2! Met fib (100) en fib (101) is de recursieve diepte 100! Ik kan niet geloven dat ik dit eerder niet heb gemerkt. En ja, recursie is aanzienlijk langzamer!
toegevoegd de auteur Felix, de bron