8

考虑以下 Java 代码（完整、编译和运行良好）。

该代码创建一个包含 5,000,000 个整数（1 到 500 万）的数组，对其进行循环，并创建一个它找到的完美正方形的 ArrayList。使用简单的技术检测完美的正方形，而不是位操作，但这不是当前问题的重点。

数学上，在 1 到 5M 之间，有 2236 个完美的正方形。因此，放入完美正方形的 ArrayList 的最终大小为 2236。

import java.util.ArrayList;

public class PerfSquares {

    public static ArrayList<Integer> perfectSquares(int[] arr) {
        ArrayList<Integer> al = new ArrayList<Integer>();
    //  ArrayList<Integer> al = new ArrayList<Integer>(arr.length);

        for (int i = 0; i < arr.length; i++) {
            double root = Math.sqrt(arr[i]);
            int irt = (int) Math.floor(root);
            if (irt * irt == arr[i]) {
                al.add(arr[i]);
            }
        }
        return al;
    }

    public static void main(String[] args) {
        int[] arr = new int[5000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i + 1;
        }

        long s = System.currentTimeMillis();
        perfectSquares(arr);
        long e = System.currentTimeMillis();
        System.out.println(e - s);
    }
}

我想专注于 ArrayList 的声明。这两行，其中之一被注释掉：

  ArrayList<Integer> al = new ArrayList<Integer>();
//ArrayList<Integer> al = new ArrayList<Integer>(arr.length);

当我使用第一个声明（没有明确提供大小）运行时，我看到的 timediff 是：

~96 milliseconds.

当我使用第二个声明（明确提供的大小）运行时， timediff 增加到：

~105 milliseconds

问题：

为什么会出现这种行为？第二种情况（提供的尺寸）不应该更快吗？

根据我的理解，在第一种情况下，当我们在创建 ArrayList 时省略 size 参数时，会在幕后初始化一个长度为 10 的数组。而当超过这个容量时，会分配一个容量更大（不确定大多少）的新数组，并复制之前的元素。

对于 2236 个元素且未指定初始大小，此“超出上限 - 分配新 - 复制 - 追加更多直到上限”循环应重复多次，从而减慢速度。

因此，我期望提供的大小声明会更快 - 因为分配将发生一次，并且不会发生容量超过/新数组创建和复制的情况。

或者这基本上是因为 2236 附加到 ArrayList，即使有所有 cap-exceeds-copy-over 周期，仍然比创建大小为 5,000,000 的 ArrayList 更快？

4

4 回答 4

6

你正在创建一个 500 万的数组列表，所以很明显它比较慢。你只需要 2236。那太浪费了。

例如，如果您将数组列表的大小更改为 10k，您会看到时差缩小。

为了使它更简单，只需以不同的顺序多次尝试此测试 -

public static void main(String[] args) {

   long timea = System.currentTimeMillis();

   // ArrayList<Integer> al = new ArrayList<Integer>();
   ArrayList<Integer> al = new ArrayList<Integer>(5000000);


    System.out.println(System.currentTimeMillis() - timea);

}

您会看到将数组列表初始化为 500 万需要大约 10 毫秒（在我的 macbook 上），而没有默认大小的数组几乎是瞬时的。无论您测试哪个订单，这都是一样的。

于 2013-10-28T12:35:45.890 回答
2

首先，你的测量方法有缺陷。然而，在这些情况下，测量并不容易，因为对于如此大的数组分配，每个下面的 new 可能会更慢。

至于您的问题：内存分配（甚至解除分配）是一项昂贵的操作。不是在你使用的时候new——现在 vms 已经针对许多小的短期对象进行了优化——但主要是当 JVM 必须malloc()在较低的系统级别上保留/分配（又名）内存时。此外，内存分配时间还取决于分配的内存量——你需要的越多，需要的时间就越长。

在您的情况下：完美正方形的数量很容易计算。只需使用(Math.sqrt(arr.length) + 1)确定初始ArrayList尺寸并立即获得完全正确的尺寸。

于 2013-10-28T13:16:25.410 回答
1

因为内存分配通常是一个缓慢的操作。我计算了这两种情况的分配数量和新元素。

在这种情况下

ArrayList<Integer> al = new ArrayList<Integer>();

总共只有 15 个分配 8317 个元素。在这种情况下

ArrayList<Integer> al = new ArrayList<Integer>(arr.length);

您有 5000000 个元素的单一分配。

于 2013-10-28T12:46:01.227 回答
0

当你调用add()一个ArrayList已经满的，它会自动增长 50%。所以它很快就会足够大，不会有那么多内存分配。

于 2013-10-28T13:34:36.023 回答