14

我有 2 ArrayListsA并且B具有相同的数据结构C（hashCode() 和 equals() 被覆盖）。C代表学生的记录。这两个列表大小相同，分别代表新学生记录和旧学生记录（两个列表中的学生相同，排序可能不同）。我希望只保留 A 中已更改的那些记录。因此，我这样做：

 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);
    }
}

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

4

4 回答 4

11

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

我怀疑您没有任何重复的条目。如果是这种情况，您也可以通过HashSet（更改为，LinkedHashSet如果您想保留订单A）：

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

（或者如果顺序对你来说不重要，你可以HashSet一直使用 s 。）

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

于 2012-04-03T07:29:30.510 回答
1

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

比较时，它只是查找与支持数组匹配的第一次出现的索引Object[]。该算法维护两个索引，一个用于遍历后备数组，另一个作为匹配的占位符。在匹配的情况下，它只是移动后备数组上的索引并继续到下一个传入元素；这是相对便宜的。

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

例如：考虑一个带有 1,2,4,5 的数组列表 A 和我们匹配的带有 4,1 的集合“C”；想要删除 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。由于它们不相等，所以将 w 到数组末尾的值清空并重置大小。

A: 2,5 大小 2

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

于 2012-04-03T09:44:49.387 回答
1

绝对第二个“算法”比首先考虑摊销分析要好。这是最好的方法吗？你需要那个吗？它会对用户的性能造成任何明显的影响列表中的项目数量是否增长得如此之大，以至于这成为系统的瓶颈？

第一种方法更具可读性，将您的意图传达给维护代码的人。此外，最好使用“经过测试”的 API 而不是重新发明轮子（除非绝对必要） 计算机已经变得如此之快，以至于我们不应该进行任何过早的优化。

如果看到必要，我可能会使用 Set 的解决方案，类似于 @aioob 的

于 2012-04-03T11:03:40.227 回答
1

在某些情况下（与 EMF 模型操作相关），我在成员 removeAll 中遇到了性能瓶颈。ArrayList如上所述，只需使用标准，但如果 A 是例如removeAllEList，则可以遇到 n^2。

因此，避免依赖于特定实现的隐藏良好属性List< T >；Set.contains()O(1) 是一个保证（如果你使用 aHashSet并且有一个不错的 hashCode，log2(n) 用于TreeSet排序关系），用它来限制算法的复杂性。

我使用以下代码来避免无用的副本；目的是您正在扫描数据结构，找到您不想要的不相关元素并将它们添加到“todel”。

出于某种原因，例如避免并发修改，您正在导航树等......，您无法在执行此遍历时删除元素。因此，我们将它们累积成一个 HashSet “todel”。

在函数中，我们需要修改“容器”，因为它通常是调用者的属性，但是在“容器”上使用 remove(int index) 可能会因为元素的左移而导致复制。我们使用副本“内容”来实现这一点。

模板参数是因为在选择过程中，我经常得到 C 的子类型，但可以随意使用 <T>。

/**
 * Efficient O (n) operation to removeAll from an aggregation.
 * @param container a container for a set of elements (no duplicates), some of which we want to get rid of
 * @param todel some elements to remove, typically stored in a HashSet.
 */
public static <T> void removeAll ( List<T> container, Set<? extends T> todel ) {
    if (todel.isEmpty())
        return;
    List<T> contents = new ArrayList<T>(container);
    container.clear();
    // since container contains no duplicates ensure |B| max contains() operations
    int torem = todel.size();
    for (T elt : contents) {
        if ( torem==0 || ! todel.contains(elt) ) {
            container.add(elt);
        } else {
            torem--;
        }
    }
}

removeAll(A, new HashSet < C >(B)); 因此，在您的情况下，如果您在选择阶段确​​实无法累积到 Set< C > 中，您将调用 :支付 B 的一份副本。

将其放在实用程序类和静态导入中以方便使用。

于 2015-07-01T19:07:07.367 回答