Используйте не вложенный цикл, а сравнение по хэшу

Иногда требуется сравнить два больших списка и вытащить одинаковые элементы. На ум первым приходит решение вложенным циклом:

vector<string> nestedLoopJoin(vector<string>& setA, vector<string>& setB) {
    vector<string> res;
    for (int i = 0; i < setA.size(); i++)
    {
        for (int j = 0; j < setB.size(); j++)
        {
            if (setA[i] == setB[j]) {
                res.push_back(setB[j]);
                break;
            }
                
        }
    }

    return res;
}

НО! Как известно, nested loop один из самых медленных алгоритмов, поэтому используем сравнение по хэшу:

vector<string> hashJoin(vector<string>& setA, vector<string>& setB) {
    vector<string> res;
    unordered_map<string, string> mp;
    for (int i = 0; i < setB.size(); i++)
    {
        mp[setB[i]] = setB[i]; //сперва хэшируем меньший список
    }

    for (int i = 0; i < setA.size(); i++) //пробегаем по большему списку
    {
        if (mp.find(setA[i]) != mp.end()) //проверяем на существование элемента в hash map'е
            res.push_back(setA[i]);
    }

    return res;
}

Тут все просто: хэшируем один из списков (в моем случае меньший) и далее просто пробегаемся по большому списку, проверяя на существование элемента в hash map'е.

Результаты двух подходов при сравнении двух списков размером 1000 и миллион строк:

Даже при увеличении меньшего списка до 10 тысяч элементов (10k x 1M => 10 млрд операций) nested loop занимает 6 минут, тогда как сравнение по хэшу опять 0 сек!

Почему так?

Вложенный цикл в худшем случае выполняет 1M x 10k = 1 миллиард операций сравнения, а сравнение по хэшу всего 1M, т.к. сложность поиска в hash map'е есть O(1):

Возможные минусы подхода

Сравнение по хэшу, как правило, занимает больше памяти, т.к. создается копия списка, но на практике 1M x 10K строк оба варианта заняли по 32 килобайта.

Где используется сравнение по хэшу в промышленном коде?

Ввиду своей работы (поддержка баз данных) я знаю, что сравнение по хэшу используется в различных СУБД (MS SQL Server, Oracle и тп). Пример плана T-SQL:

Как сами Microsoft пишут Hash Join используется, если хотя бы один из списков большой.

Заключение

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

Жду ваших комментариев. Спасибо за внимание. С вами был Бегалиев Чингис.