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 des 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 via 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

Il y a une astuce plutôt sournoise non mentionnée jusqu'ici. Nous supposons que vous n'avez aucun moyen supplémentaire de stocker des données, mais ce n'est pas strictement vrai.

Une façon de contourner votre problème est de faire la chose horrible suivante, qui ne devrait en aucun cas être tentée par quiconque: Utiliser le trafic réseau pour stocker des données. Et non, je ne parle pas de NAS.

Vous pouvez trier les nombres avec seulement quelques octets de RAM de la manière suivante:

• Prenez d'abord 2 variables: COUNTERet VALUE.
• Réglez d'abord tous les registres sur 0;
• Chaque fois que vous recevez un entier I, incrémentez COUNTERet réglez VALUEsur max(VALUE, I);
• Envoyez ensuite un paquet de demande d'écho ICMP avec l'ensemble de données Iau routeur. Effacez Iet répétez.
• Chaque fois que vous recevez le paquet ICMP retourné, vous extrayez simplement l'entier et le renvoyez dans une autre demande d'écho. Cela produit un grand nombre de requêtes ICMP se précipitant en arrière et en avant contenant les entiers.

Une fois COUNTERatteint 1000000, vous avez toutes les valeurs stockées dans le flux incessant de requêtes ICMP et VALUEcontient maintenant l'entier maximum. Choisissez-en threshold T >> 1000000. Mis COUNTERà zéro. Chaque fois que vous recevez un paquet ICMP, incrémentez COUNTERet renvoyez l'entier contenu Idans une autre demande d'écho, sauf I=VALUEdans ce cas, transmettez-le à la destination des entiers triés. Une fois COUNTER=T, décrément VALUEpar 1, remettre COUNTERà zéro et répéter. Une fois VALUEatteint zéro, vous devez avoir transmis tous les entiers dans l'ordre, du plus grand au plus petit, vers la destination, et avoir utilisé seulement environ 47 bits de RAM pour les deux variables persistantes (et quelle que soit la petite quantité 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 faire rire certains d'entre vous ou du moins vous horrifier.

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

Preuve que les contraintes de mémoire sont satisfaites:

Éditeur: Il n'y a aucune preuve de la mémoire maximale requise par l'auteur ni dans cet article ni dans ses blogs. Étant donné que le nombre de bits nécessaires pour coder 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 1011732et a choisi 1013000arbitrairement la taille de la mémoire tampon .

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

Il s'exécute en environ 23 secondes sur mon Xeon W3520. Vous pouvez vérifier que le programme fonctionne en utilisant le script Python suivant, en supposant 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 suivante:

• Explication du tri de 1 Mo
• Codage arithmétique et problème de tri de 1 Mo
• Codage arithmétique utilisant des mathématiques à virgule fixe

Veuillez consulter la première réponse correcte ou la réponse ultérieure avec codage arithmétique . Ci-dessous, vous trouverez peut-être 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 initiale des données, 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 numéro, 27 bits sont nécessaires (en supposant que des numéros non signés seront utilisés). Ainsi, pour stocker un flux brut, 3,5 Mo de RAM seront nécessaires. Quelqu'un a déjà dit que cela ne semblait pas possible, mais je dirais que la tâche peut être résolue si l'entrée 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 un 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

Il semble que LZMA ( algorithme de chaîne Lempel – Ziv – Markov ) soit un bon choix pour continuer. J'ai préparé un PoC simple, mais il reste encore quelques détails à souligner:

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

Veuillez noter que le code joint est un POC , il ne peut pas être utilisé comme solution finale, il démontre simplement l'idée d'utiliser plusieurs tampons plus petits pour stocker les numéros pré-triés de manière optimale (éventuellement compressés). Le LZMA n'est pas proposé comme solution finale. Il est utilisé comme moyen le plus rapide pour introduire une compression dans ce PoC.

Voir le code PoC ci-dessous (veuillez le noter 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 seul compartiment 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

ÉDITER

Conclusion:

1. N'essayez pas de tromper la nature
2. Utilisez une compression plus simple avec une empreinte mémoire réduite
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. Alors débarrassons-nous de LZMA en faveur d'une approche plus simple et meilleure (si possible). Il existe de nombreuses bonnes solutions, notamment le codage arithmétique , l' arbre Radix, etc.

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

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 que cette approche:

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

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 monter d'un niveau et de revoir la tâche d'un point de vue méta-niveau .

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 joyeux codage.

Une solution n'est possible qu'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 de numéros à 8 chiffres avec des doublons autorisés et de commander 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 a besoin d'un peu plus de 1M, je vais l'affiner pour l'adapter à 1M plus tard.

Je vais stocker une liste triée compacte de nombres compris entre 0 et 99999999 sous la forme d'une séquence de sous-listes de nombres à 7 bits. La première sous-liste contient des nombres de 0 à 127, la deuxième sous-liste contient des 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 occupe 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 où commence la suivante. La mémoire totale requise pour une liste entièrement remplie est de 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 bits suivants la contiennent.

10 La sous-liste contient au moins 2 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 sous la forme (4,6,2). Les nombres 2,2,3,4,4 seraient stockés sous la forme (2,3,4,4,2).

11 La sous-liste contient au moins 2 répétitions d'un même numéro. Les 7 bits suivants donnent le nombre. Viennent ensuite zéro ou plusieurs entrées de 7 bits avec la valeur 1, suivies 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 trie les nouveaux numéros en place (à l'aide de heapsort, probablement), puis je les fusionne dans une nouvelle liste triée compacte. Répétez jusqu'à ce qu'il n'y ait plus de chiffres à lire, puis parcourez à nouveau la liste compacte 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 l'espace d'extension 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 au "O" le plus à gauche et au "X" le plus à gauche, et commence à écrire au "=" le plus à gauche. Le pointeur d'écriture n'attrape pas le pointeur de lecture de liste compacte 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 de l'ancienne liste compacte, et il y a suffisamment d'espace supplémentaire pour le Entrées 7 bits pour les nouveaux numéros.

Partie 2, entasser en 1M

Pour compresser la solution ci-dessus en 1 Mo, je dois rendre le format de liste compact un peu plus compact. Je vais me débarrasser de l'un des types de sous-liste, de sorte qu'il n'y aura que 3 différentes 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-listes 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 bits suivants la contiennent.

C La sous-liste contient au moins 2 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 sous la forme (4,6,2). Les nombres 2,2,3,4,4 seraient stockés sous la forme (2,3,4,4,2).

D La sous-liste consiste en 2 répétitions ou plus d'un même numéro.

Mes 3 valeurs d'en-tête de sous-liste seront "A", "B" et "C", j'ai donc 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, car la troisième entrée est inférieure à la seconde mais supérieure à 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 l'utiliser pour représenter une sous-liste composée de 3 répétitions ou plus d'un même numéro. Les deux premiers mots de 7 bits codent le nombre (les "N" bits ci-dessous) et sont suivis de zéro ou plusieurs mots {0100001} 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 2 répétitions d'un même numéro. Je vais représenter 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 modèle, j'ai donc: "C {0NNNNNN} {11N ????} 10" comme modèle, avec le nombre à répéter stocké dans le "N "s. C'est 2 bits de trop.

Je vais devoir emprunter 2 bits et les rembourser sur les 4 bits inutilisés de ce modèle. Lors de la lecture, en rencontrant "C {0NNNNNN} {11N00AB} 10", sortez 2 instances du nombre dans les "N", écrasez le "10" à la fin avec les bits A et B et rembobinez le pointeur de lecture de 2 morceaux. Les lectures destructives sont acceptables pour cet algorithme, car chaque liste compacte n'est parcourue qu'une seule fois.

Lors de l'écriture d'une sous-liste de 2 répétitions d'un même nombre, écrivez "C {0NNNNNN} 11N00" et réglez le compteur de bits empruntés sur 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. Ainsi, les 2 bits suivants écrits iront dans les emplacements A et B, puis le "10" sera déposé à la fin.

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

La pire représentation minimale d'une liste compacte entièrement remplie se produit lorsque tous les types de sous-listes sont également populaires. Dans ce cas, j'enregistre 1 bit pour 3 en-têtes de sous-liste, la taille de la liste est donc de 2 * 781250 + 7 * 1000000 - 781250/3 = 8302083,3 bits. Arrondi à une limite de mots de 32 bits, soit 8302112 bits ou 1037764 octets.

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

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 une surcharge aléatoire, "=" est un espace libre, "X" est la liste compacte.

ZZZ=====XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Commencez à lire au "X" le plus à gauche et commencez à écrire au "=" le plus à gauche et travaillez à droite. Une fois terminé, la liste compacte sera un peu plus courte et se trouvera à la mauvaise extrémité de la mémoire:

ZZZXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX=======

Alors je vais devoir le shunter vers la droite:

ZZZ=======XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

Pour contourner cela, je vais diviser les sous-listes 781250 en 10 groupes de sous-listes 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 diminue ou reste le même lors d'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

La pire expansion temporaire d'un groupe de sous-listes lors 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 de sous-liste, 30 comptes d'occurrence d'en-tête de sous-liste et les quelques autres compteurs, pointeurs et petits tampons dont j'ai besoin, et l'espace que j'ai utilisé sans le remarquer, comme l'espace de pile pour les adresses de retour d'appel de fonction et variables locales.

Partie 3, combien de temps faudrait-il pour fonctionner?

Avec une liste compacte vide, l'en-tête de liste 1 bit sera utilisé pour une sous-liste vide, et la taille de départ de la liste sera de 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 numéros 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 800000 numéros dans la liste, une exécution dans le pire des cas impliquerait un total d'environ 30 millions d'activités de lecture et d'écriture de liste compacte.

La source:

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

La réponse de Gilmanov est très fausse dans ses hypothèses. Il commence à spéculer sur la base d'une mesure inutile d'un million d' entiers consécutifs . Cela signifie pas de lacunes. Ces écarts aléatoires, même minimes, en font vraiment une mauvaise idée.

Essayez-le vous-même. Obtenez 1 million d'entiers aléatoires de 27 bits, triez-les, compressez avec 7-Zip , xz, quel que soit le LZMA que vous voulez. Le résultat est supérieur à 1,5 Mo. La prémisse en haut est la compression des nombres séquentiels. Même le codage delta de qui est plus de 1,1 MB . Et peu importe, cela utilise plus de 100 Mo de RAM pour la compression. Ainsi, même les entiers compressés ne conviennent pas au problème et ne vous occupez jamais de l'utilisation de la RAM au moment de l'exécution .

Cela m'attriste de voir que les gens votent pour de jolis 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);

}

Compressez maintenant 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

Je pense qu'une façon de penser à cela est du point de vue de la combinatoire: combien de combinaisons possibles d'ordonnances de numéros triées existe-t-il? 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 chemins 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 chemins les plus courts du bas à gauche vers le haut à droite? Bien entendu, les chemins les plus courts ne vous obligent à vous déplacer que vers la droite ou vers le haut (si vous descendiez ou descendiez, vous annuleriez les progrès accomplis précédemment). Pour voir en quoi il s'agit d'une bijection de notre problème de tri des nombres, observez ce qui suit:

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

Donc, si le chemin se déplace simplement vers la droite jusqu'à la fin, puis saute complètement vers le haut, c'est l'équivalent de l'ordre 0,0,0, ..., 0. s'il commence à la place par un saut 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 à droite, puis une fois vers le haut, puis à droite , puis une fois, etc. jusqu'au bout (puis saute nécessairement jusqu'au sommet), équivaut à 0,1,2,3, ..., 999999.

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

(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.

Pour stocker tous les nombres compris entre 0 et 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 ayons au moins suffisamment d'espace pour stocker le résultat! Maintenant, bien sûr, le bit intéressant fait le tri au fur et à mesure que les nombres affluent. Je ne suis pas sûr que la meilleure approche soit donnée, il nous reste 294908 bits. J'imagine qu'une technique intéressante serait de supposer à chaque point qu'il s'agit de la commande entière, de trouver le code de cette commande, puis que vous receviez un nouveau numéro en remontant et en mettant à jour le code précédent. Vague de main Vague de main.

Mes suggestions ici doivent beaucoup à la solution de Dan

Tout d'abord, je suppose que la solution doit gérer toutes les listes d'entrée possibles. Je pense que les réponses populaires ne font pas cette hypothèse (ce que l'OMI 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’elles pourront appliquer une compression suffisamment efficace pour leur laisser plus d’espace. En fait, un morceau d'espace supplémentaire 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 connaissant la façon dont elle effectue sa compression sera en mesure de concevoir des données d'entrée qui ne se compressent pas bien pour ce schéma, et la "solution" se cassera très probablement à cause du 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 plage 0..MAX. Ici, le LEN est de 1 000 000 et notre MAX de 100 000 000.

Pour arbitraire LEN et MAX, la quantité de bits nécessaires pour coder 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 d'au moins Log2 (100 000 000 MC 1 000 000) bits pour stocker notre résultat d'une manière qui puisse distinguer de manière unique toutes les sorties possibles.

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

[Suppression inutile de la randonnée maintenant qu'il existe de meilleurs exemples ...]

La meilleure réponse est ici .

Une autre bonne réponse est ici et utilise essentiellement le tri par insertion comme fonction pour étendre la liste d'un élément (met en mémoire tampon quelques éléments et pré-trie, pour permettre l'insertion de plusieurs éléments à la fois, économise un peu de temps). utilise également un bon codage d'état compact, des segments de deltas de sept bits

Supposons que cette tâche soit possible. Juste avant la sortie, il y aura une représentation en mémoire du million de numéros triés. Combien de représentations différentes existe-t-il? Puisqu'il peut y avoir des nombres répétés, nous ne pouvons pas utiliser nCr (choisir), mais il existe une opération appelée multichoose qui fonctionne sur les multisets .

• Il existe 2,2e2436455 façons de choisir un million de numéros dans la plage 0..99,999,999.
• Cela nécessite 8 093 730 bits pour représenter toutes les combinaisons possibles, soit 1 011 717 octets.

Donc, théoriquement, cela peut être possible, si vous pouvez trouver une représentation saine (suffisante) de la liste triée de nombres. 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 de RAM" signifie un million d'octets, alors il n'y a clairement pas assez d'espace. Le fait que 5% de mémoire en plus le rend théoriquement possible me suggère que la représentation devra être TRÈS efficace et probablement pas sensée.

(Ma réponse originale était fausse, désolé pour les mauvais calculs, voir ci-dessous la pause.)

Que dis-tu de ça?

Les 27 premiers bits stockent le nombre le plus bas que vous avez vu, puis la différence avec le nombre suivant vu, codés comme suit: 5 bits pour stocker le nombre de bits utilisés pour stocker la différence, puis la différence. Utilisez 00000 pour indiquer que vous avez revu ce numéro.

Cela fonctionne parce que plus de nombres sont insérés, la différence moyenne entre les nombres diminue, vous utilisez donc moins de bits pour stocker la différence lorsque vous ajoutez plus de nombres. Je crois que cela s'appelle une liste delta.

Le pire cas auquel je puisse penser est que tous les nombres sont espacés uniformément (par 100), par exemple en supposant que 0 est le premier nombre:

000000000000000000000000000 00111 1100100
                            ^^^^^^^^^^^^^
                            a million times

27 + 1,000,000 * (5+7) bits = ~ 427k

Reddit à la rescousse!

Si tout ce que vous aviez à faire était de les trier, ce problème serait facile. Il faut 122k (1 million de bits) pour stocker les nombres que vous avez vus (0ème bit si 0 a été vu, 2300ème bit si 2300 a été vu, etc.

Vous lisez les nombres, les stockez dans le champ de bits, puis décalez les bits tout en conservant un décompte.

MAIS, vous devez vous rappeler combien vous en avez vu. J'ai été inspiré par la réponse de la sous-liste ci-dessus pour arriver à ce schéma:

Au lieu d'utiliser un bit, utilisez 2 ou 27 bits:

• 00 signifie que vous n'avez pas vu le numéro.
• 01 signifie que vous l'avez vu une fois
• 1 signifie que vous l'avez vu, et les 26 bits suivants sont le nombre de fois.

Je pense que cela fonctionne: s'il n'y a pas de doublons, vous avez une liste de 244 Ko. Dans le pire des cas, vous voyez chaque numéro deux fois (si vous voyez un numéro trois fois, cela raccourcit le reste de la liste pour vous), cela signifie que vous avez vu 50000 plus d'une fois et que vous avez vu 950000 éléments 0 ou 1 fois.

50 000 * 27 + 950 000 * 2 = 396,7 k.

Vous pouvez apporter d'autres améliorations si vous utilisez l'encodage suivant:

0 signifie que vous n'avez pas vu le nombre 10 signifie que vous l'avez vu une fois 11 est la façon dont vous comptez

Ce qui se traduira en moyenne par 280,7k de stockage.

EDIT: mes mathématiques du dimanche matin étaient erronées.

Le pire des cas est que nous voyons deux fois 500 000 nombres, donc le calcul devient:

500 000 * 27 + 500 000 * 2 = 1,77 M

Le codage alternatif se traduit par un stockage moyen de

500 000 * 27 + 500 000 = 1,70 M

: (

Il existe une solution à ce problème pour toutes les entrées possibles. Tricher.

1. Lisez les valeurs m sur TCP, où m est proche du maximum qui peut être trié en mémoire, peut-être n / 4.
2. Triez les 250 000 (ou plus) nombres et sortez-les.
3. Répétez l'opération pour les 3 autres trimestres.
4. Laissez le récepteur fusionner les 4 listes de numéros qu'il a reçues pendant qu'il les traite. (Ce n'est pas beaucoup plus lent que d'utiliser une seule liste.)

Je voudrais essayer un arbre Radix . Si vous pouviez stocker les données dans une arborescence, vous pourriez alors faire un cheminement dans l'ordre pour transmettre les données.

Je ne suis pas sûr que vous puissiez intégrer cela dans 1 Mo, mais je pense que cela vaut la peine d'essayer.

Quel type d'ordinateur utilisez-vous? Il peut ne pas avoir d'autre stockage local "normal", mais a-t-il une RAM vidéo, par exemple? 1 mégapixel x 32 bits par pixel (disons) est assez proche de la taille d'entrée de données requise.

(Je demande en grande partie à la mémoire de l'ancien PC Acorn RISC , qui pourrait "emprunter" la VRAM pour étendre la RAM système disponible, si vous choisissez un mode d'écran à faible résolution ou à faible profondeur de couleur!). C'était plutôt utile sur une machine avec seulement quelques Mo de RAM normale.

Une représentation arborescente de radix serait près de gérer ce problème, car l'arbre radix tire parti de la "compression de préfixe". Mais il est difficile de concevoir une représentation d'arbre radix qui pourrait représenter un seul nœud dans un octet - deux est probablement à peu près la limite.

Mais, quelle que soit la façon dont les données sont représentées, une fois triées, elles peuvent être stockées sous forme de préfixe compressé, où les nombres 10, 11 et 12 seraient représentés, disons 001b, 001b, 001b, indiquant un incrément de 1 du numéro précédent. Peut-être que 10101b représenterait alors un incrément de 5, 1101001b un incrément de 9, etc.

Il y a 10 ^ 6 valeurs dans une plage de 10 ^ 8, il y a donc une valeur pour cent points de code en moyenne. Enregistrez la distance entre le Nème point et le (N + 1) ème. Les valeurs en double ont un saut de 0. Cela signifie que le saut a besoin d'une moyenne d'un peu moins de 7 bits pour être stocké, donc un million d'entre elles s'intégrera avec plaisir dans nos 8 millions de bits de stockage.

Ces sauts doivent être codés dans un flux binaire, par exemple par le codage Huffman. L'insertion se fait par itération dans le train de bits et réécriture après la nouvelle valeur. Sortie en itérant et en écrivant les valeurs implicites. Pour des raisons pratiques, cela veut probablement être fait comme, disons, 10 ^ 4 listes couvrant 10 ^ 4 points de code (et une moyenne de 100 valeurs) chacune.

Un bon arbre de Huffman pour les données aléatoires peut être construit a priori en supposant une distribution de Poisson (moyenne = variance = 100) sur la longueur des sauts, mais des statistiques réelles peuvent être conservées sur l'entrée et utilisées pour générer un arbre optimal pour traiter cas pathologiques.

J'ai un ordinateur avec 1 Mo de RAM et aucun autre stockage local

Une autre façon de tricher: vous pouvez utiliser un stockage non local (en réseau) à la place (votre question ne l'empêche pas) et appeler un service en réseau qui pourrait utiliser un fusionnement sur disque simple (ou juste assez de RAM pour trier en mémoire, puisque vous ne doivent accepter que des nombres 1M), sans avoir besoin des solutions (certes extrêmement ingénieuses) déjà données.

Cela peut être de la triche, mais il n'est pas clair si vous cherchez une solution à un problème du monde réel, ou un puzzle qui invite à plier les règles ... si ce dernier, alors une simple triche peut obtenir de meilleurs résultats qu'un complexe mais une solution "authentique" (qui, comme d'autres l'ont souligné, ne peut fonctionner que pour les intrants compressibles).

Je pense que la solution est de combiner des techniques de codage vidéo, à savoir la transformation discrète en cosinus. En vidéo numérique, plutôt qu'en enregistrant la modification de la luminosité ou de la couleur de la vidéo sous forme de valeurs normales telles que 110 112 115 116, chacune est soustraite de la dernière (similaire au codage de la longueur de la séquence). 110 112 115 116 devient 110 2 3 1. Les valeurs, 2 3 1 nécessitent moins de bits que les originaux.

Disons donc que nous créons une liste des valeurs d'entrée lorsqu'elles arrivent sur le socket. Nous stockons dans chaque élément, non pas la valeur, mais le décalage de celui qui le précède. Nous trions au fur et à mesure, donc les compensations ne seront que positives. Mais le décalage pourrait être de 8 chiffres décimaux de large, ce qui correspond à 3 octets. Chaque élément ne peut pas faire 3 octets, nous devons donc les emballer. Nous pourrions utiliser le bit supérieur de chaque octet comme un "bit continu", indiquant que l'octet suivant fait partie du nombre et que les 7 bits inférieurs de chaque octet doivent être combinés. zéro est valable pour les doublons.

Au fur et à mesure que la liste se remplit, les nombres doivent se rapprocher, ce qui signifie qu'en moyenne, seulement 1 octet est utilisé pour déterminer la distance jusqu'à la valeur suivante. 7 bits de valeur et 1 bit de décalage si cela est pratique, mais il peut y avoir un point faible qui nécessite moins de 8 bits pour une valeur "continuer".

Quoi qu'il en soit, j'ai fait une expérience. J'utilise un générateur de nombres aléatoires et je peux adapter un million de nombres décimaux triés à 8 chiffres en environ 1279000 octets. L'espace moyen entre chaque numéro est toujours de 99 ...

public class Test {
    public static void main(String[] args) throws IOException {
        // 1 million values
        int[] values = new int[1000000];

        // create random values up to 8 digits lrong
        Random random = new Random();
        for (int x=0;x<values.length;x++) {
            values[x] = random.nextInt(100000000);
        }
        Arrays.sort(values);

        ByteArrayOutputStream baos = new ByteArrayOutputStream();

        int av = 0;    
        writeCompact(baos, values[0]);     // first value
        for (int x=1;x<values.length;x++) {
            int v = values[x] - values[x-1];  // difference
            av += v;
            System.out.println(values[x] + " diff " + v);
            writeCompact(baos, v);
        }

        System.out.println("Average offset " + (av/values.length));
        System.out.println("Fits in " + baos.toByteArray().length);
    }

    public static void writeCompact(OutputStream os, long value) throws IOException {
        do {
            int b = (int) value & 0x7f;
            value = (value & 0x7fffffffffffffffl) >> 7;
            os.write(value == 0 ? b : (b | 0x80));
        } while (value != 0);
    }
}

Nous pourrions jouer avec la pile de mise en réseau pour envoyer les numéros dans l'ordre trié avant d'avoir tous les numéros. Si vous envoyez 1M de données, TCP / IP les divisera en paquets de 1 500 octets et les diffusera en continu vers la cible. Chaque paquet recevra un numéro de séquence.

Nous pouvons le faire à la main. Juste avant de remplir notre RAM, nous pouvons trier ce que nous avons et envoyer la liste à notre cible mais laisser des trous dans notre séquence autour de chaque numéro. Ensuite, traitez le 2ème 1/2 des nombres de la même manière en utilisant ces trous dans la séquence.

La pile de mise en réseau à l'extrémité distante assemblera le flux de données résultant dans l'ordre avant de le remettre à l'application.

Il utilise le réseau pour effectuer un tri par fusion. Il s'agit d'un hack total, mais j'ai été inspiré par les autres hack de réseau répertoriés précédemment.

(Mauvaise) approche de Google , à partir du fil HN. Stockez les nombres de style RLE.

Votre structure de données initiale est '99999999: 0' (tous les zéros, n'ont vu aucun nombre), puis disons que vous voyez le nombre 3,866,344 pour que votre structure de données devienne '3866343: 0,1: 1,96133654: 0' lorsque vous peut voir que les nombres alterneront toujours entre le nombre de bits zéro et le nombre de bits "1", vous pouvez donc supposer que les nombres impairs représentent 0 bits et les nombres pairs 1 bits. Cela devient (3866343,1,96133654)

Leur problème ne semble pas couvrir les doublons, mais disons qu'ils utilisent "0: 1" pour les doublons.

Gros problème # 1: les insertions pour des entiers 1M prendraient des âges .

Gros problème n ° 2: comme toutes les solutions d'encodage delta standard, certaines distributions ne peuvent pas être couvertes de cette façon. Par exemple, 1 m d'entiers avec des distances 0:99 (par exemple +99 chacun). Pensez maintenant de la même façon, mais avec une distance aléatoire de l' ordre de 0:99 . (Remarque: 99999999/1000000 = 99,99)

L'approche de Google est à la fois indigne (lente) et incorrecte. Mais pour leur défense, leur problème aurait pu être légèrement différent.

Pour représenter le tableau trié, il suffit de stocker le premier élément et la différence entre les éléments adjacents. De cette façon, nous nous préoccupons de coder 10 ^ 6 éléments qui peuvent résumer jusqu'à 10 ^ 8 au maximum. Appelons cette D . Pour coder les éléments de D, on peut utiliser un code Huffman . Le dictionnaire du code Huffman peut être créé en déplacement et le tableau mis à jour chaque fois qu'un nouvel élément est inséré dans le tableau trié (tri par insertion). Notez que lorsque le dictionnaire change en raison d'un nouvel élément, l'ensemble du tableau doit être mis à jour pour correspondre au nouvel encodage.

Le nombre moyen de bits pour coder chaque élément de D est maximisé si nous avons un nombre égal de chaque élément unique. Dire les éléments d1 , d2 , ..., dN dans D apparaissent chacun F fois. Dans ce cas (dans le pire des cas, nous avons à la fois 0 et 10 ^ 8 dans la séquence d'entrée), nous avons

somme (1 <= i <= N ) F . di = 10 ^ 8

où

sum (1 <= i <= N ) F = 10 ^ 6, ou F = 10 ^ 6 / N et la fréquence normalisée sera p = F / 10 ^ = 1 / N

Le nombre moyen de bits sera -log2 (1 / P ) = log2 ( N ). Dans ces circonstances , nous devons trouver un cas qui maximise N . Cela se produit si nous avons des nombres consécutifs pour di partir de 0, ou, di = i -1, donc

10 ^ 8 = somme (1 <= i <= N ) F . di = somme (1 <= i <= N ) (10 ^ 6 / N ) (i-1) = (10 ^ 6 / N ) N ( N -1) / 2

c'est à dire

N <= 201. Et dans ce cas, le nombre moyen de bits est log2 (201) = 7,6511, ce qui signifie que nous aurons besoin d'environ 1 octet par élément d'entrée pour enregistrer le tableau trié. Notez que cela ne signifie pas que D en général ne peut pas avoir plus de 201 éléments. Cela sème juste que si les éléments de D sont uniformément distribués, il ne peut pas avoir plus de 201 valeurs uniques.

J'exploiterais le comportement de retransmission de TCP.

1. Faites en sorte que le composant TCP crée une grande fenêtre de réception.
2. Recevez une certaine quantité de paquets sans envoyer un ACK pour eux.
   • Traitez ceux des passes en créant une structure de données compressée (préfixe)
   • Envoyer un accusé de réception en double pour le dernier paquet qui n'est plus nécessaire / attendre le délai d'expiration de la retransmission
   • Goto 2
3. Tous les paquets ont été acceptés

Cela suppose une sorte d'avantage de seaux ou de passes multiples.

Probablement en triant les lots / seaux et en les fusionnant. -> arbres radix

Utilisez cette technique pour accepter et trier les 80 premiers%, puis lisez les 20 derniers%, vérifiez que les 20 derniers% ne contiennent pas de nombres qui atterriraient dans les 20 premiers% des nombres les plus bas. Ensuite, envoyez les 20% des numéros les plus bas, supprimez de la mémoire, acceptez les 20% restants des nouveaux numéros et fusionnez. **

Voici une solution généralisée à ce type de problème:

Procédure générale

L'approche adoptée est la suivante. L'algorithme fonctionne sur un seul tampon de mots de 32 bits. Il exécute la procédure suivante en boucle:

• Nous commençons avec un tampon rempli de données compressées de la dernière itération. Le tampon ressemble à ceci

  |compressed sorted|empty|

• Calculez la quantité maximale de nombres pouvant être stockés dans ce tampon, compressés et non compressés. Divisez le tampon en ces deux sections, en commençant par l'espace pour les données compressées, en terminant par les données non compressées. Le tampon ressemble à

  |compressed sorted|empty|empty|

• Remplissez la section non compressée avec des nombres à trier. Le tampon ressemble à

  |compressed sorted|empty|uncompressed unsorted|

• Triez les nouveaux numéros avec un tri sur place. Le tampon ressemble à

  |compressed sorted|empty|uncompressed sorted|

• Alignez à droite toutes les données déjà compressées de l'itération précédente dans la section compressée. À ce stade, le tampon est partitionné

  |empty|compressed sorted|uncompressed sorted|

• Effectuez une décompression-recompression en continu sur la section compressée, en fusionnant les données triées dans la section non compressée. L'ancienne section compressée est consommée à mesure que la nouvelle section compressée se développe. Le tampon ressemble à

  |compressed sorted|empty|

Cette procédure est effectuée jusqu'à ce que tous les numéros aient été triés.

Compression

Cet algorithme ne fonctionne bien sûr que lorsqu'il est possible de calculer la taille compressée finale du nouveau tampon de tri avant de savoir réellement ce qui sera réellement compressé. À côté de cela, l'algorithme de compression doit être suffisamment bon pour résoudre le problème réel.

L'approche utilisée comporte trois étapes. Premièrement, l'algorithme stockera toujours des séquences triées, donc nous pouvons à la place stocker uniquement les différences entre les entrées consécutives. Chaque différence se situe dans la plage [0, 99999999].

Ces différences sont ensuite codées comme un train binaire unaire. Un 1 dans ce flux signifie "Ajouter 1 à l'accumulateur, A 0 signifie" Emettre l'accumulateur en entrée et réinitialiser ". Ainsi, la différence N sera représentée par N 1 et un 0.

La somme de toutes les différences approchera de la valeur maximale prise en charge par l'algorithme et le nombre de toutes les différences approchera de la quantité de valeurs insérées dans l'algorithme. Cela signifie que nous nous attendons à ce que le flux contienne à la fin la valeur maximale de 1 et le nombre de 0. Cela nous permet de calculer la probabilité attendue d'un 0 et 1 dans le flux. À savoir, la probabilité d'un 0 est count/(count+maxval)et la probabilité d'un 1 estmaxval/(count+maxval) .

Nous utilisons ces probabilités pour définir un modèle de codage arithmétique sur ce flux binaire. Ce code arithmétique encodera exactement ces quantités de 1 et de 0 dans un espace optimal. Nous pouvons calculer l'espace utilisé par ce modèle pour tout bitstream intermédiaire comme: bits = encoded * log2(1 + amount / maxval) + maxval * log2(1 + maxval / amount). Pour calculer l'espace total requis pour l'algorithme, définissezencoded égal à montant.

Pour ne pas exiger une quantité ridicule d'itérations, une petite surcharge peut être ajoutée au tampon. Cela garantira que l'algorithme fonctionnera au moins sur la quantité de nombres qui correspondent à cette surcharge, car de loin le plus grand coût en temps de l'algorithme est la compression et la décompression du codage arithmétique à chaque cycle.

À côté de cela, une surcharge est nécessaire pour stocker des données de comptabilité et pour gérer de légères inexactitudes dans l'approximation à virgule fixe de l'algorithme de codage arithmétique, mais au total, l'algorithme est capable de tenir dans 1 Mo d'espace, même avec un tampon supplémentaire qui peut contenir 8000 numéros, pour un total de 1043916 octets d'espace.

L'optimalité

En dehors de la réduction de la (petite) surcharge de l'algorithme, il devrait être théoriquement impossible d'obtenir un résultat plus petit. Pour contenir juste l'entropie du résultat final, 1011717 octets seraient nécessaires. Si nous soustrayons le tampon supplémentaire ajouté pour plus d'efficacité, cet algorithme utilise 1011916 octets pour stocker le résultat final + la surcharge.

Si le flux d'entrée pouvait être reçu plusieurs fois, ce serait beaucoup plus facile (aucune information à ce sujet, problème d'idée et de performance temporelle).

Ensuite, nous pourrions compter les valeurs décimales. Avec des valeurs comptées, il serait facile de créer le flux de sortie. Compressez en comptant les valeurs. Cela dépend de ce qui serait dans le flux d'entrée.

Si le flux d'entrée pouvait être reçu plusieurs fois, ce serait beaucoup plus facile (aucune information à ce sujet, problème d'idée et de performance temporelle). Ensuite, nous pourrions compter les valeurs décimales. Avec des valeurs comptées, il serait facile de créer le flux de sortie. Compressez en comptant les valeurs. Cela dépend de ce qui serait dans le flux d'entrée.

Le tri est ici un problème secondaire. Comme d'autres l'ont dit, le simple stockage des entiers est difficile et ne peut pas fonctionner sur toutes les entrées , car 27 bits par nombre seraient nécessaires.

Ma vision est la suivante: ne stocker que les différences entre les entiers consécutifs (triés), car ils seront très probablement petits. Ensuite, utilisez un schéma de compression, par exemple avec 2 bits supplémentaires par numéro d'entrée, pour coder sur combien de bits le numéro est stocké. Quelque chose comme:

00 -> 5 bits
01 -> 11 bits
10 -> 19 bits
11 -> 27 bits

Il devrait être possible de stocker un bon nombre de listes d'entrée possibles dans la contrainte de mémoire donnée. Les mathématiques sur la façon de choisir le schéma de compression pour le faire fonctionner sur le nombre maximal d'entrées, me dépassent.

J'espère que vous pourrez exploiter les connaissances spécifiques au domaine de votre entrée pour trouver un schéma de compression d'entier suffisamment bon basé sur cela.

Oh et puis, vous effectuez un tri par insertion sur cette liste triée lorsque vous recevez des données.

Visant maintenant une solution réelle, couvrant tous les cas possibles d'entrée dans la plage de 8 chiffres avec seulement 1 Mo de RAM. NOTE: travaux en cours, demain continuera. En utilisant le codage arithmétique des deltas des entiers triés, le pire des cas pour les entiers triés 1M coûterait environ 7 bits par entrée (puisque 99999999/1000000 est 99 et log2 (99) est presque 7 bits).

Mais vous avez besoin des entiers de 1 m triés pour atteindre 7 ou 8 bits! Des séries plus courtes auraient des deltas plus grands, donc plus de bits par élément.

Je travaille à en prendre autant que possible et à compresser (presque) sur place. Le premier lot de près de 250 000 pouces nécessiterait au mieux environ 9 bits chacun. Le résultat prendrait donc environ 275 Ko. Répétez l'opération avec la mémoire libre restante plusieurs fois. Ensuite, décompressez-fusionnez-en-place-compressez ces morceaux compressés. C'est assez difficile , mais possible. Je pense.

Les listes fusionnées se rapprocheraient de plus en plus de la cible de 7 bits par entier. Mais je ne sais pas combien d'itérations cela prendrait de la boucle de fusion. Peut-être 3.

Mais l'imprécision de l'implémentation du codage arithmétique pourrait la rendre impossible. Si ce problème est possible, il serait extrêmement serré.

Des volontaires?

Il vous suffit de stocker les différences entre les nombres dans l'ordre et d'utiliser un encodage pour compresser ces numéros de séquence. Nous avons 2 ^ 23 bits. Nous allons le diviser en morceaux de 6 bits, et laisser le dernier bit indiquer si le nombre s'étend sur 6 autres bits (5 bits plus le bloc d'extension).

Ainsi, 000010 est 1 et 000100 est 2. 000001100000 est 128. Maintenant, nous considérons le pire cast pour représenter les différences dans la séquence d'un nombre jusqu'à 10 000 000. Il peut y avoir 10 000 000/2 ^ 5 différences supérieures à 2 ^ 5, 10 000 000/2 ^ 10 différences supérieures à 2 ^ 10, et 10 000 000/2 ^ 15 différences supérieures à 2 ^ 15, etc.

Donc, nous ajoutons combien de bits il faudra pour représenter notre séquence. Nous avons 1 000 000 * 6 + arrondi (10 000 000/2 ^ 5) * 6 + arrondi (10 000 000/2 ^ 10) * 6 + arrondi (10 000 000/2 ^ 15) * 6 + arrondi (10 000 000/2 ^ 20) * 4 = 7935479.

2 ^ 24 = 8388608. Depuis 8388608> 7935479, nous devrions facilement avoir suffisamment de mémoire. Nous aurons probablement besoin d'un autre peu de mémoire pour stocker la somme de l'endroit où nous insérons de nouveaux nombres. Nous parcourons ensuite la séquence et trouvons où insérer notre nouveau numéro, diminuons la différence suivante si nécessaire et déplaçons tout après.

Si nous ne savons rien de ces chiffres, nous sommes limités par les contraintes suivantes:

• nous devons charger tous les numéros avant de pouvoir les trier,
• l'ensemble des nombres n'est pas compressible.

Si ces hypothèses se vérifient, il n'y a aucun moyen d'accomplir votre tâche, car vous aurez besoin d'au moins 26 575 425 bits de stockage (3 321 929 octets).

Que pouvez-vous nous dire sur vos données?

L'astuce consiste à représenter l'état des algorithmes, qui est un ensemble multiple entier, sous la forme d'un flux compressé de "compteur d'incréments" = "+" et "compteur de sorties" = "!" personnages. Par exemple, l'ensemble {0,3,3,4} serait représenté par "! +++ !! +!", Suivi d'un nombre quelconque de caractères "+". Pour modifier le multi-set, vous diffusez les personnages, en ne gardant qu'une quantité constante décompressée à la fois, et en apportant des modifications avant de les retransmettre sous forme compressée.

Détails

Nous savons qu'il y a exactement 10 ^ 6 nombres dans l'ensemble final, donc il y a au plus 10 ^ 6 "!" personnages. Nous savons également que notre gamme a une taille de 10 ^ 8, ce qui signifie qu'il y a au plus 10 ^ 8 "+" caractères. Le nombre de façons dont nous pouvons arranger 10 ^ 6 "!" S parmi 10 ^ 8 "+" s est (10^8 + 10^6) choose 10^6, et donc spécifier un arrangement particulier prend ~ 0,965 Mio `de données. Ce sera un ajustement serré.

Nous pouvons traiter chaque personnage comme indépendant sans dépasser notre quota. Il y a exactement 100 fois plus de caractères "+" que "!" caractères, ce qui simplifie à 100: 1 les chances de chaque caractère étant un "+" si nous oublions qu'ils sont dépendants. Les chances de 100: 101 correspondent à ~ 0,08 bits par caractère , pour un total presque identique de ~ 0,965 MiB (ignorer la dépendance a un coût de seulement ~ 12 bits dans ce cas!).

La technique la plus simple pour stocker des caractères indépendants avec une probabilité antérieure connue est le codage de Huffman . Notez que nous avons besoin d'un arbre de taille peu pratique (un arbre de Huffman pour des blocs de 10 caractères a un coût moyen par bloc d'environ 2,4 bits, pour un total de ~ 2,9 Mib. Un arbre de Huffman pour des blocs de 20 caractères a un coût moyen par bloc d'environ 3 bits, soit un total de ~ 1,8 Mio. Nous aurons probablement besoin d'un bloc de taille de l'ordre d'une centaine, ce qui implique plus de nœuds dans notre arborescence que tout l'équipement informatique qui a jamais existé peut en stocker. ). Cependant, la ROM est techniquement "gratuite" en fonction du problème et les solutions pratiques qui tirent parti de la régularité de l'arborescence seront essentiellement identiques.

Pseudo-code

• Avoir un arbre de huffman suffisamment grand (ou des données de compression bloc par bloc similaires) stockés dans la ROM
• Commencez avec une chaîne compressée de 10 ^ 8 "+" caractères.
• Pour insérer le nombre N, diffusez la chaîne compressée jusqu'à ce que N "+" caractères soient passés, puis insérez un "!". Diffusez la chaîne recompressée sur la précédente au fur et à mesure, en conservant une quantité constante de blocs tamponnés pour éviter les sur / sous-exécutions.
• Répétez un million de fois: [entrée, décompression de flux> insertion> compression], puis décompression pour sortir

Nous avons 1 Mo - 3 Ko de RAM = 2 ^ 23 - 3 * 2 ^ 13 bits = 8388608 - 24576 = 8364032 bits disponibles.

On nous donne 10 ^ 6 nombres dans une plage de 10 ^ 8. Cela donne un écart moyen de ~ 100 <2 ^ 7 = 128

Considérons d'abord le problème plus simple des nombres assez régulièrement espacés lorsque tous les écarts sont <128. C'est facile. Enregistrez simplement le premier nombre et les intervalles de 7 bits:

(27 bits) + 10 ^ 6 numéros d'intervalle de 7 bits = 7000027 bits requis

Notez que les nombres répétés ont des lacunes de 0.

Mais que faire si nous avons des écarts supérieurs à 127?

OK, disons qu'une taille d'espace <127 est représentée directement, mais une taille d'espace de 127 est suivie d'un codage continu de 8 bits pour la longueur réelle de l'espace:

 10xxxxxx xxxxxxxx                       = 127 .. 16,383
 110xxxxx xxxxxxxx xxxxxxxx              = 16384 .. 2,097,151

etc.

Notez que cette représentation numérique décrit sa propre longueur afin que nous sachions quand le prochain numéro d'espace commence.

Avec seulement de petits espaces <127, cela nécessite toujours 7000027 bits.

Il peut y avoir jusqu'à (10 ^ 8) / (2 ^ 7) = 781250 numéro d'intervalle de 23 bits, nécessitant 16 * 781,250 = 12,500,000 bits supplémentaires, ce qui est trop. Nous avons besoin d'une représentation plus compacte et qui augmente lentement des lacunes.

La taille moyenne de l'écart est de 100, donc si nous les réorganisons comme [100, 99, 101, 98, 102, ..., 2, 198, 1, 199, 0, 200, 201, 202, ...] et l'indexons avec une base binaire dense de Fibonacci encodant sans paire de zéros (par exemple, 11011 = 8 + 5 + 2 + 1 = 16) avec des nombres délimités par '00' alors je pense que nous pouvons garder la représentation de l'écart assez courte, mais elle a besoin plus d'analyse.

Pendant la réception du flux, procédez comme suit.

1er ensemble une taille de morceau raisonnable

Idée de pseudo code:

1. La première étape serait de trouver tous les doublons et de les coller dans un dictionnaire avec son nombre et de les supprimer.
2. La troisième étape serait de placer des nombres qui existent en séquence de leurs étapes algorithmiques et de les placer dans des compteurs dictionnaires spéciaux avec le premier nombre et leur pas comme n, n + 1 ..., n + 2, 2n, 2n + 1, 2n + 2 ...
3. Commencez à compresser en morceaux certaines plages raisonnables de nombres comme tous les 1000 ou jamais 10000 les nombres restants qui semblent moins souvent répétés.
4. Décompressez cette plage si un nombre est trouvé et ajoutez-le à la plage et laissez-le non compressé pendant un certain temps.
5. Sinon, ajoutez simplement ce numéro à un octet [chunkSize]

Continuez les 4 premières étapes lors de la réception du flux. La dernière étape serait d'échouer si vous avez dépassé la mémoire ou de commencer à produire le résultat une fois que toutes les données sont collectées en commençant à trier les plages et à cracher les résultats dans l'ordre et à décompresser celles qui doivent être décompressées et à les trier lorsque vous les atteignez.