August 28, 2019

Разоблачаем магию DiffUtil

Каждый Android-разработчик использовал RecyclerView для отображения списков и каждый сталкивался с проблемой обновления данных в списке, пока в 2016 году не появился магический класс DiffUtil. Я на пальцах объясню, как на самом деле он работает, и постараюсь рассеять его магию.

Немного истории

Одним из самых распространённых элементов в мобильных приложениях является список, в нашем случае RecyclerView. Это могут быть списки чего угодно: адреса офисов, списки друзей в соц. сетях, история заказов в приложениях такси и т.д. Все эти кейсы объединяет необходимость постоянно менять данные в списке на новые, когда, например, пользователь сделал Swipe to refresh, отфильтровал список или каким-либо другим способом получил пачку новых данных с бека.

Для реализации такого поведения предок современного Android-разработчика вручную выбирал, какие данные и каким образом изменились, и вызывал соответствующие методы у RecyclerView. Однако всё изменилось, когда Google выпустил Support Library версии 25.1.0, добавив туда DiffUtil, который позволял волшебным образом преобразовывать старый список в новый без полной пересборки RecyclerView. В этой статье я развею волшебство DiffUtil и объясню, как именно он работает.

Как работать с DiffUtil?

Для работы с DiffUtil необходимо реализовать DiffUtil.Callback, вызвать метод calculateDiff(Callback) и применить к RecyclerView полученный DiffResult методом dispatchUpdatesTo(). Что же происходит при вызове метода calucalteDiff(Callback)? Данный метод возвращает DiffResult, который содержит набор операций для преобразования изначального списка в новый. Обновления применяются вызовами методов notifyItemRangeInserted, notifyItemRangeRemoved, notifyItemMoved и notifyItemRangeChanged. Первые три метода меняют структуру списка, а именно позиции у элементов, при этом не меняя сами элементы и не вызывая у них onBindViewHolder() (за исключением добавляемого элемента). Последний меняет сам элемент и вызывает onBindViewHolder() для изменения вьюхи элемента.

DiffUtil проверяет два списка на различия, используя алгоритм Майерса, который определяет только наличие/отсутствие изменений, но не умеет находить перемещения элементов. Для этого DiffUtil проходится по созданным алгоритмом Майерса змейкам (об этом дальше), а затем ищет перемещения. DiffResult формируется за

если алгоритм не проверяет перемещения элементов и

где P – количество добавленных и удалённых элементов.

Алгоритм Майерса

Далее будет рассмотрено объяснение алгоритма Майерса на пальцах, ссылки на математические объяснения алгоритма (а также другие крутые статьи по теме) будут в конце статьи. Рассмотрим две последовательности: BACAAC и CBCBAB. Необходимо написать последовательность преобразований над первой последовательностью, после которых получим вторую. Выпишем последовательности в таблицу следующим образом: старый список будет обозначать первые элементы столбцов, а новый список первые элементы строк.

Перечеркнём ячейки, в которых пересекаются одинаковые элементы обоих последовательностей:

Дальнейшая задача состоит в том, чтобы дойти из левого верхнего угла матрицы в правый нижний угол за наименьшее количество шагов. Двигаться можно по горизонтальным и вертикальным граням. Если попали в точку, откуда начинается диагональная линия, то обязаны двигаться по ней, однако стоимость такого шага – 0. Соответственно стоимость шага по граням – 1.

Из точки (0;0) можем двигаться вправо и вниз. При движении вниз необходимо дополнительно пройти по диагонали. Движение, совершаемое за один шаг, называется змейкой, в данном случае получили 2 змейки: (0; 0) -> (0; 1) и (0; 0) -> (1; 2). Стрелкой обозначается конец змейки, т.е. если после шага по вертикали/горизонтали идёт обязательный шаг по диагонали, то стрелка будет на шаге по диагонали. Ниже показано полное построение змеек из начальной точки в конечную. Некоторые пути на видео были опущены, т.к. были заведомо не самыми короткими.

В итоге получим несколько возможных кратчайших путей, ниже отображены некоторые из них.

Как прохождение матрицы из крайнего левого угла в крайний правый поможет определить последовательность действий (скрипт) для преобразования одной последовательности в другую? Что значат шаги по горизонтали, вертикали и диагонали? Шаг по матрице в одном из возможных направлений – это действия над старой строкой:

  • Шаг по горизонтали – удаление из старой строки
  • Шаг по вертикали – добавление в старую строку
  • Шаг по диагонали – без изменений

На примере второго пути сопоставим путь и получаемый скрипт. Первый шаг – по вертикали, значит добавляем на 0 позицию в старую строку символ «С».

Однако это ещё не вся змейка. Далее мы обязаны двигаться по диагонали. При движении по диагонали элемент B остаётся неизменным. В итоге змейка состоит из движения по вертикали + движение по диагонали.

Далее змейка по горизонтали – убираем из старой строки элемент A.

На гифке ниже приведён весь путь из начала в конец с изменением исходной строки, пока она не преобразуется в конечную.

Результатом работы алгоритма Майерса является скрипт с набором минимального количества действий, которые надо сделать для преобразования одной последовательности в другую. В DiffUtil алгоритм Майерса используется для поиска разных элементов, которые определяются методом areItemsTheSame(). Помимо формирования списка змеек, при прохождении по спискам алгоритмом Майерса создаются списки статусов элементов старого и нового списков. Все эти данные, а также флаг detectMoves и реализованный пользователем callback передаются в конструктор DiffResult(Callback callback, List<Snake> snakes, int[] oldItemStatuses, int[] newItemStatuses, boolean detectMoves).

Пока я писал эту статью, удалось раскопать, что именно происходит в DiffResult: алгоритм проходится по змейкам и выставляет элементам флаги (в списки статусов), по которым определяется, что именно произошло с элементом. По этим флагам во время применения изменений к RecyclerView определяется, каким методом применять обновления: notifyItemRangeInserted, notifyItemRangeRemoved, notifyItemMoved и notifyItemRangeChanged. Более подробно я расскажу об этом в следующий раз.

Ссылки

Источник: Разоблачаем магию DiffUtil