比较两个arraylists以保持它们之间的增量的有效方式

Question

这是我的问题:

我需要比较两个ArrayLists并返回它们是否相同或者它们是不同的,返回其中一个元素是新的元素,可以这么说.

这是数据集的行为:

• 两个ArrayLists由字符串组成
• 它们来自同一个来源,因此大部分时间都是相同的
• 是有序的(在附加到他们的自定义逻辑的意义上)
• 永远不会有空的弦乐
• 所有的弦乐总是有相同的长度
• 没有重复

我想要的是:

• 实现我的两个目标的最快方式,无论哪种情况
• 仅使用Java 1.6标准库特性,我宁愿不实现一个混合类,它可以从List模拟一些东西然后再设置为Set.

例:

A: [ 'a', 'b', 'c', 'd']   

B: [ 'a', 'c', 'd']

结果:列表不同,返回元素'b'; A将是"工作"列表,我们将根据此ArrayList中的新内容进行比较,因为B将永远不会更改.

感谢您的回复和您的意见.

Answer 1

你最快的要求困扰我很多 - 我反对优化 - 我通常认为早期优化是最糟糕的编程实践之一.

如果您真的想这样做,请按顺序浏览两个列表.

如果第一个条目匹配,则将该一个条目放入"相同"堆中并递增两个索引.如果它们不同,则将第一个(低于/低于)一个放入"不同"堆中并递增列出索引.以这种方式循环,直到你到达一个列表的末尾(另一个列表中的任何剩余显然都进入"不同"集合.

这应该让你"接近"最快的方式.如果你想要绝对最快,那么你必须从使用数组而不是列表开始,然后非常注意你在每一步中做的其他事情 - 但算法应该仍然非常接近最优.

作为次优但更易读的示例,您可以使用一些集合操作.

Set set1=new HashSet(list1)
Set set2=new HashSet(list2)
Set same=set1.retainAll(set2) // I forget if retainAll modifies set1--if so you need to copy it first
set1.removeAll(list2)
set2.removeAll(list1)
Set different=set1.addAll(set2)

// at this point same contains all the similar values and different contains the ones that don't match.  Done.

这是简短易读的,可能比您想象的更高效.如果类似这样的东西运行良好(例如,在GUI代码中速度不太重要),那么编写自己的代码将是不好的做法.