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.
Dat is in C toch niet heel veel moeilijker?quote:Op donderdag 14 juni 2012 10:07 schreef ralfie het volgende:
[..]
[ code verwijderd ]
Vergeleken met c++ is C# zoo makkelijk.
| 1 2 3 4 5 6 7 8 | char tmp[33]; char outp[1024] = {0}; for(char *c=in; *c; c++) { strcat(outp, "-"); strcat(outp, itoa(toupper(*c)-'A'+1, tmp, 10)); } return strdup(&outp[1]); |
Ha, nu wil ik ook meedoen met een echte C++ oplossing:
Ik vind het wel wat hebben.
| 1 2 3 4 5 | std::string encode(std::string const &input) { std::ostringstream ss; std::for_each(input.begin(), input.end(), [&ss](char c){ ss << c - 96 << '-'; }); return ss.str(); } |
Ik vind het wel wat hebben.
"Slechts diegene mag slopen die iets beters kan bouwen."
Je vergeet de laatste '-' eraf te strippen, en een toupper/tolower ergens 
Maar goed: de algemene aanpak in C, C++ en C# is hetzelfde; zitten wat kleine API/syntax verschillen in, maar ik zie niet waarom het ene fundamenteel makkelijker zou zijn dan het andere
Maar goed: de algemene aanpak in C, C++ en C# is hetzelfde; zitten wat kleine API/syntax verschillen in, maar ik zie niet waarom het ene fundamenteel makkelijker zou zijn dan het andere
Volgens de opgave is de input altijd in kleine letters en mag de laatste '-' blijven staan. Wel lezen he?quote:Op donderdag 14 juni 2012 13:11 schreef Ai_KaRaMBa het volgende:
Je vergeet de laatste '-' eraf te strippen, en een toupper/tolower ergens
Maar je hebt gelijk, natuurlijk. De oplossingen zijn precies hetzelfde. De programmeertaal is voorkeur.quote:Maar goed: de algemene aanpak in C, C++ en C# is hetzelfde; zitten wat kleine API/syntax verschillen in, maar ik zie niet waarom het ene fundamenteel makkelijker zou zijn dan het andere
"Slechts diegene mag slopen die iets beters kan bouwen."
quote:
[..]
[ code verwijderd ]
Vergeleken met c++ is C# zoo makkelijk.
| 1 | return "-".join([str(ord(c) - ord("a") + 1) for c in string]) |
[ Bericht 1% gewijzigd door thabit op 14-06-2012 15:06:10 ]
Oh, ik had de opgave niet gelezen... Ik had mijn code gelijk getrokken aan die van ralfiequote:Op donderdag 14 juni 2012 13:13 schreef GS42 het volgende:
[..]
Volgens de opgave is de input altijd in kleine letters en mag de laatste '-' blijven staan. Wel lezen he?
Als je de opgave nog eens goed leest, dan zie je dat het weghalen van de laatste "-" punten oplevert.
Tsja, uiteindelijk doet Python het ook in C. Er zijn natuurlijk ook parsergeneratoren die het parsen van tekst prachtig doen, zoals de combinatie van Flex en Bison. Daarmee kan je tekst parsen in een soort meta-taaltje waarna de parsergenerator de broncode voor je genereert en je zelf niets hoeft te schijven. De programma's worden daarom ook wel compiler-compilers genoemd.quote:Op donderdag 14 juni 2012 13:17 schreef thabit het volgende:
Nog makkelijker! String parsing moet je niet in C-watdanook willen doen.
Trouwens, nu we zo enthousiast met een simpel opdrachtje bezig zijn, vraag ik me af of jullie Project Euler ook kennen. Het is een website met programmeerpuzzels, meestal gecombineerd met een beetje wiskunde. Het begin is goed te doen, maar de opgaves worden steeds lastiger. Iemand die het kent of zelfs meedoet?
"Slechts diegene mag slopen die iets beters kan bouwen."
Zeker, erg leuke site! Ik moet bekennen dat ik er uit zelfbescherming niet te vaak op zit, omdat ik anders hele dagen niks anders doe.quote:
[..]
Trouwens, nu we zo enthousiast met een simpel opdrachtje bezig zijn, vraag ik me af of jullie Project Euler ook kennen. Het is een website met programmeerpuzzels, meestal gecombineerd met een beetje wiskunde. Het begin is goed te doen, maar de opgaves worden steeds lastiger. Iemand die het kent of zelfs meedoet?
Ik ken 't idd! Dat soort programmeer uitdagingen zijn trouwens altijd leuk.
Ik heb in het verleden ook wel deelgenomen aan USACO, TopCoder, Codecup en de ACM-ICPC (nooit verder gekomen dan de NWERC trouwens). Allemaal net wat anders van opzet, maar ook allemaal leuk om aan deel te nemen.
Helaas heb ik op het moment een beetje last van tijdgebrek
Ik heb in het verleden ook wel deelgenomen aan USACO, TopCoder, Codecup en de ACM-ICPC (nooit verder gekomen dan de NWERC trouwens). Allemaal net wat anders van opzet, maar ook allemaal leuk om aan deel te nemen.
Helaas heb ik op het moment een beetje last van tijdgebrek
Nee had ik nog nooit van gehoord maar zit er idd zeer interessant uit, ik ga na mijn tentamens denk ik maar eens even goed bekijken (als ik het er voor doe haal ik mijn tentamens waarschijnlijk niet meer)quote:
Trouwens, nu we zo enthousiast met een simpel opdrachtje bezig zijn, vraag ik me af of jullie Project Euler ook kennen. Het is een website met programmeerpuzzels, meestal gecombineerd met een beetje wiskunde. Het begin is goed te doen, maar de opgaves worden steeds lastiger. Iemand die het kent of zelfs meedoet?
Beware of the Raping Zebra's
Ik heb als fysicus een c++ cursus gedaan op de universiteit.
En ik vind het altijd leuk om dummies te helpen.
En ik vind het altijd leuk om dummies te helpen.
Ik ben daar mee bezig met amd64 assembly en wiskunde, voor sommige heb je geen programma nodig.quote:
Trouwens, nu we zo enthousiast met een simpel opdrachtje bezig zijn, vraag ik me af of jullie Project Euler ook kennen. Het is een website met programmeerpuzzels, meestal gecombineerd met een beetje wiskunde. Het begin is goed te doen, maar de opgaves worden steeds lastiger. Iemand die het kent of zelfs meedoet?
Ik ben pas begonnen met C++ te leren. Ik probeer het te doen aan de hand van die projecteuler site. Het is me gelukt de eerste drie vragen op te lossen. Het is misschien niet moeilijk als je weet hoe C++ in elkaar zit, maar voor mij is het een hele opgave (maar wel een leukequote:
Trouwens, nu we zo enthousiast met een simpel opdrachtje bezig zijn, vraag ik me af of jullie Project Euler ook kennen. Het is een website met programmeerpuzzels, meestal gecombineerd met een beetje wiskunde. Het begin is goed te doen, maar de opgaves worden steeds lastiger. Iemand die het kent of zelfs meedoet?
).Ik ben nu aanbeland bij het volgende probleem:
Mijn aanpak is als volgt:quote:A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
1. Maak een functie die een getal opsplitst in zijn cijfers. Dus bvb: 123 --> 1, 2, 3
2. Maak een functie die het eerste en laatste cijfer vergelijkt, het tweede en het één na laatste, etc. Als die allemaal hetzelfde zijn dan is het een palindroom.
3. Genereer alle producten van 3 cijfers en pas 1. en 2. toe. (dat kan vast ook efficiënter)
Ik loop al vast bij stap 1. Het is me wel gelukt om die functie te maken, die van een getal 123 een array {1,2,3} maakt, alleen het lukt me niet om die in zijn geheel te "returnen". Ik heb ook van alles geprobeerd met pointers en vectors en van alles bij elkaar gegoogled, maar ik kom er maar niet verder mee.
Dit is mijn huidige code, waar ik ter illustratie een getal return. De hele array lukt niet, dus als iemand me daarmee kan helpen, graag!
| 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 | #include <iostream> #include <vector> using namespace std; //Deze functie bepaalt het aantal cijfers in een getal int numDigits(int q){ if(q>0 && q<10){return(1);}; if(q>9 && q<100){return(2);}; if(q>99 && q<1000){return(3);}; if(q>999 && q<10000){return(4);}; if(q>9999 && q<1000000){return(5);}; if(q>99999 && q<10000000){return(6);}; if(q>999999 && q<100000000){return(7);}; if(q>9999999 && q<1000000000){return(8);}; } //Deze functie splitst het getal op in zijn cijfers int digit(int p){ int z; int k(1); int l(1); int i(0); int m[numDigits(p)]; for(z=0; z<numDigits(p); z++){ k=(p/l)%10; l=10*l; m[i]=k; i++; } return m[1]; } int main(){ cout << digit(52); return 0; } |
Ik heb het zelf opgelost door het getal om te zetten naar een std::string en in de string het getal op palindromiteit te controleren. Dit is een mogelijkheid die je kunt overwegen. Ook kan je een std::vector gebruiken om de getallen in op te slaan. Een std::vector of std::string kan je beide gewoon returnen.quote:
Ik loop al vast bij stap 1. Het is me wel gelukt om die functie te maken, die van een getal 123 een array {1,2,3} maakt, alleen het lukt me niet om die in zijn geheel te "returnen". Ik heb ook van alles geprobeerd met pointers en vectors en van alles bij elkaar gegoogled, maar ik kom er maar niet verder mee.
Het is niet mogelijk een array te returnen uit een functie. Wel is het mogelijk een pointer naar een dynamisch gealloceerde array terug te geven, maar dit zou ik in dit geval niet aanraden.
Denk je dat je hiermee verder komt?
"Slechts diegene mag slopen die iets beters kan bouwen."
Met zo'n string is ook wel handig. Maar ik wil het proberen als array of vector (dan leer ik daar ook mee omgaan). Ik had al gevonden op internet dat je een array niet kon returnen en een vector wel, maar toch lukte het me niet met een vector.quote:
[..]
Ik heb het zelf opgelost door het getal om te zetten naar een std::string en in de string het getal op palindromiteit te controleren. Dit is een mogelijkheid die je kunt overwegen. Ook kan je een std::vector gebruiken om de getallen in op te slaan. Een std::vector of std::string kan je beide gewoon returnen.
Het is niet mogelijk een array te returnen uit een functie. Wel is het mogelijk een pointer naar een dynamisch gealloceerde array terug te geven, maar dit zou ik in dit geval niet aanraden.
Denk je dat je hiermee verder komt?
Ik heb bijvoorbeeld het volgende geprobeerd:
| 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 | #include <iostream> #include <vector> using namespace std; //Deze functie bepaalt het aantal cijfers in een getal int numDigits(int q){ if(q>0 && q<10){return(1);}; if(q>9 && q<100){return(2);}; if(q>99 && q<1000){return(3);}; if(q>999 && q<10000){return(4);}; if(q>9999 && q<1000000){return(5);}; if(q>99999 && q<10000000){return(6);}; if(q>999999 && q<100000000){return(7);}; if(q>9999999 && q<1000000000){return(8);}; } //Deze functie splitst het getal op in zijn cijfers int digit(int p){ int z; int k(1); int l(1); int i(0); vector<int> m; for(z=0; z<numDigits(p); z++){ k=(p/l)%10; l=10*l; m.push_back(k); i++; } return m; } int main(){ cout << digit(52); return 0; } |
Maar dan krijg ik:
| 1 | error: cannot convert 'std::vector<int, std::allocator<int> >' to 'int' in return| |
Ah, dat is een vrij duidelijk foutmelding. Je weet dat je een functie begint door aan te geven welk type een functie returnt? Deze foutmelding geeft aan dat je een ander type teruggeeft dan volgens de functie-declaratie zou moeten. Dat klopt ook, want je schrijft int digit(), terwijl je een vector<int> teruggeeft. Dat moet veranderd worden.quote:
[..]
Met zo'n string is ook wel handig. Maar ik wil het proberen als array of vector (dan leer ik daar ook mee omgaan). Ik had al gevonden op internet dat je een array niet kon returnen en een vector wel, maar toch lukte het me niet met een vector.
Ik heb bijvoorbeeld het volgende geprobeerd:
[ code verwijderd ]
Maar dan krijg ik:
[ code verwijderd ]
Daarnaast kan je een vector niet afdrukken door deze gelijk in std::cout te stoppen. Jouw regel 35 kan dus ook niet: je zult de elementen van de vector 1 voor 1 af moeten drukken.
Verder gebruik je de vector echter op de juiste manier, dus dat zit goed. Er zijn nog wat andere op- en aanmerkingen, maar die zijn van minder belang. (Heb je toevallig eerder iets met C gedaan?)
"Slechts diegene mag slopen die iets beters kan bouwen."
Dank! Hier ben ik dus uren mee bezig geweest, heb geprobeerd in de return aan te geven dat hij een vector moet returnen, etc. En dan is het zo simpelquote:
[..]
Ah, dat is een vrij duidelijk foutmelding. Je weet dat je een functie begint door aan te geven welk type een functie returnt? Deze foutmelding geeft aan dat je een ander type teruggeeft dan volgens de functie-declaratie zou moeten. Dat klopt ook, want je schrijft int digit(), terwijl je een vector<int> teruggeeft. Dat moet veranderd worden.
. Heb geen ervaring met C. Heb alleen een beetje geprogrammeerd in Mathematica en Matlab.quote:Daarnaast kan je een vector niet afdrukken door deze gelijk in std::cout te stoppen. Jouw regel 35 kan dus ook niet: je zult de elementen van de vector 1 voor 1 af moeten drukken.
Verder gebruik je de vector echter op de juiste manier, dus dat zit goed. Er zijn nog wat andere op- en aanmerkingen, maar die zijn van minder belang. (Heb je toevallig eerder iets met C gedaan?)
Heb het nu ook eindelijk voor elkaar dat mijn code palindromen herkent en opslaat in een vector. Nu nog al die producten genereren, of iets slims gaan bedenken want ik weet niet hoe lang het duurt als ik ze allemaal ga genereren
Alle produkten van 2 driecijferige getallen controleren op palindroom zijn, dat zou op de meest naïeve wijze niet meer dan een fractie van een seconde moeten duren.quote:Op zaterdag 28 juli 2012 23:54 schreef thenxero het volgende:
Heb het nu ook eindelijk voor elkaar dat mijn code palindromen herkent en opslaat in een vector. Nu nog al die producten genereren, of iets slims gaan bedenken want ik weet niet hoe lang het duurt als ik ze allemaal ga genereren
Bij dit soort problemen kun je als vuistregel gebruiken dat je ongeveer 50 miljoen groepjes van simpele operaties per seconde kunt doen. Met brute force heb je minder dan 1k*1k = 1M mogelijkheden en de palindroom test vergt 6 stappen. Dus gaat makkelijk lukken binnen een seconde. Het is wel handig om zulk soort worst case analyses te doen, zeker als je een exponentieel algoritme hebt bedachtquote:
Heb het nu ook eindelijk voor elkaar dat mijn code palindromen herkent en opslaat in een vector. Nu nog al die producten genereren, of iets slims gaan bedenken want ik weet niet hoe lang het duurt als ik ze allemaal ga genereren
.Morgen ga ik ook weer eens project euler proberen, maar dan wel in python
.
quote:Op zondag 29 juli 2012 00:02 schreef thabit het volgende:
[..]
Alle produkten van 2 driecijferige getallen controleren op palindroom zijn, dat zou op de meest naïeve wijze niet meer dan een fractie van een seconde moeten duren.
Ah, handig zo'n vuistregel. Dan moet je waarschijnlijk wel wat beter programmeren dan dat ik het gedaan heb, want hier duurt het 21 secquote:Op zondag 29 juli 2012 00:43 schreef Wolfje het volgende:
[..]
Bij dit soort problemen kun je als vuistregel gebruiken dat je ongeveer 50 miljoen groepjes van simpele operaties per seconde kunt doen. Met brute force heb je minder dan 1k*1k = 1M mogelijkheden en de palindroom test vergt 6 stappen. Dus gaat makkelijk lukken binnen een seconde. Het is wel handig om zulk soort worst case analyses te doen, zeker als je een exponentieel algoritme hebt bedacht
Morgen ga ik ook weer eens project euler proberen, maar dan wel in python
. Hij geeft nu wel het goede antwoord. Waar gaat al die tijd heen?-code weg-
[ Bericht 13% gewijzigd door thenxero op 29-07-2012 10:35:51 ]
Ik denk dat het netter is om geen complete oplossingen te posten. Immers, andere mensen willen het ook zelf oplossen. Misschien kan je de code weghalen en vervangen door pseudo-code van de relevante gedeeltes?quote:
Ah, handig zo'n vuistregel. Dan moet je waarschijnlijk wel wat beter programmeren dan dat ik het gedaan heb, want hier duurt het 21 sec
[ code verwijderd ]
Maar als antwoord over waar al die tijd heen gaat: hoe vaak roep je digit() en numDigits() aan per getal dat je controleert? Zou je dat terug kunnen brengen?
En is er een snelle controle die je kunt doen om te kijken of je een getal [s] uberhaupt hoeft te controleren? Gecombineerd met deze lopmerking kan je ook wat tijd winnen door te bedenken waar het getal dat je zoekt zich waarschijnlijk bevindt in je zoekgebied en de zoekruimte in een andere volgorde doorlopen.
"Slechts diegene mag slopen die iets beters kan bouwen."
Geheugenallocatie is vrij duur en dat doe je nu juist heel vaak met de vector<int> in de digit() methode. Een bijkomend nadeel is dat je veel zogenaamde cache misses zult hebben. Een cpu kan data in lokaal geheugen (op de cpu zelf) opslaan om het later weer snel op te kunnen vragen. Maar als je de hele tijd nieuwe data maakt, kan de cpu er ook geen gebruik van maken.quote:
[..]
[..]
Ah, handig zo'n vuistregel. Dan moet je waarschijnlijk wel wat beter programmeren dan dat ik het gedaan heb, want hier duurt het 21 sec
[ code verwijderd ]
Heb het met die tips teruggebracht naar 0.4sec (die staan natuurlijk ook op EP, dus daar ging het eigenlijk niet om). Maar omdat thabit zei dat het op de meest naïeve manier nog een fractie van een seconde zou duren als je alle palindromen zou controleren, dacht ik dus dat er een soort fout in mijn code zat.
Maar als ik het goed begrijp kost het steeds callen van een functie veel tijd. Is het dan beter om die functie te verwerken in de main?
Maar als ik het goed begrijp kost het steeds callen van een functie veel tijd. Is het dan beter om die functie te verwerken in de main?
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:
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:
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;?
