Cosa è più efficiente in termini di memoria e utilizzo della CPU: una serie di boolean s o un BitSet? Non vengono utilizzati metodi BitSet specifici, solo get/set/clear (==, =, Arrays.fill rispettivamente per un array).booleano [] rispetto a BitSet: che è più efficiente?
Da alcuni benchmark con Sun JDK 1.6 numeri primi di calcolo con un setaccio (meglio del 10 iterazioni per riscaldare, dare il compilatore JIT una possibilità, e escludere ritardi di programmazione casuale, Core 2 Duo T5600 1.83GHz):
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.
booleano [] è più efficiente della CPU tranne che per dimensioni molto grandi, dove sono pari. Ad esempio, per la dimensione 1 milione booleano [] è circa quattro volte più veloce (ad esempio 6ms vs 27ms), per dieci e cento milioni sono pari.
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 dovessi usare gli altri metodi (e, o, ecc.), Scoprirai che BitSet è più efficiente, in quanto non è necessario eseguire iterazioni su ogni elemento di un array; viene utilizzata invece la matematica bit a bit.
Memoria efficiente - probabilmente vero. CPU efficiente - sicuramente no. È quasi sempre meno efficiente eseguire due operazioni bit a bit (shift/e o shift/o) e fino a due accessi alla memoria (anche se molto probabilmente memorizzati nella cache) rispetto a un singolo accesso di memoria su x86. – EFraim
@EFraim: Riducendo la quantità di memoria utilizzata si aumenta la possibilità di avere tutto nella cache. Le mancanze nella cache sono molto costose. Non sarei affatto sorpreso di vedere questo fattore rendere BitArray più veloce. –
Ad esempio: un bitset supererebbe il valore booleano [] se l'intero set di bit si inserisce nella cache, ma non il valore booleano [] e sono richiesti accessi casuali. – Ron
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 non si sappia che è importante, è meglio scrivere il codice per essere chiari, configurarlo e quindi correggere le parti che sono lente o che consumano molta memoria.
È possibile farlo mentre si va. 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).
Dipende come sempre. Sì BitSet è più efficiente in termini di memoria, ma non appena si richiede l'accesso multithread, boolean [] potrebbe essere la scelta migliore. Ad esempio per il calcolo dei numeri primi si imposta solo il valore booleano su true e quindi non è proprio necessaria la sincronizzazione. Hans Boehm ha scritto un articolo su questo e la stessa tecnica può essere utilizzata per marcare i nodi nel grafico.
a condizione che il tuo array booleano non cresca, sarebbe sicuramente meglio per l'uso simultaneo. – Randolpho
Hai ancora bisogno di sincronizzazione per assicurarti che tutti i thread vedano ciò che hanno scritto gli altri thread. [Here] (http://jeremymanson.blogspot.de/2007/08/atomicity-visibility-and-ordering.html) è una buona introduzione. Mi piacerebbe leggere il giornale di Hans Boehm - peccato che il link sia morto. –
Penso di aver trovato il documento di Hans Boehm: http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf Risultato: non è necessaria la sincronizzazione. Speri solo che i thread vedano cosa hanno fatto gli altri. Non è un problema se non lo fanno, faranno semplicemente un lavoro doppio. Ma in pratica, le modifiche saranno generalmente visibili e l'algoritmo accelererà linearmente. –
Boolean[] utilizza circa 4-20 byte per valore booleano.boolean[] utilizza circa 1 byte per valore booleano.BitSet utilizza circa 1 bit per valore booleano.Le dimensioni della memoria potrebbero non costituire un problema, nel qual caso booleano [] potrebbe essere più semplice da codificare.
Nota che 1 bit per booleano nel BitSet è il valore asintotico. Sotto le copertine viene utilizzato un long [] quindi viene granulato in 64 bit chuncks. –
E 'opportuno menzionare che in genere è sufficiente il puntatore a 4 byte per valore. Perché è memorizzato nella cache. Tranne che tu usi esplicitamente il nuovo Boolean(); Ma ovviamente è molto più di booleano [] – keiki
Un po 'a sinistra della domanda, ma se lo spazio di archiviazione è un problema, è consigliabile esaminare Huffman compression. 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 es. {(2)0, (3)1, (1)0, (1)1, (1)0} e occupano più spazio. A seconda della struttura dei dati bit, è possibile ottenere alcuni vantaggi di archiviazione dal suo utilizzo, oltre BitSet.
Per quanto riguarda la memoria, la documentazione per un BitSet ha implicazioni piuttosto chiare.In particolare:
Ogni bit impostato ha una dimensione di corrente, che è il numero di bit di spazio attualmente in uso dal bit impostato. Si noti che la dimensione è correlata all'implementazione di di un set di bit, pertanto potrebbe cambiare con l'implementazione. La lunghezza di un bit di si riferisce alla lunghezza logica di un bit impostato ed è definita indipendentemente dall'implementazione.
L'origine per le classi di libreria Java è apertamente disponibile e si può facilmente check this for themselves. 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.
Venendo a SO e chiedendo se A è più veloce di B è sciocco per molte ragioni, tra cui, ma non certo limitato a:
So che questa è una vecchia domanda ma è venuta di recente; e credo che valga la pena aggiungere.
Puoi pubblicare il test? – basszero
Sospetto che alcune delle operazioni in stile BitSet (e, o, non) siano più veloci come BitSet anziché array. Vale la pena notare quali operazioni sono migliori. Il titolo sta per indurre in errore tutti a non utilizzare mai più un BitSet – basszero
Il test non utilizza le operazioni impostate ed è distorto rispetto alla scrittura. – starblue