将std::map与std::string键和int键一起使用的成本是多少?

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

通常,您应该选择在您的情况下最有意义的替代方案,并且仅根据实际性能测试进行优化。众所周知,很难判断什么是瓶颈。

分析算法的渐近性能就是研究必须执行的操作以及它们给方程增加的成本。为此,您需要首先了解所执行的操作,然后评估其成本。

在平衡二叉树(映射恰好是)中搜索密钥需要 O( log N ) 复杂的操作。这些操作中的每一个都意味着比较键是否匹配,如果键不匹配,则跟随相应的指针(子项)。这意味着总成本与成本成正比 log N 乘以这两次行动的成本。以下指针是一个常数时间操作 O(1) ,比较键取决于键。对于整数键,比较速度很快 . 比较两个字符串是另一回事,它需要的时间与所涉及字符串的大小成比例 O(L) L 作为 弦长 参数,而不是更常见的 N

当你把所有的成本加起来,用整数作为键,总成本是 O( log N )*( O(1) + O(1) ) 这相当于 . ( O(1) 隐藏在 O 符号悄悄隐藏。

如果使用字符串作为键,则总成本为 O( log N )*( O(L) + O(1) ) 恒定时间操作被成本更高的线性操作隐藏 并且可以转换成 O( L * log N ) . 也就是说,在由字符串键控的映射中定位元素的成本与映射中存储的元素数乘以用作键的字符串的平均长度的对数成正比。

请注意,big-O表示法最适合用作分析工具,以确定当问题规模增大时算法将如何运行,但它隐藏了许多对原始性能很重要的事实。

操作,如整数。

许多其他隐藏成本也是如此,因为创建元素的成本通常被视为一个恒定时间操作,这只是因为它不取决于问题的参数(在每个分配中定位内存块的成本不取决于您的数据集,但是,在算法分析范围之外的内存碎片上,在malloc内获取锁以确保两个进程不会尝试返回同一内存块的成本取决于锁的争用,而锁争用本身取决于处理器、进程的数量以及它们执行的内存请求量。。。,再次超出了算法分析的范围)。当阅读大O符号的成本时,你必须意识到它的真正含义。

在比较两个字符串时,必须取消对指针的引用以获得第一个字符,并对它们进行比较。如果它们相同,则必须比较第二个字符,依此类推。如果您的字符串有一个很长的公共前缀,这可能会使处理速度减慢一点。不过,它不太可能像比较整数那样快。

除了这些明显的差异,没有重大的性能成本。

首先,我怀疑在实际应用程序中,是否有字符串键或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 .

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