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:

1
2
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?

1
2
3
4
5
6
7
8
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:

1
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:

1
2
3
4
5
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:

1
2
3
4
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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

1
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