"平坦化" std :: set <std::string>の保存と比較は可能ですか？

Question

これは、std :: set <>が既に完全に優れた比較演算子を持っているという事実に基づく愚かな質問かもしれませんが、私は特定のユースケースの最適化があり、自分自身を傷つけないようにしたいと思いますどういうわけか。

本質的には、入力としてstd :: set &をとる高価な操作があります。私はその後、同じ入力がすでに渡されている場合、私はちょうど結果を返すことができますので、これは私が

std::map<std::set<std::string>, Result*> 

でやっているセットのコピーを（保存する必要がない。操作の結果をキャッシュし、よ同じ操作が何千回も連続して呼び出される可能性が非常に高いので、キャッシュされたstd :: setは> 99％の時間内に検出されます。私は最近、渡された文字列で特定の文字が無効であるという事実に基づいて、少し改良があると思ったものを試しました。私はstd :: setを単一の文字列に平坦化しました。コンポーネント文字列は '： '文字。私のstd :: mapは

になります3210

std::map<std::string, Result*> 

と呼ばれ、操作が呼び出されるたびに、そのセットは平坦化され、単一の文字列がキャッシュ内で検索されます。

私は実際にパフォーマンスの向上に驚いていました。私のテストでは、5つの文字列、それぞれ30文字の長さ、10,000,000回の実行を含むstd :: setsを使用しました。私のワークステーションでは、それぞれの実行のための時間がそれもセットにすべての呼び出しを平坦化するオーバーヘッドで、第2の方法は大幅に改善され、と思われ

std::map<std::set<std::string>, Result*> : 138.8 seconds 
std::map<std::string, Result>   : 89.2 seconds 

ました。私の質問は、なぜでしょうか？ std :: setの実装者が意図的に回避されている（つまり、より大きな文字列でひどいヒープフラグメンテーションを引き起こす可能性がある）可能性がありますか？単純にセット内の個々の文字列が異なる場所にあり、別々に比較される必要があるからです？私は足で自分を撃っていますか？このようなパフォーマンスを向上させるためには、この特定のケースでの改善があまりにも明白なように思えます。

Answer 1

なぜですか？

データのローカリティ。

std::setは、通常、バイナリ検索ツリーとして実装されます。 std::setと比較して、std::stringのマシンでキャッシングすると検索操作がより高速になる場合があります。

Answer 2

私は、そのアドレスとバージョン番号を追跡するセットの周りに小さなラッパーを書くことを検討します。これには、セットを変更する操作のオーバーロード（挿入、消去など）が含まれ、挿入/消去が行われると、バージョン番号がインクリメントされます。

次に、等価性を判断するために、セットのアドレスとバージョン番号の2つだけを調べます。変更がかなりまれであり、同等性のテストがかなり一般的である場合、比較で保存される時間は、変更を追跡するのにかかる時間よりもはるかに大きい可能性があります。

あなたは完全ラッパー（setの機能をすべてを公開1）を書き込む必要がある場合、これは多くの仕事である可能性が高いです。ほとんどの場合、それは不要です。最も一般的なコードでは、ほんのわずかな機能しか表示されません。

#include <iostream> 
#include <set> 
#include <utility> 

template <class T> 
class tracked_set { 
    std::set<T> data; 
    size_t version = 0; 
public: 
    typedef typename std::set<T>::iterator iterator; 

    std::pair<iterator, bool> insert(T &&d) { 
     auto ret = data.insert(std::forward<T>(d)); 
     version += ret.second; 
     return ret; 
    } 

    iterator erase(iterator i) { 
     auto ret = data.erase(i); 
     if (ret != data.end()) 
      ++version; 
    } 

    // At least if memory serves, even non-const iterators on a `set` don't 
    // allow the set to be modified, so these should be safe. 
    auto begin() { return data.begin(); } 
    auto end() { return data.end(); } 
    auto rbegin() { return data.rbegin(); } 
    auto rend() { return data.rend(); } 

    // The `c*` iterator functions return const_iterator's, so 
    // they're definitely safe. 
    auto cbegin() const { return data.cbegin(); } 
    auto cend() const { return data.cend(); } 
    auto crbegin() const { return data.crbegin(); } 
    auto crend() const { return data.crend(); } 

    class token { 
     std::set<T> const *addr; 
     size_t version; 
    public: 
     friend bool operator==(token const &a, token const &b) { 
      return a.addr == b.addr && a.version == b.version; 
     } 

     token(tracked_set const &ts) { 
      addr = &ts.data; 
      version = ts.version; 
     } 
    }; 

    operator token() const { return token(*this); } 
}; 

int main() { 
    using T = tracked_set<int>; 

    T ts; 

    ts.insert(1); 
    ts.insert(2); 

    T::token t(ts); 

    if (t == T::token(ts)) 
     std::cout << "Good\n"; 

    ts.insert(3); 

    if (t == T::token(ts)) 
     std::cout << "bad\n"; 
}