哪个更有效:使用removeAll()或使用以下HashMap技术仅保留ArrayList中已更改的记录

Question

我有2 ArrayList秒A和B相同的数据结构C(hashCode()和equals()重写).C代表学生的记录.这两个列表大小相同,分别代表新的学生记录和旧学生记录(学生在两个列表中都是相同的,排序可能不同).我希望只保留A中那些已被更改的记录.因此,我这样做:

 A.removeAll(B)

根据javadoc,这将获取A的每个记录并与B的每个记录进行比较,如果它们两者都相等,它将从A中删除记录.如果未发现A的记录等于任何记录. B,因为A中的所有学生也在B中,这意味着A的记录已经改变.问题是它容易产生n平方的复杂性.

另一种方法可以是:

Map<C> map = new HashMap<C>();
for (C record : B){
    map.add(record.getStudentId(),record);
}
List<C> changedRecords = new ArrayList<C>();
for (C record : A){
    if (record.equals(map.get(record.getStudentId())){
        changedRecords.add(record);
    }
}

我认为这可能比上述解决方案的复杂性低.那是对的吗 ？

Answer 1

是的,后一种算法比O(n^2)你好,因为你有两个循环,一个在一个范围内B,另一个在A你的每个循环中你做(分摊)常量工作,你的新解决方案就会运行O(|A| + |B|).

我怀疑你没有任何重复的条目.如果是这种情况,您也可以通过a HashSet(LinkedHashSet如果您想保留订单,请更改为A):

HashSet<C> tmp = new HashSet<C>(A);
tmp.removeAll(B);                     // Linear operation
A = new ArrayList<C>(tmp);

(或者,如果订单对您无关紧要,您可以一直使用HashSets.)

正如@Daud在下面的评论中所指出的,如果哈希集的大小小于影响复杂性的集合(至少在OpenJDK中),HashSet.removeAll(Collection c)实际上会c.contains反复调用.这是因为实现总是选择迭代较小的集合.