Understanding Diff Algorithms and Batch Updates in UICollectionView (iOS)

In computer science, the concept of Diff is widely used in many scenarios such as React rendering, Git version comparison, and Tencent Tinker hot‑fix patches. This series uses UICollectionView as an example, together with open‑source libraries like IGListKit and DeepDiff, to discuss the application and implementation principles of diff algorithms in iOS.

Partial Reload in UICollectionView

UICollectionView provides four APIs for partial updates: insertItems , deleteItems , reloadItems , and moveItem . The basic usage of each operation is shown below.

var items = ["iOS", "Weekly", "Damonwong"]
items.append(contentsOf: ["Diff", "UICollectionView"])
let indexPaths = Array(3...4).map { IndexPath(item: $0, section: 0) }
collectionView.insertItems(at: indexPaths)

var items = ["iOS", "Weekly", "Damonwong", "Diff", "UICollectionView"]
items.removeLast()
items.removeLast()
let indexPaths = Array(3...4).map { IndexPath(item: $0, section: 0) }
collectionView.deleteItems(at: indexPaths)

var items = ["iOS", "Weekly", "Damonwong"]
items[2] = "OldDriver"
let indexPath = IndexPath(item: 2, section: 0)
collectionView.reloadItems(at: [indexPath])

var items = ["iOS", "Weekly", "Damonwong"]
items.remove(at: 1)
items.append("Weekly")
collectionView.moveItem(at: IndexPath(item: 1, section: 0), to: IndexPath(item: 2, section: 0))

In practice, these operations often need to be combined, and misuse can lead to runtime errors such as "Invalid update: invalid number of items in section 0". The recommended approach is to use performBatchUpdates , which processes deletions before insertions and requires correct index paths.

var items = ["a", "b", "c", "d", "e", "f"]
items.append(contentsOf: ["g", "h", "i"])
items.removeFirst()
items.removeFirst()
items.removeFirst()
collectionView.performBatchUpdates({
    let deleteIndexPaths = Array(0...2).map { IndexPath(item: $0, section: 0) }
    collectionView.deleteItems(at: deleteIndexPaths)
    let insertIndexPaths = Array(3...5).map { IndexPath(item: $0, section: 0) }
    collectionView.insertItems(at: insertIndexPaths)
}, completion: nil)

Edit Path

When the data source changes from an Old state to a New state, the series of insert, delete, reload and move operations constitute an edit path . For example, transforming "Wong" into "VVong" requires deleting the first character "W" and inserting two "V" characters at the first position.

Wagner–Fischer Algorithm

The Wagner–Fischer algorithm computes the optimal edit path (minimum number of insertions, deletions, and substitutions) using dynamic programming. It builds a matrix where vertical moves represent deletions and horizontal moves represent insertions; each cell is filled based on the minimum cost among deletion, insertion, and substitution.

Dynamic Programming

Dynamic programming solves complex problems by breaking them into simpler sub‑problems. For the transformation "wong" → "vvong", the algorithm recursively solves smaller sub‑problems such as "won" → "vvon" and combines the results to obtain the optimal sequence of edit steps.

Computing the Minimum Edit Path

The matrix is initialized with base cases (empty‑to‑string and string‑to‑empty). Each cell is then filled according to the following rules:

If the characters differ, choose the minimum among (deletion + 1), (insertion + 1), and (substitution + 1).

If the characters are the same, inherit the value from the diagonal cell.

Illustrative matrix images (omitted) show how the algorithm selects the optimal path, ultimately yielding the minimal edit sequence.

Code Implementation

/// A single edit step.
public enum EditStep
{
    case insert(location: Int, value: Value)
    case substitute(location: Int, value: Value)
    case delete(location: Int)
    
    public var location: Int {
        switch self {
        case .insert(let location, _): return location
        case .substitute(let location, _): return location
        case .delete(let location): return location
        }
    }
}

extension EditStep: CustomDebugStringConvertible {
    public var debugDescription: String {
        switch self {
        case .insert(let index, let value):
            return "Insert(\(index), \(value))"
        case .substitute(let index, let value):
            return "Substitute(\(index), \(value))"
        case .delete(let index):
            return "Delete(\(index))"
        }
    }
}

public func editSteps
(_ source: [T], _ destination: [T], compare: (T, T) -> Bool) -> [EditStep
] {
    // Return all insertions if the source is empty.
    if source.isEmpty {
        return destination.enumerated().map(EditStep.insert)
    }
    // Return all deletions if the destination is empty.
    if destination.isEmpty {
        return (0..
]>(rows: source.count + 1, columns: destination.count + 1, repeatedValue: [])
    for i in 1...source.count {
        matrix[i, 0] = (0...i).map(EditStep.delete)
    }
    for j in 1...destination.count {
        matrix[0, j] = (1...j).map { EditStep.insert(location: $0 - 1, value: destination[$0 - 1]) }
    }
    for i in 1...source.count {
        for j in 1...destination.count {
            let destValue = destination[j - 1]
            if compare(source[i - 1], destValue) {
                matrix[i, j] = matrix[i - 1, j - 1]
            } else {
                let delete = matrix[i - 1, j] + [EditStep.delete(location: i - 1)]
                let insert = matrix[i, j - 1] + [EditStep.insert(location: j - 1, value: destValue)]
                let substitute = matrix[i - 1, j - 1] + [EditStep.substitute(location: j - 1, value: destValue)]
                matrix[i, j] = shortest(delete, insert, substitute)
            }
        }
    }
    return matrix[source.count, destination.count]
}

Advantages and Limitations

Because it uses dynamic programming, the algorithm always finds an optimal edit path, but its time complexity is O(m·n), which can be prohibitive for large data sets. A linear‑time diff algorithm will be discussed in the next article, based on IGListKit’s implementation.

References

Diff – https://en.wikipedia.org/wiki/Diff

Wagner–Fischer algorithm – https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm