Keskustelu: Yleinen keskustelu: Lukujenvihaaja-putkaposti

Olen tuosta kyseisestä putkapostista ratkaissut raa'alla voimalla 10 lukua, mutta sen jälkeen laskenta-aika kasvaa liian suureksi. Miten tuota oikein kannattaisi lähestyä, jotta laskenta-aikaa voisi lyhentää. Luku 1234567898 ratkeaa voimalla suunilleen järkevässä ajassa (muutama minuutti), mutta 11:a luvun laskeminen kestää luultavasti jo tunteja.

Alla hajotusfunktio

int havitaLuku( long long int luku ){
	long long int miinus = 0LL;

	while(luku > 0){
		if(luku & 1){
			luku--;
			++miinus;
		}else{
			luku = (luku >> 1);
		}
	}
	return miinus;
}

Bittioperaatioiden kanssa olet jo oikeilla jäljillä, vaikka ehkä oletkin ottanut ne käyttöön vain optimointimielessä.

Yritän kirjoittaa nämä vihjeet muodossa, jossa niistä voisi päästä jyvälle mutta jossa ne eivät aukeaisi suoraan. Toivottavasti saat niistä jotain irti muttet aivan liikaa. :)

Tämä lienee helppo ymmärtää:

Tämän tärkeämpää merkitystä joudut ehkä jonkin verran pohtimaan:

Joo. Brute force ratkaisu ei oikein toimi kovin hyvin miljardien suuruisilla arvoilla. Kannattaa siis miettiä noita Metabolixin vinkkejä, mutta voi tuota brute force ratkaisuakin toki optimoida melkoisesti tehokkaammaksi. Silloin se saattaa suoriutua jo 11 numeron luvuista suht järkevässä ajassa ;)

Ensinnä ihan yleisiä pikkuviilauksia. Käytä prefix operaatiota --luku; postfix operaation luku--; sijaan. Postfix operaatio tekee ylimääräisen välivaiheen ja on hieman hitaampi. Sama juttu lausekkessa luku = (luku >> 1); Käytä sen sijaan luku >>= 1; ,jotta välttäisit ylimääräisen välisijoituksen. Lisäksi tuo else-haara on täysin turha. Jako kahdella voidaan tehdä jokaisella kierroksella. Sillä yhdellä vähentämisen jälkeen luku on joka tapauksessa parillinen tai nolla, eikä nollan jakaminen haittaa mitään. Näin vältetään turhaa looppausta. Ja sitten tehdään sama itse assylla. ;)

Sitten pari isompaa optimointia. Ensinnäkään parittomien lukujen vähennyksiä ei tarvitse laskea. Sehän on joka tapauksessa aina yhtä suurempi kuin edellinen. Täytyy siis vain muistaa viimeisimmän parillisen luvun erotusten määrä. Ja toisekseen, laskettaessa uusien lukujen erotusten määrää, ei tarvitse aloittaa alusta, vaan jatketaan edellisestä tuloksesta.

Kuten sanottua, niin ratkaisu on noidenkin jälkeen vielä melkoisen hidas, mutta tässä esimerkin vuoksi koodi, jossa nuo viilaukset on tehty. Kokeilin ajaa tuota ruokatunnin ajan ja siinä ajassa se oli tuhonnut 11 ensimmäistä lukua.

// Destroys numbers between start and end and returns amount of reductions needed for destruction
unsigned long long DestroyNumbers(unsigned long long start, unsigned long long end)
{
	static unsigned long long lastReductions = 0;
	unsigned long long totalReductions = 0;

	// calculate amount of reductions between start and end
	for(unsigned long long number = start; number <= end; number++) {
		unsigned long long destroyed = number;
		// Iff odd, the amount of reductions is the same as (last + 1)
		if(destroyed&1) {
			totalReductions += lastReductions+1;
		}
		// Else calculate new amount
		else {
			lastReductions = 0;
			while(destroyed) {
				destroyed >>= 1;
				if(destroyed&1) {
					++lastReductions;
					--destroyed;
				}
			}
			totalReductions += lastReductions;
		}
	}

	return totalReductions;
}

Torgo kirjoitti:

Ensinnä ihan yleisiä pikkuviilauksia. Käytä prefix operaatiota --luku; postfix operaation luku--; sijaan. Postfix operaatio tekee ylimääräisen välivaiheen ja on hieman hitaampi.

Ei tee, ei ole.

Torgo kirjoitti:

Sama juttu lausekkessa luku = (luku >> 1); Käytä sen sijaan luku >>= 1; ,jotta välttäisit ylimääräisen välisijoituksen.

Et vältä (tai tarkemmin: "välisijoitusta" ei ole).

Kääntäjästä riippuen todennäköisesti näin myös ilman minkäänlaisia optimointiasetuksia. Sitä en toki kiistä, etteikö varsinkin vm. tapa olisi suotava – ihan jo selkeyden vuoksi.

eq kirjoitti:

Torgo kirjoitti:

Ensinnä ihan yleisiä pikkuviilauksia. Käytä prefix operaatiota --luku; postfix operaation luku--; sijaan. Postfix operaatio tekee ylimääräisen välivaiheen ja on hieman hitaampi.

Ei tee, ei ole.

Torgo kirjoitti:

Sama juttu lausekkessa luku = (luku >> 1); Käytä sen sijaan luku >>= 1; ,jotta välttäisit ylimääräisen välisijoituksen.

Et vältä (tai tarkemmin: "välisijoitusta" ei ole).

Kääntäjästä riippuen todennäköisesti näin myös ilman minkäänlaisia optimointiasetuksia. Sitä en toki kiistä, etteikö varsinkin vm. tapa olisi suotava – ihan jo selkeyden vuoksi.

Suoraan kielen sääntöjen perusteella molemmissa tapauksissa tehdään välisijoitus. Voi olla että useimmat kääntäjät osaavat optimoida nämä kyseiset tilanteet, koska sitä välisijoitusta ei käytetä mihinkään. En kuitenkaan luottaisi siihen, vaan kirjoittaisin sen mieluummin suoraan siten kuin se on kielen säännöissä sanottu.

Prefix operaatio siis muuttaa kyseistä muuttujaa ja palauttaa sen arvon. Postfix operaatio puolestaan _tallettaa_ vanhan arvon talteen, muuttaa sen jälkeen muuttujan arvoa ja sen jälkeen vasta palauttaa sen tallennetun arvon. Tuota käytetään hyväksi esimerkiksi taulukon kopioinnissa: *dest++ = *src++; Prefix operaatio on siis juuri tuon arvon tallennuksen verran nopeampi.

Samoin on kielen sääntöjen mukaan tuossa shiftauksessa. Sääntöjen mukaan ensin lasketaan sulkeissa oleva lauseke, jonka arvo palautetaan sijoitusoperaattorille, joka puolestaan sijoittaa lasketun arvon muuttujaan. Sen sijaan jos käytetään <<= operaattoria, niin sijoitusta ei tapahdu lainkaan vaan shiftauksen toisena operandina käytetään suoraan vasemmankäden muuttujaa, kun oikean käden lauseke on evaluoitu (tässä tapauksessa vakio). Muuten lausekkeet ovat ekvivalentteja, joten voi olla että kääntäjät osaavat tilanteen optimoida.

Torgo kirjoitti:

Suoraan kielen sääntöjen perusteella molemmissa tapauksissa tehdään välisijoitus. Voi olla että useimmat kääntäjät osaavat optimoida nämä kyseiset tilanteet, koska sitä välisijoitusta ei käytetä mihinkään. En kuitenkaan luottaisi siihen, vaan kirjoittaisin sen mieluummin suoraan siten kuin se on kielen säännöissä sanottu.

Ei, vaan "voisi kuvitella, että tehdään välisijoitus".

Torgo kirjoitti:

Prefix operaatio siis muuttaa kyseistä muuttujaa ja palauttaa sen arvon. Postfix operaatio puolestaan _tallettaa_ vanhan arvon talteen, muuttaa sen jälkeen muuttujan arvoa ja sen jälkeen vasta palauttaa sen tallennetun arvon. Tuota käytetään hyväksi esimerkiksi taulukon kopioinnissa: *dest++ = *src++; Prefix operaatio on siis juuri tuon arvon tallennuksen verran nopeampi.

Tallettaa mihin? Sulautettujen järjestelmien osaajana luulisi sinunkin tietävän, mikä komento muuttujan kasvatuksen hoitaa - ja ei, se ei palauta mitään arvoa. Siksipä konekielisessä muodossaan kyse on vain komentojen järjestyksestä.

Esimerkki:
1a.

muuttuja++;
//"Konekielellä" (esim.)
//addl   $0x1,-0x4(%rbp)

1b.

++muuttuja;
//addl   $0x1,-0x4(%rbp)

1c.

muuttuja += 1;
//addl   $0x1,-0x4(%rbp)

2a.

arvo = muuttuja++;
//mov    -0x4(%rbp),%eax
//mov    %eax,-0x8(%rbp)
//addl   $0x1,-0x4(%rbp)

2b.

arvo = ++muuttuja;
//addl   $0x1,-0x4(%rbp)
//mov    -0x4(%rbp),%eax
//mov    %eax,-0x8(%rbp)

Missä tilanteessa tällä on sitten merkitystä? C:ssä ei missään; ns. natiiveilla tyypeillä nopeuseroa ei synny. Sen sijaan C++-luokat saattavat tehdä kuormitetulla postfix-operaattorilla turhan kopion, jota ei edes kääntäjä osaa optimoida pois - selkeästikään tästä ei tässä tapauksessa ole kyse.

lainaus:

Samoin on kielen sääntöjen mukaan tuossa shiftauksessa. Sääntöjen mukaan ensin lasketaan sulkeissa oleva lauseke, jonka arvo palautetaan sijoitusoperaattorille, joka puolestaan sijoittaa lasketun arvon muuttujaan. Sen sijaan jos käytetään <<= operaattoria, niin sijoitusta ei tapahdu lainkaan vaan shiftauksen toisena operandina käytetään suoraan vasemmankäden muuttujaa, kun oikean käden lauseke on evaluoitu (tässä tapauksessa vakio). Muuten lausekkeet ovat ekvivalentteja, joten voi olla että kääntäjät osaavat tilanteen optimoida.

Sulkeilla ei ole komennon kannalta merkitystä. Kielen säännöt takaavat pitkälti vain sen, että terminaattorin jälkeen lvaluen arvo on rvalue - eivät esimerkiksi sitä, että rvaluella olisi oma muistipaikkansa.

edit, edit1

eq kirjoitti:

Tallettaa mihin? Sulautettujen järjestelmien osaajana luulisi sinunkin tietävän, mikä komento muuttujan kasvatuksen hoitaa - ja ei, se ei palauta mitään arvoa. Siksipä konekielisessä muodossaan kyse on vain komentojen järjestyksestä.

Se on laskutoimitus siinä missä muutkin ja se palauttaa arvon. Ja postfixin tapauksessa arvo on se mikä muuttujan arvo oli alunperinkin. Prefixin tapauksessa se on muuttujan arvo kasvatuksen jälkeen. Postifix++:n on suoritusjärjestyksessä ennen mitään muuta operaattoria, mutta silti operaattoreille palautuu muuttujan vanha arvo.

eq kirjoitti:

Missä tilanteessa tällä on sitten merkitystä? C:ssä ei missään; ns. natiiveilla tyypeillä nopeuseroa ei synny. Sen sijaan C++-luokat saattavat tehdä kuormitetulla postfix-operaattorilla turhan kopion, jota ei edes kääntäjä osaa optimoida pois - selkeästikään tästä ei tässä tapauksessa ole kyse.

Tämä riippuu kääntäjästä. Vaikka nopeuseroa ei yleensä synnykään natiiveilla muuttujilla, ei sitä voi taata jokaisen kääntäjän osalta. Tässä tapauksessa tuskin on merkitystä kumpaa tapaa käytetään, mutta yleensä kannattaa suosia prefix tapaa, joka takaa että ei tehdä turhaa työtä.

C++ Primer 4th ed., 2008 kirjoitti:

ADVICE:USE POSTFIX OPERATIONS ONLY WHEN NECESSARY
The reason is simple. The prefix does less work. It increments the value and returns the incremented version. The postfix operator must store the original value so that it can return the unincremented value as its result. For ints and pointers, the compiler can optimize away the extra work.

eq kirjoitti:

Sulkeilla ei ole komennon kannalta merkitystä. Kielen säännöt takaavat pitkälti vain sen, että terminaattorin jälkeen lvaluen arvo on rvalue - eivät esimerkiksi sitä, että rvaluella olisi omaa muistipaikkaansa (tai rekisteriä).

Ei olekaan. Tässä tapauksessa sijoituksen oikealla puolella oleva osuus oli sulkeissa. Sama pätee kuitenkin ilman sulkeitakin.

C++ Primer 4th ed., 2008 kirjoitti:

The general syntactic form of a compound assignment operator is
a op= b;
Each compound operator is essentially equivalent to
a = a op b;

There is one important difference: When we use the compound assignment, the left-hand operand is evaluated only once. If we write the similar longer version, that operand is evaluated twice: once as the right-hand operand and again as the left. In many, perhaps most, contexts this difference is immaretial aside from possible performance consequences.

Kumpikaan muutos ei siis välttämättä takaa nopeampaa suoritusta, mutta ainakin se on mahdollista. Kuten alunperin sanoinkin, niin kyse on vain pikku viilailusta, jolla tuskin on suurtakaan vaikutusta.

Kun nyt standardeista ruvettiin väittelemään, niin otetaan vielä tueksi muutama pala sitä standardia.

ISO/IEC 9899:1999 kirjoitti:

The expression ++E is equivalent to (E+=1).

ISO/IEC 9899:1999 kirjoitti:

The result of the postfix ++ operator is the value of the operand. After the result is obtained, the value of the operand is incremented.

Mikään tässä ei velvoita kääntäjää esimerkiksi hakemaan arvoa rekisteriin. Jos siis kääntäjä sen turhaan tekee, voidaan minusta todeta, että kyseessä on huono kääntäjä.

ISO/IEC 9899:1999 kirjoitti:

A compound assignment of the form E1 op = E2 differs from the simple assignment expression E1 = E1 op (E2) only in that the lvalue E1 is evaluated only once.

Muuttujan nimessä ei ole erityisesti evaluoitavaa, joten merkinnöillä ei ole tuossa tilanteessa tätäkään pientä eroa.

Torgo kirjoitti:

Postifix++:n on suoritusjärjestyksessä

Suoritusjärjestyksestä sanotaan kylläkin vain, että korotus tapahtuu ennen seuraavaa puolipistettä. Ehkä sinun pitäisi lukea vielä hieman tarkemmin sitä standardia, jonka nojalla väitteitäsi esität.

Heh. Tästähän nyt ihmeen suuri haloo nousi. No kai se on hyvä selvittää asia perin pohjin.

Metabolix kirjoitti:

ISO/IEC 9899:1999 kirjoitti:

A compound assignment of the form E1 op = E2 differs from the simple assignment expression E1 = E1 op (E2) only in that the lvalue E1 is evaluated only once.

Muuttujan nimessä ei ole erityisesti evaluoitavaa, joten merkinnöillä ei ole tuossa tilanteessa tätäkään pientä eroa.

Totta. Jos tarkemmin ajattelee mitä noissa operaatioissa pitäisi konekielitasolla tapahtua, niin kääntäjän todella pitäisi toimia aika erikoisesti että se tässä tapauksessa generoisi erilaista koodia. Eli olette oikeassa että sillä ei ole tässä tapauksessa suorituskyvyn kannalta merkitystä.

Mutta jos asiaa ajatellaan vielä tarkemmin, niin miksi pitäisi opetella tuon pidemmän tavan käyttö, kun siitä ei saada mitään hyötyä? Päinvastoin, kuten standardikin toteaa, siinä tehdään turhaa työtä jos E1:ssä on evaluoitavaa ja lisäksi se on epäselvempi tapa. Lisäksi se on virhealttiimpaa tuon tuplaevaluointinsa vuoksi, koska jos esimerkiksi tuon E1:n evaluointiin vaikuttava keskeytys tulee evaluointien väliin, ollaan todennäköisesti vaikeasti löydettävässä vikatilanteessa.

Metabolix kirjoitti:

Torgo kirjoitti:

Postfix++:n on suoritusjärjestyksessä

Suoritusjärjestyksestä sanotaan kylläkin vain, että korotus tapahtuu ennen seuraavaa puolipistettä. Ehkä sinun pitäisi lukea vielä hieman tarkemmin sitä standardia, jonka nojalla väitteitäsi esität.

Kiitos vain lukutaitoni huolehtimisesta, mutta enemmänkin vikaa on suomenkielisten termien osaamattomuudessani, kuin lukutaidossani. Olisikohan laskujärjestys tai operaattorien arvojärjestys parempia termejä? Kuitenkin, tarkoitan nyt tällä arvojärjestyksellä että postix++:n korkeamman arvojärjestyksen takia esim (a + b++) on sama kuin (a + (b++)), eikä ((a+b)++)

Se miten se toteutetaan konekielitasolla jää kääntäjän tehtäväksi, eikä aina voida luottaa että kääntäjä tekee kaiken järkevästi. Esimerkiksi erään c-kääntäjän referenssimanuaalissa (en kuolemaksenikaan muista minkä. olisko ollut joku hitachin tai hiwaren tekele.) on selitetty postfixin ja prefixin ero näin: Prefix vähentää muuttujan arvoa yhdellä ja palauttaa muutetun arvon evaluoitavaan lausekkeeseen. Postfix ottaa muuttujan vanhan arvon talteen, vähentää muuttujan arvoa ja sen jälkeen palauttaa talteen otetun arvon evaluoitavaan lausekkeeseen. Joissain ohjelmointioppaissa tätä samaa on toistettu, mutta samalla todettu että yleisesti ottaen kääntäjät osaavat tuon optimoida. Eli ne järjestävät konekieliset komennot siten että tuo lisäys tehdään arvojärjestyksestään huolimatta vasta kun lauseke on evaluoitu.

Tässä tapauksessa on vaikea kuvitella, että huonokaan kääntäjä tekisi välitalletusta, koska evaluoitavaa lauseketta ei ole. Mutta yleisesti ottaen kääntäjän optimointi ei päde kaikissa tilanteissa. Miksei siis ottaisi tavaksi käyttää merkintää, joka toimii varmemmin joka tilanteessa, ellei postfixin käyttöä edellytetä?

Mutta ettei nyt eksytä ihan kokonaan alkuperäisestä aiheesta, niin kokeilin äsken tehdä tuon tehtävän ja käytin Metabolixin vinkkiä hyväkseni. Vallan mainio vinkki. Siitä saa näppärästi johdettua erittäin tehokkaan algoritmin, jolle ei tule pituuttaa muutamaa riviä enempää. Ajoin koko rimpsun cygwinin timellä ja sain tuloksen:
real 0m0.080s
user 0m0.010s
sys 0m0.020s

Ja vastauksetkin kelpasivat tarkistuskoneelle. Joten kyllä tuo alittaa Teuron tehokkuusvaatimukset kirkkaasti, vaikka koodiin vielä viilattavaa jäikin ;)