Программирование[11]

чел, ты бы хоть имплементацию посмотрел прежде чем пиздеть

там буквально твой же код, только возвращает результат сетовой операции, а не тру/фолс

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

видимо у тебя листА и листБ это нечто иное

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

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

Kant написал 1 час назад:

чел, ты бы хоть имплементацию посмотрел прежде чем пиздеть

там буквально твой же код, только возвращает результат сетовой операции, а не тру/фолс

 

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

видимо у тебя листА и листБ это нечто иное

Нахуя мне смотреть имплементацию, если метод работает с ИТЕРАТОРАМИ блять.

В java collectionA.removeAll(collectionB) вызывает contains() на collectionB который для хэшсетов O(1)

Grohuf написал 3 минуты назад:

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

Пройти да, проверить есть ли элемент в хэш-сете - O(1) епта

Index написал 4 минуты назад:

Пройти да, проверить есть ли элемент в хэш-сете - O(1) епта

А ты знаешь, как устроены хэш-сеты?

Grohuf написал 7 минут назад:

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

@grok это правда?

Нет, это неправда. В общем случае пересечение двух массивов не быстрее пересечения двух сетов. Наоборот — пересечение сетов почти всегда намного быстрее.

Когда массивы теоретически могут выиграть

Только в очень специфических случаях:

Массивы уже отсортированы → можно сделать O(n + m) двумя указателями без доп. памяти.

Элементы — только маленькие целые числа (0..1000), и можно использовать битовые массивы или счётчики.

Объёмы данных совсем крошечные (десятки элементов) — тогда константы перевешивают асимптотику.

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

Но в 99 % обычных задач (особенно когда массивы содержат строки, объекты, большие числа, UUID и т.д. — превращение в set и пересечение через него будет на порядки быстрее.