24 - a Vector monád¶

A funkcionális paradigmában a(z egyirányú, immutable láncolt) lista egy alapvető adatszerkezet. Performance megfontolásból azonban mindenképp érdemes megismernünk más adatszerkezeteket is, az egyik ilyen, mely szintén elemek egy immutable szekvenciáját tárolja, a Vector lesz.

a problémák a Listtel¶

Lássuk először a megoldandó kérdéseket a listával:

Egy listában nincs hatékony direkt címzés: ha az n-edik elemet akarjuk lekérni, akkor a lista fejétől el kell szaladnunk n lépésen keresztül a megfelelő elemhez. Ez lassú tud lenni.
Egy immutable listában a módosítás nagyon nem hatékony. Mit is jelent ez? Mivel a lista immutable, így egy olyen updated(i: Int, value: T): List[T] metódust keresünk, ami visszaad egy olyan új listát, mely ugyanaz, mint az eredeti, azzal az egy különbséggel, hogy a lista i. elemét felváltja a value elem.

Implementáljuk ezt a metódust a saját MyList adatszerkezetünkön!

trait MyList[T] {
  def updated(i: Int, value: T): List[T]
}
case class MyNil[T]() extends MyList[T] {
  override def updated(i: Int, value: T) = ??? //nincs mit updatelni, dobjunk inkább hibát
}
case class MyCons[T](head: T, tail: MyList[T]) extends MyList[T] {
  override def updated(i: Int, value: T) = i match {
    case 0 => MyCons(value,tail)                     //a 0. elemet, azaz a headet updateltük
    case _ => MyCons(head, tail.updated(i-1,value) ) //különben a tail i-1. elemét update és rá a headet
  }
}

Válasz mutatása

Mi ezzel a gond? Ha például a listánk az (1,4,2,8,5,7) lista, akkor ez így van a memóriában:

1
2
3

Cons --> Cons --> Cons --> Cons --> Cons --> Cons --> Nil
  |        |        |        |        |        |
  1        4        2        8        5        7

(lefelé a head, jobbra a tail mező)

Ha ezen hívjuk az updated(3,6) metódust, akkor a memóriában hogy fog kinézni az új listánk?

Cons --> Cons --> Cons --> Cons   
  |        |        |        |   \
  1        4        2        6    \
                                   V
Cons --> Cons --> Cons --> Cons --> Cons --> Cons --> Nil
  |        |        |        |        |        |
  1        4        2        8        5        7

Válasz mutatása

Nem csak hogy az elért indexszel arányosan sok lépést teszünk meg az updated metódus hívásakor, de még ráadásul attól a ponttól kezdve visszafelé fel is építjük az egész listát, hiába változatlan!

Ez egyrészt sokáig tart, másrészt ha amúgy már máshol nincs szükségünk az eredeti listára, akkor ugyan idővel erre rájön a JVM és felszabadítja a memóriát, de elég nagy méretű memóriát foglalunk pluszban, ha hosszú lista vége felé módosítunk.

A Listen nem igazán tudunk párhuzamos számításokat végezni: érzi az ember, hogy például egy map-szerű metódust egy tömbön egyszerűen tudnánk párhuzamosítani, minden core egyszerre egy tömbelemet helyettesítene be a mappelő függvénybe; a listában viszont ahhoz, hogy elérjék az elemeket, követniük kell a linkeket.
prepend függvénye lehet, de az append függvénnyel hasonlóak a problémák, mint az updated metódussal: újra kell hozzá másolni az egész listát.

a Vector¶

A Vector osztály ezeket a hiányosságokat küszöböli ki:

van direkt access: apply(index: Int): T metódus a Vector[T]-ben visszaadja az i. indexen lévő elemet (mint egy C vagy Java tömbben, 0-tól indexel sorfolytonosan, ez a direkt access ,,gyors'' (nem annyira, mint a tömbcímzés, de majdnem)
van updated(index: Int, value: T): Vector[T] metódusa, ami ,,gyorsan'' updateli a megfelelő indexen lévő elemet - ez is immutable, tehát egy új Vectort kapunk vissza, de sokkal kevesebb adatot másol hozzá pluszban le, mint ami a listánál történik
van append, prepend

és

ez is monád

használata¶

A listában is szereplő műveletei megegyeznek azéval, nem kell beimportolnunk semmit, mert ő is le van type aliasolva a Predef objektumban, teljes neve scala.collections.immutable.Vector:

val vec  = Vector[Int]()            //üres új int vektort hoz létre
val vec2 = Vector(1, 4, 2, 8, 5, 7) //ez egy hatelemű vektor
println(vec2)                       //prints Vector(1, 4, 2, 8, 5, 7)

println(vec2(3))                    //prints 8: az apply metódus az indexet várja
println(vec2(6))                    //dob egy java.lang.ArrayIndexOutOfBoundsException-t

val vec3 = vec2 :+ 9                //append
println(vec3)                       //prints Vector(1, 4, 2, 8, 5, 7, 9)

val vec4 = vec2.updated(1,9)        //megváltoztat
println(vec4)                       //prints Vector(1, 9, 2, 8, 5, 7)

val vec5 = 7 +: vec2                //prepend
println(vec5)                       //prints Vector(7, 1, 4, 2, 8, 5, 7)

println( vec2.flatMap( x => Vector(x,x,x) ) ) //prints Vector(1, 1, 1, 4, 4, 4, 2, 2, 2, 8, 8, 8, 5, 5, 5, 7, 7, 7)
println( vec2.filter { _%3 == 2 } )  //prints Vector(2, 8, 5)

Emlékeztetőül az appendhez és a prependhez: ha a metódus neve :-ra végződik, akkor amennyiben nem tesszük ki a pontot, úgy balról ragad az objektumhoz, így a 7 +: vec2 kifejezés a vec2.+:(7) kifejezéssel egyenértékű.

felépítése a memóriában¶

Nem szerves része a kurzusnak az, hogy pl pont Scalában valamelyik adatszerkezezet hogyan van felépítve, de azért pár szó arról, hogy hogy néz ki ez az adatszerkezet:

alapvetően amíg a Vector mérete 32 vagy kevesebb, addig ez egy tömb lesz, konstans időben eléri az elemeit, az updated metódus lemásolja az egész tömböt
ha több, mint 32 eleme van, akkor egy fa struktúrában kezdi tárolni az elemeit: a fa gyökerében 32 darab referencia lesz egy tömbben, mindegyik referencia egy 32-elemű tömbre fog mutatni, így összesen 32 * 32 = 1024 elem tárolható egy ilyen kétszintes fában
ha pl. ebben a 100. elemet akarjuk elérni, akkor a 100/32=3 azt mondja, hogy a 3. referenciát kell követnünk a tömbben (a nulladik tárolja a 0..31, az első a 32..63, a második a 64..95 és a harmadik a 96..127. elemeket), majd ha oda leléptünk, akkor ott a 100 % 32=4 azt mondja, hogy ebben a tömbben a 4. indexen lesz a keresett elem, így ha nem is konstans időben, de gyorsan elérjük
ha pl. updateljük a 100. elemet, akkor csak az őt ténylegesen tároló 32-elemű tömb csomópontot kell lemásoljuk megváltoztatva a memóriában, és a gyökeret (mivel az tárol egy új mutatót), de ez csak 2 * 32 = 64 elem másolása akkor is, ha a Vector már 1000 elemet tárol
ha eléri az 1024 helyet, akkor újra növeli eggyel a szintet, a felső két szinten 32-elemű, referenciákat tároló tömbök lesznek, alul pedig a tényleges adatok, ez már 32.768 méretig elég, és bárkit 3 csomóponton keresztül elérünk, maximum 3*32 méretű tömböt kell update-nél duplikálnunk
négy szint már egymillió elemre, hat szint már egymilliárd elemre elég
nem teljesen így néz ki, hogy a prepend és az append is hatékony lehessen, tárol egy "offset"et is, hogy valójában hanyadik elemtől is kezdődik a tényleges adat

Alapvetően ha immutable sorozatot szeretnénk tárolni, a Listnél kb minden tekintetben jobb választás lesz real-life scenarióban a Vector.

Általában ha n elemet tárolunk a Vectorban, akkor hány szintes fánk lesz?

`log_32(n)`, azaz 32-es alapú logaritmusát kell venni az elemszámnak (és felfele kerekíteni)

Válasz mutatása

for comprehension több monáddal¶

Vajon mi lesz a for( x <- list; y <- vec ) yield x*y kifejezés értéke (ha lefordul egyáltalán), ha list=List(1,2,3) és vec=Vector(1,5)? És a for( x <- vec; y <- list ) yield x*y értéke?

Hát próbáljuk ki:

  val list = List(1,2,3)
  val vec = Vector(1,5)
  val result1 = for( x <- list; y <- vec ) yield x*y
  val result2 = for( x <- vec; y <- list ) yield x*y
  println(result1) //prints List(1, 5, 2, 10, 3, 15)
  println(result2) //prints Vector(1, 2, 3, 5, 10, 15)

Nem csak az elemek sorrendje (ez megváltozott volna akkor is, ha mindkettő `List` - gondoljuk át, hogy miért?), de a konténerosztály **típusa** is más a két esetben. De legalább lefordul; kicsit kényelmetlenebb lenne a konténerosztályok használata, ha egy for comprehensionben mindig csak ugyanannak az osztálynak a flatMapjét fejtené ki a fordító. Nézzük mondjuk az első eredményt! Ezt a for yield comprehensiont a következőre konvertálja a compiler:

1	`list.flatMap( x => { vec.map( { y => x*y } ) } )`

Amit, ha a flatMapet egy mapet követő flattenként modellezünk (note: ez nem minden monádnál fog működni, ha különböző típusú enumerátoraink lesznek), akkor először is vesszük a **lista** mindhárom elemét `x`-nek, és mindegyikre kiértékeljük a `vec.map({ y => x*y})` kifejezést. Ez a lista első elemére, `1`-re `vec.map( { y => 1*y })` lesz, azaz ennek az értéke `Vector(1,5)`. A második elemére, `2`-re `vec.map( { y => 2*y} )` lesz, azaz ennek az értéke `Vector(2,10)`. A harmadik elemére, `3`ra pedig `vec.map( { y => 3*y } )` lesz, ami `Vector(3,15)`. Ezt a három értéket egy **listába** rakjuk, hiszen a `List` osztály flatMapjét hívtuk, eddig tehát amink van:

1	`List(Vector(1,5),Vector(2,10),Vector(3,15))`

Ezen hívjuk a `flatten`t, ami **értelmezve van** így is (ez annak köszönhető, hogy a `List` is és a `Vector` is leszármazik az `IterableOnce` osztályból, és abban van implementálva a `flatMap`), és az eredménye: a **külső** konténer alaptípusába lesz sorban hozzáadva először az első alkonténer összes eleme, majd a másodiké, és így tovább. Az eredmény: `List(1,5,2,10,3,15)`. A másik esetben a `Vector` lesz a külső konténer és a sorrend is persze más lesz.

Válasz mutatása

Mindenesetre, az látszik, hogy az a rész, hogy két különböző osztályból hogy is lesz egy eredménye a flatMapnek, az nemtriviális, és nem mindig van jóldefiniálva vagy megvalósítva: minél több monádot (vagy legalábbis flatMap metódussal rendelkező osztályt) fogunk ismerni, annál többször futhatunk bele abba, hogy nem minden enumerátor-kombináció fog lefordulni. Szerencsére a built-in osztályok közt vannak konverziós metódusok: a Vector és a List is rendelkezik toVector és toList metódusokkal, amik a másik konténerosztálynak megfelelő adatszerkezetbe rakják át az adatot, ez persze lineáris ideig eltart.

Utolsó frissítés: 2020-12-24 20:55:43