Collection, без дублей и в случайном порядке в Java

Похож, я не могу либо использовать ArrayList, ни Set:Collection, без дублей и в случайном порядке в Java

Set<> - я могу избежать дубликатов, используя набор, но не варианта воспроизведения в случайном порядке// Collections.shuffle(List<?> list)
ArrayList<> - Я могу использовать shuffle, чтобы рандомизировать список, но дубликаты разрешены.

Я мог бы использовать Set и преобразовать это в ArrayList (или наоборот), чтобы избежать дубликатов. В качестве альтернативы, проведите петлю через набор, чтобы рандомизировать элементы. Но я ищу что-то более эффективное.

источник

2013-02-15 BLuEGoD

Вы можете проверить, находится ли элемент уже в ArrayList, прежде чем добавлять его: myList.contains (myItem); Эта проверка должна быть только O (n). – HectorLector

* что-то более эффективное *> Вы говорите это, потому что вы (а) попробовали его и (б) завершили с помощью соответствующего бенчмаркинга, что это существенное узкое место в вашей заявке? Если нет, преждевременно не оптимизируйте и не напишите, какая версия читается наиболее четко (возможно, конвертировать в arraylist). –

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

Если вы обеспокоены капсулирования, обернуть две коллекции в мета-объект, который реализует List и тщательно документировать, что вставки дубликатов элементов будут отклонены, даже если общий договор List не предписывает так ,

Говоря о стоимости этого решения, я считаю, что с точки зрения времени стоимость будет абсолютно незначительным по сравнению с равниной ArrayList: большинство операций по HashSet сек стоимости амортизируется O (1), а именно поиск и вставки. С другой стороны, использование вашей памяти будет в два раза (или больше, в зависимости от коэффициента загрузки HashSet).

источник

2013-02-15 10:58:33 gd1

Основываясь на вашем комментарии к моему ответу, ваше решение, вероятно, лучше всего. Но я бы упомянул повторную проверку O (1). –

Это несколько противоречиво.В некоторых случаях вставки в HashSet могут стоить O (n). Однако я добавил его. – gd1

Вы также можете реализовать Set вместо этого и создать итератор, который возвращает элементы в случайном порядке, я полагаю. –

Насколько я знаю, комплекты не упорядочены, поэтому вы, очевидно, не можете перетасовывать элементы множеств. Для удаления дубликатов из списка я нашел это: How do I remove repeated elements from ArrayList?.

источник

2013-02-15 10:57:35 qben

С наименьшим количеством кода и наиболее элегантности вы можете сделать что-то вроде:

public void testFoo() { 
    Set<Integer> s = new TreeSet<Integer>(); 

    s.add(2); 
    s.add(1); 
    s.add(3); 

    Collections.shuffle(Arrays.asList(s.toArray())); 
}

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

источник

2013-02-15 10:59:21 comanitza

Вы можете использовать карту, чтобы избежать дубликатов, а затем Map.entrySet() и перетасовать Список_массивов

источник

2013-02-15 11:01:19

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

источник

2013-02-15 11:04:10 gnomie

Collection, без дублей и в случайном порядке в Java

ответ

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