为什么 vector 比 unordered_map 快？

Question

我正在 LeetCode 上解决一个问题，但是还没有人能够解释我的问题。

问题是这样的：

给定一个任意的赎金票据字符串和另一个包含来自所有杂志的字母的字符串，编写一个函数，如果赎金票据可以从杂志中构造出来，该函数将 return 为真；否则，它将 return false.

杂志字符串中的每个字母只能在您的赎金记录中使用一次。

注意：您可以假设这两个字符串都只包含小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

我的代码（耗时 32 毫秒）：

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        if(ransomNote.size() > magazine.size()) return false;
        unordered_map<char, int> m;
        
        for(int i = 0; i < magazine.size(); i++)
            m[magazine[i]]++;
            
        for(int i = 0; i < ransomNote.size(); i++)
        {
            if(m[ransomNote[i]] <= 0) return false;
            m[ransomNote[i]]--;
        }
        return true;
    }
};

代码（我不知道为什么更快 - 需要 19 毫秒）：

bool canConstruct(string ransomNote, string magazine) {
        int lettersLeft = ransomNote.size(); // Remaining # of letters to be found in magazine
        int arr[26] = {0};
        for (int j = 0; j < ransomNote.size(); j++) {
            arr[ransomNote[j] - 'a']++; // letter - 'a' gives a value of 0 - 25 for each lower case letter a-z
        }
        
        int i = 0;
        while (i < magazine.size() && lettersLeft > 0) {
            if (arr[magazine[i] - 'a'] > 0) {
                arr[magazine[i] - 'a']--;
                lettersLeft--;
            }
            i++;
        }
        if (lettersLeft == 0) {
            return true;
        } else {
            return false;
        }
    }

两者的复杂度相同，使用相同的结构来解决问题，但我不明白为什么一个花费的时间几乎是另一个的两倍。查询向量的时间是 O(1)，但对于 unordered_map 是相同的。同样的故事，向其中任何一个添加 entry/key。

有人能解释一下为什么运行时间变化如此之大吗？

Answer 1

首先要注意的是，虽然查询一个 unordered_map 的平均时间是恒定的，但最坏的情况不是 O(1)。可以看到here实际上上升到O(N)的数量级，N表示容器的大小。

其次，由于 vector 分配内存的顺序部分，访问该内存非常高效，实际上是常量，即使在最坏的情况下也是如此。（即简单的指针算法，而不是计算更复杂的散列函数的结果）还有可能涉及不同级别的顺序内存缓存（即取决于平台，您的代码是运行 on) 这可能会使使用 vector 的代码执行速度比使用 unordered_map.

的代码执行得更快

本质上，就复杂度而言，a vector 的最坏情况性能比 unordered_map 更有效。最重要的是，大多数硬件系统都提供诸如缓存之类的功能，这使 vector 的使用具有更大的优势。（即 O(1) 操作中较小的常数因子）

Answer 2

您的第二种方法使用普通 C 数组，其中访问元素是一个简单的指针取消引用。但 unordered_map 并非如此。有两点需要注意：

首先，访问元素不是简单的指针解引用。它必须做其他工作来维护它的内部结构。 unordered_map 实际上是引擎盖下的散列 table，C++ 标准间接要求，这是一个比简单数组访问复杂得多的算法。
其次，O(1) 访问是平均的，但不是最坏的情况。

由于这些原因，难怪数组版本会比 unordered_map 工作得更好，即使它们具有相同的运行时间复杂度。这是另一个示例，其中具有相同运行时间复杂度的两个代码执行不同。

只有当你有大量的keys时，你才会看到unordered_map的好处（这里反对固定26个）。

为什么 vector 比 unordered_map 快？

Why is vector faster than unordered_map?

c++

algorithm

dictionary

unordered-map

vector

问题是这样的：

我的代码（耗时 32 毫秒）：

代码（我不知道为什么更快 - 需要 19 毫秒）：