Vlákno názorů k článku Erlang: trochu jiný přístup k programování od buks - Zajímalo by mě, jak je to s těmi...
-
Sten (neregistrovaný)
Seznamy jsou (stejně jako všechny ostatní hodnoty) neměnné, takže se při změně kopírují, ale protože seznamy obsahují jen ukazatele na hodnoty, tak je to většinou celkem levná operace. Pokud potřebujete seznamy o hodně prvcích, lze použít třeba hashové tabulky, kde se kopíruje akorát seznam kyblíků (bucketů) a ten kyblík, který se změnil.
-
Pavel TišnovskýZlatý podporovatelJestli jde o seznamy, tak tam se diky tomu, ze jsou immutable u mnoha operaci kopie provadet nemusi, protoze vic seznamu muze sdilet stejnou pamet. To stejne je v Clojure taktez se seznamy a (jeste "fikaneji") pro vektory.
-
Karel (neregistrovaný)
K funkcionálnímu programování jsem se nejblíže dostal s Lispem, takže mi zřejmě "opravdové funkcionální programování" uniká. Tak nějak jsem žil v domění, že základem jsou právě seznamy a jejich nekonečné změny. Některé funkce seznamy generují, jiné zpracovávají, některé transformují. Všechny ty "head" a "tail" ve mně evokují pocit, že je tam moře seznamů, které se neustále mění.
Čtu tohle vlákno několikrát, ale moc mi to nedochází. Znamená to, že prvky seznamu jsou immutable někde v paměti, ale vlastní seznam je dynamická struktura, která se mění? Ve smyslu že je to pole nebo nějaká jiná struktura pointerů a že se v ní přepisuje, přičemž "neměnná" se vztahuje k jednotlivým prvkům, ale nikoliv seznamům vlastním?
Nebo to doopravdy neustále generuje nové a nové seznamy, kde je jen nižší režie díky tomu, že jsou to odkazy na prvky a tak se bavíme o řádově 4-8 bytech na prvek?
Kupříkladu by mě zajímal Bubble sort nebo Merge sort. Typicky algoritmy měnící pořadí prvků v seznamu. Jestli ten Bubble sort skutečně O(n^2) krát kopíruje seznam.
-
Pavel TišnovskýZlatý podporovatel
Zkusím říct, jak je to v Clojure, určitě nekdo doplní i informace o Erlangu. V Clojure existují mj. i typy "seznam" a "vektor", které jsou immutable, tj. nemění se ani jejich obsah (jednotlivé prvky), ani jejich struktura (pořadí prvků, nelze přidat ani ubrat prvky atd.). Ono by to jinak nešlo, protože prvkem seznamu/vektoru může být samozřejmě i další seznam nebo vektor.
Dále - k seznamu lze připojit další prvek na začátek, aniž by to změnilo zbytek seznamu (jedná se o klasický lineárně vázaný seznam). to ovšem znamená, že nově vytvořený seznam může sdílet svoji strukturu (tail) se stávajícím seznamem, protože je zaručeno, že nedojde ke změně ani jednoho seznamu (jsou immutable) == k žádným kopiím zde nedochází.
Dtto - k vektoru lze připojit prvek na konec, se stejnými vlastnostmi, jaké jsem zmínil v předchozím odstavci, tj. nový vektor i starý vektor sdílí svoji strukturu, opět žádné kopie.
Ad bubble sort - když se to napíše naivně, bude se (v Clojure) provádět skutečně kopie, ale to snad nikdo tímto způsobem psát nebude ne? :-) resp. pro immutable struktury asi těžko někdo zvolí bubble sort a když ano, tak se všemi důsledky.
-
V Erlangu je seznam tvoren 2 prvkovymi bunkami - prvni prvek obsahuje hodnotu (nebo odkaz na hodnotu) a druhy prvek obsahuje odkaz na dalsi prvek (nebo specialni hodnotu "prazdny seznam") - to je shodne napr. s Lispem.
Pridani prvku na zacatek je jednoducha operace - vytori se jedna nova bunka, do prvni polozky se vlozi hodnota a do druhe odkaz na stary seznam. Tim druhy seznam sdili vse az na prvni bunku s prvnim seznamem.
Pridani prvku na konec je oproti tomu velmi draha operace. Nejdriv se vytvori nova buknka, do prvni polozky se vlozi hodnota a do druhe odkaz na prazdny seznam. Pak se vezme posledni bunka predchoziho seznamu - ta se zkopiruje a jako druhy prvek se nastavi predchozi vytvorena bunka. A takhle se rekurzivne pokracuje az na zacatek.
To znamena, ze se musi zkopirovat vsechny bunky seznamu.Erlang nema nic jako pole. Na vyber je jen seznam, n-tice (neco jako pole pevne delky) a pole bitu / bytu.
-
ad: Znamená to, že prvky seznamu jsou immutable někde v paměti, ale vlastní seznam je dynamická struktura, která se mění?
Probuh. To znamena, ze immutable jsou jak prvky, tak samotne "seznamy", a prave proto se daji (cele nebo jejich casti) znovu vyuzivat.
Pokud jde o singly-linked listy, znamena to napr. ze prepend (pridani na zacatek) je kurva lacina operace, protoze se vytvori jen novy head (ve smyslu drzaku na jeden prvek a tail), a tail je puvodni list. A zrovna tak odebrani prvniho prvku, jen se vrati tail, coz je - mozna prazdny - list.
Podobne v pripadech slozitejsich struktur (treba clojure immutable vectory, scala to ma reseny stejne, http://hypirion.com/musings/understanding-persistent-vector-pt-1), proste se pouzijou casti ktery se nezmenily, jednak samotny prvky, ale hlavne uz hotove casti puvodni datove struktury ktere nebylo treba "zmenit".
Bubble sort je neefektivni i v mutable provedeni (immutable varianta je silenstvi).
Immutable merge sort nemeni poradi prvku, jen rozlozi puvodni strukturu a kdyz sklada novou, vlozi prvky ve spravnym poradi.
Trocha o merge a quick sortech a immutable strukturach: http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists
Samozrejme je tu moznost udelat docasnou mutable datovou strukturu, preskladat to v ni na miste a pak vyrobit immutable strukturu (nebo jen zakazat dalsi zmeny), pokud to ze je neco mutable neni "pozorovatelny z venku", je to immutable ;-)))
-
Karel (neregistrovaný)
Díky, už to chápu, snad správně. Je to celé immutable, takže "naivní" bubblesort je katastrofa. Co to umí levně (skoro zadarmo) je práce s head a tail, takže přidávání prvků na začátek nebo jejich odebírání je složitost konstantní. Proto pokud použiji algoritmus, který vystačí s "head a tail", tak bude velmi efektivní. Mimochodem, i ten bubblesort se dá napsat nad linked listem jako O(n^2), takže pokud immutable umí head a tail s konstatní složitostí, tak by to immutable nemělo zhoršit.
Jestli to chápu správně, tak obecně pokud mám kód, který zpracovává seznam jako linked list, tak bude efektivní i při jeho přeskládávání a fakt, že je immutable, to nijak nezhorší. Teprve pokud použiji pole (nebo nějakou jeho "simulaci") tak mám problém. Kreslení do frame bufferu tedy asi nebude typickou aplikací.
Čemu ale vůbec nerozumím je použití částí. Chápu, že když mám nějaký linked list, tak přidat mu prvek na začátek je triviální - udělám nový prvek a dám mu odkaz na původně první prvek. Mám tak dva seznamy, kde jeden je podmnožinou druhého. Jenže v tomhle případě oba končí stejně, jen má jeden něco extra na začátku. Když bych měl seznam linkovaný zpětně, tak můžu takhle přidávat na konec, ale začátek mají stejný. Jak realizovat, abych měl jeden seznam řekněme CDE a druhý ABCDEFG? Tedy jak to realizovat bez toho, že bych měl v paměti seznamy dva? Kdyby byl jen jeden prvek E, jak by poznal, kdy má jako následníka hlásit nic (první seznam) nebo F (druhý seznam)? Bez toho, abych měl dva prvky E (jen položku seznamu, v té bude pointer na datovou strukturu samotného objektu E, v obou seznamech stejný) si to představit nedokážu.
Jinak řečeno umím pochopit konstantní složitost přidání/odebrání prvku na začátku, respektive na konci (ne oboje najednou), ale ne obecné "proste se pouzijou casti ktery se nezmenily". Řečeno na příkladu, pokud mám seznam N prvků a ten na pozici M chci odstranit, tak vše od začátku až po M musím vytvořit znovu, M tam už nepřidám a místo něj tam dám link na tail(M). Takže znovu použití se týká jen části tail(M), vše před tím M musím vytvářet znovu, byť se to vlastně nemění. Jen prostě v mé nové verzi seznamu prvek M-1 linkuje nikoliv na M, ale na M+1. Je právě tohle myšleno tím "části který se nezměnily", nebo mi uniká ještě nějaká jiná vlastnost seznamů?
ČLÁNKY DO MAILU