为什么Java的ArrayList中的删除功能似乎花费这么少？ [英] Why does Java's ArrayList's remove function seem to cost so little?
问题描述
我有操纵一个非常大的名单，超过25万项的功能。对大多数这些项目的，它只是在位置x替换项。然而，对于其中的约5％，它必须从列表中删除。
I have a function which manipulates a very large list, exceeding about 250,000 items. For the majority of those items, it simply replaces the item at position x. However, for about 5% of them, it must remove them from the list.
使用链表似乎是最明显的解决方案，以避免昂贵的清除量。然而，自然，通过索引访问的LinkedList变得随着时间的推移越来越慢。这里的代价是分（和他们中的很多）。
Using a LinkedList seemed to be the most obvious solution to avoid expensive removals. However, naturally, accessing a LinkedList by index becomes increasingly slow as time goes on. The cost here is minutes (and a lot of them).
在使用该LinkedList的迭代器也是昂贵的，因为我似乎需要一个单独的副本以避免迭代器并发的问题，而编辑该列表。这里的成本分钟。
Using an Iterator over that LinkedList is also expensive, as I appear to need a separate copy to avoid Iterator concurrency issues while editing that list. The cost here is minutes.
然而，这也正是我的脑海里吹了一下。如果我改变到一个ArrayList，它运行几乎瞬间。
However, here's where my mind is blown a bit. If I change to an ArrayList, it runs almost instantly.
对于297515元，除去11958元和其他的一切修改的列表需要909ms。我验证了结果列表确实是在大小285557，符合市场预期，并包含最新的信息，我需要。
For a list with 297515 elements, removing 11958 elements and modifying everything else takes 909ms. I verified that the resulting list is indeed 285557 in size, as expected, and contains the updated information I need.
这是为什么这么快？我看了看源在JDK6 ArrayList和它似乎是使用arraycopy功能如预期。我很想知道为什么一个ArrayList这么好这里的时候，常识似乎表明，这一任务的数组是一个可怕的想法，需要移几十万的项目。
Why is this so fast? I looked at the source for ArrayList in JDK6 and it appears to be using an arraycopy function as expected. I would love to understand why an ArrayList works so well here when common sense would seem to indicate that an array for this task is an awful idea, requiring shifting several hundred thousand items.
推荐答案
我跑了基准测试，试图每个以下策略用于过滤列表中的元素：
I ran a benchmark, trying each of the following strategies for filtering the list elements:
- 通缉元素复制到一个新的列表
-
使用Iterator.remove（）从删除不需要的元素一个的ArrayList - 使用
Iterator.remove（）去除不需要的元素的LinkedList - 紧凑列表就地（移动想要的元素，以较低的位置）
- 通过指数（
List.remove（INT））删除的ArrayList - 通过指数（
List.remove（INT））删除的LinkedList
- Copy the wanted elements into a new list
UseIterator.remove()to remove the unwanted elements from anArrayList- Use
Iterator.remove()to remove the unwanted elements from aLinkedList - Compact the list in-place (moving the wanted elements to lower positions)
- Remove by index (
List.remove(int)) on anArrayList - Remove by index (
List.remove(int)) on aLinkedList
每个我填充列表与点 100000随机实例和使用的过滤条件（基于散列code）该会接受元素的95％的时间并拒绝剩下的5％（同一比例的问题说明，但有一个小名单，因为我没有时间来运行测试的250000元）。
Each time I populated the list with 100000 random instances of Point and used a filter condition (based on the hash code) that would accept 95% of elements and reject the remaining 5% (the same proportion stated in the question, but with a smaller list because I didn't have time to run the test for 250000 elements.)
和平均时间（在我的旧的MacBook Pro：Core 2 Duo处理器，2.2GHz的，3GB内存）是：
And the average times (on my old MacBook Pro: Core 2 Duo, 2.2GHz, 3Gb RAM) were:
CopyIntoNewListWithIterator : 4.24ms
CopyIntoNewListWithoutIterator: 3.57ms
FilterLinkedListInPlace : 4.21ms
RandomRemoveByIndex : 312.50ms
SequentialRemoveByIndex : 33632.28ms
ShiftDown : 3.75ms
因此，移除从的LinkedList 一度超过300倍更昂贵通过索引的元素不是从消除他们的的ArrayList 和时间可能介于6000-10000之间比其他方法更昂贵的（即避免线性搜索和 arraycopy ）
So removing elements by index from a LinkedList was more than 300 times more expensive than removing them from an ArrayList, and probably somewhere between 6000-10000 times more expensive than the other methods (that avoid linear search and arraycopy)
下面似乎没有成为四更快的方法相差无几，但我用下面的结果500000元素列表又跑只是那些四：
Here there doesn't seem to be much difference between the four faster methods, but I ran just those four again with a 500000-element list with the following results:
CopyIntoNewListWithIterator : 92.49ms
CopyIntoNewListWithoutIterator: 71.77ms
FilterLinkedListInPlace : 15.73ms
ShiftDown : 11.86ms
我猜测，随着更大尺寸的高速缓存存储器成为限制因素，因此创建列表的第二个副本的成本变得显著。
I'm guessing that with the larger size cache memory becomes the limiting factor, so the cost of creating a second copy of the list becomes significant.
这里的code：
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的ArrayList中的删除功能似乎花费这么少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
