0xDEADBEEF

[RSS]
««« »»»

Scala: dočasné mutable a immutable mapy

14. 1. 2020

V pro­gra­mech jsou často vy­tvá­řeny do­časné mapy pro efek­tivní hle­dání v čase O(1). Jsou zcela lo­kální, po­u­žité pouze v jedné metodě a dál nijak sdí­lené. Ve Scale to může vy­pa­dat nějak takhle:

entities.collect { case e if e.something => (e.id, e) }.toMap

Vý­sled­kem je mapa, kterou můžu použít pro hle­dání podle ur­či­tého klíče. Metoda toMap vyrobí ne­měn­nou (im­mu­table) mapu. Pokud si dobře vzpo­mí­nám, toto cho­vání pů­vodně nebylo za­ru­čeno. Kon­trakt sli­bo­val jen, že vý­sled­kem bude nějaká mapa, ne­spe­ci­fi­ko­váno zdali ne­měnná nebo mě­ni­telná. Ve verzi 2.13 (a nej­spíš i ně­ko­lik verzí nazpět) metoda vždy vrací scala.collection.immutable.Map.

Ne­měnné mapy jsou in­terně im­ple­men­to­vané s pomocí trie – pre­fi­xo­vého stromu do nějž se in­de­xuje hashem klíče. Od verze 2.13 stan­dardní knihovna po­u­žívá efek­tivní CHAMP im­ple­men­taci. Jde o po­měrně kom­pli­ko­va­nou struk­turu, která mí ně­ko­lik úrovní, po­tře­buje mnoho alo­kací a na­há­nění poin­terů. Na­proti tomu mě­ni­telná mapa je oby­čejná ha­sh­ta­bulka po­sta­vená na jednom poli a spo­jo­vých se­zna­mech kolizí. Ta­ko­vou mapu je mnohem snad­nější vy­tvo­řit.

Proto v ur­či­tých pří­pa­dech může být efek­tiv­nější zmi­ňo­vané do­časné mapy vy­tvá­řet jako mě­ni­telné. Ne­před­sta­vuje to pro­blém, pro­tože jsou zcela lo­kální a nikdo kromě metody, kde vznik­nou a za­nik­nou, je ne­u­vidí.

Ve Scale je i na tohle one­li­ner:

keyValues.to(mutable.Map)

Podle ben­chmarků, kdy se vy­tvoří mapa s 10000 ná­hod­nými Int klíči a pak jsou všechny v ná­hod­ném pořadí vy­hle­dány, je verze s mu­table mapou 5x-6x rych­lejší.

píše k47 (@kaja47, k47)