哪个更有效：使用 removeAll（）或使用以下 HashMap 技术在 ArrayList 中仅保留已更改的记录

performance hashmap java arraylist removeall

2022-09-04 03:14:43

我有2 s和相同的数据结构（hashCode（）和equals（）overred）。C 代表学生的记录。这两个列表的大小相同，分别代表新学生记录和旧记录（两个列表中的学生相同，顺序可能不同）。我希望只保留 A 中已更改的记录。因此，我做：ArrayListABC

 A.removeAll(B)

根据javadocs，这将获取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);
    }
}

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

答案 1

是的，后一种算法比更好，因为您有两个循环，一个范围超过，另一个循环，并且您在每个循环中执行（摊销）常量工作，因此您的新解决方案在中运行。O(n^2)BAO(|A| + |B|)

我怀疑你没有任何重复的条目。如果是这种情况，您也可以通过 a（更改为如果要保留以下位置的顺序）：HashSetLinkedHashSetA

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

（或者，如果顺序对您无关紧要，您可以一直使用s。HashSet

正如@Daud在下面的评论中指出的那样，如果哈希集的大小小于影响复杂性的集合（至少在OpenJDK中），则实际上会重复调用。这是因为实现始终选择循环访问较小的集合。HashSet.removeAll(Collection c)c.contains

答案 2

您可以节省的复杂性，您可能会在内存分配中丢失，因此不一定更有效率。Arrraylist使用类似于就地分区算法的东西来运行支持数组并针对比较进行测试。

在比较时，它只是简单地查找与后备数组匹配的第一次匹配的索引。该算法维护两个索引，一个用于循环访问后备数组，另一个用作匹配项的占位符。在匹配的情况下，它只需移动后备数组上的索引并继续到下一个传入元素;这是相对便宜的。Object[]

如果它发现传入集合不包含后备数组中当前索引处的值，则它只是覆盖了与当前索引处的元素发生最后一次匹配的元素，而不会产生新的内存分配。此模式将重复，直到 ArrayList 中的所有元素都已与传入的集合进行比较，因此您关注的复杂性。

例如：考虑一个数组列表 A 与 1，2，4，5 和集合 'C' 与 4，1 匹配;想要删除 4 和 1。这里是 for 循环上的每个迭代，它将变为 0 -> 4

迭代：r 是数组列表 a 上的 for 循环索引for (; r < size; r++)

r = 0 （C 是否包含 1？是的，跳到下一个） A： 1，2，4，5 w = 0

r = 1 （C 是否包含 2？否，将 r 处的值复制到 w++所指向的点中） A： 2，2，4，5 w=1

r = 2 （C 是否包含 4？，是跳过） A： 2，2，4，5 w=1

r = 3 （C 是否包含 5？否，将 r 处的值复制到 w++ 所指向的点中）

答：2，5，4，5 w=2

r=4，停止

将 w 与支持数组的大小进行比较，后者为 4。由于它们不相等 Null，因此从 w 到数组末尾的值将 null 出并重置大小。

答：2，5 大小 2

内置的 removeAll 还认为 ArrayList 可以包含 null。您可以在上面的解决方案中将NPE放在record.getStudentId（）上。最后，removeAll 可防止在 Collection.contains 上的比较中出现异常。如果发生这种情况，它最终会使用本机memcopy，以高效的方式保护支持阵列免受损坏。

哪个更有效：使用 removeAll（） 或使用以下 HashMap 技术在 ArrayList 中仅保留已更改的记录

哪个更有效：使用 removeAll（）或使用以下 HashMap 技术在 ArrayList 中仅保留已更改的记录