Question Tri d'un million de numéros à 8 chiffres dans 1 Mo de RAM


J'ai un ordinateur avec 1 Mo de RAM et aucun autre stockage local. Je dois l'utiliser pour accepter 1 million de nombres décimaux à 8 chiffres sur une connexion TCP, les trier, puis envoyer la liste triée sur une autre connexion TCP.

La liste des numéros peut contenir des doublons, que je ne dois pas rejeter. Le code sera placé dans la ROM, donc je n'ai pas besoin de soustraire la taille de mon code de 1 Mo. J'ai déjà du code pour piloter le port Ethernet et gérer les connexions TCP / IP, et il nécessite 2 Ko pour ses données d'état, y compris un tampon de 1 Ko par lequel le code va lire et écrire des données. Y at-il une solution à ce problème?

Sources de questions et réponses
slashdot.org

cleaton.net


620


origine


Réponses:


Il y a un truc plutôt sournois qui n'est pas mentionné ici jusqu'à présent. Nous supposons que vous n'avez aucun moyen supplémentaire de stocker des données, mais ce n'est pas tout à fait vrai.

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

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

  • D'abord prendre 2 variables: COUNTER et VALUE.
  • Réglez d'abord tous les registres 0;
  • Chaque fois que vous recevez un nombre entier I, incrément COUNTER Et mettre VALUE à max(VALUE, I);
  • Envoyez ensuite un paquet de requête d'écho ICMP avec l'ensemble de données à I au routeur. Efface moi et répète.
  • Chaque fois que vous recevez le paquet ICMP retourné, vous extrayez simplement l'entier et renvoyez-le dans une autre requête d'écho. Cela produit un grand nombre de requêtes ICMP qui se propagent en arrière et en avant et qui contiennent les entiers.

Une fois que COUNTER atteint 1000000, vous avez toutes les valeurs stockées dans le flux incessant de requêtes ICMP, et VALUE contient maintenant l'entier maximum. Choisissez quelques threshold T >> 1000000. Ensemble COUNTER à zéro. Chaque fois que vous recevez un paquet ICMP, incrémentez COUNTER et renvoyer l'entier contenu I dans une autre requête d'écho, sauf si I=VALUE, auquel cas il est transmis à la destination pour les entiers triés. Une fois que COUNTER=T, décrément VALUE par 1, réinitialiser COUNTER à zéro et répétez. Une fois que VALUE atteint zéro, vous devriez avoir transmis tous les entiers dans l'ordre du plus grand au plus petit à la destination, et avez seulement utilisé environ 47 bits de RAM pour les deux variables persistantes (et tout petit montant dont vous avez besoin pour les valeurs temporaires).

Je sais que c'est horrible, et je sais qu'il peut y avoir toutes sortes de problèmes pratiques, mais je pensais que cela pourrait donner à certains d'entre vous un rire ou au moins vous horrifier.


406



Voici du code C ++ ce qui résout le problème.

Preuve que les contraintes de mémoire sont satisfaites:

Éditeur: Il n'y a aucune preuve des besoins de mémoire maximum offerts par l'auteur dans ce billet ou dans ses blogs. Puisque le nombre de bits nécessaires pour encoder une valeur dépend des valeurs précédemment codées, une telle preuve est probablement non triviale. L'auteur note que la plus grande taille codée sur laquelle il pouvait tomber empiriquement était 1011732, et choisi la taille de la mémoire tampon 1013000 arbitrairement.

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 baies prennent 1045000 octets de stockage. Cela laisse 1048576 - 1045000 - 2 × 1024 = 1528 octets pour les variables restantes et l'espace de pile.

Il fonctionne en environ 23 secondes sur mon Xeon W3520. Vous pouvez vérifier que le programme fonctionne en utilisant le script Python suivant, en supposant qu'un nom de programme 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!')

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


404



S'il vous plaît voir le première bonne réponse ou la réponse plus tard avec l'encodage arithmétique. Vous trouverez ci-dessous du plaisir, mais pas une solution 100% pare-balles.

C'est une tâche assez intéressante et voici une autre solution. J'espère que quelqu'un trouvera le résultat utile (ou du moins intéressant).

Étape 1: Structure de données initiale, approche de compression grossière, résultats de base

Faisons quelques calculs simples: nous avons 1M (1048576 octets) de RAM initialement disponible pour stocker 10 ^ 6 nombres décimaux à 8 chiffres. [0; 99999999]. Donc, pour stocker un nombre, 27 bits sont nécessaires (en supposant que les nombres non signés seront utilisés). Ainsi, pour stocker un flux brut ~ 3.5M de RAM sera nécessaire. Quelqu'un a déjà dit que cela ne semblait pas faisable, mais je dirais que la tâche peut être résolue si la contribution est «assez bonne». Fondamentalement, l'idée est de compresser les données d'entrée avec un facteur de compression de 0,29 ou plus et de faire le tri de manière appropriée.

Résolvons d'abord le problème de compression. Certains tests pertinents sont déjà disponibles:

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

"J'ai effectué un test pour compresser un million d'entiers consécutifs en utilisant   diverses formes de compression. Les résultats sont les suivants:"

None     4000027
Deflate  2006803
Filtered 1391833
BZip2    427067
Lzma     255040

On dirait LZMA (Algorithme de chaîne de Lempel-Ziv-Markov) est un bon choix pour continuer. J'ai préparé un simple PoC, mais il reste quelques détails à souligner:

  1. La mémoire est limitée, donc l'idée est de trier les numéros et d'utiliser Seaux compressés (taille dynamique) en tant que stockage temporaire
  2. Il est plus facile d'obtenir un meilleur facteur de compression avec des présaturés données, donc il y a un tampon statique pour chaque compartiment (les numéros du tampon doivent être triés avant LZMA)
  3. Chaque compartiment contient une plage spécifique, de sorte que le tri final peut être fait pour chaque seau séparément
  4. La taille du godet peut être correctement définie, il y aura donc assez de mémoire pour décompressez les données stockées et effectuez le tri final pour chaque compartiment séparément

In-memory sorting

S'il vous plaît noter, le code ci-joint est un POC, il ne peut pas être utilisé comme une solution finale, il démontre simplement l'idée d'utiliser plusieurs tampons plus petits pour stocker des nombres pré-triés d'une manière optimale (éventuellement compressé). LZMA n'est pas proposé comme solution finale. Il est utilisé comme moyen le plus rapide d'introduire une compression sur ce PoC.

Voir le code PoC ci-dessous (notez s'il vous plaît juste une démo, pour le compiler LZMA-Java sera nécessaire):

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, cela produit ce qui suit:

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 séquence ascendante simple (un seau est utilisé), il produit:

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 le La nature
  2. Utilisez une compression plus simple avec une empreinte mémoire plus faible
  3. Quelques indices supplémentaires sont vraiment nécessaires. Une solution pare-balles commune ne semble pas réalisable.

Étape 2: compression améliorée, conclusion finale

Comme cela a déjà été mentionné dans la section précédente, toute technique de compression appropriée peut être utilisée. Donc, débarrassons-nous de LZMA en faveur d'une approche plus simple et meilleure (si possible). Il y a beaucoup de bonnes solutions, y compris Codage arithmétique, Arbre de Radix etc.

Quoi qu'il en soit, un schéma d'encodage simple mais utile sera plus illustratif qu'une autre bibliothèque externe, fournissant un algorithme astucieux. La solution actuelle est assez simple: comme il existe des compartiments avec des données partiellement triées, les deltas peuvent être utilisés à la place des nombres.

encoding scheme

Le test d'entrée aléatoire 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, cette approche:

  1. ne consomme pas beaucoup de mémoire
  2. fonctionne avec les cours d'eau
  3. fournit pas si mauvais résultats

Le code complet peut être trouvé ici, Les implémentations BinaryInput et BinaryOutput peuvent être trouvées ici

Conclusion finale

Pas de conclusion finale :) Parfois, c'est vraiment une bonne idée de passer d'un niveau à l'autre et de revoir la tâche d'un méta-niveau point de vue.

C'était amusant de passer du temps avec cette tâche. BTW, il y a beaucoup de réponses intéressantes ci-dessous. Merci pour votre attention et bonne codification.


361



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

Partie 1, solution initiale

Cette approche nécessite un peu plus de 1M, je vais l'affiner pour l'intégrer dans 1M plus tard.

Je vais stocker une liste compacte triée de nombres dans la plage de 0 à 99999999 comme une séquence de sous-listes de nombres à 7 bits. La première sous-liste contient les nombres de 0 à 127, la deuxième sous-liste contient les nombres de 128 à 255, etc. 100000000/128 est exactement 781250, donc 781250 de telles sous-listes seront nécessaires.

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

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

00 Sous-liste vide, rien ne suit.

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

dix La sous-liste contient au moins deux nombres distincts. Les entrées sont stockées dans un ordre non décroissant, sauf que la dernière entrée est inférieure ou égale à la première. Cela permet d'identifier la fin de la sous-liste. Par exemple, les nombres 2,4,6 seraient stockés comme (4,6,2). Les nombres 2,2,3,4,4 seraient stockés comme (2,3,4,4,2).

11 La sous-liste contient deux répétitions ou plus d'un seul nombre. Les 7 bits suivants donnent le numéro. Viennent ensuite zéro ou plusieurs entrées de 7 bits avec la valeur 1, suivie d'une entrée de 7 bits avec la valeur 0. La longueur du corps de sous-liste dicte le nombre de répétitions. Par exemple, les nombres 12,12 seraient stockés comme (12,0), les nombres 12,12,12 seraient stockés comme (12,1,0), 12,12,12,12 seraient (12,1 , 1,0) et ainsi de suite.

Je commence par une liste vide, je lis un tas de nombres et je les stocke sous forme d'entiers 32 bits, je classe les nouveaux nombres (en utilisant heapsort, probablement) et ensuite je les fusionne dans une nouvelle liste triée compacte. Répétez jusqu'à ce qu'il n'y ait plus de nombres à lire, puis parcourez la liste compacte 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 l'opération de fusion de liste. Les "O" sont la région qui contient les entiers triés de 32 bits. Les "X" sont la région qui contient l'ancienne liste compacte. Les signes "=" sont la pièce d'expansion pour la liste compacte, 7 bits pour chaque entier dans les "O". Les "Z" sont d'autres frais généraux aléatoires.

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

La routine de fusion commence à lire à l'extrême gauche "O" et à l'extrême gauche "X", et commence à écrire à l'extrême gauche "=". Le pointeur d'écriture n'attrape pas le pointeur de lecture compact jusqu'à ce que tous les nouveaux entiers soient fusionnés, car les deux pointeurs avancent 2 bits pour chaque sous-liste et 7 bits pour chaque entrée dans l'ancienne liste compacte. Entrées de 7 bits pour les nouveaux numéros.

Partie 2, le bachotage en 1M

Pour compresser la solution ci-dessus en 1M, je dois rendre le format de liste compact un peu plus compact. Je vais me débarrasser de l'un des types de sous-listes, de sorte qu'il n'y aura que 3 valeurs d'en-tête de sous-liste possibles. Ensuite, je peux utiliser "00", "01" et "1" comme valeurs d'en-tête de sous-liste et enregistrer quelques bits. Les types de sous-liste sont:

Une sous-liste vide, rien ne suit.

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

C La sous-liste contient au moins deux nombres distincts. Les entrées sont stockées dans un ordre non décroissant, sauf que la dernière entrée est inférieure ou égale à la première. Cela permet d'identifier la fin de la sous-liste. Par exemple, les nombres 2,4,6 seraient stockés comme (4,6,2). Les nombres 2,2,3,4,4 seraient stockés comme (2,3,4,4,2).

D La sous-liste consiste en 2 répétitions ou plus d'un nombre unique.

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

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

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

Cela laisse juste des listes qui contiennent exactement deux répétitions d'un seul nombre. Je représenterai ceux avec un autre motif de sous-liste de type C impossible: "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 long que la sous-liste qu'il représente, ce qui rend les choses un peu plus complexes. Les cinq points d'interrogation à la fin peuvent être considérés comme ne faisant pas partie du motif, j'ai donc: "C {0NNNNN} {11N ????} 10" comme mon motif, avec le nombre à répéter stocké dans le "N" "s. C'est 2 bits trop long.

Je vais devoir emprunter 2 bits et les rembourser à partir des 4 bits inutilisés dans ce modèle. En lisant, en rencontrant "C {0NNNNNN} {11N00AB} 10", sortir 2 instances du nombre dans les "N", écraser le "10" à la fin avec les bits A et B, et rembobiner le pointeur de lecture par 2 morceaux. Les lectures destructives sont correctes pour cet algorithme, puisque chaque liste compacte ne peut être parcourue qu'une seule fois.

Lors de l'écriture d'une sous-liste de 2 répétitions d'un seul nombre, écrire "C {0NNNNNN} 11N00" et mettre les bits empruntés à 2. A chaque écriture où le compteur de bits empruntés est non nul, il est décrémenté pour chaque bit écrit et "10" est écrit lorsque le compteur atteint zéro. Donc, les 2 bits suivants vont aller dans les slots A et B, et ensuite le "10" va tomber sur la fin.

Avec 3 valeurs d'en-tête de sous-liste représentées par "00", "01" et "1", je peux attribuer "1" au type de sous-liste le plus populaire. J'ai besoin d'une petite table pour mapper les valeurs d'en-tête de sous-liste aux types de sous-listes, et j'ai besoin d'un compteur d'occurrences pour chaque type de sous-liste afin de savoir quel est le meilleur mappage d'en-tête.

La représentation minimale dans le pire des cas d'une liste compacte entièrement remplie se produit lorsque tous les types de sous-listes sont également populaires. Dans ce cas, j'économise 1 bit pour chaque 3 sous-titres, donc la taille de la liste est 2 * 781250 + 7 * 1000000 - 781250/3 = 8302083.3 bits. Arrondir à une limite de mot de 32 bits, c'est 8302112 bits ou 1037764 octets.

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

Mais qu'en est-il du processus de modification du mappage d'en-tête de sous-liste? Dans la carte mémoire ci-dessous, "Z" est aléatoire, "=" est un espace libre, "X" est la liste compacte.

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Commencez à lire à l'extrême gauche "X" et commencez à écrire à l'extrême gauche "=" et travaillez à droite. Quand c'est fait la liste compacte sera un peu plus courte et elle sera à la mauvaise fin de la mémoire:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

Alors je vais devoir le shunter vers la droite:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Dans le processus de modification de mappage d'en-tête, jusqu'à 1/3 des en-têtes de sous-liste passe de 1 à 2 bits. Dans le pire des cas, ils seront tous en tête de liste, j'ai donc besoin d'au moins 781250/3 bits de stockage avant de commencer, ce qui me ramène aux exigences de mémoire de la version précédente de la liste compacte: (

Pour contourner cela, je vais diviser les sous-listes 781250 en 10 sous-groupes de 78125 sous-listes chacun. Chaque groupe a son propre mappage d'en-tête de sous-liste indépendant. En utilisant les lettres A à J pour les groupes:

ZZZ=====AAAAAABBCCCCDDDDDEEEFFFGGGGGGGGGGGHHIJJJJJJJJJJJJJJJJJJJJ

Chaque groupe de sous-listes se rétrécit ou reste le même pendant un changement de mappage d'en-tête de sous-liste:

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 cas d'expansion temporaire d'un groupe de sous-listes au cours d'un changement de mappage est 78125/3 = 26042 bits, sous 4k. Si j'autorise 4k plus les 1037764 octets pour une liste compacte entièrement remplie, cela me laisse 8764 - 4096 = 4668 octets pour les "Z" dans la carte mémoire.

Cela devrait être suffisant pour les 10 tables de mappage d'en-tête, 30 compteurs d'occurrences d'en-tête et les autres compteurs, pointeurs et petits tampons dont j'ai besoin, et l'espace que j'ai utilisé sans remarquer, comme l'espace de pile pour les adresses de retour d'appel de fonction variables locales.

Partie 3, combien de temps cela prendrait-il pour courir?

Avec une liste compacte vide, l'en-tête de liste de 1 bit sera utilisé pour une sous-liste vide, et la taille de départ de la liste sera 781250 bits. Dans le pire des cas, la liste augmente de 8 bits pour chaque numéro ajouté, donc 32 + 8 = 40 bits d'espace libre sont nécessaires pour chacun des nombres de 32 bits à placer en haut du tampon de liste puis triés et fusionnés. Dans le pire des cas, la modification du mappage d'en-tête de sous-liste entraîne une utilisation de l'espace de 2 * 781250 + 7 * entrées - 781250/3 bits.

Avec une politique de modification du mappage d'en-tête de sous-liste après chaque cinquième fusion une fois qu'il y a au moins 800 000 numéros dans la liste, une exécution dans le pire des cas impliquerait un total d'environ 30M d'activité de lecture et d'écriture de liste compacte.

La source:

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


164



La réponse de Gilmanov est très fausse dans ses hypothèses. Il commence à spéculer basé sur un inutile mesure d'un million consécutif entiers. Cela signifie pas de lacunes. Ces lacunes aléatoires, si petites soient-elles, en font une mauvaise idée.

Essayez-le vous-même. Obtenez 1 million d'entiers aléatoires 27 bits, les trier, compresser avec 7-Zip, xz, quel que soit le LZMA que vous voulez. Le résultat est supérieur à 1,5 Mo. La prémisse sur le dessus est la compression des nombres séquentiels. Même codage delta de c'est plus de 1,1 Mo. Et peu importe que cela utilise plus de 100 Mo de RAM pour la compression. Donc, même les entiers compressés ne correspondent pas au problème et ne vous occupez jamais de l'utilisation de la mémoire RAM.

Cela m'attriste de voir comment les gens ont amélioré les graphismes et la rationalisation.

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

}

Maintenant compresser ints.bin avec 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



Je pense qu'une façon d'y penser est d'un point de vue combinatoire: combien y a-t-il de combinaisons possibles de triements de numéros triés? Si nous donnons la combinaison 0,0,0, ...., 0 le code 0, et 0,0,0, ..., 1 le code 1, et 99999999, 99999999, ... 99999999 le code N, qu'est-ce que N? En d'autres termes, quelle est la taille de l'espace de résultat?

Eh bien, une façon de penser à cela est de remarquer qu'il s'agit d'une bijection du problème de trouver le nombre de trajets monotones dans une grille N x M, où N = 1 000 000 et M = 100 000 000. En d'autres termes, si vous avez une grille de 1 000 000 de largeur et de 100 000 000 de hauteur, combien y a-t-il de plus courts chemins entre le bas à gauche et le haut à droite? Les chemins les plus courts exigent bien sûr que vous vous déplaciez à droite ou à gauche (si vous deviez vous déplacer vers le bas ou à gauche, vous annuleriez les progrès déjà accomplis). Pour voir comment ceci est une bijection de notre problème de tri des nombres, observez ce qui suit:

Vous pouvez imaginer n'importe quelle jambe horizontale dans notre chemin comme un nombre dans notre commande, où l'emplacement Y de la jambe représente la valeur.

enter image description here

Donc, si le chemin se déplace simplement vers la droite jusqu'à la fin, alors il saute tout en haut, c'est-à-dire que l'ordre est 0,0,0, ..., 0. si elle commence par sauter tout le chemin vers le haut, puis se déplace vers la droite 1 000 000 fois, ce qui équivaut à 99999999,99999999, ..., 99999999. Un chemin où il se déplace une fois, puis une fois, puis à droite , puis une fois, etc à la toute fin (saute nécessairement tout le chemin vers le haut), est équivalent à 0,1,2,3, ..., 999999.

Heureusement pour nous ce problème a déjà été résolu, une telle grille a (N + M) Choisir les chemins (M):

(1 000 000 + 100 000 000) Choisissez (100 000 000) ~ = 2,27 * 10 ^ 2436455

N est donc égal à 2.27 * 10 ^ 2436455, et donc le code 0 représente 0,0,0, ..., 0 et le code 2.27 * 10 ^ 2436455 et certains changements représentent 99999999,99999999, ..., 99999999.

Afin de stocker tous les nombres de 0 à 2.27 * 10 ^ 2436455 vous avez besoin de lg2 (2.27 * 10 ^ 2436455) = 8.0937 * 10 ^ 6 bits.

1 mégaoctet = 8388608 bits> 8093700 bits

Il semble donc que nous avons au moins assez de place pour stocker le résultat! Maintenant, bien sûr, le bit intéressant est de faire le tri lorsque les chiffres entrent en ligne de compte. Pas sûr que la meilleure approche à cela est donnée, nous avons 294908 bits restants. J'imagine qu'une technique intéressante consisterait à supposer que c'est la commande entière, trouver le code pour cet ordre, et puis que vous recevez un nouveau numéro en remontant et en mettant à jour le code précédent. Vague de main vague de la main.


40



Mes suggestions ici doivent beaucoup à La solution de Dan

Tout d'abord, je suppose que la solution doit gérer tout listes d'entrée possibles. Je pense que les réponses populaires ne font pas cette hypothèse (quelle IMO est une énorme erreur).

Il est connu qu'aucune forme de compression sans perte ne réduira la taille de toutes les entrées.

Toutes les réponses populaires supposent qu'ils seront en mesure d'appliquer une compression suffisamment efficace pour leur permettre un espace supplémentaire. En fait, un morceau d'espace supplémentaire est suffisamment grand pour contenir une partie de leur liste partiellement remplie sous une forme non compressée et leur permettre d'effectuer leurs opérations de tri. C'est juste une mauvaise hypothèse.

Pour une telle solution, toute personne ayant une connaissance de la façon dont elle effectue sa compression sera capable de concevoir des données d'entrée qui ne se compressent pas bien pour ce schéma, et la "solution" se cassera probablement en raison d'un manque d'espace.

Au lieu de cela, je prends une approche mathématique. Nos sorties possibles sont toutes les listes de longueur LEN constituées d'éléments dans la gamme 0..MAX. Ici, le LEN est 1 000 000 et notre MAX est 100 000 000.

Pour les LEN et MAX arbitraires, la quantité de bits nécessaire pour encoder cet état est:

Log2 (MAX Multichoose LEN)

Donc, pour nos chiffres, une fois que nous aurons terminé la réception et le tri, nous aurons besoin au moins de Log2 (100.000.000 MC 1.000.000) de bits pour stocker notre résultat d'une manière qui permet de distinguer de façon unique toutes les sorties possibles.

C'est ~ = 988kb. Nous avons donc assez d'espace pour tenir notre résultat. De ce point de vue, c'est possible.

[Suppression radicale inutile maintenant que de meilleurs exemples existent ...]

Meilleure réponse est là.

Une autre bonne réponse est là et utilise essentiellement le tri par insertion comme fonction permettant d'étendre la liste d'un élément (tamponne quelques éléments et pré-trie, pour permettre l'insertion de plus d'un à la fois, économise un peu de temps). utilise un bon codage d'état compact, des godets de sept deltas


19



Supposons que cette tâche est possible. Juste avant la sortie, il y aura une représentation en mémoire des millions de numéros triés. Combien de différentes représentations de ce type y a-t-il? Comme il peut y avoir des nombres répétés, nous ne pouvons pas utiliser nCr (choose), mais il y a une opération appelée multichoose qui fonctionne multisets.

  • Il y a 2.2e2436455 façons de choisir un million de numéros dans la gamme 0.99,999,999.
  • Cela exige 8 093 730 bits pour représenter chaque combinaison possible, soit 1 011 717 octets.

Donc, théoriquement, cela peut être possible, si vous pouvez arriver à une représentation saine (suffisante) de la liste des nombres triés. Par exemple, une représentation insensée peut nécessiter une table de recherche de 10 Mo ou des milliers de lignes de code.

Cependant, si "1M RAM" signifie un million d'octets, il n'y a clairement pas assez d'espace. Le fait que 5% de mémoire en plus le rende théoriquement possible me suggère que la représentation devra être TRÈS efficace et probablement pas saine d'esprit.


17