¿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).booleano [] vs. BitSet: ¿Cuál es más eficiente?
Desde algunos puntos de referencia con Sun JDK 1.6 primos de computación con un tamiz (mejor de 10 iteraciones para calentar, dar el compilador JIT una oportunidad, y no incluyen retrasos en el calendario al azar, Core 2 Duo T5600 a 1,83 GHz):
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.
booleano [] es más eficiente en el uso de la CPU, excepto en el caso de 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, 6 ms frente a 27 ms), para diez y cien millones son parejos.
Creo que un BitSet ahorra más memoria y CPU, puede empacar internamente los bits en int, longs o tipos de datos nativos, mientras que boolean [] 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.
Memoria eficiente - probablemente cierto. Eficiencia de la CPU: ciertamente no. Casi siempre es menos eficiente realizar dos operaciones de bit a bit (shift/y/o shift/o) y hasta dos accesos de memoria (aunque muy probablemente en caché) que un solo acceso a la memoria en x86. – EFraim
@EFraim: al reducir la cantidad de memoria utilizada, aumenta la posibilidad de tener todo en caché. Los errores de caché son muy caros. No me sorprendería en absoluto que este factor haga que BitArray sea más rápido. –
Por ejemplo: un conjunto de bits superaría a boolean [] si todo el conjunto de bits cabe en el caché, pero no el booleano [], y se requería un acceso aleatorio. – Ron
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.
Puede hacerlo a medida que avanza. 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).
Depende de 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 utilizar para marcar nodos en el gráfico.
, siempre que su matriz booleana no crezca, sin duda sería mejor para el uso simultáneo. – Randolpho
Aún necesitará la sincronización para asegurarse de que todos los subprocesos vean lo que los otros subprocesos han escrito. [Aquí] (http://jeremymanson.blogspot.de/2007/08/atomicity-visibility-and-ordering.html) es una muy buena introducción. Me encantaría leer el artículo de Hans Boehm, lástima que el enlace esté muerto. –
Creo que encontré el documento de Hans Boehm: http://www.hpl.hp.com/techreports/2004/HPL-2004-209.pdf Resultado: no necesita sincronización. Solo espera que los hilos vean lo que otros han hecho. No es problema si no lo hacen, simplemente harán un trabajo duplicado. Pero en la práctica, los cambios generalmente serán visibles, y el algoritmo se acelerará linealmente. –
Boolean[] utiliza 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 podría no ser un problema para usted, en cuyo caso booleano [] podría ser más simple de codificar.
Tenga en cuenta que 1 bit por booleano en el BitSet es el valor asintótico. Debajo de las cubiertas se usa un largo [] por lo que se granula en trozos de 64 bits. –
Sería bueno mencionar que generalmente solo necesita el puntero de 4 bytes por valor. Porque está en la memoria caché. Excepto que usa explícitamente nuevo Boolean(); Pero, por supuesto, es mucho más que booleano [] – keiki
Un poco a la izquierda del campo de su pregunta, pero si el almacenamiento es una preocupación es posible que desee consultar Huffman compression. Por ejemplo, 00000001 podría ser comprimido por frecuencia a algo equivalente a {(7)0, (1)1}. Una cadena más "aleatorizada" 00111010 requeriría una representación más compleja, p. {(2)0, (3)1, (1)0, (1)1, (1)0}, y ocupan 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.
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 conjunto de bits. 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 es definida independientemente de la implementación.
La fuente de la librería de clases de Java está disponible públicamente y uno puede fácilmente check this for themselves. En particular:
The internal field corresponding to the serialField "bits".
89
90 private long[] words;
En cuanto a 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.
Llegando a SO y preguntando si A es más rápido que B es tonta por muchas razones, incluyendo pero sin duda no se limita a:
Sé que esta es una vieja pregunta pero surgió recientemente; y creo que esto vale la pena agregar
¿Puedes publicar tu prueba? – basszero
Sospecho que algunas de las operaciones de estilo BitSet (y, o, no) son más rápidas que BitSet en lugar de array. Vale la pena señalar qué operaciones son mejores. El título confundirá a todos para que nunca vuelvan a utilizar un BitSet – basszero
La prueba no utiliza operaciones de conjunto y está sesgada hacia la escritura. – starblue