Java:两个列表之间的差异

Question

我公司的猫饲养应用程序追踪一队猫.它需要定期previousOrder与currentOrder(每个是ArrayList<Cat>)进行比较,并通知cat-wranglers任何变化.

每只猫都是独一无二的,只能在每个列表中出现一次(或根本不出现).大多数情况下,previousOrder和currentOrder列表具有相同的内容,顺序相同,但可能发生以下任何情况(从更频繁到更不频繁):

1. 猫的顺序完全被扰乱
2. 猫在列表中单独向上或向下移动
3. 新猫加入,在车队的特定点
4. 猫离开了车队

这对我来说似乎是一个编辑距离问题.理想情况下,我正在寻找一种算法来确定进行previousOrder匹配所需的步骤currentOrder:

• 移动Fluffy到位置12
• 插入Snuggles位置37
• 删除 Mr. Chubbs
• 等等

算法还应识别场景#1,在这种情况下,新订单将完整地传达.

对此最好的方法是什么？

(这篇文章和那篇文章提出了类似的问题,但是他们都在处理排序列表.我的订单是订购的,但未分类.)

编辑

该Levenshtein算法是一个很好的建议,但我很担心创建一个矩阵的时间/空间需求.我的主要目标是尽快确定并传达变更.比找到添加和发送消息更快的事情是"这是新猫,这是当前的订单."

Answer 1

这是我合并两个列表的算法,old和new.它不是最优雅或最有效的,但它似乎对我使用它的数据没问题.

new是最新的数据old列表,是需要转换为的过时列表new.该算法在old列表上执行其操作- 相应地移除,移动和插入项目.

for(item in old)
    if (new does not contain item)
        remove item from old

for(item in new)
    if (item exists in old)
        if (position(item, old) == position(item, new))
            continue // next loop iteration
        else
            move old item to position(item, new)
    else
        insert new item into old at position(item, new)

删除都是预先完成的,以使项目的位置在第二个循环中更可预测.

这背后的驱动力是将来自服务器的数据列表与<table>浏览器DOM中的行同步(使用javascript).这是必要的,因为我们不想在数据发生变化时重绘整个表格; 列表之间的差异可能很小,只影响一行或两行.它可能不是您正在寻找的数据算法.如果没有,请告诉我,我会删除它.

可能会对此进行一些优化.但它对我和我正在使用的数据来说足够高效和可预测.