Java:声明一个大小为n的数组的大时间是什么？

Question

在Java中声明大小为n的数组的运行时间是多少？我想这将取决于内存是否zero'ed出来的垃圾收集(在这种情况下,它可能是O(1)),或在初始化(在这种情况下,它不得不为O(N)).

Answer 1

是的O(n).考虑这个简单的程序:

public class ArrayTest {

  public static void main(String[] args) {
     int[] var = new int[5];
  }

}

生成的字节码是:

Compiled from "ArrayTest.java"
public class ArrayTest extends java.lang.Object{
public ArrayTest();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_5
   1:   newarray int
   3:   astore_1
   4:   return

}

要查看的newarray指令是指令(只是搜索newarray).来自VM规范:

从垃圾收集堆中分配一个新数组,其组件类型为atype,长度为count.此新数组对象的引用arrayref被推入操作数堆栈.新数组的每个元素都初始化为数组类型的默认初始值(第2.5.1节).

由于每个元素都被初始化,因此需要O(n)时间.

编辑

查看提供的链接amit,可以在常量时间内使用默认值实现数组初始化.所以我猜它最终取决于JVM.你可以做一些粗略的基准测试,看看是否是这种情况.

Answer 2

关于JRE1.6的小型非专业基准测试:

public static void main(String[] args) {
    long start = System.nanoTime();
    int[] x = new int[50];
    long smallArray = System.nanoTime();
    int[] m = new int[1000000];
    long bigArray = System.nanoTime();
    System.out.println("big:" +  new Long( bigArray - smallArray));
    System.out.println("small:" +  new Long( smallArray - start));


}

给出了以下结果:

big:6133612
small:6159

所以我假设O(n).当然,这还不够确定,但这是一个暗示.