(Mod. siirsi rekursiokeskustelun toisesta keskustelusta.)
koodaaja kirjoitti:
sub Kertoma($){ #Lasketaan binomikertoimeen tarvittava kerroin. $a = @_[0]; $tulos = 1; for ($i = 1; $i <= $a; $i += 1){ $tulos *= $i; } return $tulos }
Olet toteuttanut tuon kertoma-funktion toistolauseen sisällä rekursion sijaan, onhan tuokin yksi keino laskea kertoma. Tuota toistoratkaisua näkee rekursiota harvemmin. En tiedä, onko siitä mitään virallista keskustelua käynnissä missään piireissä, kumpi tavoista on "oikeampi".
Rekursio on helpompi toteuttaa, mutta loopin käyttäminen on tehokkaampaa.
AtskaFin kirjoitti:
Rekursio on helpompi toteuttaa, mutta loopin käyttäminen on tehokkaampaa.
Onhan se niinkin, että toistorakenteessa on helpompi määritellä ja laskea aikakompleksisuus, kuin rekursiossa. Rekursiossa syötekokona käytetään n:ttä metodin itsensä uudelleen kutsua siinä laskentakaavassa, kun taas iteraatiossa, mitä tuo toistorakenne, tässä koodiesimerkissä for-toistorakenteessa, niin on se iteraatioiden lukumäärä se syötekoko, kun lasketaan tuota kertoma-funktion aikakompleksisuutta.
En tiedä, miten historian saatossa alan oppikirjallisuudessa on asia esitetty, mutta mitä itse käsitin tuon rekursion menetelmän Hanoin Tornit-ongelmasta ensimmäisen kerran, ja tuo kertoma-esimerkki on klassinen tapa esittää tuo rekursio alan kirjallisuudessa.
Melkein se menee niin, että niitä menetelmiä kukin ohjelmoija käyttää, jotka joskus opiskeluaikoinaan juurtunut mielen sopukoihin. En omaa asiantuntemusta kritisoida tuota silmukka-toisto-ratkaisua, koska en kykene muita argumentteja esittämään puolesta tai vastaan, mitä nyt kerroin, että aikakomplesisuus on rekursiossa vaikeampaa määritellä, mitä iteraation tapauksessa.
Jere Sumell kirjoitti:
Onhan se niinkin, että toistorakenteessa on helpompi määritellä ja laskea aikakompleksisuus, kuin rekursiossa. Rekursiossa syötekokona käytetään n:ttä metodin itsensä uudelleen kutsua siinä laskentakaavassa, kun taas iteraatiossa, mitä tuo toistorakenne, tässä koodiesimerkissä for-toistorakenteessa, niin on se iteraatioiden lukumäärä se syötekoko, kun lasketaan tuota kertoma-funktion aikakompleksisuutta.
Melkein se menee niin, että niitä menetelmiä kukin ohjelmoija käyttää, jotka joskus opiskeluaikoinaan juurtunut mielen sopukoihin. En omaa asiantuntemusta kritisoida tuota silmukka-toisto-ratkaisua, koska en kykene muita argumentteja esittämään puolesta tai vastaan, mitä nyt kerroin, että aikakomplesisuus on rekursiossa vaikeampaa määritellä, mitä iteraation tapauksessa.
Rekursiotakin on monenlaista ja esimerkiksi häntärekursion tapauksessa suorituskyky varmasti on hyvä.
Jere Sumell kirjoitti:
Tuota toistoratkaisua näkee rekursiota harvemmin.
Oikeassa koodissako? Kertomaa käytetään usein esimerkkinä kun halutaan selittää rekursiosta, mutta ei se tarkoita, että rekursio on oikeasti järkevä toteutustapa (ainakaan perinteisissä ei-funktionaalisissa kielissä).
Proseduraalisissa kielissä silmukka on minusta parempi, tosin yleensä silmukka tehdään vain kerran ja tarvittavat arvot tallennetaan taulukkoon. Kisakoodauksessa joutuu silloin tällöin laskemaan vaikka 200000! (mod joku alkuluku), enkä ole nähnyt kenenkään käyttävän tähän rekursiota.
jalski: Skriptikielet eivät välttämättä toteuta häntärekursion optimointia, eikä tyypillinen rekursiivinen kertoma ole häntärekursiivinen.
Jere Sumell kirjoitti:
Tuota toistoratkaisua näkee rekursiota harvemmin. En tiedä, onko siitä mitään virallista keskustelua käynnissä missään piireissä, kumpi tavoista on "oikeampi".
No valitse nyt ainakin oikea adjektiivi. Rekursio on yksinkertaisesti huonoin vaihtoehto. Keskityit yksinomaan aikavaativuuden arvuutteluun, mutta ehkä triviaalein esimerkki rekursion ongelmallisuudesta on kuitenkin tilavaativuus.
Silmukassa ohjelman tila on se mitä silmukan sisällä tapahtuu. Rekursiossa ohjelman tila alkaa ensimmäisestä rekursiivisesta kutsusta ja sama tila pysyy yllä (ja kasvaa) kunnes rekursion viimeinen kutsu on valmis. Eli jos rekursiivinen funktio kutsuu itseään sata kertaa, niin voisi karkeasti sanoa tilavaatimuksenkin olevan satakertainen verrattuna yhteen funktiokutsuun.
Tarkoitan "tilalla" tässä sitä tavaraa, mikä täytyy pitää ohjelman muistissa tietyn koodilohkon suorituksen aikana.
muuskanuikku kirjoitti:
No valitse nyt ainakin oikea adjektiivi. Rekursio on yksinkertaisesti huonoin vaihtoehto. Keskityit yksinomaan aikavaativuuden arvuutteluun, mutta ehkä triviaalein esimerkki rekursion ongelmallisuudesta on kuitenkin tilavaativuus.
...
Tarkoitan "tilalla" tässä sitä tavaraa, mikä täytyy pitää ohjelman muistissa tietyn koodilohkon suorituksen aikana.
Ymmärrän kyllä, että on muitakin resursseja, kuin aika. Kuten totesit, muisti on yksi, tajusin että tarkoitat tilalla tietokoneen muistista vaadittavaa tilakokoa.
Muistivaatimus, eli tilavaatimus, algoritmin suorittamiseen vaadittava aika, mitä muita resursseja niitä onkaan, niin kaikkea ei voi optimaalisesti käyttää vähän, aina kun jostain toisesta tinkii, niin aina se on jonkin toisen resurssin käyton eduksi, ja päinvastoin.
Varmaan tapauskohtaisesti riippuen siitä, mihin käyttotarkoitukseen ohjelmaa kehitetään, niin joudutaan puntaroimaan eri resurssien käyton välillä, mistä säästetään ja mikä on tärkeää, kaikkea ei voi aina saada.
On totta, että tässä ohjelmaesimerkissä tuo silmukassa kertoman laskeminen vaatii vähemmän muistikapasiteettia tietokoneelta, mitä tuo rekursio, enkä sitten aikavaatimuksestakaan tiedä, taitaa tämä silmukassa laskeminen olla nopeampaakin, niin siinä mielessä saatat olla oikeassa, että jos vertailee rekursiota ja toistorakennetta tässä ohjelmaesimerkissä, niin rekursio olisi selkeästi huonompi ratkaisu.
Jere Sumell kirjoitti:
Muistivaatimus, eli tilavaatimus, algoritmin suorittamiseen vaadittava aika, mitä muita resursseja niitä onkaan, niin kaikkea ei voi optimaalisesti käyttää vähän, aina kun jostain toisesta tinkii, niin aina se on jonkin toisen resurssin käyton eduksi, ja päinvastoin.
Avainsana on "optimaalisesti". Nyt puhuttiin kertomasta, jossa rekursio ei ole millään tavalla optimaalinen vaan joka suhteessa huonompi.
Turun yliopiston perusopintoihin sisältyvässä aineopinto-kokonaisuuteen kuuluvassa viimeisessä lopputentissä piti kurssin yhden bitin muistavan mikro-ohjelmoitavan tietokoneen kertoma-ohjelma kirjoittaa alkeellisella konekielellä, ja siinäkin oli ainut vaihtoehto käyttää silmukkaa, eli jump, ja vertailu jumpzero oli ne käytetyt siinä, joilla toistorakenne saatiin alkeellisesti toteutettua. Tosin kehittyneimmissä konekielissä kyllä on mahdollisuudet rekursiiviseen ratkaisuunkin, mutta yksi rajoite myos on, milloin esimerkiksi rekursiota ei voi käyttää on se, minkälaiseen suorituskykyyn maksimissaan tietokone kykenee, johon ohjelmaa ollaan ohjelmoimassa, jos siinä on piirilevyyn poltettuna juuri tietynlainen konekielinen tulkki, kuten tuossa Turun yliopiston mielestäni tuon kyseisen kurssin klassikoksi muodostuneessa tietokoneessa.
Totta puhuen vastaavia rajoituksia ei nyky-kotikäyttoon tarkoitetuissa mikrotietokoneissa juuri ole, vaan nykyään näillä voidaan suorittaa korkean tason kielen ohjelmia melko pitkälti välittämättä juuri muisti tai aikavaatimuksista noin karkeasti ottaen, etenkään jos suoritettava ohjelmisto ei ole kovinkaan laaja tai monimutkainen.
En tiedä, pitäisiko tasta luoda oma viestiketju, mutta liitän tähän nyt sen, kun kertoma -funktio aiheutti monta viestiä tähän keskustelusäikeeseen. Oma toteutukseni Javalla molemmista, niin joku voi ohjelmoida ajan kuluksi aikaa mittaavan koodin näihin leikepoydältä kopioinnin jälkeen, jos tykkää vertailla, kumpi on nopeampi suorittaa.
Kyllähän rekursio vaatii vähemmän ohjelmoijalta ohjelmoituja lähdekoodirivejä, mitä tuo iteraatio toistorakenteessa, mutta noita resursseja silmällä pitäen, mistä oli nyt puhetta tilasta, ajasta, ja tietokoneen mahdollisista rajoituksista yhtenä myos, niin voinee tehdä saman johtopäätoksen, että ohjelmoijaa, joka toteuttaa rekursiolla kertoman, voidaan pitää tietokone-resurssijuoppouden edistäjänä.
public class Kertoma {
//Kertoma rekursiona
public static int kertomaRec(int x) {
if (x>0) return x*(kertomaRec(x-1));
return 1;
}
//Kertoma toistorakenteessa iteraatio-ratkaisu
public static int kertomaIter(int x) {
int y=1;
if (x>0) {
for (x=x;x>1;x--) {
y*=x;
}
}
return y;
}Molemmista noista metodeista tekee saman asian, joskin tuossa rekursiossa on vähemmän koodausta.
public static void main(String[] args) {
System.out.println(kertomaRec(5));
System.out.println(kertomaIter(5));
}
}Tulosteet:
120 120
Jos joku on kiinnostunut havainnon tekemään suoritusajasta ja haluaa vertailla noita, on syytä valita syoteparametriksi paljon suurempi luku, ja yhtä suuret luvut molemmissa metodikutsuissa, jotta ne on vertailukelpoisia.
Näin voidaan päätyä varmaankin samaan lopputulemaan, mitä muuskanuikku ja Metabolix totesikin, että resurssien käyton kannalta tuo toistolause -ratkaisu on ehdottomasti parempi. Ja proseduraalisessa ohjelmoinnissa myos kätevin.
jlaire kirjoitti:
jalski: Skriptikielet eivät välttämättä toteuta häntärekursion optimointia, eikä tyypillinen rekursiivinen kertoma ole häntärekursiivinen.
Oma kokemukseni on, että se on monesti ainoita optimointeja mitä skriptikieletkin tekevät.
Miksei tyypillinen kertoma ole häntärekursiivinen? Eihän tuohon tarvitse lisätä kuin yksi argumentti lisää ja kääriä toisen funktion sisään...
Jere Sumell kirjoitti:
Kyllähän rekursio vaatii vähemmän ohjelmoijalta ohjelmoituja lähdekoodirivejä, mitä tuo iteraatio toistorakenteessa,
Ensinnäkin olet koodannut taas ihmeellistä sotkua, joten noiden perusteella ei kannata tehdä päätelmiä. Tarpeeton if-lause ja tarpeeton sijoitus x=x, mitä ihmettä? Selvempi koodi olisi esim. tämä:
public static int kertomaIter(int x) {
int tulos = 1;
while (x > 1) tulos *= x--;
return tulos;
}Jos oikeasti haluat vertailla koodirivien määrää (tyhmä mittari), Javassa voi poistaa rivinvaihdot, tai tämänkin koodin voi purkkavirittää ”yhdelle riville”:
public static int kertomaIter(int x) {
for (int tulos = 1;; tulos *= x--) if (x <= 1) return tulos;
}Toki rekursiosta saa edelleen lyhyemmän ?:-operaattorilla:
public static int kertomaRek(int x) {
return x > 1 ? x * kertomaRek(x - 1) : 1;
}Jere Sumell kirjoitti:
Jos joku on kiinnostunut havainnon tekemään suoritusajasta ja haluaa vertailla noita, on syytä valita syoteparametriksi paljon suurempi luku,
Niin no kai tiedät, että Javan int on 32-bittinen eli siihen mahtuu kertomista enintään 12! ja puolestaan long on 64-bittinen eli siihen mahtuu enintään 20!, eli näillä ei vielä paljon suorituskykyä mitata. Ja vertailu testaamalla on sikäli turhaa, että koodista voi suoraan todeta tuloksen: molemmissa tehdään samat laskutoimitukset (kertolaskut, vähennyslaskut, vertailut), ja rekursiossa tehdään lisäksi funktiokutsuja, joten loogisesti rekursion on oltava hitaampi. Algoritmiohjelmoijan yleistietoon kuuluu, että funktiokutsu on suhteellisen hidas toimenpide esimerkiksi tavallisiin kokonaislukulaskuihin verrattuna.
Muutenkin varsinaista suorituskykyä aikaisemmin tulee vastaan se karu todellisuus, että rekursio syö rajallista pinomuistia: omassa testissäni noin 16900 rekursiotason kohdalla ohjelma kaatuu poikkeukseen java.lang.StackOverflowError, ja ajankäyttö ei tuossa vaiheessa näkyvästi eroa tyhjästä ohjelmasta.
Tämä myös osoittaa suoraan vääräksi väitteesi: ”nykyään näillä voidaan suorittaa korkean tason kielen ohjelmia melko pitkälti välittämättä juuri muisti tai aikavaatimuksista noin karkeasti ottaen”. Vaikka jotain alkeellisia käyttöliittymiä ja ohjelmoinnin alkeiskurssin harjoituksia voi tehdä surutta huonosti, oikeassa ohjelmoinnissa ohjelman nopeus ja muistinkäyttö ovat edelleen tärkeimpiä asioita. Tämä näkyy konkreettisesti mm. siinä, että markkinoilla on edelleen kysyntää nopeammille koneille ja isommalle muistille – ei ole saavutettu tilaa, jossa näistä asioista ei tarvitsisi välittää.
jalski kirjoitti:
Miksei tyypillinen kertoma ole häntärekursiivinen? Eihän tuohon tarvitse lisätä kuin yksi argumentti lisää ja kääriä toisen funktion sisään...
Hauskasti vastasit itse kysymykseesi. Eli tietenkin kertoman saa häntärekursiiviseksi kuvaamallasi tavalla, mutta se ei ole enää ”tyypillinen rekursiivinen kertoma”. Yleensä esitetään yksinkertaisin mahdollinen versio (f(x-1)*x).
Metabolix kirjoitti:
Niin no kai tiedät, että Javan int on 32-bittinen eli siihen mahtuu enintään 12! ja puolestaan long on 64-bittinen eli siihen mahtuu enintään 20!, eli näillä ei paljon suorituskykyä mitata.
Tiedän tämän hyvinkin. Tuolla 32-bittisellä arvollahan voidaan esittää lukuväli -4294967295-4294967295, ja tuo 12! on viimeinen kertoman lopputulos on viimeinen, joka mahtuu tuohon lukualueeseen. Tarvittaisiin 33 bittiä, jotta 13! olisi mahdollista tietokoneen antaa laskettavaksi, mutta se ei ole 2:n potenssi, niin käytännossa seuraava on juuri tuo 64 bittinen 32:sta, niin siinäkin tulee melko pian rajoitukset vastaan, mistä tuo pinon ylivuoto johtuu. (64 bitillä voidaan esittää arvoalue -18446744073709551615 - 18446744073709551615)
Jere Sumell kirjoitti:
Tiedän tämän hyvinkin. Tuolla 32-bittisellä arvollahan voidaan esittää lukuväli -4294967295-4294967295,
Vai niin? Kylläkin 32-bittisen kokonaisluvun lukualue on -2147483648 – 2147483647 eli siis -(2³¹) – (2³¹ - 1). Yhden ero pienimmässä ja suurimmassa luvussa liittyy siihen kahden komplementtiin, jota aikaisemmin ihmettelit. Myös 64-bittinen alue meni samalla tavalla pieleen, eli ilmoitit lähinnä 65-bittisen yhden komplementtina ilmaistavan luvun alueen.
Jere Sumell kirjoitti:
siinäkin [64-bittisessä] tulee melko pian rajoitukset vastaan, mistä tuo pinon ylivuoto johtuu.
Pinon ylivuoto ei johdu millään tavalla 32- tai 64-bittisten lukujen lukualueesta vaan pinon muistimäärästä, jota rekursio kuluttaa.
Juuri näin, hyvä että korjasit nämä virheelliset lukuni nopeasti, että kenellekkään pääse muodostumaan virheellistä muistijälkeä aivopoimujen reseptoreihin minun virheideni takia!
Metabolix kirjoitti:
Jos oikeasti haluat vertailla koodirivien määrää (tyhmä mittari), Javassa voi poistaa rivinvaihdot, tai tämänkin koodin voi purkkavirittää ”yhdelle riville”:
En koodirivien määrän vertailussa itsekään näe mitään järkevää ideaa, mutta ohjelmoijan työmäärän kannalta mitä vähemmällä koodirivillä saadaan toteutettua jotain välittämättä siitä, mitä resursseja on käytössä ja kuinka paljon, niin ohjelmoijan työtaakka vähenee. Todellisuudessa ohjelmoijan täytyy puntaroida tosiaan noitat musiti-tila, aika, kohde-tietokoneen suorituskyvyn asettamat resurssit, ne ne tärkeimmät on tosiaan.
On tuo while-toistorakenne for-toistoa tehokkaampi iteraatio-ratkaisussa, jonka esitit. Kävi mullakin mielessä while, mutta pistin nyt forin, kun alkuperäisessäkin esimerkissä oli for, tosin eri lähdekielellä.
jalski kirjoitti:
jlaire kirjoitti:
jalski: Skriptikielet eivät välttämättä toteuta häntärekursion optimointia
Oma kokemukseni on, että se on monesti ainoita optimointeja mitä skriptikieletkin tekevät.
Meillä on pakko olla kokemuksia eri skriptikielistä.
Alunperin puhuttiin Perlistä, joten tein sillä pienen testin. Lasken kertoman modulo 10^9+7. Bigintit dominoisivat ajoaikaa eikä natiiveilla tyypeillä saa mielekästä tulosta.
#!/usr/bin/perl
use strict;
use warnings;
use v5.16;
use Time::HiRes qw(time);
use feature "signatures";
no warnings "experimental::signatures";
use constant MOD => 1000000007;
sub kertoma_silmukka($n) {
my $tulo = 1;
$tulo = ($tulo * $_) % MOD for 1 .. $n;
return $tulo;
}
sub kertoma_rekursio($n) {
return 1 if $n == 0;
return ($n * kertoma_rekursio($n-1)) % MOD;
}
sub kertoma_hantarekursio($n, $tulo=1) {
return $tulo if $n == 0;
return kertoma_hantarekursio($n-1, ($n*$tulo) % MOD);
}
sub kertoma_goto($n, $tulo=1) {
return $tulo if $n == 0;
@_ = ($n-1, ($n*$tulo) % MOD);
goto &kertoma_goto;
}
my $N = shift() // 10**6;
my $alku = time();
say kertoma_silmukka($N);
printf "silmukka: %d ms\n\n", 1000 * (time() - $alku);
$alku = time();
say kertoma_rekursio($N);
printf "rekursio: %d ms\n\n", 1000 * (time() - $alku);
$alku = time();
say kertoma_hantarekursio($N);
printf "häntärekursio: %d ms\n\n", 1000 * (time() - $alku);
$alku = time();
say kertoma_goto($N);
printf "goto-rekursio %d ms\n\n", 1000 * (time() - $alku);Alla on tulostus. Rekursio on yli 15 kertaa hitaampi kuin silmukka ja syvästä rekursiosta tulee varoituksia.
Vaikka häntärekursion optimoisi manuaalisesti (goto &NAME), se on huomattavasti silmukkaa hitaampi. Pinon (@_) toimivuutta parametrilistan kanssa ei myöskään ole taattu tulevissa Perl-versioissa.
$ perl fact.pl 641102369 silmukka: 40 ms Deep recursion on subroutine "main::kertoma_rekursio" at fact.pl line 21. 641102369 rekursio: 671 ms Deep recursion on subroutine "main::kertoma_hantarekursio" at fact.pl line 26. 641102369 häntärekursio: 779 ms 641102369 goto-rekursio 380 ms
jlaire kirjoitti:
$ perl fact.pl 641102369 silmukka: 40 ms Deep recursion on subroutine "main::kertoma_rekursio" at fact.pl line 21. 641102369 rekursio: 671 ms Deep recursion on subroutine "main::kertoma_hantarekursio" at fact.pl line 26. 641102369 häntärekursio: 779 ms 641102369 goto-rekursio 380 ms
Aika huikea tuo aikaero. perl on jotenkin vieras minulle, mutta eipä nuo suoritusajat taida poiketa, sama millä kielellä ohjelmoi. Ainakaan ratkaisevasti.
Hienoa, että jaksoit tehdä aikavertailun, jossa käytit jotain vertailukelpoista syotetta tuon kertoman laskemiseen, joka vaati sinulta ponnisteluja, kun primaaritietotyypit eivät kelpaa.
jlaire kirjoitti:
Lasken kertoman modulo 10^9+7. Bigintit dominoisivat ajoaikaa eikä natiiveilla tyypeillä saa mielekästä tulosta.
Tässäkin, kun 9 merkitsevää numeroa, niin alkaa virheellisiä tuloksia tulemaan verraten jos laskee kynällä ja paperilla, jossa teoriassa on käytossa ääreton määrä lukuyksikkoa, jos aletaan menemään juuri tuon Metabolixenkin aiemmin mainitun 12-yli. Toisaalta, ihmisen reaalielämän ongelmissa taitaa aika harvassa olla 13! ja sen yli menevät kertomat, kun avaruuslennotkin nyt pääosin ihan hyvin tähän asti onnistuneet, vaikka on niitä ohjelmistovirheitä niiissäkin ollut ja mitä lennon valmisteluun kuluva aika ja rahamäärä useita kymmeniä miljardeja ennen lennon toteutumishetkeä rahassa mitattuna, niin sitten on epäonnistunut ohjelmistovian tai jonkin laskuvirheen takia heti ensimetreillä, mutta pääosin voi sanoa, että avaruuslennotkin on saatu aika hyvin onnistumaan, niin sielläkään tule tällaista yli 12! tilannetta eteen, vai olenko käsittänyt jotain väärin.
Kertoma-taulu x = 1 - 1 x = 2 - 2 x = 3 - 6 x = 4 - 24 x = 5 - 120 x = 6 - 720 x = 7 - 5040 x = 8 - 40320 x = 9 - 362880 x = 10 - 3628800 x = 11 - 39916800 x = 12 - 479001600 -------------------- x = 13 - 227020758 -------------------- x = 14 - 178290591 -------------------- x = 15 - 674358851 ------------------- x = 16 - 789741546
Tein Javalla tuon saman, mitä jlaire perlillä tuolla toistolausekkeella,niin tässä koodini:
//Modulo 10^9+7 (1000000007)
static long kertomaMod(int n)
{
long M = 1000000007;
long f = 1;
for (int i = 1; i <= n; i++)
f = (f*i) % M;
return f;
}Moneenko erilaiseen järjestykseen voidaan lajitella korttipakan 52 korttia Tietokone antaa vastaukseksi: 948537388
jlaire kirjoitti:
Alla on tulostus. Rekursio on yli 15 kertaa hitaampi kuin silmukka ja syvästä rekursiosta tulee varoituksia.
Vaikka häntärekursion optimoisi manuaalisesti (goto &NAME), se on huomattavasti silmukkaa hitaampi. Pinon (
@_) toimivuutta parametrilistan kanssa ei myöskään ole taattu tulevissa Perl-versioissa.
Tuntuu isolta erolta kyllä. Alla häntärekursiivinen 8th ohjelma, mikä laskee kertoman luvulle 25206. Aikaa omalla vanhalla kannettavallani kuluu yhteensä 131 ms laskentaan ja tulostukseen.
: tailrecursive-fact \ n a -- a
over 1 n:= if
nip
else
over n:1- 3rev n:*
recurse
then ;
: fact \ n -- n
1 \ n 1
tailrecursive-fact ;
: app:main
d:msec >r
25206 fact "%.f\n" s:strfmt .
d:msec r> n:- "\nAikaa kului: %d millisekuntia.\n" s:strfmt .
bye ;Metabolix kirjoitti:
Muutenkin varsinaista suorituskykyä aikaisemmin tulee vastaan se karu todellisuus, että rekursio syö rajallista pinomuistia: omassa testissäni noin 16900 rekursiotason kohdalla ohjelma kaatuu poikkeukseen java.lang.StackOverflowError, ja ajankäyttö ei tuossa vaiheessa näkyvästi eroa tyhjästä ohjelmasta.
Itse sain tuon tulemaan 41000-42000 rekursiokierroksen kohdalla.
Koodini
public static long kertomaModRek(int x) {
long m = 1000000007;
return x > 1 ? x * kertomaModRek(x - 1) % m : 1;
}Satunnaistulostus toistokokeen jälkeen
x - 41880 18113022
x - 41881 591469076
x - 41882 907667635
Exception in thread "main" java.lang.StackOverflowError
at Kertoma.kertomaModRek(Kertoma.java:26)Kutsuin main-metodista tuota kertomaModRek -metodia, ja rivillä 26 on juuri tämä relevantein avainrivi:
return x > 1 ? x * kertomaModRek(x - 1) % m : 1;
Toistokoetta toistaessa 41000-42000 kierroksen kohdalla jossain vaiheessa pätkäisee tuon herjan ilmoille, mutta iteroidessa for-silmukka pystyy laskemaan vielä tämänkin! Suoritusaikana 1-2 millisekuntia 64-bittisellä Intelin i5 8.sukupolven prosessorilla ja 8 gigatavun RAMmilla Windows 10-ympäristössä.
172940 kierrosta pääsee Javalla, ja jatkuisikin vielä varmaan, jos ajaa komentokehoitteesta java -parametrilla
java -Xss4m Kertoma > StackTest.txt
Toisaalta, en tiedä miten ohjelma päättyy, kun katkaisin väkivaltaisesti ohjelman suorituksen CTRL-C +näppäinyhdistelmällä, niin sitten tuli noita java.lang.StackOverflowError -virheherjoja konsoliin. Mutta tuolla Stack.txt -tiedostossa, jonka kooksi kasvoi noin 3,5 megatavua, niin viimeisin kertoma. josta se laskettiin, eli x ja kertoma, oli tuo 172940
x - 172938 973127015 x - 172939 611669048 x - 172940 44420646
(Mod. siirsi uusiutuneen sivujuonteen toisesta keskustelusta...) – – ja mitä oli tuossa rekursio vai iteraatio kertoma -säikeessä juttua java.lang.StackOverFlow -errorista, mitä se heittää, niin joissain tilanteissa voisi olla kätevää tehdä javaStackSize -alias, jossa parametrina annettaisiin haluttu koko tuolle pinolle ohjelmaa suorittaessa.
Kannattaa näköjään kokeilla eikä vain olettaa... Edellinen laittamani häntärekursiolla toteutettu versioni 8th:lla ei toiminut niin kuin luulin. Näyttäisi olevan, että recurse pitää olla viimeinen käännetty sana, jotta häntärekursio "eliminaattori" havaitsee häntärekursion.
Alla oleva toimii oikein. Lisäksi suurilla luvuilla toimittaessa pitäisi muistaa asettaa laskentatarkkuus riittävän moneen numeroon oikean laskentatuloksen saamiseksi.
: tailrecursive-fact \ n1 n2 -- n2
over 1 n:= if
nip ;;
then
over n:1- 3rev n:*
recurse ;
: fact \ n -- n
1 \ n 1
tailrecursive-fact ;
: app:main
d:msec >r
800 fact "%d\n" s:strfmt .
d:msec r> n:- "\nAikaa kului: %d millisekuntia.\n" s:strfmt .
bye ;Jere Sumell kirjoitti:
ja mitä oli tuossa rekursio vai iteraatio kertoma -säikeessä juttua java.lang.StackOverFlow -errorista, mitä se heittää, niin joissain tilanteissa voisi olla kätevää tehdä javaStackSize -alias, jossa parametrina annettaisiin haluttu koko tuolle pinolle ohjelmaa suorittaessa.
Mielestäni, jos joudut kasvattamaan pinon oletus kokoa niin kannattaa mielummin miettiä mitä ohjelmassa voisi tehdä toisin.
jalski kirjoitti:
Mielestäni, jos joudut kasvattamaan pinon oletus kokoa niin kannattaa mielummin miettiä mitä ohjelmassa voisi tehdä toisin.
Tuo on kyllä minunkin mielestäni täysin totta. Itse nyt tuossa testissä, kun testasin, kuinka monennella rekursio-kierroksella tulee tuo virheherja pinon ylivuodosta, kun tämän palstan ylläpitäjä? Metabolix -nimimerkki kertoi itse saaneensa javassa tuon herjan jo päälle 16 000 kutsuma-kasauman jälkeen, mitä itse pääsin melkein 180 000, kun ajoin java-komennon tuolla pinon koon asettamis-parametrilla. Itse en ole koskaan muutoin tarvinnut sitä.
Tässä, kun valaistuin todella, kuinka hidas tuo rekursio on iteraatioon verrattuna kiitos asiallisen viestiketjun, jonka aloitti tämän putka-moderaattorin siirtämä viestini tuolta binomitodennäköisyys-säikeestä omaan säikeenseensä, niin tällainenkin kysymys on käynyt mielessä, että "Onko rekursio täysin turha lopulta, koska ei taida olla ainuttakaan ongelmaa, jota ei voitaisi iteraatiolla ratkaista." Iteraatio todellakin nopeampi, kuten tuolla perlillä tehty demonstraatio ajanoton suhteen osoitti, mitä tuonne eräs nimimerkki oli demostraationa laittanut esille.
Jere Sumell kirjoitti:
Tässä, kun valaistuin todella, kuinka hidas tuo rekursio on iteraatioon verrattuna kiitos asiallisen viestiketjun, jonka aloitti tämän putka-moderaattorin siirtämä viestini tuolta binomitodennäköisyys-säikeestä omaan säikeenseensä, niin tällainenkin kysymys on käynyt mielessä, että "Onko rekursio täysin turha lopulta, koska ei taida olla ainuttakaan ongelmaa, jota ei voitaisi iteraatiolla ratkaista." Iteraatio todellakin nopeampi, kuten tuolla perlillä tehty demonstraatio ajanoton suhteen osoitti, mitä tuonne eräs nimimerkki oli demostraationa laittanut esille.
Jotkut ongelmat ratkeavat elegantimmin rekursiolla ja esimerkiksi häntärekursion tapauksessa suorituskyvyn pitäisi olla iteratiivistä vastaava, koska useimmat ohjelmointikielet optimoivat silloin kutsun pois hypyksi, jolloin tuloksena on käytännössä silmukka ja pinon käyttökään ei tuosta siten kasva. Jos tiedossa on, että rekursion syvyys ei ole kovin suuri, niin en näe mitään syytä välttää rekursiota.
Näin kai se on sitten nähtävä lopulta, kuten arvon jalski totesit viisaasti.
Tämä case aika loppuun pureskeltu, rekursiosta ja iteraatiosta niiden viisauden puremat ovat aika syvällä olleet tässä yöunissanikin jo tätä ketjua seuratessa nämä viime päivät, mitä itsekin osallistuin tähän keskusteluun ja tein testejä Javalla. Yhteenvedon paikka.
Conclusion:
- Pääsääntöisesti lienee syytä suosia iteraatiota rekursion sijaan, koska se on nopeampi suorittaa?
- Nyky-koti mikrotietokoneemme ei kykene laskemaan 12: yli meneviä kertomia, jos ei jollekulle tullut epäselväksi vielä, kokeilkaa vaikka Windowsin Laskimella 13!, niin vastaukseksi tulee "Ylivuoto". Se on mahdollista toteuttaa tietokoneella tiettyyn pisteeseen saakka, mutta lopputulos-ulostulosteet ovat virheellisiä.
- Rekursiossa toiston määrän kasautuessa ennen pitkää päädytään pinon ylivuoto -ongelmiin, tosin voihan ne ylivuodot johtua jostain muustakin.
Tuossa nyt jotain johtopäätöksiä, joita tein tämän keskustelun lopuksi.
Jere Sumell kirjoitti:
- Nyky-koti mikrotietokoneemme ei kykene laskemaan 12: yli meneviä kertomia, jos ei jollekulle tullut epäselväksi vielä, kokeilkaa vaikka Windowsin Laskimella 13!, niin vastaukseksi tulee "Ylivuoto".
Tuossa nyt jotain johtopäätöksiä, joita tein tämän keskustelun lopuksi.
Tässä heti väärä johtopäätös. Vaikka jollakin antiikkisista retrotietokoneistanikin pystyn laskemaan paljon tuon yli. Voit käyttää jotain isoja lukuja tukevaa kirjastoa tai toteuttaa itse Karatsuba algoritmin tähän puuhaan. Jotkut ohjelmointikielet tukevat myös suoraan "big float" ja "big int" tietotyyppejä. Tällä hetkellä aiemmin laittamani häntärekursiivinen ohjelma laskee kertomaa luvulle 1000000. Tuloksessa on muuten 5565710 merkitsevää numeroa!
Nämä viimeisimmät postaukset tässä säikeessä kuuluisi periaatteessa siirtää tuonne rekursio/iteraatio -ketjuun, mutta vastaan nyt. (Mod. siirsi!)
Olet oikeassa, jalski, olin vain niin kiinni Javassa ja Metabolixen 12-luvussa, jota hän esitti. En epäilisi lainkaan, etteikö olisi olemassa ohjelmointikieliä, jotka tukevat juuri esimerkiksi niinkin isoja lukuja, että voivat esittää sen 5565710 merkitsevällä numerolla. Onhan näin pakko olla.
Windowsin laskin kuitenkaan ei tähän kykene, lähinnä se viittauksena siihen, kun Winkkari 10 on nyt kuitenkin aika monen taviksen käsitys perustietokoneen käyttäjän käyttöjärjestelmästä, mikä mahdollistaa kaiken tekemisen tietokoneella, niin siitä tuli tuo, että nykymikrotietokoneemme ei kykene laskemaan, korjataan: Windows-ympäristöön ohjelmoitu laskin ei kykene antamaan vastausta 12-yli meneville kertomille.
Jere Sumell kirjoitti:
korjataan: Windows-ympäristöön ohjelmoitu laskin ei kykene antamaan vastausta 12-yli meneville kertomille.
Jos nyt Windowsin Laskin-sovellus sisältää jonkin rajan, se on kyseisen ohjelman suunnittelusta kiinni, ei mikään tietokoneen tai kielen tai Windowsin absoluuttinen rajoitus. Varmasti moni muu Windowsissa toimiva laskinohjelma pystyy parempaan. (Ilmeisesti myös Windowsin Laskin on jossain versiossa tukenut isoja lukuja, onkohan ominaisuus sitten poistettu...) Mainitsemasi Java sisältää BigInteger-luokan, jolla voi laskea isoilla luvuilla, ja vastaavan voi myös tehdä itse millä tahansa tavallisella ohjelmointikielellä.
Isojen lukujen kanssa pitää muistaa, että myös tavalliset laskut vievät aikaa lukujen pituuden mukaan, jolloin esimerkiksi tuossa kertoman laskemisessa tulee pian isommaksi asiaksi kertolasku eikä iteraation ja rekursion ero.
Minusta tuntuu, että sinun kannattaisi lukea ja kysyä enemmän ja esittää omia johtopäätöksiä vähemmän, kun virheiden määrä on aika suuri.
Metabolix kirjoitti:
Minusta tuntuu, että sinun kannattaisi lukea ja kysyä enemmän ja esittää omia johtopäätöksiä vähemmän, kun virheiden määrä on aika suuri.
On totta, että pitää ottaa selvää enemmän ja olla enemmän uteliaampi ja kiinnostuneempi, ennen kuin alkaa tekemään mitään johtopäätoksiä. Otan opista vaarin entisestään!
Jere Sumell kirjoitti:
- Nyky-koti mikrotietokoneemme ei kykene laskemaan 12: yli meneviä kertomia, jos ei jollekulle tullut epäselväksi vielä, kokeilkaa vaikka Windowsin Laskimella 13!, niin vastaukseksi tulee "Ylivuoto"
Mitähän sä nyt taas horiset? Jotenkin tuntuu että täältä foorumilta ei löydy yhtäkään Jeren viestiä, jossa ei olisi harhakuvitelmia ja täysin tuulesta temmattuja väitteitä.
Windowsin laskimella pystyy aivan mainiosti (ja on pystynyt niin kauan kun siinä kertomatoiminto on ollut*) laskemaan 13!. Se antaa tulokseksi 6 227 020 800.
Itse asiassa suurin kertoma, jonka Windows 10 laskimella pystyy laskemaan on
3248! = 1,9736342530860425312047080034031e+9997
Ja tämäkin rajoitus johtuu ihan vaan siitä, että microsoftilla on päätetty rajata lukujen koko max. 10^10000:een. Vähän niinkuin kouluissa aikoinaan käytetyissä ei-funktionaalisissa laskimissa pystyi laskemaan isoimmillaan 69! koska muuten olisi tullut yli 10^100.
Windows 10:n laskin muuten käyttää sisäisesti rajattoman tarkkuuden RatPack (Rational Pack) kirjastoa peruslaskutoimituksille, eikä esim. liukulukuja.
* Vuonna 1990 julkaistu Windows 3.00 oli ensimmäinen jonka mukana tulleessa laskimessa oli kertomatoiminto "Scientific modessa". Suurin sillä laskettavissa ollut kertoma on 170!. Sitä vanhemmilla (eli ennen 1990 julkaistuissa) oli käytössä vain kymmenen numeron "näyttö" joten tosiaankin 12! oli suurin jonka pystyi laskemalla kertomalla numeroita yksi kerrallaan keskenään. Muuten voisin olettaa että Jere on jumittanut 30 vuotta jossain kiven alla, mutta hän kuitenkin mainitsi myöhemmässä viestissä Windows 10:n joten tämäkään ei asiaa selitä.
Myonnettäkoot, että olin väärässä.
Windows 3.00 todella oli ensimmäinen Windows, kun tutustuin pc-maailmaan lapsena, en elä mitään digitaalisaatio-aikakautta reaaliarjessani, mutta kyllä nyt ihan Windows 10 käytän toisessa koneessani siihen asti, kun Microsoft lopettaa päivitystuen siihen, ja sitten haen uuden tehomyllyn kodinkoneliikkeestä, jossa sitten on vakiona Windows 11, kun sekin tulossa vielä.
Ohjelmistokehitys-koneessa, josta pidän enemmän on ja paljon tehoja, niin siinä pyoritän Linux Minttiä, ja palvelinkone, jota en ole kytkenyt verkkoon, vaan katselen jotain turvallisuushommia siinä, opiskelen järjestelmän ylläpitäjän taholta Linuxia, ja sitten bash-skriptausta, niin siinä on Ubuntu Server 18
pitänee siirtyä sivustaseuraajaksi täällä putkassa, eikä heti laukoa sitä, mitä tulee ensimmäisenä mieleen. Ottaa selvää ensin, kuin avaa sanallisen aarrearkun.
jalski kirjoitti:
Tällä hetkellä aiemmin laittamani häntärekursiivinen ohjelma laskee kertomaa luvulle 1000000. Tuloksessa on muuten 5565710 merkitsevää numeroa!
Kun nyt keskusteltiin parhaasta tavasta kertoman laskemiseen, niin siinähän tämä kerrottavien lukujen suora läpikäynti iteraation tai rekursion avulla ei ole paras vaihtoehto, jos halutaan laskea yksittäisen kertoman tarkka tulos isoilla luvuilla.
Ainakin Pythonissa lasku nopeutuu huomattavasti, kun kerrotaan keskenään suunnilleen samankokoisia lukuja. Tuo jalskin ehdottama miljoonan kertoma vei suoralla silmukalla noin viisi minuuttia mutta keon avulla noin kymmenen sekuntia! (Koko tuloksen muunnos kymmenjärjestelmään on niin hidasta, että tyydyin tulosteessa muutamaan ensimmäiseen numeroon.) Väittävät, että laskeminen alkulukujen kautta olisi vielä nopeampaa, mutta itse en saanut tällä vakuuttavaa eroa. Läppärillä tarkempi nopeustestaus on ikävää, kun nopeus riippuu olennaisesti lämpötilasta.
import time, math, heapq
def kertoma_silmukalla(n):
kertoma = 1
for i in range(2, n + 1):
kertoma *= i
return kertoma
def kertoma_keolla(n):
keko = list(range(2, n+1))
while len(keko) > 1:
heapq.heappush(keko, heapq.heappop(keko) * heapq.heappop(keko))
return keko[0]
# Palauttaa kokonaisluvun ensimmäiset numerot.
def str_trunc(integer, digits = 20):
e = int(integer.bit_length() * math.log10(2) - digits)
if e > 0:
s = str(integer // 10 ** e)
e += len(s) - 1
else:
s = str(integer)
e = len(s) - 1
return f"{s[0]}.{s[1:]}e+{e}"
n = 1000000
for f in [kertoma_keolla, kertoma_silmukalla]:
t0 = time.time()
kertoma = f(n)
t1 = time.time()
s = str_trunc(kertoma, digits = 20)
t2 = time.time()
print(f"{f.__name__} vei {t1-t0:.3f} s")
print(f"{n}! = {s}, muunnos vei {t2-t1:.3f} s")En ole koskaan törmännyt tai oppilaitoksen ohjaaja ei ole maininnut keosta mitään AMK-ohjelmoitikursseila, eikä yliopistossakaan. Miten se niinkuin toimii?
Luin lähteestä
https://mitpress.mit.edu/sites/default/files/
että kaikki iteroitavissa olevat ongelmat on ratkaistavissa keolla, ja kun kaikki rekursiiviset ongelmat ovat iteraation avulla ratkeavia myös, niin kaikki rekursiiviset ongelmat ovat myös keko-ratkaisun takana.
Jere Sumell kirjoitti:
Miten se niinkuin toimii?
Kertolaskussa laskujärjestyksellä ei ole merkitystä.
Kertomassa syötteenä on luvut 1...N ja tehtävänä on palauttaa niiden tulo. Voit valita mitkä tahansa kaksi lukua, poistaa ne ja lisätä niiden tulon. Toista tätä kunnes jäljellä on vain yksi luku.
Metabolixin koodi valitsee fiksusti joka vaiheessa kaksi pienintä lukua.
Jere Sumell kirjoitti:
Luin lähteestä
https://mitpress.mit.edu/sites/default/files/sicp/full-text/sicp/book/node110.html
Tämä lähde ei liity Metabolixin ratkaisuun mitenkään.
Stack on suomeksi pino. Keko on englanniksi heap.
Joo, no valveutuneet lukijat ja ne, kenellä ei ole aivot turtuneet nettisurffailusessionsa aikana vielä tähän aikaan, niin voivat ignorettaa tuon linkkilähteeni.
Tässä nyt 11:s tunti menossa putkeen koneen äärellä, niin katsoin tuon "keko" -sanan sanakirja.orgista, ja sitten aivot narikassa -menetelmällä poimisin tuon ensimmäisen sieltä tulevan "stack", vaikka todellakin yhdistän pinon "stack" -käännökseen suomeksi, ja queue on jono, mutta heap -keko on vähän vieraampi, joskaan sekään nyt terminä ja käännöksenä mikään aivan uusi minulle ole.
Joskus ylä-asteella, kun aloin kuuntelemaan Uriah Heappia, pohtisin osuvaa suomennosta bändille, niin päädyttiin bändikaverini kanssa siihen, että ehkä Hensley ja Box tarkoittivat sillä "Jättimäistä paskaläjää", vaikka musiikki kolahti jo silloin ja on kestänyt hyvin aikaa ja on erinomaista vielä tänä päivänä, kyllä 70-luvun fantasia-metallia jaksaa vieläkin kuunella.
Muisti-tilaa säästävä ratkaisu, kun poistetaan jo lasketut, ja jos järjestyksessä pienimmästä lähdetään liikenteeseen, niin muistitilaa ei ole syömässä, kuin kaksi numeromuuttujaa kerrallaan, tai kolme siis, kun pitää tulos tallentaa kolmanteen muistipaikkaan, jonka jälkeen voi vasta alkaa poistamaan niitä.
Jere Sumell kirjoitti:
Uriah Heap
Uriah Heep.
Jere Sumell kirjoitti:
Muisti-tilaa säästävä ratkaisu
Pointti on nimenomaan säästää aikaa, ei muistia... Voi hyvänen aika nyt.
Ehkä pitäisi nukkumaan mennä jo vähäksi aikaa, jotta huomenna taas jaksaa roikkua netissä.
No, aikaa säästyy, ja muistiakaan tarvita paljoa masiinassa, jotta keko-ratkaisulla saadaan isoistakin luvuista kertoma lasketuksi. Molempi parempi.
Ainakin tässä miljoonan kertomassa Pythonilla vielä parempi tulos saadaan, kun rajoitetaan myös keon kokoa. Seuraava versio laittaa alussa kekoon 1024 suurinta lukua ja kertoo sitten aina pienimmän näistä seuraavalla syöteluvulla (koska seuraava syöteluku on tunnetusti pienempi kuin mikään kekoon laitettu luku), ja lopuksi keossa olevat luvut kerrotaan samoin kuin aiemmassa koodissa.
def kertoma_keolla_maxkoko(n): keko = list(range(max(2, n - 1023), n + 1)) for i in range(keko[0], 1, -1): heapq.heapreplace(keko, keko[0] * i) while len(keko) > 1: heapq.heappush(keko, heapq.heappop(keko) * heapq.heappop(keko)) return keko[0]
Samaan tai jopa niukasti parempaan pääsee myös silmukalla, kun optimoi tuon samankokoisten lukujen kertolaskun. Seuraavassa koodissa ideana on, että lasketaan noin 128 luvun kertolasku sellaisenaan ja sitten syötetään tämä välitulos kertolaskun ”portaikkoon”, jossa kahdesta saman tason välituloksesta kerrotaan seuraavan tason välitulos. Näin muistissa tarvitsee olla kerralla vain yksi kunkin välitason tulos eli miljoonan kertomassa vain 13 välitulosta tässä nimenomaisessa versiossa. (Jeren rakastamaa O-notaatiota tilankäytölle voi joku muu arvailla, kun asiaan on sotkettu kertoma ja pitkät luvut...)
def kertoma_silmukalla_kertolaskuoptimoitu(n): isot = [1] askel = 1 + (n // 128) # Käydään läpi aloituskohdat. for i in range(1, min(askel, n) + 1): # Kertolasku askeleen välein luvuista i ... n+1. osakertoma = i for j in range(i + askel, n + 1, askel): osakertoma *= j # Laitetaan osatulos isojen lukujen portaisiin. if 1 not in isot: isot.append(1) for j in range(len(isot)): # Jos portaissa on ykkönen, luku jää siihen odottamaan. if isot[j] == 1: isot[j] = osakertoma break # Muuten kertolaskun tulos nousee seuraavalle portaalle. osakertoma *= isot[j] isot[j] = 1 # Kerrotaan jäljelle jääneet isot luvut tulokseksi. tulos = 1 for i in isot: tulos *= i return tulos
Miljoonan kertomaa ajatellen tässä on vaihdettu muutama sekunnin osanen muutamaan suhteellisen vaikeaselkoiseen koodiriviin...
Aihe on jo aika vanha, joten et voi enää vastata siihen.