La maggior parte della memoria efficiente per far crescere un array in Java?

Question

Non sono troppo preoccupato dell'efficienza temporale (l'operazione sarà rara), ma piuttosto dell'efficienza della memoria: È possibile far crescere l'array senza disporre temporaneamente di tutti i valori due volte?

Esiste un modo più efficiente di far crescere un array di grandi dimensioni piuttosto che crearne uno nuovo e copiare tutti i valori? Come, concatenandolo con uno nuovo?

Che dire di avere array di dimensioni fisse memorizzati in un altro array e riallocarlo/copiarne uno di livello superiore? Questo lascerebbe i valori attuali sul posto?

Sono a conoscenza di ArrayList, ma ho bisogno di molto controllo sull'accesso all'array e l'accesso deve essere molto veloce. Ad esempio, penso di preferire a[i] a al.get(i).

Il motivo principale per cui mi interessa è che la matrice in questione (o un numero di tali matrici) potrebbe benissimo occupare una porzione abbastanza grande di memoria principale che la solita strategia di creare una copia di dimensioni doppie prima di scartare la l'originale potrebbe non funzionare. Ciò potrebbe significare che devo riconsiderare la strategia generale (o aumentare i miei consigli sull'hardware).

Answer 1

C'è un modo più efficiente per crescere una vasta gamma di crearne uno nuovo e copia su tutto i valori? Mi piace, concatenandolo con uno nuovo?

No. E probabilmente non c'è linguaggio, che garantisce che la crescita di un array avverrà sempre senza copiare. Una volta che si assegna lo spazio per l'array e si fa qualcos'altro, molto probabilmente si avranno altri oggetti in memoria subito dopo la fine dell'array. A quel punto, è fondamentalmente impossibile far crescere l'array senza copiarlo.

Avere degli array a dimensione fissa memorizzati in un altro array e riallocare /copia che cima-livello uno? Sarebbe quello lasciare i valori attuali sul posto?

Si intende un array di matrici e lo si considera come un unico array consistente in una concatenazione degli array sottostanti? Sì, funzionerebbe (l'approccio "simulando facendo indiretta"), come in Java, Object[][] è semplicemente un array di puntatori alle istanze Object[].

Answer 2

Dai un'occhiata allo System.arraycopy.

Answer 3

per quanto ne so l'unico modo di crescere o ridurre una matrice sta facendo uno System.arraycopy

/** 
    * Removes the element at the specified position in this list. 
    * Shifts any subsequent elements to the left (subtracts one from their 
    * indices). 
    * 
    * @param index the index of the element to removed. 
    * @return the element that was removed from the list. 
    * @throws IndexOutOfBoundsException if index out of range <tt>(index 
    *  &lt; 0 || index &gt;= length)</tt>. 
    */ 
    public static <T> T[] removeArrayIndex(T[] src, int index) { 
     Object[] tmp = src.clone(); 

     int size = tmp.length; 
     if ((index < 0) && (index >= size)) { 
      throw new ArrayIndexOutOfBoundsException(index); 
     } 

     int numMoved = size - index - 1; 
     if (numMoved > 0) { 
      System.arraycopy(tmp, index + 1, tmp, index, numMoved); 
     } 
     tmp[--size] = null; // Let gc do its work 

     return (T[]) Arrays.copyOf(tmp, size - 1); 
    } 

    /** 
    * Inserts the element at the specified position in this list. 
    * Shifts any subsequent elements to the rigth (adds one to their indices). 
    * 
    * @param index the index of the element to inserted. 
    * @return the element that is inserted in the list. 
    * @throws IndexOutOfBoundsException if index out of range <tt>(index 
    *  &lt; 0 || index &gt;= length)</tt>. 
    */ 
    public static <T> T[] insertArrayIndex(T[] src, Object newData, int index) { 
     Object[] tmp = null; 
     if (src == null) { 
      tmp = new Object[index+1]; 
     } else { 
      tmp = new Object[src.length+1]; 

      int size = tmp.length; 
      if ((index < 0) && (index >= size)) { 
       throw new ArrayIndexOutOfBoundsException(index); 
      } 

      System.arraycopy(src, 0, tmp, 0, index); 
      System.arraycopy(src, index, tmp, index+1, src.length-index); 
     } 

     tmp[index] = newData; 

     return (T[]) Arrays.copyOf(tmp, tmp.length); 
    }  

Answer 4

Il modo migliore per avere un ridimensionamento dinamico 'allineamento' o un elenco di elementi è quello di utilizzare un ArrayList.

Java ha già incorporato algoritmi di ridimensionamento molto efficienti in quella struttura di dati.

Tuttavia, se è necessario ridimensionare il proprio array, è preferibile utilizzare System.arraycopy() o Arrays.copyOf().

Arrays.copyOf() può più semplicemente essere utilizzato in questo modo:

int[] oldArr; 
int newArr = Arrays.copyOf(oldArr, oldArr.length * 2); 

questo vi darà una nuova matrice con gli stessi elementi della vecchia serie, ma ora con una camera di riserva.

La classe Arrays in generale ha molti ottimi metodi per gestire gli array.

anche

E 'importante assicurarsi che non si sta solo crescendo il tuo array di un elemento ogni volta che viene aggiunto un elemento. È meglio implementare alcune strategie in cui è necessario ridimensionare l'array ogni tanto. Il ridimensionamento degli array è un'operazione costosa.

Answer 5

Ovviamente, il bit importante qui non è se si concatenano gli array o li si copia; la cosa più importante è la strategia di crescita dell'array. Non è difficile vedere che un ottimo modo per far crescere un array raddoppia sempre le sue dimensioni quando diventa pieno. In questo modo, cambierai il costo dell'aggiunta di un elemento a O (1) poiché la fase di crescita effettiva si verificherà solo relativamente raramente.

Answer 6

Gli array sono di dimensioni costanti, quindi non c'è modo di farli crescere.Puoi copiarli solo usando System.arrayCopy per essere efficiente.

---

ArrayList fa esattamente quello che ti serve. È ottimizzato molto meglio di quanto chiunque potrebbe fare, a meno di non dedicare molto tempo ad esso. Usa internamente System.arrayCopy.

---

Ancora di più, se si dispone di alcuni enormi fasi in cui è necessario l'elenco di crescere/ridurre, e altri in cui non cresce/ridurre e fare migliaia di lettura o scrittura in esso. Supponiamo anche che tu abbia un enorme bisogno di prestazioni, che tu abbia dimostrato che ArrayList è troppo lento durante la lettura/scrittura. Si può ancora usare ArrayList per una fase enorme e convertirlo in un array per l'altro. Nota questo sarebbe efficace solo se le tue fasi di applicazione sono enormi.

Answer 7

Heres un punto di riferimento di tempo impiegato per aggiungere e rimuovere elementi da una collezione/arraylist/vettore

Answer 8

L'array è di grandi dimensioni o si fa riferimento a ReferenceTypes di grandi dimensioni?

C'è una differenza tra una matrice di un PrimitiveType con miliardi di elementi e una matrice con migliaia di elementi, ma si riferiscono a istanze di classi di grandi dimensioni.

int[] largeArrayWithSmallElements = new int[1000000000000]; 
myClass[] smallArrayWithLargeElements = new myClass[10000]; 

Edit:

Se si dispone di considerazioni sulle prestazioni utilizzando ArrayList, io posso assicurare che si esibirà più o meno esattamente come Array indicizzazione.

E se l'applicazione ha risorse di memoria limitate, è possibile provare a giocare con la dimensione iniziale di ArrayList (uno dei suoi costruttori).

Per un'efficienza ottimale della memoria, è possibile creare una classe contenitore con ArrayList di array.

Qualcosa di simile:

class DynamicList 
{ 
    public long BufferSize; 
    public long CurrentIndex; 

    ArrayList al = new ArrayList(); 

    public DynamicList(long bufferSize) 
    { 
     BufferSize = bufferSize; 

     al.add(new long[BufferSize]); 
    } 

    public void add(long val) 
    { 
     long[] array; 

     int arrayIndex = (int)(CurrentIndex/BufferSize); 

     if (arrayIndex > al.size() - 1) 
     { 
      array = new long[BufferSize]; 
      al.add(array); 
     } 
     else 
     { 
      array = (long[])al.get(arrayIndex); 
     } 

     array[CurrentIndex % BufferSize] = val; 
    } 

    public void removeLast() 
    { 
     CurrentIndex--; 
    } 

    public long get(long index) 
    { 
     long[] array; 

     int arrayIndex = (int)(index/BufferSize); 

     if (arrayIndex < al.size()) 
     { 
      array = (long[])al.get(arrayIndex); 
     } 
     else 
     { 
      // throw Exception 
     } 

     return array[index % BufferSize]; 
    } 
} 

(il mio Java è arrugginito, quindi per favore abbiate pazienza con me ...)

Answer 9

Che ne dite di una lista collegata accoppiato con una matrice che contiene solo riferimenti.

L'elenco collegato può crescere senza dover allocare nuova memoria, l'array garantisce un accesso facile. E ogni volta che la matrice diventa piccola, puoi semplicemente spazzare l'intero array e ricostruirlo di nuovo dall'elenco collegato.

Answer 10

Un modo di fare questo è avere una lista collegata di nodi di matrice. Questo è piuttosto complesso ma la premessa è questa:

Si dispone di un elenco collegato e ogni nodo all'interno della lista fa riferimento a una matrice. In questo modo, il tuo array può crescere senza mai copiare. Per crescere devi solo aggiungere ulteriori nodi alla fine. Pertanto l'operazione di crescita "costosa" si verifica solo ogni operazione M in cui M è la dimensione di ciascun nodo. Certo, questo presuppone che si aggiunga sempre alla fine e non si rimuove.

L'inserimento e la rimozione in questa struttura sono piuttosto complicati, ma se riesci a evitarli è perfetto.

L'unica perdita con questa struttura (ignorando l'inserimento e la cancellazione) è con l'ottiene. Il risultato sarà leggermente più lungo; l'accesso al nodo corretto richiede l'accesso al nodo corretto all'interno dell'elenco collegato e quindi il recupero lì. Se ci sono molti accessi nel mezzo, questo può essere lento, tuttavia ci sono trucchi per accelerare le liste collegate.

Answer 11

Hai guardato allo GNU Trove per raccolte java altamente efficienti? Le loro collezioni memorizzano le primitive direttamente per un utilizzo della memoria molto migliore.

Answer 12

"Posso far crescere la matrice senza dover temporaneamente tutti i valori due volte?"

Anche se si copia gli array, si avranno solo tutti i valori una volta. A meno che non chiami clone() sui tuoi valori, questi vengono passati per riferimento nel nuovo array.

Se i tuoi valori sono già in memoria, l'unica spesa aggiuntiva per la memoria durante la copia in un nuovo array è l'assegnazione del nuovo array Object [], che non richiede molta memoria, in quanto è solo un elenco di puntatori valutare oggetti