Java:两个列表之间的差异

小马托尼:

我公司的养猫应用程序跟踪一群猫。每隔一段时间,它需要比较previousOrdercurrentOrder(各自为ArrayList<Cat>),并通知任何更改猫争吵。

每只猫都是唯一的,并且在每个列表中只能出现一次(或根本不出现)。在大多数情况下,previousOrdercurrentOrder列表的内容相同,顺序相同,但是可能发生以下任何一种情况(从更频繁到更不频繁):

  1. 猫的顺序被完全打乱了
  2. 猫在列表中上下移动
  3. 在车队的特定地点有新猫加入
  4. 猫离开车队

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

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

该算法还应该识别方案#1,在这种情况下,将完整传达新订单。

最好的方法是什么?

此帖子该帖子提出了类似的问题,但它们都在处理排序列表。我的列表是有序的,但未排序。)

编辑

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

罗布·赫鲁斯卡(Rob Hruska):

这是我汇总在一起的算法,用于合并两个列表oldnew它不是最优雅或最有效的方法,但是对于我使用它的数据来说似乎还可以。

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)。之所以需要它,是因为我们不想在数据更改时重新绘制整个表。列表之间的差异可能很小,仅影响一两行。它可能不是您要寻找数据的算法。如果没有,请告诉我,我将其删除。

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

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章