1

如果我知道当时的大小，将大小传递Collection给构造函数会更好吗？在扩展和分配/重新分配Collection方面的节省效果是否显着？Collection

如果我知道的最小尺寸Collection但不知道上限怎么办。至少以最小的尺寸创建它仍然值得吗？

4

5 回答 5

6

不同的集合对此有不同的性能影响，对于 ArrayList 的节省可能非常明显。

import java.util.*;
public class Main{
public static void main(String[] args){
  List<Integer> numbers = new ArrayList<Integer>(5);
  int max = 1000000;
  // Warmup
  for (int i=0;i<max;i++) {
    numbers.add(i);
  }

  long start = System.currentTimeMillis();
  numbers = new ArrayList<Integer>(max);
  for (int i=0;i<max;i++) {
    numbers.add(i);
  }
  System.out.println("Preall: "+(System.currentTimeMillis()-start));

  start = System.currentTimeMillis();
  numbers = new ArrayList<Integer>(5);
  for (int i=0;i<max;i++) {
    numbers.add(i);
  }
  System.out.println("Resizing: "+(System.currentTimeMillis()-start));

}
}

结果：

Preall: 26
Resizing: 58

将 max 设置为 10000000 处的值的 10 倍运行会给出：

Preall: 510
Resizing: 935

因此，即使尺寸不同，您也可以看到比例保持不变。

这几乎是最坏情况的测试，但一次填充一个元素的数组非常常见，您可以看到大约有 2* 速度差异。

于 2014-01-15T13:38:32.757 回答
5

好的，这是我的 jmh 代码：

@OutputTimeUnit(TimeUnit.MICROSECONDS)
@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 3, time = 1)
@Fork(3)
public class Comparison
{
  static final int size = 1_000;
  @GenerateMicroBenchmark
  public List<?> testSpecifiedSize() {
    final ArrayList<Integer> l = new ArrayList(size);
    for (int i = 0; i < size; i++) l.add(1);
    return l;
  }

  @GenerateMicroBenchmark
  public List<?> testDefaultSize() {
    final ArrayList<Integer> l = new ArrayList();
    for (int i = 0; i < size; i++) l.add(1);
    return l;
  }
}

我的结果size = 10_000：

Benchmark             Mode Thr    Cnt  Sec         Mean   Mean error    Units
testDefaultSize       avgt   1      9    1       80.770        2.095  usec/op
testSpecifiedSize     avgt   1      9    1       50.060        1.078  usec/op

结果size = 1_000：

Benchmark             Mode Thr    Cnt  Sec         Mean   Mean error    Units
testDefaultSize       avgt   1      9    1        6.208        0.131  usec/op
testSpecifiedSize     avgt   1      9    1        4.900        0.078  usec/op

我的解释：

  • presizing在默认大小上有一些优势；
  • 边缘不是那么壮观；
  • 花费在添加到列表任务上的绝对时间是微不足道的。

我的结论：

添加初始尺寸，如果这让您感觉更温暖，但客观地说，您的客户不太可能注意到差异。

于 2014-01-15T14:09:52.973 回答
4

所有集合都是自动扩展的。不知道边界不会影响它们的功能（除非您遇到其他问题，例如使用所有可用内存等），但它可能会影响它们的性能。

有一些收藏。最值得注意的是 ArrayList，由于复制了整个底层数组，因此自动扩展的成本很高；数组列表的默认大小为 10，然后每次达到最大值时大小增加一倍。所以，假设你知道你的 arraylist 将包含 110 个对象但不给它一个大小，下面的副本将会发生

复印 10 --> 20
复印 20 --> 40
复印 40 --> 80
复印 80 --> 160

通过预先告诉 arraylist 它包含 110 个项目，您可以跳过这些副本。

有根据的猜测总比没有好

即使你错了也没关系。该集合仍将自动扩展，您仍将避免一些副本。降低性能的唯一方法是您的猜测太大：这将导致分配给集合的内存过多

于 2014-01-15T13:42:58.717 回答
0

在大小已知的极少数情况下（例如，将已知数量的元素填充到新集合中时），可能出于性能原因设置它。

大多数情况下，最好省略它并使用默认构造函数，从而使代码更简单、更易于理解。

于 2014-01-15T13:45:22.833 回答
0

对于基于数组的集合，重新调整大小是一项非常昂贵的操作。这就是为什么传递精确尺寸ArrayList是一个好主意的原因。

如果您将 size 设置为最小 size( MIN)，然后添加到集合MIN+1 元素，那么您将重新调整大小。ArrayList()调用ArrayList(10)，所以如果MIN足够大，那么您将获得一些优势。但最好的方法是创建预期ArrayList的集合大小。

但可能你更喜欢 LinkedList 因为它没有任何添加元素的成本（尽管list.get(i)有 O(i) 成本）

于 2014-01-15T13:54:56.413 回答