値がstlコンテナに既に存在するかどうかを確認する最速の方法

Question

私は非常に大きなメモリアドレス（約400.000）のリストを保持しており、特定のアドレスがすでに400.000回あるかどうかを確認する必要があります。私のセットアップを説明するため

コード例：

std::set<uintptr_t> existingAddresses; // this one contains 400.000 entries 

while (true) { 
    // a new list with possible new addresses 
    std::set<uintptr_t> newAddresses; // also contains about ~400.000 entries 

    // in my own code, these represent a new address list 
    for (auto newAddress : newAddresses) { 

     // already processed this address, skip it 
     if (existingAddresses.find(newAddress) != existingAddresses.end()) { 
      continue; 
     } 

     // we didn't have this address yet, so process it. 
     SomeHeavyTask(newAddress); 

     // so we don't process it again 
     existingAddresses.emplace(newAddress); 
    } 

    Sleep(1000); 
} 

これは私が思い付いたし、私はそれを大幅に向上させることができると思う最初の実装です。

次は、データベースでも使用されているカスタムインデックス作成戦略を思いつきました。アイデアは価値の一部をとり、それを使ってそれ自身のグループ・セットでそれを索引付けすることです。私は、例えば、アドレスの最後の2つの数値を取る場合、私は内のアドレスを入れて16^2 = 256グループを持っているでしょう

だから私はこのようなマップで終わるでしょう：。これにより

[FF] -> all address ending with `FF` 
[EF] -> all addresses ending with `EF` 
[00] -> all addresses ending with `00` 
// etc... 

私だけでしょう対応するセットの〜360のエントリを検索する必要があります。その結果、〜360のルックアップが400.000回/秒実行されます。ずっといい！

これを行うには、他の方法やより良い方法があるのでしょうか？私の目標は、このアドレス検索を可能な限り高速化することです。

Answer 1

std::set<uintptr_t>はバランスのとれたツリーを使用しているため、ルックアップ時間はO(log N)です。一方 std::unordered_set<uintptr_t>は、参照時刻がO(1)のハッシュベースです。

これは唯一asymptotic complexityメジャーですが、一定の要因が原因で保証される改善がないことを意味しますが、コレクションに400,000個の要素が含まれていると、その差が顕著になることがあります。

Answer 2

あなたはマージする同様のアルゴリズムを使用することがあります。

std::set<uintptr_t> existingAddresses; // this one contains 400.000 entries 

while (true) { 
    // a new list with possible new addresses 
    std::set<uintptr_t> newAddresses; // also contains about ~400.000 entries 
    auto existing_it = existingAddresses.begin(); 
    auto new_it = newAddresses.begin(); 

    while (new_it != newAddresses.end() && existing_it != existingAddresses.end()) { 
     if (*new_it < *existing_it) { 
      // we didn't have this address yet, so process it. 
      SomeHeavyTask(*new_it); 
      // so we don't process it again 
      existingAddresses.insert(existing_it, *new_it); 
      ++new_it; 
     } else if (*existing_it < *new_it) { 
      ++existing_it; 
     } else { // Both equal 
      ++existing_it; 
      ++new_it; 
     } 
    } 
    for (new_it != newAddresses.end()) 
     // we didn't have this address yet, so process it. 
     SomeHeavyTask(*new_it); 
     // so we don't process it again 
     existingAddresses.insert(existingAddresses.end(), *new_it); 
     ++new_it; 
    } 
    Sleep(1000); 
} 

複雑さは今線形である：O(N + M)代わりO(N log M)の（新しいアドレスのN数、および古いもののためMカウントが）。