🤫 Что общего у UITableView и git diff

Когда-то давно, лет 10 назад (у меня была задача: получать пачку данных с сервера, находить различия с кэшем и красиво обновлять UITableView, чтобы не было резких reload'ов, а всё плавно вставлялось, удалялось и двигалось.
Тогда задача обошлась мне, не в один день анализа и проектирования, чтобы научиться сравнивать старый и новый массивы.

Тогда ещё не было никакого CollectionDifference, и я просто пошёл реализовывать алгоритм Вагнера–Фишера и работать с вычислением: расстояния Левенштейна и редакционноого предписания - минимального количества действий и их последовательности чтобы из "ABC" получилось "ACD".

Ну и конечно, всё это руками прикручивалось к performBatchUpdates:

tableView.performBatchUpdates {     
  tableView.deleteRows(at: ...)     
  tableView.insertRows(at: ...) 
}

Весело? Не очень. Но тогда по-другому никак.

Потом, с приходом iOS 13 и Swift 5.1, всё изменилось.
Apple выкатили DiffableDataSource, и вместе с ним — CollectionDifference.
Это была буквально революция, теперь можно просто сформировать снапшот и отдать его таблице:

var snapshot = NSDiffableDataSourceSnapshot<Section, Item>() 
snapshot.appendSections([.main]) 
snapshot.appendItems(items) 
dataSource.apply(snapshot, animatingDifferences: true)

UITableView сама всё поймёт, сама вычислит, что вставить, что удалить, что переместить — и сделает это с анимацией.
А мы — просто передаём новое состояние.

Если копнуть глубже, то под капотом лежит алгоритм Майерса.
Он также находит минимальную последовательность изменений между двумя массивами.

Apple реализует его для CollectionDifference.
Можно глянуть исходники Swift или вот обьяснение алгоритма.

Но если хочется больше контроля или скорости — есть и альтернативы.
Например, DifferenceKit, который использует алгоритм Пола Хекеля.
Вот сам код.
Он быстрее в ряде кейсов, особенно если много данных, на это влияет сложность O(n), бенчмарки можно посмотреть на gh.
И с ним сделали даже backport - DiffableDataSource для старых iOS.

Мораль истории: задача сравнения последовательностей — стара как мир.
Её решают в UI, в git, в текстовых редакторах.
А теперь и мы — наконец-то — можем делать это в UITableView, не теряя нервы на написание сложных алгоритмов и работу с indexPath-ами.

#L #UITableView #DiffableDataSource #CollectionDifference #LevenshteinDistance

👏