Hinweis: die angebliche doppelte Frage ist, denke ich, meist bezogen auf "<" und ">" Vergleich, aber nicht "==" Vergleich und daher nicht meine Frage nach der Leistung des "==" -Operators.Ist "==" im sortierten Array nicht schneller als unsortiertes Array?
Ich habe lange geglaubt, dass die "Verarbeitung" eines sortierten Arrays schneller sein sollte als ein unsortiertes Array. Zuerst dachte ich, "==" in sortierten Array sollte schneller sein als in unsortierten Array, weil - ich denke - wie Verzweigungsvorhersage arbeitet:
UNSORTEDARRAY:
5 == 100 F
43 == 100 F
100 == 100 T
250 == 100 F
6 == 100 F
(other elements to check)
SORTEDARRAY:
5 == 100 F
6 == 100 F
43 == 100 F
100 == 100 T
(no need to check other elements, so all are F)
Also ich denke, SORTEDARRAY sollte schneller sein als UNSORTEDARRAY, aber heute habe ich den Code verwendet, um 2 Arrays in einem Header zu testen, und Zweig Vorhersage schien nicht zu funktionieren, wie ich dachte.
I eine unsortierte Array und ein sortiertes Array zu Test 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();
so zu testen, zählen nur, wenn der Wert == RAND_MAX/2 ist wie folgt:
#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);
}
Lauf 3 Zeiten:
UNSORTEDARRAY
0.005376
0.005239
0.005220
SORTEDARRAY
0.005334
0.005120
0.005223
scheint es einen kleinen Unterschied in der Leistung, so dass ich es nicht glauben, und dann versucht, ändern "SORTEDARRAY [i] == RAND_MAX/2" bis "SORTEDARRAY [i]> RAND_MAX/2" um zu sehen, ob es einen Unterschied gemacht:
UNSORTEDARRAY
0.008407
0.008363
0.008606
SORTEDARRAY
0.005306
0.005227
0.005146
Diesmal gibt es einen großen Unterschied.
Ist "==" im sortierten Array nicht schneller als unsortiertes Array? Wenn ja, warum ist ">" im sortierten Array schneller als ein unsortiertes Array, aber "==" nicht?
Bezug zu einem der upvoted Fragen aller Zeiten: http://stackoverflow.com/questions/11227809/why-is- processing-a-sorted-array-schneller-als-unsortiertes-array –
"Ich glaube," Verarbeitung "sortierte Array sollte schneller sein als unsortierte Array": versuchen Sie selbst zu beantworten, warum Sie denken, dass das für diesen Algorithmus wahr ist. Das ist - welche Art von Arbeit und wie viel davon Sie für jeden Fall tun. Sie können erkennen, was die Antwort ist. – viraptor
'string' ist kein Standardtyp in C und die Verwendung des' + = 'Operators mit einem Operanden vom Typ' string' und dem anderen 'char *' macht keinen Sinn. Sind Sie sicher, dass dies kein C++ - Code ist? – Sebivor