Vlákno názorů k článku Podpora funkcionálního programování v Pythonu a knihovna functools (3. část) od Calculon - CPython se teda moc nevyznamenal.
-
No... chyba v implementacii...
pre n =40 sa ta fibonacciho funkcia zavola 331160281x
a pritom staci podla definicie (clen vo fibonacciho postupnosti je suctom dvoch predchadzajucich clenov) a napisat:
def fibonacci(n): a=0 b=1 while n>1: (a,b) = (b,a+b) n-=1 return brychlost je potom niekde uplne inde aj bez optimalizacii
-
> To je blábol, Go taky není funkcionální a trvá to v něm půl sekundy, stejně jako v Rustu (jo, není rychlejší), Julii nebo, překvapení, LPythonu.
Blábol je, co píšeš ty:
1. Rekurzivní algoritmy jsou obecně vhodnější pro jazyky, které mají tail call optimalizaci a další techniky, které tomu napomáhají.
2. Nepsal jsem, že volání funkcí v Pythonu je pomalé proto, že není funkcionální, ale uváděl jsem to jako jeden z dalších důvodů, proč podobné věci v Pythonu nedělat. Tohle je známé 20 let a od té doby se to moc nezměnilo. V CPythonu to má zjevně zásadní důvod a je to holt trade-off dané platformy. Hračky typu LPython mají zase jiné nevýhody, třeba že zatím moc nefungují.
3. Pisatel výše ukázal notoricky známý imperativní přístup bez rekurze, který je samozřejmě lepší. Pavel Tišnovský ukázal hezkou optimalizaci pomocí LRU cache. Kdybych náhodou musel něco podobného řešit já, udělám si extenzi v nějakém vhodnějším jazyce, dnes pravděpodobně v Rustu pomocí PyO3. Tohle se v CPythonu dělá tradičně a nikoho to nepřekvapuje a nepadá do mdlob.
Články tohoto typu jsou určeny pro lidi, kteří používají daný jazyk a chtějí se naučit něco užitečného nového. Pak přijde nějaký snobský troll bez základního vychování, honí si ego a stočí debatu dost neproduktivním směrem. Článek je super, ale pojďme ho nedegradovat. Aspoň tím, že se budeme v diskusi chovat slušně a pokud snad máme pocit, že se někdo mýlí, napišme to jako lidi. Třeba zjistíme, že jsme si interpretovali jeho tvrzení jinak, než mělo vyznit.
-
Podívej se, Calculone, já nemám potřebu se přizpůsobovat Tvým výlevům, raději komunikuju s lidmi, kteří mají praktický přístup (a ideálně píší k věci). Tentokrát beru na vědomí, že máš potřebu "zachovat tvář" a nebudu ani psát, co a proč je a není ad hominem. Prostě nechci, aby tady vznikalo toxické nepřátelské prostředí, kde si člověk musí dávat pozor na každé slovo, aby ho někdo za něj nebral. Je zajímavé, že na zahraničních fórech tohle není, nemám takové zkušenosti. Takže teď už si piš v reakci co chceš, posluž si, já jsem svoje napsal. Až podobný exces uděláš příště, mně nebo někomu jinému, čekej podobnou reakci. Pythonu zdar!
-
No je pravda, že v českém prostředí to je dost ostré. Že by tím jazykem ? :D.
Je podle Vás tedy problém v jazyku Python nebo implemetaci (CPython). Často se říká, že jazyk není rychlý/pomalý, ale že to je vše o implementaci. Prakticky mi ale přijde, že jazyk často diktuje implementaci -- jinak si neumím představit, že tolik chytrých hlav co tom pracuje, tohle nepromýšlelo. Ta TCO se nedá třeba implementovat dodatečně? Pokud plácám, tak se omlouvám, ale třeba se něco dozvím. Nejsem Comp. Sci. Eng. ;)
-
Ostré jsou jen reakce na trolly a žvanily ;) Nicméně k věci, je pravda, že žádný jazyk není per se pomalý, ostatně pro Python se rýsuje LPython a Mojo. Blbá je prostě implementace, kvůli tomu vlastně původně vznikla Julia, která je taky dynamicky typovaná a přitom rychlá.
TCO neřeší rychlost ani v nejmenším, řeší přetečení zásobníku při hluboké rekurzi. Čistě funkcionální jazyky na to dost spoléhají, jinak je v podstatě k ničemu (Go ji třeba nemá a ten příklad běžel stejně rychle jako v jazycích, kde je, prostě to nijak nesouvisí).
Na druhou stranu někdy jazyk implementaci “diktuje”, například Smalltalk (a ObjC), ale to jsou spíše výjimky. Spíše než jazyk jako takový si někdy “diktuje” typ typového systému.
-
"TCO neřeší rychlost ani v nejmenším, řeší přetečení zásobníku při hluboké rekurzi." Jo to jsem zamotal k té rychlosti, ale nemělo to tak vyznít. Spíše mne zajímá proč některé jazyky TCO mají implementovanou a jiné ne. Jestli je to nějakým technickým omezením nebo jen prostě tím, že to prostě nikdo neudělal.
15. 8. 2023, 22:03 editováno autorem komentáře
-
Nezamotal ses vůbec, TCO samozřejmě obecně může vést k rychlejšímu výpočtu a ve spoustě případů taky vede. Volání funkce něco stojí a to i v jazycích, které se kompilují do nativního strojového kódu. Skočil jsi na špek. Použij Google a přesvědč se sám, jestli TCO má vliv na rychlost nebo nemá.
Proč tohle některé jazyky řeší a jiné ne, je trochu moc obecná otázka. Proč to není v Pythonu, řešila komunita opakovaně, Guido van Rossum se k tomu několikrát vyjadřoval. Pokud je teda pro Tebe TCO věc, která má řešit jenom "nekonečnou" rekurzi, existují třeba dekorátory, které to řeší. V drtivé většině případů ale hlubokou rekurzi nepotřebuješ, v Pythonu ani nechceš. Mrkni sem: https://stackoverflow.com/questions/13591970/does-python-optimize-tail-recursion nebo Google.
-
Pavel TišnovskýZlatý podporovatelTreba v Clojure TCO neni implementovane podle autora naschval, protoze by to vyzadovalo pouziti trampolin atd. Jako samotna tail rekurze pro jednu funkci neni problem (na to ma Clojure explicitni recur), ale rekurze pres vice funkci uz je horsi.
(tedy osobne si myslim, ze by to vyresilo vygenrovani bajtkodu znovu a bez problemu, ale Rich je guru v teto oblasti, tak asi vi co rika).
* btw ten vypocet fibonacciho stejne neni v tail pozici
-
Mám přehled o JVM a bytecode, méně vím o Clojure, nicméně asi chápu, proč se do TCO nepouštěli.
JVM nenabízí možnost nahradit poslední volání (tzv. frame) na stacku něčím jiným. To znamená, že sice tail recursion optimization lze udělat relativně snadno* (a třeba Scala a Kotlin to mají – prostě přepíšete lokální proměnné a skočíte na začátek metody), ale obecnější tail call optimization, kdy můžete volat i jinou metodu, tak snadné není. Nevím o lepším řešení než trampolíny.
Jenže trampolíny znamenají režii, kterou by bylo potřeba platit i ve chvíli, kdy je nevyužijete. Nevidím způsob, jak udělat automatické tail call optimization, aniž by každý tail call znamenal režii.
Paradoxně by to nemusel nutně být problém u non-tail calls. Ty by mohly volat netrampolínovou verzi funkce. Ano, znamenalo by to ± mít každou metodu v bytecode dvakrát**. Vtipné by pak bylo tomu říkat non-tail call optimization (NTCO), protože non-tail call by byl rychlejší než tail call.
Ve výsledku by tak jediná výhoda automatického TCO v Clojure nejspíš spočívala v šetření stacku, ne v rychlosti.*) Nicméně je potřeba pamatovat na to, že volání sebe sama není v případě non-final metody obecně rekurze, protože může dojít k volání metody nahrazené v potomkovi. I pokud se nic takového nestane, kompilátor nemůže předem usoudit, že jde o rekurzi, takže optimalizaci neprovede. I pro tyto případy mají Scala a Kotlin možnost označit metodu jako tailrec, kde si pak kompilátor stěžuje, když se mu nepodaří TRO. Kotlin dává snad jen warning, ale i to pomůže.
**) BTW, na JVM lze rozlišovat metody jen podle return type – šlo by tedy vygenerovat obě varianty se stejným jménem. Trochu problém to může být tam, kde je potřeba interoperabilita s dalšími jazyky, ale to by asi řešil příznak synthetic. -
Pavel TišnovskýZlatý podporovatel
jj chtel jsem neco kratkeho a pomaleho. Samozrejme to jde takto rozbalit. Hmm priste mozna zkusim Ackermannovu funkci, i kdyz tam je ten caching asi trosku hur pochopitelny (co a s jakymi parametry se kdy vola).
-
Ackermann by asi uz bola tak trochu brutalita. Ten fibonacci je pre priklad dobry. Akurat by to tam chcelo zdoraznit (cervene a blikajuco) ze cache by mala byt az posledna moznost. Pretoze vydavam cache kam sa podivam (zvedsa blbo invalidovanu) a to aj od ludi, ktory dookola melu na temu asymptoticka zlozitost, ibaze akurat teoreticky...
-
Pavel TišnovskýZlatý podporovatel
Tyjo to je zvlastni. Ja kdybych s v tymu zeptal na caching (jako jestli to vubec jde a co to v tomto kontextu znamena) a asymptotickou slozitost, tak by asi moc odpovedi nebylo.
-
Pavel TišnovskýZlatý podporovatel
no zrovna tento tyden nam kolega hlasil, jak je matchovani s regexpy v Go pomale oproti grepu. No bodejt by nebylo, kdyz si regexp preklada uvnitr smycky pro kazdy zpracovavany radek ;) Potom jeste byla debata, jak asi vlastne regexpy pracuji, jakou to bude mit slozitost a jestli tedy neni lepsi si napred radek pro regexp predpripravit (slo o nejaky logy, takze klasika s casovyma razitkama).
-
Pavel TišnovskýZlatý podporovatel
Zvlastni je, ze by v mem pripade nekdo na radu typu "toto muzes nacachovat" nebo na otazku "a jakou to ma vlastne slozitost?" nedokazali (nekdy vubec) patricne zareagovat. Jako uznavam, u nas se delal nabor trosku zvlastnim zpusobem, takze se na to nedbalo.
-
Já se na tyhle věci neptám nikdy, protože pak se dozvím, že složitost algoritmu je inverzní Ackermann, do čehož pak zabředneme, nakonec se radujeme, že jsme přišli na lepší algoritmus, načež zjistíme, že s ním přišel Tarjan dekády zpátky (to se mi fakt stalo). Moje pohovory jsou vůbec dost dada, s jiným kandidátem jsme zase vymýšleli formální gramatiku pro švýcarskou němčinu (protože klasický Chomsky funguje jen pro Hochdeutsch). A tak bych mohl pokračovat.
-
Jaj tak... No, hlavnym kriteriom pri vybere by malo byt to ci je kandidat ochotny a schopny sa dalej vzdelavat a zdokonalovat... Ako je jasne ze nie kazdy ma mozok zadratovany abstraktne, aby bol schopny dekompozicie zadania, to sa neda naucit tak aby to islo same, da sa to ale naucit to aspom simulovat. Ale k takym zvedsa staci dat niekoho komu sa da povedat architekt.
-
Pavel TišnovskýZlatý podporovatel
no prave. Pokud je primarnim kriteriem znalost technologii X a Y a navic kandidatovi reknu, ze bude delat i ops (krome dev) a mit on cally, tak me proste spousta potencialne dobrejch lidi vypadne uz na tomto prvnim filtru.
(no ja z toho kolotoce uz trosku vypadavam, orientuji se v side projektu vic na research, tam je svet jeste docela v poradku :)
-
to bylo v bare bone jazyku, kterej mel jen rekurzi + snad jeste test na nulu. Neco takoveho. Tech jazyku existuje vic, treba jazyk s while != 0, operacemi ++ a -- a nekonecne registrama (nic dalsiho, tedy treba nastaveni na 0 je while a --, soucet pres while pro vynulovani destination nasledovane while a ++,---,) a tak. Jako nakonec je to docela sranda, ale ten Ackermann ne
-
Pavel TišnovskýZlatý podporovatel
ono to jde zmenit https://docs.python.org/3/library/sys.html#sys.setrecursionlimit ale zase se clovek vysledku nedocka v rozumnem case.
-
Pavel TišnovskýZlatý podporovatel
OT: pro ten Tvuj kurz: viz headline https://www.tiobe.com/tiobe-index/
-
Pavel TišnovskýZlatý podporovatel
jako byt v top 20 uz znamena dost z "politickeho" hlediska, tedy kdyz se to treba clovek snazi prosadit ve firme (nedejboze v korporaci)
-
Hm, ackermann(3, 12) v Pythonu neprojde, rekurze je moc hluboká. Všude jinde na M2 cca. 4 sekundy (Go, Rust, Julia, Lean).
To by malo nejako vypovedat o kvalite pythonu? Hoci ackerman(3,12) v Ada na i7-4510U @ 2.00GHz je za 3 sekundy, tak je mnoho veci kde radsej volim python...
Pre vecsinu algoritmov pre realne pouzitie proste rekurzia nie je potrebna...
-
Ono “cachování” se často hodí a bývá přímo součástí algoritmů, kdy z naivní NP-těžké úlohy vznikne například kubická. Například Rete, bottom-up parsing a SLG rezoluce jsou tři pohledy na jeden efektivní a prakticky použitelný algoritmus. Jen se teda v tomto kontextu neříká cachování, ale tabling. Je na tom založen například IBM Watson.
-
Setkávám se se dvěma extrémy - jedni vývojáři píšou kód naivně a bez základní představy, že existuje výrazně lepší cesta z pohledu výkonu s řádově nižší složitostí a "premature optimalizátoři", kteří honí mikrosekundy tam, kde to není potřeba a zhoršují často i čitelnost. Lepší než cache je dobrý základní algoritmus (tedy samozřejmě souhlasím s tím, co píšeš), cache je zase lepší než snaha to pořešit nějakým vícevláknovým mechanismem, který je navíc konkrétně v Pythonu tak trochu problematický (GIL).
-
Njn, ja netvrdim ze cache ako taka je zbytocna. Problem ktory vidavam je ten ze:
- Cache je pouzita aj tam kde je zbytocna
- Clovek ktory ma problem s optimalizaciou algoritmu, optimalny algoritmus pre invalidaciu cache uz nedava vobec
- cache dopomoze len k zlomku vykonu, ktory by mohol byt vdaka optimalnemu algoritmu
- zvysi sa chybovost koli zastaralemu obsahu cache
- vzrastu aj naklady na prevadzku, pretoze cache zoberie urcity vykon a budete potrebovat aj povodny vykon koli refresu chache...
Cache je ako koks, prilezitostne povzbudi, ale nespravne pouzitie a nauzivanie sa vzdy nepekne zvrhne...
13. 8. 2023, 21:30 editováno autorem komentáře
