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

Да что с вами сегодня такое? 😵‍💫 Поиск и занесение в set - константная операция. Все что в этом алгоритме переменного - две итерации по входным данным, итого O(n).

Процессор? Компилятор? Это интересно!

Ап. Ага, забил он 😂 Возьми исходные данные.

Там поц-счёт делается только при условии

Что правильно отрабатывает только если второй проход по сету. Авторы задачки - молодцы, аплодирую.

Но вот если вектор забить значением 1, то set дает 1e-7 сек на этом спорном цикле и 5e-4 сек вообще, а вектор дает 1.2e-3 сек на цикле и 1.8e-3 вообще.

Никакого секрета здесь нет - у Вас в векторе много дублей, конечно set будет быстрее за счет меньшего числа итераций.

11th Gen Intel(R) Core(TM) i5-1145G7 @ 2.60GHz

gcc version 11.4.0

Поиск и занесение в set - константная операция.

https://en.cppreference.com/w/cpp/container/unordered_set/find

Complexity

Constant on average, worst case linear in the size of the container.

https://en.cppreference.com/w/cpp/container/unordered_set/insert

If after the operation the new number of elements is greater than old max_load_factor() * bucket_count() a rehashing takes place.

Complexity

1-4) Average case: O(1), worst case O(size())*.

Возьми исходные данные.

В исходном массиве 50000 значений, уникальных 25001. На них соответственно 4e-4 сек против 1.5 сек.

Скорее всего дело в алгоритме.

итого O(n).

Если быть совсем точным то там до O(3n) причем насколько близко к этому порогу зависит только от расположения элементов и количества дубликатов. (да я в курсе что это все всходит в O(n), но мы задачку с собеседования в гугл обсуждаем или где?).

Это общий случай. А в данном случае мы храним числа, они хешируются в своё числовое значение. Все операции константны. Если бы это было корнем проблемы - Окей, а так - болтовня

Поиск и занесение в set - константная операция

В идеале, если нет коллизий.

Судя по коду самая длинная обработка там для нуля, а нулей там 25000 (половина). Вот на них все время и уходит, есть разница - один раз ноль обработать или 25000.

И никакие кэши тут непричем.

Завтра буду смотреть детальнее.

Че тут смотреть то?! Если добавить

    for (auto n : nums) {
		if(!n) continue; //<=== вот это
...

то там что set что nums дают одинаковый результат

Если бы это было корнем проблемы - Окей, а так - болтовня

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

А то когда нить впендюрите список (потому что у него добавление O(1)) вместо вектора, у которого типа O(N) и залагает все в тыщщу раз.

Дело вообще не в сложностях, все сложности я указал правильно. У алгоритма похоже есть дефект со множеством нулей, который проявился на этом конкретном наборе данных, на котором в худшем случае будет (и есть) O(n2). И этот худший случай обходится с помощью итерации по set, кажется разобрался. Умно, умно, такое Г подсунуть во входных данных 😂

вместо вектора, у которого типа O(N)

У вектора добавление - O(n)?

В исходной формулировке задача не имеет решения. При плохих данных даже «правильный» алгоритм с хеш-таблицей может легко зависнуть на O(n^2).

Как там проверяются реализации: человеком или запускается программа с ограничением по времени случайными данными? Если второе, то некоторые не пройдут - не повезло.

Автоматически проверяется естественно.

Какие задачи - такие и решатели.

Гугл и пр. так не считает, для них это то как они нанимают людей. В Гугл не собираюсь, для себя решаю.

Гугл - это «уровень».

Дело вообще не в сложностях, все сложности я указал правильно. У алгоритма похоже есть дефект со множеством нулей

И единиц. И двоек… ну конечно-конечно, Вы все сложности указали правильно, это алгоритм кривой. Обычно так всегда и бывает.

У вектора добавление - O(n)?

Смотря какой вектор. Если реаллокация требуется то конечно O(N)

O-нотация описывает поведение сферического вычислителя в вакууме и не учитывает особенностей подсистемы памяти и еще кучи всяких вещей.

ЗЫ если бы Вы взяли set вместо unordered_set, то при правильном подходе имели бы сложность O(n log n) вместо O(n^2). А то length++ здесь это просто какой то лютый говнокод, пардонте… :-(

Если реаллокация требуется то конечно O(N)

Только про реаллокацию ты ничего не говорил 😂

ЗЫ если бы Вы взяли set вместо unordered_set, то при правильном подходе имели бы сложность O(n log n)

Напиши такую функцию, я посмотрю, изучу, протестирую. N log N я и без set-а вообщем-то легко могу получить, просто отсортировав массив и проитерировать окном из двух индексов. Несложно. Но не O(n).

Напиши такую функцию

Зачем мне это?

покажи оба сырца (на векторе и на сете)

время на сервере - сервер тайминги(на малых) криво кажит

если TLE обычно косяк в алго

на (этом) медиуме вполне заходят квадроO

«очевидно» как линеить

твой алго квадратный ибо для каждого из чисел ты луч

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

но можно и квадрат ибо это медиум

правильный алгоритм такой:

1 сортируешь массив по возрастанию.

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

тут только один проход, нет повторного сканирования, ты просто проверяешь монотонного возрастание текущего числа. это O(n).

итого сортировка массива (n*log n) + один проход (n), с просмотром на одно число вперед.

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

Зачем тут +=? Данные надо при наполнении set организовывать так, что бы потом при поиске сразу получать ответ. Более того, тут сам поиск то и не нужен - ответ считается при наполнении set.

Это задача на построение правильной структуры данных, а не на махание for по разным контейнерам.

Зачем мне это?

А ну да, точно. Теоретик.

Я так и написал, используя сортировку эта задача решается достаточно легко. Не понял зачем ты мне это расписал, если я написал тоже самое 😂 Только этот способ не будет O(n).

Бггг, конечно, куда мне до Вас то - прибегающего на ЛОР с непонятками в тривиальной задаче.

Детский сад какой то у Вас в голове… соболезную.

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

Спросить не стыдно. Стыдно не знать complexity вектора, и ещё рассказывать как по-умному всё нужно сделать. Ну так ты сделай сперва, теоретик. Если сделаешь лучше - снимаю шляпу.

Ну в час ночи эта задача меня согнула, я не отрицаю 😂

Зачем тут +=

всяко нужно 2 переменные для задания отрезка(связности)

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

дык код pls

Более того, тут сам поиск то и не нужен - ответ считается при наполнении set.

что за set такой - реализацию pls

Это задача на построение правильной структуры данных, а не на махание for по разным контейнерам.

да! код ?

код в студии?!

линейный код прост если не пробать все по новой

как выше «пушкой по воробьям» это union-find где ребро это соседи в натуральном ряде :)

Стыдно не знать complexity вектора

Вы не знаете судя по всему. «Ты про реаллокацию ничего не говорил»(с)

Ну так ты сделай сперва, теоретик.

Стыдно хамить незнакомым дядям.

Если сделаешь лучше - снимаю шляпу.

А накой мне Ваша шляпа?!

Если бы Вы нормально общались я бы м.б. и сделал. А так… мне по работе приходится делать куда более сложные и интересные вещи, а вот Ваши задачи и Ваше мнение меня вообще не интересуют. Это результат хамства и Вашей необучаемости. Зачем мне тратить на Вас время?!

Всего хорошего, вон с alysnix общайтесь - как раз Ваш уровень, бггг. Хотя нет, даже до него Вы не дотягиваете.

всяко нужно 2 переменные для задания отрезка(связности)

Напиши объект непрерывного интервала и храни такие штуки в set. В переменной держи самый длинный интервал. Но помни, что интервалы придется иногда сшивать.

На питоне set куцый в смысле интерфейса, это лучше на плюсах делать.

Формально будет все тот же O(N log N), но на практике скорее всего O(N log M) где M много меньше N, от данных зависит. Для 5e4 элементов можно в сторону битовой маски подумать, или тупо взять вектор тех же самых интервалов длины 5e4.

Дальше нюансы реализации, но все ОЧЕНЬ сильно зависит от данных. В данных ТС максимальный int 25000 например;-)

ну так словарём

отфильтровывая setoм(входным) дубли

можно пихать новый ключ в словарь с 1 если нет предшественика иначе новый ключ со значением предшественика+1

так мы получим список лучей

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

O(n*Z) n размер входа

где Z сложность единичной модификации словаря

всё ж код был бы интересней :)

ну так словарём

Зачем две дублирующих сущности - словарь и set?

Да ты глянь входные данные ТС. Там [1, 2, 3,... 25000, 0, 0... 0]

На самом деле всё правильно ТС сделал, накосячил только чутка чем увёл дискуссию в несколько неправильное русло. И то что там O(N) получается тоже очевидно доказывается, и даже hash(n) = n хватает.

Чем правильно то?!

Решение кривое как код студентов заборостроительного техникума…. даже алгоритм от alysinx более прямой;-)

Вот накой там unordered_set? Зачем ТС его взял понятно - прочитал что вставка O(1) и возрадовался, но по делу то оно там нафига? Для данных ТС с его алгоритмом тогда уж лучше пару битовых масок взять, O(N^2) останется но можно соптимизироваться на два порядка и дублей с нулями не будет.

И как ты в общем случае задачу с сортировкой сведешь к O(N)?

даже hash(n) = n хватает.

А если возьмем вектор со значениями до 1<<31 и все значения кратны числу бакетов?;-)

и даже hash(n) = n хватает

Constraints:
    0 <= nums.length <= 10^5
    -10^9 <= nums[i] <= 10^9

там диапазон чисел 10^10. хеш должен быть от числа, а не от его индекса. поэтому что в одно значение хеша при формуле -

hash(x) = x 

попадает до 10^5 чисел. нипайдет.

чтобы компактно захешить 10^10 натуральных нужен не такой уж тривиальный хеш.

но если нет ограничений по памяти - то просто битовый массив длиной 10^10 бит. std::bitset кажется называется.

Вот накой там unordered_set?

Антон, вот сейчас ты меня откровенно расстраиваешь. У меня тоже была первая реакция отсортировать и пробежаться. Но там неизбежно вылазит log(N). Смотри на этот hash set как bitmap - я спешу напомнить что в условии ограничение на диапазон значений имеется, и одно это позволяет уместиться в ~250MB даже если делать в лоб. Hash set это просто более компактное представление этого bitmap’чика.

Если не вводить интервалы то есть два варианта:

1. делаем как ТС - взяли очередной элемент и проверяем все что может быть дальше последовательно. Это O(N^2) - N элементов и на каждый элемент N проверок.

2. используем сортировку в том или ином виде, тогда это O(N log N) на сортировку и потом O(N) на один проход подсчета.

Угадай что быстрее?;-)

Решение кривое как код студентов заборостроительного техникума…. даже алгоритм от alysinx более прямой;-)

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

Я не отрицаю что только учусь

А ты пока ничего не показал

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

sorry but:

Constraints:

0 <= nums.length <= 10**5

-10**9 <= nums <= 10**9

2ALL

уважаемые знатоки вы эта - прочитайте что-ли условия аааа! аааа?

Угадай что быстрее?;-)

Я продолжаю делать ставку на решение от ТС и утверждаю что после всех фиксов там честные O(N).

И что?

А, да, ты прав а я нет;-(. За счет оптимизации

if (set.find(n - 1) == set.end())

которая лочит внутренний цикл можно выйти на O(N).

ТС, сорри - не так у Вас все криво как кажется.

Но читать и понимать написанное Вам таки лучше научиться.

А то когда нить впендюрите список (потому что у него добавление O(1)) вместо вектора, у которого типа O(N) и залагает все в тыщщу раз.

Помню-помню такой bread хлебушка – одно тело замутило «вектор» на основе std::list. «Шаблон затрещал, но выдержал». Там правда это была не единственная проблема – это был еще и «вектор мьютексов» (не вектор и не мьютексов, т.к. велосипед по-видимому должен был быть таки семафором). Велосипедил автор как обычно «базу данных в памяти» местами с явной копипастой из «Large Scale C++ Software Design». Не прошло и полгода, как до этого выпилили чей-то «олимпиадский» DAG… толку от которого все равно не было, т.к. он был с ключами на строках.