Bonne idée/mauvaise idée: Utiliser le QSet de Qt sur un très grand ensemble de données?

Question

Est-ce une mauvaise idée d'utiliser QSet pour suivre un très grand nombre de chaînes assez grandes? Chaque chaîne contient 54 caractères (108 octets). L'ensemble peut contenir des milliers d'entrées (je ne suis pas encore sûr du nombre exact). Le QSet ne sera utilisé que pour les requêtes d'insertion et d'adhésion.

Si c'est une mauvaise idée, je suis définitivement ouvert aux suggestions. Mes 54 chaînes de caractères sont composées de seulement 6 caractères différents (par exemple "AAAAAAAAABBBBBBBBBCCCCCCCCCDDDDDDDDDEEEEEEEEEFFFFFFFFF"). Cela semble être un bon candidat à la compression, peut-être? N'importe quelles autres suggestions sont les bienvenues.

Answer 1

Réalisez qu'en utilisant un ensemble intégré, vous allez avoir une compression au niveau du chemin basée sur la nature de vos données. Bien sûr, cela dépend de l'implémentation du conteneur. Regardez quelques informations sur les radix, les arbres de recherche numérique, les arbres rouge-noir, etc. Vous verrez que vous n'avez pas besoin de stocker chaque chaîne, mais plutôt les motifs. Par exemple, simplifions votre problème: nous avons seulement 3 caractères qui peuvent apparaître au maximum 2 fois chacun, et chaque chaîne a 6 caractères. Trois chaînes possibles sont les suivantes:

AABBCC, aabcbc et AACBCB

Avec ces exemples, nous pourrions sortir avec l'aide d'un maximum de 6 + 3 + 4 = 13 noeuds au lieu d'un 18 noeuds. pas important, mais je ne sais pas ce que vous faites non plus. Comme avec tout type de compression, plus vos modèles de préfixes sont réutilisés, plus vous avez de compression.

Édition: Les numéros 13 et 18 proviennent de la compression au niveau du chemin. Par exemple, dans C (pour argument/discussion), si j'implémente ma classe de stockage de chaînes comme un wrapper autour d'un tableau, j'aurais probablement un tableau de pointeurs de caractères avec chaque pointeur référençant un point en mémoire contenant un motif. Dans l'exemple que j'ai donné ci-dessus, cela prendrait 18 caractères (6 * 3 = 18). Si l'on ajoute la taille du tableau (disons que sizeof (char *) vaut 4, notre tableau prendrait 3 * 4 octets de stockage = 12 + 18 ou 30 octets au total pour stocker nos patterns.)

Si je suis plutôt en stockant les motifs dans une sorte d'arbre de recherche numérique, je fais un petit compromis: les nœuds de mon arbre vont être plus gros que 1 octet chacun (1 octet pour le caractère dans le nœud, 4 octets pour le pointeur "suivant" chaque noeud, 5 octets chacun) Le premier motif que nous stockons est AABBCC, c'est-à-dire 6 noeuds dans l'arbre, ensuite AABCBC, nous réutilisons le chemin AAB du premier arbre et n'avons besoin que de 3 noeuds supplémentaires pour CBC. est AACBCB Nous réutilisons AA, et avons besoin de 4 nouveaux nœuds pour CBCB.C'est un total de 13 nœuds * 5 octets = 65 octets de stockage. Cependant, si vous avez beaucoup de motifs longs et répétitifs dans le préfixe de vos données, alors vous verrez une compression de niveau de chemin de préfixe.

Si ce n'est pas le cas pour vous, je me pencherais sur la compression Huffman ou LZW. Cela vous obligera à construire un dictionnaire de modèles qui ont des nombres entiers liés à eux. Lorsque vous compressez, vous créez le dictionnaire et créez des ID entiers pour chaque motif de votre texte. Vous remplacez ensuite les motifs dans votre texte avec les ID entiers. Lorsque vous décompressez, vous faites le contraire. Je n'ai pas le temps de décrire ces algorithmes plus en détail, vous devrez donc les consulter.

C'est un compromis entre simplicité et temps. Si vos données le permettent, prenez la méthode la plus courte et utilisez simplement le conteneur intégré. Sinon, vous aurez besoin de quelque chose de plus adapté à vos données.

Answer 2

Je ne pense pas que vous auriez des problèmes supplémentaires en utilisant QSet sur un autre type de conteneur, tel que std :: set, une carte ou un vecteur. Si vous vous interrogez sur le manque de mémoire, cela dépend probablement du nombre de milliers de chaînes que vous avez besoin de stocker, et s'il y avait un moyen de les encoder de manière plus concise. (Par exemple, si les caractères apparaissent toujours dans le même ordre mais varient en longueur relative, stockez la longueur de chaque caractère plutôt que tous les caractères.) Cependant, même 50 000 de ces chaînes ne font que 5 Mo et 500 000 d'entre elles est de seulement 50 Mo à stocker, ce qui réduit les frais généraux de stockage, ce qui représente une quantité modérée de mémoire sur les machines modernes.

Answer 3

De votre commentaire précédent: "Dans mes cordes, il y aura toujours 54 caractères, et il y aura toujours 9 caractères de chaque caractère, l'ordre est la seule chose qui change."

Ne pas stocker les chaînes brutes alors. Vous pouvez simplement les compresser en 6 caractères réellement utilisés, puis en faire un QSet. Une compression triviale serait {a, b, c, d, e, f}, et si le jeu de caractères est connu à l'avance (et seulement les 6 caractères), vous pouvez même emballer les choses dans un entier de 16 bits.

Answer 4

QSet semble être une bonne idée. Il s'agit essentiellement d'une table de hachage et il peut optimiser sa taille de manière dynamique. Parfait. Une autre suggestion pour compresser la clé: Traitez-la comme une chaîne de nombres base-6 (pensez A = 0, B = 1, ... F = 5) et convertissez-la en binaire (int).

QByteArray ba("112"); // instead of "BBC" 
    int num = ba.toInt(0, 6 /*base*/); // num == 44 

6^3 < 2^8, afin que nous puissions représenter tous les 3 caractères dans votre chaîne avec un 1 octet int (ou char) et faire un bytearray de celui-ci. Cela réduirait la taille de la clé de 54 octets à 18 octets.