java - 当我需要调整源列表时，addAll 最有效的等价物是什么？

Question

如果我想将一个列表添加到另一个列表，我调用 target.adAll(source)。

但是如果我需要先处理列表中的每个值怎么办？

我可以做类似的事情

for(String s: source) {
  target.add(s.toLowerCase());
}

或使用 java 8:

source.stream().map(x->x.toLowerCase()).forEachOrdered(target::add);

但无论哪种方式，我似乎都失去了 addAll 的性能优势。执行此操作的最高效方法是什么？

Answer 1

那么，“addAll 的性能优势”是什么？最后，addAll 必须将所有元素添加到目标 Collection 中。如果目标是 ArrayList，主要好处是确保没有不必要的容量增加操作。

但请注意，这是以创建临时数组为代价的，参见 implementation of ArrayList.addAll .为了抵消这笔费用，您必须添加大量元素。

如果我们要添加比目标当前容量更多的元素，则增加操作是不可避免的。所以 addAll 只提供一个好处，如果目标必须增加容量 不止一次 如果您只是使用 add。由于容量增加了 1.5 倍并且容量等于或大于当前大小，因此我们必须添加至少多于当前大小一半的元素，以防止不必要的容量增加操作。

如果您真的认为这会成为一个问题，那么很容易解决:

if(target instanceof ArrayList)
    ((ArrayList)target).ensureCapacity(target.size()+source.size());
source.stream().map(String::toLowerCase).forEachOrdered(target::add);

当然，在一些极端情况下，add 的成本要高得多，例如CopyOnWriteArrayList。对于此目标集合类型，首先通过 collect(Collectors.toList()) 将其收集到 List 中，然后使用 addAll 可能会有所帮助。或者你创建一个简单的惰性 Collection 作为中间步骤:

public static <T> Collection<T> lazyCollection(Supplier<? extends Stream<T>> s) {
    return new AbstractCollection<T>() {
        public Iterator<T> iterator() { return s.get().iterator(); }
        public int size() { return (int)s.get().count(); }
        public Object[] toArray() { return s.get().toArray(); }
    };
}

可以这样使用:

target.addAll(lazyCollection(() -> source.stream().map(String::toLowerCase)));

如果集合在获取 Iterator 之前先请求 size()，那么这种方法会因为计算 Stream 两次而受到影响，但据我所知，没有标准集合会这样做。他们要么在不依赖预测大小的情况下使用迭代器，要么求助于 toArray()，例如 ArrayList.addAll 或 CopyOnWriteArrayList.addAll .