15 - hash halmaz

Ebben a leckében egy funkcionális generikus hashsetet fogunk implementálni. Hogy ne kavarodjon a beépített HashSet-tel, a mienk HashHalmaz lesz.

• Egy HashHalmaz[T] objektum T típusú elemek halmazát tárolja.
• A hatékony kereshetőség céljából hashCode alapján szortírozza szét a tárolt objektumokat. (Ez a metódusa minden Scala objektumnak létezik, Intet ad vissza.)
• Belső adatszerkezete egy data: Vector[ Vector[T] ] adatmező, melynek a méretét most nevezzük size-nak.
• Ha egy value: T objektum hashkódja x, akkor az x Intnek a size-al való osztási maradéka határozza meg, hogy a data vektor hanyadik cellájában van a helye az elemnek. (Tehát például ha size=8 és x=21, akkor data(5)-ben a helye, ha x=-6, akkor data(2)-ben.)
• Támogatnunk kell a contains: T => Boolean metódust, ami miután kiszámolja, hogy a data vektor hanyadik cellájában kéne legyen az elem, az ott tárolt Vector[T]-ben keresi meg az elemet.
• Támogatnunk kell a removed: T => HashHalmaz[T] metódust, ami visszaad egy új adatszerkezetet, mely ugyanaz, mint az eredeti, azzal a különbséggel, hogy a kért elem ha benne volt, már nincs.
• Támogatnunk kell a inserted: T => HashHalmaz[T] metódust, ami visszaad egy új adatszerkezetet, mely ugyanaz, mint az eredeti, azzal a különbséggel, hogy a kért elem ha nem volt benne, akkor már igen.
• Támogatnunk kell az intelligens átskálázást: ha a data vektorban beszúrás után több, mint 3/4-e a celláknak tartalmaz nemüres vektort, akkor az inserted metódus által visszaadott HashHalmaz-ban a size legyen kétszer akkora, mint eredetileg volt (és így persze újra kell osztani az elemeket).
• Implementáljuk azt, hogy a HashHalmaz[T]() kifejezés egy üres hashhalmazt hozzon létre, size=8 mérettel.
• Implementáljuk azt, hogy a HashHalmaz[T](size: Int) kifejezés egy üres hashhalmazt hozzon létre, size mérettel.
• Támogassuk a foreach, map, flatMap, filter, foldLeft metódusokat a szokásos fejlécekkel és elvárt viselkedéssel.

osztály, companion object

A leírás szerint az osztály lényege a data adatmező, melyet nem akarunk láthatóvá tenni. Erre van lehetőség: a case class fejlécében bármelyik paramétert feltüntethetjük private valként, és ekkor létrehozáskor ugyan át kell adnunk ezt a paramétert is, de nem fogják tudni kódból elérni. Ezek alapján hogy kezdenénk bele az osztály implementálásába?

case class HashHalmaz[T]( private val data: Vector[Vector[T]] )

Ezek után tehát létrehozhatjuk a halmazt, de a `data` mezőjét közvetlenül elérni nem fogjuk:

val halmaz = HashHalmaz[Int]( Vector(Vector(), Vector() ) ) // ,,üres halmaz'', size = 2-vel

halmaz.data // NEM FORDUL

Válasz mutatása

Talán a következő könnyű feladat a két kért konstruktor megírása. Hogy tudjuk a kért funkciót támogatni?

Companion objectben implementált `apply` metódusokkal. Érdemes lehet megírni a számot kérő konstruktort (hogyan hozzunk létre `size` méretű vektort, melyben `Vector()`ok vannak?), majd a paraméter nélküli konstruktorból is ezt hívni megfelelő paraméterezéssel, hogy ne duplikáljuk a kódot.

Hint mutatása

Egy `size`-elemű `Vector` létrehozása történhet akár `foldLeft`tel: egy `Range` objektumon foldleftelünk, az aggregált típus `Vector[Vector[T]]` lesz, a művelet hozzáappendel a meglévő vektorhoz még egy üres `Vector[T]`-t, majd ha kész van az üres adatvektorunk, visszaadunk egy új HashHalmazt, ezzel az adatmezővel.

object HashHalmaz {
  def apply[T](): HashHalmaz[T] = apply[T](8)
  def apply[T](size: Int): HashHalmaz[T] = {
    val data = (1 to size).foldLeft( Vector[Vector[T]]() ) {
      (data, _) => data :+ Vector[T]()
    }
    HashHalmaz[T](data)
  }
}

Válasz mutatása

getIndex, contains

Privát metódusként implementáljuk a getIndexOf: T => Int függvényt, ami a kapott objektum hashkódja alapján visszaadja, hogy hanyadik cellába való az elem! Note: Scalában a negatívok maradékos osztásának maradéka negatív, pl. (-8) % 6 == -2.

Privát tagfüggvényként a case classban:

private def getIndexOf( value: T ): Int = {
  val base = value.hashCode() % data.size
  (base + data.size) % data.size
}

Az első modulo beteszi az értéket a `(-size..size)` (nyitott) intervallumba, így ha hozzáadunk `size`-t, az már garantáltan a `(0..2*size)` intervallumba esik, még egy modulo után megkapjuk a `[0..size)`-ba eső kért osztási maradékot.

Válasz mutatása

Ezt a metódust használva a contains: T => Boolean könnyen implementálható. Hogyan?

(Nem privát) tagfüggvényként a case classban:

def contains( value: T ): Boolean =
  data( getIndexOf(value ).contains( value )

A belső vektorban nyugodtan használhatjuk a `Vector` osztály `contains` metódusát.

Válasz mutatása

removed

Törlésnél - elkerülendő a felesleges másolásokat - ha eleve nem szerepelt az elem a halmazban, adjuk vissza a this objektumot változtatás nélkül! Ebben a feladatban talán hasznos metódusok a Vector osztályban:

• updated( pos: Int, value: T ): Vector[T] visszaad egy új vektort, mely annyiban különbözik az eredetitől, hogy pos pozíción értéke value
• dropRight( n: Int ): Vector[T]: visszaad egy új vektort, mely az eredetiből úgy készül, hogy jobbról levág n elemet
• indexOf( value: T ): Int visszaadja, hogy a vektornak value hanyadik eleme, vagy -1-et, ha nincs benne.

Próbáljuk meg a vektorból törlést hatékonyan megvalósítani.

Egy hatékony megvalósítás lehet az, ha a vektor **eredetileg utolsó elemét tesszük a törlendő elem pozíciójára**, majd levágjuk a jobb szélén álló egy elemet. Ezzel az új vektorral updateljük az eredeti datát és ezzel példányosítsuk a visszaadott új hashhalmazt.

Hint mutatása

Tagfüggvényként a case classban:

def removed( value: T ): HashHalmaz[T] = {
  val index = getIndexOf( value )  //index adja meg, hogy hanyadik ,,vödörben'' kell legyen az érték
  val smallVector = data( index )  //smallVector az ebben a vödörben lévő vektor
  val pos   = smallVector.indexOf( value )  //ebben megkeressük az elemet, pos a pozíciója
  if( pos == -1 ) this             //ha nincs benne, nem másolunk
  else {
    val oldLastValue = smallVector.last  //a vödörben lévő vektor eredetileg utolsó eleme
    val newSmallVector = smallVector.updated( pos, oldLastValue ).dropRight( 1 )  //updateljük: csere és levágás
    val newData = data.updated( index, newSmallVector )  //updateljük az adatot is
    HashHalmaz[T]( newData ) //és visszaadjuk az így készülő halmazt
  }
}

Válasz mutatása

insert, foldLeft

Beszúrásnál alapvetően működne a törléshez hasonló megközelítés, kivéve azt a részt, amikor is ki kell bővíteni duplájára a data vektor méretét. Ekkor készítenünk kell egy új üres hashhalmazt kétszer akkora méretben és hozzáadni egyesével a meglévő elemeket. Erre korábban a foldLeft metódust láttuk, és most is alkalmas lehet rá, ha implementálva lesz. Kezdjük tehát talán azzal!

A foldLeft[U] metódus kap egy U típusú kezdőértéket, és visszaad egy függvényt, mely kap egy (U,T)=>U függvényt, és visszaad egy U értéket. Próbáljuk meg megírni a függvény fejlécét úgy, hogy leforduljon!

A legolvashatóbb metódus fejléc talán ez:

def foldLeft[U](init: U)( op: (U,T) => U ): U = ???

Válasz mutatása

Implementáljuk is a foldLeftet mondjuk úgy, hogy a kezdeti értékből kiindulva minden, a datában tárolt vektorral szép sorban foldolunk!

Ez ismét talán egy tailrec belső függvénnyel lehet könnyen megoldható, mely úgy üzemel, mint egy for ciklus.

Hint mutatása

A legolvashatóbb metódus fejléc talán ez:

def foldLeft[U](init: U)( op: (U,T) => U ): U = {

  @tailrec
  def foldVec( i: Int, init: U ): U =
    if( i == data.size ) init
    else foldVec( i+1, data(i).foldLeft(init)(op) )

  foldVec(0, init)
}

Válasz mutatása

Ha már van foldLeftünk, írjuk meg az inserted fejlécét és felhasználva a (még nem megírt) insertedet, implementáljunk egy ++( that: HashHalmaz[T] ): HashHalmaz[T] metódust, ami visszaadj a két hashhalmaz unióját!

Az uniózást implementálhatjuk inserteddel való foldlefteléssel, kiindulva az aktuális halmazunkból.

Hint mutatása

def inserted(value: T): HashHalmaz[T] = ???

def ++(that: HashHalmaz[T]): HashHalmaz[T] =
  that.foldLeft(this)( (halmaz, elem) => halmaz.inserted(elem) )

Hint mutatása

Ezeket felhasználva már tudjuk implementálni az inserted metódust is. Hogyan?

Az uniózást implementálhatjuk inserteddel való foldlefteléssel, kiindulva az aktuális halmazunkból. Egy hasznos metódus lehet a load factor kiszámítására a `Vector` osztály `count( p: T=>Boolean ): Int` metódusa, mely visszaadja, hogy a vektornak hány olyan eleme van, melyre igaz a `p` predikátum.

Hint mutatása

def inserted(value: T): HashHalmaz[T] = {
  val index = getIndexOf(value)  //index: hanyadik bucketbe kell kerüljön az elem
  // ha már eleve ott van, akkor nincs változás
  if( data(index).contains(value)) this
  else{
    //különben beszúrjuk, updateljük datát
    val newSmallVector = data(index) :+ value
    val newData        = data.updated(index, newSmallVector)
    val newHashHalmaz = HashHalmaz[T]( newData )
    // hány bucket üres most?
    val countEmpty  = newData.count( _.isEmpty )
    if( countEmpty < newData.size / 4 ){ //túl kevés
      //készítünk egy új hashhalmazt kétszer akkora size-al és beleöntjük newHalmazt
      HashHalmaz[T]( data.size * 2 ) ++ newHashHalmaz
    }else{//ok, készítsünk egy új hashhalmazt ezzel az új adattal
      newHashHalmaz
    }
  }
}

Válasz mutatása

foreach, filter, map, flatMap

A foreach metódus a szokásos fejléccel menjen végig az összes belső vektoron sorban és mindegyikek minden elemén értékelje ki a kapott függvényt!

Használjunk egymásba ágyazott enumerátorokat.

Hint mutatása

def foreach[U]( f: T=>U ): Unit =
  for(
    smallVector <- data;
    value <- smallVector
  ) f(value)

Válasz mutatása

A filter( p: T=>Boolean ): HashHalmaz[T] metódust filterezett foldlefttel implementálhatjuk például, hiszen minden elem ugyanabban a vödörben maradhat, mint volt.

def filter( p: T=>Boolean ): HashHalmaz[T] = {
  val newData = data.foldLeft[Vector[Vector[T]]]( Vector() ) {
    (d, v) => d :+ v.filter(p)
  }
  HashHalmaz[T]( newData )
}

Válasz mutatása

A map metódusnál viszont már eleve a típus is lehet más, az értékek hashkódjának sincs köze az eredetiekhez, így egy teljesen új HashHalmazba érdemes egyesével beszúrni az elemeket -- foldLefttel, amit már úgyis implementáltunk.

def map[U]( f: T=>U ): HashHalmaz[U] = {
  foldLeft[HashHalmaz[U]]( HashHalmaz[U]() ){
    (ujHalmaz, eredetiElem) => ujHalmaz.inserted( f(eredetiElem) )
  }
}

Válasz mutatása

Végül a flatMap metódus csak annyiban kell különbözzön a maptől, hogy nem az összes f(eredetiElem) értéket kell egyesével beszúrnunk, hanem hozzá kell uniózzuk az eddig legyártott halmazhoz.

def flatMap[U]( f: T=>HashHalmaz[U] ): HashHalmaz[U] = {
  foldLeft[HashHalmaz[U]]( HashHalmaz[U]() ){
    (ujHalmaz, eredetiElem) => ujHalmaz ++ f(eredetiElem)
  }
}

Válasz mutatása

További feladatként teszteljük a kódunkat!

---

Utolsó frissítés: 2021-01-02 16:22:45