java - 在 Java 中过滤列表，同时避免 o(n) 复杂度中的 ConcurrentModificationException

Question

我发现显然 iterator.remove() 的复杂度为 o(n)。任何人都知道一种在不使用 iterator.remove() 的情况下过滤列表同时避免 ConcurrentModificationException 的方法。

以下是显示差异的代码片段。它创建一个大型数组列表，然后使用 it.remove() 从中间删除其中的大部分。然后这一次它从一开始就做同样的事情。在我的机器上它写着:第一次测试 699962ms第二次测试329181ms

明显区别很大

package src;

import java.util.*;
import java.lang.*;

class Main {
    public static void main(String[] args) {
        ArrayList<Integer> a = new ArrayList<Integer>();
        long before, after;

        double elements = Math.pow(10, 3);

        for(int i = 0; i < elements; i++) {
            a.add(i);
        }

        Iterator<Integer> it = a.iterator();
        for(int i = 0; i < elements * 0.4; i++){
            it.next();
        }

        before = System.nanoTime();
        for(int i = 0; i < elements * 0.5; i++){
            it.remove();
            it.next();
        }
        after = System.nanoTime();
        System.out.println(after - before);

        a = new ArrayList<Integer>();
        for(int i = 0; i < elements; i++) {
            a.add(i);
        }


        before = System.nanoTime();
        it = a.iterator();
        it.next();
        for(int i = 0; i < elements * 0.5; i++){
            it.remove();
            it.next();
        }
        after = System.nanoTime();
        System.out.println(after - before);


    }
}

Answer 1

据了解，您的基准不正确。考虑到使用 remove() 或 Iterator.remove() 从 ArrayList 中进行一次删除的时间复杂度为 O(n) 操作(除非删除最后一个元素)由于内部数组大小的调整，代码在任何情况下都不会很好地执行。

LinkedList 会在迭代时为您提供 O(1) 删除操作，但您应该选择最简单的解决方案并使用 List.removeIf() 。 ArrayList 会覆盖它以实现 O(n) 性能，并避免 CME。