DiffUtil和它的差量算法
作者：Reathin
Myers差分算法是一種在每一步選擇中都采取當前狀態(tài)下最優(yōu)決策的算法。在軟件測試中，Myers差分算法使用了差分算法來尋找兩個文本之間的最小差異集合。該算法通過比較兩個文本的不同版本，找出它們之間的差異，并生成一個表示差異的最小集合。
DiffUtil介紹
DiffUtil是Android中的一個實用工具類，用于計算并應用RecyclerView中數(shù)據(jù)集的更改。它可以高效地計算出兩個數(shù)據(jù)集之間的差異，并且只更新發(fā)生變化的部分，從而避免不必要的刷新操作，提高了RecyclerView的性能和流暢度。
DiffUtil的主要作用是在數(shù)據(jù)集發(fā)生變化時，計算出新舊數(shù)據(jù)集之間的差異，并提供給RecyclerView.Adapter進行局部刷新。它通過計算出數(shù)據(jù)集的差異，可以精確地知道哪些項目需要插入、刪除、移動或更新，從而避免了全局刷新，減少了不必要的UI更新操作。
在使用DiffUtil時，需要創(chuàng)建一個繼承自DiffUtil.Callback的類，然后在其中實現(xiàn)兩個方法：getOldListSize()和getNewListSize()用于返回舊數(shù)據(jù)集和新數(shù)據(jù)集的大小，以及areItemsTheSame()和areContentsTheSame()用于判斷兩個對象是否代表同一個item和內(nèi)容是否相同。DiffUtil會根據(jù)這些方法的返回結(jié)果來計算出數(shù)據(jù)集的差異，并提供給RecyclerView.Adapter進行局部刷新。
總的來說，DiffUtil差量算法能夠幫助開發(fā)者高效地處理RecyclerView數(shù)據(jù)集的更新，提升了列表的性能和用戶體驗。
DiffUtil使用
- 創(chuàng)建數(shù)據(jù)類：首先，需要創(chuàng)建一個數(shù)據(jù)類，用于表示RecyclerView中的每個項的數(shù)據(jù)。這個數(shù)據(jù)類需要正確地實現(xiàn)equals()和hashCode()方法，以便DiffUtil能夠正確地比較數(shù)據(jù)項的差異。
- 創(chuàng)建Adapter：接下來，創(chuàng)建一個RecyclerView的Adapter，并在其中實現(xiàn)一個繼承自DiffUtil.Callback的內(nèi)部類，用于計算數(shù)據(jù)集的差異。
- 實現(xiàn)DiffUtil.Callback：在內(nèi)部類中，需要實現(xiàn)DiffUtil.Callback的四個方法：
- areItemsTheSame(oldItemPosition: Int, newItemPosition: Int)：用于判斷兩個項是否代表同一個對象。
- areContentsTheSame(oldItemPosition: Int, newItemPosition: Int)：用于判斷兩個項的內(nèi)容是否相同。
- getOldListSize()：返回舊數(shù)據(jù)集的大小。
- getNewListSize()：返回新數(shù)據(jù)集的大小。
- 計算差異：在Adapter中調(diào)用DiffUtil.calculateDiff()方法，傳入實現(xiàn)了DiffUtil.Callback的內(nèi)部類，并獲取DiffUtil.DiffResult對象。
- 應用差異：最后，調(diào)用DiffUtil.DiffResult對象的dispatchUpdatesTo()方法，將計算出的差異應用到RecyclerView的Adapter上，從而更新列表項。
創(chuàng)建一個繼承自DiffUtil.ItemCallback的類，用于比較兩個數(shù)據(jù)對象是否相同：
public class MyDiffCallback extends DiffUtil.ItemCallback<MyDataModel> {
@Override
public boolean areItemsTheSame(@NonNull MyDataModel oldItem, @NonNull MyDataModel newItem) {
return oldItem.getId() == newItem.getId();
}
@Override
public boolean areContentsTheSame(@NonNull MyDataModel oldItem, @NonNull MyDataModel newItem) {
return oldItem.equals(newItem);
}
}在你的Adapter中使用DiffUtil進行數(shù)據(jù)更新：
public class MyAdapter extends RecyclerView.Adapter<MyAdapter.MyViewHolder> {
private List<MyDataModel> dataList = new ArrayList<>();
// ... 其他方法
public void updateDataList(List<MyDataModel> newDataList) {
DiffUtil.DiffResult diffResult = DiffUtil.calculateDiff(new MyDiffCallback(dataList, newDataList));
dataList.clear();
dataList.addAll(newDataList);
diffResult.dispatchUpdatesTo(this);
}
// ... 其他方法
}MyDiffCallback類用于比較兩個數(shù)據(jù)對象是否相同，然后在Adapter的updateDataList方法中使用DiffUtil.calculateDiff方法計算出數(shù)據(jù)變化，并通過dispatchUpdatesTo方法應用到RecyclerView上。
當你調(diào)用updateDataList方法更新數(shù)據(jù)時，DiffUtil會幫你計算出數(shù)據(jù)的變化，并只更新發(fā)生變化的部分，而不是整個列表都進行刷新，從而提升了性能。
DiffUtil差量算法
DiffUtil中的Myers算法是一種用于比較兩個序列差異的算法。它通常用于RecyclerView的數(shù)據(jù)更新中，以便有效地計算出兩個列表之間的差異，并且只更新發(fā)生變化的部分。
Myers算法的核心思想是將兩個序列的比較轉(zhuǎn)化為一個圖形化的問題，然后通過動態(tài)規(guī)劃的方式來找到最小的編輯路徑，從而確定兩個序列之間的差異。
在DiffUtil中，Myers算法被用于計算出兩個列表之間的差異，并生成用于更新RecyclerView的操作指令，比如插入、刪除、移動等操作，以便實現(xiàn)高效的列表更新。
public class MyDiffUtilCallback extends DiffUtil.Callback {
private List<MyItem> oldList;
private List<MyItem> newList;
public MyDiffUtilCallback(List<MyItem> oldList, List<MyItem> newList) {
this.oldList = oldList;
this.newList = newList;
}
@Override
public int getOldListSize() {
return oldList.size();
}
@Override
public int getNewListSize() {
return newList.size();
}
@Override
public boolean areItemsTheSame(int oldItemPosition, int newItemPosition) {
return oldList.get(oldItemPosition).getId() == newList.get(newItemPosition).getId();
}
@Override
public boolean areContentsTheSame(int oldItemPosition, int newItemPosition) {
MyItem oldItem = oldList.get(oldItemPosition);
MyItem newItem = newList.get(newItemPosition);
return oldItem.equals(newItem);
}
@Nullable
@Override
public Object getChangePayload(int oldItemPosition, int newItemPosition) {
// 如果areContentsTheSame返回false，則可以在這里返回具體的變化內(nèi)容，以便進行局部刷新
return super.getChangePayload(oldItemPosition, newItemPosition);
}
}- getOldListSize()和getNewListSize()方法用于返回舊數(shù)據(jù)集和新數(shù)據(jù)集的大小。
- areItemsTheSame()方法用于判斷兩個item是否代表同一個對象，通?？梢愿鶕?jù)對象的唯一標識來判斷。
- areContentsTheSame()方法用于判斷兩個item的內(nèi)容是否相同，通?？梢愿鶕?jù)對象的內(nèi)容來判斷。
- getChangePayload()方法用于返回具體的變化內(nèi)容，以便進行局部刷新。
DiffUtil差量算法實現(xiàn):
public class DiffUtil {
//部分代碼省略
@NonNull
public static DiffResult calculateDiff(@NonNull Callback cb, boolean detectMoves) {
final int oldSize = cb.getOldListSize();
final int newSize = cb.getNewListSize();
final List<Snake> snakes = new ArrayList<>();
// instead of a recursive implementation, we keep our own stack to avoid potential stack
// overflow exceptions
final List<Range> stack = new ArrayList<>();
stack.add(new Range(0, oldSize, 0, newSize));
final int max = oldSize + newSize + Math.abs(oldSize - newSize);
// allocate forward and backward k-lines. K lines are diagonal lines in the matrix. (see the
// paper for details)
// These arrays lines keep the max reachable position for each k-line.
final int[] forward = new int[max * 2];
final int[] backward = new int[max * 2];
// We pool the ranges to avoid allocations for each recursive call.
final List<Range> rangePool = new ArrayList<>();
while (!stack.isEmpty()) {
final Range range = stack.remove(stack.size() - 1);
final Snake snake = diffPartial(cb, range.oldListStart, range.oldListEnd,
range.newListStart, range.newListEnd, forward, backward, max);
if (snake != null) {
if (snake.size > 0) {
snakes.add(snake);
}
// offset the snake to convert its coordinates from the Range's area to global
//使路徑點的偏移以將其坐標從范圍區(qū)域轉(zhuǎn)換為全局
snake.x += range.oldListStart;
snake.y += range.newListStart;
//拆分左上角和右下角進行遞歸
// add new ranges for left and right
final Range left = rangePool.isEmpty() ? new Range() : rangePool.remove(
rangePool.size() - 1);
//起點為上一次的起點
left.oldListStart = range.oldListStart;
left.newListStart = range.newListStart;
//如果是逆向得到的中間路徑，那么左上角的終點為該中間路徑的起點
if (snake.reverse) {
left.oldListEnd = snake.x;
left.newListEnd = snake.y;
} else {
if (snake.removal) {//中間路徑是向右操作，那么終點的x需要退一
left.oldListEnd = snake.x - 1;
left.newListEnd = snake.y;
} else {//中間路徑是向下操作，那么終點的y需要退一
left.oldListEnd = snake.x;
left.newListEnd = snake.y - 1;
}
}
stack.add(left);
// re-use range for right
//noinspection UnnecessaryLocalVariable
final Range right = range;//右下角終點和之前的終點相同
if (snake.reverse) {
if (snake.removal) {//中間路徑是向右操作，那么起點的x需要進一
right.oldListStart = snake.x + snake.size + 1;
right.newListStart = snake.y + snake.size;
} else {//中間路徑是向下操作，那么起點的y需要進一
right.oldListStart = snake.x + snake.size;
right.newListStart = snake.y + snake.size + 1;
}
} else {//如果是逆向得到的中間路徑，那么右下角的起點為該中間路徑的終點
right.oldListStart = snake.x + snake.size;
right.newListStart = snake.y + snake.size;
}
stack.add(right);
} else {
rangePool.add(range);
}
}
// sort snakes
Collections.sort(snakes, SNAKE_COMPARATOR);
return new DiffResult(cb, snakes, forward, backward, detectMoves);
}
//diffPartial方法主要是來尋找一條snake，它的核心也就是Myers算法。
private static Snake diffPartial(Callback cb, int startOld, int endOld,
int startNew, int endNew, int[] forward, int[] backward, int kOffset) {
final int oldSize = endOld - startOld;
final int newSize = endNew - startNew;
if (endOld - startOld < 1 || endNew - startNew < 1) {
return null;
}
//差異增量
final int delta = oldSize - newSize;
//最雙向最長路徑
final int dLimit = (oldSize + newSize + 1) / 2;
//進行初始化設置
Arrays.fill(forward, kOffset - dLimit - 1, kOffset + dLimit + 1, 0);
Arrays.fill(backward, kOffset - dLimit - 1 + delta, kOffset + dLimit + 1 + delta, oldSize);
/**
* 差異量為奇數(shù)
* 每個差異-水平刪除或垂直插入-都是從一千行移到其相鄰行。
* 由于增量是正向和反向算法中心之間的差異，因此我們知道需要檢查中間snack的d值。
* 對于奇數(shù)增量，我們必須尋找差異為d的前向路徑與差異為d-1的反向路徑重疊。
* 類似地，對于偶數(shù)增量，重疊將是當正向和反向路徑具有相同數(shù)量的差異時
*/
final boolean checkInFwd = delta % 2 != 0;
for (int d = 0; d <= dLimit; d++) {
/**
* 這一循環(huán)是從(0,0)出發(fā)找到移動d步能達到的最遠點
* 引理：d和k同奇同偶，所以每次k都遞增2
*/
for (int k = -d; k <= d; k += 2) {
// find forward path
// we can reach k from k - 1 or k + 1. Check which one is further in the graph
//找到前進路徑
//我們可以從k-1或k + 1到達k。檢查圖中的哪個更遠
int x;
final boolean removal;//向下
//bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
if (k == -d || (k != d && forward[kOffset + k - 1] < forward[kOffset + k + 1])) {
x = forward[kOffset + k + 1];
removal = false;
} else {
x = forward[kOffset + k - 1] + 1;
removal = true;
}
// set y based on x
//k = x - y
int y = x - k;
// move diagonal as long as items match
//只要item匹配就移動對角線
while (x < oldSize && y < newSize
&& cb.areItemsTheSame(startOld + x, startNew + y)) {
x++;
y++;
}
forward[kOffset + k] = x;
//如果delta為奇數(shù)，那么相連通的節(jié)點一定是向前移動的節(jié)點，也就是執(zhí)行forward操作所觸發(fā)的節(jié)點
//if delta is odd and ( k >= delta - ( d - 1 ) and k <= delta + ( d - 1 ) )
if (checkInFwd && k >= delta - d + 1 && k <= delta + d - 1) {
//if overlap with reverse[ d - 1 ] on line k
//forward'x >= backward'x，如果在k線上正向查找能到到的位置的x坐標比反向查找達到的y坐標小
if (forward[kOffset + k] >= backward[kOffset + k]) {
Snake outSnake = new Snake();
outSnake.x = backward[kOffset + k];
outSnake.y = outSnake.x - k;
outSnake.size = forward[kOffset + k] - backward[kOffset + k];
outSnake.removal = removal;
outSnake.reverse = false;
return outSnake;
}
}
}
/**
* 這一循環(huán)是從(m,n)出發(fā)找到移動d步能達到的最遠點
*/
for (int k = -d; k <= d; k += 2) {
// find reverse path at k + delta, in reverse
//以k + delta,找到反向路徑。backwardK相當于反向轉(zhuǎn)化之后的正向的k
final int backwardK = k + delta;
int x;
final boolean removal;
//與k線類似
//bool down = ( k == -d || ( k != d && V[ k - 1 ] < V[ k + 1 ] ) );
if (backwardK == d + delta || (backwardK != -d + delta
&& backward[kOffset + backwardK - 1] < backward[kOffset + backwardK + 1])) {
x = backward[kOffset + backwardK - 1];
removal = false;
} else {
x = backward[kOffset + backwardK + 1] - 1;
removal = true;
}
// set y based on x
int y = x - backwardK;
// move diagonal as long as items match
//只要item匹配就移動對角線
while (x > 0 && y > 0
&& cb.areItemsTheSame(startOld + x - 1, startNew + y - 1)) {
x--;
y--;
}
backward[kOffset + backwardK] = x;
//如果delta為偶數(shù)，那么相連通的節(jié)點一定是反向移動的節(jié)點，也就是執(zhí)行backward操作所觸發(fā)的節(jié)點
//if delta is even and ( k >= -d - delta and k <= d - delta )
if (!checkInFwd && k + delta >= -d && k + delta <= d) {
//if overlap with forward[ d ] on line k
//forward'x >= backward'x，判斷正向反向是否連通了
if (forward[kOffset + backwardK] >= backward[kOffset + backwardK]) {
Snake outSnake = new Snake();
outSnake.x = backward[kOffset + backwardK];
outSnake.y = outSnake.x - backwardK;
outSnake.size =
forward[kOffset + backwardK] - backward[kOffset + backwardK];
outSnake.removal = removal;
outSnake.reverse = true;
return outSnake;
}
}
}
}
throw new IllegalStateException("DiffUtil hit an unexpected case while trying to calculate"
+ " the optimal path. Please make sure your data is not changing during the"
+ " diff calculation.");
}
//部分代碼省略
}Myers差分算法是一種在每一步選擇中都采取當前狀態(tài)下最優(yōu)決策的算法。在軟件測試中，Myers差分算法使用了差分算法來尋找兩個文本之間的最小差異集合。該算法通過比較兩個文本的不同版本，找出它們之間的差異，并生成一個表示差異的最小集合。
Myers差分算法會盡可能地選擇最長的公共子序列，以便最小化差異集合的大小。這種方法在實際應用中通常能夠產(chǎn)生較好的結(jié)果，盡管并不一定能夠找到最優(yōu)解。
責任編輯：武曉燕
來源：
沐雨花飛蝶
