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 a través de 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, por lo que no necesito restar el tamaño de mi código de 1 MB. Ya tengo código para controlar el puerto Ethernet y manejar las 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

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 evitar su problema es hacer lo siguiente, algo horrible, que nadie debe intentar bajo ninguna circunstancia: usar el tráfico de 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 tome 2 variables: COUNTERy VALUE.
• Primero establezca todos los registros en 0;
• Cada vez que reciba un número entero I, incremente COUNTERy establezca VALUEen max(VALUE, I);
• Luego envíe un paquete de solicitud de eco ICMP con el conjunto de datos Ial enrutador. Borrar Iy repetir.
• Cada vez que recibe el paquete ICMP devuelto, simplemente extrae el número entero y lo envía nuevamente en otra solicitud de eco. Esto produce una gran cantidad de solicitudes ICMP que se desplazan hacia atrás y hacia adelante y contienen los enteros.

Una vez que COUNTERalcanza 1000000, tiene todos los valores almacenados en la secuencia incesante de solicitudes ICMP, y VALUEahora contiene el número entero máximo. Elige algunos threshold T >> 1000000. Poner COUNTERa cero. Cada vez que reciba un paquete ICMP, incremente COUNTERy envíe el entero contenido Inuevamente en otra solicitud de eco, a menos queI=VALUE , en cuyo caso, lo transmita al destino para los enteros ordenados. Una vez COUNTER=T, disminuir VALUEpor 1, restablecer COUNTERa cero y repetir. Una vez que VALUEllegue a cero, debería haber transmitido todos los enteros en orden, de mayor a menor, al destino, y solo haber usado aproximadamente 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 hacer reír a algunos o al menos horrorizarlos.

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

Prueba de que se cumplen las restricciones de memoria:

Editor: No hay prueba de los requisitos máximos de memoria ofrecidos por el autor ni en esta publicación ni en sus blogs. Dado que el número de bits necesarios para codificar un valor depende de los valores codificados previamente, es probable que dicha prueba no sea trivial. El autor señala que el tamaño codificado más grande con el que podría tropezar empíricamente fue 1011732, y eligió el tamaño del búfer 1013000arbitrariamente.

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 utilizando el siguiente script de Python, suponiendo 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!')

Se puede encontrar una explicación detallada del algoritmo en la siguiente serie de publicaciones:

• Clasificación de 1 MB explicada
• Codificación aritmética y el problema de clasificación de 1 MB
• Codificación aritmética utilizando 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 matemáticos simples: tenemos 1M (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 (suponiendo 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 factible, pero yo diría que la tarea puede resolverse 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 ordenar de manera adecuada.

Vamos a resolver el problema de compresión primero. 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 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 un PoC simple, pero todavía hay algunos detalles a destacar:

1. La memoria es limitada, por lo que la idea es ordenar los números y usar cubos comprimidos (tamaño dinámico) como almacenamiento temporal
2. Es más fácil lograr un mejor factor de compresión con datos preseleccionados, por lo que hay un búfer estático para cada cubo (los números del búfer se deben clasificar antes de LZMA)
3. Cada cubo tiene un rango específico, por lo que la clasificación final se puede hacer para cada cubo por separado
4. 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 una solución final, solo demuestra la idea de usar varios buffers más pequeños para almacenar números preseleccionados 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 PoC a continuación (tenga en cuenta que es solo 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 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:

1. No trates de engañar al naturaleza
2. Use una compresión más simple con menor huella de memoria
3. 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 eliminemos LZMA a favor de un enfoque más simple y mejor (si es posible). Hay muchas buenas soluciones que incluyen codificación aritmética , á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 cubos 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:

1. no consume mucha memoria
2. trabaja con transmisiones
3. 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 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.

Una solución solo es posible debido a la diferencia entre 1 megabyte y 1 millón de bytes. Hay alrededor de 2 en el poder 8093729.5 formas diferentes de elegir 1 millón de números de 8 dígitos con duplicados permitidos y pedidos sin importancia, 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 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 encaje en 1M más tarde.

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

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

Los 4 posibles valores de encabezado de sublista son:

00 Sublista vacía, no sigue nada.

01 Singleton, solo hay una entrada en la sublista y los siguientes 7 bits la retienen.

10 La sublista 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 se almacenarían como (4,6,2). Los números 2,2,3,4,4 se almacenarían como (2,3,4,4,2).

11 La sublista contiene 2 o más repeticiones de un solo número. Los siguientes 7 bits dan el número. Luego, ingrese cero o más entradas de 7 bits con el valor 1, seguido de una entrada de 7 bits con el valor 0. La longitud del cuerpo de la sublista dicta 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.

Comienzo con una lista vacía, leo un montón de números y los almaceno como números enteros de 32 bits, clasifico los nuevos números en su lugar (probablemente usando un montón) y luego los combino 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 fusión de lista. Las "O" son la región que contiene los enteros ordenados de 32 bits. Las "X" son la región que contiene la antigua lista compacta. Los signos "=" son la sala de expansión para la lista compacta, 7 bits para cada entero en las "O". Las "Z" son otros gastos indirectos al azar.

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

La rutina de combinación comienza a leer en el extremo izquierdo "O" y en el extremo izquierdo "X", y comienza a escribir en el extremo izquierdo "=". El puntero de escritura no captura el puntero de lectura de la lista compacta hasta que se fusionen todos los enteros nuevos, porque ambos punteros avanzan 2 bits para cada sublista y 7 bits para cada entrada en la lista compacta anterior, y hay suficiente espacio adicional para el Entradas de 7 bits para los nuevos números.

Parte 2, metiéndolo en 1M

Para exprimir 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 sublista, de modo que solo haya 3 posibles valores de encabezado de sublista diferentes. Entonces puedo usar "00", "01" y "1" como los valores del encabezado de la sublista y guardar algunos bits. Los tipos de sublista son:

Una sublista vacía, nada sigue.

B Singleton, solo hay una entrada en la sublista y los siguientes 7 bits la retienen.

C La sublista 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 se almacenarían como (4,6,2). Los números 2,2,3,4,4 se almacenarían como (2,3,4,4,2).

D La sublista 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 sublista de tipo C seguido de 3 entradas, como "C [17] [101] [58]". Esto no puede ser parte de una sublista de tipo C válida 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 sublista que consta de 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 van seguidas de cero o más palabras {0100001} seguidas de una palabra {0100000}.

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

Eso solo deja listas que contienen exactamente 2 repeticiones de un solo número. Representaré a aquellos con otro patrón de sublista de tipo C imposible: "C {0 ??????} {11 ?????} {10 ?????}". Hay mucho 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, por lo que tengo: "C {0NNNNNN} {11N ????} 10" como mi patrón, con el número que se repetirá almacenado en el "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", muestra 2 instancias del número en las "N", sobrescribe el "10" al final con los bits A y B, y rebobina el puntero de lectura en 2 bits Las lecturas destructivas están bien para este algoritmo, ya que cada lista compacta se recorre solo una vez.

Al escribir una sublista de 2 repeticiones de un solo número, escriba "C {0NNNNNN} 11N00" y establezca el contador de bits prestados en 2. En cada escritura donde el contador de bits prestados no es cero, se disminuye para cada bit escrito y "10" se escribe cuando el contador llega a cero. Por lo tanto, los siguientes 2 bits escritos irán a las ranuras A y B, y luego el "10" se dejará caer 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 tabla pequeña para asignar los valores de encabezado de sublista a los tipos de sublista, y necesitaré un contador de ocurrencias para cada tipo de sublista para que sepa cuál es la mejor asignación de encabezado de sublista.

La peor representación mínima de una lista compacta totalmente poblada ocurre cuando todos los tipos de sublista son igualmente populares. En ese caso, guardo 1 bit por cada 3 encabezados de sublista, por lo que el tamaño de la lista es 2 * 781250 + 7 * 1000000 - 781250/3 = 8302083.3 bits. Redondeando a un límite de palabra de 32 bits, eso es 8302112 bits o 1037764 bytes.

1M menos los 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 de sublista? En el mapa de memoria a continuación, "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 en la "=" más a la izquierda y trabaje a la derecha. Cuando termine, 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 lleva de vuelta a los requisitos de memoria de la versión anterior de la lista compacta: (

Para evitar eso, dividiré las sublistas 781250 en 10 grupos de sublistas de 78125 cada una. Cada grupo tiene su propia asignación de encabezado de sublista independiente. Usando las letras A a J para los grupos:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

Cada grupo de sublista se reduce o permanece igual durante un cambio de asignación de encabezado de sublista:

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 de 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 poblada, 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 mapeo de encabezado de sublista, 30 recuentos de ocurrencia de encabezado de sublista y los otros pocos contadores, punteros y pequeños buffers que necesitaré, y espacio que he usado sin darme cuenta, como espacio de pila para direcciones de retorno de llamadas de función y variables locales

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

Con una lista compacta vacía, el encabezado de la lista de 1 bit se usará para una sublista 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 cada uno de los números de 32 bits que se colocarán en la parte superior del búfer de la lista y luego se ordenarán y fusionarán. En el peor de los casos, cambiar la asignación de encabezado de sublista da como resultado un uso de espacio de 2 * 781250 + 7 * entradas - 781250/3 bits.

Con una política de cambiar el mapeo del encabezado de la sublista después de cada quinta fusión, una vez que haya al menos 800000 números en la lista, una ejecución de caso más desfavorable implicaría un total de aproximadamente 30 millones de actividades de lectura y escritura de listas compactas.

Fuente:

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

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

Inténtalo tú mismo. Obtenga 1 millón de enteros aleatorios de 27 bits, ordénelos, comprímalos con 7-Zip , xz, cualquier LZMA que desee. El resultado supera los 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. Entonces, incluso los enteros comprimidos no se ajustan al problema y no importa el uso de RAM en tiempo de ejecución .

Me entristece cómo la gente simplemente vota gráficos bonitos y 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 comprima 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

Creo que una forma de pensar en esto es desde un punto de vista combinatorio: ¿cuántas combinaciones posibles de ordenamiento de números ordenados hay? Si damos 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 resultante?

Bueno, una forma de pensar en esto es darse cuenta de que esto es una biyección del problema de encontrar el número de caminos monótonos 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 que tiene 1,000,000 de ancho y 100,000,000 de alto, ¿cuántos caminos más cortos hay de la parte inferior izquierda a la superior derecha? Los caminos más cortos, por supuesto, requieren que solo te muevas hacia la derecha o hacia arriba (si te mueves hacia abajo o hacia la izquierda estarías deshaciendo el progreso realizado anteriormente). Para ver cómo esto es una biyecció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 orden, 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 hacia la parte superior, eso es equivalente al orden 0,0,0, ..., 0. si en cambio comienza saltando hasta la cima y luego se mueve hacia la derecha 1,000,000 de veces, eso es equivalente a 99999999,99999999, ..., 99999999. Una ruta donde se mueve hacia la derecha una vez, luego hacia arriba una vez, luego hacia la derecha , luego hacia arriba 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, 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 algunos cambios representan 99999999,99999999, ..., 99999999.

Para almacenar todos los números del 0 al 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 tenemos suficiente espacio para almacenar el resultado! Ahora, por supuesto, lo interesante es hacer la clasificación a medida que fluyen los números. No estoy seguro de que el mejor enfoque para esto sea dado que tenemos 294908 bits restantes. Me imagino que una técnica interesante sería asumir en cada punto que ese es el pedido completo, encontrar el código para ese pedido y luego, a medida que recibe un nuevo número, volver y actualizar el código anterior. Onda de la mano Onda de la mano.

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

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

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

Todas las respuestas populares suponen que podrán aplicar la compresión lo suficientemente eficaz 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 una forma sin comprimir y permitirles realizar sus operaciones de clasificación. Esto es solo una mala suposición.

Para tal solución, cualquiera con conocimiento de cómo hacen 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 cambio, adopto un enfoque matemático. Nuestras posibles salidas 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 (LEN Múltiple Múltiple)

Entonces, 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 manera ú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.

[Divagación sin sentido eliminada ahora que existen mejores ejemplos ...]

La mejor respuesta está aquí .

Otra buena respuesta está aquí y, básicamente, utiliza el orden de inserción como la función para expandir la lista por un elemento (almacena algunos elementos y ordena previamente, para permitir la inserción de más de uno a la vez, ahorra un poco de tiempo). usa una buena codificación de estado compacto también, cubos de deltas de siete bits

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? Como puede haber números repetidos, no podemos usar nCr (elegir), pero hay una operación llamada multichoose que funciona en multisets .

• Hay 2.2e2436455 formas de elegir un millón de números en el rango 0..99,999,999.
• Eso requiere 8.093.730 bits para representar todas las combinaciones posibles, o 1.011.717 bytes.

Entonces, en teoría, puede ser posible, si se puede llegar a una representación sensata (suficiente) de la lista ordenada de números. Por ejemplo, una representación loca 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 hace teóricamente posible me sugiere que la representación tendrá que ser MUY eficiente y probablemente no sensata.

(Mi respuesta original fue incorrecta, perdón por las malas matemáticas, ver debajo del descanso).

¿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 el número 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 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 uniformemente espaciados (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 tuviera que hacer fuera ordenarlos, este problema sería fácil. Se necesitan 122k (1 millón de bits) para almacenar los números que ha visto (0 ° bit si se vio 0, 2300 ° bit si se vio 2300, etc.

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

PERO, tienes que recordar cuántos has visto. Me inspiró la respuesta de la sublista anterior para elaborar 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, verá cada número dos veces (si ve un número tres veces, acorta el resto de la lista), 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 viste el número 10 significa que lo viste una vez 11 es cómo mantienes la cuenta

Lo que, en promedio, dará como resultado 280.7k de almacenamiento.

EDITAR: mi matemática del domingo por la mañana estaba mal.

El peor de los casos es que vemos 500,000 números dos veces, entonces la matemática se convierte en:

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

La codificación alternativa da como resultado un almacenamiento promedio de

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

: (

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

1. 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.
2. Ordene los 250,000 (más o menos) números y envíelos.
3. Repita para los otros 3 cuartos.
4. Deje que el receptor combine las 4 listas de números que ha recibido a medida que las procesa. (No es mucho más lento que usar una sola lista).

Yo probaría un árbol 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 1 MB, pero creo que vale la pena intentarlo.

¿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 megapíxel x 32 bits por píxel (por ejemplo) se acerca bastante al tamaño de entrada de datos requerido.

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

Una representación de árbol de raíz se acercaría a manejar este problema, ya que el árbol de raíz aprovecha la "compresión de prefijo". Pero es difícil concebir una representación de árbol de raíz que pueda representar un solo nodo en un byte; dos probablemente sea 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án, digamos 001b, 001b, 001b, lo que indica un incremento de 1 del número anterior Quizás, entonces, 10101b representaría un incremento de 5, 1101001b un incremento de 9, etc.

Hay 10 ^ 6 valores en un rango de 10 ^ 8, por lo que hay un valor por cien puntos de código en promedio. Almacene la distancia desde el enésimo punto hasta el (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 encajará 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 es iterando a través del flujo de bits y reescribiendo después del nuevo valor. Salida iterando y escribiendo los valores implícitos. Para mayor practicidad, probablemente quiera hacerse como, digamos, 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 suponiendo una distribución de Poisson (media = varianza = 100) en la longitud de los saltos, pero las estadísticas reales se pueden mantener en la entrada y utilizar para generar un árbol óptimo para tratar Casos patológicos.

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

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

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

Creo que la solución es combinar técnicas de codificación de video, es decir, la transformación discreta del coseno. En el video digital, en lugar de grabar el cambio del brillo o el 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.

Entonces, 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. Ordenamos 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 cabe en 3 bytes. Cada elemento no puede tener 3 bytes, por lo que debemos empacarlos. 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 inferiores de cada byte deben combinarse. 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 óptimo que requiera menos de 8 bits para un valor "continuo".

De todos modos, hice un experimento. Uso 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 constantemente 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);
    }
}

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

Podemos hacer esto a mano. Justo antes de llenar nuestra RAM podemos clasificar lo que tenemos y enviar la lista a nuestro objetivo, pero dejar huecos en nuestra secuencia alrededor de cada número. Luego procese el 2do 1/2 de los números de la misma manera usando esos agujeros en la secuencia.

La pila de red en el otro extremo 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 por fusión. Este es un truco total, pero me inspiró el otro truco de redes mencionado anteriormente.

Enfoque (malo) de Google , del hilo de HN. Almacene cuentas de estilo RLE.

Su estructura de datos inicial es '99999999: 0' (todos ceros, no han 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 # 1: las inserciones para enteros de 1M tomarían años .

Gran problema # 2: como todas las soluciones de codificación delta simples, algunas distribuciones no se pueden cubrir de esta manera. Por ejemplo, 1 m enteros con distancias 0:99 (por ejemplo, +99 cada uno). Ahora piense 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 en su defensa, su problema podría haber sido ligeramente diferente.

Para representar la matriz ordenada, uno puede almacenar el primer elemento y la diferencia entre elementos adyacentes. De esta manera, nos preocupa codificar 10 ^ 6 elementos que pueden sumar hasta 10 ^ 8 como máximo. 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 Huffman se puede crear sobre la marcha y la matriz se actualiza cada vez que se inserta un nuevo elemento en la matriz ordenada (clasificación por 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. Digamos que los elementos d1 , d2 , ..., dN en D aparecen cada 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

sum (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 a partir de 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 están distribuidos uniformemente, no puede tener más de 201 valores únicos.

Explotaría el comportamiento de retransmisión de TCP.

1. Haga que el componente TCP cree una gran ventana de recepción.
2. Reciba cierta cantidad de paquetes sin enviarles un ACK.
   • Procese los pases creando una estructura de datos comprimidos (prefijo)
   • Enviar un acuse de recibo duplicado para el último paquete que ya no se necesita / esperar el tiempo de espera de la retransmisión
   • Ir a 2
3. Todos los paquetes fueron aceptados

Esto supone algún tipo de beneficio de 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 aterrizarían en el primer 20% de los números más bajos. Luego envíe el 20% de los números más bajos, retírelo de la memoria, acepte el 20% restante de números nuevos y fusione. **

Aquí hay una solución generalizada para este tipo de problema:

Procedimiento general

El enfoque adoptado es el siguiente. El algoritmo funciona en un único búfer de palabras de 32 bits. Realiza el siguiente procedimiento en un bucle:

• Comenzamos con un búfer lleno de datos comprimidos de la última iteración. El búfer se ve así

  |compressed sorted|empty|

• Calcule la cantidad máxima de números que se pueden almacenar en este búfer, tanto comprimidos como sin comprimir. Divida el búfer en estas dos secciones, comenzando con el espacio para datos comprimidos y terminando con los datos sin comprimir. El búfer se parece a

  |compressed sorted|empty|empty|

• Rellene la sección sin comprimir con los números que se ordenarán. El búfer se parece a

  |compressed sorted|empty|uncompressed unsorted|

• Ordenar los nuevos números con una ordenación en el lugar. El búfer se parece a

  |compressed sorted|empty|uncompressed sorted|

• Alinee a la derecha cualquier dato ya comprimido de la iteración anterior en la sección comprimida. En este punto, el búfer está particionado

  |empty|compressed sorted|uncompressed sorted|

• Realice una descompresión-recompresión de transmisión en la sección comprimida, fusionando los datos ordenados en la sección sin comprimir. La antigua sección comprimida se consume a medida que crece la nueva sección comprimida. El búfer se parece a

  |compressed sorted|empty|

Este procedimiento se realiza hasta que se hayan ordenado todos los números.

Compresión

Este algoritmo, por supuesto, solo funciona cuando es posible calcular el tamaño comprimido final del nuevo búfer de clasificación antes de saber qué se comprimirá realmente. Además de eso, el algoritmo de compresión debe ser lo suficientemente bueno como para resolver el problema real.

El enfoque utilizado utiliza tres pasos. Primero, el algoritmo siempre almacenará secuencias ordenadas, por lo tanto, podemos almacenar puramente las diferencias entre entradas consecutivas. Cada diferencia está en el rango [0, 99999999].

Estas diferencias se codifican como un flujo de bits unario. A 1 en este flujo significa "Agregar 1 al acumulador, A 0 significa" Emitir el acumulador como una entrada y restablecer ". Entonces la diferencia N estará representada por N 1 y un 0.

La suma de todas las diferencias se acercará al valor máximo que admite el algoritmo, y el recuento de todas las diferencias se acercará a la cantidad de valores insertados en el algoritmo. Esto significa que esperamos que la secuencia, al final, contenga el valor máximo de 1 y cuente los 0. Esto nos permite calcular la probabilidad esperada de un 0 y 1 en la secuencia. A saber, la probabilidad de un 0 es count/(count+maxval)y la probabilidad de un 1 es maxval/(count+maxval).

Utilizamos estas probabilidades para definir un modelo de codificación aritmética sobre este flujo de bits. Este código aritmético codificará exactamente estas cantidades de 1 y 0 en el espacio óptimo. Podemos calcular el espacio utilizado por este modelo para cualquier flujo de bits intermedia como: bits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount). Para calcular el espacio total requerido para el algoritmo, establezca encodedigual a cantidad.

Para no requerir una cantidad ridícula de iteraciones, se puede agregar una pequeña sobrecarga al búfer. Esto asegurará que el algoritmo al menos opere en la cantidad de números que caben en esta sobrecarga, ya que, con mucho, el mayor costo de tiempo del algoritmo es la compresión y descompresión de codificación aritmética en cada ciclo.

Además de eso, es necesario algo de sobrecarga para almacenar datos de contabilidad y manejar pequeñas inexactitudes en la aproximación de punto fijo del algoritmo de codificación aritmética, pero en total el algoritmo puede caber en 1MiB de espacio incluso con un búfer adicional que puede contener 8000 números, para un total de 1043916 bytes de espacio.

Óptima

Fuera de reducir la sobrecarga (pequeña) del algoritmo, debería ser teóricamente imposible obtener un resultado menor. Para contener la entropía del resultado final, serían necesarios 1011717 bytes. Si restamos el búfer adicional agregado para mayor eficiencia, este algoritmo usará 1011916 bytes para almacenar el resultado final + sobrecarga.

Si el flujo de entrada pudiera recibirse pocas 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 la secuencia de salida. Comprima contando los valores. Depende de lo que estaría en la secuencia de entrada.

Si el flujo de entrada se pudiera recibir 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 la secuencia de salida. Comprima contando los valores. Depende de lo que estaría en la secuencia de entrada.

La clasificación es un problema secundario aquí. Como dijo otro, solo 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 serán 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 buen número de posibles listas de entrada 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 más allá de mí.

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

Ah, y luego, realiza una ordenación por inserción en esa lista ordenada a medida que recibe datos.

Ahora apuntando a una solución real, que cubra todos los casos posibles de entrada en el rango de 8 dígitos con solo 1 MB de RAM. NOTA: trabajo en progreso, mañana continuará. Usando la codificación aritmética de los deltas de las entradas ordenadas, el peor de los casos para 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 necesita 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 250K ints necesitaría aproximadamente 9 bits cada uno en el mejor de los casos. Por lo tanto, el resultado tomaría alrededor de 275 KB. Repita con el resto de la memoria libre varias 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. Quizás 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 apretado.

¿Algun voluntario?

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 fragmentos de 6 bits y dejaremos que el último bit indique si el número se extiende a otros 6 bits (5 bits más un fragmento extendido).

Por lo tanto, 000010 es 1 y 000100 es 2. 000001100000 es 128. Ahora, consideramos el peor modelo para representar diferencias en la secuencia de números 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 se necesitarán 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. Dado que 8388608> 7935479, deberíamos tener fácilmente suficiente memoria. Probablemente necesitaremos otro poco de memoria para almacenar la suma de dónde estamos cuando insertemos nuevos números. Luego pasamos por la secuencia y encontramos dónde insertar nuestro nuevo número, disminuimos la siguiente diferencia si es necesario y cambiamos todo después de eso a la derecha.

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

• necesitamos cargar todos los números antes de poder clasificarlos,
• El conjunto de números no es compresible.

Si se cumplen estos supuestos, no hay forma de llevar a cabo su tarea, ya que necesitará al menos 26,575,425 bits de almacenamiento (3,321,929 bytes).

¿Qué nos puede decir sobre sus datos?

El truco consiste en representar el estado de los algoritmos, que es un conjunto múltiple de enteros, como una secuencia comprimida 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, transmite los caracteres, manteniendo solo una cantidad constante descomprimida a la vez, y realiza cambios en el lugar antes de transmitirlos nuevamente en forma comprimida.

Detalles

Sabemos que hay exactamente 10 ^ 6 números en el conjunto final, por lo 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, por lo que especificar algún arreglo particular requiere ~ 0.965 MiB `de datos. Será un ajuste apretado.

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 carácter 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 simple 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 "gratuita" 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 bloque por bloque similares) almacenados en la ROM
• Comience con una cadena comprimida de 10 ^ 8 "+" caracteres.
• Para insertar el número N, transmita la cadena comprimida hasta que hayan pasado N caracteres "+" y luego inserte un "!". Transmita la cadena recomprimida sobre la anterior a medida que avanza, manteniendo una cantidad constante de bloques almacenados en búfer para evitar ejecuciones excesivas / insuficientes.
• Repita un millón de veces: [entrada, descompresión de flujo> insertar> comprimir], luego descomprima a salida

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

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

Primero consideremos el problema más simple de números espaciados de manera bastante uniforme cuando todos los espacios son <128. Esto es fácil. Simplemente almacene 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 huecos 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 esta representación numérica describe su propia longitud para que sepamos cuándo comienza el siguiente número de hueco.

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

Puede haber hasta (10 ^ 8) / (2 ^ 7) = 781250 número de intervalo de 23 bits, lo que requiere 16 * 781,250 adicionales = 12,500,000 bits, lo cual es demasiado. Necesitamos una representación de brechas más compacta y que aumente lentamente.

El tamaño de espacio promedio 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 binaria densa de Fibonacci 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 brecha lo suficientemente corta, pero necesita Más análisis.

Mientras recibe la transmisión, siga estos pasos.

1.er set un tamaño de trozo razonable

Idea de pseudocódigo:

1. El primer paso sería encontrar todos los duplicados y pegarlos en un diccionario con su conteo y eliminarlos.
2. El tercer paso sería colocar el número que existe en la 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 ...
3. Comience a comprimir en fragmentos algunos rangos razonables de números, como cada 1000 o cada 10000, los números restantes que parecen repetir con menos frecuencia.
4. Descomprima ese rango si se encuentra un número, agréguelo al rango y déjelo sin comprimir durante un tiempo más.
5. De lo contrario, simplemente agregue ese número a un byte [chunkSize]

Continúe los primeros 4 pasos mientras recibe la transmisión. El paso final sería fallar si excedió la memoria o comenzar a generar el resultado una vez que se recopilan todos los datos, comenzando a ordenar los rangos y escupiendo los resultados en orden y descomprimiendo los que deben descomprimirse y ordenarlos cuando los llegas a ellos.