Pregunta Clasificando 1 millón de números de 8 dígitos en 1 MB de RAM


Tengo una computadora con 1 MB de RAM y ningún otro almacenamiento local. Debo utilizarlo 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 ROM, por lo 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 buffer de 1 KB a través del cual el código leerá y escribirá datos. ¿Hay una solución a este problema?

Fuentes de pregunta y respuesta:
slashdot.org

cleaton.net


620


origen


Respuestas:


Hay un truco bastante furtivo no mencionado aquí hasta el momento. Suponemos que no tiene una forma adicional de almacenar datos, pero eso no es estrictamente cierto.

Una forma de resolver su problema es hacer lo siguiente horrible, que bajo ninguna circunstancia debe intentar cualquiera: use 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 configure todos los registros para 0;
  • Cada vez que recibes un número entero I, incremento COUNTER y establecer VALUE a max(VALUE, I);
  • A continuación, envíe un paquete de solicitud de eco ICMP con los datos configurados en I al enrutador. Borrar I y repetir
  • Cada vez que recibe el paquete ICMP devuelto, simplemente extrae el entero y lo envía de nuevo en otra solicitud de eco. Esto produce una gran cantidad de solicitudes ICMP que se desplazan hacia atrás y hacia adelante conteniendo los enteros.

Una vez COUNTER alcanza 1000000, tiene todos los valores almacenados en la secuencia incesante de solicitudes ICMP, y VALUE ahora contiene el entero máximo. Elige un poco threshold T >> 1000000. Conjunto COUNTER a cero. Cada vez que reciba un paquete ICMP, incremente COUNTER y enviar el entero contenido I hacia atrás en otra solicitud de eco, a menos que I=VALUE, en cuyo caso, transmitirlo al destino para los enteros clasificados. Una vez COUNTER=Tdecremento 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 hasta el destino, y solo ha usado 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 alguno de ustedes o al menos horrorizarlos.


406



Aquí hay algunos códigos de C ++ en funcionamiento que soluciona el problema

Prueba de que las restricciones de memoria están satisfechas:

Editor: No hay pruebas de los requisitos máximos de memoria ofrecidos por el autor en esta publicación o en sus blogs. Dado que el número de bits necesarios para codificar un valor depende de los valores codificados previamente, tal prueba es probable que no sea trivial. El autor señala que el tamaño codificado más grande con el que podría tropezar empíricamente era 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 la pila.

Se ejecuta en aproximadamente 23 segundos en mi Xeon W3520. Puede verificar que el programa funciona utilizando la siguiente secuencia de comandos de Python, suponiendo que el nombre de un programa 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:


404



Por favor mira el 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 algunas matemáticas simples: tenemos 1M (1048576 bytes) de RAM disponible inicialmente para almacenar 10 ^ 6 números decimales de 8 dígitos. [0; 99999999]. Así que para almacenar un número se necesitan 27 bits (asumiendo que se usarán números sin firmar). Por lo tanto, para almacenar una secuencia sin procesar, se necesitarán aproximadamente 3.5M de RAM. Alguien ya dijo que no parece 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 hacer la clasificación 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 utilizando   varias formas de compresión. Los resultados son los siguientes:"

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

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

  1. La memoria es limitada, así que la idea es preseleccionar 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 la preclasificación datos, por lo que hay un búfer estático para cada segmento (los números del búfer deben ordenarse antes de LZMA)
  3. Cada cucharón tiene un rango específico, por lo que el tipo final se puede hacer para cada cubo por separado
  4. El tamaño del cubo puede ajustarse correctamente, por lo que habrá suficiente memoria para descomprime los datos almacenados y realiza el último orden para cada cubo por separado

In-memory sorting

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

Vea el código PoC a continuación (tenga en cuenta que es solo una demostración, para compilarlo LZMA-Java será necesario):

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 intentes 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 usar cualquier técnica de compresión adecuada. Así que deshagamos de 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 de Radix etc.

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

encoding scheme

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 streams
  3. proporciona resultados no tan malos

El código completo se puede encontrar aquí, Las implementaciones 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 meta-nivel punto de vista.

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


361



Una solución solo es posible debido a la diferencia entre 1 megabyte y 1 millón de bytes. Hay aproximadamente 2 formas de 8093729.5 de poder diferentes para elegir 1 millón de números de 8 dígitos con duplicados permitidos y orden 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 encajar 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 de 0 a 127, la segunda sublista contiene números de 128 a 255, etc. 100000000/128 es exactamente 781250, por lo que se necesitarán 781250 sublistas.

Cada sublista consiste en un encabezado de sublista de 2 bits seguido de un cuerpo de sublista. El cuerpo de la sublista toma 7 bits por entrada de sublista. Las sublistas están todas concatenadas juntas, y el formato permite saber dónde termina una sublista y comienza la siguiente. El almacenamiento total requerido para una lista totalmente 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 Lista vacía, nada sigue.

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

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án 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 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 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 (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 (usando heapsort, probablemente) y luego los fusiono en una nueva lista ordenada compacta. 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 la lista. Las "O" son la región que contiene los enteros clasificados 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 la "O" s. 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 el extremo izquierdo "=". El puntero de escritura no captura el puntero de lectura de la lista compacta hasta que todos los nuevos enteros se fusionan, porque ambos punteros avanzan 2 bits para cada sublista y 7 bits para cada entrada en la antigua lista compacta, 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 la lista compacta sea un poco más compacto. Me desharé de uno de los tipos de sublista, de modo que habrá solo 3 diferentes posibles valores de encabezado de sublista. Entonces puedo usar "00", "01" y "1" como el encabezado de la sublista valora y guardo 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 mantienen.

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án como (2,3,4,4,2).

D La sublista consiste en 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 describió anteriormente, ya que la tercera entrada es menor que la segunda, pero más que la primera. Puedo usar este tipo de constructo 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. Lo usaré 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 "N" bits a continuación) y son 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 solo deja listas que contienen exactamente 2 repeticiones de un solo número. Representaré a aquellos con otro patrón de sublista tipo C imposible: "C {0 ??????} {11 ?????} {10 ?????}". Hay espacio suficiente 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 como 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 la "N "s. Eso es 2 bits demasiado tiempo.

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", emite 2 instancias del número en las "N" s, sobrescribe el "10" al final con los bits A y B, y rebobina el puntero de lectura en 2 bits. Las lecturas destructivas son correctas para este algoritmo, ya que cada lista compacta solo se puede recorrer 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 decrementa por cada bit escrito y "10" se escribe cuando el contador llega a cero. De modo que los siguientes 2 bits escritos entrarán en las ranuras A y B, y luego se colocará el "10" en el extremo.

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 mapear los valores de los encabezados de la sublista a los tipos de la sublista, y necesitaré un contador de ocurrencias para cada tipo de sublista para saber cuál es la mejor mapeo de encabezado de sublista.

En el peor de los casos, la representación mínima de una lista compacta totalmente poblada se produce 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 el 2k para el estado TCP / IP y los buffers son 1022 * 1024 = 1046528 bytes, dejándome 8764 bytes para jugar.

Pero, ¿qué ocurre con el proceso de cambio de la asignación de encabezado de 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 en el extremo izquierdo "=" y trabaje a la derecha. Cuando termine, la lista compacta será un poco más corta y estará en el lado equivocado 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á de 1 bit a 2 bit. En el peor de los casos, todos estarán a la cabeza 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 evitarlo, dividiré las sublistas 781250 en 10 grupos de sublista de 78125 sublistas cada uno. 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 contrae 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 asignación es 78125/3 = 26042 bits, en 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 conteos de ocurrencia de encabezado de sublista y los otros pocos contadores, punteros y pequeños amortiguadores que necesitaré, y el espacio que he usado sin notar, como espacio de pila para las direcciones de retorno de llamada 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 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 ordenan y fusionan. En el peor de los casos, el cambio de la asignación de encabezado de la 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 sublista después de cada quinta fusión una vez que haya al menos 800000 números en la lista, una ejecución de peor caso implicaría un total de aproximadamente 30M de actividad de escritura y lectura de lista compacta.

Fuente:

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


164



La respuesta de Gilmanov está muy equivocada en sus suposiciones. Comienza a especular basado en una inútil medida de un millón consecutivo enteros. Eso significa que no hay lagunas. Esos vacíos aleatorios, por pequeños 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, comprima con 7-Zip, xz, cualquier LZMA que quieras. El resultado es más de 1.5 MB. La premisa en la parte superior es la compresión de números secuenciales. Incluso codificación delta de eso es más de 1.1 MB. Y no importa que 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 la RAM de tiempo de ejecución.

Me entristece cómo las personas simplemente votan a favor de los gráficos bonitos 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

54



Creo que una forma de pensar sobre esto es desde un punto de vista combinatorio: ¿cuántas combinaciones posibles de ordenamientos numéricos 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, ¿Qué es N? En otras palabras, ¿qué tan grande es el espacio de resultados?

Bueno, una forma de pensar sobre esto es darse cuenta de que esto es una biyección del problema de encontrar el número de caminos monotónicos 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 alto, ¿cuántos caminos más cortos de abajo a la izquierda están arriba? Los recorridos más cortos, por supuesto, requieren que solo te muevas hacia la derecha o hacia arriba (si te movías hacia abajo o hacia la izquierda, estarías deshaciendo el progreso logrado anteriormente). Para ver cómo esto es una biyección de nuestro problema de clasificación numérica, observe lo siguiente:

Puedes imaginar cualquier tramo horizontal en nuestro camino como un número en nuestro orden, donde la ubicación Y de la pierna representa el valor.

enter image description here

Entonces, si la ruta simplemente se mueve hacia la derecha hasta el final, entonces salta hasta la parte superior, que es equivalente al orden de 0,0,0, ..., 0. si, en cambio, comienza saltando hasta la parte superior y luego se mueve hacia la derecha 1,000,000 de veces, eso es equivalente a 99999999,99999999, ..., 99999999. Un camino donde se mueve una vez, luego arriba una vez, luego la derecha , luego sube una vez, etc. hasta el final (luego 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 así tiene (N + M) rutas de selección (M):

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

N por lo tanto 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 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 espacio suficiente para almacenar el resultado! Ahora, por supuesto, lo interesante es hacer la clasificación a medida que los números se transmiten. No estoy seguro de que el mejor enfoque para esto sea que tenemos 294908 bits restantes. Imagino que una técnica interesante sería suponer en cada punto que ese es el orden completo, encontrar el código para ese orden y luego, cuando reciba un nuevo número, retroceda y actualice el código anterior. Ola de la mano de la mano.


40



Mis sugerencias aquí le debo mucho a La solución de Dan

En primer lugar, supongo que la solución debe manejar todas posibles listas de entrada. 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érdida reducirá el tamaño de todas las entradas.

Todas las respuestas populares suponen que podrán aplicar una compresión lo suficientemente efectiva como para permitirles espacio adicional. De hecho, una porción de espacio adicional lo suficientemente grande como para mantener parte de su lista parcialmente completada en una forma no comprimida y permitirles realizar sus operaciones de clasificación. Esta es solo una mala suposición.

Para una solución de este tipo, cualquier persona con conocimiento de cómo hacen su compresión será capaz de diseñar algunos datos de entrada que no se comprimen bien para este esquema, y ​​la "solución" probablemente se rompa debido a quedarse sin espacio.

En cambio, tomo un enfoque matemático. Nuestros posibles resultados son todas las listas de longitud LEN que constan de 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 LONG multichoose)

Entonces, para nuestros números, una vez que hayamos terminado de recibir y clasificar, 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 todos los resultados posibles.

Esto es ~ = 988kb. Entonces realmente tenemos espacio suficiente para mantener nuestro resultado. Desde este punto de vista, es posible.

[Suprimido despropósito inútil ahora que existen mejores ejemplos ...]

La mejor respuesta es aquí.

Otra buena respuesta es aquí y básicamente utiliza la ordenación por inserción como la función para expandir la lista por un elemento (almacena temporalmente algunos elementos y clasificaciones previas, para permitir la inserción de más de uno a la vez, ahorra un poco de tiempo). usa una agradable codificación de estado compacto, cubos de deltas de siete bits


19