Java：两个列表之间的区别

algorithm list java edit-distance

2022-09-02 22:05:50

我公司的猫群应用程序跟踪一群猫。它需要定期与（每个都是一个）进行比较，并通知猫牧马人任何变化。previousOrdercurrentOrderArrayList<Cat>

每只猫都是唯一的，每个列表中只能出现一次（或根本不出现）。大多数情况下，和列表具有相同的内容，顺序相同，但可能会发生以下任何一种情况（从更频繁到更不频繁）：previousOrdercurrentOrder

猫的顺序完全混乱
猫在列表中分别向上或向下移动
新猫咪加入，在车队的特定地点
猫离开车队

这对我来说似乎是一个编辑距离问题。理想情况下，我正在寻找一种算法来确定匹配所需的步骤：previousOrdercurrentOrder

移动到位置Fluffy12
在位置插入Snuggles37
删除Mr. Chubbs
等。

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

最好的方法是什么？

(这篇文章和那个帖子提出了类似的问题，但它们都在处理排序列表。我的是有序的，但没有分类。

编辑

Levenshtein算法是一个很好的建议，但我担心创建矩阵的时间/空间要求。我的主要目标是尽快确定和传达更改。这比查找添加的内容并按照“这是新猫，这是当前订单”的行发送消息更快。

答案 1

这是我放在一起合并两个列表的算法，和.它不是最优雅或最高效的，但它似乎适用于我使用它的数据。oldnew

new是最新的数据列表，并且是需要转换为的过期列表。该算法对列表执行其操作 - 相应地删除、移动和插入项目。oldnewold

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)

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

这背后的驱动力是将来自服务器的数据列表与浏览器DOM中的行同步（使用javascript）。这是必需的，因为我们不想在数据更改时重绘整个表;列表之间的差异可能很小，只影响一两行。它可能不是您要查找数据的算法。如果没有，请告诉我，我会删除它。<table>

可能为此可以进行一些优化。但它对于我和我正在使用的数据来说足够高性能和可预测。

答案 2

Levenshtein distance metric.

http://www.levenshtein.net/