Любой кто сталкивался с разработкой на платформе Android, вполне скоро встречает задачу реализации отображения какого-либо списка, например список продуктов в приложении магазина. Самым распространённым виджетом для этой задачи является RecyclerView.
До конца 2016 года, программист вызывал методы показывающие, где и как поменялись данные в его списке, либо проводил обновление всего списка, что не всегда являлось эффективным решением. Несколько примеров таких методов:
- adapter.notifyItemRangeInserted(rangeStart, rangeEnd);
- adapter.notifyItemRemoved(position);
- adapter.notifyItemChanged(position);
- adapter.notifyItemInserted(position);
- adapter.notifyDataSetChanged();
- adapter.notifyItemMoved(fromPosition, toPosition);
На замен такому неудобному и рутинному методу, Google выпустив очередное обновление для Support Library добавили DiffUtil.
DiffUtil это вспомогательный класс, который помогает посчитать различие между двумя списками и на выходе отдать список операций, для того чтобы перевести первый список во второй. Он начал использоваться для обновления RecyclerView адаптеров.
Большую часть ситуаций, наш лист меняется полностью и мы его заменяем в адаптере, после этого мы вызываем notifyDataSetChanged, этот метод является тяжелым для обработки системой. DiffUtil же решает эту проблему (хоть и частично, иногда будет выгоднее вызвать notify вручную, например если у нас нет дополнительных затрат на вычисление позиции измененной позиции листа).
DiffUtil.Callback это абстрактный класс с 4 абстрактными методами и 1 неабстракным.
getOldListSize() : Возвращает размерность старого списка
getNewListSize() : Возвращает размерность нового списка
areItemsTheSame(int oldItemPosition, int newItemPosition) : Вызывается для выяснения, представляют ли объекты одну и ту же модель. Например, если в моделях есть id, то проверка id моделей из двух списков происходит именно здесь.
areContentsTheSame(int oldItemPosition, int newItemPosition) : Вызывается когда areItemsTheSame возвращает True. Проверяет, являются ли модели одинаковыми с точки зрения данных (логика может меняться в зависимости от требования UI).
getChangePayload(int oldItemPosition, int newItemPosition) : Если areItemTheSame возвращает true, а areContentsTheSame возвращает false, DiffUtil вызывает этот метод чтобы получить дополнительную информацию об изменениях. Иногда бывает полезно свойство, что если здесь вернуть только определенное изменённое поле, то ItemAnimator корректно проведёт анимацию и не будет перерисовывать всю ячейку.
А дальше всё просто ! С помощью calculateDiff, получаем DiffResult и вызывая метод полученного результата dispathUpdatesTo применяем к адаптеру изменения. Сам DiffResult представляет собой последовательность простых операций удаления/изменения/добавления/перемещения описанных в начале статьи. Остаётся один вопрос, каким образом он получает эту последовательность и так же интересна её алгоритмическая сложность. Это и будем рассматривать дальше в статье.
DiffUtil под собой использует алгоритм Майерса. Этот алгоритм определяет наличие/отсутствие изменений, но в нём отсутствует возможность находить перемещения элементов. Поэтому DiffUtil используя результаты алгоритма Майерса дополнительно ищет перемещения. Без нахождения перемещений сложность алгоритма составляет O(N+D^2), в обратном случае O(N+D^2)+O(P^2), где P - количество добавленных и удалённых элементов.
Рассмотрим на примере работу алгоритма Майерса. Возьмём две последовательности.
Q1 = C A A B C
Q2 = B A C C A
Построим матрицу с помощью этих двух последовательностей и пронумеруем каждую линию начиная с 0.
На пересечениях с одинаковыми буквами нарисуем диагональную линию. Будем считать данные квадраты "специальными". Попадая на них по пути на каждом шагу алгоритм "проваливается" через эту диагональную линию дальше, не считая данное действие за ход.
Далее итеративно пойдём разными путями, пока один из способов не достигнет конечной точки (5, 5) быстрее чем другой путь.
На данном примере имеется 2 одинаково правильных решения. Теперь с помощью этого решения можно записать последовательность различий, придерживаясь следующих правил:
- Каждый вертикальный ход считается добавлением соответствующего элемента в квадрат, в который мы движемся из «новой» строки (Q2 ). Например, переход от (0,0) к (0,1) указывает на добавление «B» из Q2 .
- Каждый горизонтальный ход считается удалением соответствующего символа из квадрата, в который мы движемся из «старой» строки (Q1) . Например: переход от (2,5) к (3,5) означает удаление «A » из строки Q1 .
- Каждый диагональный ход считается сохранением соответствующего символа в квадрате, к которому мы движемся.
Для каждого из правильных путей запишем последовательность:
Нижняя последовательность:
- (0, 0) -> (0, 1) +B
- (0, 1) -> (0, 2) +A
- (0, 2) -> (1, 3) C
- (1, 3) -> (1, 4) +C
- (1, 4) -> (2, 5) A
- (2, 5) -> (3, 5) -A
- (3, 5) -> (4, 5) -B
- (4, 5) -> (5, 5) -C
Верхняя последовательность:
- (0, 0) -> (1, 0) -C
- (1, 0) -> (2, 0) -A
- (2, 0) -> (2, 1) +B
- (2, 1) -> (3, 2) A
- (3, 2) -> (4, 2) -B
- (4, 2) -> (5, 3) C
- (5, 3) -> (5, 4) +C
- (5, 4) -> (5, 5) +A
Как видите в каждой последовательности находится одинаковое количество удалений, добавлений и сохранений. Как итог обе последовательности являются правильными решениями для исходной задачи и мы получили набор действий для преобразования исходной последовательности в новую. В DiffUtil алгоритм Майерса используется для поиска разных элементов, которые определяются методом areItemsTheSame(), не считая еще одного прохода, в котором он выставляет по решению каждому объекту статусы, по котором потом решает каким из изначальных методов notify у адаптера воспользоваться для конкретного объекта.