Solución:
Hay un truco bastante engañoso que no se ha mencionado aquí hasta ahora. Suponemos que no tiene ninguna forma adicional de almacenar datos, pero eso no es estrictamente cierto.
Una forma de solucionar su problema es hacer lo siguiente, que nadie debería intentar bajo ninguna circunstancia: Usar 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:
COUNTERyVALUE. - Primero establezca todos los registros en
0; - Cada vez que recibes un número entero
I, incrementoCOUNTERy establecerVALUEparamax(VALUE, I); - Luego envíe un paquete de solicitud de eco ICMP con datos configurados en
Ial enrutador. BorrarIy 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 escabullen hacia atrás y hacia adelante y contienen los números enteros.
Una vez COUNTER alcanza 1000000, tiene todos los valores almacenados en el flujo incesante de solicitudes ICMP, y VALUE ahora contiene el número entero máximo. Elige algunos threshold T >> 1000000. Colocar COUNTER a cero. Cada vez que reciba un paquete ICMP, incremente COUNTER y enviar el entero contenido I retroceder en otra solicitud de eco, a menos que I=VALUE, en cuyo caso transmítalo al destino de los enteros ordenados. Una vez COUNTER=T, decremento VALUE por 1, Reiniciar COUNTER a cero y repetir. Una vez VALUE llega a cero, debería haber transmitido todos los enteros en orden de mayor a menor al destino, y solo haber usado alrededor de 47 bits de RAM para las dos variables persistentes (y cualquier cantidad pequeña 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 hacerles reír a algunos de ustedes o al menos horrorizarlos.
Aquí hay un código C ++ funcional que resuelve el problema.
Prueba de que se satisfacen las limitaciones de memoria:
Editor: No hay prueba de los requisitos máximos de memoria que ofrece el autor ni en este artículo ni en sus blogs. Dado que el número 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 con el que pudo tropezar empíricamente fue 1011732y 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.
Funciona en unos 23 segundos en mi Xeon W3520. Puede verificar que el programa funciona usando 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('%08dn' % value)
sorter.stdin.close()
result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')
Se puede encontrar una explicación detallada del algoritmo en la siguiente serie de publicaciones:
- Explicación de la clasificación de 1 MB
- Codificación aritmética y el problema de clasificación de 1 MB
- Codificación aritmética mediante matemáticas de punto fijo
Consulte la primera respuesta correcta o la respuesta posterior con codificación aritmética. A continuación puede encontrar algo divertido, 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 útil el resultado (o al menos interesante).
Etapa 1: estructura de datos inicial, enfoque de compresión aproximada, resultados básicos
Hagamos algunos cálculos simples: tenemos 1 M (1048576 bytes) de RAM inicialmente disponible para almacenar 10 ^ 6 números decimales de 8 dígitos. [0;99999999]. Entonces, para almacenar un número, se necesitan 27 bits (asumiendo que se usarán números sin signo). Por lo tanto, para almacenar un flujo sin procesar, se necesitarán ~ 3.5M de RAM. Alguien ya dijo que no parece ser factible, pero yo diría que la tarea se puede resolver si la entrada es “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.
Primero solucionemos el problema de la compresión. Hay algunas pruebas relevantes ya disponibles:
http://www.theeggeadventure.com/wikimedia/index.php/Java_Data_Compression
“Ejecuté una prueba para comprimir un millón de enteros consecutivos usando 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 una PoC simple, pero aún quedan algunos detalles por destacar:
- La memoria es limitada, por lo que la idea es preordenar números y usar depósitos comprimidos (tamaño dinámico) como almacenamiento temporal.
- Es más fácil lograr un mejor factor de compresión con datos preordenados, por lo que hay un búfer estático para cada depósito (los números del búfer deben ordenarse antes de LZMA)
- Cada cubo tiene un rango específico, por lo que la clasificación final se puede hacer para cada cubo por separado.
- El tamaño del depósito se puede configurar correctamente, por lo que habrá suficiente memoria para descomprimir los datos almacenados y hacer la clasificación final para cada depósito por separado.
Tenga en cuenta que el código adjunto es un POC, no se puede usar como solución final, simplemente demuestra la idea de usar varios búferes más pequeños para almacenar números preordenados de alguna manera óptima (posiblemente comprimidos). LZMA no se propone como solución final. Se utiliza como la forma más rápida posible de introducir una compresión en esta PoC.
Vea el código PoC a continuación (tenga en cuenta que solo es 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 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 un cubo) 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 naturaleza
- Utilice una compresión más simple con una menor huella de memoria
- Realmente se necesitan algunas pistas adicionales. La solución común a prueba de balas no parece 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 eliminemos LZMA en favor de un enfoque más simple y mejor (si es posible). Hay muchas buenas soluciones, incluida la codificación aritmética, el árbol 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: dado que hay depósitos con datos parcialmente ordenados, se pueden usar deltas en lugar de números.
La 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 que este enfoque:
- no consume mucha memoria
- funciona con arroyos
- proporciona resultados no tan malos
El código completo se puede encontrar aquí, las implementaciones de BinaryInput y BinaryOutput se pueden encontrar aquí
Conclusión final
Sin conclusión final 🙂 A veces es realmente una buena idea subir un nivel y revisar la tarea desde un punto de vista de meta-nivel.
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.
Calificaciones y reseñas
Si te gustó nuestro trabajo, puedes dejar un escrito acerca de qué le añadirías a esta división.