如何在密钥类型为std :: string的地图查找中提高性能？

Question

我正在使用std::map（VC ++实现），并且通过map的find方法查找速度有点慢。

密钥类型是std::string。

我可以通过地图的自定义键比较覆盖来提高此string::size()查找的性能吗？例如，也许<=> <！> lt; compare在比较数据之前没有考虑简单的<=>比较？

加快比较的其他想法？

在我的情况下，地图将始终包含<！> lt; 15个元素，但它被不停地查询，性能至关重要。也许我可以使用更好的数据结构更快？

更新：地图包含文件路径。

Update2：地图的元素经常变化。

Answer 1

首先，关闭所有分析和DEBUG开关。这些可以极大地减缓STL。

如果不是这样，问题的一部分可能是你的字符串对于字符串的前80-90％是相同的。这对于地图来说也不错，但它是用于字符串比较的。如果是这种情况，您的搜索可能需要更长时间。

例如，在这段代码中，find（）可能会导致几个字符串比较，但每个字符串比较之后都会返回，直到<！>“david <！>”，然后是前三个字符将被检查。因此，每次调用最多可检查5个字符。

map<string,int> names;
names["larry"] = 1;
names["david"] = 2;
names["juanita"] = 3;

map<string,int>::iterator iter = names.find("daniel");

另一方面，在以下代码中，find（）可能会检查135个以上的字符：

map<string,int> names;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/wilma"] = 1;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/fred"] = 2;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/barney"] = 3;

map<string,int>::iterator iter = names.find("/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/betty");

那是因为字符串比较必须更深入地搜索才能找到匹配项，因为每个字符串的开头都是相同的。

在比较中使用size（）表示相等对你的帮助不大，因为你的数据集很小。 std :: map保持排序，因此可以使用二进制搜索来搜索其元素。每次查找调用都应该导致未命中的字符串比较少于5次，并且命中的平均值为2次比较。但它确实取决于您的数据。如果你的大多数路径字符串都有不同的长度，那么像Motti描述的大小检查可能会有很大的帮助。

在考虑替代算法时需要考虑的事情是多少次<！>“命中<！>你得到。你的大多数find（）调用是返回end（）还是命中？如果你的find（）的大部分返回end（）（未命中），那么你每次都在搜索整个地图（2logn字符串比较）。

Hash_map是个好主意;它应该将您的搜索时间减少一半左右;更多的是因为未命中。

由于路径字符串的性质，可能会调用自定义算法，特别是如果您的数据集具有上述代码中的共同祖先。

要考虑的另一件事是如何获得搜索字符串。如果您正在重复使用它们，将它们编码为更容易比较的内容可能会有所帮助。如果你使用它们并丢弃它们，那么这个编码步骤可能太贵了。

我曾经（很久以前）使用类似霍夫曼编码树的东西来优化字符串搜索。像这样的二进制字符串搜索树在某些情况下可能更有效，但对于像你这样的小集合来说它非常昂贵。

最后，研究替代的std :: map实现。我听说过一些VC的stl代码性能不好的事情。特别是DEBUG库在每次通话时都会检查你。 StlPort 曾经是一个不错的选择，但我在几年内没有尝试过。我也一直很喜欢 Boost 。

Answer 2

as 偶数表示set中使用的运算符<不==。

如果您不关心string.length中字符串的顺序，则可以传递comp(a, b) == true自定义比较器，该比较器的性能优于常规 。

例如，如果你的很多字符串都有相似的前缀（但长度各不相同），你可以按字符串长度排序（因为comp(b, a) == true是恒定速度）。

如果你这样做，请注意一个常见的错误：

struct comp {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.length() < rhs.length())
            return true;
        return lhs < rhs;
    }
};

此运营商未维护严格的弱订购，您可以使用两个字符串每个都比另一个少。

string a = "z";
string b = "aa";

遵循逻辑，你会看到<=>和<=>。

正确的实施是：

struct comp {
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.length() != rhs.length())
            return lhs.length() < rhs.length();
        return lhs < rhs;
    }
};

Answer 3

第一件事是尝试使用hash_map，如果可能的话 - 你是正确的，标准字符串比较不首先检查大小（因为它按字典顺序进行比较），但编写你自己的地图代码是你的意思最好避免。从你的问题来看，听起来你不需要迭代范围;在那种情况下，map没有任何hash_map没有。

它还取决于您在地图中使用的键类型。它们通常很长吗？还有什么呢？有点慢<！>意思？如果你还没有对代码进行分析，很可能这是一个花费时间的不同部分。

更新：嗯，程序中的瓶颈是map :: find，但地图总是少于15个元素。这让我怀疑这个配置文件在某种程度上是误导性的，因为在地图上找到这么小的应该不会很慢。实际上，map :: find应该如此之快，只是分析的开销可能比查找调用本身更多。我不得不再问一遍，你确定这真的是你程序中的瓶颈吗？你说字符串是路径，但是你没有在这个循环中进行任何类型的OS调用，文件系统访问，磁盘访问？其中任何一个都应该比一个小地图上的map :: find慢几个数量级。实际上获取字符串的任何方式都应该比map :: find。

慢

Answer 4

您可以尝试使用已排序的矢量（此处为一个示例） ，这可能会更快（你必须对其进行分析以确保当然）。

认为它会更快的原因：

1. 更少的内存分配和解除分配（向量将扩展到使用的最大大小，然后重用已释放的内存）。
2. 随机访问的二进制查找应该比树遍历更快（特别是由于数据位置）。

认为它会变慢的原因：

1. 删除和添加将意味着在内存中移动字符串，因为string的swap是有效的，并且数据集的大小很小，这可能不是问题。

Answer 5

std :: map的比较器不是std :: equal_to它的std :: less，我不确定什么是短路<！> lt的最佳方法。比较，以便它比内置的更快。

如果总是<！> lt; 15元，也许你可以使用除了std :: string之外的一个键？

Answer 6

Motti有一个很好的解决方案。但是，我很确定你的<！> lt; 15个元素映射不正确，因为它的开销总是大于具有适当散列方案的简单查找表的开销。在你的情况下，它甚至可能足以单独按长度散列，如果仍然产生冲突，则使用线性搜索所有相同长度的条目。

为了确定我是否正确，当然需要基准，但我很确定其结果。

Answer 7

您可以考虑预先计算字符串的哈希值，并将其保存在地图中。这样做可以在搜索std :: map树时提供散列比较而不是字符串比较的优势。

class HashedString
{
  unsigned m_hash;
  std::string m_string;

public:
  HashedString(const std::string& str)
    : m_hash(HashString(str))
    , m_string(str)
  {};
  // ... copy constructor and etc...

  unsigned GetHash() const {return m_hash;}
  const std::string& GetString() const {return m_string;}
};

这具有在构造时计算字符串的哈希值的好处。在此之后，您可以实现比较功能：

struct comp
{
  bool operator()(const HashedString& lhs, const HashedString& rhs)
  {
    if(lhs.GetHash() < rhs.GetHash()) return true;
    if(lhs.GetHash() > rhs.GetHash()) return false;
    return lhs.GetString() < rhs.GetString();
  }
};

因为哈希现在是在HashedString构造上计算的，所以它们以这种方式存储在std :: map中，因此比较可以非常快速地进行（整数比较）在一个天文数字的高百分比时间内，回落当哈希值相等时，在标准字符串上进行比较。

Answer 8

也许你可以在将字符串用作地图中的键之前将其反转？如果每个字符串的前几个字母相同，那可能会有所帮助。

Answer 9

以下是您可以考虑的一些事项：

0）您确定这是性能瓶颈所在吗？像Quantify，Cachegrind，gprof或类似的结果？因为在这样的smap地图上查找应该相当快......

1）您可以覆盖用于比较std :: map <！> lt; <！> gt;中的键的仿函数，还有第二个模板参数可以做到这一点。我怀疑你能比操作员<！> lt;做得更好。

2）地图内容是否发生了很大变化？如果没有，并且考虑到地图的非常小的尺寸，可能使用排序向量和二进制搜索可以产生更好的结果（例如，因为您可以更好地利用内存位置。

3）编译时是否知道元素？如果是这种情况，您可以使用完美的哈希函数来改善查找时间。在网上搜索gperf。

4）你有很多找不到的查找吗？如果是这样，也许与集合中的第一个和最后一个元素进行比较可以比每次完整搜索更快地消除许多不匹配。

已经提出过这些建议，但更详细地说：

5）由于你的字符串很少，也许你可以使用不同的密钥。例如，你的钥匙大小是否相同？你能使用一个包含固定长度字符数组的类吗？您可以将字符串转换为数字或仅包含数字的数据结构吗？

Answer 10

根据使用情况，您可以使用其他一些技术。例如，我们有一个应用程序需要跟上超过一百万个不同的文件路径。问题是有数千个对象需要保留这些文件路径的小地图。

由于向数据集添加新文件路径是一种不常见的操作，因此在将路径添加到系统时，会搜索主映射。如果未找到路径，则添加该路径并返回新的序列整数（从1开始）。如果路径已存在，则返回先前分配的整数。然后，每个对象维护的每个映射都从基于字符串的映射转换为整数映射。这不仅大大提高了性能，还因为没有那么多的字符串重复副本而减少了内存使用量。

当然，这是一个非常具体的优化。但是，当谈到性能改进时，您经常会发现自己必须针对特定问题制定定制解决方案。

而且我讨厌字符串:)不是它们比较慢，但它们真的可以将CPU缓存丢弃在高性能软件上。

Answer 11

尝试std :: tr1 :: unordered_map（在标题<！> lt; tr1 / unordered_map <！> gt;中找到）。这是一个哈希映射，虽然它不维护元素的排序顺序，但可能比常规映射快得多。

如果您的编译器不支持TR1，请获取更新版本。 MSVC和gcc都支持TR1，我相信大多数其他编译器的最新版本也有支持。遗憾的是，许多图书馆参考网站尚未更新，因此TR1仍然是一项很大程度上未知的技术。

我希望C ++ 0x的方式不一样。

编辑：请注意，tr1 :: unordered_map的默认哈希方法是tr1 :: hash，它可能需要专门用于处理UDT。

Answer 12

如果你有很长的公共子串，trie可能是比map或hash_map更好的数据结构。我说<！>“可能<！>”，但是 - hash_map每次查询只能遍历一次密钥，所以应该相当快。我不会进一步讨论，因为其他人已经有了。

如果某些键比其他键更频繁地查找，你也可以考虑使用splay树，但当然这会使最坏情况的查找比平衡树更糟糕，并且查找是变异操作，这对你来说可能很重要'使用例如读写器锁。

如果您关心查找的性能而不是修改，那么使用AVL树可能比使用红黑更好，我认为是STL实现通常用于地图的。 AVL树通常更好地平衡，因此平均每次查找需要更少的比较，但差异很小。

找到您满意的实施可能是一个问题。在Boost主页上搜索表明它们有一个splay和AVL树，但不是trie。

您在评论中提到，您从未有过无法找到任何内容的查找。所以你理论上可以跳过最后的比较，它在15 <！> lt的树中。 2 ^ 4个元素可以为你提供20-25％的加速比而不做任何其他事情。实际上，也许不止于此，因为相等的字符串比较慢。是否值得为此优化编写自己的容器是另一个问题。

您也可以考虑引用的位置 - 我不知道您是否可以通过从小堆中分配密钥和节点来避免偶尔的页面未命中。如果您一次只需要大约15个条目，那么假设文件名限制在256字节以下，您可以确保在查找期间访问的所有内容都适合单个4k页面（当然，除了要查找的密钥之外）。与一些页面加载相比，可能是比较字符串是无关紧要的。但是，如果这是你的瓶颈，那么必须进行大量的查找，所以我猜想一切都与CPU相当接近。值得一试，也许。

另一个想法：如果你在一个存在很多争用的结构上使用悲观锁定（你在评论中说程序是大规模的多线程）那么无论分析器告诉你什么（CPU循环是什么代码）花在），通过有效地限制你到1核心，可能比你想象的更多。试试读写器锁？

Answer 13

hash_map不是标准的，请尝试在tr1中使用unordered_map（如果您的工具链尚未提供，则可在boost中使用）。

对于少量字符串，您可能更好地使用vector，因为map通常实现为树。

Answer 14

为什么不使用哈希表呢？ boost :: unordered_map可以做到。或者您可以推出自己的解决方案，并存储字符串的crc而不是字符串本身。或者更好的是，将#defines用于字符串，并将其用于查找，例如，

#define "STRING_1" STRING_1