使用std :: map与std :: string键vs int键的代价？

Question

我知道个人地图查询最多需要log（N）时间。但是我想知道，我看到很多使用字符串作为映射键的例子。将std :: string作为关键字关联到map而不是int的性能成本是多少？

std::map<std::string, aClass*> someMap; VS std::map<int, aClass*> someMap;

谢谢！

Answer 1

除了比较已经提到的字符串的时间复杂性之外，字符串键还会在每次将项添加到容器时导致额外的内存分配。在某些情况下，例如高度并行的系统，全局分配器互斥可能成为性能问题的来源。

一般而言，您应该选择最适合您情况的替代方案，并且仅根据实际性能测试进行优化。很难判断哪些是瓶颈。

Answer 2

成本差异将与比较两个字符串与比较两个字符串之间的成本差异相关联。

比较两个字符串时，您必须取消引用指向第一个字符的指针，并对它们进行比较。如果它们相同，则必须比较第二个字符，依此类推。如果你的字符串有一个很长的公共前缀，这可能会使进程变慢一点。尽管如此，它不可能像比较整数一样快。

Answer 3

成本是理所当然可以在实时O（1）时间比较ints，而字符串在O（n）time（n是最大共享前缀）进行比较。而且，字符串的存储消耗比整数更多的空间。 除了这些明显的差异之外，没有主要的性能成本。

Answer 4

渐近性能的分析算法正在研究必须执行的操作以及它们添加到方程中的成本。为此，您需要首先了解执行的操作，然后评估其成本。

在平衡二叉树中搜索关键字（哪些地图碰巧是）需要O(log N)复杂的操作。这些操作中的每一个意味着比较匹配的关键字并且如果关键字不匹配则跟随适当的指针（子）。这意味着总成本与这两个操作的成本成正比。以下指针是恒定时间操作O(1)，并且比较密钥取决于密钥。对于整数密钥，比较很快O(1)。比较两个字符串是另一个故事，它需要的时间与参与O(L)串的大小（这里我特意用L作为长度字符串参数，而不是更常见的N的。

当你总结所有费用高达你得到使用整数作为键的总成本是O(log N)*(O(1) + O(1))等效于O(log N)（O(1)被隐藏在不断的O符号默默隐藏。

如果使用字符串作为键，总成本为O(log N)*(O(L) + O(1))恒定时间操作得到隐藏n通过更昂贵的线性操作O(L)并且可以转换成O(L * log N)。也就是说，在由字符串键入的映射中查找元素的成本与存储在映射中的元素数的对数乘以用作键的字符串的平均长度成比例。

请注意，大O符号最适合用作分析工具，以确定算法在问题规模增长时的行为方式，但它掩盖了许多对原始性能非常重要的事实。

作为最简单的示例，如果将密钥从通用字符串更改为1000个字符的数组，则可以将该成本隐藏在从符号中删除的常量内。比较1000个字符的数组是一个持续的操作，只需要很长时间。使用渐近符号，就像O(log N)操作一样，使用整数。

许多其他隐藏成本也是如此，因为创建元素的成本通常被认为是恒定时间操作，仅仅因为它不依赖于问题的参数（查找块的成本的内存不依赖于你的数据集，而是依赖于算法分析范围之外的内存碎片，获得malloc内部锁的代价，以保证两个进程不会尝试返回相同的块的内存取决于锁的争用，这取决于它本身的处理器数量，进程和它们执行多少内存请求......，这同样超出了算法分析的范围）。当用大O符号阅读成本时，你必须意识到它的真正含义。

Answer 5

首先，我怀疑在一个真实的应用程序中，不管你是否有字符串键或int键都有明显的区别。分析你的应用程序会告诉你它是否重要。

如果这非常重要，你可以改变你的关键是这样的（未经测试）：

class Key { 
public: 
    unsigned hash; 
    std::string s; 

    int cmp(const Key& other) { 
     int diff = hash - other.hash; 
     if (diff == 0) 
      diff = strcmp(s, other.s); 
     return diff; 
} 

现在你正在做的两个字符串的哈希一个int比较。如果哈希值不同，字符串肯定是不同的。如果哈希值相同，则由于Pigeonhole Principle，您仍然需要比较字符串。

Answer 6

简单的例子，只需访问两个具有相同键数的映射中的值 - 一个int键另一个具有相同int值的字符串需要8倍的字符串长度。