Aleksandr
О(n) vs O(position)
ну, в каких случаях, при 1000 позиций у нас будет O(1000) при слайсе? В каком случае у нас сработает худший вариант? При фильтре всегда O(n)
Андрей
Чо?) O(position)?) Кек. А откуда этот position будет получен?
Sergey
Я тут немного вмешаюсь в ваш деликатный спор... Речь идёт про slice vs filter или про splice vs filter? А то часто splice со slice путают 🙈
Ivan
ну, в каких случаях, при 1000 позиций у нас будет O(1000) при слайсе? В каком случае у нас сработает худший вариант? При фильтре всегда O(n)
Либо перестань пороть чушь, либо не используй О-нотацию. Просто признай, что порешь чушь, и мы все пойдём спать. А завтра снова все пойдём верстать формочки.
Maksim
Это где? или ты только через строку читаешь? Я сразу написал, что они равны только в худшем случае, в 90% у слайса скорость не равна O(n)
«Худший» и «Лучший» случаи для алгоритмов употребляются не в этом случае. Например при сортировке один и тот же алгоритм может выдавать разную сложность при разных данных в массиве. У slice и filter сложность всегда одна O(n) и нет никаких худших и лучших случаев
Китикет
Aleksandr
Либо перестань пороть чушь, либо не используй О-нотацию. Просто признай, что порешь чушь, и мы все пойдём спать. А завтра снова все пойдём верстать формочки.
Эм, тебе чем так моя чушь спать мешает? или это не чушь? у тебя есть 1000 элементов, при фильтре ты всегда обрабатываешь 1000 элементов, при слайсе ты доходишь до первого нужного
Андрей
Первое Этот чувак считает что надо всегда писать слайс, так как это быстрее
Я уверен, что благодаря подобным чувакам в движке специальную оптимизацию под этот кейс написали.
Aleksandr
да, в худшем варианте это всегда O(n), но худший вариант не всегда работает =)
Dmitry
Уже ж спорили о слайс и фильтр Это где 2 слайда делали ?
Андрей
https://jsperf.com/array-slice-vs-filter-for-removal-by-index
И это если не забывать, что во многих случаях сначала этот индекс надо найти)
Aleksandr
+
The get/post request has failed :( не работает график, можешь скинуть?
Китикет
Вообще истина простая, вариант со слайсом действительно быстрее, только вот для разных кейсов (удаление, модификация) надо писать разные хелперы, в отличие от фильтра, который в разы более читаемый и универсальный
Ivan
Эм, тебе чем так моя чушь спать мешает? или это не чушь? у тебя есть 1000 элементов, при фильтре ты всегда обрабатываешь 1000 элементов, при слайсе ты доходишь до первого нужного
Да, всё верно. НО ЭТО НЕ МЕНЯЕТ АЛГОРИТМИЧЕСКУЮ СЛОЖНОСТЬ, КОТОРАЯ ВСЕГДА СЧИТАЕТСЯ ДЛЯ ХУДШЕГО ВАРИАНТА! Ты тут орал «или алгоритмы учи, ты чсв», а сам придумал какой-то O(position).
Андрей
Ivan
Подскажите, вероятно, я тут неправильный тип использую. Какой нужно, чтобы датасет был доступен?
Sergey
Firefox?
Yury
во, парень фильтр использует
Андрей
Firefox?
edge(chromium)
Yury
у меня в хроме тож не подгрузило
Aleksandr
Да, всё верно. НО ЭТО НЕ МЕНЯЕТ АЛГОРИТМИЧЕСКУЮ СЛОЖНОСТЬ, КОТОРАЯ ВСЕГДА СЧИТАЕТСЯ ДЛЯ ХУДШЕГО ВАРИАНТА! Ты тут орал «или алгоритмы учи, ты чсв», а сам придумал какой-то O(position).
Алгоритмическая сложность да, считается для худшего, в реальном исполнении какой процент худших вариантов мы получаем? Всегда считаем худший и норм? но что же, в этом исполнении мы всегда грузимся как при худшем варианте, что хуево
Sergey
edge(chromium)
Чёт ms походу перелопатело хромого походу 👀 раз такой разрброс x11 vs x2
Андрей
Чёт ms походу перелопатело хромого походу 👀 раз такой разрброс x11 vs x2
Нет, у меня показатели скачут. Хреново мы бенчмаркаем)
Dmitry
Я пропустил Какую сложность для среза тут написали ?
Андрей
Ещё один запуск.
+ там ошибка что-то слишком огроменная. +-17%.
Aleksandr
return [...array.slice(0, index), ...array.slice(index + 1)]; я скорее всего тупой, но почему тут деструктуризация используется, а не array.slice(index, index+1)
Sergey
Нет, у меня показатели скачут. Хреново мы бенчмаркаем)
Ну я готовый взял. Лень свой писать, т.к. в целом этот бэнч и так показывает разницу.
Aleksandr
Ты серьезно не понимаешь, что я имею ввиду?)
Я тебя понимаю, но я писал про другое, а не про то, что ты =)
Андрей
O(n) всегда считается для самых плохих вариантов =)
Какая сложность у быстрой сортировки?
Ivan
Тебе в https://t.me/ts_ru
Тут скорее по реакту вопрос, мне кажется. Я предполагаю, что нужно правильный тип выбрать и в качестве дженерика сюда что-то кинуть? хотя могу и ошибаться
Андрей
пузырек?
google "quick sort".
Китикет
const idx = items.findIndex(item => { return item.id === searchIndex }) const partA = items.slice(0, idx) const partB = items.slice(idx + 1) const updatedItems = partA.concat(partB) Вот так надо делать, деструктуризацию нельзя там юзать, плохой бенчмарк
Китикет
пузырек?
Чувак, кто там мне про алгоритмы говорил?
Aleksandr
Чувак, кто там мне про алгоритмы говорил?
Я, тебе =) у тебя все еще нет этого представления =) ты чего молчал то?
Китикет
Деструктуризация быстрее конката в тестах
Ахаах, не поверю, кучу раз тестил)
Андрей
Я, тебе =) у тебя все еще нет этого представления =) ты чего молчал то?
Так какая сложность у быстрой сортировки? Даже с гуглом ответить не можете?
Dmitry
Ахаах, не поверю, кучу раз тестил)
Я тоже тестил И вот она реще
Андрей
O(n) в худшем случае =)
Эм, что? Сортировка с линейной сложностью, которая написана методом разделяй и влавствуй?
Aleksandr
O(LogN) в общем =)
Андрей
А вы знаете, что ещё 50 лет назад было теоретически доказано, что никакая сортировка методом разделяй и влавствуй не может быть быстрее чем O(NlongN)?
Sm•ok
O(LogN) в общем =)
Не похоже
Андрей
Вы точно что-то в теории алгоритмов понимаете?
Китикет
Я тоже тестил И вот она реще
У меня в jsbench с телефона в 2 раза быстрее конкат, но это на мелких массивах Не могу сейчас норм проверить Но вообще конкат не делает итераций, должен быть однозначно быстрее, странно если не так
Андрей
и? ты сократи свое выражение для худшего случая, получится O(N)
Тебе пора нобелевку получать. https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B4%D0%B5%D0%BB%D1%8F%D0%B9_%D0%B8_%D0%B2%D0%BB%D0%B0%D1%81%D1%82%D0%B2%D1%83%D0%B9_(%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0)#%D0%AD%D1%84%D1%84%D0%B5%D0%BA%D1%82%D0%B8%D0%B2%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0 Ты опроверг теоретическую минимальную сложность алгоритма.
Андрей
И это правда нобелевка, потому что после такого достижения вся математика идёт нахуй полностью.
Андрей
Ну, кроме арифметики, наверное.
Stanislav
Хуясе история на моих глазах вершится
Андрей
Вместе с ней
Ну, всё-таки счёт на пальцах непоколебим, я надеюсь)
Stanislav
Так и к чему пришли пачаны, а то интереснее нежели вечерний сериальчик
Китикет
Вот мы ржом, а человек ведь завтра пойдет и докажет
Aleksandr
И это правда нобелевка, потому что после такого достижения вся математика идёт нахуй полностью.
ты всю статью прочитай =) Таким образом, например, многие библиотечные применения быстрой сортировки превратятся в простой алгоритм сортировки вставки на основе цикла (или аналогичный), как только количество элементов, подлежащих сортировке, будет достаточно мало. Причем, если бы пустой список был единственным базовым случаем, то сортировка списка с n записями привела бы к максимальному n числу вызовов быстрых сортировок
Китикет
что слайс сбыстрее фильтра ?
Нет, что у quick sort сложность O(N) xD