Хабрахабр

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

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

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

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

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

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

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

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

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

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

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

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

При движении вниз необходимо дополнительно пройти по диагонали. Из точки (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). Помимо формирования списка змеек, при прохождении по спискам алгоритмом Майерса создаются списки статусов элементов старого и нового списков.

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

Ссылки 

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть