为什么Java的ArrayList的remove函数似乎花费如此之less？
我有一个function，操纵一个非常大的名单，超过约25万件。 对于大多数这些项目，它只是取代位置x的项目。 但是，其中约5％的人必须将其从名单中删除。
使用LinkedList似乎是避免昂贵的清除的最明显的解决scheme。 然而，自然地，随着时间的推移，索引访问LinkedList变得越来越慢。 这里的成本是几分钟（其中很多）。
在这个LinkedList上使用迭代器也很昂贵，因为我似乎需要一个单独的副本来避免编辑该列表时出现Iterator并发问题。 这里的成本是几分钟。
但是，这里是我的头脑被吹了一下。 如果我更改为一个ArrayList，它几乎立即运行。
对于包含297515个元素的列表，删除11958个元素并修改其他所有内容需要909ms。 我证实，结果列表的大小确实是285557，并且包含我需要的更新信息。
为什么这么快？ 我在JDK6中查看了ArrayList的源代码，它似乎正在按照预期使用arraycopy函数。 我很想理解为什么一个ArrayList在这里工作得很好，当常识似乎表明这个任务的数组是一个可怕的想法，需要移动数十万个项目。
我运行了一个基准testing，尝试以下每个策略来过滤列表元素：
- 将想要的元素复制到新列表中
-
使用Iterator.remove()从ArrayList删除不需要的元素 - 使用
Iterator.remove()从LinkedList删除不需要的元素 - 将列表压缩到原位（将想要的元素移动到较低的位置）
- 通过
ArrayList上的索引（List.remove(int)）删除 - 在
LinkedList上通过索引（List.remove(int)）移除
每次我用100000个随机的Point实例填充列表，并使用一个过滤条件（基于哈希代码），它将接受95％的元素，并拒绝剩余的5％（与问题中陈述的比例相同，但是较小因为我没有时间去testing25万个元素。）
平均时间（在我的旧MacBook Pro：Core 2 Duo，2.2GHz，3Gb RAM上）是：
CopyIntoNewListWithIterator : 4.24ms CopyIntoNewListWithoutIterator: 3.57ms FilterLinkedListInPlace : 4.21ms RandomRemoveByIndex : 312.50ms SequentialRemoveByIndex : 33632.28ms ShiftDown : 3.75ms
因此，从LinkedList删除元素的索引要比从ArrayList删除元素要贵300倍以上，并且可能比其他方法（避免线性search和arrays拷贝）贵6000-10000倍，
在这四种快速方法之间似乎没有太大差别，但是我只用500000个元素的列表再次运行这四个元素，结果如下：
CopyIntoNewListWithIterator : 92.49ms CopyIntoNewListWithoutIterator: 71.77ms FilterLinkedListInPlace : 15.73ms ShiftDown : 11.86ms
我猜测，更大的caching容量成为限制因素，所以创build列表的第二个副本的成本变得很大。
代码如下：
import java.awt.Point; import java.security.SecureRandom; import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Random; import java.util.TreeMap; public class ListBenchmark { public static void main(String[] args) { Random rnd = new SecureRandom(); Map<String, Long> timings = new TreeMap<String, Long>(); for (int outerPass = 0; outerPass < 10; ++ outerPass) { List<FilterStrategy> strategies = Arrays.asList(new CopyIntoNewListWithIterator(), new CopyIntoNewListWithoutIterator(), new FilterLinkedListInPlace(), new RandomRemoveByIndex(), new SequentialRemoveByIndex(), new ShiftDown()); for (FilterStrategy strategy: strategies) { String strategyName = strategy.getClass().getSimpleName(); for (int innerPass = 0; innerPass < 10; ++ innerPass) { strategy.populate(rnd); if (outerPass >= 5 && innerPass >= 5) { Long totalTime = timings.get(strategyName); if (totalTime == null) totalTime = 0L; timings.put(strategyName, totalTime - System.currentTimeMillis()); } Collection<Point> filtered = strategy.filter(); if (outerPass >= 5 && innerPass >= 5) { Long totalTime = timings.get(strategyName); timings.put(strategy.getClass().getSimpleName(), totalTime + System.currentTimeMillis()); } CHECKSUM += filtered.hashCode(); System.err.printf("%-30s %d %d %d%n", strategy.getClass().getSimpleName(), outerPass, innerPass, filtered.size()); strategy.clear(); } } } for (Map.Entry<String, Long> e: timings.entrySet()) { System.err.printf("%-30s: %9.2fms%n", e.getKey(), e.getValue() * (1.0/25.0)); } } public static volatile int CHECKSUM = 0; static void populate(Collection<Point> dst, Random rnd) { for (int i = 0; i < INITIAL_SIZE; ++ i) { dst.add(new Point(rnd.nextInt(), rnd.nextInt())); } } static boolean wanted(Point p) { return p.hashCode() % 20 != 0; } static abstract class FilterStrategy { abstract void clear(); abstract Collection<Point> filter(); abstract void populate(Random rnd); } static final int INITIAL_SIZE = 100000; private static class CopyIntoNewListWithIterator extends FilterStrategy { public CopyIntoNewListWithIterator() { list = new ArrayList<Point>(INITIAL_SIZE); } @Override void clear() { list.clear(); } @Override Collection<Point> filter() { ArrayList<Point> dst = new ArrayList<Point>(list.size()); for (Point p: list) { if (wanted(p)) dst.add(p); } return dst; } @Override void populate(Random rnd) { ListBenchmark.populate(list, rnd); } private final ArrayList<Point> list; } private static class CopyIntoNewListWithoutIterator extends FilterStrategy { public CopyIntoNewListWithoutIterator() { list = new ArrayList<Point>(INITIAL_SIZE); } @Override void clear() { list.clear(); } @Override Collection<Point> filter() { int inputSize = list.size(); ArrayList<Point> dst = new ArrayList<Point>(inputSize); for (int i = 0; i < inputSize; ++ i) { Point p = list.get(i); if (wanted(p)) dst.add(p); } return dst; } @Override void populate(Random rnd) { ListBenchmark.populate(list, rnd); } private final ArrayList<Point> list; } private static class FilterLinkedListInPlace extends FilterStrategy { public String toString() { return getClass().getSimpleName(); } FilterLinkedListInPlace() { list = new LinkedList<Point>(); } @Override void clear() { list.clear(); } @Override Collection<Point> filter() { for (Iterator<Point> it = list.iterator(); it.hasNext(); ) { Point p = it.next(); if (! wanted(p)) it.remove(); } return list; } @Override void populate(Random rnd) { ListBenchmark.populate(list, rnd); } private final LinkedList<Point> list; } private static class RandomRemoveByIndex extends FilterStrategy { public RandomRemoveByIndex() { list = new ArrayList<Point>(INITIAL_SIZE); } @Override void clear() { list.clear(); } @Override Collection<Point> filter() { for (int i = 0; i < list.size();) { if (wanted(list.get(i))) { ++ i; } else { list.remove(i); } } return list; } @Override void populate(Random rnd) { ListBenchmark.populate(list, rnd); } private final ArrayList<Point> list; } private static class SequentialRemoveByIndex extends FilterStrategy { public SequentialRemoveByIndex() { list = new LinkedList<Point>(); } @Override void clear() { list.clear(); } @Override Collection<Point> filter() { for (int i = 0; i < list.size();) { if (wanted(list.get(i))) { ++ i; } else { list.remove(i); } } return list; } @Override void populate(Random rnd) { ListBenchmark.populate(list, rnd); } private final LinkedList<Point> list; } private static class ShiftDown extends FilterStrategy { public ShiftDown() { list = new ArrayList<Point>(); } @Override void clear() { list.clear(); } @Override Collection<Point> filter() { int inputSize = list.size(); int outputSize = 0; for (int i = 0; i < inputSize; ++ i) { Point p = list.get(i); if (wanted(p)) { list.set(outputSize++, p); } } list.subList(outputSize, inputSize).clear(); return list; } @Override void populate(Random rnd) { ListBenchmark.populate(list, rnd); } private final ArrayList<Point> list; } }
数组拷贝是一个相当便宜的操作。 它是在一个非常基本的层次上完成的（它是一个java本地静态方法），而且你还没有进入性能变得非常重要的范围。
在你的例子中，你拷贝大约150000（平均）的数组大约12000次。 这并不需要太多时间。 我在笔记本电脑上对它进行了testing，耗时不到500毫秒。
更新我使用下面的代码来测量我的笔记本电脑（英特尔P8400）
import java.util.Random; public class PerformanceArrayCopy { public static void main(String[] args) { int[] lengths = new int[] { 10000, 50000, 125000, 250000 }; int[] loops = new int[] { 1000, 5000, 10000, 20000 }; for (int length : lengths) { for (int loop : loops) { Object[] list1 = new Object[length]; Object[] list2 = new Object[length]; for (int k = 0; k < 100; k++) { System.arraycopy(list1, 0, list2, 0, list1.length); } int[] len = new int[loop]; int[] ofs = new int[loop]; Random rnd = new Random(); for (int k = 0; k < loop; k++) { len[k] = rnd.nextInt(length); ofs[k] = rnd.nextInt(length - len[k]); } long n = System.nanoTime(); for (int k = 0; k < loop; k++) { System.arraycopy(list1, ofs[k], list2, ofs[k], len[k]); } n = System.nanoTime() - n; System.out.print("length: " + length); System.out.print("\tloop: " + loop); System.out.print("\truntime [ms]: " + n / 1000000); System.out.println(); } } } }
一些结果：
length: 10000 loop: 10000 runtime [ms]: 47 length: 50000 loop: 10000 runtime [ms]: 228 length: 125000 loop: 10000 runtime [ms]: 575 length: 250000 loop: 10000 runtime [ms]: 1198
我认为性能的差异很可能归结于ArrayList支持随机访问的地方，而LinkedList没有。
如果我想获得一个ArrayList（1000）我指定一个特定的索引来访问这个，但LinkedList不支持这个，因为它是通过节点引用组织的。
如果我调用LinkedList的get（1000），它将遍历整个列表，直到find索引1000，如果在LinkedList中有大量的项目，这可能是非常昂贵的。
有趣和意想不到的结果。 这只是一个假设，但…
平均来说，你的一个数组元素的删除将需要移动你的列表的一半（在它之后的所有内容）返回一个元素。 如果每个项目是一个指向对象的64位指针（8字节），那么这意味着复制125000个项目，每个指针8个字节= 1 MB。
一个现代化的CPU可以很快地将一个连续的1MB的RAM块复制到RAM中。
与循环链接列表的每个访问相比，这需要比较和分支和其他CPU不友好的活动，RAM副本是快速的。
你应该真的尝试独立地对各种操作进行基准testing，看看它们在各种列表实现方面的效率如何。 如果你在这里分享你的结果！
我在这里跳过一些实现细节，只是为了解释根本的区别。
为了移除M个元素列表中的第N个元素，LinkedList实现将导航到这个元素，然后简单地移除它，并相应地更新N-1和N + 1个元素的指针。 这第二个操作非常简单，但是这个过程要花费你的时间。
然而，对于ArrayList，访问时间是由数组支持的即时访问，意味着连续的内存空间。 您可以直接跳到正确的内存地址来执行，广义地说，执行以下操作：
- 重新分配一个新的M – 1元素数组
- 把所有从0到N – 1的索引0放在新的数组列表中
- 将数组N中的所有N + 1都置于M的索引N处。
想一想，你会注意到甚至可以重复使用相同的数组，因为Java可以使用带有预分配大小的ArrayList，所以如果你删除元素，你可以跳过步骤1和步骤2，直接执行步骤3并更新你的大小。
内存访问速度很快，在现代硬件上复制一块内存可能足够快，移动到N位太耗时。
但是，如果您使用LinkedList的方式允许您删除多个相互关联的元素并跟踪您的位置，您将看到一个收益。
但是很明显，在一个很长的名单上，做一个简单的删除（i）将会是昂贵的。
为此添加一些盐和香料：
- 有关arrays数据结构效率的说明以及dynamic数组 维基百科条目中关于性能的说明，请参阅您的疑虑。
- 请记住，使用需要连续内存的内存结构需要连续的内存。 这意味着你的虚拟内存将需要能够分配连续的块。 甚至在使用Java的时候，你会发现你的JVM高兴地在一个低级的崩溃中发生了一个难以理解的OutOfMemoryException。
