booleano contro BitSet: che è più efficiente?

Cosa è più efficiente in termini di memoria e utilizzo della CPU: una serie di boolean o di BitSet? Non vengono utilizzati metodi BitSet specifici, solo get / set / clear (==, =, Arrays.fill rispettivamente per un array).

Da alcuni benchmark con primari di calcolo Sun JDK 1.6 con un setaccio (migliore di 10 iterazioni per il riscaldamento, dare al compilatore JIT una possibilità ed escludere ritardi di schedulazione casuali, Core 2 Duo T5600 1.83 GHz):

BitSet ha una memoria più efficiente di boolean [] tranne che per dimensioni molto piccole. Ogni booleano nell’array prende un byte. I numeri di runtime.freeMemory () sono un po ‘confusi con BitSet, ma meno.

boolean [] è più efficiente della CPU tranne che per dimensioni molto grandi, dove sono quasi pari. Ad esempio, per la dimensione 1 milione booleano [] è circa quattro volte più veloce (es. 6ms vs 27ms), per dieci e cento milioni sono pari.

  • Boolean[] utilizza circa 4-20 byte per valore booleano.
  • boolean[] usa circa 1 byte per valore booleano.
  • BitSet utilizza circa 1 bit per valore booleano.

Le dimensioni della memoria potrebbero non essere un problema per te, nel qual caso booleano [] potrebbe essere più semplice da codificare.

Un po ‘a sinistra della tua domanda, ma se lo spazio di archiviazione è un problema, potresti voler esaminare la compressione di Huffman . Ad esempio, 00000001 potrebbe essere ridotto per frequenza a qualcosa di equivalente a {(7)0, (1)1} . Una stringa più “randomizzata” 00111010 richiederebbe una rappresentazione più complessa, ad esempio {(2)0, (3)1, (1)0, (1)1, (1)0} e occuperà più spazio. A seconda della struttura dei dati bit, è ansible che alcuni vantaggi dello storage BitSet dal suo utilizzo, oltre a BitSet .

Per quanto riguarda la memoria, la documentazione di un BitSet ha implicazioni piuttosto chiare. In particolare:

Ogni bit impostato ha una dimensione corrente, che è il numero di bit di spazio attualmente in uso dal bit impostato. Si noti che la dimensione è correlata all’implementazione di un set di bit, quindi potrebbe cambiare con l’implementazione. La lunghezza di un bit impostato si riferisce alla lunghezza logica di un bit impostato e viene definita indipendentemente dall’implementazione.

L’origine per le classi di librerie Java è apertamente disponibile e si può facilmente controllare da sé . In particolare:

 The internal field corresponding to the serialField "bits". 89 90 private long[] words; 

Per quanto riguarda la velocità; dipende da cosa si sta facendo. In generale, non pensare alla velocità in anticipo; usa lo strumento che ha più senso semanticamente e porta al codice più chiaro. Ottimizza solo dopo aver osservato che i requisiti di prestazione non sono soddisfatti e identificando i colli di bottiglia.

Venire a SO e chiedere se A è più veloce di B è sciocco per molte ragioni, incluse ma certamente non limitate a:

  1. Dipende dall’applicazione, a cui in genere nessuno ha accesso. Analizzalo e profilalo nel contesto in cui viene utilizzato. Assicurati che sia un collo di bottiglia che vale la pena ottimizzare.
  2. Domande come questa che chiedono informazioni sulla velocità in generale mostrano che l’OP pensa che si preoccupino dell’efficienza ma non è disposto a profilare e non ha definito i requisiti di prestazione. Sotto la superficie, di solito c’è una bandiera rossa che l’OP si trova nella direzione sbagliata.

So che questa è una vecchia domanda, ma è arrivata di recente; e credo che valga la pena aggiungere.

Dipende come sempre. Sì BitSet è più efficiente in termini di memoria, ma non appena richiedi l’accesso multithread, boolean [] potrebbe essere la scelta migliore. Ad esempio, per il calcolo dei numeri primi si imposta il valore booleano su true e quindi non è necessario sincronizzare. Hans Boehm ha scritto un articolo su questo e la stessa tecnica può essere usata per marcare i nodes nel grafico.

Passare da Java a CPU è totalmente VM specifico. Ad esempio, un booleano è stato effettivamente implementato come valore a 32 bit (probabilmente è vero fino ad oggi).

A meno che tu non sappia che sta per importare, è meglio scrivere il codice per essere chiari, profilarlo e quindi correggere le parti che sono lente o che consumano molta memoria.

Puoi farlo mentre vai. Ad esempio, una volta ho deciso di non chiamare .intern () su Stringhe perché quando eseguivo il codice nel profiler lo rallentava troppo (nonostante usassi meno memoria).

Qui puoi vedere un benchmark Memoria / Tempo confrontando una matrice triangular bola [] [] con la matrice triangular BitSet [].

Creo, imposta e leggo i valori (size * (size-1) / 2) e confronta l’utilizzo della memoria e il tempo …

inserisci la descrizione dell'immagine qui

inserisci la descrizione dell'immagine qui

Spero che questo aiuto …

Ecco il codice … (solo un codice di test molto disinvolto, mi dispiace;)

 import java.util.BitSet; import java.util.Date; public class BooleanBitSetProfiler { Runtime runtime; int sum = 0; public void doIt() { runtime = Runtime.getRuntime(); long[][] bitsetMatrix = new long[30][2]; long[][] booleanMatrix = new long[30][2]; int size = 1000; for (int i = 0; i < booleanMatrix.length; i++) { booleanMatrix[i] = testBooleanMatrix(size); bitsetMatrix[i] = testBitSet(size); size += 2000; } int debug = 1; for (int j = 0; j < booleanMatrix.length; j++){ System.out.print(booleanMatrix[j][0] + ";"); } System.out.println(); for (int j = 0; j < booleanMatrix.length; j++){ System.out.print(booleanMatrix[j][1] + ";"); } System.out.println(); for (int j = 0; j < bitsetMatrix.length; j++){ System.out.print(bitsetMatrix[j][0] + ";"); } System.out.println(); for (int j = 0; j < bitsetMatrix.length; j++){ System.out.print(bitsetMatrix[j][1] + ";"); } System.out.println(); } private long memory () { return runtime.totalMemory() - runtime.freeMemory(); } private long[] testBooleanMatrix(int size) { runtime.gc(); long startTime = new Date().getTime(); long startMemory = memory(); boolean[][] matrix = new boolean[size][]; for (int i = 0; i < size; i++) { matrix[i] = new boolean[size - i - 1]; } long creationMemory = memory(); long creationTime = new Date().getTime(); for (int i = 0; i < size; i++) { for (int j = 0; j < matrix[i].length; j++) { matrix[i][j] = i % 2 == 0; } } long setMemory = memory(); long setTime = new Date().getTime(); for (int i = 0; i < size; i++) { for (int j = 0; j < matrix[i].length; j++) { if (matrix[i][j]) sum++; } } long readTime = new Date().getTime(); System.out.println("Boolean[][] (size " + size + ")"); System.out.println("Creation memory " + printMem(creationMemory-startMemory) + ", set memory " + printMem(setMemory-startMemory)); System.out.println("Creation time " + printTime(creationTime-startTime) + ", set time " + printTime(setTime - creationTime) + " read time " + printTime(readTime - setTime) + "\n"); runtime.gc(); return new long[]{(setMemory-startMemory)/(1024*1024), (readTime-startTime)}; } private long[] testBitSet(int size) { runtime.gc(); long startTime = new Date().getTime(); long startMemory = memory(); BitSet[] matrix = new BitSet[size]; for (int i = 0; i < size; i++) { matrix[i] = new BitSet(size - i - 1); } long creationMemory = memory(); long creationTime = new Date().getTime(); for (int i = 0; i < size; i++) { for (int j = 0; j < matrix[i].size(); j++) { matrix[i].set(j, (i % 2 == 0)); } } long setMemory = memory(); long setTime = new Date().getTime(); for (int i = 0; i < size; i++) { for (int j = 0; j < matrix[i].size(); j++) { if (matrix[i].get(j)) sum++; } } long readTime = new Date().getTime(); System.out.println("BitSet[] (size " + size + ")"); System.out.println("Creation memory " + printMem(creationMemory-startMemory) + ", set memory " + printMem(setMemory-startMemory)); System.out.println("Creation time " + printTime(creationTime-startTime) + ", set time " + printTime(setTime - creationTime) + " read time " + printTime(readTime - setTime) + "\n"); runtime.gc(); return new long[]{(setMemory-startMemory)/(1024*1024), (readTime-startTime)}; } private String printMem(long mem) { mem = mem / (1024*1024); return mem + "MB"; } private String printTime(long milis) { int seconds = (int) (milis / 1000); milis = milis % 1000; return seconds > 0 ? seconds + "s " + milis + "ms" : milis + "ms"; } } 

Credo che un BitSet sia più efficiente in termini di memoria e CPU, è in grado di impacchettare internamente i bit in int, long o tipi di dati nativi, mentre un booleano [] richiede un byte per ogni bit di dati. Inoltre, se si utilizzassero gli altri metodi (e, o, ecc.), Si scoprirà che il BitSet è più efficiente, in quanto non è necessario eseguire iterazioni su ogni elemento di un array; viene utilizzata invece la matematica bit a bit.