使用 std::map 和 std::string 键与 int 键的成本？

Question

我知道单个地图查询最多需要 log(N) 时间。不过我想知道，我见过很多使用字符串作为映射键的示例。例如，将 std::string 而不是 int 关联为映射的键的性能成本是多少？

std::map; someMap; 与 std::map; someMap;

谢谢！

Answer 1

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

在平衡二叉树（恰好是映射）中搜索键需要 O( log N ) 复杂的操作。这些操作中的每一个都意味着比较密钥是否匹配，如果密钥不匹配，则遵循适当的指针（子级）。这意味着总成本与这两个操作的成本的 log N 倍成正比。跟随指针是一个常数时间操作O(1)，并且比较键取决于键。对于整数键，比较速度很快 O(1)。比较两个字符串是另一回事，它所花费的时间与所涉及的字符串的大小成正比O(L)（其中我故意使用L作为长度string 参数，而不是更常见的 N

当您将所有成本相加时，您会发现使用整数作为键，总成本为 O( log N )*( O( 1) + O(1) ) 相当于 O( log N ) (O(1) 隐藏在 的常量中。 >O 表示法默默隐藏，

如果您使用字符串作为键，则总成本为 O( log N )*( O(L) + O(1) )，其中常数时间操作。被成本更高的线性运算 O(L) 隐藏，并且可以转换为 O( L * log N ) 即在 a 中定位元素的成本。由字符串作为键的映射与存储在映射中的元素数量乘以用作键的字符串的平均长度的对数成正比。

请注意，大 O 表示法最适合用作确定算法如何进行的分析工具。当问题规模扩大时，它会表现出来，但它隐藏了许多对原始性能很重要的事实。

作为最简单的示例，如果将键从通用字符串更改为 1000 个字符的数组，则可以将该成本隐藏在从表示法中删除的常量中。比较 1000 个字符的数组是一个常量操作，只是需要相当多的时间。使用渐近符号，这只是一个 O( log N ) 运算，就像整数一样。

许多其他隐藏成本也会发生同样的情况，因为创建元素的成本通常被视为恒定时间操作，只是因为它不依赖于问题的参数（在每个元素中定位内存块的成本）分配不取决于您的数据集，而是取决于内存碎片，这超出了算法分析的范围，在 malloc 内获取锁以保证不是两个进程尝试返回同一内存块的成本取决于锁的争用取决于处理器、进程的数量以及它们执行的内存请求量......，同样超出了算法分析的范围）。当阅读大 O 表示法中的成本时，您必须意识到它的真正含义。

Answer 2

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

一般来说，您应该选择最适合您的情况的替代方案，并且仅根据实际性能测试进行优化。众所周知，很难判断什么会成为瓶颈。

Answer 3

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

比较两个字符串时，必须取消引用指针以获取第一个字符，然后比较它们。如果它们相同，则必须比较第二个字符，依此类推。如果您的字符串具有很长的公共前缀，这可能会稍微减慢该过程。不过，它不太可能像比较整数那么快。

Answer 4

当然，代价是整数可以在真正的 O(1) 时间内进行比较，而字符串可以在 O(n) 时间内进行比较（n 是最大共享前缀）。此外，字符串的存储比整数的存储消耗更多的空间。
除了这些明显的差异之外，没有重大的性能成本。

Answer 5

首先，我怀疑在实际应用程序中，是否有字符串键或整数键会产生任何明显的差异。分析您的应用程序会告诉您它是否重要。

如果确实重要，您可以将密钥更改为如下所示（未经测试）：

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 比较。如果哈希值不同，则字符串肯定会不同。如果哈希值相同，由于鸽洞原理，您仍然需要比较字符串。

Answer 6

简单的例子，仅访问具有相同数量键的两个映射中的值 - 一个 int 键另一个具有相同 int 值的字符串使用字符串需要花费 8 倍的时间。