Funkcionální pole (a jiné mutabilní datové struktury)

[Jason]

Na pohovoru jsem dostal za úkol navrhnout co nejefektivnější implementaci referenčně transparentního pole, tj. když chci třeba změnit prvek, píšu

Kód: [Vybrat]

arr = arr.set(index, value) Kromě naivní implementace (kopírování) mě napadla jenom kráva, ale prý existují i efektivnější optimalizace, jen jsme se k nim kvůli nedostatku času už nedostali. Máte někdo zkušenosti, jak se takové věci implementují v produkčním kódu? Nějaká lepší optimalizace mě už nenapadá.

[Reklama]

[gegi]

co je to kráva?

[Filip Jirsák]

co je to kráva?

CoW, copy-on-write.

Na pohovoru jsem dostal za úkol navrhnout co nejefektivnější implementaci referenčně transparentního pole, tj. když chci třeba změnit prvek, píšu

Kód: [Vybrat]

arr = arr.set(index, value) Kromě naivní implementace (kopírování) mě napadla jenom kráva, ale prý existují i efektivnější optimalizace, jen jsme se k nim kvůli nedostatku času už nedostali. Máte někdo zkušenosti, jak se takové věci implementují v produkčním kódu? Nějaká lepší optimalizace mě už nenapadá.

Např. nemusíte při změně kopírovat celé pole, ale jen si zapamatujete změnu a k ní odkaz na původní pole. Čtení pak probíhá tak, že nejprve hledáte mezi změnami, a když tam nic nenajdete, hledáte v předkovi. Samozřejmě závisí na poměru čtení a zápisů, CoW je efektivnější při nízkém počtu zápisů a vysokém počtu čtení, pamatovat si jen rozdíly je pro čtení méně efektivní.

[gll]

vektor v clojure

https://hypirion.com/musings/understanding-persistent-vector-pt-1

[gegi]

Mají tyhle funkcionální hracky vubec realny smysl? Jakykoliv vypocetni vykon ktery byste mohli ziskat paralerizaci, stejně ztratíte na režii, zbytecnem kopirovani a cache misses.

[Reklama]

[gll]

Mají tyhle funkcionální hracky vubec realny smysl? Jakykoliv vypocetni vykon ktery byste mohli ziskat paralerizaci, stejně ztratíte na režii, zbytecnem kopirovani a cache misses.

z hlediska výkonu asi většinou ne, ale podle mě to usnadňuje psaní korektních a testovatelnách programů. Vyzkoušejte Elixir.

[Filip Jirsák]

Mají tyhle funkcionální hracky vubec realny smysl? Jakykoliv vypocetni vykon ktery byste mohli ziskat paralerizaci, stejně ztratíte na režii, zbytecnem kopirovani a cache misses.

Mají. Výpočetní výkon nemusíte získávat jenom paralelizací a různé datové struktury nijak nesouvisí s funkcionálním programováním. I obyčejný mutable seznam můžete implementovat třeba jako pole (s CoW a „zbytečným“ kopírováním) nebo jako spojový seznam (s cache miss).

[ava]

Mají tyhle funkcionální hracky vubec realny smysl? Jakykoliv vypocetni vykon ktery byste mohli ziskat paralerizaci, stejně ztratíte na režii, zbytecnem kopirovani a cache misses.

Záleží na úloze. Třeba vector ve Scale (starý doc: https://www.scala-lang.org/docu/files/collections-api/collections_15.html) má dobrou prostorovou lokalitu dat, takže s cache misses není extra problém. Zbytečné kopírování je naopak často problém mutable struktur - ať už jako defenzivní kopie, nebo právě kopie pro paralelní zpracování, když se chci vyhnout zamykání. Immutable struktury je možné sdílet i bez zamykání a díky structural sharing částí dat se mohu spoustě kopírování vyhnout.

[JSH]

Mají tyhle funkcionální hracky vubec realny smysl? Jakykoliv vypocetni vykon ktery byste mohli ziskat paralerizaci, stejně ztratíte na režii, zbytecnem kopirovani a cache misses.

Mají. Třeba implementovat undo/redo je s referenčně transparentníma strukturama úplná trivialita.

[Bacsa]

Mají tyhle funkcionální hracky vubec realny smysl? Jakykoliv vypocetni vykon ktery byste mohli ziskat paralerizaci, stejně ztratíte na režii, zbytecnem kopirovani a cache misses.

Jaké režii? V reálných algoritmech nebývají persistentní datové struktury pomalejší, CoW není jediná optimalizace, ilustrativní je například funkcionální bubble sort, který se dá dělat in-place. Problém rádobyvývojářů je, že umí trochu PHP a hned si myslí, že na všechno mohou mít relevantní názor, ale sofistikované algoritmy nejsou schopni ani jen pochopit, natož naimplementovat.