0xDEADBEEF

RSS odkazy english edition
««« »»»

Scala: dočasné mutable a immutable mapy

14. 1. 2020

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-6x rychlejší.

píše k47 (@kaja47, k47)