27 - a Map kollekció

A Map adatszerkezet szintén egy kollekció: kulcs-érték párokat tárolhatunk benne. Minden kulcshoz legfeljebb egy érték tartozhat. Más programozási nyelvekben hívják dictionarynak vagy asszociatív tömbnek is.

inicializálás, lekérdezés

Ha úgy vesszük, a Vector is egy Map, melyben a kulcsok Intek, mégpedig 0-tól sorfolytonosan indexelt intekhez tartozik érték egy korlátig. A Map ebből annyiban tud többet, hogy generikus kulcsban is, értékben is: Map[K,V], két generikus paramétere van, K adja a kulcs, V adja az érték típusát.

Az osztály használatára példa, ha mondjuk a use case az, hogy karakterekből számoljuk, melyikből mennyi van egy szövegben:

val counts: Map[Char, Int] = Map( 'a' -> 7, 'b' -> 8, 'c' -> 10, 'a' -> 9 )
println( counts ) //prints Map(a -> 9, b -> 8, c -> 10)

Mit tanultunk ebből a kódból?

• Inicializálásnál kulcs -> érték párok sorozataként megadhatjuk a Mapet
• Az a kulcshoz tartozó második beszúrás felülírta az elsőt: egy kulcshoz csak egy érték tartozhat
• Nem kellett importolnunk: a scala.collection.immutable.Map a Predef Map.

Ha már elkészítettünk egy Mapet, akkor vannak lekérdező műveleteink, amik kulcs alapján adnak vissza értéket, de abban eltérnek, hogy hogyan viselkednek, ha az adott kulcshoz nincs érték a Mapben:

• get( key: K ): Option[V] egy Optiont ad vissza: ha van (key,value) pár ebben a Mapben, akkor Some(value) az eredmény, ha a kulcs nem szerepel a Mapben, akkor None.
• apply( key: K ): V ha szerepel a key kulcs a Mapben, akkor viszaadja a hozzá tartozó értéket; ha nem, akkor dob egy NoSuchElementExceptiont
• getOrElse( key: K, defaultValue: =>V ): V hasonlóan az Option ilyen nevű metódusához, ha szerepel a key kulcs a Mapben, akkor visszaadja a hozzá tartozó értéket; ha nem, akkor kiértékeli a név szerint átadott defaultValue argumentumot és visszaadja azt
• contains( key: K ): Boolean igazat ad, ha a key kulcs szerepel a Mapben.

Mik lesznek a fenti counts Map esetén tehát az alábbi értékek?

counts.get('a')
counts.get('d')
counts('a')
counts('d')
counts.getOrElse('a', 0)
counts.getOrElse('d', 0)
counts.contains('a')
counts.contains('d')

Nézzük csoportonként: * Mivel `a` szerepel a Mapben és utolsóként `9`-cel updateltük inicializáláskor, `counts.get('a') == Some(9)`, `counts('a') == 9`, `counts.getOrElse('a',0) == 9` és persze `counts.contains('a') == true`. * Mivel `d` nem szerepel a Mapben, `counts.get('d') == None`, `counts('d')` kivételt dob, `counts.getOrElse('d',0) == 0` és `counts.contains('d') == false`.

Válasz mutatása

Meg tudjuk kapni a getOrElse metódust másképp?

A `get` által visszaadott `Option` ugyanilyen nevű függvényével:

Map.getOrElse( key, value ) == Map.get( key ).getOrElse( value )

Persze használjuk a `Map.getOrElse` metódust inkább, azért van.

Válasz mutatása

funkcionális módosítás

Immutable kollekcióról lévén szó, itt is igaz, hogy nem mutátor metódusok vannak, hanem egy új Mapet kapunk vissza a következők kiértékelésekor:

• updated( key: K, value: V ): Map[K,V] - ha a key kulccsal még nem szerepel érték, akkor beszúrjuk ezzel a kulccsal a value értéket; ha már szerepel benne, akkor a régi értéket kicseréljük a value-re.
• removed( key: K ): Map[K,V] - a visszaadott Map ugyanaz, mint az eredeti, azzal, hogy ha volt benne a key kulccsal érték, az újban már nem lesz.
• ++( that: Map[K,V]): Map[K,V] - a that Mapben szereplő (key,value) párokat beszúrja az eredeti Mapbe, szintén funkcionálisan.

Igaz-e, hogy map1 ++ map2 == map2 ++ map1 minden map1, map2 Mapre?

Nem, ha egy kulcs **mindkét** Mapben szerepel, akkor az összegben a **jobb oldali** Map adja az értéket:

val counts  = Map( 'b' -> 8, 'a' -> 7,  'c' -> 10, 'a' -> 9 )
val counts2 = Map('a' -> 7, 'd' -> 3)

println( counts ++ counts2 ) //Map(b -> 8, a -> 7, c -> 10, d -> 3)
println( counts2 ++ counts ) //Map(a -> 9, d -> 3, b -> 8, c -> 10)

Látszik, hogy az `a` kulcshoz az első esetben a `counts2`-beli `7` érték, a másodikban a `counts`-beli `9` érték tartozik.

Válasz mutatása

Olyan értelemben számít ,,kollekciónak'', mintha egy (K,V) pár típusú értékeket tároló kollekció lenne (mint pl. egy Set[(K,V)], azzal, hogy nem csak hogy egyenlő párokból, de egyenlő kulcsú párokból sem lehet több: mintha ezeknek a pároknak az == metódusa konkrétan a kulcsok közti egyenlőséget adná vissza.) Ezen az alapon már nem meglepő a flatMap and co. szignatúrája:

• flatMap[K2,V2]( f: ((K,V)) => Map[K2, V2]): Map[K2,V2]. Ez a metódus az összes (key,value) párra a Mapben kiszámolja f((key,value))-t, ami egy-egy Map[K2,V2] lesz, majd ezeket a kapott Mapeket össze ++-olja. A sorrend nem specifikált alapértelmezésben, tehát ha van átfedés a készített Mapek kulcskészletében, akkor bármelyikükből jöhet a végérték!

Miért van dupla zárójel az f-nél a K,V pár körül?

Ha azt írnánk, hogy `(K,V) => Map[K2,V2]`, az azt jelentené, hogy `f` egy **kétváltozós** függvény, az első paraméterének típusa `K`, második paraméterének pedig `V`. De **nem erről van szó**: `f` egy **egyváltozós** függvény kell legyen, egyetlen paraméterének típusa pedig egy `(K,V)` **tuple** kell legyen.

Válasz mutatása

• filter( p: ((K,V)) => Boolean ): Map[K,V] szintén minden egyes (key,value) párra vonatkozó predikátumot kap, nem csak a kulcsra vagy csak az értékre vonatkozót
• map[K2,V2]( f: ((K,V)) => (K2,V2) ): Map[K2,V2] minden egyes (key,value) entryből készít egy (key2,value2) entryt és ezekből az entrykből állít össze egy Mapet. Itt is igaz: ha van átfedés a készített entryk kulcsai közt, csak az egyik jelenik majd meg az eredményben!
• foreach[U]( f: ((K,V)) => U ): Unit is az elvárt működést hozza, minden entryn kiértékeli az f-et vélhetően mellékhatás végett.

a Map egyben K => V függvény is

Ha tehát egy metódus egy f: K => V függvényt vár paraméterben, akkor nyugodtan odaadhatunk neki egy Map[K,V]-t, el fogja fogadni, lefordul:

val counts = Map( 'b' -> 8, 'a' -> 7,  'c' -> 10 )

val hop = "abbabaca"
println( hop.map( counts ) ) //ArraySeq(7, 8, 8, 7, 8, 7, 10, 7)

Miért lehet ez?

Mert a `Map[K,V]` extendeli a `PartialFunction[K,V]` traitet. Ehhez végül is csak az `apply(key: K): V` metódust (és az `isDefinedAt(key: K): Boolean` metódust) kell implementálnia, amit meg is tesz.

Válasz mutatása

TODO gyakorlat: input stringben számoljunk karaktereket Mapbe! Huffman kódoljunk

TODO gyakorlat: vector[Int], Int: maradékosztályonként szedjük szét az input vektor elemeit. felkészül: groupBy

nem mind monád, ami flatMap

A Map nem monád, mert (mainly az azonos kulcsok kezeléséből származó információvesztés végett) nem teljesíti az asszociativitási axiómát: Hogy egy axióma nem teljesül, ahhoz elég egy ellenpéldát adnunk, vagyis egy m Mapet, egy f és egy g flatmapni alkalmas függvényt, melyekre nem jön ki egyenlőre a két oldal:

val m = Map( 1 -> 1, 2 -> 2 )

def f : ((Int,Int)) => Map[Int,Int] = {
  entry => Map(entry._1 -> entry._2, (entry._1+1) -> entry._2 )
}

def g: ((Int,Int)) => Map[Int,Int] = {
  entry => Map( (entry._1 + entry._2) -> entry._2 )
}

println( m.flatMap(f).flatMap(g) )                  //Map(2 -> 1, 4 -> 2, 5 -> 2)
println( m.flatMap( entry => f(entry).flatMap(g) )) //Map(2 -> 1, 3 -> 1, 4 -> 2, 5 -> 2)

Látjuk: ezzel a fenti m, f és g függvényekkel a két eredmény egész más, pl. az alsóban szerepel a 3-as kulcs, a felsőben meg nem.

Próbáljuk meg végigszámolni, hogy miért!

Lássuk előbb `m.flatMap(f).flatMap(g)`-t: * Az `f` metódus az `(1,1)` entryből készíti a `Map( 1->1, 2->1 )`-et (emlékszünk: a `_1` a tuple első koordinátája, azaz most a kulcs, a `_2` pedig a második, azaz most az érték). * A `(2,2)` entryből készíti a `Map( 2->2, 3->2 )` Mapet. * Ezeket egy Mapbe olvasztja **és itt veszít adatot**, mivel a `2`-es kulcshoz mindkét Mapben tartozik érték. Most valószínűleg, ha ilyen sorrendben járta be és vonja egybe a Mapeket, így a `Map( 1->1, 2->2, 3->2 )` Mapet kapjuk mint `m.flatMap(f)`-et. * Ezen jön a `flatMap(g)` hívás, ami az `(1,1)` entryből (érték marad, új kulcs a kulcs és az érték összege lesz, ez az egy elem lesz az új Mapben) készíti a `Map( 2->1 )`-et, `(2,2)`-ből `Map( 4->2 )`, `(3,2)`-ből pedig `Map( 5->2 )` lesz, ezek összeadásából lesz a `Map( 2->1, 4->2, 5->2 )` eredmény. * A másik oldal kiértékeléséhez: előbb az `(1,1)`-ből lesz (ismét) a `Map( 1->1, 2->1 )`, de most előbb ezen `flatMap(g)`-zünk: `(1,1)`-ből kapjuk `Map( 2->1 )`-et, `(2,1)`-ből `Map( 3->1 )`-et, egybevonva `(1,1)` képe `Map( 2->1, 3->1 )` lesz. * A `(2,2)` entryn az alsó kifejezés belső függvénye először (ismét) a `Map( 2->2, 3->2 )` Mapet, ezen a `flatMap(g)` pedig a `Map( 4->2, 5->2 )` mapet készíti. * Az alsó kifejezés tehát a két elkészült Map összege, ami `Map( 2->1, 3->1, 4->2, 5->2 )`. Nem ugyanaz tehát a két eredmény, ezért **a Map nem monád**.

Válasz mutatása

ha a kulcsok rendezhetők, lehet SortedMap is

Nagyon hasonló a Map underlying implementációja a Setéhez: elvégre, a kulcsokat valamiféle halmazban tárolja. Hasonlóan a Set esetéhez, itt is van SortedMapünk: ha beimportoljuk

import scala.collection.immutable.SortedMap

például az immutable csomagból (ahonnan minden mást is szerzünk), akkor csak annyit kell tennünk, hogy Map helyett SortedMappel példányosítunk, ekkor a bejárás sorrendje garantáltan a kulcsok rendezése szerinti lesz.

A műveletek időigényéről itt is ugyanaz mondható el, mint a Set esetében: a rendezetlen Map átlagos viselkedése konstans időigény lesz a lekérdezés és egy elem hozzáadása-elvétele műveletek esetén, ez kicsit megnőve logaritmikus lesz (nem 32-es alapú logaritmus, mint a Vectornál, hanem kettes alapú: tény, a kettő közt csak egy ötös szorzó van, tehát azért nem egy extrém nagy időigény ez), ha rendezett Mapot használunk.

---

Utolsó frissítés: 2020-12-25 19:16:06