C++ if文の順序

Question

プログラムの一部は、順序付きリストを検索する際に2つのc-stringが同一であるかどうかを確認する必要があります（例：{"AAA", "AAB", "ABA", "CLL", "CLZ"}）。リストがかなり大きくなる可能性があるので、速度のわずかな向上は可読性の低下に値する。あなたがC++に制限されていると仮定します（アセンブリへの切り替えを推奨しないでください）。どのように改善することができますか？

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); 
    } 
} 

あなたはstringXとstringYが常に同じ長さであると仮定することができますし、無効なデータ入力を取得することはありません。

コンパイラは、CPUが最初のif文をチェックして偽であればジャンプするようにコードを作成するので、最初の文が真である可能性が最も高い場合に最適ですジャンプがパイプラインに干渉します。私は、比較を行うときに、[n Intel] CPUが減算を行い、減算の結果を保存せずにフラグの状態を調べると聞いています。 strcmpを1回実行し、結果を変数に保存せずに、最初の2つのif文の両方でその結果を確認することはできますか？

Answer 1

std::binary_searchは助けることがあります。

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

ハッシュテーブルを使用すると、比較の速度が大幅に向上すると思います。また、プログラムがマルチスレッド化されている場合は、intelスレッドビルディングブロックライブラリで有用なハッシュテーブルを見つけることができます。たとえば、tbb :: concurrent_unordered_mapはstd :: unordered_mapと同じapiを持っています

私はそれがあなたを助けてくれることを願っています。

Answer 3

を使用すると、お互いにすべての文字列を比較しようとする場合は、O(N*(N-1))問題で取得します。リストが大きくなる可能性があると主張しているように（qsortアルゴリズムはO(N*log(N))です）の各要素をリストの次の要素と比較すると、合計がO(N*log(N))の合計複雑度を与えるO(N)が追加されます。 がすでにに注文されているので、各要素を次の要素と比較するだけで、それをトラバースすることができます（O(N)ということになります）。 CやC++で有効な例は、以下の：

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 */ 
}