Итерация по unordered_set быстрее чем по vector?

В nums много дублей?

Нет дублей.

Тормозит не итерация, а проверка каждого элемента в unordered_set. Только я не понял, зачем проверять, есть ли элемент в set, если там есть все элементы?

Немного не точно объяснил, но суть с проверкой не меняется от этого.

Тормозит не итерация, а проверка каждого элемента в unordered_set.

Проверка осталась внутри for, она никуда делась. Проверяются абсолютно все элементы по алгоритму.

Для ускорения алгоритма меняем только одно слово. Вместо nums в for пишем set. Всё.

nums из кеша вытеснило

вы код покажите, где оно «быстрей». set сделан для того, чтобы быстро определять наличие элемента в данном множестве, а не для быстрой «итерации» по всем элементам этого множества.

в силу специфики реализации скорость итерации там не может(с чего бы?) быть выше скорости итерации на непрерывном массиве.

скорее всего ваш код делает не то, что вам кажется.

А элементов сколько?

И я б гонял у себя локально а не ХЗ на чем удаленно непойми как собранное.

итератор по vector, и проверка есть ли каждый элемент в unordered_set и далее логика если есть

По этому коду - всегда есть, можно не проверять. Ваш К.О.;-)

Какая задача?

Задача https://leetcode.com/problems/longest-consecutive-sequence

Локальный код:

#include <vector>
#include <unordered_set>

using namespace std;

int longestConsecutive(const vector<int>& nums) {
    unordered_set<int> set;

    for (auto n : nums) {
        set.insert(n);
    }

    int longest = 0;

    // Итерация по nums медленнее чем по 'set' !!!
    for (auto n : nums) {
        // Start of a chain
        if (set.find(n - 1) == set.end()) {
            int length = 0;
            while (set.find(n + length) != set.end()) {
                length++;
            }
            longest = max(longest, length);
        }
    }

    return longest;
}

Тест:

nums содержит 50’000 элементов https://pastebin.com/diqtqMP4

Время отработки с nums в for - порядка 5000 мс на моём ПК.

Время отработки с set в for - порядка 10 мс на моём ПК.

Код main на Qt:

int main(int argc, char *argv[])
{
    const vector<int> nums = ...

    qint64 v = QDateTime::currentMSecsSinceEpoch();

    int longest = longestConsecutive(nums);

    qDebug() << nums.size() << longest << QDateTime::currentMSecsSinceEpoch() - v;

    return 0;
}

Локально или нет - без разницы, см. код, добавил. Разница - НА ПОРЯДОК.

https://leetcode.com/problems/longest-consecutive-sequence

nums из кеша вытеснило

скорее всего

50к * 4 = 200кб, в L2 должен помещаться

50000*4 = 200000 ~= 200к.

Какой процессор? Какой размер L1 cache? Если 256к, то здесь:

    for (auto n : nums) {
        set.insert(n);
    }

при записи set вытесняется nums из L1.

Если nums помещается в L1, а set вытесняется в L2, то вот и потеря производительности. Если мы итерируем по set вместо nums, то весь set помещается в L1, и более мы никуда не лезем. Отсюда и прирост производительности в 50 раз

Кэш L1/L2/L3 = 384Kb/8Mb/8Mb

вы ищете максимальную монотонно возрастающую подстроку чисел в исходном массиве

а вот это выражение вовсе не про подстроку, а просто про наличие следующего числа в произвольном месте исходного массива.

while (set.find(n + length) != set.end()) {
                length++;
            }

например если текущее число 10 - вы ищете 11 во всей последовательности. а не на следующем месте. то есть вы решаете какую-то не ту задачу.

вы ищете 11 во всей последовательности

по условиям задачи так и должно быть.

Для исходного массива [8, 5, 10, 6, 20, 7] монотонная последовательность будет [5,6,7,8]

а, ну да. это я условие криво прочитал. тогда код примерно правильный. и что? это быстрей, чем какой код? откуда там еще некая «итерация по массиву»?

в данном случае вам интересен факт наличия следующего числа в множестве. для того set и предназначен, чтобы быстро это вычислить(не перебирая все элементы).

откуда у вас берется какая-то «итерация по массиву»? если вы пытаетесь найти перебором - находится ли след. число в массиве, то это очевидно неправильно, с точки зрения производительности. а через множество - правильно. и кеши там не причем.

Возьми код и посмотри на строку «Итерация по nums медленнее чем по ‘set’»

You must write an algorithm that runs in O(n) time.

for (auto n : nums) {
    set.insert(n);
}

Незачет.

Тебе незачёт за незнание big-O 😂

Лол кек лор ужо не торт, эт же медиум лор упал в чьих глозах

Время отработки с nums в for - порядка 5000 мс на моём ПК.

Время отработки с set в for - порядка 10 мс на моём ПК.

никакие кеши такие цифры не дадут. разница в 500 раз что-ли???

это или систематическая некая ошибка, ну или на крайняк - какая-то мегаоптимизация(там какие ключи компиляции-то?), когда компилятор, видя что работают только в set, сумел свернуть код так, что получилась такое вот ускорение. хотя уж слишком хорошо получилось.

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

Дело не в stl, а в cache-friendly коде, который да, может дать 500 раз прироста. Магия! Возьми код и скомпилируй у себя, экспериментируй 🙂

Магия!

с какой стати set стал cache friendly. он не более friedly чем vector, а то и менее, поскольку сложней устроен.

Вставка в хэштаблицу имеет амортизированную O(1), в худшем случае - квадрат, если очень постараться то квадрат логарифмов.

Сперва докажи, что у тебя хорошие хэши подходящие под задачу.

там N вставок - то есть O(n).

потом сканирование массива c поиском в set- опять порядка O(n).
итого - общее O(n).

Код который использует контейнеры должен быть cache-friendly. Когда ты итерируешь по nums, а внутри цикла обращаешься к set, то nums и set постоянно выталкивают друг друга на кеш другого уровня. Теоретически, просто исходя из их размеров. Если ты итерируешь по set, то весь этот set спокойно лежит в L1 весь цикл, и цикл работает со скоростью света.

Ты угараешь, какой квадрат? https://en.cppreference.com/w/cpp/utility/hash

Notably, some implementations use trivial (identity) hash functions which map an integer to itself.

https://en.m.wikipedia.org/wiki/Hash_table

Operation	Average	Worst case
Insert	        Θ(1)	O((log n)2)

В общем, примерно ясен уровень задач и их решателей.

Когда ты итерируешь по nums, а внутри цикла обращаешься к set, то nums и set постоянно выталкивают друг друга на кеш другого уровня.

когда у тебя итерация и по nums и set, у тебя просто в два раза больше размер данных, чем только по nums.

можно сказать, что в первом случае эффективный размер кеша в два раза меньше, чем во втором.

но это не даст 500 раз по производительности. и не будут они выталкивать «друг друга», а разлягутся в своих половинках неким статистическим образов.

Я конечно давно в крестах не ковырялся, но может у тебя при векторе auto n копирует значение из массива в локальную переменную на стеке, а потом использует (не константа). А в случае с сетом загружает сразу в регистр (как константу).

но может у тебя при векторе auto n копирует значение из массива в локальную переменную на стеке

не. это если вообще нет оптимизации. с оптимизацией он будет держать переменные в регистрах. и даже если б от что-то клал на стек - 500 раз это бы не дало. ну максимум какие-нить 20 процентов может и дало бы.

Латентность доступа между L1 и L2 отличается в 2.5-3 раза, а не в 50. А между L1 и L3 в 10 раз, а не в 50. В конце концов возьмите профайлер да посмотрите, больше разговоров

Так я не против 🙂 Объясни исходя из этого разницу в 500 раз?

Объясни исходя из этого разницу в 500 раз?

паленая водка с элементами галлюцинаций.

Можно тупо валить на одинаковых алгоритмах с хэш-таблицами, просто подобрав плохие исходные данные (случайно или намеренно).

Так это тебе нужно, а не мне

Нет дублей.

nums содержит 50’000 элементов https://pastebin.com/diqtqMP4

В конце массива куча нолей. На глаз 1/4 массива.

Согласен, только это мало что объясняет 😂

Локальный код

Жесть. И квадрата в своём алгоритме вы конечно не видите?

Неа. Может его там и нет?

Это же O(n^2) Там в тэгах union find. Объединяй последовательности с помощью union find, а потом выдай максимальную. Тогда O(n) будет

   unordered_set<int> set;

   for (auto n : nums) {
       set.insert(n);
   }

unordered_set<int> set(nums.begin(), nums.end());, раз уж НАТО пошло?

Это же O(n^2)

Докажи построчно. Алгоритм не самый оптимальный мб, но O(n).

Локально или нет - без разницы, см. код, добавил. Разница - НА ПОРЯДОК.

У меня разницы вообще нет (в пределах погрешности). Упс? Я правда вектор забил от 0 до N-1. Если есть дубли, то разумеется set будет короче и это может сыграть.

Но вообще на таких смешных размерах (5e4) че то достоверно померять сложно.

Для ввода 1,2,3,4,5,6,…,n будет n*(n-1)/2 операций, так как каждая итерация будет проходить все элементы начиная с i.

Там поц-счёт делается только при условии if (set.find(n - 1) == set.end()), т.е. в данном случае только для 1