optimering av c++-kod

[Jalle_88]

Jag har en skoluppgift som går ut på att implementera en vektorklass i c++. Jag tror att all funktionalitet fungerar hyffsat, men problemet är att koden är för långsam.

Rättningen går till så att man skickar in koden till en sida, och där körs den automatiskt, och när vi kör vår så får vi alltid "time limit exceeded".

Så frågan är hur vi kan göra vår kod snabbare. Tidsgränsen är två sekunder, och de snabbaste har gjort det på 0.43 sekunder, så vi måste göra något rejält misstag i vår kod.

[David Andersson]

Jag tror att all funktionalitet fungerar hyffsat, men problemet är att koden är för långsam.

Kan du körnings-profilera programmet så att du ser var den använder mest tid?

Det står kommentarer om hur göra snabbare vid konstruktorer och accessor (op[]), men de tror jag inte är nåt problem. "Unwind"-grejen i konstruktorerna tror jag inte hjälper, eftersom C++ bör kunna optimera en vanlig loop rätt bra, kanske t.o.m kan vara en aning bättre utan "unwind".

Potential 1:

Det verkar finnas en mekanism att ha f_elm extra platser förallokerade för vektorn att växa i, men om jag fattat rätt så när den väl nåt gränsen och måste allokera om hela vektorn så allokerar den inte flera nya att växa i (ny f_elm>0) utan bara en till för det nya elementet, och varje ny insert/push_back leder till en omallokering av hela vektorn.

Potential 2:

Alla sorterings-metoderna använder ineffektiva algoritmer som är O(n^2) (utom fuskversionen, men den funkar ju inte).

[Jalle_88]

Tack så mycket för svaret!

jag vet inte hur man körningsprofilerar ett program... men jag skall försöka kolla upp det. Är det något som kan göras i gdb?

Hela grejen med att unwinda loopar var ju ett rätt desperat försök att jag millisekunder, som att komma till en översvämning med ett öskar och en rulle hushållspapper...

Det stämmer helt det du säger om f_elm och allokeringen av nya objekt, men den tanken har faktiskt slagit oss också, och vi har provat med att allokera upp till 1000 platser extra, men det hjälpte inte.

Vi vet att sorteringsmetoderna är ineffektiva, men det är väl ungefär vad vi klarar av. Den som körs nu, med den inbyggda std::sort, fungerar, men det går fortfarande för långsamt.

Som sagt så måste det vara något rejält misstag vi gör. Problemet är också att vi vet inte vad exakt som testas, eller hur lång tid det tar, bara att det tar mer än två sekunder.

[David Andersson]

jag vet inte hur man körningsprofilerar ett program... men jag skall försöka kolla upp det. Är det något som kan göras i gdb?

Vet inte. Med nåt verktyg i gnus låda ska det gå.

I main() så testas med ungefär 7 element. Även en klantig sortering eller omallokering vid varje insert går skitfort med 7 element, eller med 100. Först med tusentals eller tiotusentals element så borde sån ineffektivitet börja märkas i sekunder. Gör egna test med minst tusen element.

Det stämmer helt det du säger om f_elm och allokeringen av nya objekt, men den tanken har faktiskt slagit oss också, och vi har provat med att allokera upp till 1000 platser extra, men det hjälpte inte.

Kan det vara en bugg som gjorde att den ändå allokerade om allt varje gång?
Tusen insert med omallokerade varje gång skulle jag tro tar mer cpu än en O(n^2) sortering av tusen element.

Problemet är också att vi vet inte vad exakt som testas,

Det är ju lite besvärligt att inte få veta vad som testas, bara att den gick fel. Men faktiskt väldigt nyttigt. Bra utbildning det där.