18.03.2016 21:31
lavelas 4 2500 Источник
Доброй ночи, сообщество.

В текущем проекте, над которым я работаю, возникла необходимость определить изменения в двух коллекциях данных. Если в двух словах, то с Сервера приходит List заказов и в БД лежит такой же List заказов. Нужно определить сколько заказов было добавлено, обновлено и удалено в новой коллекции. Заинтересовавшихся прошу под кат.



Вроде как тривиальная задача скажете Вы и будете правы! Но я не спал уже 3 дня, поэтому изначально мой код получился в 3 цикла. Херня Херня подумал я и начал сначала. Даже код приводить не буду :)

Через полчаса родился класс в 2 цикла — проходимся по новым данным и считаем новые и обновленные, потом проходимся по старым и считаем удаленые. Код тоже приводить не стану, потому что мне сразу захотелось уместить все в один цикл и по совету одной статьи я избавился от только что написанного класса.

Итак, спустя еще 30 минут я написал класс CollectionChangeCouner, алгоритм работы которого на мой взгляд является оптимальным.

Листинг
import java.util.Iterator;
import java.util.List;

/**
 * Created by vitaliy on 18.03.2016.
 *
 */
public class CollectionChangeCouner<T> {
    private int inserted;
    private int updated;
    private int deleted;

    public CollectionChangeCouner(List<T> oldData, List<T> newData) {
        Iterator<T> oldDataIterator = oldData.iterator();
        while (oldDataIterator.hasNext()) {
            T oldItem = oldDataIterator.next();
            int index = newData.indexOf(oldItem);
            if (index < 0) {
                deleted++;
                oldDataIterator.remove();
            } else {
                final T newItem = newData.get(index);
                if (!oldItem.equals(newItem)) {
                    updated++;
                }
                newData.remove(index);
            }
        }
        inserted = newData.size();
    }

    public int inserted() {
        return inserted;
    }

    public int updated() {
        return updated;
    }
    public int deleted() {
        return deleted;
    }

    public boolean hadChangedData() {
        return (inserted > 0)
                || (updated > 0)
                || (deleted > 0);
    }
}



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

P.S. Спите чаще и больше, это полезно!

Комментарии (4)


  1. chabapok
    19.03.2016 02:15
    #8811007

    Оптимальным — по какому параметру? По размеру юзер-кода — наверное, да. Но там у вас используется indexOf по одному из списков, так что вряд ли по времени исполнения (на больших списках).

    Посмотрите, как работает diff. По сути — это решение для вашей задачи. Это если строки в списках не перемешаны. Если перемешаны, то нужны конечно дополнительные финты ушами.


  1. grossws
    19.03.2016 02:25
    #8811015
    +11

    Страх и ужас:

    • модификация входных данных (oldData, newData) — явный code smell;
    • updated = 0 всегда, т. к. если newData.indexOf(oldItem) >= 0, то либо oldItem == null, либо oldItem.equals(newData.get(index));
    • непонятно зачем нужная нагрузка на GC, если используются ArrayList'ы (засчёт oldDataIterator.remove() и newData.remove(index), а если используется LinkedList — то вообще убиться веником;

    Если списки сортированы, то можно не использовать квадратичный алгоритм (итерация по oldData + List#indexOf), а сделать линейный проход двумя итераторами/по индексам. Если нет, то использовать два HashSet'а:

    Set<T> insertedData = new HashSet<>(newData);
insertedData.removeAll(oldData);
inserted = insertedData.size();

Set<T> removedData = new HashSet<>(oldData);
removedData.removeAll(newData);
removed = removedData.size();


    1. grossws
      19.03.2016 02:28
      #8811017
      +6

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


    1. GoldenStar
      19.03.2016 12:47
      #8811177

      Спасибо за статью и хорошие рецепты в обсуждении. Сам недавно решал подобную задачу на C#. Так и не разобрался с HashSet — сейчас вы прояснили для меня данный вопрос (важен порядок строк, который при клонировании List почему то постоянно изменяется на противоположный). Решил свою задачу просто добавив в класс описываемый шаблоном \<T> свой HashSet, который генерируется автоматически при любом изменении некоторого свойства в исходном классе. Получилось решение которое позволяет менять любое значение исходного List и используя его клонирование находить появившиеся изменения в нем отражая затем их в DataTable. Понимаю теперь, что все можно было сделать используя DataBindings на исходный List (или собрать все на делегатах), но так далеко я не погружался, хотя когда будет время, наверное так и поступлю.