Perché preoccuparsi di usare ArrayList (capacità int)?

Question

Quindi praticamente ogni domanda relativa alla capacità in ArrayList è come usarla o (stranamente) accedervi e sono abbastanza familiare con quell'informazione. Cosa mi interessa sapere se valga davvero la pena usare il costruttore ArrayList che imposta la capacità se si sa o si ha una vaga idea di quanti oggetti ci saranno in ArrayList?

Esistono benchmark completi che mettono a confronto il tempo necessario per utilizzare semplicemente l'aggiunta ingenua di elementi a un ArrayList rispetto alla preimpostazione della capacità di un ArrayList?

Answer 1

Ovviamente per qualsiasi applicazione specifica è necessario testare eventuali adeguamenti delle prestazioni per determinare se sono effettivamente ottimizzazioni (e se sono effettivamente necessarie), ma ci sono alcune volte che l'impostazione della capacità in modo esplicito può essere utile. Ad esempio:

• Si sta creando un numero molto elevato di elenchi di array, molti dei quali saranno molto piccoli. In questo caso, potresti voler impostare la capacità iniziale molto bassa e/o ritagliare la capacità ogni volta che hai finito di compilare un determinato array. (In questo caso, l'ottimizzazione è meno una questione di velocità rispetto all'utilizzo della memoria, ma si noti che l'elenco stesso ha sovraccarico della memoria, così come l'array in esso contenuto, quindi in questo tipo di situazione è probabile che sia meglio riprogettarlo in un modo da avere un minor numero di liste.)
• si sta creando una matrice-list di un molto grandi dimensioni note, e si desidera il tempo di aggiungere ogni elemento essere molto piccolo (forse perché ogni volta che si aggiungi un elemento, devi inviare una risposta a una fonte di dati esterna). (La crescita geometrica predefinita richiede tempo di ammortamento ammortizzato: una volta ogni tanto si incorre in una pena enorme, in modo che la prestazione media complessiva sia completamente soddisfacente, ma se si preoccupano degli inserimenti individuali presi singolarmente, potrebbe non essere abbastanza buono .)

Answer 2

ArrayList interni utilizza matrici semplici per memorizzare i suoi elementi, se il numero di elementi supera la capacità dell'array sottostante, è necessario uno sforzo di ridimensionamento. Quindi, nel caso in cui tu sappia quanti oggetti contiene il tuo Elenco, puoi informare ArrayList di usare un array della dimensione necessaria in modo che la logica di ridimensionamento non sia necessaria o eseguita.

Answer 3

Non ho nulla di sostanziale da aggiungere alla risposta di ruakh, ma ecco una rapida funzione di test. Mantengo un progetto di scarto in giro per scrivere piccoli test come questi. Regola SourceSize su qualcosa di rappresentativo dei tuoi dati e puoi farti un'idea approssimativa dell'entità dell'effetto. Come mostrato, ho visto un fattore di 2 tra di loro.

import java.util.ArrayList; 
import java.util.Random; 

public class ALTest { 
    public static long fill(ArrayList<Byte> al, byte[] source) { 
     long start = System.currentTimeMillis(); 
     for (byte b : source) { 
      al.add(b); 
     } 
     return System.currentTimeMillis()-start; 
    } 
    public static void main(String[] args) { 
     int sourceSize = 1<<20; // 1 MB 
     int smallIter = 50; 
     int bigIter = 4; 

     Random r = new Random(); 
     byte[] source = new byte[sourceSize]; 
     for (int i = 0;i<bigIter;i++) { 
      r.nextBytes(source); 
      { 
       long time = 0; 
       for (int j = 0;j<smallIter;j++) { 
        ArrayList<Byte> al = new ArrayList<Byte>(sourceSize); 
        time += fill(al,source); 
       } 
       System.out.print("With: "+time+"ms\t"); 
      } 
      { 
       long time = 0; 
       for (int j = 0;j<smallIter;j++) { 
        ArrayList<Byte> al = new ArrayList<Byte>(); 
        time += fill(al,source); 
       } 
       System.out.print("Without: "+time+"ms\t"); 
      } 
      { 
       long time = 0; 
       for (int j = 0;j<smallIter;j++) { 
        ArrayList<Byte> al = new ArrayList<Byte>(); 
        time += fill(al,source); 
       } 
       System.out.print("Without: "+time+"ms\t"); 
      } 
      { 
       long time = 0; 
       for (int j = 0;j<smallIter;j++) { 
        ArrayList<Byte> al = new ArrayList<Byte>(sourceSize); 
        time += fill(al,source); 
       } 
       System.out.print("With: "+time+"ms"); 
      } 
      System.out.println(); 
     } 
    } 
} 

uscita:

With: 401ms Without: 799ms Without: 731ms With: 347ms 
With: 358ms Without: 744ms Without: 749ms With: 342ms 
With: 348ms Without: 719ms Without: 739ms With: 347ms 
With: 339ms Without: 734ms Without: 774ms With: 358ms