Clasificar 1 millón de números de 8 dígitos decimales con 1 MB de RAM

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 un código para controlar el puerto Ethernet y manejar conexiones TCP/IP, y requiere 2 KB para sus datos de estado, incluido un búfer de 1 KB a través del cual el código leerá y escribirá datos. ¿Hay una solución a este problema?

Fuentes de preguntas y respuestas:

barradot.org

cleaton.net

Oct 05 '12 21:10 phuclv

Aquí hay un código C++ funcional 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 este post ni en sus blogs. Dado que el número de bits necesarios para codificar un valor depende de los valores previamente codificados, es probable que dicha prueba no sea trivial. El autor señala que el tamaño codificado más grande con el que pudo toparse empíricamente fue 1011732y eligió el tamaño del búfer 1013000de forma arbitraria.

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

    ...

Juntas, estas dos matrices ocupan 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, asumiendo un nombre de programa de sort1mb.exe.

from subprocess import *
import random

sequence = [random.randint(0, 99999999) for i in xrange(1000000)]

sorter = Popen('sort1mb.exe', stdin=PIPE, stdout=PIPE)
for value in sequence:
    sorter.stdin.write('%08d\n' % value)
sorter.stdin.close()

result = [int(line) for line in sorter.stdout]
print('OK!' if result == sorted(sequence) else 'Error!')

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 mediante matemáticas de punto fijo

Oct 25 '2012 11:10 preshing

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

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

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

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

Primero solucionemos el problema de la compresión. Ya hay algunas pruebas relevantes disponibles:

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

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

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

Parece que LZMA ( algoritmo de cadena de Lempel-Ziv-Markov ) es una buena opción para continuar. He preparado una PoC sencilla, pero aún quedan algunos detalles por destacar:

1. La memoria es limitada, por lo que la idea es ordenar previamente los números y utilizar depósitos comprimidos (tamaño dinámico) como almacenamiento temporal.
2. Es más fácil lograr un mejor factor de compresión con datos preclasificados, por lo que hay un búfer estático para cada depósito (los números del búfer deben ordenarse antes de LZMA)
3. Cada depósito tiene un rango específico, por lo que la clasificación final se puede realizar para cada depósito 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 realizar la clasificación final para cada depósito por separado.

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

Vea el código PoC a continuación (tenga en cuenta que es solo una demostración, para compilarlo será necesario 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 intentes engañar a la naturaleza.
2. Utilice una compresión más simple con menor consumo de memoria
3. Realmente se necesitan algunas pistas adicionales. Una solución común a prueba de balas no parece factible.

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

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

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

La prueba de entrada aleatoria muestra resultados ligeramente mejores:

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

Código de muestra

  public static void encode(int[] buffer, int length, BinaryOut output) {
    short size = (short)(length & 0x7FFF);

    output.write(size);
    output.write(buffer[0]);

    for(int i=1; i< size; i++) {
        int next = buffer[i] - buffer[i-1];
        int bits = getBinarySize(next);

        int len = bits;

        if(bits > 24) {
          output.write(3, 2);
          len = bits - 24;
        }else if(bits > 16) {
          output.write(2, 2);
          len = bits-16;
        }else if(bits > 8) {
          output.write(1, 2);
          len = bits - 8;
        }else{
          output.write(0, 2);
        }

        if (len > 0) {
            if ((len % 2) > 0) {
                len = len / 2;
                output.write(len, 2);
                output.write(false);
            } else {
                len = len / 2 - 1;
                output.write(len, 2);
            }

            output.write(next, bits);
        }
    }
}

public static short decode(BinaryIn input, int[] buffer, int offset) {
    short length = input.readShort();
    int value = input.readInt();
    buffer[offset] = value;

    for (int i = 1; i < length; i++) {
        int flag = input.readInt(2);

        int bits;
        int next = 0;
        switch (flag) {
            case 0:
                bits = 2 * input.readInt(2) + 2;
                next = input.readInt(bits);
                break;
            case 1:
                bits = 8 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 2:
                bits = 16 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
            case 3:
                bits = 24 + 2 * input.readInt(2) +2;
                next = input.readInt(bits);
                break;
        }

        buffer[offset + i] = buffer[offset + i - 1] + next;
    }

   return length;
}

Tenga en cuenta que este enfoque:

1. no consume mucha memoria
2. funciona con corrientes
3. no proporciona tan malos resultados

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

Conclusión final

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

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.

Oct 19 '2012 20:10 Renat Gilmanov

Una solución sólo es posible debido a la diferencia entre 1 megabyte y 1 millón de bytes. Hay alrededor de 2 elevado a 8093729,5 formas diferentes de 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 sólo 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 perfeccionaré para que quepa en 1M más adelante.

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 esas 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 la sublista. Todas las sublistas están concatenadas y el formato permite saber dónde termina una sublista y comienza la siguiente. El almacenamiento total requerido para una lista completamente completa es 2*781250 + 7*1000000 = 8562500 bits, que es aproximadamente 1,021 M-bytes.

Los 4 valores posibles del encabezado de la sublista son:

00 Sublista vacía, no sigue nada.

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

10 La sublista contiene al menos 2 números distintos. Las entradas se almacenan en orden no decreciente, excepto que la última entrada sea menor o igual a 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 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 serían (12,1 ,1,0) y así sucesivamente.

Empiezo con una lista vacía, leo un montón de números y los almaceno como enteros de 32 bits, ordeno los nuevos números en su lugar (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 el resultado.

La siguiente línea representa la memoria justo antes del inicio de la operación de combinación de listas. Las "O" son la región que contiene los números enteros de 32 bits ordenados. Las "X" son la región que contiene la antigua lista compacta. Los signos "=" son el espacio de expansión para la lista compacta, 7 bits por cada número entero en las "O". Las "Z" son otros gastos indirectos aleatorios.

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 "=" más a la izquierda. El puntero de escritura no captura el puntero de lectura de la lista compacta hasta que se fusionan todos los nuevos enteros, 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 comprimir la solución anterior en 1M, necesito hacer que el formato de lista compacta sea un poco más compacto. Me desharé de uno de los tipos de sublista, de modo que solo habrá 3 posibles valores de encabezado de sublista diferentes. Luego puedo usar "00", "01" y "1" como valores del encabezado de la sublista y guardar algunos bits. Los tipos de sublista son:

Una sublista vacía, no sigue nada.

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

C La sublista contiene al menos 2 números distintos. Las entradas se almacenan en orden no decreciente, excepto que la última entrada sea menor o igual a 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 la 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 mayor que la primera. Puedo usar este tipo de construcción para representar una sublista de tipo D. En términos de bits, cualquier lugar donde 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 dos primeras 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é 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 2 primeras 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. Se puede considerar que los cinco signos de interrogación al final no son 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 campo "N". "s. Eso son 2 bits demasiado largos.

Tendré que pedir prestados 2 bits y devolverlos con los 4 bits no utilizados en este patrón. Al leer, al encontrar "C{0NNNNNN}{11N00AB}10", genere 2 instancias del número en las "N", sobrescriba el "10" al final con los bits A y B, y rebobine el puntero de lectura 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 en la que el contador de bits prestados no sea cero, se decrementa por cada bit escrito y "10" se escribe cuando el contador llega a cero. Entonces, los siguientes 2 bits escritos irán a las ranuras A y B, y luego el "10" se colocará al final.

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

El peor de los casos, la representación mínima de una lista compacta completamente completa ocurre cuando todos los tipos de sublistas 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, son 8302112 bits o 1037764 bytes.

1M menos los 2k para el estado TCP/IP y los buffers son 1022*1024 = 1046528 bytes, lo que me deja 8764 bytes para jugar.

Pero ¿qué pasa con el proceso de cambiar el mapeo del encabezado de la sublista? En el mapa de memoria siguiente, "Z" es la sobrecarga aleatoria, "=" es el espacio libre y "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 hacia la derecha. Cuando termine, la lista compacta será un poco más corta y estará en el extremo equivocado de la memoria:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

Entonces tendré que desviarlo hacia la derecha:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

Para solucionar esto, dividiré las 781250 sublistas en 10 grupos de sublistas de 78125 sublistas cada uno. Cada grupo tiene su propia asignación de encabezados de sublista independiente. Usando las letras de la A a la 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 completa, 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 encabezados de sublista, los 30 recuentos de ocurrencia de encabezados de sublista y los otros pocos contadores, punteros y pequeños buffers que necesitaré, y el espacio que he usado sin darme cuenta, como espacio de pila para direcciones de retorno de llamadas a funciones y variables locales.

Parte 3, ¿cuánto tiempo tardaría en ejecutarse?

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á 781250 bits. En el peor de los casos, la lista crece 8 bits por cada número agregado, por lo que se necesitan 32 + 8 = 40 bits de espacio libre para que cada uno de los números de 32 bits se coloque en la parte superior del búfer de la lista y luego se ordene y combine. En el peor de los casos, cambiar la asignación del 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 encabezados de la sublista después de cada quinta fusión una vez que haya al menos 800 000 números en la lista, la ejecución en el peor de los casos implicaría un total de aproximadamente 30 millones de actividad de lectura y escritura de listas compactas.

Fuente:

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

Oct 19 '2012 16:10 Favourite Onwuemene