HashSet против ArrayList содержит производительность

При обработке больших объемов данных, я часто делаю следующее:HashSet против ArrayList содержит производительность

HashSet<String> set = new HashSet<String>(); 
//Adding elements to the set 
ArrayList<String> list = new ArrayList<String> (set);

Что-то вроде «демпинг» содержимое набора в списке. Обычно я делаю это, так как элементы, которые я добавляю, часто содержат дубликаты, которые я хочу удалить, и это кажется простым способом их удалить.

Только с этой целью в виде (избегая дубликаты) Я мог бы также написать:

ArrayList<String> list = new ArrayList<String>(); 
// Processing here 
if (! list.contains(element)) list.add(element); 
//More processing here

И, таким образом, нет необходимости «сбрасывать» набор в список. Тем не менее, я бы сделал небольшую проверку перед вставкой каждого элемента (который я также предполагаю, что HashSet делает это)

Является ли любая из двух возможностей более эффективной?

источник

2015-09-13 Jorge

У вас возникла ваша первая часть вопроса. Вы сбрасываете список в наборе, чтобы избавиться от дубликатов, а не наоборот, не так ли? – MirMasej

Почему бы вам не проверить его? Кстати, зачем вообще конвертировать набор в список? Переход через набор, скорее всего, будет быстрее для больших массивов. – luk32

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

Набор даст гораздо более высокую производительность (O(n) против O(n^2) для списка), и это нормально, потому что избежать дубликатов является сама цель набора.

Содержит для HashSet не O(1) по сравнению с O(n) для списка, поэтому вы должны не использовать список, если вам часто приходится работать contains.

источник

2015-09-13 17:11:56 Dici

Что делать, если список содержит только несколько элементов? –

Сложность расчета не распространяется на ограниченные задачи. Его цель - понять, насколько медленнее происходит вычисление, когда размер проблемы увеличивается, становясь бесконечно большим. Тем не менее, я не думаю, что когда-либо существовало преимущество при использовании списка по хэш-набору для операции 'contains'. Несомненно, в наборе есть большие накладные расходы памяти, но если у вас есть несколько элементов, только зачем вам это вообще нужно? Более эффективные реализации набора существуют для ограниченных наборов данных (например, EnumSet), но, как правило, простой набор хэшей должен быть достаточным для типичных требований к производительности. – Dici

Часто у нас уже есть эфемерный список, для которого нам нужно запустить '.contains'. Вопрос в том, из какого размера имеет смысл создавать набор? Менее 10 элементов выполняются в масштабе 1-2 микрона, но мы тратим время на создание набора. В любом случае, это быстрый тест, если кто-то интересуется https://gist.github.com/ibalashov/0138e850e58942569a636dffa75f0bb9 –

ArrayList использует массив для хранения данных. ArrayList.contains будет иметь сложность O (n). Таким образом, по существу поиск в массиве снова и снова будет иметь сложность O(n^2).

В то время как HashSet использует хеширующий механизм для хранения элементов в своих соответствующих ковшиках. Операция HashSet будет быстрее для длинного списка значений. Он достигнет элемента в O(1).

источник

2015-09-13 17:11:47 YoungHobbit

Если вам не нужен список, я бы просто использовал Set, и это естественная коллекция, которая будет использоваться, если заказ не имеет значения, и вы хотите игнорировать дубликаты.

Вы можете сделать это, так как вам нужен список без дубликатов.

private Set<String> set = new HashSet<>(); 
private List<String> list = new ArrayList<>(); 


public void add(String str) { 
    if (set.add(str)) 
     list.add(str); 
}

Таким образом, список будет содержать только уникальные значения, исходный порядок вставки сохраняется, и операция является O (1).

источник

2015-09-13 17:12:07

Я бы упомянул, что вместо ссылки «LinkedHashSet» можно использовать, если порядок имеет значение, или «TreeSet», если есть порядок сортировки Требование – Dici

Так просто и так элегантно! Мне нравится! – Jorge

@Jorge примечание: Set.add (x) возвращает true только в том случае, если он был добавлен в первый раз. –

Вы можете добавить элементы в список. Затем к DeDup -

HashSet<String> hs = new HashSet<>(); // new hashset 
hs.addAll(list); // add all list elements to hashset (this is the dedup, since addAll works as a union, thus removing all duplicates) 
list.clear(); // clear the list 
list.addAll(hs); // add all hashset elements to the list

Если вам нужен только набор с DeDup, вы можете также использовать addAll() на другой набор, так что он будет иметь только уникальные значения.

источник

2018-03-08 05:06:53

HashSet против ArrayList содержит производительность

ответ

Смежные вопросы