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

Question

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

 A.removeAll(B)

В соответствии с javadocs, это будет принимать каждую запись A и сравнивать с каждой записью B, и если она найдет обе записи равными, она удалит запись из A. Если запись A не будет найдена равной любая запись в B, и поскольку все учащиеся в A также находятся в 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);
    }
}

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

Answer 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 s до конца.)

---

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

Answer 2

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

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

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

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

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

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

/**
 * 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, new HashSet < C >(B)); выплата одной копии B, если вы действительно не можете накапливаться в Set на этапе выбора.

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

Answer 3

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

Первый подход более читабелен, передает ваше намерение людям, которыеподдерживать код.Также предпочтительнее использовать «проверенный» API, а не заново изобретать колесо (если это не является абсолютно необходимым). Компьютеры стали настолько быстрыми, что мы не должны делать каких-либо преждевременных оптимизаций.решение с использованием Set, похожее на @ aioob's

Answer 4

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

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

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

Например: рассмотрим массив A с 1,2,4,5 и коллекцию 'C 'с 4,1, с которыми мы сопоставляем;желая удалить 4 и 1. вот каждая итерация цикла for, которая будет идти 0 -> 4

итерация: r - индекс цикла for для массива 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, остановка

Сравните значение w с размером резервного массива, равным 4. Поскольку они не равны Обнулите значения от w до конца массива и сбросьте размер.

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

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