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!

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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:

1
2
3
4
5
6
  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, 3ra 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 flattent, 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