DiffUtil
DiffUtil is a utility class that calculates the difference between two lists and outputs a list of update operations that converts the first list into the second one.
It can be used to calculate updates for a RecyclerView Adapter. See ListAdapter and AsyncListDiffer which can simplify the use of DiffUtil on a background thread.
DiffUtil uses Eugene W. Myers's difference algorithm to calculate the minimal number of updates to convert one list into another. Myers's algorithm does not handle items that are moved so DiffUtil runs a second pass on the result to detect items that were moved.
Note that DiffUtil, ListAdapter, and AsyncListDiffer require the list to not mutate while in use. This generally means that both the lists themselves and their elements (or at least, the properties of elements used in diffing) should not be modified directly. Instead, new lists should be provided any time content changes. It's common for lists passed to DiffUtil to share elements that have not mutated, so it is not strictly required to reload all data to use DiffUtil.
If the lists are large, this operation may take significant time so you are advised to run this on a background thread, get the DiffResult then apply it on the RecyclerView on the main thread.
This algorithm is optimized for space and uses O(N) space to find the minimal number of addition and removal operations between the two lists. It has O(N + D^2) expected time performance where D is the length of the edit script.
If move detection is enabled, it takes an additional O(MN) time where M is the total number of added items and N is the total number of removed items. If your lists are already sorted by the same constraint (e.g. a created timestamp for a list of posts), you can disable move detection to improve performance.
The actual runtime of the algorithm significantly depends on the number of changes in the list and the cost of your comparison methods. Below are some average run times for reference: (The test list is composed of random UUID Strings and the tests are run on Nexus 5X with M)
- 100 items and 10 modifications: avg: 0.39 ms, median: 0.35 ms
- 100 items and 100 modifications: 3.82 ms, median: 3.75 ms
- 100 items and 100 modifications without moves: 2.09 ms, median: 2.06 ms
- 1000 items and 50 modifications: avg: 4.67 ms, median: 4.59 ms
- 1000 items and 50 modifications without moves: avg: 3.59 ms, median: 3.50 ms
- 1000 items and 200 modifications: 27.07 ms, median: 26.92 ms
- 1000 items and 200 modifications without moves: 13.54 ms, median: 13.36 ms
Due to implementation constraints, the max size of the list can be 2^26.