Trouver efficacement plusieurs éléments dans un conteneur

Question

Je dois trouver un certain nombre d'objets dans un grand conteneur.

Le seul moyen auquel je pense pour y parvenir semble être de rechercher dans le conteneur un élément à la fois dans une boucle. Cependant, même avec une recherche efficace avec un cas moyen de disons "log n" (où n est la taille du conteneur), cela me donne "m log n" (où m est le nombre d'éléments que je recherche) pour toute l'opération.

Cela me semble très sous-optimal, et comme c'est quelque chose que je suis susceptible de devoir faire fréquemment, j'aimerais vraiment l'améliorer si possible.

Aucune des deux parties n'a encore été implémentée, donc je suis ouvert aux suggestions sur le format du conteneur principal, la "liste" d'éléments que je recherche, etc, ainsi que sur l'algorithme de recherche proprement dit.

Les éléments sont des objets complexes, mais la clé de recherche n'est qu'un simple nombre entier.

Answer 1

Etes-vous sûr que m journal ₂ ( n ) va réellement poser un problème ? Si vous utilisez un std::map Si vous recherchez 10 000 éléments dans une carte de 1 000 000, le nombre de comparaisons devrait être d'environ 200 000, soit environ 20 comparaisons par élément cible. Ce n'est vraiment pas mal si votre clé n'est qu'un simple entier.

Si vous deviez hacher quelque chose qui n'a pas déjà une bonne clé, alors je dirais que aller avec boost::unordered_map . Je le mettrais en œuvre avec std::map d'abord, établissez son profil, puis décidez si vous voulez faire le saut vers Boost.

Answer 2

Si vous effectuez fréquemment les mêmes projections sur votre collection, par exemple en extrayant les éléments dont la clé est "42", vous pouvez envisager de maintenir ces sous-ensembles dans des buckets. Vous maintiendriez en interne une table de hachage des clés vers les vecteurs d'éléments avec cette clé, et ajouteriez des éléments au seau approprié ainsi qu'à votre collection primaire représentant "tout". L'extraction d'un sous-groupe d'éléments se fait en temps constant (parce que les collections respectives ont déjà été construites), et la surcharge mémoire de la maintenance des seaux s'échelonne principalement avec le nombre de clés uniques dans votre ensemble de données.

Cette technique est décidément moins efficace si vous avez un grand nombre de valeurs de clés uniques, et rend les insertions et les suppressions plus coûteuses, mais elle est bonne dans certaines situations - j'ai pensé qu'elle valait au moins la peine d'être mentionnée.