我公司的养猫应用程序跟踪一群猫。每隔一段时间,它需要比较previousOrder
到currentOrder
(各自为ArrayList<Cat>
),并通知任何更改猫争吵。
每只猫都是唯一的,并且在每个列表中只能出现一次(或根本不出现)。在大多数情况下,previousOrder
和currentOrder
列表的内容相同,顺序相同,但是可能发生以下任何一种情况(从更频繁到更不频繁):
对我来说,这似乎是一个编辑距离问题。理想情况下,我正在寻找一种算法,该算法确定进行previousOrder
匹配所需的步骤currentOrder
:
Fluffy
到位置12
Snuggles
在位置插入37
Mr. Chubbs
该算法还应该识别方案#1,在这种情况下,将完整传达新订单。
最好的方法是什么?
(此帖子和该帖子提出了类似的问题,但它们都在处理排序列表。我的列表是有序的,但未排序。)
编辑
该Levenshtein算法是一个很好的建议,但我很担心创建一个矩阵的时间/空间需求。我的主要目标是尽快确定并传达更改。这比查找添加内容并按照“这里有新猫,这是当前订单”的行发送消息要快。
这是我汇总在一起的算法,用于合并两个列表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)。之所以需要它,是因为我们不想在数据更改时重新绘制整个表。列表之间的差异可能很小,仅影响一两行。它可能不是您要寻找数据的算法。如果没有,请告诉我,我将其删除。
为此可能需要进行一些优化。但是对于我和正在使用的数据来说,它的性能和可预测性都足够。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句