algorithm - udc - tabla posicional de los numeros

Clasificación de 1 millón de números de 8 dígitos en 1 MB de RAM (30)

Tengo una computadora con 1 MB de RAM y ningún otro almacenamiento local. Debo usarlo para aceptar 1 millón de números decimales de 8 dígitos en una conexión TCP, ordenarlos y luego enviar la lista ordenada a través de otra conexión TCP.

La lista de números puede contener duplicados, que no debo descartar. El código se colocará en la ROM, así que no necesito restar el tamaño de mi código de 1 MB. Ya tengo un código para manejar el puerto Ethernet y manejar conexiones TCP / IP, y requiere 2 KB para sus datos de estado, incluido un búfer de 1 KB a través del cual el código leerá y escribirá datos. ¿Hay una solución a este problema?

Fuentes de preguntas y respuestas:
slashdot.org

cleaton.net

Tengo una computadora con 1M de RAM y ningún otro almacenamiento local

Otra forma de hacer trampa: podría usar un almacenamiento no local (en red) en su lugar (su pregunta no lo excluye) y llamar a un servicio en red que podría usar mergesort basado en disco directo (o simplemente suficiente RAM para ordenar en la memoria, ya que solo es necesario aceptar números 1M), sin necesidad de las soluciones (ciertamente extremadamente ingeniosas) ya dadas.

Esto podría ser trampa, pero no está claro si está buscando una solución a un problema del mundo real, o un rompecabezas que invita a doblar las reglas ... si es lo último, entonces una trampa simple puede obtener mejores resultados que una compleja. pero la solución "genuina" (que, como otros han señalado, solo puede funcionar para entradas compresibles).

Hay un truco bastante astuto que no se menciona aquí hasta ahora. Suponemos que no tiene una forma adicional de almacenar datos, pero eso no es estrictamente cierto.

Una forma de solucionar su problema es hacer lo siguiente, que nadie debe intentar en ninguna circunstancia: utilizar el tráfico de la red para almacenar datos. Y no, no me refiero a NAS.

Puede ordenar los números con solo unos pocos bytes de RAM de la siguiente manera:

Primero toma 2 variables: COUNTER y VALUE .
Primero ponga todos los registros a 0 ;
Cada vez que reciba un entero I , incremente el COUNTER y establezca VALUE en max(VALUE, I) ;
Luego, envíe un paquete de solicitud de eco ICMP con los datos establecidos a I para el enrutador. Borrar I y repetir.
Cada vez que recibe el paquete ICMP devuelto, simplemente extrae el número entero y lo envía de nuevo en otra solicitud de eco. Esto produce una gran cantidad de solicitudes ICMP que se arrastran hacia atrás y hacia adelante y contienen los números enteros.

Una vez que el COUNTER llega a 1000000 , tiene todos los valores almacenados en el flujo incesante de solicitudes ICMP, y VALUE ahora contiene el número entero máximo. Elige algún threshold T >> 1000000 . Ponga el COUNTER en cero. Cada vez que reciba un paquete ICMP, aumente el COUNTER y envíe el número entero contenido I en una solicitud de eco, a menos que I=VALUE , en cuyo caso, transmítalo al destino para los números enteros ordenados. Una vez que COUNTER=T , disminuya el VALUE en 1 , restablezca el COUNTER a cero y repita. Una vez que VALUE llegue a cero, debería haber transmitido todos los números enteros en orden de mayor a menor al destino, y solo se usaron aproximadamente 47 bits de RAM para las dos variables persistentes (y cualquier pequeña cantidad que necesite para los valores temporales).

Sé que esto es horrible, y sé que puede haber todo tipo de problemas prácticos, pero pensé que podría hacer reír a algunos de ustedes o al menos horrorizarlos.

La respuesta de Gilmanov es muy errónea en sus suposiciones. Comienza a especular basándose en una medida sin sentido de un millón de enteros consecutivos . Eso significa que no hay lagunas. Esos huecos aleatorios, por pequeños que sean, realmente hacen que sea una mala idea.

Inténtalo tú mismo. Obtenga 1 millón de enteros al azar de 27 bits, ordénelos, comprímalos con 7-Zip , xz, cualquier LZMA que desee. El resultado es más de 1.5 MB. La premisa en la parte superior es la compresión de números secuenciales. Incluso la codificación delta de eso es más de 1.1 MB . Y no importa, esto está usando más de 100 MB de RAM para la compresión. Así que incluso los enteros comprimidos no encajan en el problema y no importa el tiempo de ejecución del uso de RAM .

Me entristece cómo las personas simplemente votan bonitos gráficos y la racionalización.

#include <stdint.h> #include <stdlib.h> #include <time.h> int32_t ints[1000000]; // Random 27-bit integers int cmpi32(const void *a, const void *b) { return ( *(int32_t *)a - *(int32_t *)b ); } int main() { int32_t *pi = ints; // Pointer to input ints (REPLACE W/ read from net) // Fill pseudo-random integers of 27 bits srand(time(NULL)); for (int i = 0; i < 1000000; i++) ints[i] = rand() & ((1<<27) - 1); // Random 32 bits masked to 27 bits qsort(ints, 1000000, sizeof (ints[0]), cmpi32); // Sort 1000000 int32s // Now delta encode, optional, store differences to previous int for (int i = 1, prev = ints[0]; i < 1000000; i++) { ints[i] -= prev; prev += ints[i]; } FILE *f = fopen("ints.bin", "w"); fwrite(ints, 4, 1000000, f); fclose(f); exit(0); }

Ahora comprime ints.bin con LZMA ...

$ xz -f --keep ints.bin # 100 MB RAM $ 7z a ints.bin.7z ints.bin # 130 MB RAM $ ls -lh ints.bin* 3.8M ints.bin 1.1M ints.bin.7z 1.2M ints.bin.xz

Una solución solo es posible debido a la diferencia entre 1 megabyte y 1 millón de bytes. Hay aproximadamente 2 en el poder 8093729.5 formas diferentes de elegir 1 millón de números de 8 dígitos con duplicados permitidos y el orden no es importante, por lo que una máquina con solo 1 millón de bytes de RAM no tiene suficientes estados para representar todas las posibilidades. Pero 1M (menos 2k para TCP / IP) es de 1022 * 1024 * 8 = 8372224 bits, por lo que es posible una solución.

Parte 1, solución inicial.

Este enfoque necesita un poco más de 1M, lo refinaré para que se ajuste a 1M más adelante.

Almacenaré una lista compacta de números ordenados en el rango de 0 a 99999999 como una secuencia de sublistas de números de 7 bits. La primera lista secundaria contiene números del 0 al 127, la segunda lista secundaria contiene números del 128 al 255, etc. 100000000/128 es exactamente 781250, por lo que se necesitarán 781250 listas de este tipo.

Cada sublista consta de un encabezado de sublista de 2 bits seguido de un cuerpo de sublista. El cuerpo sublista ocupa 7 bits por entrada sublista. Todas las sublistas se concatenan juntas, y el formato permite saber dónde termina una sublista y comienza la siguiente. El almacenamiento total requerido para una lista completa es 2 * 781250 + 7 * 1000000 = 8562500 bits, que es aproximadamente 1.021 M-bytes.

Los 4 valores de encabezado de sublista posibles son:

00 sublista vacía, nada sigue.

01 Singleton, solo hay una entrada en la lista secundaria y los siguientes 7 bits la contienen.

10 La lista secundaria contiene al menos 2 números distintos. Las entradas se almacenan en orden no decreciente, excepto que la última entrada es menor o igual que la primera. Esto permite identificar el final de la sublista. Por ejemplo, los números 2,4,6 serían almacenados como (4,6,2). Los números 2,2,3,4,4 serían almacenados como (2,3,4,4,2).

11 La lista secundaria contiene 2 o más repeticiones de un solo número. Los siguientes 7 bits dan el número. Luego vienen cero o más entradas de 7 bits con el valor 1, seguidas de una entrada de 7 bits con el valor 0. La longitud del cuerpo de la sublista determina el número de repeticiones. Por ejemplo, los números 12,12 se almacenarían como (12,0), los números 12,12,12 se almacenarían como (12,1,0), 12,12,12,12 serían (12,1 , 1,0) y así sucesivamente.

Empiezo con una lista vacía, leo un montón de números y los almaceno como enteros de 32 bits, ordeno los nuevos números en su lugar (probablemente usando Heapsort) y luego los fusiono en una nueva lista compacta ordenada. Repita hasta que no haya más números para leer, luego recorra la lista compacta una vez más para generar la salida.

La siguiente línea representa la memoria justo antes del inicio de la operación de combinación de listas. Las "O" son la región que contiene los enteros ordenados de 32 bits. Las "X" son la región que contiene la lista compacta anterior. Los signos "=" son la sala de expansión para la lista compacta, 7 bits para cada entero en las "O". Las "Z" son otra sobrecarga aleatoria.

ZZZOOOOOOOOOOOOOOOOOOOOOOOOOO==========XXXXXXXXXXXXXXXXXXXXXXXXXX

La rutina de fusión comienza a leer en la "O" más a la izquierda y en la "X" más a la izquierda, y comienza a escribir en la "=" más a la izquierda. El puntero de escritura no captura el puntero de lectura de la lista compacta hasta que se combinan todos los nuevos enteros, porque los dos punteros avanzan 2 bits para cada sublista y 7 bits para cada entrada en la lista compacta antigua, y hay suficiente espacio adicional para Entradas de 7 bits para los nuevos números.

Parte 2, metiéndolo en 1M

Para comprimir la solución anterior en 1M, necesito hacer que el formato de lista compacta sea un poco más compacto. Me desharé de uno de los tipos de lista secundaria, de modo que solo haya 3 valores de encabezado de lista secundaria posibles. Luego puedo usar "00", "01" y "1" como valores de encabezado de sublista y guardar algunos bits. Los tipos de sublistas son:

Una sublista vacía, nada le sigue.

B Singleton, solo hay una entrada en la lista secundaria y los siguientes 7 bits la contienen.

C La lista secundaria contiene al menos 2 números distintos. Las entradas se almacenan en orden no decreciente, excepto que la última entrada es menor o igual que la primera. Esto permite identificar el final de la sublista. Por ejemplo, los números 2,4,6 serían almacenados como (4,6,2). Los números 2,2,3,4,4 serían almacenados como (2,3,4,4,2).

D La lista secundaria consta de 2 o más repeticiones de un solo número.

Mis 3 valores de encabezado de sublista serán "A", "B" y "C", por lo que necesito una forma de representar sublistas de tipo D.

Supongamos que tengo el encabezado de lista secundaria de tipo C seguido de 3 entradas, como "C [17] [101] [58]". Esto no puede ser parte de una sub-lista válida de tipo C como se describe anteriormente, ya que la tercera entrada es menor que la segunda pero más que la primera. Puedo usar este tipo de construcción para representar una sublista de tipo D. En términos de bits, en cualquier lugar que tenga "C {00 ?????} {1 ??????} {01 ?????}" es una sublista de tipo C imposible. Usaré esto para representar una lista secundaria que consiste en 3 o más repeticiones de un solo número. Las primeras dos palabras de 7 bits codifican el número (los bits "N" a continuación) y están seguidas por cero o más {0100001} palabras seguidas por una {0100000} palabra.

For example, 3 repetitions: "C{00NNNNN}{1NN0000}{0100000}", 4 repetitions: "C{00NNNNN}{1NN0000}{0100001}{0100000}", and so on.

Eso deja listas que contienen exactamente 2 repeticiones de un solo número. Representaré aquellos con otro patrón de sublista de tipo C imposible: "C {0 ??????} {11 ?????} {10 ?????}". Hay un montón de espacio para los 7 bits del número en las primeras 2 palabras, pero este patrón es más largo que la sublista que representa, lo que hace que las cosas sean un poco más complejas. Los cinco signos de interrogación al final pueden considerarse no parte del patrón, así que tengo: "C {0NNNNNN} {11N ????} 10" como mi patrón, con el número que se repetirá almacenado en la "N "s. Eso es 2 bits demasiado largo.

Tendré que pedir prestados 2 bits y devolverlos de los 4 bits no utilizados en este patrón. Al leer, al encontrar "C {0NNNNNN} {11N00AB} 10", genere 2 instancias del número en la "N", sobrescriba el "10" al final con los bits A y B, y rebobine el puntero de lectura en 2 pedacitos Las lecturas destructivas están bien para este algoritmo, ya que cada lista compacta se recorre solo una vez.

Al escribir una lista secundaria de 2 repeticiones de un solo número, escriba "C {0NNNNNN} 11N00" y configure el contador de bits prestados en 2. En cada escritura donde el contador de bits prestados no sea cero, se decrementa por cada bit escrito y "10" se escribe cuando el contador llega a cero. Así que los siguientes 2 bits escritos irán a las ranuras A y B, y luego los "10" se caerán al final.

Con 3 valores de encabezado de sublista representados por "00", "01" y "1", puedo asignar "1" al tipo de sublista más popular. Necesitaré una pequeña tabla para asignar los valores de encabezado de sublista a los tipos de sublista, y necesitaré un contador de ocurrencia para cada tipo de sublista para saber cuál es el mejor mapeo de encabezado de sublista.

El peor caso es la representación mínima de una lista compacta completamente rellena cuando todos los tipos de listas secundarias son igualmente populares. En ese caso, guardo 1 bit por cada 3 encabezados de sublistas, por lo que el tamaño de la lista es 2 * 781250 + 7 * 1000000 - 781250/3 = 8302083.3 bits. Redondeo hasta un límite de palabra de 32 bits, eso es 8302112 bits, o 1037764 bytes.

1M menos 2k para el estado TCP / IP y los buffers son 1022 * 1024 = 1046528 bytes, dejándome 8764 bytes para jugar.

Pero, ¿qué pasa con el proceso de cambiar la asignación de encabezado sublista? En el siguiente mapa de memoria, "Z" es una sobrecarga aleatoria, "=" es espacio libre, "X" es la lista compacta.

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Comience a leer en la "X" más a la izquierda y comience a escribir a la izquierda "=" y trabaje a la derecha. Cuando haya terminado, la lista compacta será un poco más corta y estará en el extremo incorrecto de la memoria:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

Entonces tendré que desviarlo a la derecha:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

En el proceso de cambio de asignación de encabezado, hasta 1/3 de los encabezados de sublista cambiarán de 1 bit a 2 bit. En el peor de los casos, todos estarán al principio de la lista, por lo que necesitaré al menos 781250/3 bits de almacenamiento gratuito antes de comenzar, lo que me remite a los requisitos de memoria de la versión anterior de la lista compacta: (

Para evitar eso, dividiré las 781250 sublistas en 10 grupos de sublistas de 78125 sublistas cada uno. Cada grupo tiene su propio mapeo de encabezado sublista independiente. Usando las letras A a J para los grupos:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

Cada grupo de sublistas se reduce o permanece igual durante un cambio de mapeo de encabezados de sublistas:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAA=====BBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABB=====CCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCC======DDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDD======EEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEE======FFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFF======GGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGG=======HHIJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHH=======IJJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHI=======JJJJJJJJJJJJJJJJJJJJ ZZZAAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ======= ZZZ=======AAAAAABBCCCDDDDDEEEFFFGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

El peor caso de expansión temporal de un grupo sublista durante un cambio de mapeo es 78125/3 = 26042 bits, por debajo de 4k. Si permito 4k más los 1037764 bytes para una lista compacta completamente llena, eso me deja 8764 - 4096 = 4668 bytes para las "Z" en el mapa de memoria.

Eso debería ser suficiente para las 10 tablas de asignación de encabezados sublistas, 30 recuentos de ocurrencia de encabezados sublistas y los otros pocos contadores, punteros y pequeños búferes que necesitaré, y el espacio que he usado sin darme cuenta, como el espacio de pila para las direcciones de retorno de llamadas de función y variables locales.

Parte 3, ¿cuánto tiempo tomaría correr?

Con una lista compacta vacía, el encabezado de la lista de 1 bit se utilizará para una lista secundaria vacía, y el tamaño inicial de la lista será de 781250 bits. En el peor de los casos, la lista crece 8 bits por cada número agregado, por lo que se necesitan 32 + 8 = 40 bits de espacio libre para que cada uno de los números de 32 bits se coloque en la parte superior del búfer de lista y luego se clasifique y fusione. En el peor de los casos, cambiar la asignación de encabezado sublista da como resultado un uso de espacio de 2 * 781250 + 7 * entradas - 781250/3 bits.

Con una política de cambiar la asignación de encabezado de lista sublista después de cada quinta fusión, una vez que haya al menos 800000 números en la lista, una ejecución en el peor de los casos implicaría un total de aproximadamente 30M de actividad de lectura y escritura de listas compactas.

Fuente:

http://nick.cleaton.net/ramsortsol.html

(Mi respuesta original fue incorrecta, perdón por las malas matemáticas, ver más abajo el receso).

¿Qué tal esto?

Los primeros 27 bits almacenan el número más bajo que haya visto, luego la diferencia con el siguiente número visto, codificado de la siguiente manera: 5 bits para almacenar la cantidad de bits utilizados para almacenar la diferencia, luego la diferencia. Use 00000 para indicar que vio ese número nuevamente.

Esto funciona porque a medida que se insertan más números, la diferencia promedio entre los números disminuye, por lo que usa menos bits para almacenar la diferencia a medida que agrega más números. Creo que esto se llama una lista delta.

El peor de los casos que se me ocurre es que todos los números están espaciados uniformemente (por 100), por ejemplo, Suponiendo que 0 es el primer número:

000000000000000000000000000 00111 1100100 ^^^^^^^^^^^^^ a million times 27 + 1,000,000 * (5+7) bits = ~ 427k

Reddit al rescate!

Si todo lo que tenía que hacer era resolverlos, este problema sería fácil. Se requieren 122k (1 millón de bits) para almacenar los números que ha visto (bit 0 en si se vio 0, bit 2300 en si se vieron 2300, etc.

Usted lee los números, los almacena en el campo de bits y luego los desplaza mientras mantiene un conteo.

PERO, tienes que recordar cuántos has visto. Me inspiré en la respuesta sublista de arriba para llegar a este esquema:

En lugar de usar un bit, use 2 o 27 bits:

00 significa que no viste el número.
01 significa que lo viste una vez
1 significa que lo viste, y los siguientes 26 bits son la cuenta de cuántas veces.

Creo que esto funciona: si no hay duplicados, tienes una lista de 244k. En el peor de los casos, ve cada número dos veces (si ve un número tres veces, acorta el resto de la lista por usted), eso significa que ha visto 50,000 más de una vez, y ha visto 950,000 artículos 0 o 1 veces.

50,000 * 27 + 950,000 * 2 = 396.7k.

Puede realizar mejoras adicionales si utiliza la siguiente codificación:

0 significa que no vio el número 10 significa que lo vio una vez 11 es la forma en que sigue contando

Lo que, en promedio, resultará en 280.7k de almacenamiento.

EDIT: mi domingo por la mañana las matemáticas estaban mal.

El peor de los casos es que vemos 500,000 números dos veces, por lo que las matemáticas se convierten en:

500,000 * 27 + 500,000 * 2 = 1.77M

La codificación alternativa resulta en un almacenamiento promedio de

500,000 * 27 + 500,000 = 1.70M

: (

Aquí hay un código de trabajo de C ++ que resuelve el problema.

~~Prueba de que se cumplen las restricciones de memoria:~~

Editor: No hay pruebas de los requisitos de memoria máximos ofrecidos por el autor en esta publicación o en sus blogs. Dado que la cantidad de bits necesarios para codificar un valor depende de los valores codificados previamente, tal prueba probablemente no sea trivial. El autor señala que el tamaño codificado más grande que pudo encontrar empíricamente fue 1011732 , y eligió el tamaño del búfer 1013000 arbitrariamente.

typedef unsigned int u32; namespace WorkArea { static const u32 circularSize = 253250; u32 circular[circularSize] = { 0 }; // consumes 1013000 bytes static const u32 stageSize = 8000; u32 stage[stageSize]; // consumes 32000 bytes ...

Juntos, estos dos arreglos toman 1045000 bytes de almacenamiento. Eso deja 1048576 - 1045000 - 2 × 1024 = 1528 bytes para las variables restantes y el espacio de pila.

Se ejecuta en unos 23 segundos en mi Xeon W3520. Puede verificar que el programa funciona con la siguiente secuencia de comandos de Python, asumiendo un nombre de programa de sort1mb.exe .

from subprocess import * import random sequence = [random.randint(0, 99999999) for i in xrange(1000000)] sorter = Popen(''sort1mb.exe'', stdin=PIPE, stdout=PIPE) for value in sequence: sorter.stdin.write(''%08d/n'' % value) sorter.stdin.close() result = [int(line) for line in sorter.stdout] print(''OK!'' if result == sorted(sequence) else ''Error!'')

Una explicación detallada del algoritmo se puede encontrar en la siguiente serie de publicaciones:

El enfoque de Google (malo), desde el hilo de HN. Almacenar recuentos de estilo RLE.

Su estructura de datos inicial es ''99999999: 0'' (todos los ceros, no he visto ningún número) y luego digamos que ve el número 3,866,344 para que su estructura de datos se convierta en ''3866343: 0,1: 1,96133654: 0'' a medida que puede ver que los números siempre alternarán entre el número de bits cero y el número de bits ''1'', por lo que puede suponer que los números impares representan 0 bits y los números pares 1 bits. Esto se convierte en (3866343,1,96133654)

Su problema no parece cubrir duplicados, pero digamos que usan "0: 1" para duplicados.

Gran problema n. ° 1: las inserciones para enteros de 1M llevaban edades .

Gran problema n. ° 2: como todas las soluciones de codificación delta simple, algunas distribuciones no pueden cubrirse de esta manera. Por ejemplo, 1m enteros con distancias de 0:99 (por ejemplo, +99 cada uno). Ahora piensa lo mismo pero con una distancia aleatoria en el rango de 0:99 . (Nota: 99999999/1000000 = 99.99)

El enfoque de Google es indigno (lento) e incorrecto. Pero para su defensa, su problema podría haber sido ligeramente diferente.

Consulte la primera respuesta correcta o la respuesta posterior con codificación aritmética . A continuación puede encontrar algo de diversión, pero no una solución 100% a prueba de balas.

Esta es una tarea bastante interesante y aquí hay otra solución. Espero que alguien encuentre el resultado útil (o al menos interesante).

Etapa 1: estructura de datos inicial, enfoque de compresión aproximada, resultados básicos

Hagamos algunos cálculos simples: tenemos 1M (1048576 bytes) de RAM inicialmente disponible para almacenar 10 ^ 6 números decimales de 8 dígitos. [0; 99999999]. Por lo tanto, para almacenar un número se necesitan 27 bits (suponiendo que se usarán números sin signo). Por lo tanto, para almacenar un flujo en bruto ~ 3.5M de RAM serán necesarios. Alguien ya dijo que no parece ser factible, pero yo diría que la tarea se puede resolver si la entrada es "lo suficientemente buena". Básicamente, la idea es comprimir los datos de entrada con un factor de compresión de 0.29 o superior y ordenarlos de manera adecuada.

Resolvamos primero el problema de la compresión. Hay algunas pruebas relevantes ya disponibles:

http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression

"Realicé una prueba para comprimir un millón de enteros consecutivos utilizando varias formas de compresión. Los resultados son los siguientes:"

None 4000027 Deflate 2006803 Filtered 1391833 BZip2 427067 Lzma 255040

Parece que LZMA ( algoritmo de cadena Lempel – Ziv – Markov ) es una buena opción para continuar. He preparado un PoC simple, pero todavía hay algunos detalles para destacar:

La memoria es limitada, por lo que la idea es realizar una ordenación previa de los números y usar depósitos compartidos (tamaño dinámico) como almacenamiento temporal
Es más fácil lograr un mejor factor de compresión con datos preclasificados, por lo que hay un búfer estático para cada grupo (los números del búfer se deben clasificar antes de LZMA)
Cada cubo contiene un rango específico, por lo que la clasificación final se puede hacer para cada cubo por separado
El tamaño del cubo se puede configurar correctamente, por lo que habrá suficiente memoria para descomprimir los datos almacenados y hacer la clasificación final para cada grupo por separado

Tenga en cuenta que el código adjunto es un POC , no se puede usar como solución final, solo demuestra la idea de usar varios búferes más pequeños para almacenar números precortados de una manera óptima (posiblemente comprimida). LZMA no se propone como una solución final. Se utiliza como la forma más rápida posible de introducir una compresión en este PoC.

Vea el código de PoC a continuación (por favor, tenga en cuenta que solo se necesita una demostración, para compilarlo se necesitará LZMA-Java ):

public class MemorySortDemo { static final int NUM_COUNT = 1000000; static final int NUM_MAX = 100000000; static final int BUCKETS = 5; static final int DICT_SIZE = 16 * 1024; // LZMA dictionary size static final int BUCKET_SIZE = 1024; static final int BUFFER_SIZE = 10 * 1024; static final int BUCKET_RANGE = NUM_MAX / BUCKETS; static class Producer { private Random random = new Random(); public int produce() { return random.nextInt(NUM_MAX); } } static class Bucket { public int size, pointer; public int[] buffer = new int[BUFFER_SIZE]; public ByteArrayOutputStream tempOut = new ByteArrayOutputStream(); public DataOutputStream tempDataOut = new DataOutputStream(tempOut); public ByteArrayOutputStream compressedOut = new ByteArrayOutputStream(); public void submitBuffer() throws IOException { Arrays.sort(buffer, 0, pointer); for (int j = 0; j < pointer; j++) { tempDataOut.writeInt(buffer[j]); size++; } pointer = 0; } public void write(int value) throws IOException { if (isBufferFull()) { submitBuffer(); } buffer[pointer++] = value; } public boolean isBufferFull() { return pointer == BUFFER_SIZE; } public byte[] compressData() throws IOException { tempDataOut.close(); return compress(tempOut.toByteArray()); } private byte[] compress(byte[] input) throws IOException { final BufferedInputStream in = new BufferedInputStream(new ByteArrayInputStream(input)); final DataOutputStream out = new DataOutputStream(new BufferedOutputStream(compressedOut)); final Encoder encoder = new Encoder(); encoder.setEndMarkerMode(true); encoder.setNumFastBytes(0x20); encoder.setDictionarySize(DICT_SIZE); encoder.setMatchFinder(Encoder.EMatchFinderTypeBT4); ByteArrayOutputStream encoderPrperties = new ByteArrayOutputStream(); encoder.writeCoderProperties(encoderPrperties); encoderPrperties.flush(); encoderPrperties.close(); encoder.code(in, out, -1, -1, null); out.flush(); out.close(); in.close(); return encoderPrperties.toByteArray(); } public int[] decompress(byte[] properties) throws IOException { InputStream in = new ByteArrayInputStream(compressedOut.toByteArray()); ByteArrayOutputStream data = new ByteArrayOutputStream(10 * 1024); BufferedOutputStream out = new BufferedOutputStream(data); Decoder decoder = new Decoder(); decoder.setDecoderProperties(properties); decoder.code(in, out, 4 * size); out.flush(); out.close(); in.close(); DataInputStream input = new DataInputStream(new ByteArrayInputStream(data.toByteArray())); int[] array = new int[size]; for (int k = 0; k < size; k++) { array[k] = input.readInt(); } return array; } } static class Sorter { private Bucket[] bucket = new Bucket[BUCKETS]; public void doSort(Producer p, Consumer c) throws IOException { for (int i = 0; i < bucket.length; i++) { // allocate buckets bucket[i] = new Bucket(); } for(int i=0; i< NUM_COUNT; i++) { // produce some data int value = p.produce(); int bucketId = value/BUCKET_RANGE; bucket[bucketId].write(value); c.register(value); } for (int i = 0; i < bucket.length; i++) { // submit non-empty buffers bucket[i].submitBuffer(); } byte[] compressProperties = null; for (int i = 0; i < bucket.length; i++) { // compress the data compressProperties = bucket[i].compressData(); } printStatistics(); for (int i = 0; i < bucket.length; i++) { // decode & sort buckets one by one int[] array = bucket[i].decompress(compressProperties); Arrays.sort(array); for(int v : array) { c.consume(v); } } c.finalCheck(); } public void printStatistics() { int size = 0; int sizeCompressed = 0; for (int i = 0; i < BUCKETS; i++) { int bucketSize = 4*bucket[i].size; size += bucketSize; sizeCompressed += bucket[i].compressedOut.size(); System.out.println(" bucket[" + i + "] contains: " + bucket[i].size + " numbers, compressed size: " + bucket[i].compressedOut.size() + String.format(" compression factor: %.2f", ((double)bucket[i].compressedOut.size())/bucketSize)); } System.out.println(String.format("Data size: %.2fM",(double)size/(1014*1024)) + String.format(" compressed %.2fM",(double)sizeCompressed/(1014*1024)) + String.format(" compression factor %.2f",(double)sizeCompressed/size)); } } static class Consumer { private Set<Integer> values = new HashSet<>(); int v = -1; public void consume(int value) { if(v < 0) v = value; if(v > value) { throw new IllegalArgumentException("Current value is greater than previous: " + v + " > " + value); }else{ v = value; values.remove(value); } } public void register(int value) { values.add(value); } public void finalCheck() { System.out.println(values.size() > 0 ? "NOT OK: " + values.size() : "OK!"); } } public static void main(String[] args) throws IOException { Producer p = new Producer(); Consumer c = new Consumer(); Sorter sorter = new Sorter(); sorter.doSort(p, c); } }

Con números aleatorios produce lo siguiente:

bucket[0] contains: 200357 numbers, compressed size: 353679 compression factor: 0.44 bucket[1] contains: 199465 numbers, compressed size: 352127 compression factor: 0.44 bucket[2] contains: 199682 numbers, compressed size: 352464 compression factor: 0.44 bucket[3] contains: 199949 numbers, compressed size: 352947 compression factor: 0.44 bucket[4] contains: 200547 numbers, compressed size: 353914 compression factor: 0.44 Data size: 3.85M compressed 1.70M compression factor 0.44

Para una secuencia ascendente simple (se usa una cubeta) produce:

bucket[0] contains: 1000000 numbers, compressed size: 256700 compression factor: 0.06 Data size: 3.85M compressed 0.25M compression factor 0.06

EDITAR

Conclusión:

No trates de engañar a la Nature
Utilice una compresión más simple con menor espacio de memoria
Algunas pistas adicionales son realmente necesarias. La solución común a prueba de balas no parece ser factible.

Etapa 2: compresión mejorada, conclusión final

Como ya se mencionó en la sección anterior, se puede utilizar cualquier técnica de compresión adecuada. Así que deshacámonos de LZMA en favor de un enfoque más simple y mejor (si es posible). Hay muchas soluciones buenas que incluyen codificación aritmética , árbol de radix, etc.

De todos modos, el esquema de codificación simple pero útil será más ilustrativo que otra biblioteca externa, proporcionando un algoritmo ingenioso. La solución real es bastante sencilla: ya que hay grupos con datos parcialmente ordenados, se pueden usar deltas en lugar de números.

Prueba de entrada aleatoria muestra resultados ligeramente mejores:

bucket[0] contains: 10103 numbers, compressed size: 13683 compression factor: 0.34 bucket[1] contains: 9885 numbers, compressed size: 13479 compression factor: 0.34 ... bucket[98] contains: 10026 numbers, compressed size: 13612 compression factor: 0.34 bucket[99] contains: 10058 numbers, compressed size: 13701 compression factor: 0.34 Data size: 3.85M compressed 1.31M compression factor 0.34

Código de muestra

public static void encode(int[] buffer, int length, BinaryOut output) { short size = (short)(length & 0x7FFF); output.write(size); output.write(buffer[0]); for(int i=1; i< size; i++) { int next = buffer[i] - buffer[i-1]; int bits = getBinarySize(next); int len = bits; if(bits > 24) { output.write(3, 2); len = bits - 24; }else if(bits > 16) { output.write(2, 2); len = bits-16; }else if(bits > 8) { output.write(1, 2); len = bits - 8; }else{ output.write(0, 2); } if (len > 0) { if ((len % 2) > 0) { len = len / 2; output.write(len, 2); output.write(false); } else { len = len / 2 - 1; output.write(len, 2); } output.write(next, bits); } } } public static short decode(BinaryIn input, int[] buffer, int offset) { short length = input.readShort(); int value = input.readInt(); buffer[offset] = value; for (int i = 1; i < length; i++) { int flag = input.readInt(2); int bits; int next = 0; switch (flag) { case 0: bits = 2 * input.readInt(2) + 2; next = input.readInt(bits); break; case 1: bits = 8 + 2 * input.readInt(2) +2; next = input.readInt(bits); break; case 2: bits = 16 + 2 * input.readInt(2) +2; next = input.readInt(bits); break; case 3: bits = 24 + 2 * input.readInt(2) +2; next = input.readInt(bits); break; } buffer[offset + i] = buffer[offset + i - 1] + next; } return length; }

Tenga en cuenta, este enfoque:

no consume mucha memoria
trabaja con arroyos
proporciona resultados no tan malos

El código completo se puede encontrar here , las implementaciones de BinaryInput y BinaryOutput se pueden encontrar here

Conclusión final

No hay una conclusión final :) A veces es una buena idea subir un nivel y revisar la tarea desde un punto de vista de meta-level .

Fue divertido pasar algún tiempo con esta tarea. Por cierto, hay muchas respuestas interesantes a continuación. Gracias por su atención y feliz codificación.

Mientras recibe la transmisión siga estos pasos.

1er set un tamaño razonable de trozo

Pseudo codigo idea:

El primer paso sería encontrar todos los duplicados y pegarlos en un diccionario con su recuento y eliminarlos.
El tercer paso sería colocar el número que existe en secuencia de sus pasos algorítmicos y colocarlos en contadores diccionarios especiales con el primer número y su paso como n, n + 1 ..., n + 2, 2n, 2n + 1, 2n + 2 ...
Comience a comprimir en trozos algunos rangos razonables de números, como cada 1000 o 10000, los números restantes que aparecen con menos frecuencia para repetir.
Descomprima ese rango si se encuentra un número, agréguelo al rango y déjelo sin comprimir por un tiempo más.
De lo contrario, simplemente agregue ese número a un byte [tamaño de chunk]

Continúa los primeros 4 pasos mientras recibes la transmisión. El paso final sería fallar si superó la memoria o comenzó a emitir el resultado una vez que se recopilan todos los datos al comenzar a ordenar los rangos y escupir los resultados en orden y descomprimirlos para descomprimirlos y ordenarlos cuando sea necesario. llegas a ellos

Si el flujo de entrada pudiera recibirse varias veces, esto sería mucho más fácil (no hay información sobre eso, idea y problema de rendimiento de tiempo).

Entonces, podríamos contar los valores decimales. Con valores contados sería fácil hacer el flujo de salida. Comprimir contando los valores. Depende de lo que estaría en el flujo de entrada.

Si no sabemos nada acerca de esos números, estamos limitados por las siguientes restricciones:

Necesitamos cargar todos los números antes de poder ordenarlos,
El conjunto de números no es compresible.

Si se cumplen estas suposiciones, no hay forma de realizar su tarea, ya que necesitará al menos 26,575,425 bits de almacenamiento (3,321,929 bytes).

¿Qué nos puedes contar de tus datos?

Tenemos 1 MB - 3 KB RAM = 2 ^ 23 - 3 * 2 ^ 13 bits = 8388608 - 24576 = 8364032 bits disponibles.

Nos dan 10 ^ 6 números en un rango de 10 ^ 8. Esto da una brecha promedio de ~ 100 <2 ^ 7 = 128

Consideremos primero el problema más simple de los números espaciados de manera bastante uniforme cuando todas las brechas son <128. Esto es fácil. Solo almacena el primer número y las brechas de 7 bits:

(27 bits) + 10 ^ 6 números de espacio de 7 bits = 7000027 bits requeridos

Tenga en cuenta que los números repetidos tienen huecos de 0.

¿Pero qué pasa si tenemos brechas mayores a 127?

Bien, digamos que un tamaño de espacio <127 se representa directamente, pero un tamaño de espacio de 127 es seguido por una codificación continua de 8 bits para la longitud de espacio real:

10xxxxxx xxxxxxxx = 127 .. 16,383 110xxxxx xxxxxxxx xxxxxxxx = 16384 .. 2,097,151

etc.

Tenga en cuenta que la representación de este número describe su propia longitud, por lo que sabemos cuándo comienza el siguiente número de intervalo.

Con solo pequeños espacios <127, esto todavía requiere 7000027 bits.

Puede haber hasta (10 ^ 8) / (2 ^ 7) = 781250 número de espacio de 23 bits, lo que requiere un extra de 16 * 781,250 = 12,500,000 bits, lo que es demasiado. Necesitamos una representación más compacta y cada vez más lenta de las brechas.

El tamaño promedio de la brecha es de 100, por lo que si los reordenamos como [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...] e indexamos esto con una codificación de Fibonacci binaria densa densa sin pares de ceros (por ejemplo, 11011 = 8 + 5 + 2 + 1 = 16) con números delimitados por ''00'', entonces creo que podemos mantener la representación de la brecha lo suficientemente corta, pero necesita más análisis.

Yo explotaría el comportamiento de retransmisión de TCP.

Hacer que el componente TCP cree una gran ventana de recepción.
Reciba cierta cantidad de paquetes sin enviar un ACK para ellos.
- Procese los pases creando una estructura de datos comprimida (prefijo)
- Enviar ack duplicado para el último paquete que ya no se necesita / esperar el tiempo de espera de retransmisión
- Goto 2
Todos los paquetes fueron aceptados.

Esto supone algún tipo de beneficio de los cubos o pases múltiples.

Probablemente clasificando los lotes / cubos y fusionándolos. -> árboles radix

Use esta técnica para aceptar y ordenar el primer 80%, luego lea el último 20%, verifique que el último 20% no contenga números que caigan en el primer 20% de los números más bajos. Luego envíe el 20% de los números más bajos, elimínelos de la memoria, acepte el 20% restante de los nuevos números y fusione. **

¿Qué tipo de computadora estás usando? Puede que no tenga ningún otro almacenamiento local "normal", pero ¿tiene RAM de video, por ejemplo? 1 megapixel x 32 bits por píxel (por ejemplo) está bastante cerca del tamaño de entrada de datos requerido.

(En gran parte, pregunto en la memoria de la antigua Acorn RISC PC , que podría "tomar prestada" VRAM para expandir la RAM del sistema disponible, si eliges un modo de pantalla de baja resolución o poca profundidad de color). Esto fue bastante útil en una máquina con solo unos pocos MB de RAM normal.

Probaría un árbol de radix . Si pudiera almacenar los datos en un árbol, podría hacer un recorrido en orden para transmitir los datos.

No estoy seguro de que puedas incluir esto en 1MB, pero creo que vale la pena intentarlo.

Ahora apunta a una solución real, cubriendo todos los casos posibles de entrada en el rango de 8 dígitos con solo 1MB de RAM. NOTA: trabajo en progreso, mañana continuará. Usando la codificación aritmética de deltas de las entradas ordenadas, el peor caso para las entradas ordenadas de 1M costaría alrededor de 7 bits por entrada (ya que 99999999/1000000 es 99, y log2 (99) es casi 7 bits).

¡Pero necesitas los enteros de 1 m ordenados para llegar a 7 u 8 bits! Las series más cortas tendrían deltas más grandes, por lo tanto, más bits por elemento.

Estoy trabajando para tomar la mayor cantidad posible y comprimir (casi) en el lugar. El primer lote de cerca de 250 Kt. Necesitaría aproximadamente 9 bits cada uno en el mejor de los casos. Así que el resultado tomaría unos 275KB. Repita con la memoria libre restante un par de veces. Luego, descomprime-fusiona-en-lugar-comprime esos trozos comprimidos. Esto es bastante difícil , pero posible. Yo creo que.

Las listas fusionadas se acercarían cada vez más al objetivo de 7 bits por entero. Pero no sé cuántas iteraciones tomaría del bucle de fusión. Tal vez 3.

Pero la imprecisión de la implementación de la codificación aritmética podría hacerlo imposible. Si este problema es posible, sería extremadamente ajustado.

¿Algun voluntario?

Creo que la solución es combinar técnicas de codificación de video, a saber, la transformación discreta del coseno. En el video digital, en lugar de grabar el cambio de brillo o color del video como valores regulares, como 110 112 115 116, cada uno se resta del último (similar a la codificación de longitud de ejecución). 110 112 115 116 se convierte en 110 2 3 1. Los valores, 2 3 1 requieren menos bits que los originales.

Digamos que creamos una lista de los valores de entrada a medida que llegan al socket. Estamos almacenando en cada elemento, no el valor, sino el desplazamiento del anterior. Clasificamos a medida que avanzamos, por lo que las compensaciones solo serán positivas. Pero el desplazamiento podría tener 8 dígitos decimales de ancho, lo que encaja en 3 bytes. Cada elemento no puede tener 3 bytes, por lo que necesitamos empaquetarlos. Podríamos usar el bit superior de cada byte como un "bit de continuación", lo que indica que el siguiente byte es parte del número y los 7 bits más bajos de cada byte deben combinarse. El cero es válido para duplicados.

A medida que la lista se llena, los números deben acercarse, lo que significa que en promedio solo se usa 1 byte para determinar la distancia al siguiente valor. 7 bits de valor y 1 bit de desplazamiento si es conveniente, pero puede haber un punto dulce que requiera menos de 8 bits para un valor "continuar".

De todos modos, hice algún experimento. Utilizo un generador de números aleatorios y puedo colocar un millón de números decimales de 8 dígitos ordenados en aproximadamente 1279000 bytes. El espacio promedio entre cada número es consistentemente 99 ...

public class Test { public static void main(String[] args) throws IOException { // 1 million values int[] values = new int[1000000]; // create random values up to 8 digits lrong Random random = new Random(); for (int x=0;x<values.length;x++) { values[x] = random.nextInt(100000000); } Arrays.sort(values); ByteArrayOutputStream baos = new ByteArrayOutputStream(); int av = 0; writeCompact(baos, values[0]); // first value for (int x=1;x<values.length;x++) { int v = values[x] - values[x-1]; // difference av += v; System.out.println(values[x] + " diff " + v); writeCompact(baos, v); } System.out.println("Average offset " + (av/values.length)); System.out.println("Fits in " + baos.toByteArray().length); } public static void writeCompact(OutputStream os, long value) throws IOException { do { int b = (int) value & 0x7f; value = (value & 0x7fffffffffffffffl) >> 7; os.write(value == 0 ? b : (b | 0x80)); } while (value != 0); } }

Creo que una forma de pensar esto es desde el punto de vista de la combinatoria: ¿cuántas combinaciones posibles de ordenamiento numérico ordenado hay? Si le damos a la combinación 0,0,0, ...., 0 el código 0 y 0,0,0, ..., 1 el código 1, y 99999999, 99999999, ... 99999999 el código N, que es n En otras palabras, ¿qué tan grande es el espacio de resultados?

Bueno, una forma de pensar acerca de esto es notar que esto es una bijección del problema de encontrar el número de rutas monótonas en una cuadrícula N x M, donde N = 1,000,000 y M = 100,000,000. En otras palabras, si tiene una cuadrícula de 1,000,000 de ancho y 100,000,000 de altura, ¿cuántos caminos más cortos hay desde la parte inferior izquierda hasta la parte superior derecha? Por supuesto, las rutas más cortas solo requieren que se mueva hacia la derecha o hacia arriba (si tuviera que moverse hacia abajo o hacia la izquierda, estaría deshaciendo el progreso realizado anteriormente). Para ver cómo esto es una bijección de nuestro problema de clasificación de números, observe lo siguiente:

Puede imaginar cualquier tramo horizontal en nuestro camino como un número en nuestro pedido, donde la ubicación Y del tramo representa el valor.

Entonces, si la ruta simplemente se mueve hacia la derecha hasta el final, luego salta hasta la parte superior, eso es equivalente al ordenamiento 0,0,0, ..., 0. si, en cambio, comienza saltando hasta la parte superior y luego se mueve hacia la derecha 1,000,000 veces, eso es equivalente a 99999999,99999999, ..., 99999999. Una ruta donde se mueve a la derecha una vez, luego una vez, luego una derecha , luego una vez, etc. hasta el final (entonces, necesariamente salta hasta la parte superior), es equivalente a 0,1,2,3, ..., 999999.

Afortunadamente para nosotros, este problema ya se ha resuelto, como una cuadrícula tiene (N + M) Elegir (M) rutas:

(1,000,000 + 100,000,000) Elija (100,000,000) ~ = 2.27 * 10 ^ 2436455

N es igual a 2.27 * 10 ^ 2436455, por lo que el código 0 representa 0,0,0, ..., 0 y el código 2.27 * 10 ^ 2436455 y algún cambio representa 99999999,99999999, ..., 99999999.

Para almacenar todos los números de 0 a 2.27 * 10 ^ 2436455 necesita lg2 (2.27 * 10 ^ 2436455) = 8.0937 * 10 ^ 6 bits.

1 megabyte = 8388608 bits> 8093700 bits

¡Entonces parece que al menos en realidad tenemos suficiente espacio para almacenar el resultado! Ahora, por supuesto, lo interesante es hacer la clasificación a medida que los números ingresan. No estoy seguro de cuál es el mejor enfoque para esto, ya que nos quedan 294908 bits. Imagino que una técnica interesante sería asumir en cada punto que es el pedido completo, encontrar el código para ese pedido y luego, cuando reciba un nuevo número, vuelva y actualice el código anterior. Mano ola mano ola

El truco consiste en representar el estado de los algoritmos, que es un conjunto múltiple de enteros, como un flujo comprimido de "contador de incremento" = "+" y "contador de salida" = "!" caracteres. Por ejemplo, el conjunto {0,3,3,4} se representaría como "! +++ !! +!", Seguido de cualquier número de caracteres "+". Para modificar el conjunto múltiple, distribuye los caracteres, manteniendo solo una cantidad constante descomprimida a la vez, y realice cambios en el lugar antes de reproducirlos de nuevo en forma comprimida.

Detalles

Sabemos que hay exactamente 10 ^ 6 números en el conjunto final, así que hay como máximo 10 ^ 6 "!" caracteres. También sabemos que nuestro rango tiene un tamaño de 10 ^ 8, lo que significa que hay como máximo 10 ^ 8 "+" caracteres. El número de formas en que podemos organizar 10 ^ 6 "!" S entre 10 ^ 8 "+" s es (10^8 + 10^6) choose 10^6, y por lo tanto, especificar una disposición particular toma ~ 0.965 MiB `de datos. Será un ajuste perfecto.

Podemos tratar a cada personaje como independiente sin exceder nuestra cuota. Hay exactamente 100 veces más "+" caracteres que "!" Caracteres, lo que simplifica a 100: 1 las probabilidades de que cada personaje sea un "+" si olvidamos que son dependientes. Las probabilidades de 100: 101 corresponden a ~ 0.08 bits por carácter , para un total casi idéntico de ~ 0.965 MiB (¡ignorar la dependencia tiene un costo de solo ~ 12 bits en este caso!).

La técnica más sencilla para almacenar caracteres independientes con probabilidad previa conocida es la codificación de Huffman . Tenga en cuenta que necesitamos un árbol poco práctico (un árbol huffman para bloques de 10 caracteres tiene un costo promedio por bloque de aproximadamente 2.4 bits, para un total de ~ 2.9 Mib. Un árbol huffman para bloques de 20 caracteres tiene un costo promedio por bloque de aproximadamente 3 bits, que es un total de ~ 1.8 MiB. Probablemente vamos a necesitar un bloque de tamaño del orden de cien, lo que implica más nodos en nuestro árbol de los que puede almacenar todo el equipo informático que haya existido. ). Sin embargo, la ROM es técnicamente "libre" según el problema y las soluciones prácticas que aprovechan la regularidad en el árbol se verán esencialmente iguales.

Pseudocódigo

Tener un árbol huffman suficientemente grande (o datos de compresión de bloque por bloque similares) almacenados en la ROM
Comience con una cadena comprimida de 10 ^ 8 "+" caracteres.
Para insertar el número N, extienda la cadena comprimida hasta que pasen los caracteres N "+" y luego inserte un "!". Reproduzca la cadena recompresada sobre la anterior a medida que avanza, manteniendo una cantidad constante de bloques en búfer para evitar sobrecargas o faltas de ejecución.
Repita un millón de veces: [entrada, descomprimir el flujo> insertar> comprimir], luego descomprima para generar

Esto es asumiendo la base 10 y, por ejemplo, su memoria usa palabras de 8 bits: asigne en memoria todo el rango de números usando incrementos de 3 bits. Los primeros 3 bits corresponderían al número 0. El segundo conjunto de 3 bits se asignaría al número 1. El conjunto de trescientos milésimas de 3 bits se asignaría al número 300k. Repita esto hasta que haya trazado todos los números de 8 dígitos. Esto totalizaría 375k bytes en total si el rango de memoria fuera continuo.

El primer bit de los 3 marcaría la presencia del número. Los siguientes 2 bits indicarían la cantidad de duplicados que podrían representarse en bytes (1..3) si ninguno, el campo de duplicados sería 00. Habrá una segunda lista que usa un contador que se incrementa cada vez que un campo de 3 bits Está marcado como teniendo un duplicado. Si está marcado con 1, tendrá un solo rango de bits para contar la cantidad de duplicados que tiene. 8 bits pueden representar un rango de 255.

Como estoy perdiendo la pista de los pensamientos. La segunda lista mantendrá un registro de cuántos duplicados para cada número. si el número 255 tiene un duplicado y es el primer número que tiene un duplicado, su índice en la lista será 0. Si 23.543 es el segundo número que tiene un duplicado, su índice será 1. Lavar, aumentar y repetir.

El peor escenario es que tengas 500k números con duplicados. Esto puede ser representado por un solo byte (ya que 1 encaja fácilmente). Entonces 375kB (idealmente) + 500kB bytes están cerca de .875MB. Dependiendo de su procesador, esto debería dejar suficiente espacio para los punteros, la indexación y todas las demás cosas divertidas.

Si tienes un solo número que tiene 1M duplicados. Todo lo que necesita es 3 bytes, ya que tiene un límite de 1M, eso es todo de lo que tiene que preocuparse. Así que en tu segunda lista solo serán 3 byes con la cantidad total.

Ahora viene la parte divertida. La segunda lista deberá ordenarse para cada número nuevo que ingrese. En el campo de 3 bits, los últimos 2 son el número de bytes que contiene el número de duplicados. Como se espera que la segunda lista esté en orden, será necesario clasificarla. Dado que la cantidad de bytes puede variar. Creo que la inserción de tipo!

Esto mantendría la cantidad de punteros y las cosas que necesita aumentar al mínimo, por lo que debería tener un poco de flexibilidad con los 250 bytes que quedan.

¡Buena suerte! Esto suena mucho más elegante en mi mente ...

Hay 10 ^ 6 valores en un rango de 10 ^ 8, así que hay un valor por cada cien puntos de código en promedio. Almacene la distancia desde el punto Nth al (N + 1) th. Los valores duplicados tienen un salto de 0. Esto significa que el salto necesita un promedio de poco menos de 7 bits para almacenar, por lo que un millón de ellos cabrá felizmente en nuestros 8 millones de bits de almacenamiento.

Estos saltos deben codificarse en un flujo de bits, por ejemplo, mediante la codificación de Huffman. La inserción se realiza por iteración a través del flujo de bits y se vuelve a escribir después del nuevo valor. Salida por iteración y escritura de los valores implícitos. Por razones prácticas, probablemente se quiera hacer como, por ejemplo, 10 ^ 4 listas que cubren 10 ^ 4 puntos de código (y un promedio de 100 valores) cada una.

Un buen árbol de Huffman para datos aleatorios se puede construir a priori asumiendo una distribución de Poisson (media = varianza = 100) en la longitud de los saltos, pero se pueden mantener estadísticas reales en la entrada y se utilizan para generar un árbol óptimo para tratar Casos patológicos.

Hay una solución a este problema en todas las entradas posibles. Engañar.

Lea los valores de m sobre TCP, donde m está cerca del máximo que se puede ordenar en la memoria, tal vez n / 4.
Ordena los 250,000 (más o menos) números y hazlos salir.
Repita para los otros 3 cuartos.
Deje que el receptor combine las 4 listas de números que ha recibido a medida que los procesa. (No es mucho más lento que usar una sola lista).

La clasificación es un problema secundario aquí. Como se dijo en otros, simplemente almacenar los enteros es difícil y no puede funcionar en todas las entradas , ya que serían necesarios 27 bits por número.

Mi opinión sobre esto es: almacenar solo las diferencias entre los enteros consecutivos (ordenados), ya que probablemente sean pequeños. Luego use un esquema de compresión, por ejemplo, con 2 bits adicionales por número de entrada, para codificar en cuántos bits se almacena el número. Algo como:

00 -> 5 bits 01 -> 11 bits 10 -> 19 bits 11 -> 27 bits

Debería ser posible almacenar un número razonable de listas de entrada posibles dentro de la restricción de memoria dada. Las matemáticas de cómo elegir el esquema de compresión para que funcione en el número máximo de entradas, están fuera de mi alcance.

Espero que pueda aprovechar el conocimiento específico del dominio de su entrada para encontrar un esquema de compresión de enteros lo suficientemente bueno basado en esto.

Ah, y luego, haces una ordenación por inserción en esa lista ordenada a medida que recibes los datos.

Mis sugerencias aquí deben mucho a la solución de Dan.

En primer lugar asumo que la solución debe manejar todas las listas de entrada posibles. Creo que las respuestas populares no hacen esta suposición (que IMO es un gran error).

Se sabe que ninguna forma de compresión sin pérdida reducirá el tamaño de todas las entradas.

Todas las respuestas populares asumen que podrán aplicar la compresión lo suficientemente efectiva como para permitirles espacio adicional. De hecho, una porción de espacio extra lo suficientemente grande como para contener una parte de su lista parcialmente completada en un formato sin comprimir y les permite realizar sus operaciones de clasificación. Esto es solo una mala suposición.

Para una solución de este tipo, cualquier persona con conocimiento de cómo realizan su compresión podrá diseñar algunos datos de entrada que no se comprimen bien para este esquema, y la "solución" probablemente se romperá debido a la falta de espacio.

En su lugar tomo un enfoque matemático. Nuestros posibles resultados son todas las listas de longitud LEN que consisten en elementos en el rango 0..MAX. Aquí el LEN es 1,000,000 y nuestro MAX es 100,000,000.

Para LEN y MAX arbitrarios, la cantidad de bits necesarios para codificar este estado es:

Log2 (MAX Multichoose LEN)

Por lo tanto, para nuestros números, una vez que hayamos completado la recepción y la clasificación, necesitaremos al menos Log2 (100,000,000 MC 1,000,000) bits para almacenar nuestro resultado de una manera que pueda distinguir de forma única todas las salidas posibles.

Esto es ~ = 988kb . Así que en realidad tenemos suficiente espacio para mantener nuestro resultado. Desde este punto de vista, es posible.

[Se eliminó el deambular sin sentido ahora que existen mejores ejemplos ...]

La mejor respuesta está aquí .

Otra buena respuesta es aquí y básicamente utiliza la ordenación por inserción como la función para expandir la lista en un elemento (almacena algunos elementos y clasifica previamente, para permitir la inserción de más de uno a la vez, ahorra un poco de tiempo). también utiliza una buena codificación de estado compacta, grupos de deltas de siete bits

Para representar la matriz ordenada, solo se puede almacenar el primer elemento y la diferencia entre los elementos adyacentes. De esta manera, nos preocupa la codificación de 10 ^ 6 elementos que pueden sumar como máximo 10 ^ 8. Vamos a llamar a esta D . Para codificar los elementos de D se puede usar un código Huffman . El diccionario para el código de Huffman se puede crear sobre la marcha y la matriz se actualiza cada vez que se inserta un nuevo elemento en la matriz ordenada (orden de inserción). Tenga en cuenta que cuando el diccionario cambia debido a un nuevo elemento, toda la matriz debe actualizarse para que coincida con la nueva codificación.

El número promedio de bits para codificar cada elemento de D se maximiza si tenemos el mismo número de cada elemento único. Diga que los elementos d1 , d2 , ..., dN en D aparecen F veces. En ese caso (en el peor de los casos tenemos 0 y 10 ^ 8 en la secuencia de entrada) tenemos

sum (1 <= i <= N ) F . di = 10 ^ 8

dónde

suma (1 <= i <= N ) F = 10 ^ 6, o F = 10 ^ 6 / N y la frecuencia normalizada será p = F / 10 ^ = 1 / N

El número promedio de bits será -log2 (1 / P ) = log2 ( N ). En estas circunstancias hay que encontrar un caso que maximiza N . Esto sucede si tenemos números consecutivos para di empezando desde 0, o, di = i -1, por lo tanto

10 ^ 8 = sum (1 <= i <= N ) F . di = suma (1 <= i <= N ) (10 ^ 6 / N ) (i-1) = (10 ^ 6 / N ) N ( N -1) / 2

es decir

N <= 201. Y para este caso, el número promedio de bits es log2 (201) = 7.6511, lo que significa que necesitaremos alrededor de 1 byte por elemento de entrada para guardar la matriz ordenada. Tenga en cuenta que esto no significa que D en general no puede tener más de 201 elementos. Simplemente siembra que si los elementos de D se distribuyen uniformemente, no puede tener más de 201 valores únicos.

Podríamos jugar con la pila de redes para enviar los números ordenados antes de que tengamos todos los números. Si envía 1M de datos, TCP / IP lo dividirá en paquetes de 1500 bytes y los transmitirá en orden al destino. Cada paquete recibirá un número de secuencia.

Podemos hacer esto a mano. Justo antes de llenar nuestra RAM, podemos ordenar lo que tenemos y enviar la lista a nuestro objetivo, pero dejar huecos en nuestra secuencia alrededor de cada número. Luego procese la segunda mitad de los números de la misma manera utilizando esos orificios en la secuencia.

La pila de redes en el extremo remoto ensamblará el flujo de datos resultante en orden de secuencia antes de entregarlo a la aplicación.

Está utilizando la red para realizar una ordenación de fusión. Este es un hack total, pero me inspiré en el otro hack de redes que se mencionó anteriormente.

Si el flujo de entrada pudiera recibirse varias veces, esto sería mucho más fácil (no hay información sobre eso, idea y problema de rendimiento de tiempo). Entonces, podríamos contar los valores decimales. Con valores contados sería fácil hacer el flujo de salida. Comprimir contando los valores. Depende de lo que estaría en el flujo de entrada.

Solo necesita almacenar las diferencias entre los números en secuencia y usar una codificación para comprimir estos números de secuencia. Tenemos 2 ^ 23 bits. Lo dividiremos en segmentos de 6 bits y dejaremos que el último bit indique si el número se extiende a otros 6 bits (5 bits más el fragmento de extensión).

Por lo tanto, 000010 es 1 y 000100 es 2. 000001100000 es 128. Ahora, consideramos el peor reparto en la representación de las diferencias en la secuencia de un número de hasta 10,000,000. Puede haber 10,000,000 / 2 ^ 5 diferencias mayores que 2 ^ 5, 10,000,000 / 2 ^ 10 diferencias mayores que 2 ^ 10, y 10,000,000 / 2 ^ 15 diferencias mayores que 2 ^ 15, etc.

Entonces, agregamos cuántos bits tomará para representar nuestra secuencia. Tenemos 1,000,000 * 6 + resumen (10,000,000 / 2 ^ 5) * 6 + resumen (10,000,000 / 2 ^ 10) * 6 + resumen (10,000,000 / 2 ^ 15) * 6 + resumen (10,000,000 / 2 ^ 20) * 4 = 7935479.

2 ^ 24 = 8388608. Desde 8388608> 7935479, deberíamos tener suficiente memoria fácilmente. Probablemente necesitaremos otro poco de memoria para almacenar la suma de dónde estamos cuando insertamos nuevos números. Luego, repasamos la secuencia y encontramos dónde insertar nuestro nuevo número, disminuimos la siguiente diferencia si es necesario y cambiamos todo después.

Supongamos que esta tarea es posible. Justo antes de la salida, habrá una representación en memoria de los millones de números ordenados. ¿Cuántas representaciones diferentes hay? Dado que puede haber números repetidos, no podemos usar nCr (elegir), pero hay una operación llamada selección múltiple que funciona en multisets .

Hay 2.2e2436455 formas de elegir un millón de números en el rango de 0..99,999,999.
Eso requiere 8,093,730 bits para representar cada combinación posible, o 1,011,717 bytes.

Por lo tanto, en teoría, puede ser posible, si se puede llegar a una representación sana (suficiente) de la lista ordenada de números. Por ejemplo, una representación insana puede requerir una tabla de búsqueda de 10 MB o miles de líneas de código.

Sin embargo, si "1M RAM" significa un millón de bytes, entonces claramente no hay suficiente espacio. El hecho de que un 5% más de memoria lo haga teóricamente posible me sugiere que la representación tendrá que ser MUY eficiente y probablemente no sensata.

Una representación de árbol de radix se acercaría a manejar este problema, ya que el árbol de radix aprovecha la "compresión de prefijo". Pero es difícil concebir una representación de árbol de radix que pueda representar un solo nodo en un byte; dos es probablemente el límite.

Pero, independientemente de cómo se representen los datos, una vez que se clasifican, se pueden almacenar en forma de prefijo comprimido, donde los números 10, 11 y 12 se representarían, por ejemplo, 001b, 001b, 001b, lo que indica un incremento de 1 del numero anterior. Quizás, entonces, 10101b representaría un incremento de 5, 1101001b un incremento de 9, etc.