「展平」std :: set <std::string>用於存儲和比較？

Question

這可能是一個愚蠢的問題，基於std :: set <>已經有完美的比較運算符的事實，但我想我可能會對我的特定用例進行優化，並且要確保我沒有傷害到自己不知何故。

基本上，我有一個昂貴的操作，需要輸入std :: set &。我緩存操作的結果，這樣我就可以返回的結果，如果相同的輸入已經在過去。這確實需要存儲套複印件（我做的

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

，然後每次調用操作時都要搜索一次，因爲很可能連續調用同一個操作數千次，所以我會說緩存的std :: set在99％以上的時間內找到了。最近，我根據傳入字符串中某些字符無效的事實，嘗試了一些我認爲可能的小改進：我將std :: set壓扁成單個字符串，組件字符串用'：'分隔。 '字符，然後我的std :: map變成

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

並且每次調用該操作時，都會將該集合展平並在緩存中搜索單個字符串。

我實際上對性能改進感到驚訝。我的測試運行使用包含5個字符串的std :: sets，每個字符串長30個字符，並且運行10,000,000次搜索。在我的工作站，每次運行的時間分別爲

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::string緩存而導致搜索操作更快，與std::set相比，搜索操作更快。

Answer 2

我會考慮寫一個小的包裝器來跟蹤它的地址和版本號。它將包括修改該組的操作的重載（插入，擦除等），並且當插入/擦除發生時，它會增加版本號。

然後爲了確定相等性，你只看兩件事：集合的地址和版本號。如果修改相當罕見，並且對平等的測試相當普遍，那麼在比較中節省的時間可能會比跟蹤更改所花費的時間大得多 - IOW，您將獲得巨大的速度優勢。

如果你必須寫一個完整的包裝（一個暴露所有的set的功能）這很可能是大量的工作。但在大多數情況下，這是不必要的。最典型的代碼只需要幾個功能就可以看到 - 通常只有兩個或三個。

#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"; 
}