Что более эффективно: используя removeAll() или используя следующий метод HashMap, чтобы сохранить только измененные записи в ArrayList

У меня есть 2 ArrayList A и B той же структуры данных C (hashCode() и равно() переопределено). C представляет собой запись студента. Два списка имеют одинаковый размер и представляют собой новые записи студентов и старые (соответственно, ученики одинаковы в обоих списках, порядок может отличаться). Я хочу сохранить только те записи в A, которые были изменены. Как таковой, я:

 A.removeAll(B)

В соответствии с javadocs это займет каждую запись A и сравнится с каждой записью B, и если она найдет равную, она удалит запись из A. Если запись A не будет найдена равной любая запись в B, и поскольку все ученики в также находятся в B, это означает, что эта запись A изменилась. Проблема в том, что его легко n квадратная сложность.

Другой подход может быть:

Map<C> map = new HashMap<C>();
for (C record : B){
    map.add(record.getStudentId(),record);
}
List<C> changedRecords = new ArrayList<C>();
for (C record : A){
    if (record.equals(map.get(record.getStudentId())){
        changedRecords.add(record);
    }
}

Я думаю, что это может быть более сложной задачей, чем вышеупомянутое решение. Это правильно?

Ответ 1

Да, последний алгоритм лучше, чем O(n^2), так как у вас есть две петли, одна из которых находится выше B, а другая поверх A, и вы выполняете (амортизированную) постоянную работу в каждом цикле, ваше новое решение работает в O(|A| + |B|).

Я подозреваю, что у вас нет дубликатов записей. Если это так, вы также можете перейти через HashSet (изменить на LinkedHashSet, если вы хотите сохранить порядок в A):

HashSet<C> tmp = new HashSet<C>(A);
tmp.removeAll(B);                     // Linear operation
A = new ArrayList<C>(tmp);

(Или если заказ не имеет значения для вас, вы можете использовать HashSet на всем пути.)

Как указано @Daud в комментариях ниже, HashSet.removeAll(Collection c) на самом деле вызывает c.contains несколько раз, если размер хэш-набора меньше, чем сбор, который влияет на сложность (по крайней мере, в OpenJDK). Это связано с тем, что реализация всегда выбирает итерацию по более мелкой коллекции.

Ответ 2

То, что вы можете сэкономить на сложности, которую вы можете потерять при распределении памяти, не обязательно более эффективно. Arrraylist использует что-то похожее на алгоритм разбиения на месте, чтобы запустить массив поддержки и протестировать сравнение.

При сравнении просто ищет индекс первого совпадения с массивом поддержки Object[]. Алгоритм поддерживает два индекса: один для итерации через массив поддержки и один в качестве заполнителя для совпадений. В случае совпадения он просто перемещает указатель на базовый массив и переходит к следующему входящему элементу; это относительно дешево.

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

Например: Рассмотрим arraylist A с 1,2,4,5 и коллекцию "C" с 4,1, с которой мы сравниваем; желая удалить 4 и 1. здесь каждая итерация в цикле for, которая будет идти 0 → 4

Итерация: r - индекс цикла цикла для arraylist a for (; r < size; r++)

r = 0 (содержит ли C 1? Да, перейдите к следующему) A: 1,2,4,5 w = 0

r = 1 (содержит ли C 2? Нет, скопируйте значение в r в пятно, на которое указывает w ++) A: 2,2,4,5 w = 1

r = 2 (содержит ли C 4?, да пропустить) A: 2,2,4,5 w = 1

r = 3 (содержит ли C 5? Нет, скопируйте значение по r в пятно, на которое указывает w ++)

A: 2,5,4,5 w = 2

r = 4, stop

Сравните w с размером массива подложки, который равен 4. Так как они не равны. Уточните значения из w в конец массива и reset размер.

A: 2,5 размер 2

Встроенный removeAll также считает, что ArrayLists может содержать null. Вы можете выбросить NPE в record.getStudentId() в своем решении выше. Наконец, removeAll защищает от исключений в сравнении с Collection.contains. если это произойдет, он использует, наконец, встроенную memcopy, которая очень эффективно защищает массив поддержки от коррупции.

Ответ 3

Определенно второй "алгоритм" лучше, чем первый, учитывая амортизированный анализ. это лучший способ? вам это нужно? это вызовет какое-либо видимое воздействие на пользователя с точки зрения производительности количество элементов в списке растет настолько огромным, что это становится узким местом в системе?

Первый подход более читабельен, передает ваше намерение людям, которые поддерживают код. Также предпочтительно использовать "проверенный" API вместо повторного изобретательства колеса (если это абсолютно необходимо) Компьютеры стали настолько быстрыми, что мы не должны делать никаких преждевременных оптимизаций.

Если я вижу существенным, я мог бы пойти с решением, используя Set, аналогично

Ответ 4

В некоторых случаях я столкнулся с узким местом производительности в элементе removeAll (связанная с моделью моделирования EMF). Для ArrayList, как указано выше, просто используйте стандартный removeAll, но если A - это, например, EList, n ^ 2 может быть встречен.

Следовательно, избегайте полагаться на скрытые хорошие свойства конкретных реализаций List <T> ; Set.contains() O (1) является гарантией, используйте это для связанной алгоритмической сложности.

Я использую следующий код, который позволяет избежать ненужных копий; Намерение заключается в том, что вы сканируете структуру данных, в которой вы находите ненужные элементы, которые вам не нужны, и добавляете их в "todel".

По какой-то причине, например, избегая параллельных изменений, вы перемещаетесь по дереву и т.д.... вы не можете удалять элементы по мере прохождения этого обхода. Итак, мы накапливаем их в HashSet "todel".

В функции нам нужно изменить "контейнер" на месте, поскольку он обычно является атрибутом вызывающего, но использование remove (int index) в "контейнере" может вызвать копию из-за сдвига элементов влево. Для этого мы используем "содержимое" для копирования.

Аргумент шаблона заключается в том, что во время процесса выбора я часто получаю подтипы C, но не стесняйтесь использовать <T> везде.

/**
 * Efficient O (n) operation to removeAll from an aggregation.
 * @param container a container for a set of elements (no duplicates), some of which we want to get rid of
 * @param todel some elements to remove, typically stored in a HashSet.
 */
public static <T> void removeAll ( List<T> container, Set<? extends T> todel ) {
    if (todel.isEmpty())
        return;
    List<T> contents = new ArrayList<T>(container);
    container.clear();
    // since container contains no duplicates ensure |B| max contains() operations
    int torem = todel.size();
    for (T elt : contents) {
        if ( torem==0 || ! todel.contains(elt) ) {
            container.add(elt);
        } else {
            torem--;
        }
    }
}

Итак, в вашем случае вы будете ссылаться на: removeAll (A, новый HashSet <C> (B)); заплатив одну копию B, если вы действительно не можете накопить в Set <C> во время фазы выбора.

Поместите его в класс утилиты и статический импорт для удобства использования.