将 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个字符串（每个字符串长30个字符）的std::set，并运行了1000万次搜索。在我的工作站上，每次运行的时间如下：

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

看起来，即使每次调用时都要展开集合的开销，第二种方法也是一个巨大的改进。 我的问题是：为什么呢？我在这里做了一些潜在的不良行为吗，std::set的实现者故意避免了这些行为（即可能导致更大字符串的堆片段化）？这仅仅是因为集合中的单个字符串位于不同的位置并且必须分别进行比较吗？ 我是否正自我毁灭？ 在这种特定情况下，这似乎是一个太明显的改进，可以给出如此强的性能提升。

- Kevin

---

如果您99%的时间都带有相同的参数调用该函数，那么我会认为问题不在函数本身而在于调用者。不管怎样，您能否给您的集合添加某种“id”，这样方法只需要比较该“id”而不是整个“set”？听起来您传递的集合并不经常更改。 - 463035818_is_not_a_number

我可能有点过于简化了，函数的输入是std::set和2个单独的消息进行比较。该集合描述了在比较之前要应用于消息的转换，而构建此转换是成本高昂的部分（应用它是微不足道的）。该集合几乎始终保持不变，但消息几乎始终不同。理想情况下，调用者应以某种方式获取到转换的句柄，然后在调用比较时使用该句柄而不是集合 - 不幸的是，这需要替换现有代码。 - Kevin

只需确保您的分隔符不能成为实际字符串的一部分，那么您就应该没问题了。此外，每当性能不佳时，请不要忘记使用std::unordered_map或std::unordered_set进行基准测试。但是，字符串并不总是存储在其中的最佳类型，因为您必须读取整个字符串才能生成哈希值，而opreator<可以更早地停止。 - SteakOverflow

考虑到这是一个查找操作，使用unordered_map可能更有效率。此外，当使用字符串作为键时，如果不需要按字母顺序排序，先比较字符串长度可能更有效率。例如，将"z"排在"aa"之前。 - MSalters

Answer 1

为什么？

数据本地性。

std::set 通常被实现为二叉搜索树。与 std::set 相比，使用 std::string 可能会因为在您的机器上进行缓存而使搜索操作更快。

- gsamaras

---

基本上，字符串可以留在CPU缓存中，因此对其进行搜索可能会更快，而集合则不行（它在内存中是稀疏的）。有关“数据局部性”的更多信息，请参见：http://gameprogrammingpatterns.com/data-locality.html - roalz

@roalz 哦，我懂了。谢谢。 - YSC

Answer 2

我会考虑编写一个小的包装器来跟踪set的地址和版本号。它将包括修改set的操作（插入、删除等）的重载，当发生插入/删除时，它会增加版本号。

然后，为了确定相等性，您只需要查看两个东西：集合的地址和版本号。如果修改很少，而测试相等性很常见，则在比较上节省的时间可能比跟踪更改所花费的时间要大得多--也就是说，您可以获得巨大的速度优势。

如果您必须编写一个完整的包装器（暴露所有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";
}

- Jerry Coffin