DIG Digital Corner
Alles wat je altijd al over computers, hardware, software, internet en elektronische gadgets had willen weten, maar niet op Tweakers.net durft te vragen.
Het callen van een functie opzich kost niet persee veel tijd. Wel is het zo dat iedere keer als je een functie binnenkomt, de compiler het benodigde geheugen wat die functie nodig heeft voor lokale variabelen moet alloceren, en weer vrij moet geven bij het verlaten van een functie. Enkele kleine variabelen (int, char, float, etc) worden op de stack gealloceerd en kosten nauwelijks tijd, maar als je classen gebruikt binnen je functie komen die op de heap (wat wel relatief veel tijd kost).
In jou geval hoeft de compiler het initialiseren/vrijgeven van die vector<int> slechts 1 keer te doen als je die digit() functie opneemt in je main, en 18000000 keer (als ik je code goed kan herinneren; hij is nu weg) als je 'm steeds als funtie aanroept...
In jou geval hoeft de compiler het initialiseren/vrijgeven van die vector<int> slechts 1 keer te doen als je die digit() functie opneemt in je main, en 18000000 keer (als ik je code goed kan herinneren; hij is nu weg) als je 'm steeds als funtie aanroept...
Wat bedoel je met classen?quote:Op zondag 29 juli 2012 11:12 schreef Ai_KaRaMBa het volgende:
Het callen van een functie opzich kost niet persee veel tijd. Wel is het zo dat iedere keer als je een functie binnenkomt, de compiler het benodigde geheugen wat die functie nodig heeft voor lokale variabelen moet alloceren, en weer vrij moet geven bij het verlaten van een functie. Enkele kleine variabelen (int, char, float, etc) worden op de stack gealloceerd en kosten nauwelijks tijd, maar als je classen gebruikt binnen je functie komen die op de heap (wat wel relatief veel tijd kost).
In jou geval hoeft de compiler het initialiseren/vrijgeven van die vector<int> slechts 1 keer te doen als je die digit() functie opneemt in je main, en 18000000 keer (als ik je code goed kan herinneren; hij is nu weg) als je 'm steeds als funtie aanroept...
Maar als je een functie vaak callt dan is het dus vaak aan te raden om het in je main te verwerken.. Vind ik wel jammer eigenlijk, want als je het erbuiten doet ziet het er veel overzichtelijker uit.
Maar goed, op naar het volgende probleem
.
Hmm... simpel gezegt een classe is een complex data type wat zowel data als functies bevat. Ik was trouwens niet helemaal corrct: ook classen kunnen op de stack worden gealloceerd. Maar in dit geval gebruik je een vector, dat is een lijst van dynamische grootte, en die wordt wel op de heap geallocceerd.quote:
[..]
Wat bedoel je met classen?
Maar als je een functie vaak callt dan is het dus vaak aan te raden om het in je main te verwerken.. Vind ik wel jammer eigenlijk, want als je het erbuiten doet ziet het er veel overzichtelijker uit.
Maar goed, op naar het volgende probleem
Vaak is het helemaal niet aan te raden functies die je veel gebruikt in je main te verwerken!! Dat wordt er enorm onoverzichtelijk van. Loop unroling en handmatig inlinen zijn acties die je maar heeeeel zelden nodig hebt.
Als het echter een bottleneck is, kun je overwegen wat overhead weg te nemen. In jouw geval had dat bijvoorbeeld ook gekunt door je vector globaal te maken... Dat scheelt volgens mij ook (twee?) kopieer acties bij het returnen van de vector... Of wat ik vaak doe: de caller een variabele laten alloceren, en een pointer meegeven aan de functie waarin hij z'n resultaat moet wegschrijven.
Daarnaast is het gebruik van dynamische containers als vector<> of string sowieso af te raden als het tijd-critisch is!
Bedankt! Nu is het een stuk duidelijker.quote:
[..]
Hmm... simpel gezegt een classe is een complex data type wat zowel data als functies bevat. Ik was trouwens niet helemaal corrct: ook classen kunnen op de stack worden gealloceerd. Maar in dit geval gebruik je een vector, dat is een lijst van dynamische grootte, en die wordt wel op de heap geallocceerd.
Vaak is het helemaal niet aan te raden functies die je veel gebruikt in je main te verwerken!! Dat wordt er enorm onoverzichtelijk van. Loop unroling en handmatig inlinen zijn acties die je maar heeeeel zelden nodig hebt.
Als het echter een bottleneck is, kun je overwegen wat overhead weg te nemen. In jouw geval had dat bijvoorbeeld ook gekunt door je vector globaal te maken... Dat scheelt volgens mij ook (twee?) kopieer acties bij het returnen van de vector... Of wat ik vaak doe: de caller een variabele laten alloceren, en een pointer meegeven aan de functie waarin hij z'n resultaat moet wegschrijven.
Daarnaast is het gebruik van dynamische containers als vector<> of string sowieso af te raden als het tijd-critisch is!
Ondertussen alweer het volgende probleem opgelost. Begin die syntax nu wel goed onder de knie te krijgen
.
Mijn vraag was: hoe vaak roep je digit() en numDigit() per getal aan? Het probleem zit 'em niet in de functie-aanroep, maar in al het dubbele werk dat je deed. Het is beter het resultaat op te slaan dan om de (relatief dure) functie digit() elke keer te gebruiken.
Wat Ai_KaRaMBa zegt over functie-aanroepen klopt grotendeels: in principe kost een functie-aanroep niet veel en gaat de meeste tijd zitten in het kopieren van grote objecten. Dit laatste wordt echter meestal voorkomen (door (const) references mee te geven in plaats van de objecten zelf) en is een keuze: geen feit. De echte kosten van een functie (die dus niet voorkomen kunnen worden) zijn het op de stack zetten van alle argumenten (het liefst dus kleine argument of (const) references), de stack pointer aanpassen en van en naar de nieuwe code springen.
Als je deze overhead wilt voorkomen, dan laat je je functie gewoon staan en zet je er 'inline' voor, zodat de compiler weet dat jij wilt dat deze functie niet 'extern' aangeroepen moet worden, maar in de code moet worden verwerkt waar jij die aanroept. Dit doe je meestal met kleine functies (het liefst 1 regel), omdat je je voor kan stellen hoe groot de code wordt als je 20 regels code gaat plakken op elke plek waar je een functie aanroept. Let op dat 'inline' mogelijk door de compiler genegeerd wordt, als deze dat beter vindt.
Er is dus een klein tijdsverlies, maar deze is minimaal als je het goed doet. Als je een kleine functie hebt die je vaak aanroept, kun je deze 'inline' labelen, maar dit is geen zekerheid. Als het er echt, echt op aan komt, kan je erover denken om de functie-aanroep te verwijderen en de code direct op de juiste plek te zetten. Ik heb het 1 keer gedaan in een klasse voor rekenen met ongelimiteerd grote getallen in de binnenste loop van een deelfunctie. Bij PE is het niet nodig en zeker niet als het je ook doet om een programmeertaal te leren.
Ook hier kan je tijd winnen door ze juist te gebruiken. De std::vector klasse heeft bijvoorbeeld members reserve() en resize(), waarmee je de vector bij aanmaak de juiste grootte kan geven (als je deze weet, ten minste). Dit scheelt een mogelijke re-allocatie (het dure gedeelte) bij een push_back. Ook helpt het de eigenschappen van de containers te kennen, zodat je de juiste kiest.
Over het algemeen vind ik de stl-containers helemaal geen slechte keuze, ook niet als tijd erg belangrijk is.
Wat Ai_KaRaMBa zegt over functie-aanroepen klopt grotendeels: in principe kost een functie-aanroep niet veel en gaat de meeste tijd zitten in het kopieren van grote objecten. Dit laatste wordt echter meestal voorkomen (door (const) references mee te geven in plaats van de objecten zelf) en is een keuze: geen feit. De echte kosten van een functie (die dus niet voorkomen kunnen worden) zijn het op de stack zetten van alle argumenten (het liefst dus kleine argument of (const) references), de stack pointer aanpassen en van en naar de nieuwe code springen.
Als je deze overhead wilt voorkomen, dan laat je je functie gewoon staan en zet je er 'inline' voor, zodat de compiler weet dat jij wilt dat deze functie niet 'extern' aangeroepen moet worden, maar in de code moet worden verwerkt waar jij die aanroept. Dit doe je meestal met kleine functies (het liefst 1 regel), omdat je je voor kan stellen hoe groot de code wordt als je 20 regels code gaat plakken op elke plek waar je een functie aanroept. Let op dat 'inline' mogelijk door de compiler genegeerd wordt, als deze dat beter vindt.
Er is dus een klein tijdsverlies, maar deze is minimaal als je het goed doet. Als je een kleine functie hebt die je vaak aanroept, kun je deze 'inline' labelen, maar dit is geen zekerheid. Als het er echt, echt op aan komt, kan je erover denken om de functie-aanroep te verwijderen en de code direct op de juiste plek te zetten. Ik heb het 1 keer gedaan in een klasse voor rekenen met ongelimiteerd grote getallen in de binnenste loop van een deelfunctie. Bij PE is het niet nodig en zeker niet als het je ook doet om een programmeertaal te leren.
Ben ik het niet helemaal mee eens. Ook hier gaat het weer op de manier waarop je het gebruikt. Als je geen dynamische allocatie nodig hebt, is het inderdaad meestal sneller het niet te doen. Maar als je het wel nodig hebt (grote of onbekend grote input, bijvoorbeeld) dan zijn de dynamische containers een goede keuze.quote:Daarnaast is het gebruik van dynamische containers als vector<> of string sowieso af te raden als het tijd-critisch is!
Ook hier kan je tijd winnen door ze juist te gebruiken. De std::vector klasse heeft bijvoorbeeld members reserve() en resize(), waarmee je de vector bij aanmaak de juiste grootte kan geven (als je deze weet, ten minste). Dit scheelt een mogelijke re-allocatie (het dure gedeelte) bij een push_back. Ook helpt het de eigenschappen van de containers te kennen, zodat je de juiste kiest.
Over het algemeen vind ik de stl-containers helemaal geen slechte keuze, ook niet als tijd erg belangrijk is.
"Slechts diegene mag slopen die iets beters kan bouwen."
Bedankt nog voor de reacties.
Ik loop nu tegen iets heel raars aan. Hoe kan het verschil in output verklaard worden?
Geeft als output
Kennelijk herkent ie een element van de string niet als integer. Hoe kan je het in een int converteren?
[ Bericht 5% gewijzigd door thenxero op 29-07-2012 19:27:18 ]
Ik loop nu tegen iets heel raars aan. Hoe kan het verschil in output verklaard worden?
| 1 2 3 4 5 6 7 8 9 10 11 | #include <iostream> using namespace std; int main() { string mystring = "73"; cout << mystring[0] <<endl; int a=mystring[0]; cout << a; } |
| 1 2 | 7 55 |
Kennelijk herkent ie een element van de string niet als integer. Hoe kan je het in een int converteren?
[ Bericht 5% gewijzigd door thenxero op 29-07-2012 19:27:18 ]
Een string bestaat uit bytes, en a is de eerste byte van je string, te weten de byte die overeenkomt met het ascii-karakter "7". En dat is 48 + 7 = 55, want cijfers lopen in ascii van "0"=48 tot "9"=48+9=57.quote:Op zondag 29 juli 2012 19:10 schreef thenxero het volgende:
Bedankt nog voor de reacties.
Ik loop nu tegen iets heel raars aan. Hoe kan het verschil in output verklaard worden?
[ code verwijderd ]
Geeft als output
[ code verwijderd ]
Oké, en hoe vertaal je dit weer terug naar het juiste getal? Altijd -48?quote:
[..]
Een string bestaat uit bytes, en a is de eerste byte van je string, te weten de byte die overeenkomt met het ascii-karakter "7". En dat is 48 + 7 = 55, want cijfers lopen in ascii van "0"=48 tot "9"=48+9=57.
Hoe bedoel je dat?quote:
[..]
Oké, en hoe vertaal je dit weer terug naar het juiste getal? Altijd -48?
O zo. Ja, je kan er 48 aftrekken. Iets netter is misschien om '0' (met enkele aanhalingstekens) af te trekken.
Bedankt, met deze truc is het gelukt om EP9 op te lossen.quote:
O zo. Ja, je kan er 48 aftrekken. Iets netter is misschien om '0' (met enkele aanhalingstekens) af te trekken.
| 1 | Discover the largest product of five consecutive digits in the 1000-digit number. |
Weet je een goede link waar ik wat meer kan lezen over die '0'? ik weet niet echt waar ik op moet zoeken.
'0' is niets anders dan de char die met het ascii-teken '0' overeenkomt. Wordt opgeslagen in een byte en heeft de waarde 48. Zo heeft elke character een numerieke waarde: 'A' is bijvoorbeeld 65, en een spatie ' ' is 32.quote:
[..]
Bedankt, met deze truc is het gelukt om EP9 op te lossen.
[ code verwijderd ]
Weet je een goede link waar ik wat meer kan lezen over die '0'? ik weet niet echt waar ik op moet zoeken.
Een char is in principe gewoon een byte, maar wordt ook gebruikt om characters mee te representeren.
Duidelijkquote:
[..]
'0' is niets anders dan de char die met het ascii-teken '0' overeenkomt. Wordt opgeslagen in een byte en heeft de waarde 48. Zo heeft elke character een numerieke waarde: 'A' is bijvoorbeeld 65, en een spatie ' ' is 32.
Een char is in principe gewoon een byte, maar wordt ook gebruikt om characters mee te representeren.
Ik loop weer ergens mee vast. Wat ik wil doen is de vereniging van twee willekeurig grote verzamelingen bepalen. De verzamelingen codeer ik als vectors. Het idee van de code is als volgt. Stel ik wil de vereniging van vector a en van b. Dan definieer ik een vector c die bestaat uit alle elementen uit b, en alle elementen uit a die niet in b zitten (zodat ik geen duplicaten creëer).
Ik heb er een hele tijd naar zitten staren, en gedebugged, maar ik kan maar niet de fout vinden in mijn code.
Zou natuurlijk als output de vector [3,4,0,45,55,66] moeten geven. Maar ik krijg [3,4,0,55,55,1112944187]
Ik heb er een hele tijd naar zitten staren, en gedebugged, maar ik kan maar niet de fout vinden in mijn code.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | #include <iostream> #include <vector> using namespace std; vector<int> vereniging(vector<int> a, vector<int> b) { vector<int> c=b; for(int k=0; k<a.size(); k++) { int check=-1; int l(0); for(l=0; l<b.size(); l++) { if(a[l]==b[k]) { check++; break; } } if(check<0) { c.push_back(a[k]); } } return c; } int main() { int a[]={3,0,45,55,66}; vector<int> m; m.assign(a,a+5); int b[]={3,4}; vector<int> n; n.assign(b,b+2); cout << vereniging(m,n)[0] << endl << vereniging(m,n)[1] << endl << vereniging(m,n)[2] << endl<< vereniging(m,n)[3] << endl << vereniging(m,n)[4] << endl << vereniging(m,n)[5]; } |
Zou natuurlijk als output de vector [3,4,0,45,55,66] moeten geven. Maar ik krijg [3,4,0,55,55,1112944187]
STL heeft een datatype set, zou je ook kunnen gebruiken.quote:
Ik loop weer ergens mee vast. Wat ik wil doen is de vereniging van twee willekeurig grote verzamelingen bepalen. De verzamelingen codeer ik als vectors.
Wat zijn de voordelen van dat datatype? Kan je daar wel makkelijk verenigingen mee maken?quote:
[..]
STL heeft een datatype set, zou je ook kunnen gebruiken.
En ik wil alsnog wel graag weten wat er mis is met mijn code, heb er echt uren naar zitten turen
Jouw code heeft looptijd O(nm), een verzamelingendatatype kan het in O((n+m)log(n+m)).quote:
[..]
Wat zijn de voordelen van dat datatype? Kan je daar wel makkelijk verenigingen mee maken?
Weet je wat copy-constructors zijn en waar ze in je code impliciet aangeroepen worden?quote:
OK dat moet ik dan maar gaan bestuderen. Zie je zo snel geen fout in mijn algoritme?
Nee.quote:
[..]
Weet je wat copy-constructors zijn en waar ze in je code impliciet aangeroepen worden?
edit; even snel gegoogled, bedoel je de regel: vector<int> c=b;?
.
Onder andere, maar ook bijvoorbeeld in de functie-aanroep worden ze gebruikt, en in het returnen van die vector.quote:
[..]
Nee.
edit; even snel gegoogled, bedoel je de regel: vector<int> c=b;?
