Java: ¿cuál es el gran momento para declarar una matriz de tamaño n?

¿Cuál es el tiempo de ejecución para declarar una matriz de tamaño n en Java? Supongo que esto dependerá de si la memoria está a cero en la recolección de basura (en cuyo caso podría ser O (1)) o en la inicialización (en cuyo caso tendría que ser O (n)).

Es O(n) . Considera este simple progtwig:

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

El bytecode generado es:

 Compiled from "ArrayTest.java" public class ArrayTest extends java.lang.Object{ public ArrayTest(); Code: 0: aload_0 1: invokespecial #1; //Method java/lang/Object."":()V 4: return public static void main(java.lang.String[]); Code: 0: iconst_5 1: newarray int 3: astore_1 4: return } 

La instrucción de echar un vistazo es la instrucción newarray (solo busca newarray ). Desde la especificación de VM:

Se asigna una nueva matriz cuyos componentes son de tipo atype y de recuento de longitud del montón recogido de basura. Una matriz de referencia de este nuevo objeto de matriz se inserta en la stack de operandos. Cada uno de los elementos de la nueva matriz se inicializa al valor inicial predeterminado para el tipo de la matriz (§2.5.1).

Dado que cada elemento se está inicializando, tomaría O(n) tiempo.

EDITAR

Mirando el enlace amit proporcionado, es posible implementar una inicialización de matriz con un valor predeterminado, en tiempo constante. Así que supongo que finalmente depende de la JVM. Podría hacer una evaluación comparativa aproximada para ver si este es el caso.

Un pequeño punto de referencia sin profesionales en 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)); } 

dio el siguiente resultado:

 big:6133612 small:6159 

así que supongo que O (n). por supuesto, no es suficiente para estar seguro, pero es una pista.

Estoy bastante seguro de que es O (n), ya que la memoria se inicializa cuando se asigna la matriz. No debe ser mayor que O (n), y no veo la forma de hacerlo menos que O (n), por lo que parece ser la única opción.

Para más detalles, Java inicializa las matrices en la asignación. No hay forma de poner a cero una región de memoria sin recorrerla, y el tamaño de la región determina el número de instrucciones. Por lo tanto, el límite inferior es O (n). Además, no tendría sentido utilizar un algoritmo de reducción a cero más lento que lineal, ya que hay una solución lineal, por lo que el límite superior debe ser O (n). Por lo tanto, O (n) es la única respuesta que tiene sentido.

Sin embargo, solo por diversión, imagina una pieza extraña de hardware donde el sistema operativo tiene control sobre la energía de las regiones individuales de la memoria y puede poner a cero una región desconectando la alimentación y volviendo a encenderla. Parece que sería O (1). Pero una región solo puede ser tan grande antes de que desaparezca la utilidad (no querría perder todo), por lo que pedir poner a cero una región seguirá siendo O (n) con un divisor grande.

Vamos a probarlo.

 class ArrayAlloc { static long alloc(int n) { long start = System.nanoTime(); long[] var = new long[n]; long total = System.nanoTime() - start; var[n/2] = 8; return total; } public static void main(String[] args) { for(int i=1; i<100000000; i+=1000000) { System.out.println(i + "," + alloc(i)); } } } 

Y los resultados en mi computadora portátil Linux (i7-4600M @ 2.90GHz):

Tiempo tomado por la inicialización de una matriz java de tamaño n

Por lo tanto, parece claramente O(n) , pero también parece que cambia a un método más eficiente en alrededor de 5 millones de elementos.