Почему одна итерация для вставки карты и map.find () намного медленнее, чем две отдельные итерации для вставки и для map.find ()

Question

Я нахожу интересное явление, когда пытаюсь оптимизировать свое решение для задачи с двумя суммами в leetcode (https://leetcode.com/problems/two-sum/description/). Описание кода Leetcode для задачи с двумя суммами:

Для данного массивацелых чисел, вернуть индексы двух чисел так, чтобы они складывались в определенную цель. Вы можете предположить, что у каждого входа будет только одно решение, и вы не можете использовать один и тот же элемент дважды.

Сначала я решаю эту проблему с помощью двух циклов: сначала я перебираю входной массив для сохранения значения массива и индекса массива в виде пары в карте, а затем снова перебираю входной массив, чтобы зациклить каждый элемент и проверить, существует ли он на карте.Ниже приведено мое решение из 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;
    }
};

Это решение занимает 4 мс при отправке leetcode. Так как я перебираю один и тот же массив дважды, я подумал оптимизировать свой код, комбинируя операцию вставки и отображение.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,9 с) медленнее, чем версия с двумя циклами (3,0 с): результаты

Я не очень понимаю, почему версия с одним циклом работает медленнее, чем версия с двумя циклами?Я думаю, что версия с одним циклом должна уменьшить избыточность цикла.Это из-за реализации STL map , что лучше делать операции вставки и map.find () отдельно в двух циклах, а не вставлять и map.find () попеременно в одном цикле?

Кстати, я работаю в Mac OS и использую Apple LLVM версии 10.0.0 (clang-1000.10.44.2).

Answer 1

Давайте посмотрим, что на самом деле происходит в обоих сценариях.

В сценарии с двумя циклами вы делаете N вставок на карту, но затем делаете только одну находку, потому что, когда карта полностью заполнена, вы получаетеожидаемый результат на первой итерации.

В сценарии с одним циклом необходимо дождаться последней вставки, чтобы найти результат.Таким образом, вы делаете N-1 вставки и N-1 находите.

Неудивительно, что в вашем худшем случае это занимает вдвое больше времени ...

Для случайных вариантов использования дваСценарий цикла даст ровно N вставок и статистически N / 2 найдет.В лучшем случае N вставляет 1 поиск, в худшем случае N вставляет N-1 поиск.

В одиночном цикле вы начинаете поиск, как только карта не пуста.Наилучший случай - 1 вставка и 1 поиск (намного лучше, чем два цикла), а наихудший случай - N-1 вставки и N-1 находки.Я знаю, что легко ошибиться в вероятностях, но я ожидаю статистически 3N / 4 вставок и N / 2 находок.Так что немного лучше, чем сценарий с двумя циклами.

TL / DR: вы получите лучшие результаты для сценария с двумя циклами, чем для одного цикла, потому что ваш тестовый пример является лучшим для двух циклов и худшим для одного цикла.