Java: qual è il tempo di O grande per dichiarare una matrice di dimensione n?

Qual è il tempo di esecuzione della dichiarazione di una matrice di dimensione n in Java? Suppongo che ciò dipenderebbe dal fatto che la memoria sia zero sulla raccolta dei rifiuti (nel qual caso potrebbe essere O (1)) o sull’inizializzazione (nel qual caso dovrebbe essere O (n)).

È O(n) . Considera questo semplice programma:

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

Il bytecode generato è:

 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 } 

L’istruzione di dare un’occhiata è l’istruzione newarray (basta cercare newarray ). Dalle specifiche VM:

Un nuovo array i cui componenti sono di tipo atype e di lunghezza viene assegnato dall’heap raccolto. Un arrayref di riferimento a questo nuovo object array viene inserito nella pila degli operandi. Ciascuno degli elementi del nuovo array viene inizializzato sul valore iniziale predefinito per il tipo dell’array (§2.5.1).

Dal momento che ogni elemento viene inizializzato, ci vorrebbe O(n) tempo.

MODIFICARE

Osservando il collegamento fornito, è ansible implementare l’inizializzazione dell’array con un valore predefinito, in tempo costante. Quindi immagino che alla fine dipenda dalla JVM. Potresti fare un po ‘di benchmarking approssimativo per vedere se questo è il caso.

Un piccolo nessuno benchmark professionale su 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)); } 

ha dato il seguente risultato:

 big:6133612 small:6159 

quindi presumo O (n). certo, non è abbastanza per essere sicuro, ma è un suggerimento.

Sono abbastanza sicuro che sia O (n), poiché la memoria viene inizializzata quando viene assegnato l’array. Non dovrebbe essere superiore a O (n), e non vedo alcun modo per renderlo inferiore a O (n), quindi sembra l’unica opzione.

Per approfondire, Java inizializza gli array sull’assegnazione. Non c’è modo di azzerare una regione di memoria senza attraversarla, e la dimensione della regione determina il numero di istruzioni. Pertanto, il limite inferiore è O (n). Inoltre, non avrebbe senso usare un algoritmo di azzeramento più lento del lineare, poiché esiste una soluzione lineare, quindi il limite superiore deve essere O (n). Pertanto, O (n) è l’unica risposta che ha senso.

Solo per divertimento, però, immagina uno strano componente hardware in cui il sistema operativo ha il controllo sulla potenza delle singole regioni della memoria e può azzerare una regione sfogliando e poi accendendo. Sembra che sarebbe O (1). Ma una regione può essere così grande prima che l’utilità scompaia (non vorrebbe perdere tutto), quindi chiedere di azzerare una regione sarà ancora O (n) con un grosso divisore.

Cerchiamo di testarlo.

 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)); } } } 

E i risultati sul mio laptop Linux (i7-4600M @ 2.90GHz):

Tempo impiegato dall'inizializzazione di un array java di dimensione n

Quindi sembra chiaramente O(n) , ma sembra anche che passi a un metodo più efficiente a circa 5 milioni di elementi.