Citat:
Ursprungligen postat av
FaderBerg
Såvida du inte sorterar enkla datatyper så behöver du ändå en compare-funktion och då är ju fördelen borta. Då kan man ju dessutom diskutera huruvida std::sort är genrell i det avseendet du vill göra gällande.
Citat:
Ursprungligen postat av
Da
Många i tråden verkar inte tro på mig... så jag provade att sortera 10 miljoner tal slumpmässigt valda mellan 0 och 1 miljon.
C++:
Kod:
std::sort(v.data(), v.data() + n);
C:
Kod:
static int compare(const void* pa, const void* pb) {
// Testat lite olika implementationer här... verkar inte göra någon skillnad.
int a = *(int*)pa;
int b = *(int*)pb;
return a - b;
}
qsort(u.data(), n, sizeof(int), compare);
Visual Studio 2015:
C++: 0.82 sekunder.
C: 1.63 sekunder.
GCC 5.3.1:
C++: 0.68 sekunder.
C: 1.45 sekunder.
Clang 3.8: (här körde jag 100 miljoner tal instället för jag kunde bara mäta hela sekunder)
C++: 7 sekunder
C: 14 sekunder
Alltså är C++-funktionen cirka dubbelt så snabb som C-funktionen. Detta eftersom man i C++ kan bygga bibliotek som kompilatorn kan inlina mycket mer aggresivt. I C måste man ofta, om man vill skriva generisk, återanvändbar kod, använda sig av konstruktionen som omöjliggör vissa optimeringar. Detta gäller för alla dagens kompilatorer.
Alltså kan man i denna mening säga att C++ är ett snabbare språk än C.
(Skillnaden var mindre än artikeln jag citerade. Kanske på grund av att mer tid i dagens processorer spenderas på att läsa från minnet.)
Men titta på det först citerade inlägget det som
FaderBerg lade in att så länge du sorterar enkla datatyper ( i detta fallet ints) så kan det vara så att C++ kan optimera detta bättre genom inlining eftersom C++ är lite av modernare snitt. Skulle du sortera någon mer komplex datastruktur så tror jag att skillnaden blir liten.
Tips att testa: skriv en enkel bubblesort för C++ och en likadan för C kör dessa olika kodsegment på samma set av data på komplexare datatyper, dvs typ där en compare är tvungen att ha en intern loop (en sådan kan vanligtvis sällan inlinas), då kommer du att få ungefär samma resultat, skalar du upp testet så följer den skalningen enligt en standard bubblesort.
Det är alltså bara sorteringsalgoritmen som bestämmer hur snabbt det går, efterhand som N ökar. Och tiden är förutsägbar utifrån vilket N som väljs och vilken algoritm som används, inte språket. Man kan också utifrån tiden att sortera N objekt, N + 100 objekt och N + 200 objekt räkna ut hur lång tid det tar att sortera N + XXXX objekt, denna ökning av tiden är bara beroende på algoritmen, förutsatt att data är slumpmässig. Föreslår att du läser igenom sorterings teoremen om olika metoder.
Det finns dock genvägar att gå för just compare funktionen och förr så använde man bla makros för detta pga att då används inte stacken för varje anrop, men sparade därmed upp till ca 4 instruktioner i enkla fall.
Dock bör man vara fundersam om man ska använda makros i rekursiva sammanhang av sortering, och tänka igenom det hela noggrant.
Det finns dock en brasklapp i det här, om hela arrayen kan laddas in i CPUns cache så går det bra fortare pga att cachen har samma hastighet som CPUn. Måste CPUn hämta stora segment av arrayaen ifrån ett relativt slött RAM så segar det ner rätt rejält. C++ av senare snitt har kanske bättre cache-optimering inbyggd.
Nu vet ja inte riktigt om du egentligen menar att std::sort(....) är snabbare än qsort men i så fall är deras algoritmer troligen olika, än att det har med språket att göra,
Hursomhelst så väcker frågeställningen frågan om hur man kan förbättra sorteringen, men i de flesta falll så är vanligen datasettet så litet i MB räknat att man kan tåla den tid det tar även om metoden inte alltid är optimalt för just det settet.
Faktum är att en compare-funktion alltid används av std::sort internt. Det finns ett default-funktion som bara använder "<".
