Quel est le conteneur STL le plus rapide pour find?
D'accord comme préface j'ai besoin de mettre en cache un sous-ensemble relativement petit de données rarement modifiées pour éviter d'interroger la base de données aussi souvent pour des raisons de performance. Ces données sont largement utilisées en lecture seule car elles sont souvent référencées par un ensemble beaucoup plus important de données dans d'autres tableaux.
j'ai écrit une classe qui aura la capacité de stocker essentiellement l'intégralité des deux tables en question dans la mémoire tout en écoutant les changements de propagation en conjonction avec un thread mécanisme de rappel sécurisé pour la mise à jour des objets mis en cache.
mon implémentation actuelle a deux std::vectors pour les éléments de chaque tableau. La classe fournit à la fois l'accès à l'ensemble de chaque vecteur ainsi que des méthodes de commodité pour la recherche d'un élément spécifique de données de tableau via std::find,std::find_if, etc.
est-ce que quelqu'un sait s'il utilise std::list,std::set, ou std::mapstd::vector pour la recherche serait-elle préférable? La plupart du temps c'est ce qui va être demandé de ces conteneurs après avoir peuplé une fois de la base de données quand une nouvelle connexion est faite.
je suis également ouvert à l'utilisation des fonctionnalités c++0x supportées par VS2010 ou Boost.
7 réponses
Pour la recherche d'une valeur particulière, avec std::set et std::map il faut O(log N) le temps, tandis que les deux autres, il prend O(N) fois; Ainsi, std::set ou std::map sont probablement mieux. Puisque vous avez accès à C++0x, vous pouvez également utiliser std::unordered_set ou std::unordered_map qui prennent en moyenne un temps constant.
find_if, il y a peu de différence entre eux, car il faut un prédicat arbitraire et les conteneurs ne peuvent pas optimiser arbitrairement, bien sûr.
cependant si vous appeler find_if souvent avec un certain prédicat, vous pouvez optimiser vous-même: utiliser un std::map ou std::set avec un comparateur ou les touches spéciales et utiliser find à la place.
un vecteur trié utilisant std::lower_bound peut être aussi rapide que l' std::set si vous ne mettez pas à jour très souvent; ils sont tous les deux O(log n). Cela vaut la peine d'essayer à la fois de voir ce qui est mieux pour votre propre situation.
puisque de vos exigences (étendues) vous avez besoin de rechercher sur plusieurs champs, je vous indiquerais pour Boost.MultiIndex.
Cette bibliothèque Boost vous permet de construire conteneur (avec un seul exemplaire de chaque élément qu'il contient) et de l'indice sur un nombre arbitraire des indices. Il vous permet également de préciser les indices à utiliser.
pour déterminer le type d'indice à utiliser, vous aurez besoin de repères étendus. 500 est relativement faible le nombre d'entrées, donc les facteurs constants ne vont pas bien jouer. De plus, il peut y avoir une différence notable entre l'utilisation d'un seul thread et l'utilisation de plusieurs threads (la plupart des implémentations de tables de hachage peuvent s'effondrer sur L'utilisation de MT parce qu'elles n'utilisent pas le réhasage linéaire, et donc un seul thread finit par ressasser la table, bloquant tous les autres).
je recommande un index trié (sauter-liste comme, si possible) pour répondre aux demandes de portée (tous les noms commençant par Abc?) si la performance la différence est soit invisible, soit sans importance.
si vous voulez seulement rechercher des valeurs distinctes, une colonne spécifique dans le tableau, alors std::hash est le plus rapide.
si vous voulez être en mesure de rechercher en utilisant plusieurs prédicats différents, vous aurez besoin d'une sorte de structure d'index. Il peut être mis en œuvre en étendant votre approche actuelle basée sur les vecteurs avec plusieurs tables de hachage ou cartes, une pour chaque champ à rechercher, où la valeur est soit un index dans le vecteur, ou un pointeur direct vers l'élément dans le vecteur.
aller plus loin, si vous voulez être en mesure de rechercher des gammes, comme toutes les occasions ayant une date en juillet, vous avez besoin d'une structure de données ordonnée, où vous pouvez extraire une gamme.
le Tester. Il est très facile, les conteneurs sont presque interchangeables dans STL.
Pas de la stl, mais un commercial c++ conteneur est abax conteneur qui a O(1), à la recherche, de supprimer, de modifier, d'O(logn) de l'insert.
ce n'est Pas une réponse en soi, mais assurez-vous d'utiliser un typedef pour désigner le type de conteneur que vous utilisez, quelque chose comme typedef std::vector< itemtype > data_table_cache; alors utilisez votre typedef partout.