DiffUtil和它的差量算法

DiffUtil介绍

DiffUtil是Android中的一个实用工具类，用于计算并应用RecyclerView中数据集的更改。它可以高效地计算出两个数据集之间的差异，并且只更新发生变化的部分，从而避免不必要的刷新操作，提高了RecyclerView的性能和流畅度。pJh28资讯网——每日最新资讯28at.com

DiffUtil的主要作用是在数据集发生变化时，计算出新旧数据集之间的差异，并提供给RecyclerView.Adapter进行局部刷新。它通过计算出数据集的差异，可以精确地知道哪些项目需要插入、删除、移动或更新，从而避免了全局刷新，减少了不必要的UI更新操作。pJh28资讯网——每日最新资讯28at.com

在使用DiffUtil时，需要创建一个继承自DiffUtil.Callback的类，然后在其中实现两个方法：getOldListSize()和getNewListSize()用于返回旧数据集和新数据集的大小，以及areItemsTheSame()和areContentsTheSame()用于判断两个对象是否代表同一个item和内容是否相同。DiffUtil会根据这些方法的返回结果来计算出数据集的差异，并提供给RecyclerView.Adapter进行局部刷新。pJh28资讯网——每日最新资讯28at.com

总的来说，DiffUtil差量算法能够帮助开发者高效地处理RecyclerView数据集的更新，提升了列表的性能和用户体验。pJh28资讯网——每日最新资讯28at.com

DiffUtil使用

1. 创建数据类：首先，需要创建一个数据类，用于表示RecyclerView中的每个项的数据。这个数据类需要正确地实现equals()和hashCode()方法，以便DiffUtil能够正确地比较数据项的差异。
2. 创建Adapter：接下来，创建一个RecyclerView的Adapter，并在其中实现一个继承自DiffUtil.Callback的内部类，用于计算数据集的差异。
3. 实现DiffUtil.Callback：在内部类中，需要实现DiffUtil.Callback的四个方法：

• areItemsTheSame(oldItemPosition: Int, newItemPosition: Int)：用于判断两个项是否代表同一个对象。
• areContentsTheSame(oldItemPosition: Int, newItemPosition: Int)：用于判断两个项的内容是否相同。
• getOldListSize()：返回旧数据集的大小。
• getNewListSize()：返回新数据集的大小。

4. 计算差异：在Adapter中调用DiffUtil.calculateDiff()方法，传入实现了DiffUtil.Callback的内部类，并获取DiffUtil.DiffResult对象。
5. 应用差异：最后，调用DiffUtil.DiffResult对象的dispatchUpdatesTo()方法，将计算出的差异应用到RecyclerView的Adapter上，从而更新列表项。

创建一个继承自DiffUtil.ItemCallback的类，用于比较两个数据对象是否相同：pJh28资讯网——每日最新资讯28at.com

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进行数据更新：pJh28资讯网——每日最新资讯28at.com

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类用于比较两个数据对象是否相同，然后在Adapter的updateDataList方法中使用DiffUtil.calculateDiff方法计算出数据变化，并通过dispatchUpdatesTo方法应用到RecyclerView上。pJh28资讯网——每日最新资讯28at.com

当你调用updateDataList方法更新数据时，DiffUtil会帮你计算出数据的变化，并只更新发生变化的部分，而不是整个列表都进行刷新，从而提升了性能。pJh28资讯网——每日最新资讯28at.com

DiffUtil差量算法

DiffUtil中的Myers算法是一种用于比较两个序列差异的算法。它通常用于RecyclerView的数据更新中，以便有效地计算出两个列表之间的差异，并且只更新发生变化的部分。pJh28资讯网——每日最新资讯28at.com

Myers算法的核心思想是将两个序列的比较转化为一个图形化的问题，然后通过动态规划的方式来找到最小的编辑路径，从而确定两个序列之间的差异。pJh28资讯网——每日最新资讯28at.com

在DiffUtil中，Myers算法被用于计算出两个列表之间的差异，并生成用于更新RecyclerView的操作指令，比如插入、删除、移动等操作，以便实现高效的列表更新。pJh28资讯网——每日最新资讯28at.com

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，则可以在这里返回具体的变化内容，以便进行局部刷新        return super.getChangePayload(oldItemPosition, newItemPosition);    }}

1. getOldListSize()和getNewListSize()方法用于返回旧数据集和新数据集的大小。
2. areItemsTheSame()方法用于判断两个item是否代表同一个对象，通常可以根据对象的唯一标识来判断。
3. areContentsTheSame()方法用于判断两个item的内容是否相同，通常可以根据对象的内容来判断。
4. getChangePayload()方法用于返回具体的变化内容，以便进行局部刷新。

DiffUtil差量算法实现:pJh28资讯网——每日最新资讯28at.com

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                //使路径点的偏移以将其坐标从范围区域转换为全局                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);        /**         * 差异量为奇数         * 每个差异-水平删除或垂直插入-都是从一千行移到其相邻行。         * 由于增量是正向和反向算法中心之间的差异，因此我们知道需要检查中间snack的d值。         * 对于奇数增量，我们必须寻找差异为d的前向路径与差异为d-1的反向路径重叠。         * 类似地，对于偶数增量，重叠将是当正向和反向路径具有相同数量的差异时         */        final boolean checkInFwd = delta % 2 != 0;        for (int d = 0; d <= dLimit; d++) {            /**             * 这一循环是从(0,0)出发找到移动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为奇数，那么相连通的节点一定是向前移动的节点，也就是执行forward操作所触发的节点                //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;                    }                }            }            /**             * 这一循环是从(m,n)出发找到移动d步能达到的最远点             */            for (int k = -d; k <= d; k += 2) {                // find reverse path at k + delta, in reverse                //以k + delta,找到反向路径。backwardK相当于反向转化之后的正向的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为偶数，那么相连通的节点一定是反向移动的节点，也就是执行backward操作所触发的节点                //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差分算法是一种在每一步选择中都采取当前状态下最优决策的算法。在软件测试中，Myers差分算法使用了差分算法来寻找两个文本之间的最小差异集合。该算法通过比较两个文本的不同版本，找出它们之间的差异，并生成一个表示差异的最小集合。pJh28资讯网——每日最新资讯28at.com

Myers差分算法会尽可能地选择最长的公共子序列，以便最小化差异集合的大小。这种方法在实际应用中通常能够产生较好的结果，尽管并不一定能够找到最优解。pJh28资讯网——每日最新资讯28at.com

本文链接：http://www.28at.com/showinfo-26-43288-0.htmlDiffUtil和它的差量算法

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com

上一篇： 一款基于大量业务实践的轻量级高性能表单库

下一篇： SpringBoot与CQRS的完美结合：构建高效、可扩展的应用程序