1. CS-A1110
  2. Kierros 9
  3. Luku 9.2: Pareja ja hakuja

Luku 9.2: Pareja ja hakuja

../_images/person02.png

Johdanto: kaksi paluuarvoa?

Usein kysytty kysymys

Voiko funktio palauttaa kaksi arvoa? Voitaisiinko vaikkapa määritellä funktio toMinsAndSecs, jolle annettaisiin sekuntimäärä ja joka palauttaisi kerralla kaksi kokonaislukua: kokonaiset minuutit ja yli jääneet sekunnit? Jotenkin näin:

toMinsAndSecs(187)res0: (Int, Int) = (3,7)

Funktiota kutsuessa voisi sitten esimerkiksi sijoittaa palautetut arvot muuttujiin nimeltä min ja s ja tehdä niillä jotakin.

Ratkaisuvaihtoehtoja

Varsinaisesti funktio ei voi palauttaa kuin yhden arvon, mutta tätä rajoitusta voi kiertää, joten tavallaan se sittenkin voi.

Yksi kiertotapa on palauttaa kaksialkioinen kokoelma, vaikkapa Vector[Int]-tyyppinen.

val palautettu = toMinsAndSecs(187)palautettu: Vector[Int] = Vector(3,7)
val min = palautettu(0)min: Int = 3
val s = palautettu(1)s: Int = 7

Tämä on siedettävä ratkaisu, joskaan Vector[Int]-tyyppi ei osuvasti kuvaa sitä, että palautettavia lukuja on aina tasan kaksi. Tämä vaihtoehto on myös epäkäytännöllinen tilanteissa, joissa halutaan palauttaa kaksi keskenään erityyppistä arvoa.

Toinen kiertotapa on laatia oma luokka, joka kuvaa palautettavien tietojen yhdistelmää. Voitaisiin esimerkiksi laatia luokka Time, jolla olisi muuttujat täysiä minuutteja ja ylijäämäsekunteja varten, ja hoitaa asia luomalla tällainen aikaolio. Tämä tapa on parhaimmillaan silloin, jos palautettava arvopari edustaa jotakin luokkana luontevasti mallintuvaa käsitettä.

Kolmas tapa hyödyntää pareja (pair). Tämä tapa on kätevä, ja sen oppimisesta on laajemminkin iloa. Tarkastellaan pareja ensin yleisesti ja palataan sitten minuutteihin ja sekunteihin.

Parit

Parien peruskäyttö Scalalla

Parin voi muodostaa käyttämällä sulkeita ja pilkkua, kuten tässä:

("reppu", "reissumies")res1: (String, String) = (reppu,reissumies)

Sulkeet löytyvät myös paluuarvon kuvauksesta. Merkintä (String, String) tarkoittaa, että siinä on sellainen pari, jossa on kaksi merkkijonoa.

Parista voi poimia jommankumman jäsenen tuttuun tyyliin:

var pari = ("reppu", "reissumies")pari: (String, String) = (reppu,reissumies)
pari(0)res2: String = reppu
pari(1)res3: String = reissumies

Merkittävä ero parin ja vaikkapa kaksialkioisen vektorin välillä on, että parin jäsenillä voi olla eri staattiset tyypit:

val nimiJaKengannumero = ("Juha", 43)nimiJaKengannumero: (String, Int) = (Juha,43)

Keskeinen ero on sekin, että parin koko on etukäteen tiedossa. Tämä yritys tuottaa käännösaikaisen virheilmoituksen eikä näin ollen voi kaataa ohjelmaa:

nimiJaKengannumero(2)-- Error:
  nimiJaKengannumero(2)
                    ^

Parin osat voi sijoittaa kahteen eri muuttujaan näin helposti, jälleen sulkeita käyttämällä:

val (nimi, kengannumero) = nimiJaKengannumeronimi: String = Juha
kengannumero: Int = 43

Pikkutehtävä: minuuteiksi ja sekunneiksi

Toteuta luvun alussa haviteltu funktio toMinsAndSecs sellaiseksi, että sitä voi käyttää näin:

toMinsAndSecs(187)res4: (Int, Int) = (3,7)
val (min, s) = toMinsAndSecs(200)min: Int = 3
s: Int = 20

Kirjoita ratkaisu Miscellaneous-moduulin kansion o1 tiedostoon misc.scala.

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Tämä on uusintaversio luvun 1.4 pikkukysymyksestä.

Olipa kerran muuttujat nimeltä hannu ja kerttu, jotka olivat keskenään samantyyppisiä. Tarkastellaan seuraavaa koodinpätkää:

val (hannu2, kerttu2) = (kerttu, hannu)

Mikä seuraavista väittämistä kuvaa parhaiten sitä, mitä muuttujien arvoille käy, kun muuttujat on ensin luotu ja alustettu joillakin arvoilla ja äskeinen koodirivi sitten suoritetaan?

Kokoelman jaottelu pariksi

Pareja on käytetty myös useassa Scala APIn valmiissa metodissa, mistä on alla pari esimerkkiä.

Kokoelmien metodi splitAt palauttaa parin, jonka jäseninä on kaksi kokoelmaa:

val lampotilat = Vector(3, 6, -1, -5, 3, -1, 2)lampotilat: Vector[Int] = Vector(3, 6, -1, -5, 3, -1, 2)
lampotilat.splitAt(3)res5: (Vector[Int], Vector[Int]) = (Vector(3, 6, -1),Vector(-5, 3, -1, 2))
val (arki, viikonloppu) = lampotilat.splitAt(5)arki: Vector[Int] = Vector(3, 6, -1, -5, 3)
viikonloppu: Vector[Int] = Vector(-1, 2)

splitAtille annetaan parametri, joka osoittaa sijainnin kokoelmassa.

Palautetun parin ensimmäisessä jäsenessä ovat kaikki alkuperäisen kokoelman alkiot osoitettua järjestysnumeroa edeltävät alkiot ja toisessa kaikki loput.

Myös metodi partition jaottelee alkuperäisen kokoelman alkiot kahteen kokoelmaan ja tuottaa parin, jossa on kaksi kokoelmaa:

val (pakkaset, lauhat) = lampotilat.partition( _ < 0 )pakkaset: Vector[Int] = Vector(-1, -5, -1)
lauhat: Vector[Int] = Vector(3, 6, 3, 2)

Kuten esimerkistä voi arvata, tämä metodi jakaa alkiot soveltamalla niihin parametriksi annettua funktiota ja katsomalla, tuottaako se true vai false.

Pikkutehtävä: kokoelman jaottelu

Moduulin Miscellaneous pakkauksesta o1.people löytyy yksittäisolio YoungAndOldApp. Tämän ohjelman toivottu toiminta on kuvattu sen ohjelmakoodin kommentissa. Täydennä ohjelma toiveiden mukaiseksi käyttäen äsken esiteltyä metodia.

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Kokoelmat vetoketjuina

Äsken parissa oli jäseninä kokoelmia. Kokoelmassa voi myös olla alkioina pareja.

Eräs näppärä kokoelmien metodi on zipWithIndex. Se tuottaa alkuperäisen kokoelman perusteella sellaisen kokoelman, joka sisältää pareja, joissa kussakin on alkio ja sen indeksi:

val lajit = Vector("laama", "alpakka", "vikunja")lajit: Vector[String] = Vector(laama, alpakka, vikunja)
lajit.zipWithIndexres6: Vector[(String, Int)] = Vector((laama,0), (alpakka,1), (vikunja,2))

Paluuarvona saadaan vektori, jossa on sisällä pareja, joissa on jäseninä merkkijono ja kokonaisluku kussakin.

Kun pareja sisältävän kokoelman voi käydä läpi for-silmukalla, voi suljemerkintää jälleen hyödyntää. Tässä kaksi tapaa tuottaa sama tuloste:

for pari <- lajit.zipWithIndex do
  println(pari(0) + " on numero " + pari(1))laama on numero 0
alpakka on numero 1
vikunja on numero 2
for (alkio, indeksi) <- lajit.zipWithIndex do
  println(alkio + " on numero " + indeksi)laama on numero 0
alpakka on numero 1
vikunja on numero 2

Metodi zipWithIndex on erikoistapaus yleisemmästä metodista zip, joka vetää yhteen kaksi kokoelmaa alkiopareittain:

val korkeudet = Vector(120, 90, 80)korkeudet: Vector[Int] = Vector(120, 90, 80)
val korkeudetJaLajit = korkeudet.zip(lajit)korkeudetJaLajit: Vector[(Int, String)] = Vector((120,laama), (90,alpakka), (80,vikunja))

Jos kokoelmat ovat eri mittaisia, jätetään pidemmästä loppuosa käyttämättä:

val iso = Vector("laama", "alpakka", "vikunja", "guanako", "wooly")iso: Vector[String] = Vector(laama, alpakka, vikunja, guanako, wooly)
val vainKolmeParia = korkeudet.zip(iso)vainKolmeParia: Vector[(Int, String)] = Vector((120,laama), (90,alpakka), (80,vikunja))

Vetoketjun voi myös avata:

korkeudetJaLajit.unzipres7: (Vector[Int], Vector[String]) = (Vector(120, 90, 80),Vector(laama, alpakka, vikunja))

Tässä siis syntyi pari, jonka jäsenet ovat vektoreita.

Pari funktion parametrina

Luonnollisesti voimme myös määritellä funktion, joka ottaa parametriksi parin. Tämä funktio palauttaa lukuparin erotuksen itseisarvon:

def absDiff(pairOfNumbers: (Int, Int)) =
  (pairOfNumbers(0) - pairOfNumbers(1)).abs

Käyttöesimerkki:

val kokeilu = (10, 30)kokeilu: (Int, Int) = (10,30)
absDiff(kokeilu)res8: Int = 20
absDiff((-300, 100))res9: Int = 400

Tämäkin toimii:

absDiff(-300, 100)res10: Int = 400

Tästä siis puuttuvat parin muodostavat lisäsulut ja kutsumme yksiparametrista absDiff-funktiota aivan kuin se ottaisi kaksi erillistä Int-parametria. Scala muodostaa kahdesta parametriarvostamme automaattisesti parin, ja tämä tekee saman kuin absDiff((-300, 100)).

Samansuuntaisella ajatuksella toimii seuraavakin:

Parit ja korkeamman asteen funktiot

Käytetään näitä edeltä tuttuja kokoelmia:

val lajit = Vector("laama", "alpakka", "vikunja")lajit: Vector[String] = Vector(laama, alpakka, vikunja)
val korkeudet = Vector(120, 90, 80)korkeudet: Vector[Int] = Vector(120, 90, 80)
val korkeudetJaLajit = korkeudet.zip(lajit)korkeudetJaLajit: Vector[(Int, String)] = Vector((120,laama), (90,alpakka), (80,vikunja))

Yksi tapa tulostaa raportti kustakin lajista on tämä:

def korkeusraportti(korkeusLajiPari: (Int, String)) =
  korkeusLajiPari(1) + " on " + korkeusLajiPari(0) + " cm"def korkeusraportti(korkeusLajiPari: (Int, String)): String
korkeudetJaLajit.map(korkeusraportti).foreach(println)laama on 120 cm
alpakka on 90 cm
vikunja on 80 cm

Koska kokoelma sisältää pareja, annamme map-metodille funktion, joka ottaa parametriksi yhden parin ja kertoo, mitä sillä tehdään.

Kuitenkin Scala antaa käyttää parin vastaanottavan funktion sijaan kaksiparametrista funktiota. Niinpä voimme kirjoittaa näinkin:

def korkeusraportti(cm: Int, laji: String) = s"$laji on $cm cm"def korkeusraportti(cm: Int, laji: String): String
korkeudetJaLajit.map(korkeusraportti).foreach(println)laama on 120 cm
alpakka on 90 cm
vikunja on 80 cm

Määrittelemme aivan tavallisen kaksiparametrisen funktion, joka ottaa luvun ja merkkijonon.

Sen voi antaa parametriksi myös pareja sisältävän kokoelman map-metodille. Scala huolehtii siitä, että kaksiparametrista funktiotamme kutsutaan kokoelman kunkin parin jäsenille.

Tehtävä: onko kokoelma järjestyksessä?

Laadi funktio isAscending, jolle annetaan parametriksi vektorillinen kokonaislukuja ja joka kertoo, ovatko luvut nousevassa järjestyksessä. Tässä esimerkkejä:

isAscending(Vector(-10, 1, 5, 10))res11: Boolean = true
isAscending(Vector(-10, 1, 5, 5, 10))res12: Boolean = true
isAscending(Vector(-10, 1, 5, 9, 5, 10))res13: Boolean = false
isAscending(Vector(10, 5, 1, -10))res14: Boolean = false

Metodin ei sovi tehdä lisätyötä järjestämällä alkiot. Sen pitää ainoastaan tarkistaa, ovatko alkiot järjestyksessä.

Hyödynnä tässä ja aiemmissa luvuissa opittuja kokoelmametodeita ovelasti, niin metodin rungoksi riittää yksi lyhyt rivi.

Kirjoita koodi jälleen tiedostoon misc.scala moduulissa Miscellaneous.

Voit olettaa, että vektorissa on ainakin yksi alkio.

Tarkempi vinkki hyödyllisistä metodeista

Metodit zip, tail ja forall ovat käyttökelpoisia. (Vaihtoehtoisesti voit kokeilla toteuttaa funktion sliding-metodin avulla. Se esiteltiin luvun 7.1 drySpell-tehtävän yhteydessä.)

forall-metodilla voi katsoa, päteekö kaikille peräkkäisten alkioiden pareille, että ne ovat keskenään oikeassa järjestyksessä. Apufunktion, joka välität forallille voit itse määritellä joko nimetyksi funktioksi tai nimettömäksi funktioliteraaliksi.

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Parit ovat monikkoja

Pari on erikoistapaus monikon (tuple) käsitteestä. Monikossa voi olla useampiakin jäseniä kuin kaksi:

("Tässä monikossa on neljä erilaista jäsentä.", 100, 3.14159, false)res15: (String, Int, Double, Boolean) = (Tässä monikossa on neljä erilaista jäsentä.,100,3.14159,false)

Onko monikko siis kokoelma samassa mielessä kuin puskurit ja vektorit? Ei ihan.

Monikot ja kokoelmat eroavat toisistaan jo käyttötarkoituksessaan. Monikot ovat edukseen lähinnä silloin, kun 1) jäseniä on pieni vakiomäärä (esim. vain kaksi) ja 2) kullakin jäsenellä on oma erillinen merkityksensä (esim. yksi on minuutit, toinen sekunnit; yksi on nimi, toinen kengännumero), mutta 3) erillisen luokan laatiminen tuntuu silti tarkoitukseen nähden liialliselta.

Tässä keskeisimpiä teknisiä eroja monikoiden ja kokoelmien välillä:

  • Monikossa kunkin jäsenen staattinen tyyppi määritellään erikseen, kokoelmassa kaikille alkioille yhteisesti.

  • Monikot ovat muuttumattomia kooltaan ja sisällöltään, kokoelmia on sekä muuttuvatilaisia että muuttumattomia.

  • Monikoilla ei ole kokoelmien metodeita (size, map, indexOf, tms.) eikä monikkoa voi käydä läpi esimerkiksi for-silmukalla (ilman kommervenkkejä).

Monikot ja tapausluokat

Luvun 4.4 vapaaehtoisessa materiaalissa esiteltiin lyhyesti Scalan tapausluokat (case class). Tapausluokat voi nähdä tiettyyn tarkoitukseen erikoistuneina monikkoina. Lisää tapausluokista kerrotaan keväisellä Ohjelmointistudio 2 -kurssilla.

Hyödyllinen ja yleinen käyttötarkoitus monikoille ja nimenomaan pareille löytyy hakurakenteista. Siitä kohta lisää.

Toinen johdanto: avaimia ja arvoja

Miten toteuttaisit seuraavat? Mitä yhteistä niillä on?

  • Sanakirja: halutaan etsiä annettua suomenkielistä sanaa vastaava englanninkielinen sana.

  • Opiskelijahakemisto: halutaan valita opiskelijaolio opiskelijanumeron perusteella.

  • Osoitekirja: halutaan, että henkilön nimen perusteella voi löytää henkilö- ja yhteystietoja kuvaavan olion.

  • Tietosanakirja: halutaan, että tietyn hakusanamerkkijonon kautta pääsee käsiksi tiettyyn artikkeliolioon.

  • Esiintymälaskuri: on olemassa olioita, joilla on tietty ominaisuus, ja halutaan laskea kuinka yleisiä tuon ominaisuuden eri arvot ovat olioiden joukossa.

    • Esim. luvussa 1.6 esitelty teema: on joukko elokuvia listalta, kullakin elokuvalla on ohjaaj(i)a ja halutaan laskea kunkin ohjaajan yleisyys listalla.

Tutuillakin työkaluilla tuo on ratkaistavissa. Tehdään vaikkapa alkeellinen sanakirja puskureilla:

val hakusanoja = Buffer("kissa", "laama", "tapiiri", "koira")hakusanoja: Buffer[String] = ArrayBuffer(kissa, laama, tapiiri, koira)
val englanniksi = Buffer("cat", "llama", "tapir", "puppy")englanniksi: Buffer[String] = ArrayBuffer(cat, llama, tapir, puppy)

Näiden kahden puskurin perusteella voimme hakea sanakirjasta (muista indexOf-metodi luvusta 4.2):

val indeksi = hakusanoja.indexOf("tapiiri")indeksi: Int = 2
englanniksi(indeksi)res16: String = tapir
englanniksi(hakusanoja.indexOf("koira"))res17: String = puppy

Voimme myös päivittää sanakirjaa vaihtamalla puskurin alkion toiseksi:

englanniksi(hakusanoja.indexOf("koira")) = "dog"englanniksi(hakusanoja.indexOf("koira"))res18: String = dog

Mietitään vielä esimerkkimme luonnetta. Sanakirjassa on suomenkielisiä sanoja, joiden perusteella haetaan englanninkielisiä vastineita. Voidaan sanoa: suomenkieliset sanat toimivat avaimina (key), joiden perusteella haetaan englanniksi-puskurin sisältämiä arvoja (value).

Sama perusajatus toistuu muissakin yllä luetelluissa tilanteissa: avaimina on opiskelijanumeroita, arvoina opiskelijaolioita; avaimina on ohjaajien nimiä, arvoina heidän elokuviensa lukumääriä; jne. Alla käytämme sanoja "avain" ja "arvo" tässä merkityksessä.

Puskuriratkaisumme perustuu ajatukseen, että puskurien sisältö on tietyssä järjestyksessä ja avainten indeksit (hakusanoja-puskurissa) ovat samat kuin niitä vastaavien arvojen (englanniksi-puskurissa). Haluttu toiminnallisuus saadaan kyllä toteutettua näinkin, mutta ratkaisussamme on useita haittapuolia.

Ensinnäkin käytimme erillisiä puskureita avaimille ja arvoille, vaikka miellämme sanakirjan yhdeksi kokonaisuudeksi.

Lisäksi indekseillä räplääminen tuntuu vähän turhalta välivaiheelta. Eihän ketään varsinaisesti tässä kiinnosta, monentenako tietty arvo tai avain puskurissa on.

Kolmanneksi: mitä jos avainta ei löydy? Esim.

englanniksi(hakusanoja.indexOf("insulintialainen kummitussirkka"))

Tällöin indexOf palauttaa -1, ja negatiivisen luvun käyttö englanniksi-puskuriin indeksinä aiheuttaa ajonaikaisen virhetilanteen. Ohjelmassa pitäisi siis aina muistaa tutkia esimerkiksi if-käskyllä, onko indeksi negatiivinen vai ei. Näin tarjotaan ohjelmointivirheille mahdollisuus siitä, vaikka ehkäisymenetelmiäkin olisi käytettävissä.

(Ja neljänneksi: Tehokkuudessakin on parantamisen varaa. indexOf-metodi käy puskurin indeksejä läpi järjestyksessä yksitellen, kunnes haettu alkio löytyy. Tämä ei ole lainkaan optimaalista.)

Hakurakenteet

Käytetään siis sellaista kokoelmaa, johon tallennetaan sekä avaimet että arvot. Hakurakenne (map) on erittäin yleisesti käytetty ja kätevä kokoelmatyyppi, joka poikkeaa tähän mennessä kurssilla käsitellyistä indekseihin perustuvista kokoelmista kuten puskureista.

Hakurakenne sisältää avain–arvo-pareja (key–value pairs). Toisin kuin esimerkiksi puskurissa, joissa arvojen hakeminen perustuu järjestysnumeroihin, hakurakenteesta arvoja poimitaan avaimien perusteella.

Avainarvoina voi käyttää mitä tahansa olioita. Ne muodostavat joukon (set) sanan matemaattisessa mielessä, mikä käytännössä tarkoittaa, että avainten on oltava erilaiset: ei kahta samaa suomenkielistä hakusanaa, ei kahta samaa opiskelijanumeroa, jne.

Scalassa hakurakenteita kuvaa luokka nimeltä Map.

Seis! maphän on kokoelmien metodi eikä eräänlainen alkiokokoelma?

Juurihan aiemmissa luvuissa on käytetty metodia nimeltä map? Kyllä vain. Ihan sattumasta ei nimeämisessä ole kyse muttei samastakaan asiasta.

Tuttu kokoelmien metodi map synnyttää olemassa olevan kokoelman perusteella toisen kokoelman. map-metodin parametrifunktio kuvaa riippuvuuden alkuperäisten alkioiden ja tulosalkioiden välillä.

Hakurakenne — Scalassa Map-olio — kokoaa yhteen avaimia ja arvoja. Se pitää tallessa näiden välisiä riippuvuuksia.

map-metodi on (myös) ihan muilla kokoelmilla kuin hakurakenteilla.

Ensin: avain–arvo-parit

Avain–arvo-parit ovat Scalassa ihan tavallisia pareja. Sellaisen voi muodostaa vaikkapa näin:

("koira", "dog")res19: (String, String) = (koira,dog)

On kuitenkin tapana käyttää toista merkintätapaa, joka korostaa sitä, että avain "osoittaa" arvoon. Seuraava käsky tuottaa tismalleen saman lopputuloksen kuin edellinen:

"koira" -> "dog"res20: (String, String) = (koira,dog)

Nuolta -> käytetään parin määrittelemiseen.

Sen vasemmalle puolelle kirjoitetaan avain ja oikealle puolelle se arvo, johon kyseinen avain osoittaa.

Tulos on pari toisiinsa liittyvää tietoa.

Minkä tahansa parin voi luoda kummalla tahansa tavalla. Hakurakenteiden avain–arvo -pareja luodessamme mekin tulemme käyttämään nuolimerkintää.

Sekä avaimena että arvona voi käyttää mitä vain Scala-oliota. Yllä sekä avain että arvo olivat merkkijonoja, kuten sanakirjallemme on sopivaa. Tarvittaessa voi myös vaikkapa panna avaimeksi luvun ja arvoksi merkkijonon tai toisinpäin:

233524 -> "Terhi Teekkari"res21: (Int, String) = (233524,Terhi Teekkari)
"Sergio Leone" -> 5res22: (String, Int) = (Sergio Leone,5)
../_images/p%C3%A4%C3%A4kirjoitus.png

Scalaa vai sumeria?

Huomaathan, että näissä pareissa käytetty nuoli on -> eikä =>, jota olemme käyttäneet parametrien tyypeissä ja case-sanan perässä.

Nyt alkaa jo mennä nuolet vähän sekaisin.

Lisää nuolesta

-> on ihan tavallinen metodi.

"seikkailija" -> "adventurer"res23: (String, String) = (seikkailija,adventurer)

Kohdeolio, jolle metodia kutsutaan.

Viivalla ja väkäsellä nimetty metodi on tarjolla kaikille Scala-olioille. Tässä on käytetty operaattorinotaatiota (luku 5.2), jossa ei ole pistettä kohdeolion ja metodin nimen välissä.

Jälkimmäinen merkkijono on metodin parametri. Operaattorinotaatiossa sen ympäriltä voi jättää sulkeet pois.

Metodi palauttaa parin, joka muodostuu kohdeoliosta ja parametrioliosta.

Pistenotaatiotakin voisi käyttää. Seuraavat kaksi tekevät ihan saman:

"polvi".->("knee")res24: (String, String) = (polvi,knee)
"polvi" -> "knee"res25: (String, String) = (polvi,knee)

Koska kyseessä on "nuoli", on operaattorinotaatio ymmärrettävästi tässä yhteydessä paljon yleisempi.

Hakurakenteet Scalalla: Map-luokka

Map-luokan avulla äskeinen pieni suomi–englanti-sanakirja toteutuu mutkattomasti. Poimitaan ensinnäkin se Map-luokka, jota haluamme nyt käyttää:

import scala.collection.mutable.Map

Muista: oliot voivat olla muuttuvatilaisia (mutable) tai muuttumattomia (immutable). Koska Scala-kieli tukee erilaisia ohjelmointityylejä, niin sen peruskirjastoissa on kaksi eri Map-luokkaa, joista toinen kuvaa muuttuvia hakurakenteita ja toinen muuttumattomia. Tällä kurssilla käytämme varsinkin nyt aluksi muuttuvia hakurakenteita (ts. hakurakenneoliota voi muuttaa sen luomisen jälkeen). Niitä kuvaava luokka löytyy pakkauksesta scala.collection.mutable, ja se on erikseen otettava käyttöön import-käskyllä, kuten yllä tehtiin ja kuten olemme tehneet saman pakkauksen Buffer-luokan kanssa.

Luodaan Map-olio:

val suomestaEnglanniksi = Map("kissa" -> "cat", "laama" -> "llama", "tapiiri" -> "tapir", "koira" -> "puppy")suomestaEnglanniksi: Map[String,String] = Map(koira -> puppy, tapiiri -> tapir, kissa -> cat, laama -> llama)

Erona tutunlaisiin kokoelmatyyppeihin on se, että hakurakenteen alkiot ovat aina avain–arvo-pareja.

Hakurakenteella on kaksi tyyppiparametria: avainten tyyppi ja arvojen tyyppi. Tässä olemme luoneet hakurakenteen, jossa sekä avaimet että arvot ovat merkkijonoja.

REPLin tulosteestakin huomaa, että kyseessä ei ole indeksoitu rakenne. Alkiot ovat hakurakenteessa mielivaltaisen näköisessä järjestyksessä. Niillä ei ole järjestysnumeroita. Se, missä järjestyksessä hakurakenneolio pitää sisältönsä, riippuu sen sisäisestä toteutuksesta eikä ole tässä yhteydessä oleellista.

Seuraavissa esimerkeissä näet valikoiman Map-olioiden metodeita. Tälläkään kertaa oleellista ei ole opetella niitä kaikkia ulkoa, vaan se, että saat yleiskuvan tästä kokoelmatyypistä.

Seuraavaa lukiessasi huomaat myös, että hakurakenteilla on monta toisilleen vaihtoehtoista metodia, ja samaan tarpeeseen voi löytyä erilaisia ratkaisuja. Heti aluksi tuskin syntyy käsitystä siitä, mikä metodeista on milloinkin paras, mutta ei tarvitsekaan; tilanne paranee kokemuksen kasvaessa. On silti hyvä pystyä jo tunnistamaan erilaisia ratkaisuja.

Arvon hakeminen

Hakurakenteesta on helppo hakea arvo avaimen perusteella:

suomestaEnglanniksi.get("kissa")res26: Option[String] = Some(cat)
suomestaEnglanniksi.get("insulintialainen kummitussirkka")res27: Option[String] = None

get-metodille annetaan parametriksi se avain, jota vastaava arvo halutaan hakea.

get-metodilta saadaan Option[ArvojenTyyppi]-tyyppinen paluuarvo.

Jos haettu avain oli kokoelmassa, saadaan sitä vastaava arvo Some-kääreessä. Jos taas ei, saadaan None.

Arvon vaihtaminen

Kun kyseessä on muuttuvatilainen hakurakenne, voi sanakirjaa päivittää tähän tapaan:

suomestaEnglanniksi.get("koira")res28: Option[String] = Some(puppy)
suomestaEnglanniksi("koira") = "dog"suomestaEnglanniksi.get("koira")res29: Option[String] = Some(dog)

Muista: Hakurakenteen avaimet ovat kaikki erilaisia. Hakurakenteeseen ei voi kuulua useita avain–arvo-pareja, joissa on sama avain. Yllä siis korvataan pari "koira" -> "puppy" parilla "koira" -> "dog".

Avain–arvo-parin lisäys

On olemassa useita tapoja lisätä uusi avain–arvo-pari hakurakenteeseen. Yksi tapa on käyttää samanlaista käskyä kuin yllä ja yksinkertaisesti sijoittaa arvo sellaiselle avaimelle, joka ei aiemmin ollut käytössä:

suomestaEnglanniksi("hiiri") = "mouse"

Toinen tapa lisätä tai vaihtaa uusi avain–arvo-pari on käyttää +=-operaattoria samaan tapaan kuin olet jo tottunut tekemään puskureille. Tällöin operaattorin oikealle puolelle kirjoitetaan lisättävä pari:

suomestaEnglanniksi += "sika" -> "pig"res30: Map[String, String] = Map(koira -> dog, tapiiri -> tapir, kissa -> cat, sika -> pig, hiiri -> mouse,
laama -> llama)

Tuo käsky korvaa vanhan avain–arvo-parin, jos avain on jo käytössä.

Kurssimateriaalissa käytetään jatkossa enimmäkseen tätä jälkimmäistä tapaa. Itse voit käyttää kumpaa vain.

Avain–arvo-parin poistaminen

Poistaminen onnistuu esimerkiksi näin:

suomestaEnglanniksi -= "laama"res31: Map[String, String] = Map(koira -> dog, tapiiri -> tapir, kissa -> cat, sika -> pig, hiiri -> mouse)

Saman olisi voinut tehdä myös remove-metodilla, joka palauttaa poistamansa arvon Option-kääreessä:

suomestaEnglanniksi.remove("laama")res32: Option[String] = Some(llama)

Löytyykö avainta?

contains-metodilla voi tutkia, onko tietty avain käytössä:

suomestaEnglanniksi.contains("tapiiri")res33: Boolean = true
suomestaEnglanniksi.contains("laama")res34: Boolean = false

Esimerkkitapauksessamme "tapiiri" löytyy sanakirjasta, kun taas "laama" jo poistettiin eikä löydy enää.

Entä löytyykö sanakirjasta tällä tavoin esimerkiksi sana "tapir"? Eli etsiikö contains paitsi avainten myös arvojen joukosta? Kokeile.

Kaikki avaimet tai kaikki arvot

Metodeilla keys ja values saa selville kaikki hakurakenteen avaimet tai arvot. Metodien paluuarvot ovat alkiokokoelmia, joita voi käsitellä tutuilla metodeilla. Esimerkiksi tässä tulostetaan ensin kukin avaimista ja sitten kukin arvoista:

suomestaEnglanniksi.keys.foreach(println)koira
tapiiri
kissa
sika
hiiri
suomestaEnglanniksi.values.foreach(println)dog
tapir
cat
pig
mouse

Tuttuja metodeita hakurakenteillakin

Hakurakenteilla on suuri joukko muista kokoelmista tuttuja metodeita. Tässä muutama esimerkki lukujen 4.2 ja 6.3 esittelemistä kokoelmametodeista:

val englanniksi = Map("kissa" -> "cat", "tapiiri" -> "tapir", "koira" -> "dog")englanniksi: Map[String,String] = Map(koira -> dog, tapiiri -> tapir, kissa -> cat)
englanniksi.isEmptyres35: Boolean = false
englanniksi.sizeres36: Int = 3
englanniksi.foreach(println)(koira,dog)
(tapiiri,tapir)
(kissa,cat)

Erityismaininnan ansaitsee map-metodi, jolla voi käsitellä hakurakenteen sisältämiä avain–arvo-pareja ja näin muodostaa uuden hakurakenteen:

val kokeiluMap = englanniksi.map( finEngPari => finEngPari(0).toUpperCase -> (finEngPari(1) + "!!!") )kokeiluMap: Map[String,String] = Map(KISSA -> cat!!!, TAPIIRI -> tapir!!!, KOIRA -> dog!!!)

Käytämme metodia map (pienellä) hakurakenteeseen, joka on tyyppiä Map (isolla).

Koska hakurakenteen alkiot ovat pareja, niin map-metodille välitetään parametriksi parin käsittelemiseen sopiva funktio.

Esimerkkifunktiomme muodostaa uuden parin, jossa on alkuperäisen parin ensimmäisen jäsenen (eli suomenkielisen avaimen) isokirjaiminen versio sekä toisen jäsenen (eli englanninkielisen arvon) huutomerkeillä täydennetty versio.

Näistä uusista pareista muodostuu uusi hakurakenne, jossa avaimien perusteella voi hakea huutomerkillisiä merkkijonoja.

Äskeisen voi kirjoittaa kauniimmin ja selkeämmin. Hyödynnetään aiemmin tässä luvussa mainittua tietoa siitä, että Scala sallii meidän käyttää kaksiparametrista funktiota sellaisessa kohdassa, johon kelpaisi yhden parin parametrikseen ottava funktio. Siis näin:

val kokeiluMap = englanniksi.map( (fin, eng) => fin.toUpperCase -> (eng + "!!!") )kokeiluMap: Map[String,String] = Map(KISSA -> cat!!!, TAPIIRI -> tapir!!!, KOIRA -> dog!!!)

Käytämmekin kaksiparametrista funktioliteraalia, jonka parametrit on helppo nimetä kuvaavasti. Indeksejä emme tarvitse.

Usein halutaan muodostaa uusi hakurakenne, jossa avaimet ovat entiset mutta arvot erilaiset kuin alkuperäisessä. Muodostetaan kokeeksi hakurakenne, josta voi hakea avaimen perusteella englanninnoksen pituuden:

val kaannospituudet = englanniksi.map( (fin, eng) => fin -> eng.length )kaannospituudet: Map[String,Int] = Map(kissa -> 3, tapiiri -> 5, koira -> 3)

Välitämme map-metodille funktion, joka jättää avain–arvoparin ensimmäisen jäsenen ennalleen.

Hakurakenteen kääntämisestä

Joskus kysyttyä: miten saadaan muodostettua hakurakenne, jossa on alkuperäisen rakenteet avaimet arvoina ja arvot avaimina?

Yksinkertaisessa tapauksessa tuo onnistuu kätevästi, kun hyödynnämme parien swap-metodia, joka toimii näin:

val pari = "avain" -> "arvo"pari: (String, String) = (avain,arvo)
pari.swapres37: (String, String) = (arvo,avain)

Sama koko hakurakenteelle:

val suomestaEnglanniksi = Map("kissa" -> "cat", "koira" -> "dog", "laama" -> "llama")suomestaEnglanniksi: Map[String,String] = Map(kissa -> cat, koira -> dog, laama -> llama)
val englannistaSuomeksi = suomestaEnglanniksi.map( _.swap )englannistaSuomeksi: Map[String,String] = Map(cat -> kissa, dog -> koira, llama -> laama)

Sovelletaan swap-metodia kuhunkin avain–arvo-pariin.

Tässä pitää olla tarkkana. Jos sama englanninnos olisi esiintynyt useita kertoja, olisimme menettäneet suunnankäännöksessä informaatiota, koska avaimien on oltava ainutlaatuisia. (Kokeile.)

Jos haluat, että samaa avainta vastaa useita arvoja, käytä arvona kokoelmaa, jossa ovat tallessa kaikki tiettyä avainta vastaavat arvot. Tässä voi myös olla apua erityistyökaluista (hae netistä: scala multidict).

Mitä jos haettu avain puuttuu?

Hakurakenteita käytettäessä on usein huomioitava erikseen sellaiset tilanteet, joissa rakenteesta haetaan avainta, mutta sitä ei löydykään. Scalan kirjastot tukevat tällaisten tilanteiden käsittelyä useilla toisilleen vaihtoehtoisilla tavoilla, jotka on hyvä tuntea.

Tuttua yltä on jo se, että get-metodi on Option-paluuarvoinen ja palauttaa None, kun avainta ei löydy:

englanniksi.get("kummitussirkka")res38: String = None

Monesti onkin hyvä ratkaisu kutsua get-metodia ja käyttää sen palauttamaa Option-oliota. Mutta on myös tilanteita, joissa tämä ei ole näppärin vaihtoehto.

getOrElse-metodi

getOrElse-metodi tarjoaa tavan käsitellä puuttuvia tietoja. Se muistuttaa luvusta 4.3 tuttua Option-olioiden samannimistä metodia. Siinä missä Option-oliolle sanottiin "anna sisältösi tai sen puuttuessa käytä tätä arvoa", niin hakurakenteelle sanotaan "anna tätä avainta vastaava arvo tai sen puuttuessa käytä tätä arvoa".

englanniksi.getOrElse("kissa", "tuntematon hakusana")res39: String = cat
englanniksi.getOrElse("kummitussirkka", "tuntematon hakusana")res40: String = tuntematon hakusana

getOrElse-metodille annetaan parametriksi haettava avain sekä "vara-arvo", jonka on syytä olla samaa tyyppiä kuin hakurakenteen arvot.

Jos avain löytyy hakurakenteesta, getOrElse-palauttaa sitä vastaavan arvon.

Jos avainta ei löydy, metodi palauttaa toisen parametrinsa.

Metodin paluuarvo on String eikä Option[String]. Option-käärettä ei tarvita, koska kummassakin tapauksessa pystytään tuottamaan mielekäs String-tyyppinen paluuarvo. Kätevää!

apply-oletusmetodi (ja sen vaarat)

Olet jo tottunut katsomaan indeksoidun kokoelman alkion käskyllä kokoelma(indeksi), jonka luku 5.3 kertoi lyhennysmerkinnäksi metodikutsulle kokoelma.apply(indeksi). apply on siis eräänlainen "olion oletusmetodi", jonka nimeä ei ole pakko kutsuessa erikseen kirjoittaa.

Myös hakurakenteilla on apply-metodi. Se toimii samansuuntaisesti kuin get, mutta oleellinen erokin näillä metodeilla on. Vertaillaan:

val englanniksi = Map("kissa" -> "cat", "tapiiri" -> "tapir", "koira" -> "dog")englanniksi: Map[String,String] = Map(koira -> dog, tapiiri -> tapir, kissa -> cat)
englanniksi("tapiiri")res41: String = tapir
englanniksi("kummitussirkka")java.util.NoSuchElementException: key not found: kummitussirkka
   ...
   at scala.collection.mutable.HashMap.apply(HashMap.scala:64)
   ...
englanniksi.get("kissa")res42: Option[String] = Some(cat)
englanniksi.get("kummitussirkka")res43: Option[String] = None

apply-metodin hyvänä puolena verrattuna getiin on se, että arvon löytyessä saadaan tuo arvo suoraan ilman Option-käärettä, jolloin paluuarvon käyttö on pykälän verran kätevämpää. Kuitenkin apply-metodi siis tuottaa ajonaikaisen virhetilanteen, jos sille annetaan parametriksi olematon avain, ja siksi sitä käyttäessä pitää olla valppaana.

Yleensä get on turvallisempi ja parempi vaihtoehto.

get — hyvä vai huono?

Onko siis tosiaan niin, että hakurakenteiden get-nimistä metodia on usein syytä suosia? Vaikka Option-olioiden samannimistä metodia on syytä kaihtaa (ks. lukujen 4.4 ja 8.3 vapaaehtoinen lukemisto)?

On.

Pikkutehtävä: get, apply ja getOrElse

Arvioi, mitkä seuraavista väitteistä pitävät paikkansa, kun on luotu hakurakenneolio ja siihen viittaava muuttuja näin:

val scrabble = Map('A'->10, 'I'->10, 'N'->9, 'S'->7, 'T'->9, 'E'->8, 'K'->5, 'L'->5, 'O'->5,
                   'Ä'->5,  'U'->4,  'M'->3, 'H'->2, 'J'->2, 'P'->2, 'R'->2, 'U'->2, 'Y'->2)

Hakurakenne luokan ilmentymämuuttujassa

Kuten muitakin kokoelmia myös hakurakennetta voi tietysti käyttää oman luokan rakennusosana. Alla on yksi alkeellinen esimerkki tästä, ja muita esimerkkejä on tulossa myöhemmissä luvuissa.

Jäsenesimerkki

Otetaan taas käyttöön yhteisöjen jäseniä kuvaava luokka Member (luvusta 4.4). Sen koodi on oleellisin osin toistettu tässä.

class Member(val id: Int, val name: String, val yearOfBirth: Int, val yearOfDeath: Option[Int]):
  // Jne.

Laaditaan kokeeksi yhteisöä kuvaava luokka Society, jossa käytämme hakurakennetta ilmentymämuuttujan kautta.

class Society(val name: String):

  private val members = Map[Int, Member]()

  def add(newMember: Member) =
    this.members(newMember.id) = newMember

  def getByID(memberID: Int) = this.members.get(memberID)

end Society

Yhteisöoliolla on ominaisuuksina paitsi nimi myös hakurakenne, johon tallennetaan jäsenolioita, jäsennumeroita avaimina käyttäen. Kun yhteisöolio luodaan, tämä hakurakenne on vielä tyhjä.

Yhteisöoliolla on metodeita, joilla siihen voi lisätä jäseniä ja joilla sen jäsenkuntaa voi tutkia. Näiden toteutuksessa käytetään apuna Map-olion metodeita.

Pikkutehtävä: hakurakenteet ja Option

Lisää Miscellaneous-moduulista löytyvään Society-luokkaan metodi yearOfDeath, joka toimii näin:

  • Sille annetaan parametriksi jäsennumero.

  • Se palauttaa Option[Int]-tyyppisen arvon, johon on kääritty sen jäsenen kuolinvuosi, jolla on annettu jäsennumero.

  • Jos kuolinvuotta ei ole, koska kyseistä jäsentä ei ole tai hän on elossa, palautetaan None.

Älä tee muita muutoksia Society-luokkaan äläkä muuta Member-luokkaa.

Kutsu erästä aiemmista luvuista tuttua kokoelmien metodia, niin tehtävän ratkaisu on pitkälti siinä.

A+ esittää tässä kohdassa tehtävän palautuslomakkeen.

Lisäluettavaa

Hakurakenteen "vara-arvo"

Vaikka getOrElse-metodi on sinänsä kätevä, on melko tyypillistä, että sen toiseksi parametriksi annetaan tietylle hakurakenteelle aina sama "vara-arvo". Sanakirjaesimerkissämme voitaisiin vaikkapa haluta tuottaa teksti "ähäkutti" aina, jos rakenteesta haetaan olemattomalla avaimella.

Voit välttyä välittämästä samaa parametriarvoa toistuvasti getOrElse-metodille käyttämällä withDefaultValue-metodia. Tätä metodia käytetään yleensä juuri luodulle hakurakenteelle, kuten tässä:

val englanniksi = Map("kissa" -> "cat", "tapiiri" -> "tapir", "koira" -> "dog").withDefaultValue("ähäkutti")englanniksi: Map[String,String] = Map(koira -> dog, tapiiri -> tapir, kissa -> cat)
englanniksi("kissa")res44: String = cat
englanniksi("kummitussirkka")res45: String = ähäkutti

withDefaultValue-metodille ilmoitetaan, mitä haluamme käyttää "vara-arvona" silloin, kun haku on huti.

Nyt kun haemme apply-metodilla olematonta avainta, samme tämän vara-arvon.

Luodaan scrabble kuten aiemmassa tehtävässä ja lisäksi scrabble2 kuten alla:

val scrabble = Map('A'->10, 'I'->10, 'N'->9, 'S'->7, 'T'->9, 'E'->8, 'K'->5, 'L'->5, 'O'->5,
                   'Ä'->5,  'U'->4,  'M'->3, 'H'->2, 'J'->2, 'P'->2, 'R'->2, 'U'->2, 'Y'->2)
val scrabble2 = scrabble.withDefaultValue(1)

Mikä on HashMap?

Tuolla ylempänä esiintyi virheilmoituksessa luokan nimi HashMap. Sana hash ei tässä liity sosiaaliseen mediaan tai muihinkaan ajanvietteisiin vaan erääseen hakurakenteiden toteutustekniikkaan.

Scala APIn Map on abstrakteja metodeita sisältävä piirreluokka, joka kuvaa hakurakenteiden toimintoja yleisesti määrittelemättä sisäisesti käytettävää toteutustapaa. HashMap on konkreettinen luokka, joka toteuttaa Map-piirreluokan abstraktit metodit käyttäen hajautukseksi (hashing) kutsuttua toteutustapaa. Luomamme hakurakenne on siis sekä yleisempää tyyppiä Map että sen alatyyppiä HashMap.

Tämän luvun johdannossa mainittiin ohimennen, että kahteen puskuriin perustuva sanakirjatoteutus ei ollut kovin tehokas, koska indeksejä käytiin läpi järjestyksessä yksi kerrallaan ja mikä tahansa avain–arvo-pari voi löytyä mistä tahansa puskurien kohdasta. Hajautustoteutus on tyypillisissä käyttötilanteissa tehokkaampi, koska siinä avain–arvo-parit sijoitellaan hakurakenteeseen harkitusti avaimen perusteella.

Hajautusta ei käsitellä tällä kurssilla, kuten ei tehokkuuden lisäämiseen tarkoitettuja algoritmeja yleensäkään, mutta voit lukea lisää vaikkapa Wikipediasta tai käydä Aallon kurssin Tietorakenteet ja algoritmit.

Yhteenvetoa

  • Useita tietoja, keskenään erityyppisiäkin, voi koota yhteen monikoksi. Pari on kaksipaikkainen monikko.

  • Hakurakenne on erittäin yleisesti käytetty kokoelmatyyppi. Se sisältää avain–arvo-pareja ja poikkeaa indekseihin perustuvista kokoelmista muun muassa siten, että:

    • alkioilla ei ole vastaavaa numerojärjestystä

    • eikä alkioita poimita järjestysnumeron (indeksin) perusteella, vaan

    • useimmiten annetaan avain ja poimitaan sitä vastaava arvo.

  • Scalassa hakurakenteita kuvaa luokka Map, jolla on runsaasti hyödyllisiä metodeita.

  • Lukuun liittyviä termejä sanastosivulla: monikko, pari; hakurakenne, avain–arvo-pari.

Palaute

Huomaathan, että tämä on henkilökohtainen osio! Vaikka olisit tehnyt lukuun liittyvät tehtävät parin kanssa, täytä palautelomake itse.

Tekijät

Tämän oppimateriaalin kehitystyössä on käytetty apuna tuhansilta opiskelijoilta kerättyä palautetta. Kiitos!

Materiaalin luvut tehtävineen ja viikkokoosteineen on laatinut Juha Sorva.

Liitesivut (sanasto, Scala-kooste, usein kysytyt kysymykset jne.) on kirjoittanut Juha Sorva sikäli kuin sivulla ei ole toisin mainittu.

Tehtävien automaattisen arvioinnin ovat toteuttaneet: (aakkosjärjestyksessä) Riku Autio, Nikolas Drosdek, Kaisa Ek, Joonatan Honkamaa, Antti Immonen, Jaakko Kantojärvi, Onni Komulainen, Niklas Kröger, Kalle Laitinen, Teemu Lehtinen, Mikael Lenander, Ilona Ma, Jaakko Nakaza, Strasdosky Otewa, Timi Seppälä, Teemu Sirkiä, Joel Toppinen, Anna Valldeoriola Cardó ja Aleksi Vartiainen.

Lukujen alkuja koristavat kuvat ja muut vastaavat kuvituskuvat on piirtänyt Christina Lassheikki.

Yksityiskohtaiset animaatiot Scala-ohjelmien suorituksen vaiheista suunnittelivat Juha Sorva ja Teemu Sirkiä. Teemu Sirkiä ja Riku Autio toteuttivat ne apunaan Teemun aiemmin rakentamat työkalut Jsvee ja Kelmu.

Muut diagrammit ja materiaaliin upotetut vuorovaikutteiset esitykset laati Juha Sorva.

O1Library-ohjelmakirjaston ovat kehittäneet Aleksi Lukkarinen, Juha Sorva ja Jaakko Nakaza. Useat sen keskeisistä osista tukeutuvat Aleksin SMCL-kirjastoon.

Tapa, jolla käytämme O1Libraryn työkaluja (kuten Pic) yksinkertaiseen graafiseen ohjelmointiin, on saanut vaikutteita tekijöiden Flatt, Felleisen, Findler ja Krishnamurthi oppikirjasta How to Design Programs sekä Stephen Blochin oppikirjasta Picturing Programs.

Oppimisalusta A+ luotiin alun perin Aallon LeTech-tutkimusryhmässä pitkälti opiskelijavoimin. Nykyään tätä avoimen lähdekoodin projektia kehittää Tietotekniikan laitoksen opetusteknologiatiimi ja tarjoaa palveluna laitoksen IT-tuki; sitä ovat kehittäneet kymmenet Aallon opiskelijat ja muut.

A+ Courses -lisäosa, joka tukee A+:aa ja O1-kurssia IntelliJ-ohjelmointiympäristössä, on toinen avoin projekti. Sen suunnitteluun ja toteutukseen on osallistunut useita opiskelijoita yhteistyössä O1-kurssin opettajien kanssa.

Kurssin tämänhetkinen henkilökunta löytyy luvusta 1.1.

Joidenkin lukujen lopuissa on lukukohtaisia lisäyksiä tähän tekijäluetteloon.

a drop of ink
Palautusta lähetetään...