java: Vector poco escaso
https://stackoverflow.com/questions/3040864
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Hay bibliotecas conocidas en Java para los vectores de poco escaso?
(¿Y hay directrices sobre cómo escasa es útil para usarlos vs java.util.BitSet ?)
Solución
El biblioteca potro tiene matrices dispersas (1D, 2D y 3D). También tiene una BitVector eficiente, con 1 bit por valor, en lugar de 8-bits como boolean[] hace.
Sin embargo, las matrices dispersas no son compatibles con los bits directamente - sólo dobles y objetos. Se podría envolver el 1D escaso doble matriz por maping índice de bit a los índices largos (bitIndex>>6) ya que cada largo tiene 64 bits, convert el doble recuperado a un valor largo crudo, y la manipulación uso bit para acceder a los bits de la recuperada de largo. Un poco de trabajo, pero ni de lejos tanto como la implementación del vector de escasa mismo. Una vez que el envoltorio está trabajando, es posible evitar la conversión de dobles a los largos, y poner en práctica una verdadera matriz escasa larga 1d utilizando el código fuente de Colt disponible para la matriz de doble 1D escasa como punto de partida.
EDIT: Más información. Los vectores Colt / matrices no requieren memoria inicialmente para el almacenamiento, suponiendo que todos los bits (largos) son inicialmente 0. El establecimiento de un valor en la memoria no-cero consume. Configuración de la parte posterior valor a 0 sigue consumiendo memoria, aunque la memoria para los valores cero se recupera periódicamente.
Si los bits son verdaderamente escasa, de manera que cada valor de largo copias sólo tiene un conjunto de bits, a continuación, la sobrecarga de almacenamiento será muy pobres, lo que requiere 64 bits por bits real almacenados. Pero como usted menciona caso típico es 20-40% escaso, entonces la sobrecarga será mucho menor, con el almacenamiento posiblemente no desperdiciado si los bits se agrupan en intervalos de, por ejemplo, bits de 0-100, a continuación, 1000-1100, y 2000-2200 (valores en hex.) En general, sólo 1/16 de la región se asigna a los bits, pero los medios de agrupamiento que los bits se almacenan sin espacio desperdiciado.
Otros consejos
TL; DR ir aquí eficiente aplicación Escaso BitSet en Java
Yo sé que esto es una cuestión "viejo", pero con la misma pregunta que me encontré con este post. Si bien las respuestas son buenas, yo estaba en última instancia, no está satisfecho. Después de una nueva excavación, creo que he encontrado la respuesta "definitiva" a la cuestión de BitSets dispersas en Java.
esta presentación el autor, el Dr. Bruce Haddon, analiza los esfuerzos de sus investigadores para crear un reemplazo de memoria altamente eficiente y de alto rendimiento para el estándar de Java BitSet.
Los enlaces originales a su presentación están muertos, pero en contacto con el Dr. Haddon y han conservado tanto el código como la presentación aquí:
https://github.com/brettwooldridge/SparseBitSet
No se puede recomendar la lectura de esta presentación más altamente. Es una lectura fascinante, incluso si usted no tiene interés en juegos poco escaso, es más acerca de la verdadera naturaleza de la resolución de problemas ...
Diapositivas: ¿Es Ciencias de la Computación, Ingeniería de Software, o la piratería ?
Si es realmente escasa (por ejemplo, menos del 1% de carga), a continuación, utilizando una tabla hash indexado por el índice de bits es probablemente bastante bueno; mera presencia o ausencia del índice en la tabla es todo lo que necesita saber si el bit es uno o cero, respectivamente.
Si la densidad es más de un pequeño porcentaje, se puede usar una tabla hash indexado por el índice de bits dividido por 64, y almacenar mucho palabras en la tabla hash que contiene bits reales. Bit N se establece si la tabla hash contiene el valor V para int (N / 64) y (V >> (N mod 64)) y 1 es cierto.
Estas dos respuestas supuesto de que desea optimizar el acceso aleatorio a los bits. Si desea optimizar el secuencial (u otro acceso) a los bits de índice, entonces es posible que desee una estructura de matriz dispersa, utilizando el mismo tipo de representación vector de bits de bajo nivel en función de la densidad esperada. Ver Sparse Matrices
Usted podría intentar de FastUtil AVL Árbol Mapa .
CERN COLT es ampliamente utilizado para el vector y el cálculo de la matriz, y tiene matrices dispersas, pero no se utiliza específicamente para vectores de bits.
Una tabla hash donde la mera presencia o ausencia de la llave le dice algo? Eso sería un hash se establece a continuación! Soy escéptico de la actuación de un conjunto (aunque sea hash) sobre el BitSet. Realmente depende de si la velocidad o la memoria es el principal impulsor.
Usted podría intentar la biblioteca JavaEWAH.
https://code.google.com/p/javaewah/
En función de su problema puede ser una buena opción.
(Es utilizado por Apache Colmena y otros.)
