Recientemente, en uno de los proyectos surgió un problema: existe un conjunto de conjuntos (Set) que deben almacenarse de manera eficiente en la RAM. Porque hay muchos conjuntos, pero poca memoria. Y tenemos que hacer algo al respecto.
Ya que el lenguaje en el que está escrito todo esto es C #, es decir, los matices. Es decir, el HashSet <int> estándar gasta 16 bytes para almacenar un número, el factor de relleno también afecta. Hay implementaciones más eficientes (escribiré sobre ellas algún día), pero por otro lado, puedes almacenar estúpidamente en matrices, 4 bytes por número (necesitas almacenar ints), lo cual es bastante eficiente. Pero, ¿se puede reducir aún más?
Debo decir de inmediato que no tengo respuesta sobre la mejor manera de hacerlo, quizás no exista, porque hay muchos factores asociados a las peculiaridades de la distribución de datos específicos. Pero hay ideas que compartiré: qué opciones hay para ahorrar memoria. También te recomiendo que pienses por ti mismo antes de leer el post, después de todo, este es un buen ejercicio para la mente. Para ser específico, formularé el problema de la siguiente manera:
Hay un conjunto de entradas únicas no negativas (32 bits). Se requiere almacenarlos de manera eficiente en RAM, desde las operaciones, creando un conjunto y obteniendo todos los elementos. No es necesario obtener elementos por índice, agregar nuevos o eliminarlos.
El artículo contendrá muchas letras y números y ni una sola imagen (a excepción de un gato empacado en el KDPV).
, , .. , . . - , - , . - , - .
, — , .
, : , . 10
Entonces, tenemos datos básicos: una matriz de entradas, 4 bytes (32 bits) por número. Nos basaremos en este indicador.
Para empezar, expresaré una idea brillante: para que un número ocupe menos de 32 bits en la memoria, es necesario almacenarlo utilizando menos bits. Buena idea, ¿eh? Y la gente obtiene fama y reconocimiento por esto. Así que peor soy.
Digresión lírica: hace unos años, especialistas de los ferrocarriles rusos descubrieron que si haces las ruedas redondas y del mismo tamaño, el tren va más rápido y más silencioso.
Separar números por tamaño
Una solución simple para comenzar: los números del 0 al 255 se pueden almacenar usando 1 byte por número, hasta 65536 con dos, hasta 16777216 con tres. De ahí la primera solución:
creamos 4 matrices, en una almacenamos números por 1 byte, en la otra por 2, en la tercera por 3, y lo que en la cuarta, propongo adivinar por nuestra cuenta.
Aplaude, y ya estamos ahorrando. ¿Pero por qué quedarse donde ha estado? ¡Usemos 32 matrices! Y almacenar números por 1, 2 ... bits. Se ha vuelto aún más económico.
Por otro lado, ¿qué es una matriz? Este es un puntero a un bloque de memoria (8 bytes), longitud y para C # también memoria para el objeto de matriz en sí (20 bytes). En total, cada arreglo nos cuesta 32 bytes (de hecho, en C #, un objeto toma al menos 24 bytes en incrementos de 8, de los cuales 20 bytes son para el objeto y 4 para lo que queda o es estúpido para la alineación). En adelante, cálculos para un sistema de 64 bits. Para 32 bits, los punteros son 2 veces menos, la alineación también es 4, por lo que casi todo es 2 veces más económico.
¿Para qué es este pasaje? Además, 32 matrices devorarán 1 KB de memoria solo para sí mismas. ¿Qué hacer al respecto? Y todo es simple: ¡almacenaremos estos 32 arreglos en un solo arreglo!
En el primer elemento almacenamos la longitud de una matriz de un bit, luego la matriz en sí, luego la longitud de dos bits, etc. Como resultado, solo hay 32 bytes de sobrecarga y almacenamiento eficiente.
Un lector curioso (siempre me ha gustado esta frase) puede notar un cierto problema: para almacenar números de un bit, primero gastamos 2 bits para la longitud (0, 1 o 2), y luego 2 bits para los números mismos. Pero solo puede gastar 2 bits: el primer bit es si hay un 0, el segundo es si hay un 1.
Acabamos de crear un mapa de bits . No puede preocuparse mucho y almacenar números del 0 al 255 usando este método - hay un número - 1, no - 0. Y gastar 32 bytes en él (8 bits en un byte * 32 = 256). Naturalmente, con cada nuevo valor, la efectividad de la carta comienza a disminuir. Aquellos. para almacenar todos los ints necesitamos 536870912 bytes ... Es demasiado. Entonces, cuándo detenerse en 256, 16, 65536 depende de los datos. Sea 256. Me gusta este número, es hermoso.
Aquellos. almacenamos los primeros 256 números con un mapa de bits, luego almacenamos la longitud de los números de cierta longitud en bits y los números mismos.
Pero mire lo que sucede: los números del 0 al 511 requieren 9 bits para almacenarse. Al mismo tiempo, somos números del 0 al 255, ya lo hemos guardado. Aquellos. en el rango de 9 bits no se puede encontrar el número 12. Solo 256 y más. Entonces, ¿por qué almacenarlos en 9 bits, si puede almacenar un número del 0 al 255 y luego agregar los 256 que faltan en su cabeza? ¡Guardado un bit más! Naturalmente, cada siguiente rango también será un poco más económico. ¡Estamos bien!
¿Qué más puedes hacer? Y puedes mirar los datos. Si son muy densos (1,2,3,5,6), entonces puede almacenar no los números en sí, sino aquellos que no existen (4). Aquellos. en lugar de almacenar 5 números condicionales, almacenaremos uno. Una regla simple: hay más de la mitad de ellos, mantenemos los que no existen, de lo contrario, viceversa. Donde almacenar ¡Y en longitud! Mire: para almacenar números de 10 bits de longitud, necesitamos 11 bits (porque de 0 a 1024, inclusive). Pero al mismo tiempo, los valores en 11 bits se pueden introducir en 2048, y usamos solo 1025. Así que almacenaremos: longitud positiva: almacenamos números. Negativo: almacenamos lo que no lo es. Sugiero que el lector haga un cálculo detallado él mismo como un ejercicio independiente (porque no estoy seguro de que todo encaje, así que pretenderé que es necesario).
Como resultado, obtuvimos: una matriz en la que los primeros 16 bytes son una máscara de bits para la presencia de números del 0 al 255, luego, la longitud con una indicación, almacenamos los números o su ausencia, los números en sí, la longitud de bits para el siguiente, etc.
Después de implementar esto, e incluso sin errores, creo que irá directamente al durke, los programadores posteriores que intenten comprender este código lo seguirán. Probemos algunas opciones más.
Pensamos en el orden
Mira. Tenemos una matriz. ¿Qué tiene él, a diferencia de muchos? Y tiene: el orden de los elementos. Esta es información adicional y aún no la hemos utilizado. ¿Qué puedes hacer al respecto?
Y no puede almacenar los elementos en sí, sino la diferencia entre ellos:
1,2,3,4,8 => 1,1,1,1,4
Ie. almacenamos el primero como está, el segundo: sumamos el valor del primero al segundo, etc. ¿Qué nos aporta? Y el hecho de que si ordenamos la matriz de antemano , nuestros valores en ella serán más pequeños en general y se pueden almacenar en menos bits.
Además, según la condición del problema, todos los elementos son diferentes, es decir todavía podemos restar uno de la diferencia para guardar bits:
1,2,3,4,8 => 1,1,1,1,4 => 1,0,0,0,3
Esto no es difícil, así que ¿por qué no? y no.
Pero ahora el problema salió. Porque Ahora no podemos almacenar números de forma independiente, sino solo en el mismo orden, entonces el método con una matriz y longitudes ya no es adecuado. Tienes que pensar en otra cosa, porque todos los números deben almacenarse en orden.
Almacene la longitud del número en bits antes del número en sí
No es una mala opción. El número toma de 1 a 32 bits, es decir para la longitud necesitamos 5 bits, y luego el número en sí. Por conveniencia, puede cortar los casos extremos (bueno, ¿por qué ahorraremos allí? ¡Centavos!), O viceversa, resaltarlos por separado; por ejemplo, si la longitud es 0, entonces significa el número 0, si la longitud es 1 - el número - 1, si la longitud es 2, entonces los siguientes 2 bit número 2,3,4,5 (ya sabemos que podemos cambiar a algo que no puede ser), etc.
¿O puede almacenar la longitud de un número en el mismo número?
Cantidad de longitud variable
No importa cómo seamos los primeros en hacer esta pregunta, existe una solución estándar. Se utiliza para almacenar cadenas en UTF-8 y en muchos otros lugares. El significado es simple.
Si el número es de 0 a 127 inclusive, lo almacenamos en 1 byte (aunque usamos solo 7 bits). Si hay más, establezca el octavo bit en 1 y use el siguiente byte de la misma manera (7 bits, faltan - casilla de verificación y siguiente). Aquellos. los números pequeños se almacenarán en un byte, un poco más - en dos, y así sucesivamente hasta 5.
Puedes decir - fuu ... acabamos de jugar con los bits, y luego los bytes se fueron, ¡no genial! Sí, no mola, por otro lado, trabajar con bytes sigue siendo más fácil que con bits, un poco menos de ahorro, pero la velocidad de trabajo es mayor y el código es más claro. Pero ... gastar un poco por byte de alguna manera no es muy bueno, ¿tal vez haya mejores soluciones?
Usando valores como banderas
Saltemos todo razonamiento y decidamos de inmediato. Lo almacenaremos de la siguiente manera:
- los números del 0 al 252 se almacenarán en un byte. Si hay más, entonces:
- si el número es de 252 a 252 + 256 = 508 establecemos el valor 252, y en el siguiente byte el número es 252 (sí, ya sabemos cómo cambiar valores)
- si de 252 + 256 a 252 + 256 + 65536, configure 253 y use los siguientes 2 bytes para almacenar el número en sí, una diferencia innecesaria
- si de 252 + 256 + 65536 a 252 + 256 + 65536 + 16777216, ponga 254 y 3 bytes
- de lo contrario, 255 y 4 bytes.
¿Es esta una buena forma? Todo es relativo. En un byte podemos enviar valores hasta 252, mientras que en VLQ solo hasta 127, pero solo 508 en 2 bytes y ya 16383 en VLQ. el método es bueno si sus números son lo suficientemente densos, y aquí ganaremos. Pero lo bueno del método es que se puede ajustar a diferentes rangos. Por ejemplo, si sabemos que la mayoría de los números van de 10,000 a 50,000, entonces siempre podemos almacenarlos en dos bytes, pero si sale un número grande, escribiremos 65535 y usaremos ya 4. De hecho, optimizamos el almacenamiento del rango requerido a costa de un almacenamiento ineficiente. innecesario.
Conclusión
Examinamos las principales formas de ahorrar memoria (de hecho, mi imaginación se ha agotado, pero no lo admitiré). Estas técnicas pueden combinarse, usarse para otras tareas y modificarse para adaptarse a la situación. ¿Cuál es la mejor técnica al final? Todo depende de tus datos. Tómalos y pruébalos. Afortunadamente, no es necesario implementar todo completamente a la vez. Es bastante fácil escribir código que simplemente evaluará la longitud. Y tras la valoración, ya implementa lo que te gustó.
No te olvides de la velocidad de todo esto: ¿estás listo para pasar mucho tiempo preparando datos o obteniéndolos? ¿Vale la pena comenzar una pelea con bits o no debería ir por debajo de los bytes? ¿Es suficiente optimizar situaciones frecuentes, dejando raras con una implementación ineficaz? ¿Es posible, dependiendo de los datos, utilizar diferentes métodos de almacenamiento (por ejemplo, es estúpido almacenar hasta 8 bytes en una matriz, ya que los costos secundarios devorarán toda la ganancia, y de 1 byte, generalmente se almacenan en una pseudo matriz de un elemento, número).
Además, unas palabras sobre la compresión: aquí no será muy eficaz. A los algoritmos de compresión les gustan mucho las repeticiones, pero no hay muchas de ellas aquí. Si toma un Zip condicional, que consiste en LZ77 + Huffman, es poco probable que salga algo útil con LZ77, pero Huffman puede intentar ahorrar bytes. Entonces Zip será medio inútil. Pero la velocidad bajará mucho, mucho.
Las situaciones en las que sabemos que tenemos muchos conjuntos y podemos almacenarlos todos juntos usando diferentes cortes aún no se han considerado en absoluto. Aquí lo confieso, no estoy seguro de que funcione. Inmediatamente no se me ocurrieron opciones. Pero me di cuenta de que sería difícil. Sin embargo, es posible que tenga opiniones diferentes.
Así que comparte tus ideas en los comentarios, tal vez me perdí algún elefante obvio que ahorrará aún más bytes y obtendrá un resultado tal que las amas de casa del anuncio de detergente (que es suficiente para una gota) ¡nos envidiarán a todos!