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

Дык, а чего мы собственно вообще ждём от одной из самых медленных реализаций хеш-таблички, да которую ещё и не отресайзили на старте подобающе? Первое что бы я там поменял - взял бы что-нибудь с open-addressing (boost::unordered_flat_set?) и раздвинул бы табличку 2x - 4x от размера входного вектора. Вот у этого уже был бы шанс против сортировки на относительно коротком входе.

Инициализация делается раз. Поиск в union find формально это alpha(n), но для тех ограничений что в задаче можно считать что это не отличимо от O(1)

Кстати в спортивном программировании хэш таблицы это харам, так как умельцы потом на взломах подбирают ввод который приводит к O(n) :)

Инициализация делается раз.

Инициализировать надо уникальными значениями, union-find - это лес непересекающихся множеств, по началу единичных множеств из уникальных элементов. Также придется создать map числа на элемент-ноду union-find, возможно также обратный map. И всё это - не линейная сложность. Или я что-то не знаю, поэтому хочу увидеть реализацую алгоритма.

вообщет прямой слей-найди в качестве входов ожидает рёбра

в этой задачи ребро это наличие среди вершин пар вида (n,n+1)

так что само обьединение по рёбрам хоть и обратный акерман откуда вы будете брать подходящие пары :) ?

самый «быстрый» это «радикс» сорт на четверть гигабайта зажигая биты

затем второй проход по исходному массиву

и зануление для ещё ненулевого бита его окрестностей вниз и вверх с обновлением максимальной длины

т.е один служебный массив флагов от -10**9 до 10**9

и два прохода по начальному 10**5 массиву сначала для посева потом для сбора :)

если уж «совсем ускорятся» и алокация дороже (т.е вносит значимую долю в общее время) то +1 предварительный проход для сбора некоторой статистика(мин,мах,набор каких процентилей что бы кусковать и сшивать без алокации всего возможного четверти гигабайта)

но это постепенное перетекание из линейного + мноха бесплатной памяти в «сортировку на лентах» :)

В исходной формулировке задача не имеет решения

Типа, потому что O(n) требуют? При фиксированном диапазоне чисел, radix sort даст тебе O(n). Ну и что, что тормознее generic O(n*log(n)) сортировки?

Зато тру O(n)

Расшифровываю

lcs_lor_20250410 - алгоритм из linux.org.ru с датой 2025.04.10

BigO - «О большое»

6.71 NlgN - 6.71 * N*log(N), выч.сложность твоего алгоритма

lcs_sort_copy - мой алгоритм основанный на сортировке с копированием исходного, чтобы не портить исходный массив.

init_unordered_set - только инициализация/заполнение std::unordered_sort случайными числами. Хочу заметить, медленнее алгоритма на сортировке. То есть, использование unordered_set в алгоритме делает его медленноее алгоритма на сортировке.

Дополню.

Твой алгоритм можно ускорить, задав количество бакетов в 2-4 раза больше входного массива.

unordered_set<int> set(nums.begin(), nums.end(), 4 * nums.size());

Коэффициент перед N*log(N) падает примерно в 1,5 раза: 6.7 -> 4,5.

Еще чуть-чуть можно ускорить, используя boost::unordered_set (он чуть быстрее libstdc++)

Ты ускоряешь спички. Асимптотическая сложность вставки чисел в set таким образом - линейная. Дальше тоже все линейно благодаря удалению. Сет может расти/сжиматься в размере, но это bigO не учитывает.

Асимптотическая сложность вставки чисел в set таким образом - линейная.

Она кусочно-линейная, и каждый кусок выше по сложности предыдущего. В среднем растет по N*log(N).

константа излишне большая на «малых» 50к входах у этой реализации

принципиально ещё привозит кэширование

ибо линейное решение перестраивает сд :(

а сорт и сортирует достаточно быстро а ответ линейным сканом

по хорошему линейное решение которое может обойти nlogn-сортировку можно специфицировать - типо как Дейкстра учил творить алгосы путём постепенного уточнения

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

имхо на существующем железе можно синтезировать линейный_офлайн алго который будет на указанных ограничениях для входов обходит сортировку

с реализацие на си(али плюсах) тока для этого потребуется структуру данных породить :)

Вот пруфы для boost::unordered_set

https://www.boost.org/doc/libs/develop/libs/unordered/doc/html/unordered/benchmarks.html

Там плюсовая магия под капотом. Вставка в конструкторе даже для priority_queue линейная. А вот так будет nlogn:

priority_queue<int> maxHeap;
for (int n : nums)
    maxHeap.push(n);

Проверял? Игноришь даже официальные пруфы? Я проверял. Могу сказать, что reserve(C*n); insert(first,last); самый быстрый. Но все равно NlogN

Я просто решительно не понимаю, откуда в unordered_set может взяться логарифм? Я бы понял O(n^2), если ты про коллизии, но log?

оно на хэшах и амортизационных перестройках при увеличении/уменьшении пула

отсюда и лог вылазит

Я уже писал об этом выше. BigO не учитывает shrink/enlarge и амортизация там будет O(1) во всех случаях, включая «глупенькую» версию про все числа в одном бакете.

Чтобы представить число нужно log(N) бит. Из них log(Const) бит - это размер хеша (количество доступных бакетов), а остальная часть - это log(N) - log(Const) = log(N) - это коллизии в бакетах.

При идеальном хеше Const >= N, тогда логарифма не видно, и про этот идеальный случай рассказывают учебники.

Осталось написать идельный хеш для случайных чисел. Не можешь -получай логарифм.

Меньше теории, больше практики. Возьми и проверь. Можешь попробовать написать свою хеш-таблицу и проверить.

прокури что есть(такое) амортизация

оно не изчезает худшее - оно показывает что на наборе «получаем» среднее нужной сложности за счёт выплаты «амортизирующиего налога» на каждом запросе к сд что размазывает цену плохих случаев - т/е фактически таже сумма размазывается по времени что бы и в худшем случае операция попала в квант

обрати внимание на синхроность развития сд бд и сначала Кнутово O и очень быстро появление амортизационого для алгоритмов готовности

Я не понимаю, что ты несешь. Какое отношение биты имеют к сложности вставки в unordered_set? Ты клон кулинхао?

А если с обычным set? Найвный vs. с байтодрочерский

Runtime 121 ms/beats 17.43%; Memory 91.31 MB/beats 9.13%:

class Solution {
public:
	int longestConsecutive(const vector<int>& nums) {
		if (nums.empty()) return 0;

		set<int> set(nums.begin(), nums.end());

		int ret = 1;
		int cnt = 1;

		auto b = set.begin();
		auto e = set.end();
		for (auto prev = *(b++); b != e; prev = *(b++)) {
			if (*b - prev == 1) {
				cnt++;
				continue;
			}
			ret = max(ret, cnt);
			cnt = 1;
		}

		return max(ret, cnt);
	}
};

Runtime 53 ms/beats 77.13%; Memory 79.08 MB/beats 76.50%:

#include <memory_resource>

class Solution {
public:
	int longestConsecutive(const vector<int>& nums) {
		if (nums.empty()) return 0;

		// можно попробовать множитель от 2 до 4
		// ну и `node_type` задействовать, но мне было влом
		vector<byte> buf(2 * sizeof(void*) * nums.size());
		pmr::monotonic_buffer_resource mbr{buf.data(), buf.size()};;
		pmr::polymorphic_allocator<int> pa{&mbr};
		pmr::set<int> set(nums.begin(), nums.end(), pa);

		int ret = 1;
		int cnt = 1;

		auto b = set.begin();
		auto e = set.end();
		for (int prev = *(b++); b != e; prev = *(b++)) {
			if (*b - prev == 1) {
				cnt++;
				continue;
			}
			ret = max(ret, cnt);
			cnt = 1;
		}

		return max(ret, cnt);
	}
};

Что за? Есть разумное объяснение?

Есть. STL на линухе реализован на отшибись.

На днях сравнивал скорость обработки массива строк (нормализация+замена сепаратора по rvalue)

Так вот обработка пары сотен тысяч строк QString проходит быстрей чем stl::string вдвое!

Даже если список изначально хранить в stl-виде, в обработке держать текущий QString во временной переменной, и при возврате преобразовывать опять в stl-формат, то это все равно быстрей!

Короче, вот 100% O(n) 🫠, если кому-то так нужно:

struct Solution {
	template<size_t bit>
	void sort(vector<int>& arr, size_t b, size_t e)
	{
		if (e - b <= 1) return;

		auto i = b;
		auto j = e;
		while (i < j) {
			if (((unsigned)arr[i] >> bit & 1) == (bit == 31)) {
				i++;
				continue;
			}

			if (((unsigned)arr[j - 1] >> bit & 1) == (bit != 31)) {
				j--;
				continue;
			}

			std::swap(arr[i++], arr[--j]);
		}

		if constexpr (bit != 0) {
			sort<bit - 1>(arr, b, i);
			sort<bit - 1>(arr, j, e);
		}
	}


	int longestConsecutive(vector<int>& nums) {
		if (nums.empty()) return 0;

		sort<31>(nums, 0, nums.size());

		int ret = 1;
		int cnt = 1;

		auto b = nums.begin();
		auto e = nums.end();
		for (int prev = *(b++); b != e; prev = *(b++)) {
			if (*b - prev <= 1) {
				cnt += *b - prev;
				continue;
			}
			ret = max(ret, cnt);
			cnt = 1;
		}

		return max(ret, cnt);
	}
};

Runtime 39 ms/Beats 77.19%
Memory 60.20 MB/Beats 78.06%

Если сделать

	template<size_t bit>
	void sort(vector<int>& arr, size_t b, size_t e)
	{
		if (e - b <= 1) return;

		auto i = b;
		auto j = e;
		while (i < j) {
			while (i < j and ((unsigned)arr[i] >> bit & 1) == (bit == 31))
				i++;

			while (i < j and ((unsigned)arr[j - 1] >> bit & 1) == (bit != 31))
				j--;

			if (i < j) std::swap(arr[i++], arr[--j]);
		}

		if constexpr (bit != 0) {
			sort<bit - 1>(arr, b, i);
			sort<bit - 1>(arr, j, e);
		}
	}

Runtime 31 ms/Beats 77.22%
Memory 60.09 MB/Beats 85.22%

Ты ускоряешь спички. Асимптотическая сложность вставки чисел в set таким образом - линейная.

Я бы ожидал что с std::unordered_set (как и с boost::unordered_set) всё проседает на куче коротких аллокаций. Хотите соревноваться с in-place сортировкой вектора интов - возьмите хеш-табличку которой не приходится мантейнить список. Я, собственно, это уже предлагал.

P.S. обычный std::sort даёт 15 ms. Зато не O(n) 🤡

Зато не O(n)

Дык, N должен быть сильно больше чем хотят в задачке чтобы log(N) оправдал 32 прохода :)

           if (!set.contains(n - 1)) {
               cnt = 1;
               int m = n + 1;
               while (set.contains(m)) {
                   ++cnt;
                   set.erase(m++);
               }
           }
           ret = std::max(ret, cnt);

Странно что это даже быстрее (81 vs. 87 ms) чем

		for (int n : set) {
			if (set.contains(n - 1)) continue;

			int cnt = 1;
			int m = n + 1;
			for (auto it = set.find(m); it != set.end(); it = set.find(++m)) {
				cnt++;
				set.erase(it);
			}
			ret = std::max(ret, cnt);
		}

хотя ищет в два раза чаще (contains+erase по ключу)

можно матан включить

т.е той же синтаксической_болталкой подобрать хэш функцию по границе (10**6 вариантов из диапазона) предвычеслить эту функцию

али по какой нить теореме невозможности универсального сжатия такая функция хэша не возможна?!

возможно фига в кармане именно в вычислительной сложности нахождения соседа у натурального представленного в битовой(показательная по основанию 2) форме!

т.е если офлайн при любом входе предварительная сортировка «всегда» быстрее «линии»

для онлайна было решение (выше) показывающее текущий максимум

крч вопрос тюнинга и дисера по хэшам :)

а чего не понятно? в asm set это битовая маска говорящая что есть такой элемент, то есть 8 элементов хранится в байте, а вектор минимум 8 байт, или ещё больше.

можно матан включить

Можно мозг включить. Если отбросить патологические случаи постоянных коллизий mod(hash) которые придётся специально подбирать, я думаю я бы смог на хеш-табличке обогнать сортировку «on average». Если нужно гарантировать worst case perf - на практике сортировка самый приемлемый вариант.

включай!

Итерация по unordered_set быстрее чем по vector? (комментарий)

ограничевшись отведением битов для диапазона от min до max входа

можно и сортировку обойти - была бы память в проце аж в регистрах

любобытна реализация обходящая гарантированно штатную сортировку для случая офлайн(данные полностью на входе)

в ограничениях из литкода(по размеру массива и диапазона значений) - без ограничений на ram

всё упирается в сложность(относительно сравнения или разпыления(если radix)) поиска соседа у натурального числа

На литкоде всратый таймчекер, ему вообще не следует доверять. Совсем.

N должен быть сильно больше

Ага, возможно только при log(N) > 32 начнет оправдывать по сравнению с «быстрыми» сортировами, которые умеют тоже «разделять и властвовать».

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

Если использовать boost::unordered_flat_set вместо std::unordered_set, то при N меньше нескольких сотен тысяч - миллиона заметно быстрее сортировки. Но при приближении к миллиардам замедляется до алгоритма с сортировкой, и дальше продолжает замедляться. Судя по моим бенчмаркам.

PS. Надо бы сравнить с abseil-cpp

ЧиТД :)

ПыСы. Я сильно подозреваю что на длинном входе замедление связано с тем что табличка перестаёт в cache умещаться, попробуйте не раздвигать её так агрессивно.

замедление связано с тем что табличка перестаёт в cache умещаться

Про кэш и прочее.

При N меньше ~30’000 алгоритм (как бы) имеет линейную сложность (как по учебнику). А дальше коллизии, расширение бакетов, непопадание в кеш и тд и тп, и алгоритм превращается nlogn, с тенденцией ухудшения.

Кстати, стандартный unordered_set превращается в n^2 при миллиарде.

А как в ваших тестах число уникальных значений соотносится с N?

Воля псевдорандома, с вероятностью встретить хоть один повтор «допустим» N/INT_MAX. «Допустим» - потому что я не хочу (и не умею) в теорвер.

Если вы искусственно не зажимаете диапазон то по моим понятиям дупликатов там не будет. Что не очень реалистично, кмк. Попробуйте, например, на миллиарде значений из первых 100к.

на миллиарде значений из первых 100к

Неинтересно, явная поблашка для хеш-функции и коллизиям.

Ну, хотя бы в 2 раза диапазон зажмите. В оригинальном тесте вон в конце то-ли половина то-ли 25% нулей.

В оригинальном тесте

Я к нему уже давно потерял интерес. Я теоретические unordered’ы сталкиваю с псевдореальностью.

Я теоретические unordered’ы сталкиваю с псевдореальностью.

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