从 Iterable 创建 List 时使用哪种实现 [英] Which implementation to use when creating a List from Iterable

问题描述

我发现自己经常做以下事情:

I find myself frequently doing the following:

Iterator<A> itr = iterableOfA.getIterator();
List<B> list = new ArrayList<>(); // how about LinkedList?
while (itr.hasNext()) {
    B obj = iter.next().getB();
    list.add(obj);
}
someMethod(list); // this method takes an Iterable

我不知道 iterableOfA 中可能有多少元素 —可能是 5，也可能是 5000.在这种情况下，LinkedList 会是一个更好的实现吗(因为 list.add(obj) 将是 O(1))?就目前而言，如果 iterableOfA 有 5000 个元素，这将导致 list 的支持数组的许多调整大小.

I have no idea just how many elements are likely to be in iterableOfA — could be 5, could be 5000. In this case, would LinkedList be a better implementation to use here (since list.add(obj) would then be O(1))? As it stands, if iterableOfA has 5000 elements, this will lead to many resizings of backing array of list.

其他选择是:

Iterator<A> itr = iterableOfA.getIterator();
int size = Iterables.size(iterableOfA); // from Guava
List<B> list = new ArrayList<>(size);
// and the rest...

这意味着 iterableOfA 的两次迭代.当可迭代对象的大小未知且变化很大时，哪个选项最好:

This means double iteration of iterableOfA. Which option would be best when the size of the iterable is unknowns and can vary wildly:

1. 只需使用 ArrayList.
2. 只需使用 LinkedList.
3. 统计iterableOfA中的元素并分配一个ArrayList.

1. Just use ArrayList.
2. Just use LinkedList.
3. Count the elements in iterableOfA and allocate an ArrayList.

编辑 1

澄清一些细节:

1. 我主要针对性能进行优化，其次针对内存使用进行优化.
2. list 是一个短暂的分配，因为在请求结束时没有代码应该持有对它的引用.

1. I am optimizing primarily for performance and secondarily for memory usage.
2. list is a short-lived allocation as at the end of the request no code should be holding a reference to it.

编辑 2

对于我的具体情况，我意识到 someMethod(list) 不能处理超过 200 个元素的可迭代对象，所以我决定使用 new ArrayList<>(200) 对我来说效果很好.

Edit 2

For my specific case, I realized that someMethod(list) doesn't handle an iterable with greater than 200 elements, so I decided to go with new ArrayList<>(200) which works well enough for me.

但是，在一般情况下，我更愿意实施已接受答案中概述的解决方案(包装在自定义迭代中，无需分配列表).

However, in the general case I would have preferred to implement the solution outlined in the accepted answer (wrap in a custom iterable, obviating the need for allocating a list).

所有其他答案都提供了关于 ArrayList 与 LinkedList 相比如何合适的宝贵见解，所以我代表一般 SO 社区感谢大家！

All the other answers gave valuable insight into how suitable ArrayList is compared to LinkedList, so on behalf of the general SO community I thank you all!

推荐答案

我会完全跳过将元素复制到新集合的过程.

I would completely skip copying the elements to a new collection.

我们有实用程序代码可以轻松地将迭代器包装到可迭代对象和过滤器中以在类型之间进行转换，但其要点是:

We have utility code for easily wrapping Iterators into Iterables and Filter for converting between types, but the gist of it is:

final Iterable<A> iofA ... ;
Iterable<B> iofB = new Iterable<B>() {
  public Iterator<B> iterator() {
    return new Iterator<B>() {
      private final Iterator<A> _iter = iofA.iterator();
      public boolean hasNext() { return _iter.hasNext(); }
      public B next() { return _iter.next().getB(); }
    };
  }
};

无需额外的存储空间等.

No additional storage, etc. necessary.

这篇关于从 Iterable 创建 List 时使用哪种实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！