V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
beimengyeyu
V2EX  ›  程序员

如何对比两个 list 的差异

  •  
  •   beimengyeyu · 2022-10-10 21:53:13 +08:00 · 2881 次点击
    这是一个创建于 756 天前的主题,其中的信息可能已经有所发展或是发生改变。

    输入两个 list ,输出尽可能少但是完全的描述出两个 list 之间的差异

    例 1: ABCD 、ACBD 输出 1 位置顺序不一致、2 位置顺序不一致

    例 2: ABCD 、ACD 输出 list2 1 位置缺少 B ( list1 1 位置多 B )

    例 3: ABCD 、AFCD 输出 位置 1 字符不同

    想问问大佬们有没有现成的算法,或者提供一下思路,个人感觉和 git diff 的时候的行比较类似(每个元素看作一行)。但是网上找到的的讲 Myers 有点难懂,感觉也不是偏向于行比较,而是偏向于同行的字符串比较(我理解可能有偏差)

    13 条回复    2022-10-11 17:42:17 +08:00
    soap520
        1
    soap520  
       2022-10-10 21:56:14 +08:00   ❤️ 1
    听起来有点像是最小编辑距离。
    Jooooooooo
        2
    Jooooooooo  
       2022-10-10 22:03:34 +08:00
    感觉你这还是定义问题.

    ABCD 和 ADBC 是 D 多了还是 BC 是错的?
    DiamondYuan
        3
    DiamondYuan  
       2022-10-10 22:16:00 +08:00
    ```

    /**
    * diff 函数
    * @param {any} newList 新数组
    * @param {any} oldList 旧数组
    */
    const diff = function(newList, oldList) {
    // lastIndex:即访问过元素的最右下标
    let lastIndex = 0;

    // 遍历新数组
    for(let i = 0, len = newList.length; i < len; i++) {
    // 查找当前元素在旧数组的下标
    let index = getIndex(newList[i], oldList);

    // 若该元素在旧数组中存在
    if(index !== -1) {
    // 若该元素在旧数组的下标小于最右下标 lastIndex
    if(index < lastIndex) {
    // 移动元素:from index to i
    move(newList[i], i, index);
    }

    // 更新 lastIndex ,取 index 和 lastIndex 的较大者
    lastIndex = Math.max(index, lastIndex);
    }
    // 若该元素不在旧数组,说明这是个新加入元素
    else {
    // 插入元素:append to i
    append(newList[i], i);
    }
    }

    // 遍历旧数组
    for(let i = 0, len = oldList.length; i < len; i++) {
    // 若发现当前元素在新数组中不存在,说明这个元素需要移除
    if(getIndex(oldList[i], newList) === -1) {
    // 移除元素:remove from i
    remove(oldList[i], i);
    }
    }
    }

    /**
    * 找出元素在数组的下标,找不到返回-1
    * @param {T} item 要找的元素
    * @param {Array<T>} list 目标数组
    */
    const getIndex = function(item, list) {
    // 对比 key
    return list.findIndex(i => i.key === item.key);
    }


    ```

    你这个听起来很像前端的 diff

    https://github.com/phenomLi/Blog/issues/24
    leonshaw
        4
    leonshaw  
       2022-10-10 22:42:10 +08:00
    LCS 基础上处理一下输出
    Anarchy
        5
    Anarchy  
       2022-10-11 00:31:23 +08:00
    一般再前端列表展示上会需要比较新列表与旧列表数据的不同,转换为增删改移动,然后做对应的动画效果。你要的就是这种效果吧,算法也是 Myers's difference algorithm 。
    ipwx
        6
    ipwx  
       2022-10-11 00:33:25 +08:00   ❤️ 1
    chihiro2014
        7
    chihiro2014  
       2022-10-11 01:02:28 +08:00
    比较 size ,然后 removeall 看看有没有剩余
    ericls
        8
    ericls  
       2022-10-11 02:28:55 +08:00 via iPhone
    你要的是 intention 还是 diff?
    xuanbg
        9
    xuanbg  
       2022-10-11 09:07:22 +08:00
    集合没有顺序,所以 a,b,c,d 和 a,c,b,d 是相同的。要比较集合是否相同,在数学上就是取两个集合的差集,差集为空,则集合相等。
    visper
        10
    visper  
       2022-10-11 09:19:08 +08:00
    google:最小编辑距离输出编辑过程
    AoEiuV020CN
        11
    AoEiuV020CN  
       2022-10-11 10:42:59 +08:00
    第一反应是安卓有个现成的 DiffUtil, 就是算出两个列表数据的差异,然后刷新列表控件用的,
    https://android.googlesource.com/platform/frameworks/support/+/refs/heads/androidx-main/recyclerview/recyclerview/src/main/java/androidx/recyclerview/widget/DiffUtil.java
    ruanimal
        12
    ruanimal  
       2022-10-11 11:46:20 +08:00
    可以看看 python 的 difflib 内置库
    zmal
        13
    zmal  
       2022-10-11 17:42:17 +08:00
    google 有个开源项目叫 diff-match-patch
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1208 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 18:07 · PVG 02:07 · LAX 10:07 · JFK 13:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.