Récemment, dans l'un des projets, un problème est survenu: il existe un ensemble d'ensembles (Set) qui doivent être efficacement stockés dans la RAM. Parce qu'il y a beaucoup de sets, mais peu de mémoire. Et nous devons faire quelque chose à ce sujet.
Puisque le langage dans lequel tout cela est écrit est C #, c'est-à-dire les nuances. À savoir, le HashSet <int> standard dépense 16 octets pour stocker un nombre, le facteur de remplissage affecte également. Il y a des implémentations plus efficaces (j'écrirai à leur sujet un jour), mais d'un autre côté, vous pouvez bêtement stocker dans des tableaux, 4 octets par nombre (vous devez stocker des ints), ce qui est assez efficace. Mais peut-il être réduit davantage?
Je dois dire tout de suite que je n'ai pas de réponse sur la meilleure façon de le faire, peut-être que cela n'existe pas, car il y a de nombreux facteurs associés à la distribution de données spécifiques. Mais il y a des idées que je vais partager: quelles sont les options disponibles pour économiser de la mémoire. Je vous recommande également de réfléchir par vous-même avant de lire l'article, après tout, c'est un bon entraînement pour l'esprit. Pour être précis, je formulerai le problème comme suit:
Il existe un ensemble d'entiers uniques non négatifs (32 bits). Il est nécessaire de les stocker efficacement dans la RAM, à partir des opérations - création d'un ensemble et obtention de tous les éléments. Inutile de récupérer les éléments par index, d'en ajouter de nouveaux ou de les supprimer.
L'article contiendra de nombreuses lettres et chiffres et pas une seule image (sauf pour un chat emballé sur le KDPV).
, , .. , . . - , - , . - , - .
, — , .
, : , . 10
Donc, nous avons des données de base - un tableau d'entiers, 4 octets (32 bits) par nombre. Nous nous appuierons sur cet indicateur.
Pour commencer, je vais exprimer une idée géniale: pour qu'un nombre occupe moins de 32 bits en mémoire, vous devez le stocker en utilisant moins de bits. Bonne idée, hein? Et les gens obtiennent la renommée et la reconnaissance pour cela. Alors le pire je suis.
Digression lyrique: il y a quelques années, des spécialistes des chemins de fer russes ont découvert que si vous faites des roues rondes et de même taille, le train va plus vite et plus silencieux.
Séparer les nombres par taille
Une solution simple pour commencer: les nombres de 0 à 255 peuvent être stockés en utilisant 1 octet par nombre, jusqu'à 65536 avec deux, jusqu'à 16777216 avec trois. D'où la première solution:
on crée 4 tableaux, dans l'un on stocke les nombres par 1 octet, dans l'autre par 2, dans le troisième par 3, et ce que dans le quatrième, je propose de deviner par nous-mêmes.
Applaudissez, et nous économisons déjà. Mais pourquoi rester là où tu étais? Utilisons 32 tableaux! Et stocker les nombres par 1, 2 ... bits. C'est devenu encore plus économique.
D'un autre côté, qu'est-ce qu'un tableau? Il s'agit d'un pointeur vers un bloc de mémoire (8 octets), de longueur et pour C # également de mémoire pour l'objet tableau lui-même (20 octets). Au total, chaque tableau nous coûte 32 octets (en fait, en C #, un objet prend au moins 24 octets par incréments de 8, dont 20 octets sont pour l'objet, et 4 pour ce qui reste ou est stupide pour l'alignement). Ci-après, des calculs pour un système 64 bits. Pour 32 bits, les pointeurs sont 2 fois plus petits, l'alignement est également de 4, donc presque tout est 2 fois plus économique.
A quoi sert ce passage? De plus, 32 baies dévoreront 1 Ko de mémoire rien que pour elles-mêmes. Que faire? Tout est simple: nous allons stocker ces 32 tableaux dans un seul tableau!
Dans le premier élément, nous stockons la longueur d'un tableau d'un bit, puis le tableau lui-même, puis la longueur de deux bits, etc. En conséquence, il n'y a que 32 octets de surcharge et de stockage efficace.
Un lecteur curieux (j'ai toujours aimé cette phrase) peut remarquer un certain problème: pour stocker les nombres d'un bit, on passe d'abord 2 bits pour la longueur (0, 1 ou 2), puis 2 bits pour les nombres eux-mêmes. Mais vous ne pouvez dépenser que 2 bits: le premier bit est de savoir s'il y a un 0, le second est de savoir s'il y a un 1.
Nous venons de créer un bitmap . Vous ne pouvez pas vous inquiéter beaucoup et stocker des nombres de 0 à 255 en utilisant cette méthode - il y a un nombre - 1, non - 0. Et passez 32 octets dessus (8 bits dans un octet * 32 = 256). Naturellement, à chaque nouvelle valeur, l'efficacité de la carte commence à décliner. Ceux. pour stocker tous les entiers, nous avons besoin de 536870912 octets ... C'est un peu trop. Alors, quand s'arrêter: à 256, à 16, à 65536 - dépend des données. Que ce soit 256. J'aime ce nombre, c'est magnifique.
Ceux. nous stockons les 256 premiers nombres avec un bitmap, puis nous stockons la longueur des nombres d'une certaine longueur en bits et les nombres eux-mêmes.
Mais regardez ce qui se passe: les nombres de 0 à 511 nécessitent 9 bits pour être stockés. En même temps, nous sommes des nombres de 0 à 255 - nous avons déjà enregistré. Ceux. dans la plage de 9 bits, le nombre 12 est introuvable. Seulement 256 et plus. Alors pourquoi les stocker en 9 bits, si vous pouvez stocker un nombre de 0 à 255 et ensuite ajouter le 256 manquant dans votre tête. Naturellement, chaque gamme suivante sera également un peu plus économique. Nous sommes super!
Que pouvez vous faire d'autre? Et vous pouvez consulter les données. S'ils sont très denses (1, 2, 3, 5, 6), vous pouvez stocker non pas les nombres eux-mêmes, mais ceux qui n'existent pas (4). Ceux. au lieu de stocker 5 nombres conditionnels, nous en stockerons un. Une règle simple: nous en avons plus de la moitié - nous gardons celles qui n'existent pas, sinon vice versa. Où stocker? Et en longueur! Regardez: pour stocker des nombres de 10 bits, nous avons besoin de 11 bits (car de 0 à 1024 inclus). Mais en même temps, les valeurs en 11 bits peuvent être poussées en 2048, et nous n'utilisons que 1025. Nous allons donc stocker: longueur positive - nous stockons les nombres. Négatif - nous gardons ce qui ne l'est pas. Je propose de faire un calcul détaillé pour le lecteur lui-même en tant qu'exercice indépendant (car je ne suis pas sûr que tout va s'emboîter, alors je vais faire semblant que c'est nécessaire).
En conséquence, nous avons: un tableau dans lequel les 16 premiers octets sont un masque de bits pour la présence de nombres de 0 à 255, puis - la longueur avec une indication - nous stockons les nombres ou leur absence, les nombres eux-mêmes, la longueur en bits pour le suivant, etc.
Après avoir implémenté cela, et même sans erreurs, je pense que vous irez directement au durke, les programmeurs suivants essayant de comprendre ce code vous suivront. Alors essayons quelques autres options.
Nous pensons à l'ordre
Regardez. Nous avons un tableau. Qu'est-ce qu'il a, par opposition à beaucoup? Et il a: l'ordre des éléments. Ce sont des informations supplémentaires, et nous ne les avons pas encore utilisées. Que peux-tu y faire?
Et vous ne pouvez pas stocker les éléments eux-mêmes, mais la différence entre eux:
1,2,3,4,8 => 1,1,1,1,4
Ie. nous stockons le premier tel quel, le second - nous ajoutons la valeur du premier au second, etc. Qu'est-ce que ça nous donne? Et le fait que si nous trions le tableau à l'avance , les valeurs qu'il contient deviendront plus petites en général et pourront être stockées dans moins de bits.
De plus, selon l'état du problème, tous les éléments sont différents, c'est-à-dire nous pouvons encore soustraire un de la différence pour enregistrer les bits:
1,2,3,4,8 => 1,1,1,1,4 => 1,0,0,0,3
Ce n'est pas difficile, alors pourquoi et non.
Mais maintenant, le problème est sorti. Parce que Maintenant, nous ne pouvons pas stocker les nombres indépendamment, mais seulement dans le même ordre, alors la méthode avec un tableau et des longueurs ne convient plus. Il faut trouver autre chose, car tous les numéros doivent être stockés dans l'ordre.
Stockez la longueur du nombre en bits avant le nombre lui-même.
Ce n'est pas une mauvaise option. Le nombre prend de 1 à 32 bits, c'est-à-dire pour la longueur, nous avons besoin de 5 bits, puis du nombre lui-même. Pour plus de commodité, vous pouvez couper les cas extrêmes (enfin, pourquoi allons-nous y économiser? Pennies!), Ou vice versa, mettez-les en surbrillance séparément - par exemple, si la longueur est 0, cela signifie le nombre 0, si la longueur est 1 - le nombre - 1, si la longueur est 2, puis les 2 suivants nombre de bits 2,3,4,5 (nous savons déjà que nous pouvons passer à quelque chose qui ne peut pas être), etc.
Ou peut stocker la longueur d'un nombre dans le nombre lui-même?
Quantité de longueur variable
Peu importe comment nous sommes les premiers à poser cette question, il existe donc une solution standard. Utilisé pour stocker des chaînes en UTF-8 et dans de nombreux autres endroits. Le sens est simple.
Si le nombre est compris entre 0 et 127 inclus, nous le stockons dans 1 octet (bien que nous n'ayons utilisé que 7 bits). Si plus, définissez le 8e bit sur 1 et utilisez l'octet suivant de la même manière (7 bits, manquant - case à cocher et suivant). Ceux. les petits nombres seront stockés dans un octet, un peu plus - en deux, et ainsi de suite jusqu'à 5.
Vous pouvez dire - fuu ... nous venons de jouer avec les bits, puis les octets sont partis, pas cool! Oui, ce n'est pas cool, par contre, travailler avec des octets est quand même plus facile qu'avec des bits, un peu moins d'économies, mais la vitesse de travail est plus élevée et le code est plus clair. Mais ... dépenser un peu par octet n'est en quelque sorte pas très cool, peut-être existe-t-il de meilleures solutions?
Utiliser des valeurs comme indicateurs
Sautons tout raisonnement et décidons immédiatement. Nous le stockerons comme suit:
- les nombres de 0 à 252 seront stockés dans un octet. Si plus, alors:
- si le nombre est de 252 à 252 + 256 = 508, nous définissons la valeur 252, et dans l'octet suivant, le nombre est 252 (oui, nous savons déjà comment décaler les valeurs)
- si de 252 + 256 à 252 + 256 + 65536, définissez 253 et utilisez les 2 octets suivants pour stocker le numéro lui-même - une différence inutile
- si de 252 + 256 + 65536 à 252 + 256 + 65536 + 16777216, mettez 254 et 3 octets
- sinon - 255 et 4 octets.
Est-ce un bon moyen? Tout est relatif. Dans un octet, nous pouvons pousser des valeurs jusqu'à 252, tandis qu'en VLQ seulement jusqu'à 127, mais seulement 508 en 2 octets, et déjà 16383 en VLQ. la méthode est bonne si vos nombres sont suffisamment denses, et ici nous gagnerons. Mais la bonne chose à propos de la méthode est qu'elle peut être ajustée à différentes plages. Par exemple, si nous savons que la plupart des nombres vont de 10 000 à 50 000, alors nous pouvons toujours les stocker sur deux octets, mais si un grand nombre sort, nous écrirons 65535 et utiliserons déjà 4. En fait, nous optimisons le stockage de la plage requise au prix d'un stockage inefficace inutile.
Conclusion
Nous avons examiné les principaux moyens d'économiser de la mémoire (en fait, mon imagination est épuisée, mais je ne l'admets pas). Ces techniques peuvent être combinées, utilisées pour d'autres tâches et modifiées en fonction de la situation. Quelle est la meilleure technique au final? Tout dépend de vos données. Prenez-les et essayez-les. Heureusement, il n'est pas nécessaire de tout mettre en œuvre complètement en même temps. Il est assez facile d'écrire du code qui évaluera simplement la longueur. Et après l'évaluation, mettez déjà en œuvre ce que vous avez aimé.
N'oubliez pas la rapidité de tout cela: êtes-vous prêt à passer beaucoup de temps à préparer des données ou à les obtenir. Vaut-il la peine de commencer un combat avec des bits, ou ne devriez-vous pas aller en dessous d'octets. Suffit-il d'optimiser les situations fréquentes, laissant les rares avec une mise en œuvre inefficace. Est-il possible, en fonction des données, d'utiliser différentes méthodes de stockage (par exemple, il est stupide de stocker jusqu'à 8 octets dans un tableau, car les coûts secondaires dévoreront tout le gain, et à partir de 1 octet - généralement stockés dans un pseudo-tableau d'un élément, c'est-à-dire dans le nombre).
Aussi, quelques mots sur la compression: ici ce ne sera pas très efficace. Les algorithmes de compression aiment beaucoup les répétitions, mais il n'y en a pas beaucoup ici. Si vous prenez un Zip conditionnel, qui se compose de LZ77 + Huffman, il est peu probable que quelque chose d'utile sortira avec LZ77, mais Huffman peut essayer de sauver des octets. Donc Zip sera à moitié inutile. Mais la vitesse diminuera énormément.
Les situations où nous savons que nous avons de nombreux ensembles et que nous pouvons les stocker tous ensemble en utilisant différentes tranches n'ont pas encore été prises en compte. Ici, je l'avoue - je ne suis pas sûr que cela fonctionnera. Immédiatement, je n'ai pas proposé d'options. Mais j'ai réalisé que ce serait difficile. Cependant, vous pouvez avoir des opinions différentes.
Alors partagez vos idées dans les commentaires, peut-être que j'ai raté un éléphant évident qui permettra d'économiser encore plus d'octets et d'obtenir un tel résultat que les ménagères de la publicité de détergent (ce qui suffit pour une goutte) nous envieront tous!