c++ - 为什么 map 插入和 map.find() 的单次迭代比插入和 map.find() 的两次单独迭代慢得多

Question

当我尝试优化我的 leetcode 二和问题 (https://leetcode.com/problems/two-sum/description/) 的解决方案时，我发现了一个有趣的现象。 二和问题的 Leetcode 描述是:

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

最初，我通过使用两个循环来解决这个问题。首先，我遍历输入数组以将数组值和数组索引成对存储到映射中。然后我再次遍历输入数组以循环每个元素并检查它是否存在于 map 中。以下是我在 leetcode 上的解决方案:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        vector<int> res;
        map<int, int> store;

        for(int i = 0; i < nums.size(); ++i)
        {
            store[nums[i]] = i;
        }

        for(int i = 0; i < nums.size(); ++i)
        {
            auto iter = store.find(target - nums[i]);
            if(iter != store.end() && (iter -> second) != i)
            {
                res.push_back(i);
                res.push_back(iter -> second);
                break;
            }
        }
        return res;
    }
};

这个解决方案在 leetcode 提交中需要 4ms。因为我在同一个数组中循环两次，所以我想通过将插入操作和 map.find() 组合到一个循环中来优化我的代码。因此我可以在插入元素时检查解决方案。然后我有以下解决方案:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        vector<int> res;
        map<int, int> store;

        for(int i = 0; i < nums.size(); ++i)
        {
            auto iter = store.find(target - nums[i]);
            if(iter != store.end() && (iter -> second) != i)
            {
                res.push_back(i);
                res.push_back(iter -> second);
                break;
            }
            store[nums[i]] = i;
        }

        return res;
    }
};

但是，单循环版本比两个单独的循环慢得多，后者需要 12 毫秒。

为了进一步研究，我做了一个测试用例，其中输入大小为 100000001，此代码的解决方案为 [0, 100000001](第一个索引和最后一个索引)。以下是我的测试代码:

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <iterator>
#include <cstdio>
#include <ctime>

using namespace std;

vector<int> twoSum(vector<int>& nums, int target) 
{
    vector<int> res;
    map<int, int> store;

    for(int i = 0; i < nums.size(); ++i)
    {
        auto iter = store.find(target - nums[i]);
        if(iter != store.end() && (iter -> second) != i)
        {
            res.push_back(i);
            res.push_back(iter -> second);
            break;
        }
        store[nums[i]] = i;
    }

    return res;
}


vector<int> twoSum2(vector<int>& nums, int target) 
{
    vector<int> res;
    map<int, int> store;

    for(int i = 0; i < nums.size(); ++i)
    {
        store[nums[i]] = i;
    }

    for(int i = 0; i < nums.size(); ++i)
    {
        auto iter = store.find(target - nums[i]);
        if(iter != store.end() && (iter -> second) != i)
        {
            res.push_back(i);
            res.push_back(iter -> second);
            break;
        }
    }
    return res;
}

int main()
{

    std::vector<int> test1;
    test1.push_back(4);
    for (int i = 0; i < 100000000; ++i)
    {
        test1.push_back(3);
    }
    test1.push_back(6);

    std::clock_t start;
    double duration;

    start = std::clock();
    auto res1 = twoSum(test1, 10);
    duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
    std::cout<<"single loop: "<< duration <<'\n';   
    cout << "result: " << res1[1] << ", " << res1[0] << endl;

    start = std::clock();
    res1 = twoSum2(test1, 10);
    duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
    std::cout<<"double loops: "<< duration <<'\n';   
    cout << "result: " << res1[0] << ", " << res1[1] << endl;

}

我仍然得到类似的结果，单循环版本(7.9s)比双循环版本(3.0s)慢: results

我真的不明白为什么单循环组合版本比双循环分离版本慢？我认为单循环版本应该减少一些冗余循环。是不是因为STL map的实现方式，插入和map.find()操作在两个循环中分开做，而不是插入和map.find()在一个循环中交替进行？

顺便说一句，我正在使用 MAC 操作系统并使用 Apple LLVM 版本 10.0.0 (clang-1000.10.44.2)。

Answer 1

让我们看看在这两种情况下实际发生了什么。

在两个循环的场景中，您在 map 中进行了 N 次插入，但随后只进行了一次查找，因为本地图完全填满时，您会在第一次迭代中获得预期的结果。

在单循环场景下，必须等待最后一次插入才能找到结果。所以你做了 N-1 次插入和 N-1 次查找。

毫不奇怪，在最坏的情况下测试需要两倍的时间......

对于随机用例，两个循环场景将恰好导致 N 次插入，统计上 N/2 次查找。最佳情况 N 插入 1 个发现，最坏情况 N 插入 N-1 发现。

在单循环中，只要 map 不为空，您就会开始查找。最好的情况是 1 次插入和 1 次查找(远好于两次循环)，最坏的情况是 N-1 次插入和 N-1 次查找。我知道在概率上很容易被误导，但我希望统计上有 3N/4 个插入和 N/2 个发现。所以比两个循环场景稍微好一点。

TL/DR:与单循环场景相比，双循环场景的结果更好，因为您的测试用例对于双循环是最好的，而对于单循环是最差的。