Akkumulaattorimallit
Siirtäkää tilaa rekursion läpi.
Akkumulaattorimallit on ilmainen Scala backend-kehitykseen ja funktionaaliseen ohjelmointiin-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Scala backend-kehitykseen ja funktionaaliseen ohjelmointiin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Scala backend-kehitykseen ja funktionaaliseen ohjelmointiin-kurssilla on yhteensä 4 oppituntia.
Miksi akkumulointia käytetään
Tavallinen rekursio rakentaa tuloksen kutsupinoa palatessaan sen jälkeen, kun rekursiivinen kutsu on palautunut.
Akkumulaattori kuljettaa kertyvää tulosta sen sijaan jokaiselle kutsulle alaspäin, joten tulos on valmis, kun perustapaus saavutetaan.
Tämä pieni muutos mahdollistaa häntärekursion ja vakion suuruisen pinon käytön.
Apufunktio
Akkumulaattorimallissa käytetään sisäistä apufunktiota, joka ottaa ylimääräisen parametrin: tähän mennessä kertyneen tuloksen.
Ulkoinen funktio vain käynnistää sen alkuarvolla, joka on usein 0 tai tyhjä lista.
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}Akkumulaattorin suoritus
Tässä kokonainen ohjelma laskee listan summan akkumulaattorin avulla.
Huomaa, että perustapaus palauttaa acc-arvon suoraan, ei arvoa 0. Kokonaissumma on kertynyt, kun etenimme listassa alaspäin.
def sum(xs: List[Int]): Int = {
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}
@main def run(): Unit =
println(sum(List(1, 2, 3, 4))) // 10Kahden rakenteen vertailu
Tavallisessa rekursiossa yhdistämisvaihe (h + ...) odottaa sisemmän kutsun valmistumista.
Akkumulaattoriversiossa yhdistäminen tehdään ennen kutsua, ja kutsu on funktion viimeinen toiminto.
Juuri tämä viimeisen kutsun ominaisuus tekee siitä häntärekursiivisen.
// Plain: combine after the call
case h :: t => h + sum(t)
// Accumulator: combine before the call
case h :: t => loop(t, acc + h)Häntärekursio
Häntärekursiivinen kutsu on kutsu, jossa rekursiivinen kutsu on funktion viimeinen toiminto eikä sen jälkeen jää mitään tehtävää.
Scala voi optimoida tämän silmukaksi ja käyttää uudelleen yhtä pinokehystä, joten pino ei ylity syvyydestä riippumatta.
import scala.annotation.tailrec
@tailrec
def countDown(n: Int): Unit =
if (n < 0) ()
else { println(n); countDown(n - 1) }@tailrec-annotaatio
Lisäämällä @tailrec pyydät kääntäjää tarkistamaan, että funktio on todella häntärekursiivinen.
Jos näin ei ole, käännös epäonnistuu selkeän virheen kera. Näin huomaamattomasta suorituskykyloukusta tulee käännösaikainen takuu.
import scala.annotation.tailrec
def sum(xs: List[Int]): Int = {
@tailrec
def loop(rest: List[Int], acc: Int): Int = rest match {
case Nil => acc
case h :: t => loop(t, acc + h)
}
loop(xs, 0)
}
@main def run(): Unit = println(sum((1 to 100000).toList))Listan akkumulointi
Akkumulaattorien ei tarvitse sisältää lukuja. Niillä voi rakentaa myös kokoelmia.
Tämä käänteisfunktio lisää jokaisen pään akkumulaattorin alkuun, mikä kääntää järjestyksen luontevasti. Lisääminen ::-rakenteella on nopeaa, joten tämä on tehokasta.
def reverse[A](xs: List[A]): List[A] = {
def loop(rest: List[A], acc: List[A]): List[A] = rest match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}Käänteinen lista käytännössä
Akkumulaattori alkaa tyhjänä ja kasvaa, kun käsittelemme syötettä.
Koska jokainen pää lisätään acc-arvon alkuun, ensimmäinen alkio päätyy viimeiseksi. Näin saadaan käännetty lista vakiokokoisella pinokustannuksella.
def reverse[A](xs: List[A]): List[A] = {
def loop(rest: List[A], acc: List[A]): List[A] = rest match {
case Nil => acc
case h :: t => loop(t, h :: acc)
}
loop(xs, Nil)
}
@main def run(): Unit =
println(reverse(List(1, 2, 3))) // List(3, 2, 1)Useita akkumulaattoreita
Apufunktio voi kuljettaa samanaikaisesti useita akkumulaattoreita.
Tässä seuraamme kertynyttä tuloa ja lukumäärää samassa silmukassa ja palautamme molemmat tuplena.
Kumpikin välittää päivitetyn arvonsa seuraavalle kutsulle.
def stats(xs: List[Int]): (Int, Int) = {
def loop(rest: List[Int], prod: Int, count: Int): (Int, Int) =
rest match {
case Nil => (prod, count)
case h :: t => loop(t, prod * h, count + 1)
}
loop(xs, 1, 0)
}Alkuarvon valitseminen
Akkumulaattorin alkuarvon on oltava käytettävän operaation neutraali alkio.
Käytä yhteenlaskussa arvoa 0, kertolaskussa arvoa 1, listan rakentamisessa arvoa Nil ja merkkijonojen yhdistämisessä tyhjää merkkijonoa.
Väärä alkuarvo tuottaa huomaamatta vääriä tuloksia.
// addition -> seed 0
// product -> seed 1
// list -> seed Nil
// string -> seed ""Tulosten järjestys
Akkumulaattorirekursio käsittelee alkiot vasemmalta oikealle, mutta alkuun lisäävä akkumulaattori kääntää niiden järjestyksen.
Jos haluat säilyttää järjestyksen listaa rakentaessasi, käännä lista lopuksi tai lisää alkiot loppuun, vaikka jälkimmäinen on hitaampaa. Alkuun lisääminen ja lopuksi kääntäminen on tavallinen käytäntö.
def mapInc(xs: List[Int]): List[Int] = {
def loop(rest: List[Int], acc: List[Int]): List[Int] = rest match {
case Nil => acc.reverse
case h :: t => loop(t, (h + 1) :: acc)
}
loop(xs, Nil)
}Pikatarkistus
Valitse täsmällinen väite akkumulaattorirekursiosta.
Kertaus
Akkumulaattori kuljettaa kertyvää tulosta alaspäin rekursiivisten kutsujen läpi, joten perustapaus voi palauttaa sen suoraan.
Tällöin rekursiivinen kutsu on häntäasemassa, mikä mahdollistaa Scalan häntäkutsuoptimoinnin ja @tailrec-turvatarkistuksen.
Alusta akkumulaattori operaation neutraalilla alkiolla ja käännä lista lopuksi, jos järjestyksellä on merkitystä.
Opi Scala tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 39
- Oppitunnit
- 143
Usein kysytyt kysymykset
Onko oppitunti ”Akkumulaattorimallit” ilmainen?
Kyllä – oppitunnin ”Akkumulaattorimallit” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Scala backend-kehitykseen ja funktionaaliseen ohjelmointiin-kurssin, päivitä CoddyKit PROhon. Scala backend-kehitykseen ja funktionaaliseen ohjelmointiin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Akkumulaattorimallit”?
Siirtäkää tilaa rekursion läpi. Harjoittelet Scala backend-kehitykseen ja funktionaaliseen ohjelmointiin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Scala backend-kehitykseen ja funktionaaliseen ohjelmointiin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Scala backend-kehitykseen ja funktionaaliseen ohjelmointiin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Akkumulaattorimallit”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Scala backend-kehitykseen ja funktionaaliseen ohjelmointiin-oppitunnilla?
Kyllä. Jokainen Scala backend-kehitykseen ja funktionaaliseen ohjelmointiin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Rekursiivinen ajattelu
- Akkumulaattorimallit
- foldLeft ja foldRight
- reduce ja aggregate