Dědičnost dnes

zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Dědičnost dnes
« Odpověď #975 kdy: 04. 02. 2017, 11:46:11 »
Asymptotická časová složitost algoritmu přece nezáleží na tom, v jakém programovacím jazyce ho napíšeme, nebo jo?
Můžeme to udělat pomocí dynamického programování, pomocí cyklu nebo rekurze, ale to pak už není tentýž algoritmus.
gll pořád není schopnej pochopit tohle:

Myslím, že se tady hlavně motají dohromady dvě věci: teoretická možnost výpočtu ve stejném množství kroků a praktický způsob, jak se v jednom nebo druhém případě reálně programuje a jaký je pak výkon toho kódu na reálném stroji.

Pokud programuju tak, jak je v FP zvykem, tak můžu dostat míň efektivní program (praktická efektivita). Ale neznám žádný argument, proč by z principu nešlo v FP "simulovat" ne-FP výpočet v přesně stejném počtu kroků (teoretická efektivita).

gll vehementně tvrdí, že "to je pravda". No tak může podat formální důkaz, místo toho, abysme si tady hráli na kočku a myš...
Nejdřív mu musíš vysvětlit, co to je formální důkaz ;) Snad pak aspoň začne mlžit o něčem jiném.


javaman ()

Re:Dědičnost dnes
« Odpověď #976 kdy: 04. 02. 2017, 12:19:58 »
Nechcete radši rozebírat něco k věci? Mirkův Elixír byl super a pak takový píčoviny, kde ani nevím, co je výsledkem. Je teda přístup do RAM konstantní?

SB už se na to taky vykašlal, i když měl plno zajímavých postřehů. Jen bohužel měl rád dynamické OOP, což vlastně OOP není :D Ba ne.

Takže je tu někdo, kdo píše větší věci v něčem dynamickém? A výhody vidí v čem? Dědičnost je tam asi už to nejmenší, protože prostě dědičnost je OK, jen se musí umět použit.

gll

Re:Dědičnost dnes
« Odpověď #977 kdy: 04. 02. 2017, 16:16:11 »
Myslím, že se tady hlavně motají dohromady dvě věci: teoretická možnost výpočtu ve stejném množství kroků a praktický způsob, jak se v jednom nebo druhém případě reálně programuje a jaký je pak výkon toho kódu na reálném stroji.

Pokud programuju tak, jak je v FP zvykem, tak můžu dostat míň efektivní program (praktická efektivita). Ale neznám žádný argument, proč by z principu nešlo v FP "simulovat" ne-FP výpočet v přesně stejném počtu kroků (teoretická efektivita).

gll vehementně tvrdí, že "to je pravda". No tak může podat formální důkaz, místo toho, abysme si tady hráli na kočku a myš...

Vy tvrdíte, že nějaký konkrétní algoritmus, případně datová struktura, existuje. Já netvrdím, že neexistuje. Jen vás žádám o podrobnější informace. Možná jste mohl poradit Richovi Hickeymu jak v clojure implementovat persistentní pole s konstantním přístupem k libovolnému prvku.

Pokud nevěříte mé analýze složitosti té vámi poskytnuté implementace dijkstrova algoritmu, tak si ji spusťte pro různě velké grafy a změřte si časy běhu.

Re:Dědičnost dnes
« Odpověď #978 kdy: 04. 02. 2017, 16:41:38 »
Vy tvrdíte, že nějaký konkrétní algoritmus, případně datová struktura, existuje.
Aha. Tak to jsem sám nevěděl, že tvrdím, že nějaká struktura existuje. No tak fajn.

Jen vás žádám o podrobnější informace.
Vůbec nevím o čem, takže asi těžko můžu odpovědět. Na otázky typu "a tohle funguje jak?" fakt odpověď neznám.

Pokud nevěříte mé analýze složitosti té vámi poskytnuté implementace dijkstrova algoritmu, tak si ji spusťte pro různě velké grafy a změřte si časy běhu.
Za prvé opravdu nevěřím, protože půl hodiny před tím, co jste napsal výsledek, jste zjistil, že Haskell je lazy. Čili opravdu nevěřím, že je ta analýza správně (ale netvrdím, že je špatně).

Ale především to vůbec nic nedokazuje. Je to jedna imlpementace jednoho algoritmu, co by z toho jako mělo plynout?

Opakuju znovu: pokud máte potřebu dokazovat, že v FP něco nelze, tak poskytněte formální důkaz. Tohle plácání játrama mě už fakt nebaví.

gll

Re:Dědičnost dnes
« Odpověď #979 kdy: 04. 02. 2017, 17:19:57 »
Pokud nevěříte mé analýze složitosti té vámi poskytnuté implementace dijkstrova algoritmu, tak si ji spusťte pro různě velké grafy a změřte si časy běhu.
Za prvé opravdu nevěřím, protože půl hodiny před tím, co jste napsal výsledek, jste zjistil, že Haskell je lazy. Čili opravdu nevěřím, že je ta analýza správně (ale netvrdím, že je špatně).

Tím, že je haskell lazy jste argumentoval vy. Na složitost algoritmu to nemá vliv. Stále je to minimálně O(V^2).

Ale především to vůbec nic nedokazuje. Je to jedna imlpementace jednoho algoritmu, co by z toho jako mělo plynout?

Vy jste se tím odkazem snažil podpořit Zbojovo tvrzení. Proč jste posílal odkaz na implementaci, která je asymptotycky pomalejší než běžné implementace v jiných jazycích?

Opakuju znovu: pokud máte potřebu dokazovat, že v FP něco nelze, tak poskytněte formální důkaz. Tohle plácání játrama mě už fakt nebaví.

Vy tvrdíte, že existuje řešení nějakého problému. Já neumím dokázat neexistenci toho řešení, ale chtěl bych to řešení vidět. Co bych měl já dokazovat? Takto můžete tvrdit, že umíte prolomit RSA. Nikdy zatím nedokázal, že to nejde.


gll

Re:Dědičnost dnes
« Odpověď #980 kdy: 04. 02. 2017, 17:21:43 »
s/nikdy/nikdo/

Re:Dědičnost dnes
« Odpověď #981 kdy: 04. 02. 2017, 17:52:43 »
Tak to ne, o takovouhle "diskusi" už fakt nemám zájem. Jenom, abyste věděl proč:

Tím, že je haskell lazy jste argumentoval vy. Na složitost algoritmu to nemá vliv. Stále je to minimálně O(V^2).
Ne, já jsem tím neargumentoval. Vy jste udělal chybu, protože jste nevěděl (nebo si neuvědomil), že je Haskell lazy cca půl hodiny před tím, než jste vyrukoval s výsledkem výpočtu složitosti toho algoritmu. To je asi tak, jakoby měl člověk zavézt rodinu do Chorvatska a půl hodiny před jízdou se ptal manželky, kde je spojka. Taky bych mu nevěřil.

Vy jste se tím odkazem snažil podpořit Zbojovo tvrzení.
Nic jsem se neznažil podpořit. Vy jste tady říkal, že nemůžete najít implementovaného Dijkstru. Já jsem řekl, že to jde snadno vygooglovat, pak jste tvrdil, že jste našel jenom implmentace s C-knihovnami, tak jsem opáčil, že mně dává Google jako hned druhý odkaz pure-Haskell implementaci.

Sorry, ale fakt tady nejsme vaše asistentky...

Vy tvrdíte, že existuje řešení nějakého problému. Já neumím dokázat neexistenci toho řešení, ale chtěl bych to řešení vidět.
Však jste ho viděl. Je to řetězení funkcí.

HOWGH.

Re:Dědičnost dnes
« Odpověď #982 kdy: 04. 02. 2017, 17:55:57 »
Jo, tohle jsem ještě zapomněl:

Co bych měl já dokazovat?
To, co tvrdíte: že FP výpočet něčeho musí být nutně pomalejší než ne-FP. Šup, do toho!
« Poslední změna: 04. 02. 2017, 17:59:21 od Mirek Prýmek »

gll

Re:Dědičnost dnes
« Odpověď #983 kdy: 04. 02. 2017, 18:02:32 »
Tak to ne, o takovouhle "diskusi" už fakt nemám zájem. Jenom, abyste věděl proč:

Tím, že je haskell lazy jste argumentoval vy. Na složitost algoritmu to nemá vliv. Stále je to minimálně O(V^2).
Ne, já jsem tím neargumentoval. Vy jste udělal chybu, protože jste nevěděl (nebo si neuvědomil), že je Haskell lazy cca půl hodiny před tím, než jste vyrukoval s výsledkem výpočtu složitosti toho algoritmu. To je asi tak, jakoby měl člověk zavézt rodinu do Chorvatska a půl hodiny před jízdou se ptal manželky, kde je spojka. Taky bych mu nevěřil.

složitost head . sortBy ..... vůbec nemusí být v lazy jazyce O(n). Záleží na implementaci té funkce. V pythonu je funkce sorted také "lazy" (vrací generátor), ale pro hledání minima se moc nepoužívá.

Lama

Re:Dědičnost dnes
« Odpověď #984 kdy: 04. 02. 2017, 18:03:15 »
Panove, polyka vase pritelkyne?

Tebe by slupla jak malinu..  ;) Jinak záleží jak co, v jakém množství, jaké chuti... ;) ;D
Proč se ptáš?

Re:Dědičnost dnes
« Odpověď #985 kdy: 04. 02. 2017, 18:05:48 »
složitost head . sortBy ..... vůbec nemusí být v lazy jazyce O(n). Záleží na implementaci té funkce.
Ano, to je velmi triviální pozorování, viz např:

Kód: [Vybrat]
def sort(a):
  while True:
    pass

gll

Re:Dědičnost dnes
« Odpověď #986 kdy: 04. 02. 2017, 18:11:19 »
Vy jste se tím odkazem snažil podpořit Zbojovo tvrzení.
Nic jsem se neznažil podpořit. Vy jste tady říkal, že nemůžete najít implementovaného Dijkstru. Já jsem řekl, že to jde snadno vygooglovat, pak jste tvrdil, že jste našel jenom implmentace s C-knihovnami, tak jsem opáčil, že mně dává Google jako hned druhý odkaz pure-Haskell implementaci.

Sorry, ale fakt tady nejsme vaše asistentky...

o c knihovnách jsem nic nepsal. Našel jsem buť pomalé implementace, jako ta kterou jste poslal vy, nebo implementace používající explicitně změnu stavu.

Re:Dědičnost dnes
« Odpověď #987 kdy: 04. 02. 2017, 18:25:08 »
o c knihovnách jsem nic nepsal. Našel jsem buť pomalé implementace, jako ta kterou jste poslal vy, nebo implementace používající explicitně změnu stavu.
řešení, která jsem vygooglil nejsou čistě FP. Obecně nelze libovolný algoritmus pro stroj s náhodným přístupem do paměti zapsat pomocí skládání funkcí, jak tvrdí zboj.

gll

Re:Dědičnost dnes
« Odpověď #988 kdy: 04. 02. 2017, 18:59:11 »
Jo, tohle jsem ještě zapomněl:

Co bych měl já dokazovat?
To, co tvrdíte: že FP výpočet něčeho musí být nutně pomalejší než ne-FP. Šup, do toho!

http://www.cs.princeton.edu/courses/archive/fall03/cs528/handouts/Pure%20Versus%20Impure%20LISP.pdf

v tom článku je příklad takového problému

Re:Dědičnost dnes
« Odpověď #989 kdy: 04. 02. 2017, 19:16:33 »