分配数组需要多长时间(用Java)

Question

关于数组分配的一般性问题,主要是在Java中,但我认为它与所有编程语言相关:

为大小为n的数组[以O(n)为单位)分配内存需要多长时间？我可以想象一个实现,其中内存分配在恒定时间内发生:如果你有大量的空内存你可以创建一个指向新数组的第一个和最后一个索引的指针,但是通常如何分配内存？(另外,至少在Java中,如果初始化整数数组,则数组中的所有值最初都设置为0;这是否意味着数组中的每个索引都单独设置为等于0,这将操作O(n)？)

谢谢.

Answer 1

我刚刚在热点上运行微基准 - 发布JIT编译,分配一个数组(在i7上)需要:

• 对于大小为1的数组,大约10 ns
• 对于10,000个大小的数组,大约400 ns
• 对于大小为1,000,000的阵列,大约300,000 ns

所以回答你的问题,根据经验,它似乎是热点上的O(n).

详细结果:

Benchmark                              Mode Thr    Cnt  Sec         Mean   Mean error    Units
c.a.p.ArrayVsList.createArray1         avgt   1      5    2       12.293        0.867  nsec/op
c.a.p.ArrayVsList.createArray10000     avgt   1      5    2      428.369        9.997  nsec/op
c.a.p.ArrayVsList.createArray1M        avgt   1      5    2   342972.975     7253.989  nsec/op

• 在java中创建一个对象,如果你的堆足够大,几乎是免费的(它大致包括偏移一个指针)
• 但是在null创建数组时,JVM似乎急切地将所有项初始化为(或0表示基元)
• 其他JVM可能会执行更长时间的初始化