Ist “==” in einem sortierten Array nicht schneller als ein unsortiertes Array? [duplicate]
Lesezeit: 6 Minuten
ggrr
Hinweis: Die angebliche doppelte Frage bezieht sich meiner Meinung nach hauptsächlich auf den Vergleich von “<" und ">“, aber nicht auf den Vergleich von “==” und beantwortet daher nicht meine Frage zur Leistung des Operators “==”.
Ich habe lange geglaubt, dass die “Verarbeitung” eines sortierten Arrays schneller sein sollte als ein unsortiertes Array. Zuerst dachte ich, dass die Verwendung von “==” in einem sortierten Array schneller sein sollte als in einem unsortierten Array, weil – denke ich – die Verzweigungsvorhersage funktioniert:
UNSORTIERTES ARRAY:
5 == 100 F
43 == 100 F
100 == 100 T
250 == 100 F
6 == 100 F
(other elements to check)
SORTIERTE ARRAY:
5 == 100 F
6 == 100 F
43 == 100 F
100 == 100 T
(no need to check other elements, so all are F)
also denke ich, dass SORTEDARRAY schneller sein sollte als UNSORTEDARRAY, aber heute habe ich den Code verwendet, um 2 Arrays in einem Header zum Testen zu generieren, und die Verzweigungsvorhersage schien nicht so zu funktionieren, wie ich dachte.
Ich habe ein unsortiertes Array und ein sortiertes Array zum Testen generiert:
srand(time(NULL));
int UNSORTEDARRAY[524288];
int SORTEDARRAY[sizeof(UNSORTEDARRAY)/sizeof(int)];
for(int i=0;i<sizeof(SORTEDARRAY)/sizeof(int);i++){
SORTEDARRAY[i]=UNSORTEDARRAY[i]=rand();
}
sort(SORTEDARRAY,SORTEDARRAY+sizeof(SORTEDARRAY)/sizeof(int));
string u="const int UNSORTEDARRAY[]={";
string s="const int SORTEDARRAY[]={";
for(int i=0;i<sizeof(UNSORTEDARRAY)/sizeof(int);i++){
u+=to_string(UNSORTEDARRAY[i])+",";
s+=to_string(SORTEDARRAY[i])+",";
}
u.erase(u.end()-1);
s.erase(s.end()-1);
u+="};\n";
s+="};\n";
ofstream out("number.h");
string code=u+s;
out << code;
out.close();
zählen Sie also zum Testen einfach, ob der Wert == RAND_MAX/2 ist:
#include "number.h"
int main(){
int count;
clock_t start = clock();
for(int i=0;i<sizeof(SORTEDARRAY)/sizeof(int);i++){
if(SORTEDARRAY[i]==RAND_MAX/2){
count++;
}
}
printf("%f\n",(float)(clock()-start)/CLOCKS_PER_SEC);
}
3x laufen:
UNSORTIERTE REIHE
0.005376
0.005239
0.005220
SORTIERTE ARRAY
0.005334
0.005120
0.005223
Es scheint ein kleiner Leistungsunterschied zu sein, also habe ich es nicht geglaubt und dann versucht, “SORTEDARRAY[i]==RAND_MAX/2” bis “SORTEDARRAY[i]>RAND_MAX/2”, um zu sehen, ob es einen Unterschied gemacht hat:
UNSORTIERTE REIHE
0.008407
0.008363
0.008606
SORTIERTE ARRAY
0.005306
0.005227
0.005146
Diesmal gibt es einen großen Unterschied.
Ist “==” im sortierten Array nicht schneller als ein unsortiertes Array? Wenn ja, warum ist “>” in einem sortierten Array schneller als ein unsortiertes Array, aber “==” nicht?
Bezogen auf eine der am meisten positiv bewerteten Fragen aller Zeiten: stackoverflow.com/questions/11227809/…
– Andrzej Pronobis
18. August 2015 um 3:59 Uhr
“Ich glaube, die “Verarbeitung” eines sortierten Arrays sollte schneller sein als ein unsortiertes Array”: Versuchen Sie sich selbst zu beantworten, warum Sie glauben, dass dies für diesen Algorithmus gilt. Das heißt, welche Art von Arbeit und wie viel davon Sie für jeden Fall tun. Sie können erkennen, was die Antwort ist.
– Viraptor
18. August 2015 um 4:02 Uhr
string ist kein Standardtyp in C, und die Verwendung von += Operator mit einem Operanden vom Typ string und der andere char * macht keinen Sinn. Sind Sie sicher, dass dies kein C++-Code ist?
– autistisch
18. August 2015 um 5:29 Uhr
Was verwenden Sie außerdem, um diesen Code zu timen? Etwas sehr ungenau und wahrscheinlich voreingenommen. Diese Art von Frage wird normalerweise von falsch informierten Personen geschrieben. Haben Sie überhaupt die vollständige Optimierung aktiviert? Haben Sie ein wirklich realistisches Problem zu lösen und ein Programm, um dieses Problem zu lösen? Verwenden Sie einen Profiler für dieses Programm, um festzustellen, was die wesentlichen Engpässe sind? Der Grund, warum ich frage, ist, dass die Engpässe in jedem realistischen Szenario erheblich von dem abweichen werden, was Sie beschrieben haben. Diese Frage hat keinen praktischen Nutzen.
– autistisch
18. August 2015 um 5:35 Uhr
Warum nehmen Sie an “(keine Notwendigkeit, andere Elemente zu überprüfen, also sind alle F)”? Der Compiler kann das nicht wissen, er wird einfach blind jeden Speicherplatz inspizieren. Tatsächlich wird er bei Verwendung von Zufallsdaten nur selten gleich einem festen Wert sein, wodurch er von der CPU sehr leicht vorhergesagt werden kann.
– Mihai Timar
23. Februar 2017 um 12:42 Uhr
Eine Sache, die einem sofort in den Sinn kommt, ist der Verzweigungsvorhersagealgorithmus der CPU.
Im Falle von > Im Vergleich dazu ist das Verzweigungsverhalten in sortierten Arrays sehr konsistent: Erstens, die if Bedingung konsequent falsch ist, dann ist sie konsequent wahr. Dies passt selbst zur einfachsten Verzweigungsvorhersage sehr gut.
In unsortiertem Array das Ergebnis von > Die Bedingung ist im Wesentlichen zufällig, wodurch jede Verzweigungsvorhersage vereitelt wird.
Dadurch wird die sortierte Version schneller.
Im Falle von == Im Vergleich dazu ist die Bedingung meistens falsch und nur sehr selten wahr. Dies funktioniert gut mit der Verzweigungsvorhersage, unabhängig davon, ob das Array sortiert ist oder nicht. Die Zeiten sind im Wesentlichen gleich.
imallett
NB Ich mache dies zu einer Antwort, da es für einen Kommentar zu lang ist.
Die Wirkung hier ist genau das, was in den zahlreichen Antworten auf diese Frage bereits sehr ausführlich erläutert wurde. Die Verarbeitung eines sortierten Arrays war in diesem Fall aufgrund der Verzweigungsvorhersage schneller.
Auch hier ist die Verzweigungsvorhersage der Übeltäter. Das == Der Test ist sehr selten wahr, daher funktioniert die Verzweigungsvorhersage für beide ungefähr gleich. Als Sie es geändert haben >dann haben Sie das in dieser Frage erklärte Verhalten und aus demselben Grund.
Moral:
Ich glaube, dass die “Verarbeitung” eines sortierten Arrays schneller sein sollte als [an ]unsortiertes Array.
Du musst wissen warum. Das ist keine magische Regel, und es ist nicht immer wahr.
Der Vergleich == hat weniger mit dem Bestellen zu tun als > tut. Richtig oder falsch vorhersagen == nur von der Anzahl der doppelten Werte und deren Verteilung abhängen würde.
Sie können verwenden perf stat um die Leistungszähler anzuzeigen…
Bezogen auf eine der am meisten positiv bewerteten Fragen aller Zeiten: stackoverflow.com/questions/11227809/…
– Andrzej Pronobis
18. August 2015 um 3:59 Uhr
“Ich glaube, die “Verarbeitung” eines sortierten Arrays sollte schneller sein als ein unsortiertes Array”: Versuchen Sie sich selbst zu beantworten, warum Sie glauben, dass dies für diesen Algorithmus gilt. Das heißt, welche Art von Arbeit und wie viel davon Sie für jeden Fall tun. Sie können erkennen, was die Antwort ist.
– Viraptor
18. August 2015 um 4:02 Uhr
stringist kein Standardtyp in C, und die Verwendung von+=Operator mit einem Operanden vom Typstringund der anderechar *macht keinen Sinn. Sind Sie sicher, dass dies kein C++-Code ist?– autistisch
18. August 2015 um 5:29 Uhr
Was verwenden Sie außerdem, um diesen Code zu timen? Etwas sehr ungenau und wahrscheinlich voreingenommen. Diese Art von Frage wird normalerweise von falsch informierten Personen geschrieben. Haben Sie überhaupt die vollständige Optimierung aktiviert? Haben Sie ein wirklich realistisches Problem zu lösen und ein Programm, um dieses Problem zu lösen? Verwenden Sie einen Profiler für dieses Programm, um festzustellen, was die wesentlichen Engpässe sind? Der Grund, warum ich frage, ist, dass die Engpässe in jedem realistischen Szenario erheblich von dem abweichen werden, was Sie beschrieben haben. Diese Frage hat keinen praktischen Nutzen.
– autistisch
18. August 2015 um 5:35 Uhr
Warum nehmen Sie an “(keine Notwendigkeit, andere Elemente zu überprüfen, also sind alle F)”? Der Compiler kann das nicht wissen, er wird einfach blind jeden Speicherplatz inspizieren. Tatsächlich wird er bei Verwendung von Zufallsdaten nur selten gleich einem festen Wert sein, wodurch er von der CPU sehr leicht vorhergesagt werden kann.
– Mihai Timar
23. Februar 2017 um 12:42 Uhr