Conteneur rapide pour la définition de bits dans un domaine fragmenté et l'itération (C ++)?

Question

J'ai besoin d'un conteneur rapide avec seulement deux opérations. Insertion de clés dans un domaine très fragmenté (tous les entiers 32 bits et environ 100 sont définis à un moment donné) et itération sur les clés insérées. Il devrait traiter de nombreuses insertions qui touchent les mêmes entrées (500k, mais seulement 100 différentes).

Actuellement, j'utilise un std :: set (seulement insert et l'interface itérative), ce qui est correct, mais pas encore assez rapide. std :: unordered_set était deux fois plus lent, de même pour Google Hash Maps. Je me demande quelle structure de données est optimisée pour ce cas?

Answer 1

En fonction de la distribution de l'entrée, vous pourrez peut-être améliorer certaines choses sans changer la structure.

Si vous avez tendance à effectuer plusieurs analyses d'une seule valeur, vous pouvez probablement accélérer les insertions en conservant un enregistrement de la dernière valeur que vous avez insérée, sans vous soucier d'effectuer l'insertion si elle correspond. Cela coûte une comparaison supplémentaire par entrée, mais enregistre une recherche pour chaque élément d'une exécution au-delà du premier. Cela peut donc améliorer les choses, quelle que soit la structure de données utilisée, en fonction de la fréquence des répétitions et du coût relatif de la comparaison par rapport à l'insertion.

Si vous n'obtenez pas d'exécutions, mais que vous avez tendance à constater que les valeurs ne sont pas réparties de manière égale, un arbre d'optimisation rend l'accès aux éléments les plus couramment utilisés moins coûteux. Cela fonctionne en créant un arbre délibérément déséquilibré avec les éléments fréquents près du sommet, comme un code de Huffman.

Answer 2

Je ne suis pas sûr de comprendre "de nombreuses insertions qui correspondent aux mêmes entrées". Voulez-vous dire qu'il n'y a que 100 valeurs qui soient jamais membres, mais que 500 000 opérations, pour la plupart dupliquées, insèrent l'une de ces 100 valeurs?

Si tel est le cas, alors le conteneur le plus rapide consisterait à générer un hachage sans collision pour ces 100 valeurs, puis à conserver un tableau (ou un vecteur) de drapeaux (int ou bit), en fonction de ce qui fonctionne le plus rapidement. sur votre architecture).

Je pars en générant le hachage comme exercice pour le lecteur, car j’ai conscience que c’est une technique qui existe, mais je ne me suis jamais penché là-dessus. Le but est d’obtenir un hachage rapide sur une plage aussi petite que possible, telle que pour chaque n, m dans vos 100 valeurs, hash (n)! = Hash (m).

Donc, l'insertion ressemble à array [hash (valeur)] = 1; , la suppression ressemble à array [hash (valeur)] = 0; (bien que vous n'ayez pas pas besoin de ça), et pour vous énumérer, parcourez le tableau, et pour chaque valeur définie à l’indice n, inverse_hash (n) est dans votre collection. Pour une petite plage, vous pouvez facilement gérer une table de recherche pour effectuer le hachage inverse ou, au lieu d'analyser l'ensemble du tableau à la recherche d'indicateurs d'ensemble, vous pouvez exécuter plus de 100 valeurs en vérifiant chacune à leur tour.

Désolé si j'ai mal compris la situation et que cela vous est inutile. Et pour être honnête, ce n’est pas beaucoup plus rapide qu’une table de hachage ordinaire, puisque, pour 100 valeurs, vous pouvez facilement dimensionner la table de telle sorte qu’il y ait peu ou pas de collisions, sans utiliser suffisamment de mémoire pour vider vos caches.

Answer 3

Pour un ensemble en cours d'utilisation censé être aussi petit, une table de hachage non compartimentée peut être OK. Si vous pouvez vivre avec une opération d’expansion occasionnelle, augmentez la puissance de 2 si elle est remplie à plus de 70%. Le hachage du coucou a été discuté sur Stackoverflow avant et pourrait également être une bonne approche pour un ensemble aussi petit. Si vous avez vraiment besoin d'optimiser la vitesse, vous pouvez implémenter la fonction de hachage et la recherche dans l'assembleur. Sur les structures de données linéaires, cela sera très simple. Ainsi, l'effort de codage et de maintenance d'une implémentation d'assembleur ne devrait pas être trop difficile à maintenir.

Answer 4

Vous pouvez envisager de mettre en œuvre une HashTree en utilisant une fonction de hachage en base 10 à chaque niveau au lieu d'une fonction de hachage binaire. Vous pouvez le rendre non compartimenté, auquel cas vos performances seraient déterministes (log10) ou ajuster la taille de votre compartiment en fonction de la distribution attendue afin de ne disposer que de quelques clés / compartiments.

Answer 5

Une structure de données aléatoires pourrait être parfaite pour votre travail. Consultez la ignorer la liste & # 8211; bien que je ne connaisse aucune implémentation décendue de C ++. J'avais l'intention d'en soumettre un à Boost mais je n'ai jamais eu le temps de le faire.

Answer 6

Peut-être un ensemble avec un b-tree (au lieu d'arborescence binaire) comme structure de données interne. J'ai trouvé un article sur le codeproject qui l'implémente.

Answer 7

Notez que bien que l'insertion dans une table de hachage soit rapide, son itération n'est pas particulièrement rapide, car vous devez effectuer une itération sur l'ensemble du tableau.

Quelle opération est lente pour vous? Faites-vous plus d'insertions ou plus d'itérations?

Answer 8

Combien de mémoire avez-vous? 32 bits ne prennent que "&"; 4 Go / 8 octets, ce qui correspond à 512 Mo, pas beaucoup pour un serveur haut de gamme. Cela ferait vos insertions O (1). Mais cela pourrait ralentir l'itération. Bien que sauter tous les mots avec seulement des zéros optimise la plupart des itérations. Si vos 100 numéros se situent dans une plage relativement petite, vous pouvez optimiser encore plus en gardant le minimum et le maximum autour.

Je sais que c'est juste de la force brute, mais parfois la force brute est assez bonne.

Answer 9

Puisque personne ne l’a explicitement mentionné, avez-vous pensé à la localité de la mémoire? Une structure de données vraiment géniale avec un algorithme d'insertion qui provoque une erreur de page ne vous fera aucun bien. En fait, une structure de données avec un insert qui provoque simplement un manque de cache serait probablement très mauvaise pour les performances.

Vous êtes-vous assuré qu'un ensemble d'éléments naïfs et non ordonnés est emballé dans un tableau fixe avec un simple échange vers l'avant lorsqu'une insertion entre en collision est trop lente? C’est une expérience simple qui peut montrer que vous avez des problèmes de localité de mémoire plutôt que des problèmes d’algorithme.