Table of Contents
- scene introduction
- DiffUtil
- how to use
- code analysis
- ReyclerView.ListAdapter
- Let’s see how to use it first
- Source code analysis
Scene introduction
First introduce MVVM
I believe everyone is already very familiar with
ViewModel is responsible for providing data to View. Usually, we will observe the data changes of ViewModel, and refresh the UI when new data is received.
Usually we might write
//Observe data in the View layer
mViewModel.observeData().observe(activity, Observer { data->
//Submit data to adapter to update UI
adapter. submitList(data)
})
//Write this in Adapter
var mList: List<String>? = null
fun submitList(list: List<String>) {
mList = list
notifyDataSetChanged()
}
Suppose data1 and data2 are like this
val data1 = listOf("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", " P", "Q", "R", "S", "T", "U", "V", "W", "S\ ", "Y", "Z")
val data2 = listOf( "K", "A", "b", "C", "Z", "E", "F", "G ", "H", "I", "J","L", "m","N","P","P" ,"Q","S","T","U","V","W","S","Y",\ "A","C")
The effect is probably like this
We can see that two different data data1, data2 have data movement, change (case change to change), increase, delete
But these changes are not displayed clearly, just a blunt change of view.
What if we want to have corresponding animations for the addition, deletion, and movement of each element?
Probably such an effect
We know that to have the animation effect of adding, deleting, changing and moving, we need to call RecyelerView.Adapter
public final void notifyItemInserted(int position) public final void notifyItemRemoved(int position) public final void notifyItemChanged(int position) public final void notifyItemMoved(int fromPosition, int toPosition)
Then the question turns into how to quickly find out which element has been added, deleted, modified, or moved from data1 and data2
You can spend a little time thinking about this problem, this is actually a very complicated difference problem
but! Fortunately, Google officially provides us with DiffUtil to help us with this operation
Next introduce DiffUtil
DiffUtil
This utility class is based on a paper by Eugene W. Myers, published in the journal “Algorithmica” in November 1986
An O(Nd) difference Algorithm and Its Variations
This is an algorithm with a time complexity of O(N + D^2), where D is the size of two data directly modified,
In the actual data modification, D should not be large, so this efficiency is very high.
(Myers difference algorithm does not implement the operation of moving elements, so it uses O(N^2) time to find moving elements)
how to use
The code in the example we gave above can be modified like this
//Observe data in the View layer
mViewModel.observeData().observe(activity, Observer { data->
val oldList = adapter.mList ?: listOf()
val newList = data
adapter. submitList(newList)
DiffUtil.calculateDiff(object : DiffUtil.Callback() {
override fun getOldListSize() = oldList.size
override fun getNewListSize() = newList.size
override fun areItemsTheSame(oldItemPosition: Int, newItemPosition: Int): Boolean {
// Regardless of case, if equals is the same element
return oldList[oldItemPosition].equals(newList[newItemPosition],true)
}
override fun areContentsTheSame(oldItemPosition: Int, newItemPosition: Int): Boolean {
//If equals, the content is the same
return oldList[oldItemPosition] == newList[newItemPosition]
}
}, false). dispatchUpdatesTo(adapter)
})
//Write this in Adapter
var mList: List<String>? = null
fun submitList(list: List<String>) {
mList = list
}
code analysis
First look at the function calculateDiff
/** * * @param cb This callback mainly provides some functions to allow the scoring algorithm to judge, and then the comparison result can be obtained * @param detectMoves Do you need to detect the movement of the data source? As mentioned above, if you need to detect, it will take an additional O(N^2) time, and N is the sum of deleting and adding elements * * @return The result of data comparison, we can use this result to update the UI */ public static DiffResult calculateDiff(@NonNull Callback cb, boolean detectMoves)
Then look at the first entry
public abstract static class Callback {
/**
* @return the size of the original data
*/
public abstract int getOldListSize();
/**
* @return the size of the new data
*/
public abstract int getNewListSize();
/**
* @param oldItemPosition original data index
* @param newItemPosition new data index
* @return Whether the original data and the new data are the same element, usually we think that the ID is equal to the same element
*/
public abstract boolean areItemsTheSame(int oldItemPosition, int newItemPosition);
/**
* @param oldItemPosition original data index
* @param newItemPosition new data index
* @return Whether the same element has the same content, if the content is different, it will be refreshed, usually we think that the same element value (equals) means the same content,
* Of course, this equals needs to be implemented by yourself
*/
public abstract boolean areContentsTheSame(int oldItemPosition, int newItemPosition);
}
Copy Code
Then see what the return value DiffResult of calculateDiff can do
Looking at the source code, you can find that various data after the Myers differential algorithm are stored in it.
Usually we only need to use these two functions encapsulated inside
//1
public void dispatchUpdatesTo(@NonNull final RecyclerView.Adapter adapter) {
dispatchUpdatesTo(new AdapterListUpdateCallback(adapter));
}
//2
public void dispatchUpdatesTo(@NonNull ListUpdateCallback updateCallback) {
//1 is to automatically call various notify methods of the adapter after parsing the verification results
//2 is to call back the parsed verification result, generally we can use //1
Careful students will find that all our operations are in the main thread, and the Myers difference algorithm uses O(N + D^2) to determine the movement of elements O(N^2)
If there are many matching elements, one hundred or one thousand, wouldn’t it affect the fluency of the application
yes it will
We can see the efficiency of this matching by looking at the DiffUtil annotation
- 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
1000 elements, 200 modifications, plus the case of movement, the time-consuming is 27.07ms, which is almost two frames. On the current 120 Hz mobile phones, more frame rates may be dropped
(However, the test machine is the Nexus 5X released 7 years ago, and the current machines should be much better than this (manual dog head)
So do we need to move this comparison to the child thread?
Eh! Wait, you don’t have to, Google Dad has packaged a ListAdapter for us, which maintains the thread pool and will move the view modification operation to the main thread for us, so that we can use it very conveniently DiffUtil
ReyclerView. ListAdapter
Let’s see how to use it first
Take out the code just now and change it again
//Observe data in the View layer
mViewModel.observeData().observe(activity, Observer { data->
adapter. submitList(data)
})
//Delete this Adapter
var mList: List<String>? = null
fun submitList(list: List<String>) {
mList = list
}
// Change the original inheritance from RecyclerView.Adapter<VH> to ListAdapter<T, VH> and pass in a DiffUtil.ItemCallback<T> to ListAdapter
// T is the data type of the list, here we are String. Can actually be a Model or data class
class MyListAdapter : ListAdapter<String, RecyclerView. ViewHolder>(object : DiffUtil. ItemCallback<String>() {
override fun areItemsTheSame(oldItem: String, newItem: String): Boolean {
return oldItem. equals(newItem, true)
}
override fun areContentsTheSame(oldItem: String, newItem: String): Boolean {
return oldItem == newItem
}
}) {
··········
}
Looking at areItemsTheSame and areContentsTheSame of DiffUtil.ItemCallback is the same as what we just analyzed DiffUtil.CallBack, but this time we don’t need to look for them according to the index Elements, this time directly give us the elements, let us judge.
Source code analysis
//ListAdapter inherits from RecyclerView.Adapter which maintains an AsyncListDiffer
public abstract class ListAdapter<T, VH extends RecyclerView. ViewHolder> extends RecyclerView. Adapter<VH> {
final AsyncListDiffer<T> mDiffer;
//AsyncListDiffer maintains an AsyncDifferConfig and a main thread executor mMainThreadExecutor
public class AsyncListDiffer<T> {
private final ListUpdateCallback mUpdateCallback;
@SuppressWarnings("WeakerAccess") /* synthetic access */
final AsyncDifferConfig<T> mConfig;
Executor mMainThreadExecutor;
//AsyncDifferConfig is passed in when ListAdapter is initialized, mBackgroundThreadExecutor is a thread pool by default, mainly for asynchronous calculation
public final class AsyncDifferConfig<T> {
@Nullable
private final Executor mMainThreadExecutor;
@NonNull
private final Executor mBackgroundThreadExecutor;
@NonNull
private final DiffUtil.ItemCallback<T> mDiffCallback;
Their main duties are as follows
- ListAdapter submits data to AsyncListDiffer, calculates the difference result and then notify
- AsyncListDiffer uses the thread pool of AsyncDifferConfig to perform differential operations based on the submitted data, and then uses the mMainThreadExecutor callback to update ListAdapter
- AsyncDifferConfig Differential sub-thread main thread configuration, the default mBackgroundThreadExecutor is a FixedThreadPool
Let’s take a look at the overall process of ListAdapter.submitList(data)
##ListAdapter
//Give the data to AsyncListDiffer for calculation
public void submitList(@Nullable List<T> list) {
mDiffer. submitList(list);
}
##AsyncListDiffer
//Use DiffUtil to calculate the checking result, and change the data to notify the callback set by ListAdapter
public void submitList(@Nullable final List<T> newList,
@Nullable final Runnable commitCallback) {
······
final List<T> oldList = mList;
// Execute in child thread
mConfig.getBackgroundThreadExecutor().execute(new Runnable() {
@Override
public void run() {
//Call DiffUtil.calculateDiff The method of use is the same as when we introduced DiffUtil
final DiffUtil.DiffResult result = DiffUtil.calculateDiff(new DiffUtil.Callback() {
·······
});
// Execute on the main thread
mMainThreadExecutor. execute(new Runnable() {
@Override
public void run() {
if (mMaxScheduledGeneration == runGeneration) {
//Send the result (DiffResult) to the callback set by ListAdpater
latchList(newList, result, commitCallback);
}
}
});
}
});
}
void latchList(
@NonNull List<T> newList,
@NonNull DiffUtil. DiffResult diffResult,
@Nullable Runnable commitCallback) {
·····
//Are you familiar with this, as I said before, this mUpdateCallback is created when the ListAdapter is initialized
diffResult. dispatchUpdatesTo(mUpdateCallback);
···
}
I believe that everyone has roughly understood the whole process, right? At this point, the explanation of this article is almost over.