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

на литкод кривой «таймер»

решение с сортировкой(ибо она в бинаре) т.е О(nlogn) быстрее линейного слияния отрезков (предыдущий пост)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:return 0
        nums,o,l=sorted(set(nums)),0,0
        p=nums[0]-2
        for v in nums:
            if p+1==v:
                l+=1
            else:
                o=max(o,l)
                l=1
            p=v
        return max(o,l)

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

в обычно O(1) - это когда заполняем предвыделеный пул

в худщем O(N) - это когда перевыделяем и копируем

так как в правильных векторах перевыделение случается всего лишь logN раз то амортизационо добавление в вектор O(1)

у него вроде отсечка скан начинается только с меньшего в последовательности каждой

тогда все элементы проверяются тока по разу

у Кнутия константы под O глухие - не читаются :)

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

*для каждого впервые встреченного числа образуем интервал [] смотрим есть ли слева и справа интервалы - если есть сливаем

* апдейтим макс длину по ходу

итого линейный код выше по треду

неа

правильный мы просто собираем интервалы на впервые встреченых числах

алгоритм полностью online по мере поступления чисел поддерживаем набор интервалов

Так именно это и получается, просто интервалы заданы неявно в set<int>.

Я просто сразу не распарсил;-(

Зависит от аллокатора. И вообще есть контейнеры с блочным выделение памяти, есть свои менеджеры памяти и т.д. и т.п.

:) на больших

начинает вылазить длина адреса :)

сортировка не то что бы излишня - она бОльшую константу (тереритически так то sort на сях так што ) по хорошему это онлайн оно не требует офлайн-сортировки

тетеритически

по мере прихода чисел (предполагаем что они уникальны) для каждого n

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

Но ведь будет в лучшем случае O(α(n)) 🌚

самое лобовое: для каждого ещё не сожоного числа выжигаем интервал в котором оно

class Solution:
    def longestConsecutive(self, n: List[int]) -> int:
        o=0;h=(len(n)+1)//2
        f=set(n)
        for l in set(n):
            if l in f:
                r=l+1
                while l-1 in f:f.remove(l);l-=1
                while r in f:f.remove(r);r+=1
                if o<(t:=r-l):
                    o=t
                    if o>=h:return o
        return o 

end:

class Solution:
    def longestConsecutive(self, n: List[int]) -> int:
        o=0;h=(len(n)+1)//2
        f=set(n)
        while f:
            v=f.pop()
            l,r=v-1,v+1
            while l in f:f.remove(l);l-=1
            while r in f:f.remove(r);r+=1
            if o<(t:=r-l-1):
                o=t
                if o>=h:return o
        return o

решение с сортировкой(ибо она в бинаре) т.е О(nlogn) быстрее линейного слияния отрезков (предыдущий пост)

log(50000) < 16

После этого вопрос: сколько действий на одно число в 1 и 2 случаях?

sorted(set(nums)) - нафига? лень написать ещё одно условие?

Да, с сортировкой очень быстро получается

longest_consecutive([_]) -> 1;
longest_consecutive(Nums) ->
	longest_consecutive(lists:sort(Nums), 1, 0).

longest_consecutive([H1 | [H2 | _] = T], N, NMax) ->
	N2 = if
	         H1 == H2 -> N;
		 H1 == H2 - 1 -> N + 1;
		 true -> 1
	     end,
	longest_consecutive(T, N2, max(N2, NMax));

longest_consecutive(_, _, NMax) -> NMax.

Runtime
17ms
Beats100.00%

Memory
197.40MB
Beats100.00%

Вообще в managed языках бессмысленно сравнивать варианты с сортировкой или без, т.к. сортировка все равно реализована на c.

Какое?

если

42

один из аргументов не известного веса в функции принятия решения ага

али известного в достаточно нелинейной функции чорно-чорно ящечной

Нужно:

assert(set.size() == nums.size());

Мои 42 лежат в другой плоскости.

Вообще в питоне довольно глупо говорить о достижении высокой скорости - для этого есть другие яп:-)

«Плоско мыслите похвалил Проффесор одномерного человека»

Нет, просто кто на что учился.

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

А это и не питон, хотя конечно то же самое справедливо

Не Антон & Не аноним: имхо самое из online-подходов: на сяшку(и ++) прозрачно транслируется если чё:

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        u,d,o=set(),{},0
        for l,r in zip(nums,nums):
            if l in u:continue
            u.add(l)
            if(p:=l-1)in d:l=d[p]
            if(q:=r+1)in d:r=d[q]
            d[l]=r
            d[r]=l
            o=max(o,r-l+1)
        return o

Для сведения.

Инициализация std::unordered_set из случайных чисел имеет сложность O(N) = N * log(N), судя по логу google bechnmark

BM<init_set>_BigO        3.63 NlgN       3.63 NlgN 

Полный лог

-------------------------------------------------------------
Benchmark                   Time             CPU   Iterations
-------------------------------------------------------------
BM<init_set>/1           41.8 ns         41.8 ns     16747908
BM<init_set>/2           58.0 ns         58.0 ns     11824856
BM<init_set>/4           89.6 ns         89.6 ns      7208512
BM<init_set>/8            174 ns          174 ns      4225386
BM<init_set>/16           357 ns          357 ns      2007639
BM<init_set>/32           718 ns          717 ns       954686
BM<init_set>/64          1469 ns         1468 ns       474293
BM<init_set>/128         5210 ns         5207 ns       135646
BM<init_set>/256        10785 ns        10778 ns        66708
BM<init_set>/512        21090 ns        21079 ns        34205
BM<init_set>/1024       41720 ns        41698 ns        16160
BM<init_set>/2048       86734 ns        86688 ns         8202
BM<init_set>/4096      179873 ns       179763 ns         3864
BM<init_set>/8192      373319 ns       372977 ns         1893
BM<init_set>/16384     808375 ns       807874 ns          858
BM<init_set>/32768    1715917 ns      1714928 ns          410
BM<init_set>/65536    3843654 ns      3839785 ns          187
BM<init_set>_BigO        3.63 NlgN       3.63 NlgN 
BM<init_set>_RMS            5 %             5 %    

init_set это просто функция, которая создает unordered_set из N случайных чисел.

PS. Давно хотел написать, но РКН заблокировал cloudflare

с помощью union find

Я бы посмотрел реализацию. Но как минимум надо сперва надо инициализировать эту структуру «уникальными» значениями. Даешь unique за линейное время!

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

дык на айлюлюкоде основная движуха

тут угар кутежа лор-экспертов

А тут спамишь худшие варианты?

Смысл этой движухи. Я могу сразу сказать, что выиграет NlgN алгоритм с деструктивной сортировкой на месте.

bugfixer ?

тут боюсь куча нюансов, например как соотносится диапазон чисел и число бакетов?

диапазон чисел

0..RAND_MAX

число бакетов

дефолт. И врядли изменить сложность. Разве что за счет памяти размером RAND_MAX.

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

опятже как тут уже заметили для полного многообразия достаточно четверти гигабайта в котором не более лакха взведёных битов - т.е scas{q} :)

если многопроходной то число проходов скорее ближе к 3 чем к 5*log(10) - если же однопроходный то тот же союз-поиск это акерман_обратная

и это оценка сверху

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

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

То есть нет ограничения (сложности) по памяти? Тем более нет смысла.

многопроходной 5*log(10)

Фиксированные коэфициенты.

союз-поиск

Хочу увидеть реализацию, а точнее хотя бы инициализацию структуры уникальными непересекающимися значениями.

слияние интервалов по мере прихода новых единичных

основанный на hash_table/unordered_set, который медленнее сортировки?

вы предлагаете выкатить структуру данных для неболее чем 10**5 целочисленных ключей по модулю небольших 10**9

которая следуя хранению непрерывных последовательностей - по краю узнаём парный край

точка это край на себя

обставляет сортировку 10**5 ключей из вышеуказаного диапазона

так?

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

пишите!

если увижу как подтюнить подтюню

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

однопроходное включение(всякое целое(из входа) k есть интервал [ k, k ] ) и слияние соседних интервалов на ходу и хранение максимальной текущей длины

можно и померять

пишите!

Сперва покажите попугаев!

Вот мои попугаи

BM<init_set>_BigO             3.43 NlgN       3.43 NlgN
BM<lcs_sort>_BigO             0.48 NlgN       0.48 NlgN
BM<lcs_sort_copy>_BigO        2.71 NlgN       2.71 NlgN
BM<lcs_lor>_BigO              7.77 NlgN       7.77 NlgN

• init_set - только инициализация unordered_set
• lcs_sort - алгоритм с сортировкой на месте, деструктивный
• lcs_sort - алгоритм с сортировкой с копированием
• lcs_lor - алгоритм ТС

в плюссах давне(если вообще) не копенгаген

хз какой более примитивный(может какой упрощённый красно-чёрный фикус есть)

class Solution {
public:
    int longestConsecutive(vector<int>& a) {
        unordered_map<int, int> d;
        unordered_map<int, bool> u;
        int o = 0, n =a.size(),l,r,p,q,z;
        auto e=d.end();
        for(int i=0; i<n; i++){
            l=r=a[i];
            if(u[l])continue;
            u[l]=1;
            auto x=d.find(l-1);
            if(x!=e)l=x->second;
            auto y=d.find(r+1);
            if(y!=e)r=y->second;
            d[r]=l;
            d[l]=r;
            if(o<(z=r-l+1))o=z;
        }
        return o;
    }
};

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

ну и для u есть какой обычный сет(беспорядочный)?!

на литкоде показывает плохое время

по сути тот же вариант :

class Solution {
public:
    int longestConsecutive(vector<int>& a) {
        unordered_map<int, int> d;
        unordered_map<int, bool> u;
        int o = 0, n =a.size(),l,r,p,q,x,y,z;
        for(int i=0; i<n; i++){
            l=r=a[i];
            if(u[l])continue;
            u[l]=1;
            if(d.find(l-1)!=d.end())l=d[l-1];
            if(d.find(r+1)!=d.end())r=d[r+1];
            d[r]=l;
            d[l]=r;
            if(o<(z=r-l+1))o=z;
        }
        return o;
    }
};

Просто инициализация unordered_{set,map} без алгоритма(!) медленее чем полный алгоритм с сортировкой.

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

в плюссах давне(если вообще) не копенгаген

Пиши попугаи на питоне! Покажи мне попугаев!

алго с сортировкой это оффлайн

мой(последие варианты) сливает по мере прихода новых

ВОООТ

имхо можно выкрутить быструю сд с двумя свойствами:

1. есть ли целый ключ

2. какой ключ по ключу :)

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

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

дык там sort заведомо ближе к железу :(

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

тогда при слиzнии если очередная пара соседи то на выходе один отрезок

тобишь при слиянии число элементов может уменьшаться :)

Где? Попугаи?

А на словах вы совсем не Лев Николаевич. Меньше слов.

койкие попугая?

тут нет плюсоф

попугайте сырец и свои покажи(те)

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

в предположении равновероятности наборов