Лучший способ удалить повторы в коллекции на Java?

Question

Это вопрос из двух частей:

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

Это эффективное решение? Было бы лучше / более идиоматично / быстрее зацикливать и удалять повторы? Имеет ли это значение?

Мой второй (связанный) вопрос: каков наилучший способ преобразования массива в набор? Предполагая массив массива, я делал это следующим образом:

Set x = new HashSet(Arrays.asList(arr));

Это преобразует массив в список, а затем в набор. Кажется, что-то вроде кольцевой. Есть ли лучший / более идиоматический / более эффективный способ сделать это, чем способ двойного преобразования?

Спасибо!

Answer 1

1. У вас есть какая-либо информация о коллекции, например, она уже отсортирована или содержит в основном дубликаты или в основном уникальные предметы? С произвольной коллекцией я думаю, что преобразовать ее в Set нормально.

2. Arrays.asList() не создает новый список. На самом деле он просто возвращает List, который использует массив в качестве резервного хранилища, так что это дешевая операция. Итак, ваш способ сделать Set из массива - это то же самое, что и я.

Answer 2

Использовать HashSet стандартный Collection конструктор преобразования . Согласно Учебникам Java :

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

Collection<Type> noDups = new HashSet<Type>(c);

Он работает путем создания набора (который, по определение, не может содержать дубликат), изначально содержащий все элементы в с. Он использует стандартный конструктор преобразования описанный в Коллекции Интерфейс секция.

Вот небольшой вариант этой идиомы это сохраняет порядок оригинальная коллекция при удалении дубликат элемента.

Collection<Type> noDups = new LinkedHashSet<Type>(c);

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

public static <E> Set<E> removeDups(Collection<E> c) {
    return new LinkedHashSet<E>(c);
}

Answer 3

Если вы действительно хотите установить семантику, отличный выбор - создать новый Set из коллекции, содержащей дубликаты. Совершенно ясно, какова цель, он более компактен, чем выполнение цикла самостоятельно, и он оставляет исходную коллекцию нетронутой.

Для создания Set из массива обычно используется промежуточный List. Обертка, возвращаемая Arrays.asList(), легка и эффективна. К сожалению, в ядре Java нет более прямого API для этого.

Answer 4

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

Answer 5

1. Дубликаты

Совпадение других ответов: использование Set должно быть наиболее эффективным способом удаления дубликатов. HashSet должно работать в среднем за O(n) раз. Циклы и удаление повторов будут выполняться в порядке O(n^2). Поэтому в большинстве случаев рекомендуется использовать Set. В некоторых случаях (например, ограниченная память) итерация может иметь смысл.

2. Arrays.asList() - дешевая операция, которая не копирует массив, с минимальными накладными расходами памяти. Вы можете вручную добавить элементы, просматривая массив.

public static  Set arrayToSet(T[] array) {
  Set set = new HashSet(array.length / 2);
  for (T item : array)
    set.add(item);
  return set;
}

Answer 6

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

Если вам неудобно использовать Arrays.asList () по пути в набор, вы можете просто запустить цикл foreach над массивом, чтобы добавить элементы в набор, но я не вижу никакого вреда (для примитивные массивы) в вашем подходе. Arrays.asList () возвращает список, который «поддерживается» исходным массивом, поэтому он не имеет значительных затрат во времени или пространстве.