为什么Java的ArrayList的remove函数似乎成本如此之低？
10 浏览
为什么Java的ArrayList的remove函数似乎成本如此之低？
我有一个函数，用来操作一个非常大的列表，超过约250,000个项目。对于大多数项目，它只是替换位置x上的项目。然而，对于大约5%的项目，它必须从列表中移除它们。
使用LinkedList似乎是避免昂贵的删除操作的最明显的解决方案。然而，自然地，随着时间的推移，通过索引访问LinkedList变得越来越慢。这里的成本是几分钟（很多分钟）。
使用LinkedList上的迭代器也很昂贵，因为我似乎需要一个单独的副本来避免迭代器并发问题，同时编辑那个列表。这里的成本也是几分钟。
然而，这里让我有些惊讶。如果我改用ArrayList，它几乎瞬间就运行完毕。
对于一个具有297,515个元素的列表，删除11,958个元素并修改其他所有元素只需909毫秒。我验证了结果列表的大小确实是285,557，如预期的那样，并且包含我需要的更新信息。
为什么这么快？我查看了JDK6中ArrayList的源代码，它似乎使用了预期的arraycopy函数。我很想了解为什么ArrayList在这里表现得如此出色，而常识似乎表明，对于这个任务来说，使用数组是一个糟糕的想法，需要移动数十万个项目。