[c++] Array wordt veranderd bij overzetten

[Verwijderd]

Ik wist niet hoe ik het moest omschrijven, want dit is een hele vreemde bug. Eerst even de relevante code:

C++:

for (int i=0;i<number_of_primes;i++)
   printf("%i ",large_prime_table[number_of_primes-i-1]);

printf("\n");

/* priemen achterstevoren overzetten naar geheugenefficiente tabel */
prime_table = new int[number_of_primes];
for (int i=0;i<number_of_primes;i++)
   prime_table[i] = large_prime_table[number_of_primes-i-1];
delete [] large_prime_table;

for (int i=0;i<number_of_primes;i++)
   printf("%i ",prime_table[i]);

Ik ben dus bezig met het volgende voor een hackchallenge: Alle priemen onder een gegeven nummer berekenen, daar van elke 2e weggooien, dan van iedere priem het eerste en laatste cijfer optellen, en dan dat getal ontbinden in factoren (of hoe heette dat ook alweer). Vervolgens die factoren optellen en er komt een antwoord uitrollen. Het vervelende is dat dit binnen 3 seconden moet gebeuren, en daarom ben ik als een gek gaan optimaliseren, maar ik heb schijnbaar iets gebroken, in een stuk code waar ik nog helemaal niet aan gezeten heb

In het programma wordt dus een grote tabel met priemen onder dat getal gegenereerd. Dit gaat van klein naar groot (om snelheidsredenen), en daarom moet de array daarna omgedraaid worden. Dat doet dit stukje code.

Hier even wat output zodat je kunt zien wat er gebeurt:
getal=53

code:

53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2 
53 47 43 41 37 31 9 23 9 17 13 11 7 5 3 2

getal=47

code:

47 43 41 37 31 29 23 19 17 13 11 7 5 3 2 
47 43 41 37 31 9 23 9 17 13 11 7 5 3 2

getal=19

code:

19 17 13 11 7 5 3 2 
19 72 9 11 9 5 3 2

De bovenste rij is steeds van de originele array, de onderste rij is van de nieuwe array na het overzetten. Zoals je in de code kunt zien doorloop ik de arrays op precies dezelfde manier als ik bij het overzetten doe; dus het is mij een raadsel wat er fout gaat.

edit:
Ik heb het zojuist ook op mijn Windows bak getest en die voert het wel normaal uit (Dev-C++). Ik compile op m'n Linux bak dit progje trouwens met:

code:

g++ -o primes -O3 primes.cpp

Heb het ook al zonder optimization geprobeerd, maar dat mocht ook niet baten.

[ Voor 15% gewijzigd door Verwijderd op 05-09-2004 03:24 ]

[LazySod]

Waar wordt large_prime_table weer terug gezet op een geldige waarde?

en daarnaast ... large_prime_table kun je ook in-place omdraaien:

C++:

int *l_Start = large_primes_table;
int *l_End   = large_primes_table + numberofprimes - 1;

while ( l_Start > l_End)
{
     int l_Swap = *l_End;

     *l_End = *l_Start;
     *l_Start = l_Swap;

     l_Start++;
     l_End--;
}

[Verwijderd]

Teruggezet op een geldige waarde? Ik neem aan dat je bedoeld waar hij voor het eerst waarden krijgt ? Dat is (alleen relevante code) zo:

code:

int number_of_primes = 0;
large_prime_table[number_of_primes++] = 2;
for (int i=3;i<=question;i+=2) {
   if (isprime(i,large_prime_table,number_of_primes)) {
      large_prime_table[number_of_primes++] = i;
   }
}

isprime() verandert overigens niets aan de tabel.

Oja, je moet in die loop die je postte de condition omdraaien; l_Start moet kleiner zijn dan l_End. Typootje

[_Squatt_]

LazySod schreef op 05 september 2004 @ 08:14:
en daarnaast ... large_prime_table kun je ook in-place omdraaien:

<knip>lap code</knip>

Waarom het wiel opnieuw uitvinden?

C++:

#include <algorithm>

std::reverse( large_primes_table, large_primes_table + number_of_primes);

[ Voor 5% gewijzigd door _Squatt_ op 05-09-2004 12:11 ]

[MSalters]

Waarom sla je eigenlijk al die priemen op? Dat is niet nodig.

[Reptile209]

Even alle andere optimalisaties terzijde: daar vraagt de TS niet om en dit moet gewoon werken.
Heb je al eens geprobeerd om met een debugger door die kopieer-lus heen te steppen? Wat er gebeurt lijkt er op dat er inderdaad een pointer *ergens* de mist in gaat. Misschien dat je het tijdens het steppen "opeens" ziet. Of voeg direct na regel 9 eens een

C:

printf("%i -> %i",  large_prime_table[number_of_primes-i-1], prime_table[i]);

toe (wel ff je for-lus aanpassen ), zodat je tijdens het kopieeren een "tussenresultaat" krijgt.

[farlane]

Lijkt me dat je i ergens een keer te vaak ophoogt.

[Verwijderd]

Reptile209 schreef op 05 september 2004 @ 12:50:
Even alle andere optimalisaties terzijde: daar vraagt de TS niet om en dit moet gewoon werken.
Heb je al eens geprobeerd om met een debugger door die kopieer-lus heen te steppen? Wat er gebeurt lijkt er op dat er inderdaad een pointer *ergens* de mist in gaat. Misschien dat je het tijdens het steppen "opeens" ziet. Of voeg direct na regel 9 eens een

C:

printf("%i -> %i",  large_prime_table[number_of_primes-i-1], prime_table[i]);

toe (wel ff je for-lus aanpassen ), zodat je tijdens het kopieeren een "tussenresultaat" krijgt.

Bij die tussenresultaten heeft large_prime_table[number_of_primes-i-1] dus ineens de foute values Terwijl ik hem een paar regels eerder op precies dezelfde manier doorloop en output

Verder heb ik met die 2 andere implementaties van een array reversen die hier gepost werden hetzelfde probleem. Maar waardoor kunnen die values van large_prime_table nou veranderd worden na die printfs? Er zit niets tussen

[Buffy]

Hoe zit het met de geheugen allocatie van de large_prime_table? Misschien gebruik je daar geheugen wat alweer is vrijgegeven aan de heap en dan weer gebruikt wordt voor de prime_table. Bij het kopieren muteer je dan gelijk de large_prime_table.

Draai je programma eens met valgrind.

[Verwijderd]

Wat gebeurt er als je de -O3 optie weglaat bij het compileren? (Oudere versies van gcc staan erom bekend dat ze wel eens de code kapot optimaliseren op loop unrolling ed.)

Verder lijkt het me dat je toch een ietwat vreemde aanpak kiest, de veruit snelste manier om priemen te genereren is een implementatie van de zeef van Eratosthenes (zie hier voor een geoptimaliseerde java-implementatie), dus elke andere manier die je kiest om priemen te genereren kost je meer tijd (veelal een factor 10 of meer).

Dan lijkt het me nog zinvol om zo min mogelijk copieeracties te doen als het om een snelheidswedstrijd gaat, een copieeractie kost tijd maar levert geen nieuwe resultaten op en is dus per definitie tijdsverlies als je die tijd niet op een andere manier zinvol benut (door bv. elke tweede priem niet mee te copieeren).

Verder lijkt het me dat doordat je de decimalen van priemen bij elkaar optelt, die uitkomst speciale wiskundige eigenschappen heeft waarmee je evt. nog winst kunt halen bij het ontbinden in factoren en het sommeren van die factoren. (Redelijk moeilijk te verwezelijken en zal vrij veel onderzoek kosten.)

[MSalters]

Decimalen? 10 is een vreemde base, zeker als je intern de priemen binair opslaat. Het enige wat ik zo gauw kan bedenken is dat je laatse cijfer oneven is.
Ik zou het echter heel anders aanpakken: Met een std::vector<bool>, en nergens expliciet je priemgetallen opslaan. Vervolgens loop je door die array heen, en bepaal je voor elke bit telkens het eerste en laatste cijfer. Dat kan heel efficient; het laatste cijfer is namelijk repeterend {1,3,5,7,9 } dus +2 modulo 10. Het eerste cijfer bereken je efficient door index % N. Is dat eerste cijfer opeens 10, dan doe je N=N*10 en is het eerste cijfer weer 1.

[Verwijderd]

Verwijderd schreef op 05 september 2004 @ 15:58:
Wat gebeurt er als je de -O3 optie weglaat bij het compileren? (Oudere versies van gcc staan erom bekend dat ze wel eens de code kapot optimaliseren op loop unrolling ed.)

Verder lijkt het me dat je toch een ietwat vreemde aanpak kiest, de veruit snelste manier om priemen te genereren is een implementatie van de zeef van Eratosthenes (zie hier voor een geoptimaliseerde java-implementatie), dus elke andere manier die je kiest om priemen te genereren kost je meer tijd (veelal een factor 10 of meer).

Dan lijkt het me nog zinvol om zo min mogelijk copieeracties te doen als het om een snelheidswedstrijd gaat, een copieeractie kost tijd maar levert geen nieuwe resultaten op en is dus per definitie tijdsverlies als je die tijd niet op een andere manier zinvol benut (door bv. elke tweede priem niet mee te copieeren).

Verder lijkt het me dat doordat je de decimalen van priemen bij elkaar optelt, die uitkomst speciale wiskundige eigenschappen heeft waarmee je evt. nog winst kunt halen bij het ontbinden in factoren en het sommeren van die factoren. (Redelijk moeilijk te verwezelijken en zal vrij veel onderzoek kosten.)

Zonder optimization had ik al geprobeerd; zonder succes. Verder komt het optimizen nog wel, maar het gaat me vooral om de bug die ik nu tegenkwam. Verder is dit algoritme vergelijkbaar aan de Zeef van Dinges; het programma maakt het eerste element 2, en gaat dan vanaf 3 alle oneven getallen controleren (aan de hand van diezelfde tabel). Omdat de tabel bij 3 nog leeg is, komt 3 gewoon door de test als priem. De eerstvolgende niet-priem oneven getallen (9, 15, 21) zijn deelbaar door 3 dus die vallen af, en dan heb ik ondertussen al genoeg priemen in de tabel staan om betrouwbaar te zijn.

MSalters schreef op 05 september 2004 @ 17:05:
Decimalen? 10 is een vreemde base, zeker als je intern de priemen binair opslaat. Het enige wat ik zo gauw kan bedenken is dat je laatse cijfer oneven is.
Ik zou het echter heel anders aanpakken: Met een std::vector<bool>, en nergens expliciet je priemgetallen opslaan. Vervolgens loop je door die array heen, en bepaal je voor elke bit telkens het eerste en laatste cijfer. Dat kan heel efficient; het laatste cijfer is namelijk repeterend {1,3,5,7,9 } dus +2 modulo 10. Het eerste cijfer bereken je efficient door index % N. Is dat eerste cijfer opeens 10, dan doe je N=N*10 en is het eerste cijfer weer 1.

Ja, maar dat gaat me qua c++ de pet teboven

[LazySod]

Verwijderd schreef op 05 september 2004 @ 11:52:
Teruggezet op een geldige waarde? Ik neem aan dat je bedoeld waar hij voor het eerst waarden krijgt ? Dat is (alleen relevante code) zo:

Je doet een delete[] van de variable. Daarna zet je er niets meer in terug. Is geen probleem, behalve als je hem nog eens gebruikt erna. Ik had ergens een statement als

code:

large_prime_table = prime_table;

verwacht aan het einde van de code die de tabel omdraait.

Oja, je moet in die loop die je postte de condition omdraaien; l_Start moet kleiner zijn dan l_End. Typootje

[/quote]

Eww!! Ack, inderdaad.. Ik moet ook niet om 08:10 achter de pc gaan zitten op een zondag ochtend .. Zal wel snel geloopt hebben zo.. *lol*

[Verwijderd]

Verwijderd schreef op 05 september 2004 @ 19:34:
Zonder optimization had ik al geprobeerd; zonder succes. Verder komt het optimizen nog wel, maar het gaat me vooral om de bug die ik nu tegenkwam.

Mja, die bug is lastig. Het lijkt me dat je of met een side-effect van een ander deel van je code te maken hebt, of dat gcc gewoon brakke code genereert. Als je wat verstand hebt van assembly zou je misschien de assembly output kunnen genereren (met de -S en evt. de -mintel-syntax opties van gcc) en die kunnen doorspitten.

Verder is dit algoritme vergelijkbaar aan de Zeef van Dinges; het programma maakt het eerste element 2, en gaat dan vanaf 3 alle oneven getallen controleren (aan de hand van diezelfde tabel). Omdat de tabel bij 3 nog leeg is, komt 3 gewoon door de test als priem. De eerstvolgende niet-priem oneven getallen (9, 15, 21) zijn deelbaar door 3 dus die vallen af, en dan heb ik ondertussen al genoeg priemen in de tabel staan om betrouwbaar te zijn.

Ik nam al aan dat je het zo deed, maar dat is zeker niet vergelijkbaar met een zeef-algoritme, jij moet voor elk nieuw oneven getal dat je wilt toevoegen een toenemend aantal proefdelingen doen (hoe langer de lijst is, door hoe meer priemen je moet delen om te kijken of dat een rest oplevert).

Een zeef werkt (zoals MSalters dat aanduidt) door elk (oneven) getal te representeren als een bool in een array en door vervolgens alle composieten (getallen die niet priem zijn) "weg te strepen" door de beteffende bool in de array op true te zetten; de zeef van Eratosthenes gebruikt bij dat wegstrepen geen (dure) proefdelingen en is dus zeer efficiënt.

[Verwijderd]

Verwijderd schreef op 06 september 2004 @ 13:13:
[...]


Mja, die bug is lastig. Het lijkt me dat je of met een side-effect van een ander deel van je code te maken hebt, of dat gcc gewoon brakke code genereert. Als je wat verstand hebt van assembly zou je misschien de assembly output kunnen genereren (met de -S en evt. de -mintel-syntax opties van gcc) en die kunnen doorspitten.

Iemand hierboven noemde valgrind, ik zal daar eens mee gaan prutsen, als na het herschrijven van mijn engine () de bug zich nog voordoet Assembly heb ik wel een heel klein beetje verstand van (tutorial gelezen op blacksun) maar niet zo dat ik daar spannende dingen mee kan

[...]

Ik nam al aan dat je het zo deed, maar dat is zeker niet vergelijkbaar met een zeef-algoritme, jij moet voor elk nieuw oneven getal dat je wilt toevoegen een toenemend aantal proefdelingen doen (hoe langer de lijst is, door hoe meer priemen je moet delen om te kijken of dat een rest oplevert).

Ik schnap, maar de meeste getallen die ik tegenkom zijn al door 3 of 5 deelbaar (hoe kleiner, hoe meer kans)

Een zeef werkt (zoals MSalters dat aanduidt) door elk (oneven) getal te representeren als een bool in een array en door vervolgens alle composieten (getallen die niet priem zijn) "weg te strepen" door de beteffende bool in de array op true te zetten; de zeef van Eratosthenes gebruikt bij dat wegstrepen geen (dure) proefdelingen en is dus zeer efficiënt.

Maar hoe wil je die dan wegstrepen zonder element voor element proefdelingen te doen? Of vermenigvuldig je dan het getal waar je mee bezig bent een paar keer om op die plaatsen in de array true in te vullen? Ik kan me btw wel voorstellen dat vermenigvuldigen sneller is omdat je immers met eerst de modulus en dan de deling 2 berekeneningen uitvoert.

Maar als je weet dat 2 het enige even priemgetal is, dus weet dat het efficienter is om alleen de oneven getallen op te nemen in die lijst, is het dan niet moeilijker om daarmee de plaats van de multiples van het priemgetal in een array vast te stellen? Want dat is weer allemaal foutgevoelig hoofdrekenwerk wat dan optreedt...

Beetje raar verwoord, maarja

[MSalters]

Nee, dat valt mee. Neem de lijst 1,3,5,7,9,11,13,15,17,19.
Het eerste getal wat je tegenkomt, op p[0] is een special case, die negeer je. Vervolgens kom je de 'true' tegen op p[1] (dat is 1+2*1=3), dus zet je p[4](=1+2*4=9) op false, p[7](1*2+7), en verder alle p[1+N*3]. Daarna is p[2] nog steeds true, dus 5 is priem, en je streept p[7]=15, p[12], [2+5*N] weg.

In theorie kun je dit uitbreiden naar de special cases 2 en 3, maar de complexiteit neemt snel toe. Met de serie q[] = { 1,5,7,11,13,17,19,23, 25, 29 } is het lastiger waardes van q te berekenen voor een gegeven index, of snel multipliers te vinden. Het lukt wel, kijk maar nat het patroon 25,35,55,65,85,95 - dat repeteert met een periode van 2*3*5, maar je moet al twee veschillende stappen (20 en 10) gebruiken. Niet de moeite waard.

[Verwijderd]

Verwijderd schreef op 06 september 2004 @ 19:45:
Ik schnap, maar de meeste getallen die ik tegenkom zijn al door 3 of 5 deelbaar (hoe kleiner, hoe meer kans)

Ja, weet ik, de kans dat een getal n priem is, is 1 / log(n). De proefdeling door 2 elimineert de 1/2 van de getallen, de proefdeling door 3 elimineert 1/3 van de getallen en beide samen 2/3 van de getallen, enz.; maar het punt is dat je om een volgende priem te vinden nog steeds door alle voorgaande priemen moet delen en dat schiet niet op als je bv. de eerste 1.000.000 priemgetallen moet genereren (het zeefalgoritme waar ik in een vorige post naar link berekent die in ongeveer 0.5 seconden op een 1 gigahertz cpu, dat ga je op jouw manier niet niet redden).

Maar hoe wil je die dan wegstrepen zonder element voor element proefdelingen te doen? Of vermenigvuldig je dan het getal waar je mee bezig bent een paar keer om op die plaatsen in de array true in te vullen? Ik kan me btw wel voorstellen dat vermenigvuldigen sneller is omdat je immers met eerst de modulus en dan de deling 2 berekeneningen uitvoert.

MSalters legt dat prima uit en die link die ik postte is een werkende implementatie van dat verhaal, die omschrijven van java naar c++ is een kwestie van minuten. Je hebt dan maar een probleem: een zeef werkt door uit een bepaalde getallenrange weg te strepen en hoeveel priemgetallen je uiteindelijk overhoudt is nogmaar de vraag. (Je weet wel dat in een range van [1,n] ongeveer n / (log(n) - 1) priemen zitten, maar niet of het er net meer of minder zijn).

[Verwijderd]

MSalters schreef op 06 september 2004 @ 23:35:
Nee, dat valt mee. Neem de lijst 1,3,5,7,9,11,13,15,17,19.
Het eerste getal wat je tegenkomt, op p[0] is een special case, die negeer je. Vervolgens kom je de 'true' tegen op p[1] (dat is 1+2*1=3), dus zet je p[4](=1+2*4=9) op false, p[7](1*2+7), en verder alle p[1+N*3]. Daarna is p[2] nog steeds true, dus 5 is priem, en je streept p[7]=15, p[12], [2+5*N] weg.

In theorie kun je dit uitbreiden naar de special cases 2 en 3, maar de complexiteit neemt snel toe. Met de serie q[] = { 1,5,7,11,13,17,19,23, 25, 29 } is het lastiger waardes van q te berekenen voor een gegeven index, of snel multipliers te vinden. Het lukt wel, kijk maar nat het patroon 25,35,55,65,85,95 - dat repeteert met een periode van 2*3*5, maar je moet al twee veschillende stappen (20 en 10) gebruiken. Niet de moeite waard.

Daar zal ik vanmiddag eens op mijn gemak naar kijken

Verwijderd schreef op 07 september 2004 @ 00:58:
[...]


Ja, weet ik, de kans dat een getal n priem is, is 1 / log(n). De proefdeling door 2 elimineert de 1/2 van de getallen, de proefdeling door 3 elimineert 1/3 van de getallen en beide samen 2/3 van de getallen, enz.; maar het punt is dat je om een volgende priem te vinden nog steeds door alle voorgaande priemen moet delen en dat schiet niet op als je bv. de eerste 1.000.000 priemgetallen moet genereren (het zeefalgoritme waar ik in een vorige post naar link berekent die in ongeveer 0.5 seconden op een 1 gigahertz cpu, dat ga je op jouw manier niet niet redden).


[...]


MSalters legt dat prima uit en die link die ik postte is een werkende implementatie van dat verhaal, die omschrijven van java naar c++ is een kwestie van minuten. Je hebt dan maar een probleem: een zeef werkt door uit een bepaalde getallenrange weg te strepen en hoeveel priemgetallen je uiteindelijk overhoudt is nogmaar de vraag. (Je weet wel dat in een range van [1,n] ongeveer n / (log(n) - 1) priemen zitten, maar niet of het er net meer of minder zijn).

Ik heb gisteren het prog herschreven, en kan nu in 1.5s de berekeningen uitvoeren. Hoe groot de array moet zijn doet er eigenlijk niet echt toe, want 9999999 bools (bits) is niet zoveel op 512 MB Krijg nu wel een segfault, maar ja, kwestie van debuggen dus.

[Verwijderd]

Verwijderd schreef op 07 september 2004 @ 10:08:
Hoe groot de array moet zijn doet er eigenlijk niet echt toe, want 9999999 bools (bits) is niet zoveel op 512 MB

Een bool wordt meestal niet als een bit in het geheugen gezet. Het zou in hele extreme gevallen wel space effecient zijn, maar het kost veel meer cycles om een enkele bit uit het geheugen te extracten dan (afhankelijk van de cpu architectuur) een byte of het systeem woord. Gelukkig kun je dit altijd in C++ makkelijk controleren met de sizeof operator. In veel C++ implementaties zal dit 1 teruggeven ( 1 byte).

Natuurlijk is 9999999 bools nog steeds peanuts met 512MB,

[Verwijderd]

Verwijderd schreef op 07 september 2004 @ 11:13:
Een bool wordt meestal niet als een bit in het geheugen gezet. Het zou in hele extreme gevallen wel space effecient zijn, maar het kost veel meer cycles om een enkele bit uit het geheugen te extracten dan (afhankelijk van de cpu architectuur) een byte of het systeem woord. Gelukkig kun je dit altijd in C++ makkelijk controleren met de sizeof operator. In veel C++ implementaties zal dit 1 teruggeven ( 1 byte).

Natuurlijk is 9999999 bools nog steeds peanuts met 512MB,

Mja, theoretisch klopt je verhaal maar je vergeet de caching, in een bitvector sla je 8x of zelfs 32x zoveel getallen op als in een bytevector of een wordvector; en omdat het zeefalgoritme voor iedere gevonden priem de vector vrijwel compleet doorloopt betekent dat theoretisch 8x of 32x zo veel cache loads als de vector veel groter is dan de cache. Normalerwijze kosten die cache loads meer tijd dan de bit-operaties (En het is op die manier mogelijk alle 32-bit priemen te vinden met een bitvector van 256MB, ipv. met een bytevector van 2GB of een wordvector van 8GB).

[MSalters]

Verwijderd schreef op 07 september 2004 @ 11:13:
[...]
Een bool wordt meestal niet als een bit in het geheugen gezet.

Nee, maar wel als je een std::vector<bool> gebruikt.

[.oisyn]

Is dat standard behaviour of implementation dependent?
.edit: ah ja, 23.2.5

[ Voor 19% gewijzigd door .oisyn op 07-09-2004 15:10 ]

[Verwijderd]

MSalters schreef op 07 september 2004 @ 15:04:
[...]

Nee, maar wel als je een std::vector<bool> gebruikt.

Juist ja, maar dat maakt std:vector<bool> mijns inziens wel 'raar' in vergelijking met ander instantiaties van vector<>.

[Soultaker]

Tja, wat kan jou het schelen? De klasse gedraagt zich hetzelfde als de andere klassen, alleen is de performance beter.

[Verwijderd]

Soultaker schreef op 07 september 2004 @ 15:53:
Tja, wat kan jou het schelen? De klasse gedraagt zich hetzelfde als de andere klassen, alleen is de performance beter.

Er zijn heel wat implicaties van dit gedrag. Ik kan er naast zitten, maar als het verplicht is (via de standaard, en dus niet implementatie specificiek) , dan moet elke implementatie dus perse space effecient zijn, terwijl je mischien ook wel eens speed efficient will zijn.

[farlane]

Verwijderd schreef op 07 september 2004 @ 21:48:
Er zijn heel wat implicaties van dit gedrag. Ik kan er naast zitten, maar als het verplicht is (via de standaard, en dus niet implementatie specificiek) , dan moet elke implementatie dus perse space effecient zijn, terwijl je mischien ook wel eens speed efficient will zijn.

In dat geval neem je toch een vector<int>, of whatever de native type van je platform is ? Volgens mij was vector<bool> nou net voor de space efficiency geschreven.

[.oisyn]

Verwijderd schreef op 07 september 2004 @ 21:48:
[...]


Er zijn heel wat implicaties van dit gedrag. Ik kan er naast zitten, maar als het verplicht is (via de standaard, en dus niet implementatie specificiek) , dan moet elke implementatie dus perse space effecient zijn, terwijl je mischien ook wel eens speed efficient will zijn.

Het is via de standaard verplicht, het puntje 23.2.5 wat ik eerder al aanhaalde

quote: http://www.kuzbass.ru/doc...ners.html#lib.vector.bool

-1- To optimize space allocation, a specialization of vector for bool elements is provided:
[.. vector<bool> definitie ..]
-2- reference is a class that simulates the behavior of references of a single bit in vector<bool>.

farlane schreef op 07 september 2004 @ 21:54:

In dat geval neem je toch een vector<int>, of whatever de native type van je platform is ? Volgens mij was vector<bool> nou net voor de space efficiency geschreven.

Of vector<char> idd

[MSalters]

De gangbare opinie is dat std::deque<bool> het alternatief is wat je wil hebben indien space efficiency niet belangrijk is.

[Verwijderd]

dit is toch voor hackquest?

het makkelijkste is bij zulke dingen alles wat je kan uit te rekenen eerst te doen, en dan pas om invoer vragen.
zo hoef je niet alles binnen die 3 sec uit te halen en dat scheelt een hoop

ook handig om het zo snel te halen zijn de windows functies voor het clipboard

[ Voor 9% gewijzigd door Verwijderd op 07-09-2004 23:09 ]

[Verwijderd]

Dat was inderdaad ook mijn eerste insteek, maar toen het prototype van mijn prog na 8 uur nog niet op 0,01% was van het te verrichten werk haakte ik toch af

Nu ben ik het zo ver mogelijk aan het optimaliseren, kijken hoever ik het kan pushen

[Soultaker]

Ik kan je wel voorspellen dat je met low-level optimalisatie zeker geen factor 100 gaat halen (je mag blij zijn met een factor 10). Misschien kun je dus beter over een slimmere aanpak nadenken.

[Soultaker]

MSalters schreef op 07 september 2004 @ 22:39:
De gangbare opinie is dat std::deque<bool> het alternatief is wat je wil hebben indien space efficiency niet belangrijk is.

Beetje raar om een heel ander idioom te kiezen omdat de space behaviour je niet bevalt. Dan kun je mensen ook wel weer gaan aanraden om std::vector<char>'s te gaan gebruiken in plaats van std::string's (zoals ik heb een bedrijf heb zien doen omdat std::string's geen copy-on-write boden of iets dergelijks).

Ik kan me trouwens weinig praktijksituaties voorstellen waarbij je per se wil dat elke bool een byte inneemt. Echte performance-winst zal er toch bijna nooit zijn, of je moet met een kleine vector werken waar je heel intensief mee werkt.

[.oisyn]

Het vervelende van bitfields is dat een write voorafgegaan moet worden door een read, wat weer de nodige stalls met zich mee kan brengen. Als je een hele grote vector hebt en je gaat op heel veel random posities wat aanpassen dan kan dat weleens enorm traag worden.

Dit is natuurlijk wel een vrij uitzonderlijke situatie, in het gros van de gevallen is de normale vector<bool> beter

[ Voor 20% gewijzigd door .oisyn op 08-09-2004 01:00 ]

[Verwijderd]

.oisyn schreef op 08 september 2004 @ 00:59:
Het vervelende van bitfields is dat een write voorafgegaan moet worden door een read, wat weer de nodige stalls met zich mee kan brengen. Als je een hele grote vector hebt en je gaat op heel veel random posities wat aanpassen dan kan dat weleens enorm traag worden.

Dat valt wel mee, omdat je bij het schrijven van bits gebruik kunt maken van het feit dat er toch gelezen moet worden door expliciet dat bit te lezen en het alleen te schrijven als het niet de juiste waarde heeft (dmv. een XOR). Ik heb een vrij snelle zeef geschreven en vanuit die praktijk sprekend leverde die optimalisatie ongeveer 23% (!) tijdwinst op.

[.oisyn]

Maar je zeef doet geen random maar vrijwel sequentieel access, pas bij hele grote getallen wordt het echt random (random als in dat 2 opeenvolgende getallen niet meer in de cache passen)

Trouwens

en het alleen te schrijven als het niet de juiste waarde heeft (dmv. een XOR).

Hoe wil je dat implementeren dan? Als je al gelezen hebt is een write niet zo duur, dat is simpelweg een write naar de cache en de cache wordt dirty, dat zorgt verder niet voor stalls. Geen idee wat de onderliggende asm code wordt, maar als er van branches gebruik wordt gemaakt kun je de controle beter achterwege laten, ivm mogelijke pipeline flushes bij een misprediction. Tenzij je de cmov gebruikt, maar volgens mij kun je nog beter gewoon altijd schrijven

(Een andere mogelijke optimalisatie, voor gebruik van de zeef bij hele grote priemen, is misschien door gebruik te maken van intervallen. Ipv bitfields codeer je gewoon van waar tot waar de getallen al zijn weggestreept. Als een getal in de intervalboom voorkomt dan hoef je niets te doen, anders moet je de naastliggende intervallen mergen)

[ Voor 19% gewijzigd door .oisyn op 08-09-2004 01:48 ]

[Soultaker]

edit:
Hier stond iets wat niet klopte.

[ Voor 92% gewijzigd door Soultaker op 08-09-2004 01:45 ]

[Verwijderd]

.oisyn schreef op 08 september 2004 @ 01:43:
Maar je zeef doet geen random maar vrijwel sequentieel access, pas bij hele grote getallen wordt het echt random (random als in dat 2 opeenvolgende getallen niet meer in de cache passen)

Agreed, maar op eoa. manier zijn cache-writes een stuk duurder dan reads (en de stall is er sowieso bij bit operaties).

Hoe wil je dat implementeren dan?

C++:

#ifdef NO_CACHE
                        index>>= SHIFT;
                        if(val) base_[index]|= mask;
                        else base_[index]&= ~mask;
#else
                        word_type* p= base_ + (index >> SHIFT);
                        if(val != static_cast<bool>(*p & mask)) *p^= mask;
#endif

Als je al gelezen hebt is een write niet zo duur, dat is simpelweg een write naar de cache en de cache wordt dirty, dat zorgt verder niet voor stalls.

Zoals ik als zei levert het definen van NO_CACHE bijna een kwart tragere code op, ook bij kleine bitfields (ik heb ook andere operaties geprobeerd, aan pointers vs. indexing ligt het niet).

[.oisyn]

Je hebt idd gelijk, naarmate de getallen groter worden blijven er natuurlijk steeds minder en minder getallen over om weg te strepen. De branchpredictor doet in die gevallen gewoon goed werk, over het algemeen zal de test failen waardoor er niet geschreven hoeft te worden.

[.oisyn]

Even een wat oudere post ophalen

Verwijderd schreef op 05 september 2004 @ 15:58:
de veruit snelste manier om priemen te genereren is een implementatie van de zeef van Eratosthenes (zie hier voor een geoptimaliseerde java-implementatie)

Overigens kan die java implementatie die je toen gemaakt hebt nog iets meer dan een factor 2 (die winst haalde ik met mijn c++ code iig) sneller gemaakt worden. Je kijkt met de zeef namelijk welke getallen niet priem zijn, en je begint bij 3, en vervolgens steeds 2 verder. Nou hoef je voor de zeef eigenlijk alleen maar priemgetallen te gebruiken, van de anderen weet je al dat je ze al hebt weggestreept. Zo worden de meervouden van 9 bijvoorbeeld ook al weggestreept door de 3, dus die hoef je eigenlijk niet te doen.

In plaats van steeds 2 op te tellen bij het getal waar je steeds de meervouden van gaat wegstrepen, ga je gewoon op zoek naar het eerstvolgende getal in de zeef die je nog niet weggestreept hebt. Als je de 7 hebt gehad ontdek je dan dat de 9 al is weggestreept, en ga je verder met de 11. Dat scheelt weer N / 9 wegstreep-acties. Dat geldt natuurlijk ook voor de 15, 21, 25, etc., en hoe verder je komt, hoe vaker dat voor gaat komen.

Met andere woorden:

C++:

int m = (int)std::sqrt ((float)NUM_ELEMENTS);

for (int i = 3; i < m;)
{
    for (int j = i * 2; j < NUM_ELEMENTS; j += i)
        buf[j >> 1] = false;

    while (!buf[(i += 2) >> 1]);  // zoek de eerstvolgende priem
}

Hiermee bereken ik alle priemen onder de 100.000.000 in slechts 0.19 seconden op een athlon xp 2500+ @ 1.93 GHz
(Bovenstaande is overigens niet letterlijk mijn code. Dit zou kunnen werken met een vector<bool>, ware het niet dat zo'n vector<bool> een factor 6 langzamer is dan mijn eigen bit-array klasse die eveneens gebruik maakt van de schrijfwijze van mietje)

[ Voor 15% gewijzigd door .oisyn op 08-09-2004 03:57 ]

[Verwijderd]

Hmm, volgens mij mis ik iets, maar ik post de relevante code nog eens, nu met (een beetje) commentaar en zonder de java-optimalisatie:

Java:

l = (Math.sqrt(MAX) - 1.0) / 2.0;
for(i= 1; i <= l; ++i) {
  if(!numbers[i]) { // Zoek de volgende priem
    a= i * 2 + 1; // Zorg voor oneven veelvouden
    for(j= i + a; j < MAXHALF; j+= a) {
    numbers[j]= true;
    }
  }
}

Dus dat if-statement doet volgens mij wat jouw while-statement doet (alleen checkt mijn versie na elk increment van i op de eindconditie i <= l). Verder streept mijn code enkel elk oneven veelvoud van een priem weg (dus als het ware int j = i * 3 en j += i * 2 in jouw code) waardoor jouw code ook even getallen uit de lijst probeert weg te strepen (een veel voorkomende fout overigens). Dat zou dus evt. een verklaring kunnen zijn voor de snelheid, tenzij ik iets mis (niet onmogelijk op dit uur).

edit: er staat een fout in die wortel-toestand van de originele code, die ik hier maar verbeterd heb (zucht)
edit2: toch niet, tijd voor het bed...

[ Voor 14% gewijzigd door Verwijderd op 08-09-2004 04:25 ]

[.oisyn]

Doh, je hebt gelijk, ik had compleet om die if heen gelezen
Dat van die veelvouden klopt, ik had het hier wel toegepast, maar ben het in mijn post vergeten (dat was dan ook geen copypaste, daar was mijn code te ranzig voor )

[.oisyn]

Overigens kun je beginnen met wegstrepen vanaf het kwadraat van het getal. Het getal * 3 is namelijk al weggestreept door 3 zelf. Feitelijk hoef je ook alleen maar het getal * p weg te strepen, waarbij p een priemgetal is. Als p namelijk geen priem is kun je het ontbinden in factoren, en is het getal dus al weggestreept omdat je een van die factoren al gehad hebt. Eigenlijk zou je de al gefilterde priemen ook daar moeten gebruiken om de volgende veelvoud te bepalen. Eens kijken wat dat nog uitmaakt

.edit: dat wordt echter een beetje vervelend, omdat je de status van de zeef moet hebben voor dat je aan het wegstrepen begint. Als je bijvoorbeeld bij de 3 begint, dan kun je 9 wegstrepen. De volgende factor is 5, dus 15 kan ook. Daarna 7, dus 21 streep je ook weg. Dan controleer je echter of 9 een priem is, wat het niet blijkt te zijn omdat je die al hebt weggestreept, maar 3*9 moet je natuurlijk ook nog wegstrepen. In principe treedt dit alleen op bij de factoren die een veelvoud zijn van het getal waarvan je z'n veelvouden aan het wegstrepen bent (), dus heb je weer een extra check nodig om dat te controleren. Ik denk dat je dan zo langzamerhand op een punt komt waarop het voordeel niet opweegt tegen de overhead die het met zich mee brengt.

[ Voor 43% gewijzigd door .oisyn op 08-09-2004 04:51 ]

[farlane]

.oisyn schreef op 08 september 2004 @ 04:27:
In principe treedt dit alleen op bij de factoren die een veelvoud zijn van het getal waarvan je z'n veelvouden aan het wegstrepen bent (), dus heb je weer een extra check nodig om dat te controleren.

Ik volg het met veel interesse maar misschien is het verstandig om de volgende keer wat eerder naar bed te gaan.

[Verwijderd]

Dit is wat ik gisteren even in elkaar geflansd heb:

C++:

    /* initialize bitstring: all primes */
    for (int i=0;i<=question;i++) {
        primes[i] = 1;
    }

    /* strip away multiples of first numbers */
    for (int i=2;i<=question;i++) {
        for (int j=2;(i*j)<=sqrt(question);j++) {
            primes[i*j] = 0;
        }
    }   

Zeker niet perfect, maar dit vindt in 3 seconden (2.998 ) alle priemen onder 9999999
Ik ga er vanavond nog aan werken, dat kan sneller!

En is er toevallig een snellere manier om al die bools op true te zetten? Is er een snellere manier om:

C++:

sprintf(string,"%i",getal);
first_digit = string[0] - '0';

te doen?

Verder zal ik vanavond de discussie van .oisyn en mietje eens goed bekijken

[Verwijderd]

.oisyn schreef op 08 september 2004 @ 04:27:
Overigens kun je beginnen met wegstrepen vanaf het kwadraat van het getal. Het getal * 3 is namelijk al weggestreept door 3 zelf.

Hmm, klopt, door te beginnen met het kwadraat win je iets, weer 5% erbij (Dus alleen bij het kwadraat vd. priem beginnen en dan alle oneven veelvouden wegstrepen.) Ik heb overigens ook jouw versie zonder stricte eindconditie-test tegen de mijne getest; mijn versie is een fractie sneller.

Verwijderd schreef op 08 september 2004 @ 09:28:
Zeker niet perfect, maar dit vindt in 3 seconden (2.998 ) alle priemen onder 9999999
Ik ga er vanavond nog aan werken, dat kan sneller!

Zeker, je gebruikt nu een ander zeef-algoritme (een multiplicatieve zeef), de zeef van Eratosthenes is een stuk sneller. Daarnaast kun je de boel efficiënter krijgen door alleen de oneven getallen op te slaan, dat kost de helft minder operaties want je kunt dan over elk even getal heen springen zonder het weg te strepen.

En is er toevallig een snellere manier om al die bools op true te zetten?

Ja, met memset(), maar als je die bools alloceert met new dan worden ze automatisch allemaal op false gezet (tenzij je ze met true initialiseert).

Is er een snellere manier om:

C++:

sprintf(string,"%i",getal);
first_digit = string[0] - '0';

te doen?

In principe wel, maar dat loont zich niet omdat je die wortel maar één keer in je hele programma hoeft uit te rekenen.

[ Voor 7% gewijzigd door Verwijderd op 08-09-2004 13:16 . Reden: edit: stond een foutje in ]

[MSalters]

Verwijderd schreef op 08 september 2004 @ 13:08:
[...]
Ja, met memset(), maar als je die bools alloceert met new dan worden ze automatisch allemaal op false gezet (tenzij je ze met true initialiseert).

Eh? new bool; niet hoor. new bool( false ); of new bool( ); wel.

Overigens, std::vector<bool> zet ze allemaal netjes op false. Aangezien de exacte waare niet uitmaakt, is de initiele waarde false net zo goed als true, maar er is ook een twee-arg versie ctor waamee je ze allemaal initieel op true kunt zetten.

[Verwijderd]

MSalters schreef op 08 september 2004 @ 13:25:
Eh? new bool; niet hoor. new bool( false ); of new bool( ); wel.

Hmm, ik dacht dat new bool[x] altijd de default ctor van alle bools aanroept en dat new bool[x](y) naar een geschikte ctor voor het type van y zoekt en die dan voor alle bools aanroept?

[Verwijderd]

Verwijderd schreef op 08 september 2004 @ 13:08:
[...]
Zeker, je gebruikt nu een ander zeef-algoritme (een multiplicatieve zeef), de zeef van Eratosthenes is een stuk sneller. Daarnaast kun je de boel efficiënter krijgen door alleen de oneven getallen op te slaan, dat kost de helft minder operaties want je kunt dan over elk even getal heen springen zonder het weg te strepen.

Hmm, dan heb ik dus die Zeef van Eratosthenes niet goed begrepen. Ik zou toch zweren dat het zo was: een tabel met alle (oneven) getallen behalve 1, multiples van het eerste getal (3) wegstrepen, multiples van het volgende getal (5) wegstrepen, etc..

[...]
In principe wel, maar dat loont zich niet omdat je die wortel maar één keer in je hele programma hoeft uit te rekenen.

Dit gebruik ik in een loop die op de helft van de priemen toegepast wordt.

[.oisyn]

.oisyn schreef op 08 september 2004 @ 04:27:
.edit: dat wordt echter een beetje vervelend, omdat je de status van de zeef moet hebben voor dat je aan het wegstrepen begint. Als je bijvoorbeeld bij de 3 begint, dan kun je 9 wegstrepen. De volgende factor is 5, dus 15 kan ook. Daarna 7, dus 21 streep je ook weg. Dan controleer je echter of 9 een priem is, wat het niet blijkt te zijn omdat je die al hebt weggestreept, maar 3*9 moet je natuurlijk ook nog wegstrepen. In principe treedt dit alleen op bij de factoren die een veelvoud zijn van het getal waarvan je z'n veelvouden aan het wegstrepen bent (), dus heb je weer een extra check nodig om dat te controleren. Ik denk dat je dan zo langzamerhand op een punt komt waarop het voordeel niet opweegt tegen de overhead die het met zich mee brengt.

Net toen ik gisteravond naar bed ging kwam ik met een oplossing. Je kunt namelijk eerst alle "veelvouden van de veelvouden" wegstrepen. Oftewel, als je met 3 bezig bent, dan wil je dus 3 * f wegstrepen. Maar dan begin je eerst met alle waarden van f die zelf een veelvoud zijn van 3 (en oneven zijn), dus 3 * 3, 3 * 9, 3 * 15, 3 * 21, ...

Je ziet dat er bij het factor steeds 6 wordt opgeteld, oftewel 2 maal het getal. De getallen die hierna nog over zijn in de zeef zijn 3, 5, 7, 11, 13, 17, 19, 23, ...
Vervolgens pak de getallen die groter zijn dan 3 ook nog eens als factoren om weg te strepen, dus 3 * 5, 3 * 7, 3 * 11, ...

Eens even wat in elkaar vrotten

[.oisyn]

Argh
Volgens mij een behoorlijke speedboost, alleen ik heb geen vergelijkingsmateriaal aangezien ik erachter kwam dat ik mijn bitarray initialiseerde met de dword 1 ipv 0xffffffff

Daardoor is het geheel natuurlijk wel een stuk langzamer geworden, de timing die ik voorheen gaf klopt dus voor geen meter. Ik haal nu 0.72 seconden voor alle priemen onder de 50.000.000

Eens even de oude methode gebruiken, kijken wat dat wordt

.edit: mwoa, het is ongeveer even snel als beginnen bij het kwadraat en dan simpelweg weg gaan strepen

.edit2: overigens haal ik nu wel weer extra snelheid met mijn aangepaste algoritme door de getallen altijd te setten ipv de controle uit te voeren. Waarschijnlijk omdat ik nu gewoon zo weinig "overdraw" heb dat het niet meer loont om te controleren of een bit al gecleared is of niet.

[ Voor 33% gewijzigd door .oisyn op 08-09-2004 15:47 ]

[Verwijderd]

.oisyn schreef op 08 september 2004 @ 15:16:
Daardoor is het geheel natuurlijk wel een stuk langzamer geworden, de timing die ik voorheen gaf klopt dus voor geen meter. Ik haal nu 0.72 seconden voor alle priemen onder de 50.000.000

Hmm, als ik het verschil in CPU-power wegreken (ik heb een Athlon XP 1600+) zitten we nu op ongeveer een zelfde performance.

.edit2: overigens haal ik nu wel weer extra snelheid met mijn aangepaste algoritme door de getallen altijd te setten ipv de controle uit te voeren. Waarschijnlijk omdat ik nu gewoon zo weinig "overdraw" heb dat het niet meer loont om te controleren of een bit al gecleared is of niet.

Maar als je die twee mogelijke optimalisaties tegen elkaar afzet maakt het onder de streep weinig verschil, of begrijp ik je nu verkeerd?

[Verwijderd]

Verwijderd schreef op 08 september 2004 @ 13:50:
Hmm, dan heb ik dus die Zeef van Eratosthenes niet goed begrepen. Ik zou toch zweren dat het zo was: een tabel met alle (oneven) getallen behalve 1, multiples van het eerste getal (3) wegstrepen, multiples van het volgende getal (5) wegstrepen, etc..

Op zich klopt je beschrijving, maar je implementatie doet dat wel op een erg omslachtige manier. In principe (als je elk getal als een bool representeert, dus ook de even getallen) is het dit algoritme:

C++:

unsigned max= static_cast<unsigned>(std::sqrt(question));
for(unsigned i= 2; i <= max; ++i) {
    if(primes[i]) {
        for(unsigned j= i * i; j < question; j+= i) {
            primes[j]= false;
        }
    }
}

Als je alleen de oneven getallen wilt opslaan, moet je alle even getallen en veelvouden in het algoritme vermijden, je krijgt dan iets zoals ik in een vorige post geplaatst heb.

Dit gebruik ik in een loop die op de helft van de priemen toegepast wordt.

Nee, dat is iets anders. Dat stukje code uit deze post moet alle veelvouden van 2 wegstrepen (4, 6, 8, enz.) en ook alle even veelvouden van hogere priemgetallen (bij 3 de getallen 12, 18, 24, enz., bij 5 de getallen 30, 40, 50, enz.). Door die even veelvouden buiten beschouwing te laten (en niet op te slaan) hoef je dus de helft minder getallen weg te strepen.

[ Voor 5% gewijzigd door Verwijderd op 08-09-2004 16:44 ]

[Soultaker]

Verwijderd schreef op 08 september 2004 @ 13:08:
Daarnaast kun je de boel efficiënter krijgen door alleen de oneven getallen op te slaan, dat kost de helft minder operaties want je kunt dan over elk even getal heen springen zonder het weg te strepen.

Dat scheelt alleen in het geheugengebruik (en dan eventueel in verbeterde caching enzo) maar verder boeit het echt niet. Alle even getallen streep je als eerste weg en als ze weggestreept zijn hoef je er toch praktisch geen werk voor te verrichten.

[.oisyn]

Verwijderd schreef op 08 september 2004 @ 16:18:
Maar als je die twee mogelijke optimalisaties tegen elkaar afzet maakt het onder de streep weinig verschil, of begrijp ik je nu verkeerd?

Ik snap je nu niet helemaal... Mijn aangepaste algoritme en altijd setten is net ietsjes sneller dan jouw algoritme en de controle bij het setten van een bit. Als ik de controle gebruik met mijn aangepaste algoritme zijn ze ongeveer net zo snel.

[Verwijderd]

Soultaker schreef op 08 september 2004 @ 17:48:
Dat scheelt alleen in het geheugengebruik (en dan eventueel in verbeterde caching enzo) maar verder boeit het echt niet. Alle even getallen streep je als eerste weg en als ze weggestreept zijn hoef je er toch praktisch geen werk voor te verrichten.

Het probleem is dat elk getal meermaals weg gestreept wordt en dat kost tijd, dus hoe minder vaak een getal weg gestreept wordt hoe minder tijd dat kost (daarover gaat de momentele discussie met .oisyn); nul maal wegstrepen kost daarbij de minste tijd.

.oisyn schreef op 08 september 2004 @ 18:29:
Ik snap je nu niet helemaal... Mijn aangepaste algoritme en altijd setten is net ietsjes sneller dan jouw algoritme en de controle bij het setten van een bit. Als ik de controle gebruik met mijn aangepaste algoritme zijn ze ongeveer net zo snel.

Ok, dat begreep ik dus niet helemaal, ik wilde enkel zien of het zin heeft mijn algoritme nog wat aan te passen.

[.oisyn]

Voor de volledigheid:

C++:

int m = (int)std::sqrt (NUM_ELEMENTS);

for (int i = 3; i < m;)
{
    int j = i * i;
    if (j < 0x40000000)
    {
        int a = 2 * j;
        while (j < NUM_ELEMENTS)
        {
            b.set (j >> 1, 0);
            j += a;
        }
    }

    int max = NUM_ELEMENTS / i;
    for (int f = i + 2; f < max; f += 2)
    {
        if (b.get (f >> 1))
            b.set (i * f >> 1, 0);
    }

    while (!b.get ((i += 2) >> 1));
}

[Verwijderd]

Verwijderd schreef op 08 september 2004 @ 16:40:
[...]


Op zich klopt je beschrijving, maar je implementatie doet dat wel op een erg omslachtige manier. In principe (als je elk getal als een bool representeert, dus ook de even getallen) is het dit algoritme:

C++:

unsigned max= static_cast<unsigned>(std::sqrt(question));
for(unsigned i= 2; i <= max; ++i) {
    if(primes[i]) {
        for(unsigned j= i * i; j < question; j+= i) {
            primes[j]= false;
        }
    }
}

Het enige verschil is zo te zien dat jij in de geneste for loop steeds i erbij doet. Okee, wel een groot verschil performancegewijs natuurlijk Wat ik nu heb is dit:

C++:

#include <stdio.h>
#include <math.h>

/* real value calculated from element number */
unsigned int valueOf(unsigned int i) {
    return i*2+3;
}

/* real element number calculated from value */
unsigned int indexOf(unsigned int i) {
    i -= 3;
    if (i%2) {
        printf("Invalid value for indexOf: %i !\n", i+3);
        return 0;
    }
    return i/2;
}

void printTable (bool *primes, unsigned int ceiling_of_array) {
    for (unsigned int i=0; i<ceiling_of_array; i++) {
        if (primes[i]) printf("%i ", valueOf(i));
    }

    printf("\n");
}

int main() {
    unsigned int    question = 31337,
            sum_of_digits = 0,
            sum_of_factors = 0,
            ceiling_of_array = int(question/2);
    char        number_string[10],
            answer[25];
    bool        *primes = new bool[ceiling_of_array];
    unsigned int i, j, x, y;

    /* initialize bitstring: all primes */
    for (i=0; i<ceiling_of_array; i++) {
        primes[i] = 1;
    }

    /* strip away multiples */
    for (i=0; i<ceiling_of_array; i++) {
        x = valueOf(i);
        for (j=x*x; j<question; j+=2*x) {
            y = indexOf(j);
            if (!primes[y]) continue;
            primes[y] = 0;
        }
    }

    //snip een stuk code

    delete [] primes;
    return 0;
}

Die valueOf() en indexOf() zijn puur voor consistency's sake; ik moest nogal vaak die berekeningen veranderen en daarom heb ik er maar even aparte functies van gemaakt.

Maar ik heb een probleem. Een heel, _heel_, *heel* vervelend probleem Ik krijg niet de juiste uitkomst (Voor Hackquest dus). Bij Hackquest geven ze 17:24:9 en 31337:13289:234 als voorbeelden, en ik krijg bij lage getallen als 17 en 19 wel de juiste uitkomst (die kan ik nog met de hand berekenen ) maar bij 31337 krijg ik weer 'n poepuitkomst die niet klopt (31337:12932:118). Maar hoe de hel moet ik dit nu gaan debuggen als het alleen met grote getallen fout gaat

[...]

Nee, dat is iets anders. Dat stukje code uit deze post moet alle veelvouden van 2 wegstrepen (4, 6, 8, enz.) en ook alle even veelvouden van hogere priemgetallen (bij 3 de getallen 12, 18, 24, enz., bij 5 de getallen 30, 40, 50, enz.). Door die even veelvouden buiten beschouwing te laten (en niet op te slaan) hoef je dus de helft minder getallen weg te strepen.

Hmm, hier heerscht een misverstand. Je gaf eerst antwoord op mijn vraag of

C++:

sprintf(bla,"%i",getal);
last_digit = bla[0] - '0';

korter kon. "In principe wel, maar die wortel bereken je maar een keer dus dat is de moeite niet". Maar goed dit stukje gebruik ik dus voor de helft van de priemgetallen.

edit:

code:

aap@Callisto:~$ time ./sieve

3378 primes under 31337.

real    0m0.007s
user    0m0.004s
sys     0m0.002s

Misschien kan iemand dit bevestigen?

[ Voor 11% gewijzigd door Verwijderd op 08-09-2004 21:21 ]

[Verwijderd]

Verwijderd schreef op 08 september 2004 @ 20:39:
Wat ik nu heb is dit

Dat is idd een redelijke zeef, het enige wat ik nog mis is een if(!primes[x]) continue; tussen regel 43 en 44 en dat je zorgt dat de lus op regel 43 maar tot de wortel van ceiling_of_array loopt, en de lus op regel 45 totaan ceiling_of_array, dan is het algoritme vrijwel (op de verbetering van .oisyn na) optimaal.

Maar ik heb een probleem. Een heel, _heel_, *heel* vervelend probleem Ik krijg niet de juiste uitkomst (Voor Hackquest dus). Bij Hackquest geven ze 17:24:9 en 31337:13289:234 als voorbeelden, en ik krijg bij lage getallen als 17 en 19 wel de juiste uitkomst (die kan ik nog met de hand berekenen ) maar bij 31337 krijg ik weer 'n poepuitkomst die niet klopt (31337:12932:118). Maar hoe de hel moet ik dit nu gaan debuggen als het alleen met grote getallen fout gaat

Debug eerst je zeef door simpelweg een routine te schrijven die voor een willekeurig getal bepaalt of het priem is door proefdelingen; en alle priemen die die zeef genereert door die routine te checken. Verder zijn er tabellen op internet te vinden die precies vertellen hoeveel priemen er in een bepaald getallenbereik liggen, dus als je evenveel priemen uitkrijgt als in die tabellen vermeld staan en al die priemen blijken (via die proefdeling-routine) ook echt priem te zijn, dan ligt het iig. niet aan je zeef.

code:

aap@Callisto:~$ time ./sieve

3378 primes under 31337.

real    0m0.007s
user    0m0.004s
sys     0m0.002s

Misschien kan iemand dit bevestigen?

Eentje te weinig, er zijn er 3379. Waarschijnlijk vergeten de 2 of 31337 zelf mee te tellen?

[ Voor 3% gewijzigd door Verwijderd op 08-09-2004 22:08 ]

[Verwijderd]

Verwijderd schreef op 08 september 2004 @ 22:00:
[...]


Dat is idd een redelijke zeef, het enige wat ik nog mis is een if(!primes[x]) continue; tussen regel 43 en 44 en dat je zorgt dat de lus op regel 43 maar tot de wortel van ceiling_of_array loopt, en de lus op regel 45 totaan ceiling_of_array, dan is het algoritme vrijwel (op de verbetering van .oisyn na) optimaal.

Done. Ik vroeg me al af waar ik die sqrt moest plaatsen, want daar werd op iedere site wel over geroepen. Maar dit ziet er logisch uit (had hem nl. eerst in lus van regel 45 staan ). Volgens mij moet ik in de lus van regel 45 wel tot question gaan, omdat j gewoon de waarde (ipv de index op de bool array) vertegenwoordigt.

[...]
Debug eerst je zeef door simpelweg een routine te schrijven die voor een willekeurig getal bepaald of het priem is door proefdelingen; en alle priemen die die zeef genereert door die routine te checken. Verder zijn er tabellen op internet te vinden die precies vertellen hoeveel priemen er in een bepaald getallenbereik liggen, dus als je evenveel priemen uitkrijgt als in die tabellen vermeld staan en al die priemen blijken (via die proefdeling-routine) ook echt priem te zijn, dan ligt het iig. niet aan je zeef.
[...]
Eentje te weinig, er zijn er 3379. Waarschijnlijk vergeten de 2 mee te tellen?

Bingo

Maar dat was dus alleen in mijn count-functie, dus niet in de rest van de code, daar zit hem de fout dus niet

edit: ok, foutje gevonden, begon dus bij het stuk van om de twee priemen laatste en eerste cijfer optellen met i=ceiling_of_array maar daar moest nog een -1 achter. Don't you just love those errors

[ Voor 7% gewijzigd door Verwijderd op 08-09-2004 22:14 ]

[Verwijderd]

Verwijderd schreef op 08 september 2004 @ 22:10:
Volgens mij moet ik in de lus van regel 45 wel tot question gaan, omdat j gewoon de waarde (ipv de index op de bool array) vertegenwoordigt.

Sorry, je hebt gelijk, mijn fout.

Maar dat was dus alleen in mijn count-functie, dus niet in de rest van de code, daar zit hem de fout dus niet

Ok, als je nu mijn voorstel volgt en de resultaten van de zeef gewoon checkt met een is_prime() routine, dan weet je tenminste zeker of je fout in de zeef zit of in een ander deel van je programma.

[.oisyn]

Hmz frappant, ik kom op 3385 priemen onder de 31337

.edit: en er worden idd 8 getallen foutief als priem aangezien, allemaal tegen het eind (zeg maar de 25 laatste getallen ofzo). Het eerste getal dat foutief wordt aangegeven is 31243, die de factoren 157 en 199 heeft. Eens even kijken wat er nou eigenlijk fout gaat...

.edit: ah, ik deed f < NUM_PRIMES / i ipv f <= NUM_PRIMES / i

[ Voor 82% gewijzigd door .oisyn op 08-09-2004 22:35 ]

[Verwijderd]

C++:

#include <math.h>

int main () {
    unsigned int i, j, x, y, ac, q=50000000;
    ac = int(q/2);
    bool *p = new bool[ac];

    unsigned int rc = int(sqrt(ac));
    for (i=0; i<rc; i++) {
        if (p[i]) continue;
        x = i*2+3;
        for (j=x*x; j<q; j+=2*x) {
            y = int((j-3)/2);
            if (p[y]) continue;
                p[y] = 1;
        }
    }

    delete [] p;
    return 0;
}

3.050s voor alles onder 50.000.000 @ Duron 1200, zonder intensieve processen (XFree, xmms, whatever) en als root
Sneller krijg ik hem niet, want dat spul van .oisyn & mietje gaat me de pet te boven wat betreft c++

En meteen een goede oefening om onleesbare korte code te schrijven

edit: Heb trouwens mijn interpretatie van true/false omgedraaid, omdat iemand zei dat met de new operator de array geinitialiseerd wordt op false. Heb ook geprobeerd of het niet sneller was om in de array ook gewoon de even getallen mee te nemen, en daar dan gewoon overheen te springen, maar helaas

[ Voor 37% gewijzigd door Verwijderd op 08-09-2004 23:08 ]

[.oisyn]

iemand zei dat met de new operator de array geinitialiseerd wordt op false

wat dus niet klopt, als je een array alloceert met new dan wordt bij classes/structs de default constructor aangeroepen, maar primitives blijven ongeinitialiseerd. Helaas kun je geen initialiser meegeven bij arrays (wordt trouwens tijd dat ze dat eens gaan veranderen).

[Verwijderd]

.oisyn schreef op 08 september 2004 @ 23:19:
[...]

wat dus niet klopt, als je een array alloceert met new dan wordt bij classes/structs de default constructor aangeroepen, maar primitives blijven ongeinitialiseerd. Helaas kun je geen initialiser meegeven bij arrays (wordt trouwens tijd dat ze dat eens gaan veranderen).

Hmm, krijg wel allemaal nullen als ik die verse array print..

[.oisyn]

Dat is waarschijnlijk omdat het debugcode is. Of misschien is je runtime wel gewoon zo ontworpen, maar het is iig geen standard behaviour (en kan op een ander platform dus totaal anders uitpakken)

[ Voor 63% gewijzigd door .oisyn op 08-09-2004 23:30 ]

[MSalters]

.oisyn schreef op 08 september 2004 @ 23:19:
[...]

wat dus niet klopt, als je een array alloceert met new dan wordt bij classes/structs de default constructor aangeroepen, maar primitives blijven ongeinitialiseerd. Helaas kun je geen initialiser meegeven bij arrays (wordt trouwens tijd dat ze dat eens gaan veranderen).

Don't hold your breath. Als je geinitialiseerde objecten wil kun je std::vector<> gebruiken. Arrays zijn primitieve objecten, en er is weinig behoefte om ze uit te breiden.

[.oisyn]

True, maar hoe ga je dat dan oplossen voor non-copyable objecten? Je kunt nog altijd geen constructor parameters meegeven, dat moet dan via een copyconstructor. Waar, het zijn zeldzame gevallen waarvan ik me momenteel even niet kan indenken wanneer je nou zo'n array nodig hebt, maar ik vind het toch raar dat je bij een array geen initialiser list mee kan geven. Al is het alleen maar voor the sake of completeness.

[Soultaker]

Volgens mij heb je met non-copyable objecten in dynamisch-gealloceerde arrays precies hetzelfde probleem: ze worden default constructed en vervolgens kun je ze niet meer assignen.

Je kunt in beide situaties natuurlijk ook altijd de default constructed objecten destructen en er met placed new nieuwe objecten in plempen, mits je objecten wel default-constructable zijn.

Ik snap sowieso niet wat je ook met non-copyable objecten in STL containers zou willen; je kunt ze er dan bijvoorbeeld nooit meer elementen aan toevoegen.

[.oisyn]

Ik heb nooit gezegd dat ik non-copyable objecten in een dynamische array wil hebben, ik heb gezegd dat ik het raar vind dat je bij een new[] (of gewone array definitie for that matter) geen constructor-argumenten mee kunt geven

[ Voor 12% gewijzigd door .oisyn op 09-09-2004 01:28 ]

[Verwijderd]

Verwijderd schreef op 08 september 2004 @ 23:04:
3.050s voor alles onder 50.000.000 @ Duron 1200, zonder intensieve processen (XFree, xmms, whatever) en als root
Sneller krijg ik hem niet, want dat spul van .oisyn & mietje gaat me de pet te boven wat betreft c++

Nog een kleine correctie: je berekent die wortel fout, je doet sqrt(q / 2) ipv. sqrt(q) / 2.0 (dat laatste levert ook een kleiner getal op en is dus gunstiger/sneller).

En meteen een goede oefening om onleesbare korte code te schrijven

Mwah, je code doet geen gekke dingen en is redelijk tot goed volgbaar, ik denk eerder dat het een goede oefening was in eerst het juiste algoritme kiezen (het internet is hierbij je vriend) en pas nadat je dat gevonden en geïmplementeerd hebt beginnen met optimaliseren als dat nog nodig mocht blijken

edit: Heb trouwens mijn interpretatie van true/false omgedraaid, omdat iemand zei dat met de new operator de array geinitialiseerd wordt op false.

Dat zei ik en ik was in de veronderstelling dat dat ook zo was omdat ik dat op verschillende platforms (windows, linux, freebsd) heb waargenomen. Ik vermoed nu dat het een feature van gcc is, maar weet er het fijne niet van. Ik vertrouw MSalters en .oisyn als die zeggen dat het geen standaard-gedrag is (ouwe language lawyers ).

[Soultaker]

Moderne OS'es overschrijven nieuw gealloceerde pages uit veiligheidsoverwegingen (anders kun je informatie uit andere processen lezen) en die zullen meestal gemakshalve nullen gebruiken. Dat is al OS-specifiek gedrag, maar in de praktijk zouden pages dus wel op nul gealloceerd kunnen zijn. Het zou dus kunnen dat je observaties daar vandaan komen.

Ik weet echter wel vrij zeker dat het misgaat als je veel kleine arrays vrijgeeft en alloceert, want dan zal je echt niet steeds nieuwe pages krijgen toegewezen. De C++ allocator gaat die nieuwe arrays niet voor je wissen en dan zou je dus echt oude data terug moeten kunnen lezen.

Voorbeeld:

C++:

int *x, n;

x = new int[1];
cout << x[0] << endl;
x[0] = 12345;
cout << x[0] << endl;
delete[] x;

x = new int[1];
cout << x[0] << endl;
delete[] x;

Dit print hier naar verwachting 0, 12345, 12345.

[ Voor 8% gewijzigd door Soultaker op 09-09-2004 02:42 ]

[Verwijderd]

Je hebt gelijk, ik heb voor de zekerheid maar een memset() in mijn code geplaatst; en wat blijkt: met de memset() is de code sneller dan zonder (getest op linux, ik neem aan dat het komt omdat er dan in 1x alle benodigde pages gereserveerd worden dmv. copy-on-write).

Misschien nog interessant voor de zeef-fanaten Ik heb nu een werkende zeef die niet alleen de veelvouden van 2 niet opslaat, maar ook de veelvouden van 3 niet. Dat levert 1/6 ruimtebesparing extra op en meer dan 10% snellere code. (Alle 203277124 unsigned 32-bits priemen in 112.84 seconden op een Athlon XP 1600+) Als er belangstelling voor is wil ik de code wel posten (zo'n 220 regels).

edit:
En net toen ik dit schreef rapporteerde de ceck-routine dat er een priemgetal ontbreekt... back to the drawing board

[ Voor 10% gewijzigd door Verwijderd op 11-09-2004 18:04 ]

[Verwijderd]

Na wat debuggen en een nachtje proefdelen blijkt dat mijn nieuwe zeef toch goed ontworpen is, de fout werd veroorzaakt doordat je vreselijk moet oppassen met het berekenen van die wortel-limiet voor de buitenste lus, anders kwadrateer je een getal > 65535 en dat veroorzaakt een overflow. Nu worden de 203280221 priemen goed berekend, als er interesse voor is post ik de code.