java - boolean[] vs. BitSet: ¿Cuál es más eficiente?

arrays performance

Question

¿Qué es más eficiente en términos de uso de memoria y CPU, una matriz de boolean o un BitSet? No se utilizan métodos específicos de BitSet, solo get / set / clear (==, =, Arrays.fill respectivamente para una matriz).

Answer 1

Aquí puede ver una referencia de memoria / tiempo comparando una matriz triangular booleana [] [] versus una matriz triangular BitSet [].

Creo, establezco y leo los valores (tamaño * (tamaño-1) / 2) y comparo el uso de memoria y el tiempo ...

Espero que esto ayude...

Aquí el código ... (solo un código de prueba sucia, lo siento;)

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

Answer 2

Creo que un BitSet es más eficiente en cuanto a la memoria y la CPU, puede empaquetar internamente los bits en int, longs o tipos de datos nativos, mientras que un booleano [] requiere un byte para cada bit de datos. Además, si tuviera que usar los otros métodos (y, o, etc.), encontraría que el BitSet es más eficiente, ya que no hay necesidad de iterar a través de cada elemento de una matriz; En cambio, se usa la matemática a nivel de bit.

Answer 3

Depende como siempre Sí, BitSet es más eficiente en cuanto a la memoria, pero tan pronto como necesite acceso de subprocesamiento booleano [] podría ser la mejor opción. Por ejemplo, para calcular números primos, solo establece el booleano en verdadero y, por lo tanto, realmente no necesita sincronización. Hans Boehm ha escrito un artículo sobre esto y la misma técnica se puede usar para marcar nodos en el gráfico.

Answer 4

Desde algunos puntos de referencia con primers informáticos Sun JDK 1.6 con un tamiz (la mejor de las 10 iteraciones para calentar, dé una oportunidad al compilador JIT, y excluya las demoras de programación aleatorias, Core 2 Duo T5600 1.83GHz):

BitSet es más eficiente en cuanto a la memoria que boolean [], excepto para tamaños muy pequeños. Cada booleano en la matriz toma un byte. Los números de runtime.freeMemory () son un poco confusos para BitSet, pero menos.

boolean [] es más eficiente en la CPU, excepto en los tamaños muy grandes, donde son parejos. Por ejemplo, para el tamaño 1 millón booleano [] es aproximadamente cuatro veces más rápido (por ejemplo, 6ms frente a 27ms), para diez y cien millones son parejos.

Answer 5

En cuanto a la memoria, la documentación de un BitSet tiene implicaciones bastante claras. En particular:

Cada conjunto de bits tiene un tamaño actual, que es el número de bits de espacio actualmente en uso por el bit establecido. Tenga en cuenta que el tamaño está relacionado con la implementación de un conjunto de bits, por lo que puede cambiar con la implementación. La longitud de un conjunto de bits se refiere a la longitud lógica de un conjunto de bits y se define independientemente de la implementación.

La fuente de las clases de la biblioteca de Java está abiertamente disponible y uno puede verificar esto fácilmente por sí mismo . En particular:

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

En cuanto a la velocidad; depende de lo que uno está haciendo. En general, no pienses en la velocidad antes de tiempo; use la herramienta que tenga más sentido semánticamente y conduzca al código más claro. Optimice solo después de observar que no se cumplen los requisitos de rendimiento e identificando cuellos de botella.

Llegar al SO y preguntar si A es más rápido que B es una tontería por muchas razones, que incluyen pero no se limitan a:

1. Depende de la aplicación, a la que nadie responde generalmente tiene acceso. Analice y perfile en el contexto en el que se utiliza. Asegúrese de que sea un cuello de botella que realmente valga la pena optimizar.
2. Preguntas como esta que preguntan acerca de la velocidad generalmente muestran que OP piensa que se preocupan por la eficiencia pero no estaban dispuestos a crear perfiles y no definieron los requisitos de desempeño. Debajo de la superficie, por lo general, se trata de una bandera roja que indica que el PO se dirige por el camino equivocado.

Sé que esta es una vieja pregunta, pero surgió recientemente; y creo que esto vale la pena agregar

Answer 6

Pasar de Java a la CPU es totalmente específico de VM. Por ejemplo, solía ser que un booleano se implementaba realmente como un valor de 32 bits (muy probablemente sea cierto hasta el día de hoy).

A menos que sepa que va a importar, es mejor escribir el código para que sea claro, perfilarlo y luego arreglar las partes que son lentas o que consumen mucha memoria.

Puedes hacer esto sobre la marcha. Por ejemplo, una vez decidí no llamar a .intern () en Strings porque cuando ejecuté el código en el generador de perfiles, lo desaceleró demasiado (a pesar de que usaba menos memoria).

Answer 7

Un poco a la izquierda del campo de su pregunta, pero si el almacenamiento es una preocupación es posible que desee examinar la compresión de Huffman . Por ejemplo, 00000001 podría comprimirse por frecuencia a algo equivalente a {(7)0, (1)1} . Una cadena más "aleatorizada" 00111010 requeriría una representación más compleja, por ejemplo, {(2)0, (3)1, (1)0, (1)1, (1)0} , y ocuparía más espacio. Dependiendo de la estructura de los datos de su bit, puede obtener algún beneficio de almacenamiento de su uso, más allá de BitSet .

Answer 8

• Boolean[] usa alrededor de 4-20 bytes por valor booleano.
• boolean[] usa aproximadamente 1 byte por valor booleano.
• BitSet usa aproximadamente 1 bit por valor booleano.

El tamaño de la memoria puede no ser un problema para usted, en cuyo caso booleano [] podría ser más simple de codificar.