Je voudrais faire la classe « tableau comprimé » / « vecteur » comprimé (détails ci-dessous), qui permet l'accès aux données aléatoires avec le temps plus ou moins constant.
« plus ou moins de temps constant » signifie que bien que le temps d'accès de l'élément est pas constant, il ne devrait pas continuer à augmenter quand je me rapproche de certain point du tableau. C'est à dire. conteneur ne doit pas faire des calculs beaucoup plus (comme « tout decompress une nouvelle fois pour obtenir le dernier élément », et « presque rien pour obtenir le premier ») pour obtenir un élément. Peut être probablement réalisé par tableau de division en blocs de données compressées. C'est à dire. l'accès à un élément devrait prendre « AverageTime » + - un certain écart. Je pourrais dire que je veux avoir le temps d'accès le plus optimiste et le temps d'accès pire cas d'être relativement proche de temps d'accès moyen.
Quelles sont mes options (algorithmes / déjà disponibles conteneurs appropriés - s'il y en a) ?
Détails conteneur:
Exemple d'utilisation:
recherche binaire sur les données.
Détails des données:
1. Les données sont struct principalement constitué de flotteurs et quelques ints. Il y a plus de chars que ints. Pas de chaînes.
2. Il est peu probable qu'il existe de nombreux éléments identiques tableau, donc simplement des données indexeing ne seront pas possibles.
3. Taille d'un élément est inférieur à 100 octets.
4. Taille totale des données par conteneur entre quelques kilo-octets et quelques méga-octets.
5. Les données ne sont pas rares - il est bloc continu d'éléments, tous sont affectés, il n'y a pas « emplacements vides ».
Le but de la compression est de réduire la quantité de mémoire RAM du bloc prend par rapport à la représentation non compressée en tant que matrice, tout en maintenant les performances d'accès en lecture quelque peu raisonnable, et en permettant aux éléments d'accès de façon aléatoire comme matrice. C'est à dire. les données doivent être stockées sous forme comprimée à l'intérieur, et I devrait être en mesure d'y accéder (lecture seule) comme si elle était un std :: vecteur ou un récipient similaire.
Idées / Avis?
5 Réponses :
D'accord, du meilleur de ma compréhension, ce que vous voulez, c'est une sorte de modèle d'accesseur. Fondamentalement, créez un adaptateur de modèle qui a pour effet d'argument l'un de vos types d'éléments qu'il accède à l'interne via tout ce que, un pointeur, un index dans votre blob, etc. Faites le pointeur de l'adaptateur - comme:
const T &operator->(void) const;
Codez-vous un système intégré et / ou avez-vous des centaines ou des milliers de ces conteneurs? Sinon, alors que je pense que c'est une question théorique intéressante (+1), je soupçonne que le ralentissement du fait de la décompression sera non trivial et qu'il serait préférable d'utiliser utiliser un Ensuite, êtes-vous sûr que les données que vous rangez sont suffisamment redondantes que des blocs plus petits de celui-ci seront en réalité compressibles? Avez-vous essayé d'enregistrer des blocs de tailles différentes (pouvoirs de 2 peut-être) et essayé de les exécuter à travers GZIP comme un exercice? Il se peut que toute donnée supplémentaire nécessaire pour aider l'algorithme de décompression (selon l'approche) réduirait les avantages de l'espace de faire ce type de conteneur comprimé.
Si vous décidez qu'il est toujours raisonnable de faire la compression, il y a au moins quelques possibilités, aucune pré-écrite. Vous pouvez compresser chaque élément individuel, stocker un pointeur sur le morceau de données comprimé. Ensuite, l'accès à l'index est toujours constant, il suffit de décompresser les données réelles. Éventuellement à l'aide d'un objet proxy permettrait de faire la décompression réelle des données plus facile et plus transparente (et peut-être même vous permettre d'utiliser alternativement, std :: Vecteur .
std :: vecteur comme conteneur sous-jacent).
std :: deque stocke ses données dans des morceaux déjà, vous pouvez donc utiliser une approche similaire ici. Par exemple, std :: vecteur ) pourrait même mettre en cache le dernier morceau décompressé ou deux pour des performances ajoutées sur un accès consécutif (bien que cela ne puisse pas aider beaucoup de choses binaires au total) .
Mais ... la recherche binaire frappe très peu d'éléments très fréquemment. Garder les valeurs clés de ces rares articles non compressés pourrait rendre la pénalité de décompression presque disparaître sans augmenter considérablement la taille totale.
Je suppose que vous voulez un array em> dont les éléments ne sont pas stockés à la vanille, mais compressé em>, afin de minimiser l'utilisation de la mémoire. En ce qui concerne la compression, vous avez pas exceptionnel un aperçu de la structure de vos données, vous êtes très bien avec une sorte de norme codage entropique em>. Idéalement, voudrait que d'exécuter GZIP sur votre tableau entier et être fait avec, mais ce serait perdre O (1) l'accès, ce qui est crucial pour vous. P> solution strong> consiste à utiliser Huffmann codage conjointement avec un. table d'index strong> p > Huffmann codage fonctionne en remplaçant chaque symbole d'entrée (par exemple, un octet ASCII) avec un autre symbole de variable em> longueur de bits, selon la fréquence d'occurence dans le flux entier. Par exemple, le caractère E code> apparaît très souvent, il obtient une courte séquence de bits, alors que 'W' est rarement et obtient une longue séquence de bits. P> E -> 0b10
W -> 0b11110
Pour modifier (des éléments eux-mêmes, pas la longueur du vecteur), la table d'index pourrait être un arbre de fenwick. Cela permettrait de recompagner l'index sur la volée avec des changements minimes.
Je pense à cela depuis un moment maintenant. D'un point de vue théorique, j'ai identifié 2 possibilités:
Le premier est purement orienté objet et convient parfaitement, je pense en général, il n'a pas l'inconvénient de gâcher les pointeurs par exemple.
La seconde semble mieux adaptée ici, bien qu'elle ait un léger désavantage en général: invalidation du pointeur + problèmes avec codage / décodage du pointeur, tables virtuelles, etc ... notamment cela ne fonctionne pas si les articles se rapportent à l'autre. Utiliser des pointeurs au lieu d'indices.
J'ai vu quelques solutions "coding Huffman", mais cela signifie que pour chaque structure doit fournir un algorithme de compression. Ce n'est pas facile de généraliser.
Je préférerais donc aller dans l'autre sens et utiliser une bibliothèque de compression comme 'Zlib', ramassant un algorithme rapide comme Lzo par exemple.
cache_view Pour accéder au conteneur tout en stockant les 5 derniers (ou plus) nœuds décompressés ou quelque chose. Une autre variante consiste à implémenter le comptage de référence et à conserver les données non compressées tant que certaines personnes ont eu une poignée à l'un des éléments du nœud.
Certaines remarques:
- Si vous devriez un grand nombre d'éléments / clés par nœud, vous disposez d'une heure d'accès constante, par exemple avec 1001, cela signifie que des 2 niveaux d'indirection ne sont que de moins de million d'articles, 3 niveaux de Indirection pour un milliard, etc ...
- Vous pouvez créer un conteneur lisible / écritable avec une telle structure. Je le ferais pour que je ne recompresse que une fois que j'ai fini d'écrire le nœud.
Quelques réponses à " Quel est le meilleur algorithme de compression qui permet des lectures / écritures aléatoires dans un fichier? " être adapté à vos données en mémoire?
Quel est le temps "plus ou moins" constant? Soit il est constant, soit ce n'est pas le cas. Sinon une question intéressante. Êtes-vous sûr de ne pas pouvoir faire ce que vous voulez avec les nombreuses classes de conteneurs existantes?
Où la partie "comprimée" en entre -ne-t-elle? Vous n'expliquez jamais cette partie. Pourriez-vous simplement utiliser un vecteur de pointeurs sur des blobs gzippés ou quelque chose comme ça? Ou voulez-vous dire compressé comme dans vous avoir un jeu de données rare afin qu'un vecteur naïf aurait beaucoup de fentes vides?
De plus, vous dites que les éléments ne sont que des flotteurs et des INT, et qu'un élément ne dépasse jamais 100 octets. À moins que vous ne travaillez sur une architecture de 800 bits, vous pouvez quasiment omettre la dernière exigence.
@ cerneon: "Qu'est-ce que" plus ou moins "temps constant?" Mise à jour de la question, voir Explication.
@jalf: Mise à jour de la question, voir \ # 5 dans "Détails des données".
Je suppose que par "temps plus ou moins constant", vous voulez dire ce qui est officiellement appelé "temps constant amorti" (voir EN.WIKIPEDIA.ORG/WIKI/AMORTÉTIME_Analysis ) - Est-ce correct?
@Martin b.: Je ne suis pas sûr que cela décrit ce que je veux. Je pourrais dire que je veux que le meilleur temps d'accès au cas et le pire cas d'accès soit relativement proche de l'heure d'accès moyen. Si vous comprenez simplement tout en un seul bloc, le meilleur cas / le pire des cas sera trop loin de la moyenne.
Si la taille typique d'une entrée est d'environ 100 octets, il devrait être logique de comprimer chaque élément individuellement, mais de ne pas compresser la matrice dans son ensemble. En d'autres termes, chaque élément de tableau serait une représentation comprimée de votre structure au lieu de la structure non compressée elle-même. La même table de codage devrait probablement être utilisée pour tous les éléments de réseau.
Vous avez indiqué qu'il y avait très peu d'éléments identiques; Dans quelle mesure vous attendez-vous à ces données (sans perte) comprimé?
@Martin B: "Il devrait avoir du sens à compresser chaque élément individuellement". A du sens, mais en utilisant quel algorithme? Comme je me souviens, Zlib (par exemple) commence à compresser des choses lorsque les données grandissent de plus de 100 octets. Un élément peut également être aussi petit que 28 octets.
Les chiffres dans les structures ont-ils tendance à présenter des propriétés utiles lorsqu'elles sont traitées comme une séquence? Par exemple, s'ils étaient en ordre croissant, je vous suggérerais d'utiliser le codage Delta (stocker la différence entre chaque numéro et le précédent, plutôt que de stocker le nombre lui-même), puis en utilisant le codage de variables sur les Deltas afin qu'ils ont pris moins d'espace. La recherche serait linéaire, mais vous pourriez améliorer cela en ayant tous les mth numéro (pour certains mètres raisonnablement petits) codés normalement plutôt que comme un delta. Je ne sais pas si c'est ce que vous voulez, cependant.
@meagar: sur les types de données où je voudrais essayer cela, il y aura de nombreux éléments qui ont 23,42% d'octets identiques, mais presque aucun élément absolument identique. Je ne peux pas estimer à quel point cela pourrait compresser.
@David: C'est une idée très intéressante, mais je préférerais un conteneur générique. En outre, des données peuvent être générées par programme externe et, dans ce cas, alors qu'il y aura un modèle dans la manière dont les modifications de données changent, il peut être difficile de le connaître dans un programme.
@Sigterm a fait une double prise lorsque j'ai lu la taille totale du conteneur est jusqu'à "quelques mégaoctets". Pourquoi es-tu inquiet de la compresser en premier lieu?
@SIGTERM: Codage de Huffman ou (brevets permettant) codage arithmétique est ce que je commencerais avec. Zlib ne commence probablement que de compresser à 100 octets car il a besoin d'une certaine quantité d'espace pour stocker sa table de codage et que le point de rupture est probablement sur 100 octets. Dans votre cas, vous utiliseriez la même table de codage pour tous les éléments de réseau, de sorte que la préoccupation ne s'applique pas. Edit: Voir les réponses de Cubbi et Heinrich pour plus de détails sur la façon dont cela fonctionnerait.
@meager: "Pourquoi es-tu inquiet de la compresser en premier lieu?" Deux raisons: 1. Il y aura beaucoup de blocs de ce type, les données d'entre eux contiennent un peu d'informations redondantes qui ne peuvent toujours pas être facilement jetées, indexées, etc. Il suffit de "demander" d'être compressé. 2. J'ai réfléchi à ce problème (de point purement théorique) pendant un moment, je voudrais donc savoir comment cela peut être fait.