Tri 1 million 8 chiffres de 1 mo de RAM

Question

J'ai un ordinateur avec 1mo de RAM et pas d'autres locaux de stockage. Je dois l'utiliser pour accepter de 1 millions de 8 chiffres, des nombres décimaux sur une connexion TCP, de les trier, puis envoyer la liste triée sur une connexion TCP. La liste des numéros peuvent contenir des doublons, que je ne dois pas jeter. Le code sera placé dans la ROM, donc je n'ai pas besoin de soustraire la taille de mon code à partir de la 1M. J'ai déjà le code pour conduire le port ethernet et gérer les connexions TCP/IP, et il faut 2k pour son état de données, y compris les 1k de mémoire tampon par l'intermédiaire de laquelle le code s'lire et écrire des données. Est-il une solution à ce problème?

Les Sources De La Question Et La Réponse:
http://tech.slashdot.org/comments.pl?sid=232757&cid=18925745
http://nick.cleaton.net/ramsort.html

Answer 1

Il y a un truc pas mentionné jusqu'ici. Nous supposons que vous n'avez aucun moyen de stocker des données, mais qui n'est pas strictement vrai.

Une façon de résoudre votre problème, c'est de faire ce qui suit horrible chose, qui ne doit pas être tenté par une personne, en aucune circonstance: Utilisez le trafic réseau pour stocker des données. Et non, je ne veux pas de NAS.

Vous pouvez trier les nombres avec seulement quelques octets de RAM de la façon suivante:

• D'abord prendre 2 variables: le COMPTEUR et la VALEUR.
• Premier jeu de tous les registres à 0;
• Chaque fois que vous recevez un entier I, incrémenter le COMPTEUR et réglez la VALEUR max(VALEUR, I);
• Puis d'envoyer un paquet ICMP echo request avec le jeu de données à I du routeur. Effacer et je le répète.
• Chaque fois que vous recevez le retour de paquet ICMP, il vous suffit d'extraire les entiers, et de l'envoyer à nouveau dans une autre requête d'écho. Cela produit un grand nombre de requêtes ICMP sabordage vers l'arrière et vers l'avant contenant les entiers.

Une fois que le COMPTEUR atteint 1000000, vous disposez de toutes les valeurs stockées dans le flot de requêtes ICMP, et la VALEUR maintenant contient l'entier maximum. Choisir un seuil T >> 1000000. Régler le COMPTEUR à zéro. Chaque fois que vous recevez un paquet ICMP, incrémenter le COMPTEUR et envoyer le contenu de l'entier I de retour dans une autre requête d'écho, sauf si I=VALEUR, auquel cas le transmettre à la destination pour le tri des entiers. Une fois le COMPTEUR=T, décrémenter la VALEUR de 1, de réinitialisation du COMPTEUR à zéro et répéter. Une fois que la VALEUR atteint zéro, vous devriez avoir transmis tous les nombres entiers dans l'ordre, de la plus grande à la plus petite à la destination, et ont seulement utilisé environ 47 bits de RAM pour les deux variables persistantes (et toute petite quantité dont vous avez besoin pour les valeurs temporaires).

Je sais que c'est horrible, et je sais qu'il peut être toutes sortes de questions pratiques, mais j'ai pensé qu'il pourrait donner à certains d'entre vous, un rire ou au moins d'épouvante.

Answer 2

Voici quelques travail de code C++ qui permet de résoudre le problème.

La preuve que la mémoire, les contraintes sont satisfaites:

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

    ...

Ensemble, ces deux tableaux de prendre 1045000 octets de stockage. Que les feuilles 1048576 - 1045000 - 2×1024 = 1528 octets pour les autres variables de pile et de l'espace.

Il fonctionne dans environ 23 secondes sur mon Xeon W3520. Vous pouvez vérifier que le programme fonctionne à l'aide du script Python ci, en supposant que le nom d'un programme d' 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!')

Une explication détaillée de l'algorithme peut être trouvé dans la suite de la série de posts:

• 1 MO de Tri Expliqué
• Le Codage arithmétique et la 1MB Problème de Tri
• L'Arithmétique Codage À L'Aide De Point Fixe De Mathématiques

Answer 3

Veuillez voir la première bonne réponse ou la réponse plus tard avec l'arithmétique codage. Ci-dessous vous trouverez peut-être amusant, mais pas à 100% à l'épreuve des balles solution.

C'est assez un travail intéressant et voici une autre solution. J'espère que quelqu'un aurait trouver le résultat utile (ou au moins intéressant).

Étape 1: la première structure de données, rugueuse approche de compression, de résultats de base

Faisons un peu de maths simples: nous avons 1M (1 048 576 octets) de mémoire RAM d'abord disponible pour stocker 10^6 8 chiffres les nombres décimaux. [0;99999999]. Donc, pour stocker un numéro de 27 bits sont nécessaires (en prenant l'hypothèse que les nombres non signés seront utilisés). Ainsi, pour stocker les raw d'un flux d'environ 3,5 M de RAM seront nécessaires. Quelqu'un a déjà dit, il ne semble pas être réalisable, mais je dirais que la tâche peut être résolu si l'entrée est "assez bon". Fondamentalement, l'idée est de compresser les données d'entrée avec un facteur de compression de 0,29 ou plus et faire le tri dans une manière appropriée.

Nous allons résoudre le problème de compression en premier. Il y a quelques tests déjà disponibles:

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

"J'ai couru un test pour compresser un million de nombres entiers consécutifs à l'aide de divers formats de compression. Les résultats sont comme suit:"

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

Il ressemble à LZMA (Lempel–Ziv–Markov chain algorithme) est un bon choix pour continuer. J'ai préparé un simple PoC, mais il y a encore quelques détails pour être mis en évidence:

1. La mémoire est limitée, donc l'idée est de trier préalablement les nombres et les utiliser comprimé seaux (dynamique de la taille) pour le stockage temporaire
2. Il est plus facile de parvenir à un meilleur facteur de compression avec prétriés de données, il est donc statique de la mémoire tampon pour chaque seau (les nombres de la mémoire tampon doivent être triés avant LZMA)
3. Chaque seau est titulaire d'une plage spécifique, de sorte que le tri final peut être fait pour chaque segment séparément
4. Seau de taille peut être définie correctement, donc il y aura assez de mémoire pour décompresser les données stockées et de faire le tri final pour chaque segment séparément

Veuillez noter que, du code joint est un POC, il ne peut pas être utilisé comme une solution définitive, il démontre simplement l'idée d'utiliser plusieurs petits tampons pour stocker le tri préalable des nombres dans certains de façon optimale (éventuellement compressé). LZMA n'est pas proposé comme une solution définitive. Il est utilisé comme un plus rapide possible à introduire une compression de ce PoC.

Voir le Cop de code ci-dessous (veuillez noter juste une démo, de le compiler LZMA-Java seront nécessaires):

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);
}
}

Avec des nombres aléatoires, il produit le suivant:

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

Pour une simple séquence ascendante (un seau est utilisé), il donne:

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

MODIFIER

Conclusion:

1. N'essayez pas de tromper la Nature
2. Utilisation plus simple de compression avec la plus faible empreinte mémoire
3. Certains des indices supplémentaires sont vraiment nécessaires. Commun à l'épreuve des balles solution ne semble pas être possible.

Étape 2: amélioration de la compression, la conclusion finale

Comme cela a déjà été mentionné dans la section précédente, toutes les technique de compression peuvent être utilisés. So let's get débarrasser de LZMA en faveur des plus simples et mieux (si possible). Il y a beaucoup de bonnes solutions, y compris le codage Arithmétique, Radix arbre etc.

De toute façon, simple mais utile schéma de codage sera plus parlante que encore une autre bibliothèque externe, offrant quelques chouettes algorithme. La véritable solution est assez simple: puisqu'il y a des seaux avec des données partiellement triées, les deltas peuvent être utilisés à la place des numéros.

Aléatoire d'entrée de test montre des résultats légèrement meilleurs:

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

Exemple de code

  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;
}

Veuillez noter que cette approche:

1. ne consomme pas beaucoup de mémoire
2. fonctionne avec des flux
3. fournit pas de si mauvais résultats

Code complet peut être trouvé ici, BinaryInput et BinaryOutput les implémentations peuvent être trouvés ici

Conclusion finale

Aucune conclusion finale :) Parfois, c'est vraiment une bonne idée pour se déplacer d'un niveau vers le haut et de révision de la tâche à partir d'un méta-niveau point de vue.

C'était amusant de passer un peu de temps à cette tâche. BTW, il y a beaucoup de réponses intéressantes ci-dessous. Je vous remercie pour votre attention et heureux codding.

Answer 4

Une solution est possible seulement en raison de la différence entre 1 mo et 1 million d'octets. Il y a environ 2 à la puissance 8093729.5 différentes façons de choisir 1 millions de 8 chiffres, avec des doublons autorisés et de l'ordre sans importance, donc une machine avec seulement 1 million d'octets de RAM n'a pas assez de membres pour représenter toutes les possibilités. Mais 1M (moins de 2k pour le protocole TCP/IP) est 1022*1024*8 = 8372224 bits, une solution est possible.

La partie 1, la solution initiale

Cette approche a besoin d'un peu plus de 1M, je vais l'améliorer pour s'adapter à 1M plus tard.

Je vais ranger un compact liste ordonnée de nombres dans l'intervalle de 0 à 99999999 comme une séquence de sous-listes de 7 bits. La première sous-liste détient des chiffres de 0 à 127, le deuxième sous-liste détient les numéros de 128 à 255, etc. 100000000/128 est exactement 781250, donc 781250 ces sous-listes seront nécessaires.

Chaque sous-liste se compose de 2 bits de sous-en-tête suivi par un sous-corps. Le sous-corps prend 7 bits par sous-liste d'entrée. Les sous-listes sont tous concaténées ensemble, et le format permet de dire d'où une sous-liste se termine et commence la suivante. Le total de l'espace de stockage requis pour une liste est entièrement rempli 2*781250 + 7*1000000 = 8562500 bits, ce qui est sur 1.021 M-octets.

Les 4 sous-liste valeurs d'en-tête sont:

00 Vide sous-liste, rien ne suit.

01 Singleton, il n'y a qu'une seule entrée dans la sous-liste et et 7 bits de la retenir.

10 La sous-liste détient au moins 2 numéros distincts. Les entrées sont stockés dans l'ordre décroissant, sauf que la dernière entrée est inférieure ou égale à la première. Cela permet à la fin de la sous-liste à être identifiés. Par exemple, les numéros de 2,4,6 est stockée en tant que (4,6,2). Les numéros de 2,2,3,4,4 est stockée en tant que (2,3,4,4,2).

11 La sous-liste de 2 ou plus de répétitions d'un seul numéro. Les 7 bits de donner le nombre. Puis viennent zéro ou plus de 7 bits entrées dont la valeur est 1, suivi par un 7-bit avec la valeur 0. La longueur de la sous-corps détermine le nombre de répétitions. Par exemple, les numéros de 12,12 est stockée en tant que (12,0), les numéros de 12,12,12 est stockée en tant que (12,1,0), 12,12,12,12 serait (12,1,1,0) et ainsi de suite.

J'ai commencer avec une liste vide, lire un tas de chiffres et de les stocker sous forme de 32 bits par exemple, trier les nouveaux numéros en place (à l'aide de heapsort, sans doute), puis de les fusionner en un nouveau compact liste triée. Répéter jusqu'à ce qu'il n'y a pas plus de nombres à lire, puis à pied le compact liste une fois de plus pour générer la sortie.

La ligne ci-dessous représente la mémoire, juste avant le début de la liste de l'opération de fusion. Les "O"sont la région qui détiennent le tri nombres entiers de 32 bits. Le "X"de la région qui détiennent le vieux compact liste. Le "=" signes sont l'extension de la salle pour le compact liste, 7 bits pour chaque entier dans les "O". Le "Z"sont d'autres aléatoire frais généraux.

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

La fusion de la routine commence à lire à l'extrême gauche "O" et à l'extrême gauche "X", et commence à écrire à l'extrême gauche "=". L'écriture pointeur ne pas attraper le compact liste de pointeur de lecture jusqu'à ce que tous les nouveaux entiers sont fusionnées, parce que les deux pointeurs d'avance 2 bits pour chaque sous-liste et 7 bits pour chaque entrée dans la vieille compact liste, et il y a suffisamment d'espace supplémentaire pour les 7 bits les inscriptions pour les nouveaux numéros.

Partie 2, s'entasser dans 1M

Pour Serrer la solution ci-dessus dans 1M, j'ai besoin de faire la compacte la forme d'une liste un peu plus compact. Je vais me débarrasser de l'un des sous-types, de sorte qu'il n'y aura que 3 différents types de sous-liste valeurs d'en-tête. Alors je peux utiliser "00", "01" et "1" comme le sous-en-tête de valeurs et d'enregistrer quelques morceaux. Les sous-types sont:

Un Vide sous-liste, rien ne suit.

B Singleton, il n'y a qu'une seule entrée dans la sous-liste et et 7 bits de la retenir.

C La sous-liste détient au moins 2 numéros distincts. Les entrées sont stockés dans l'ordre décroissant, sauf que la dernière entrée est inférieure ou égale à la première. Cela permet à la fin de la sous-liste à être identifiés. Par exemple, les numéros de 2,4,6 est stockée en tant que (4,6,2). Les numéros de 2,2,3,4,4 est stockée en tant que (2,3,4,4,2).

D La sous-liste se compose de 2 ou plus de répétitions d'un seul numéro.

Mes 3 sous-en-tête de valeurs de "A", "B" et "C", j'ai donc besoin d'un moyen de représenter la D-type des sous-listes.

Supposons que j'ai la C-type de sous-en-tête suivi par 3 entrées, telles que "C[17][101][58]". Cela ne peut pas être de la partie valide de type C sous-liste, comme décrit ci-dessus, depuis la troisième entrée est inférieure à la seconde, mais plus que le premier. Je peux utiliser ce type de construction pour représenter un type D sous-liste. En peu de termes, n'importe où j'ai "C{00?????}{1??????}{01?????}" est impossible de type C sous-liste. Je vais l'utiliser pour représenter une sous-liste composée de 3 ou plus de répétitions d'un seul numéro. Les deux premiers 7 bits des mots de coder le nombre (le "N" bits ci-dessous) et sont suivis par zéro ou plus {0100001} mots suivis d'un {0100000} mot.

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

Cela ne laisse listes tenir exactement 2 répétitions d'un seul numéro. Je vais représenter ceux avec un autre impossible C-type de sous-motif: "C{0??????}{11?????}{10?????}". Il y a beaucoup de place pour les 7 bits du nombre dans les 2 premiers mots, mais ce modèle est plus longue que la sous-liste qu'il représente, et qui rend les choses un peu plus complexes. Les cinq points d'interrogation à la fin peut être considéré comme ne faisant pas partie du modèle, j'ai donc: "C{0NNNNNN}{11N????}10" comme mon patron, avec le nombre d'être répété stockées dans le "N". C'est 2 bits trop longtemps.

Je vais devoir emprunter 2 bits et les payer de retour à partir de la 4 les bits non utilisés dans ce modèle. Lors de la lecture, sur rencontrer "C{0NNNNNN}{11N00AB}10", sortie 2 instances du nombre dans le "N"s, de remplacer le "10" à la fin avec les bits A et B, et de rembobiner le pointeur de lecture par 2 bits. Destructeur de lectures sont ok pour cet algorithme, puisque chaque compact liste se passe qu'une fois.

Lors de l'écriture d'une sous-liste de 2 répétitions d'un seul numéro, écrire "C{0NNNNNN}11N00" et emprunté bits compteur à 2. À chaque écriture où le capital emprunté bits compteur est non-nul, il est décrémenté pour chaque bit écrite et "10" est écrit lorsque le compteur atteint zéro. Donc, la prochaine 2 bits écrits vont dans les fentes A et B, puis le "10" laché sur la fin.

Avec 3 sous-en-tête de valeurs représentées par "00", "01" et "1", je peux assigner "1" pour les plus populaires de sous-type. J'aurai besoin d'une petite table pour les sous-liste valeurs d'en-tête de sous-types, et j'aurai besoin d'un événement de compteur pour chaque sous-type, de sorte que je sais quel est le meilleur sous-en-tête de la cartographie.

Le pire des cas d'une représentation minimale d'un entièrement rempli compact liste se produit lorsque tous les sous-types sont également populaires. Dans ce cas, je vous enregistrer 1 bit pour tous les 3 sous-en-têtes, de sorte que la taille de la liste est 2*781250 + 7*1000000 - 781250/3 = 8302083.3 bits. L'arrondi d'un maximum de 32 bits limite de mot, c'est 8302112 bits, ou 1037764 octets.

1M moins le 2k pour le protocole TCP/IP de l'état et des tampons est 1022*1024 = 1046528 octets, me laissant 8764 octets pour jouer avec.

Mais quel est le processus de modification de la sous-liste de l'en-tête de la cartographie ? Dans la mémoire de la carte ci-dessous, "Z" est aléatoire, les frais généraux, les "=" est l'espace libre, "X" est la compacte de la liste.

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Démarrer la lecture à l'extrême gauche "X" et de commencer à écrire à le plus à gauche "=" et le travail à droite. Quand c'est fait, le compact liste sera un peu plus courte et il sera au mauvais bout de la mémoire:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

Alors je vais avoir besoin d'un shunt vers la droite:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Dans la tête de la cartographie des processus de changement, jusqu'à 1/3 de la sous-liste des en-têtes passera de 1 bit 2 bits. Dans le pire des cas, ils seront tous à la tête de la liste, donc je vais avoir besoin d'au moins 781250/3 bits de stockage gratuit avant de commencer, ce qui me ramène à la mémoire des exigences de la précédente version de la compacte de la liste :(

Pour contourner cela, je vais partager le 781250 des sous-listes en 10 sous-groupes de 78125 chacune des sous-listes. Chaque groupe dispose de son propre sous-en-tête de la cartographie. En utilisant les lettres A à J pour les groupes:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

Chaque sous-groupe se rétrécit ou reste la même au cours d'une sous-liste d'en-tête de la cartographie du changement:

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

Le pire des cas élargissement temporaire d'un sous-groupe lors d'une cartographie de modification est 78125/3 = 26042 bits, en vertu de la 4k. Si je puis me permettre 4k en plus de la 1037764 octets pour un entièrement rempli compact liste, qui me laisse 8764 - 4096 = 4668 octets pour le "Z"dans la carte mémoire.

Qui devrait être beaucoup pour les 10 sous-en-tête de tables de correspondance, 30 sous-en-tête de l'apparition des comtes et de l'autre quelques compteurs, des pointeurs et des petits tampons je vais avoir besoin, et l'espace que j'ai utilisé sans s'en apercevoir, comme espace de pile pour l'appel de fonction de l'adresse de retour et des variables locales.

La partie 3, combien de temps cela prendrait-il à courir ?

Avec un vide compact liste 1-liste des bits d'en-tête sera utilisé pour un vide sous-liste, et la taille de départ de la liste sera 781250 bits. Dans le pire des cas, la liste s'accroît de 8 bits pour chaque numéro est ajouté, donc 32 + 8 = 40 bits d'espace libre sont nécessaires pour chacun des nombres de 32 bits pour être placé au sommet de la liste de la mémoire tampon, puis triées et regroupées. Dans le pire des cas, la modification de la sous-liste d'en-tête les résultats de la cartographie dans l'utilisation de l'espace 2*781250 + 7*entrées - 781250/3 bits.

Avec une politique de changer les sous-en-tête de la cartographie après chaque cinquième de fusion une fois il y a au moins 800000 numéros dans la liste, un pire cas d'exécution impliquerait un total d'environ 30M de compact liste de lecture et d'écriture de l'activité.

Source:

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

Answer 5

Gilmanov réponse est très mal à cela des hypothèses. Il commence à spéculer dans un inutile mesure d'un million consécutives entiers. Cela signifie pas de lacunes. Les aléatoires lacunes, cependant petite, la rendre vraiment une mauvaise idée.

Essayez vous-même, obtenir 1 million de hasard 27 bits entiers, de les trier, de les compresser avec 7zip, xz, quel que soit l'algorithme LZMA vous le souhaitez. Le résultat est plus de 1,5 MO. La prémisse sur le dessus est la compression des numéros séquentiels. Même delta encodage est plus de 1,1 MO. Et jamais l'esprit, c'est à l'aide de plus de 100 mo de RAM pour la compression. Ainsi, même le comprimé entiers n'est pas le problème et de ne jamais l'esprit des temps d'exécution de l'utilisation de la RAM.

Il est triste la façon dont les gens juste upvote la beauté des graphismes et de la rationalisation.

#include <stdint.h>
#include <stdlib.h>
#include <time.h>

int32_t ints[1000000]; // random 27bit 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 32bit 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);

}

Maintenant compresser ints.bin avec LZMA...

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