C++ if Anweisung Reihenfolge

Question

Ein Teil eines Programms muss prüfen, ob zwei C-Strings identisch sind, während der Suche durch eine geordnete Liste (z. B. {"AAA", "AAB", "ABA", "CLL", "CLZ"}). Es ist möglich, dass die Liste ziemlich groß wird, so dass kleine Verbesserungen der Geschwindigkeit die Lesbarkeit beeinträchtigen. Angenommen, Sie sind auf C++ beschränkt (schlagen Sie nicht vor, zur Baugruppe zu wechseln). Wie kann das verbessert werden?

typedef char StringC[5]; 
void compare (const StringC stringX, const StringC stringY) 
{ 
    // use a variable so compareResult won't have to be computed twice 
    int compareResult = strcmp(stringX, stringY); 
    if (compareResult < 0) // roughly 50% chance of being true, so check this first 
    { 
     // no match. repeat with a 'lower' value string 
     compare(stringX, getLowerString()); 
    } 
    else if (compareResult > 0) // roughly 49% chance of being true, so check this next 
    { 
     // no match. repeat with a 'higher' value string 
     compare(stringX, getHigherString()); 
    } 
    else // roughly 1% chance of being true, so check this last 
    { 
     // match 
     reportMatch(stringY); 
    } 
} 

können Sie davon ausgehen, dass stringX und stringY sind immer gleich lang, und Sie werden keine ungültige Dateneingabe erhalten.

Von was ich verstehe, wird ein Compiler den Code so machen, dass die CPU die erste if-Anweisung überprüft und springt, wenn sie falsch ist, also wäre es am besten, wenn diese erste Aussage am wahrscheinlichsten wahr ist Sprünge stören die Pipeline. Ich habe auch gehört, dass bei einem Vergleich eine [n Intel] CPU eine Subtraktion durchführt und den Status von Flags betrachtet, ohne das Ergebnis der Subtraktion zu speichern. Wäre es möglich, die strcmp einmal auszuführen, ohne das Ergebnis in einer Variablen zu speichern, aber dieses Ergebnis während der beiden ersten if-Anweisungen noch überprüfen zu können?

Answer 1

std::binary_search kann helfen:

bool cstring_less(const char (&lhs)[4], const char (&rhs)[4]) 
{ 
    return std::lexicographical_compare(std::begin(lhs), std::end(lhs), 
             std::begin(rhs), std::end(rhs)); 
} 

int main(int, char**) 
{ 
    const char cstrings[][4] = {"AAA", "AAB", "ABA", "CLL", "CLZ"}; 
    const char lookFor[][4] = {"BBB", "ABA", "CLS"}; 

    for (const auto& s : lookFor) 
    { 
     if (std::binary_search(std::begin(cstrings), std::end(cstrings), 
           s, cstring_less)) 
     { 
      std::cout << s << " Found.\n"; 
     } 
    } 
} 

Demo

Answer 2

Ich denke, Hash-Tabellen können die Geschwindigkeit des Vergleichs drastisch verbessern. Wenn Ihr Programm Multithread ist, können Sie auch einige nützliche Hash-Tabellen in der Bibliothek der Intel-Thread-Bausteine ​​finden. Zum Beispiel hat tbb :: concurrent_unordered_map die gleiche api wie std :: unordered_map

Ich hoffe es hilft Ihnen.

Answer 3

Wenn Sie versuchen, alle Fäden miteinander vergleichen Sie in einem O(N*(N-1)) Problem zu bekommen. Die beste Sache, wie Sie die Listen groß haben können, ist sie zu sortieren (Algorithmus hat O(N*log(N))) und dann jedes Element mit dem nächsten in der Liste, die eine neue O(N) ergibt insgesamt O(N*log(N)) Gesamtkomplexität . Da Sie die Liste bereits bestellt haben, können Sie es einfach durchlaufen (die Sache O(N) machend) und jedes Element mit dem nächsten vergleichen. Ein Beispiel, gültig in C und C++ folgt:

for(i = 0; i < N-1; i++) /* one comparison less than the number of elements */ 
    if (strcmp(array[i], array[i+1]) == 0) 
     break; 
if (i < N-1) { /* this is a premature exit from the loop, so we found a match */ 
    /* found a match, array[i] equals array[i+1] */ 
} else { /* we exhausted al comparisons and got out normally from the loop */ 
    /* no match found */ 
}