Scala: dočasné mutable a immutable mapy
V programech jsou často vytvářeny dočasné mapy pro efektivní hledání v čase O(1). Jsou zcela lokální, použité pouze v jedné metodě a dál nijak sdílené. Ve Scale to může vypadat nějak takhle:
entities.collect { case e if e.something => (e.id, e) }.toMap
Výsledkem je mapa, kterou můžu použít pro hledání podle určitého klíče. Metoda
toMap vyrobí neměnnou (immutable) mapu. Pokud si dobře vzpomínám, toto
chování původně nebylo zaručeno. Kontrakt sliboval jen, že výsledkem bude
nějaká mapa, nespecifikováno zdali neměnná nebo měnitelná. Ve verzi 2.13 (a
nejspíš i několik verzí nazpět) metoda vždy vrací
scala.collection.immutable.Map.
Neměnné mapy jsou interně implementované s pomocí trie – prefixového stromu do nějž se indexuje hashem klíče. Od verze 2.13 standardní knihovna používá efektivní CHAMP implementaci. Jde o poměrně komplikovanou strukturu, která má několik úrovní, potřebuje mnoho alokací a nahánění pointerů. Naproti tomu měnitelná mapa je obyčejná hashtabulka postavená na jednom poli a spojových seznamech kolizí. Takovou mapu je mnohem snadnější vytvořit.
Proto v určitých případech může být efektivnější zmiňované dočasné mapy vytvářet jako měnitelné. Nepředstavuje to problém, protože jsou zcela lokální a nikdo kromě metody, kde vzniknou a zaniknou, je neuvidí.
Ve Scale je i na tohle oneliner:
keyValues.to(mutable.Map)
Podle benchmarků, kdy se vytvoří mapa s 10000 náhodnými Int klíči a pak jsou
všechny v náhodném pořadí vyhledány, je verze s mutable mapou 5x-6×
rychlejší.