Java, что быстрее: примитивы или коллекции?

Question

[Wan-Derer]

Возник небольшой спор относительно скорости алгоритма.
Вот: https://www.youtube.com/watch?v=pwG_B0tEj9M&lc=Ugz...
Задача: определить есть ли в массиве, переданном в метод, повторяющиеся элементы.
Я решил используя set , там в комментариях 2 варианта кода. И высказался что в данном конкретном случае такое решение будет более медленным чем ручной перебор int.
Дама мне оппонирует, утверждая что такой способ как раз быстрый. Но мы говорим на разных языках. Она мне валит термины из книжек, которые мне непонятны (т.к. вопросами формальной сложности я пока не занимался), а я стараюсь объяснить/понять "на пальцах".
А как по-вашему? Если можно, "на пальцах" :)

Answer 1

[Сергей Горностаев]

Я не буду смотреть 46 минут видео, чтобы понять о чём конкретно речь, но ориентируясь на заголовок вопроса, могу сказать, что сравнивать коллекции с примитивами - это как сравнивать мягкое с тёплым.

Comments

[Wan-Derer]

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

Добавлю. На случай если комментарии по ссылке не открываются, вот код:

public static boolean containsDuplicates(int[] array) {
    Set<Integer> set = new HashSet<>();
    for(int item:array){
        if (!set.add(item)) return true;
    }
    return false;
}

Я думаю что он будет медленнее чем перебор массива двумя вложенными циклами. Но строго обосновать не могу. А как думаете вы? Только объясняйте по-простому если можно :)

[Сергей Горностаев]

Wan-Derer, у меня по ссылке открылось видео. Понятия не имею о каком комментарии речь.

[Wan-Derer]

Сергей Горностаев, Я отредактировал ответ, см. выше.

[Сергей Горностаев]

Wan-Derer, почему вы думаете, что это будет медленнее? Вы знакомы с понятием множеств и принципу поиска по хэшу?

[Wan-Derer]

Сергей Горностаев, Нет, я этот вопрос не изучал. Мне интересен не поиск по хэшу вообще, а в данном конкретном случае. Мне интуитивно представляется что поиск по хэш-таблице будет не быстрее чем поиск по массиву int[]. Плюс есть накладные расходы, связанные с добавлением элемента в Set и они по моей оценке немаленькие.

[Денис Загаевский]

Wan-Derer, братан, иди учи матчасть. Это очень сложный вопрос, чтобы разбираться в нём интуитивно. Очень много факторов.
Сет будет О(n) сложен по времени и потребует дополнительно О(n) памяти. Память небесплатная, могут случиться кэш-миссы, плюс боксинг примитивов...
Но O(n²) есть О(n²). На больших объемах данных это будет медленно.
Так что самый нормальный вариант решить эту загвоздку это бенчмарк.

[Сергей Горностаев]

Wan-Derer, простая аналогия: У вас есть список людей, гостиница на 1000 номеров и необходимость проверить, живёт ли в этой гостинице кто-нибудь из списка. Перебор двумя вложенными циклами - это когда вы обходите все номера спрашивая, живёт ли тут человек, записанный первым в вашем списке, потом обходите все номера второй раз, спрашивая для второго человека в списке, и т.д. Вариант с HashSet'ом - это когда вы подходите к портье и спрашиваете номер, в котором заселён первый человек из вашего списка, потом второй, третий и т.д. Что будет быстрее?

[Wan-Derer]

Сергей Горностаев, Bavashi, Денис Загаевский,
Не так. Мне надо узнать есть ли в гостинице одинаковые постояльцы. Для этого я:
- беру постояльца из 1 номера и сравниваю его с остальными (первый цикл);
- беру постояльца из 2 номера и сравниваю его с остальными, исключая первый (второй цикл);
- и т.д.
Теперь, что значит "сравниваю"? Я должен сравнить его имя, отчество, фамилию, вес, возраст, девичью фамилию тёщи, кличку собаки соседа..... Это крайне долго и поэтому действительно проще попросить портье сделать поиск по номеру паспорта (каковой номер назначен исходя из всех перечисленных качеств), даже если портье придётся сначала пройти по всем номерам и эти паспорта составить. Ведь он пройдёт по номерам один раз, а вложенные циклы будет гонять уже у себя за стойкой (хотя до некоторых постояльцев ему-таки придётся сгонять, но это уже нюансы).
Так было бы если бы в отеле жили объекты. НО это не наш случай!

Наш случай - крольчатник. Все кролики находятся в клетках с открытой стенкой, мне не надо заходить в каждый номер и потом долго выяснять все интересующие детали. У меня все кролики - полные клоны одного родителя (примитивы!), а отличаются только номерком на ошейнике. Их "перебрать" очень легко и быстро. Я могу сделать это сам, а могу попросить портье. Он сделает то же самое, но с заполнением целой кучи ненужной документации. И что будет быстрее?

[Сергей Горностаев]

Wan-Derer, понятно, мне вас не переубедить. Могу предложить вам прочитать это и вот это, а потом написать тест-кейс для JMH и проверить самому.