Dědičnost dnes

[balki]

Co má společného Turingův stroj s tím co jsem psal? Já psal o stroji s náhodným přístupem do paměti. Pomocí turingova stroje i lambda kalkulu můžete vyřešit stejné problémy, ale ne ve stejném čase a se stejnou paměťovou náročností. Běžné algoritmy jsou postupy výpočtu pro stroj RAM.

Myslim, ze to je problem v teorii, nikoli v praxi. Pominme ted to, ze FP je jen abstrakce, ktera se pak beztak preklada do von Neumannovy architektury.

Potiz je v tom, ze RAM, ktera ma pristup O(1), nelze fyzikalne zkonstruovat. I dnes se to projevuje tim, ze existuje neco jako hierarchie pameti (a ze treba nelze zvetsovat L1 cache, protoze se typicky ocekava, ze do ni pujde pristupovat v jednom cyklu). Proto se proste fakt, ze realna RAM neni O(1) zanedbava a pocita se s tim, jako by to bylo O(1), protoze to je dostatecne dobra aproximace pro velikosti RAM, ktere se typicky pouzivaji.

Tedy realna RAM neni O(1), ale spis O(log n), a takovou RAM lze realizovat i funkcionalne (pomoci stromu).

Přístup do RAM je O(1). Definice Big-O se dnes už na školách neučí nebo co? Takhle se pak nedá vůbec diskutovat...

pristup do RAM je N*log(n). nevim co to tady spletate. minulej rok jsem statnicoval na CVUT, tak neco o tom vim

Mam dojem, ze tu motate RAM a RAM.

Jedno je Random access machine, co je vypoctovy model. A druhe random access memory.

[Reklama]

[javaman ()]

A ještě pokud tomu dobře rozumím, tak "pravé" OOP je dynamické. Takže aplikaci zapnu a vyvíjím za chodu? Protože při každém volání metody jsem ji mohl předefinovat, ne? A fakt takhle někdo vyvíjí?

A čo si, Kefalín, predstavujete pod takým slovom "dynamický"?

Že všechno je dané při spuštění aplikace. Nic se mi nemění. Pokud se něco mění, tak za pevně definované hodnoty, které jsem znal při spuštění (změna konfigurace). Takže to lze i otestovat. Všechno ostatní mi přijde jako takové hraní na vývoj. Možná ale právě tu vaši dynamičnost nechápu dobře.

Jinak děkuji ava za výjádření.

[javaman ()]

To není žádný pravěk, je to jiný přístup. Já dávám přednost klasickému vývoji editací zdrojového kód po důkladném rozvážení a distribuci změn pomocí VCS. Smalltalk mi přijde jako vaření guláše. Je to málo slaný? Přisol. Zároveň mi do hrnce někdo strká lžíci, neb má hlad, kráva se na přední straně ještě pase, zadní noha se jí už vaří. Spadlo z ní zezadu něco do hrnce? Nevadí, vem naběračku, vylov to ven, zamíchej, přidej majoránku a vaříme dál.

Může to fungovat, ale možná je i nějaký dobrý důvod, proč se to ve větším měřítku neujalo.

Neujalo se to ze zcela jednoduchého dobrého důvodu - způsob překladu a spouštění aplikací většiny jazyků to neumožňuje. Mimoto váš příměr je docela hloupý, osobně neshledávám žádný přínos v potřebě překladu celé aplikace při drobné změně v jedné metodě, ale HLAVNĚ v časově náročné opětovné simulaci situace kdesi hluboko v aplikaci, to je tím hlavním problémem.

Tomu rozumím. Když máš nějaký stav, tak je dobré si s ním hrát. Je otázkou, jestli to není jen chyba návrhu. V Javě na to nástroje jsou, jen se právě moc nepoužívají. Podle mě musíš mít dost divně definované stavy, když tě zajímá ten za chodu a nejde lehce zreplikovat.

Samozřejmě při změně metody se aplikace celá nekompiluje.

[spasitel]

Zaprvé, zkratkou RAM jsem myslel https://en.wikipedia.org/wiki/Random-access_machine .

ja jsem myslel random access memory. vy neco jineho?

Z log(n) už máme "N*log(n)", tedy funkci dvou proměnných...super. Tohle už ani není vtipný, tohle bude někdy tvořit SW? 

N=n, stale je to stejny. nevim co ucili vas, ale asi nic moc, protoze neznate elementarni veci. programuji ruzne cipy, tak snad neco o tom vim

[javaman ()]

To není žádný pravěk, je to jiný přístup. Já dávám přednost klasickému vývoji editací zdrojového kód po důkladném rozvážení a distribuci změn pomocí VCS. Smalltalk mi přijde jako vaření guláše. Je to málo slaný? Přisol. Zároveň mi do hrnce někdo strká lžíci, neb má hlad, kráva se na přední straně ještě pase, zadní noha se jí už vaří. Spadlo z ní zezadu něco do hrnce? Nevadí, vem naběračku, vylov to ven, zamíchej, přidej majoránku a vaříme dál.

Může to fungovat, ale možná je i nějaký dobrý důvod, proč se to ve větším měřítku neujalo.

Neujalo se to ze zcela jednoduchého dobrého důvodu - způsob překladu a spouštění aplikací většiny jazyků to neumožňuje. Mimoto váš příměr je docela hloupý, osobně neshledávám žádný přínos v potřebě překladu celé aplikace při drobné změně v jedné metodě, ale HLAVNĚ v časově náročné opětovné simulaci situace kdesi hluboko v aplikaci, to je tím hlavním problémem.

1. Způsob překladu a spouštění aplikací většiny jazyků to neumožňuje, protože o to jejich autoři nestáli.
2. Nikde jsem nepsal, že se má překládat celá aplikace kvůli jedné metodě a prakticky nikdy se to neděje.
3. Pokud je potřeba aplikaci opravovat tak, že do ní potřebujeme nahlížet za běhu v době, kdy k chybě došlo, máme podstatně závažnější problém - taková aplikace je časovaná bomba a do diskuse o paradigmatech je to velice závažný argument. A už vůbec si takový přístup nechci představovat v situaci, kdy dochází k poškozování cenných dat.

Nějak tak.

[Reklama]

[zboj]

Zaprvé, zkratkou RAM jsem myslel https://en.wikipedia.org/wiki/Random-access_machine .

ja jsem myslel random access memory. vy neco jineho?

Z log(n) už máme "N*log(n)", tedy funkci dvou proměnných...super. Tohle už ani není vtipný, tohle bude někdy tvořit SW? 

N=n, stale je to stejny. nevim co ucili vas, ale asi nic moc, protoze neznate elementarni veci. programuji ruzne cipy, tak snad neco o tom vim

Bože, do čehos to dal duši... 

[Kiwi]

No prave ze ten logaritmus (ne velikosti programu ale dat) muze byt casto v realu az moc optimisticky odhad :-/

http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i

Což je další argument proti používání funkcionálního programování všude.

Zkus to, prosim, ozavorkovat

Tedy realna RAM neni O(1), ale spis O(log n), a takovou RAM lze realizovat i funkcionalne (pomoci stromu).

Tak to určitě neplatí. Čas přístupu do paměti neroste logaritmicky s velikostí vstupu programu. O(1) je jen horní odhad rychlosti operace. Stačí uvažovat nejpomalejší možný přístup. Pořád to bude reálnému hardwaru mnohem blíž než Turingův stroj.

No prave ze ten logaritmus (ne velikosti programu ale dat) muze byt casto v realu az moc optimisticky odhad :-/

http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i

To je teda dobrá volovina! Vzít teoretický koncept a aplikovat ho na jedno konkrétní technické řešení... Např. v mém embedded světě nic takového neplatí. Navíc cache slouží k urychlení práce s pamětí! Autor to obrátil, vzal tu urychlenou práci za O(1) a zkoumal, o kolik pomalejší to ve skutečnosti je. Ve skutečnosti O(1) je právě ten přístup bez cache a měl případně zkoumat, o kolik je to s cache lepší než teoretická O(1).

A jak muze byt cache lepsi nez teoreticka O(1)? (hint: zamysli se nad tim, co to O znamena)

Jinak samozrejme vsechny tyhle aplikace vyzaduji nejakou davku nasili. Protoze realny pocitac s omezenou RAM a SSD ma ostatne konecny pocet stavu a tak je to, vzato do dusledku, konecne automat

Když O(1) je z hlediska algoritmu základní stav, tak optimalizovaný stav musí být zákonitě rychlejší. Samozřejmě už ne v jazyku O-notace, to by jaksi nedávalo smysl, ale z pohledu elementárních operací.
Připadá mi přitažené za vlasy vzít nějakou optimalizaci, určenou pro nějaké konkrétní podmínky, a vzhledem k ní srovnávat situaci nad rámec těch podmínek. Jediné, proč by to někdo dělal, je kvůli tomu, že takto obráceně to lze zkoumat v O-notaci. Ale to zas nedává dobrý smysl, protože bez znalosti konkrétních podmínek je to zcela k ničemu. Bude záležet na hloubce cache a jejich velikosti na jednotlivých patrech a na konkrétním objemu dat. A konec konců na tom, jestli tam vůbec nějaká je (např. na mikrokontrolérech, které mají RAM přímo v sobě, je to věc poněkud zbytečná).
Koncept O má sloužit k porovnávání algoritmů, ne konkrétního technického vybavení a už vůbec ne to takto zobecňovat na základě nějakého konkrétního řešení u PC!

[spasitel]

vidim, ze tady je to samy expert na slozitosti a algoritmy

[balki]

vidim, ze tady je to samy expert na slozitosti a algoritmy

Odporucam literaturu.
Herbert S. Wilf: Algorithms and Complexity

https://www.math.upenn.edu/~wilf/AlgoComp.pdf

[JS]

Tedy realna RAM neni O(1), ale spis O(log n), a takovou RAM lze realizovat i funkcionalne (pomoci stromu).

Tak to určitě neplatí. Čas přístupu do paměti neroste logaritmicky s velikostí vstupu programu. O(1) je jen horní odhad rychlosti operace. Stačí uvažovat nejpomalejší možný přístup. Pořád to bude reálnému hardwaru mnohem blíž než Turingův stroj.

Jenom pro ujasneni, n je mnozstvi pameti, ktere mas k dispozici (protoze RAM je konecna), a pod RAM myslim vsude Random Access Memory.

Jde mi o to, ze bud chces teoreticky dokazat, ze FP je vypocetne horsi - pak ano, mas pravdu, neumoznuje O(1) pristup do pameti. Jenze v praxi O(1) pristup neumoznuje nic, zadne zarizeni (jinak receno, kazde fyzikalni zarizeni bude pomalejsi pokud bude dostatecne velke).

Nebo se chces bavit o praktickych aspektech implementace FP, a pak nemusime nutne trvat na tom, aby vysledny program (strojovy kod) byl funkcionalne cisty, protoze FP pouzivame jen jako abstrakci pro popis, nikoli jako vypocetni model.

Takze at se snazis dokazat cokoli z toho, pro praxi to neni rozhodujici.

[gll]

Jenom pro ujasneni, n je mnozstvi pameti, ktere mas k dispozici (protoze RAM je konecna), a pod RAM myslim vsude Random Access Memory.

Předpokládám, že velikost paměti počítače je konstantní. Ani nevěřím tomu, že rychlost přístupu do paměti závisí na její velikosti. Určitě je rozdíl v rychlosti přístupu do cache a dohlavní paměti, ale to se nedá popsat takto jednoduše.

[SB]

A čo si, Kefalín, predstavujete pod takým slovom "dynamický"?

Že všechno je dané při spuštění aplikace. Nic se mi nemění. Pokud se něco mění, tak za pevně definované hodnoty, které jsem znal při spuštění (změna konfigurace). Takže to lze i otestovat. Všechno ostatní mi přijde jako takové hraní na vývoj. Možná ale právě tu vaši dynamičnost nechápu dobře...

Tak teď jsem lehce na pochybách, zda rozumíte alespoň té Javě...

[SB]

Tomu rozumím. Když máš nějaký stav, tak je dobré si s ním hrát. Je otázkou, jestli to není jen chyba návrhu. V Javě na to nástroje jsou, jen se právě moc nepoužívají. Podle mě musíš mít dost divně definované stavy, když tě zajímá ten za chodu a nejde lehce zreplikovat...

A akú rečú ste terazky hovorili?

[noef]

A čo si, Kefalín, predstavujete pod takým slovom "dynamický"?

Že všechno je dané při spuštění aplikace. Nic se mi nemění. Pokud se něco mění, tak za pevně definované hodnoty, které jsem znal při spuštění (změna konfigurace). Takže to lze i otestovat. Všechno ostatní mi přijde jako takové hraní na vývoj. Možná ale právě tu vaši dynamičnost nechápu dobře...

Tak teď jsem lehce na pochybách, zda rozumíte alespoň té Javě...

Mozna to neformuloval nejlepe, ale predpokladam, ze mluvi o typech - ty se v Jave za behu opravdu typicky nemeni (generovani bytekodu za behu neni asi moc bezne).

[gll]

Nebo se chces bavit o praktickych aspektech implementace FP, a pak nemusime nutne trvat na tom, aby vysledny program (strojovy kod) byl funkcionalne cisty, protoze FP pouzivame jen jako abstrakci pro popis, nikoli jako vypocetni model.

Takze at se snazis dokazat cokoli z toho, pro praxi to neni rozhodujici.

Já jsem požadoval konkrétní implementaci konkrétního algoritmu, v konkrétním FP jazyku bez side efektů, která po překladu vygeneruje pro reálný HW stejně efektivní kód (stačí z hlediska asymptotické složitosti) jako implementace v imperativním jazyku.

Zboj říkal, že to VŽDY jde, a zdůvodnňoval to plácáním nesmyslů o výpočetní síle lambda kalkulu. Já netvrdím, že to v tomto konkrétním případě nejde, jen jsem takové řešení dosud neviděl.

Přijde mi, že Zboj, Prýmkem a vy máte své náboženství a snažíte se ho obhajovat za každou cenu. Když náhodou nemáte pravdu, tak protivníka ubijete argumentem "to v praxi není rozhodující" nebo naopak pseudointelektuálními žvásty (ty používá hlavně zboj) a citací vašich FP guruů.