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

Les tables de hachage ont fondamentalement une consultation O(1). Cela vous donne O(m) pour consulter m éléments ; évidemment vous ne pouvez pas consulter m éléments plus rapidement que O(m) parce que vous devez sortir le résultat.

Answer 2

Si vous ne faites que de la consultation (vous n'avez pas besoin d'éléments ordonnés) et que vous pouvez renoncer à un peu de mémoire, essayez unordered_map (c'est TR1, également implémenté dans Boost), qui a un look-up amorti en temps constant.

Dans un moteur de jeu, nous avons testé std::map y unordered_map et tandis que map était plus rapide pour les insertions (si je me souviens bien), unordered_map l'a fait sortir de l'eau pour le récupérer. Nous avions plus de 1000 éléments dans la carte, pour l'échelle, ce qui est assez faible par rapport à certaines autres tâches que vous pouvez faire.

Si vous avez besoin que les éléments soient commandés, votre prochain pari est std::map qui a les temps de consultation que vous avez affichés, et garde les éléments ordonnés. En général, il utilise également moins de mémoire qu'un fichier unordered_map .

Answer 3

Si votre conteneur est un vecteur et que les éléments sont triés, vous pouvez utiliser std::lower_bound à rechercher en temps O(log n). Si vos éléments de recherche sont également triés, vous pouvez effectuer une petite optimisation en utilisant toujours le dernier itérateur trouvé comme point de départ de la recherche du suivant, par ex.

vector<stuff> container;
vector<stuff>::iterator it = container.begin();
for (int i = 0;  i < search_items.size() && it != container.end();  ++i)
{
    it = std::lower_bound(it, container.end(), search_items[i]);
    // make sure the found item is a match
    if (it != container.end() && search_items[i] < *it)
        it = container.end(); // break out early
}
if (it != container.end())  // found it!

Answer 4

Boost/tr1 unordered_map et unordered_set sont des conteneurs soutenus par une table de hachage qui vous donne une recherche en temps contant amorti [ O(1) ].

Boost Documentation non ordonnée.

Answer 5

Je suppose que si vous disposez d'un conteneur trié et d'une distribution uniforme d'éléments, le type de méthode le plus efficace serait une recherche récursive par bissection avec un chemin d'exécution ressemblant à un arbre - s'appelant deux fois chaque fois que tous les objets recherchés se trouvent dans les deux moitiés de la bissection.

Cependant, si vous choisissez un conteneur basé sur une table de hachage (boost unordered set, je pense ?), ou quelque chose de similaire, alors la recherche peut être O(1), donc la recherche dans une boucle n'a pas vraiment d'importance.

EDIT : notez que std::map et std::set sont normalement (toujours ?) implémentés en utilisant des rb-trees, donc ne sont que log(n) pour la recherche.