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

我正在使用std::map(VC++实现),并且通过map的find方法查找速度有点慢.

关键类型是std::string.

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

还有其他想法加快比较吗？

在我的情况下,地图将始终包含<15个元素,但是它会被不断地查询并且性能至关重要.也许有一个更好的数据结构,我可以使用更快？

更新:地图包含文件路径.

Update2:地图的元素经常变化.

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

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

例如,在这段代码中,find()可能会导致一些字符串比较,但每次比较第一个字符到"david"之后都会返回,然后检查前三个字符.因此,每次调用最多可检查5个字符.

map names;
names["larry"] = 1;
names["david"] = 2;
names["juanita"] = 3;

map::iterator iter = names.find("daniel");

另一方面,在以下代码中,find()可能会检查135个以上的字符:

map 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::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.

正如甚至说在使用的运营商set是<不是==.

如果你不关心你的字符串顺序,set你可以通过set一个自定义比较器,它比常规的less-than更好.

例如,如果你的很多字符串有相似的前缀(但它们的长度不同),你可以按字符串长度排序(因为它string.length是恒定的速度).

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

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

按照逻辑,你会看到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 lhs.length() < rhs.length();
        return lhs < rhs;
    }
};

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

它还取决于您在地图中使用的键类型.它们通常很长吗？"有点慢"是什么意思？如果你还没有对代码进行分析,很可能它是一个不同的部分需要时间.

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