C++ STL Carte vs Vecteur vitesse
Dans l'interpréteur de mes expériences de langage de programmation, j'ai une table de symboles. Chaque symbole est constitué d'un nom et d'une valeur (la valeur peut être par exemple: de type string, int, fonction, etc.).
Au début, j'ai représenté la table avec un vecteur et répétée à travers les symboles de vérifier si le nom de symbole équipée.
Puis je si à l'aide d'une carte, dans mon cas map<string,symbol>, serait mieux que de l'itération par le vecteur de tous les temps mais:
C'est un peu dur à expliquer cette partie, mais je vais essayer.
Si une variable est extrait la première fois dans un programme de ma langue, bien sûr, sa position dans la table des symboles doit être trouvé (à l'aide de vecteur de maintenant). Si je voulais parcourir le vecteur à chaque fois que la ligne est exécuté (pensez à une boucle), il serait terriblement lent (comme c'est le cas actuellement, presque aussi lent que microsoft lot).
Si je pouvais utiliser une carte pour récupérer la variable: SymbolTable[ myVar.Name ]
Mais pensez à ce qui suit: Si la variable, toujours à l'aide de vecteur est la première fois, je peux stocker son entier exact de la position dans le vecteur avec elle. C'est à dire: La prochaine fois que cela est nécessaire, mon interprète, qui sait qu'elle a été "mise en cache" et ne cherchent pas la table des symboles pour elle, mais fait quelque chose comme SymbolTable.at( myVar.CachedPosition ).
Maintenant mon (plutôt dur?) question:
-
Dois-je utiliser un vecteur pour la table de symbole avec la mise en cache de la position de la variable dans le vecteur?
-
Devrais-je plutôt utiliser une carte? Pourquoi? Quelle est la vitesse de l'opérateur []?
-
Dois-je utiliser quelque chose de complètement différent?
- Juste un peu de nourriture pour la pensée, si vous stockez l'entier de la position de votre variable est à et certaines variables d'avant et qui obtient des ordures collectées ou supprimé, quel est votre plan pour que l'entier de cache de position?
Vous devez vous connecter pour publier un commentaire.
Vous avez effectivement un certain nombre de solutions de rechange.
Bibliothèques existent:
vectorde paires, plus rapide qu'une carte pour les petites ou congelés définit en raison de la localité de cache.Critiques
O(log N), mais les éléments peuvent être dispersés à travers la mémoire, donc pas de bien jouer avec les stratégies de mise en cache.O(N)performance surfind, est-il acceptable ?unordered_map? Ils fournissentO(1)de recherche et de récupération (si la constante peut être élevé) et sont certainement adaptés à cette tâche. Si vous avez un coup d'oeil à l'article de Wikipedia sur Les Tables De Hachage vous vous rendrez compte qu'il ya beaucoup de stratégies disponibles et vous pouvez certainement choisir un qui correspond à votre modèle d'utilisation.O(log N)performance.Une carte est une bonne chose d'utiliser une table de symboles. mais
operator[]pour des cartes n'est pas. En général, à moins que vous écrivez quelque trivial code, vous devez utiliser la carte de membre des fonctionsinsert()etfind()au lieu deoperator[]. La sémantique deoperator[]sont un peu compliqué, et presque certainement ne pas faire ce que vous voulez si le symbole que vous cherchez n'est pas dans la carte.Comme pour le choix entre
mapetunordered_map, la différence de performance est très peu susceptible d'être importante lors de la mise en œuvre d'une simple interprétation de la langue. Si vous utilisez la carte, vous avez la garantie qu'il sera pris en charge par tous les Standard C++ implémentations.Normalement, vous pouvez utiliser une table de symbole pour rechercher la variable donné son nom tel qu'il apparaît dans la source. Dans ce cas, vous n'avez que le nom de travailler avec, donc il n'y a nulle part où stocker le cache de la position de la variable dans la table des symboles. Donc, je dirais un
mapest un bon choix. Le[]opérateur prend le temps proportionnel à la log du nombre d'éléments dans la carte - si elle s'avère à être lent, vous pouvez utiliser un hachage de la carte commestd::tr1::unordered_map.mapcomme Tronic dit dans sa réponse. La grande différence, c'est juste le temps de chercher le nom de la variable. (En fait, d'autres problèmes de pop-up si vous voulez sérialiser vos structures de données, mais je vais arrêter de spéculer au sujet de votre code ici ;))std::map de l'opérateur[] prend O(log(n)) de temps. Cela signifie qu'il est très efficace, mais vous devez tout de même éviter de faire les recherches, encore et encore. Au lieu de stocker un indice, peut-être vous pouvez stocker une référence à la valeur, ou un itérateur vers le conteneur? Cela évite d'avoir à faire de recherche entièrement.
Quand la plupart des interprètes interpréter le code, ils compiler dans un langage intermédiaire en premier. Ces intermédiaires langues souvent référence à des variables par indice ou par pointeur, au lieu du nom.
Par exemple, Python (l'implémentation C) les changements de variables locales dans des références à l'index, mais les variables globales et les variables de classe obtenir référencé par le nom à l'aide d'une table de hachage.
Je suggère à la recherche à un texte d'introduction sur les compilateurs.
un
std::map(O(log(n))) ou une table de hachage ("amorti" O(1)) serait le premier choix - utiliser des mécanismes si vous determin c'est un goulot d'étranglement. Généralement, l'utilisation d'une table de hachage ou à la segmentation de l'entrée est la première optimisation.Avant vous ont présenté, c'est plus important que de vous isoler de recherche, de sorte que vous pouvez facilement remplacer et profil de.
std::mapest probablement un peu plus lent que pour un petit nombre d'éléments (mais alors, il n'a pas vraiment d'importance).Carte est O(log N), donc pas aussi rapide que la position de recherche dans un tableau. Mais le résultat exact dépendra de beaucoup de facteurs, et donc, la meilleure approche est de faire l'interface avec le contenant dans une manière qui vous permet de permuter entre la mise en œuvre plus tard. C'est, d'écrire une "recherche" de la fonction qui peut être efficacement mis en œuvre par n'importe quel récipient approprié, pour vous permettre de basculer et de comparer les vitesses des différents la mise en œuvre.
La carte de l'opérateur [] est O(log(n)), voir wikipédia : http://en.wikipedia.org/wiki/Map_(C%2B%2B)
Je pense que vous êtes à la recherche souvent pour des symboles, à l'aide d'une carte est certainement droit. Peut-être un tableau associatif (std::unordered_map) pourrait faire de votre mieux.
Si vous allez utiliser un
vectoret aller à la difficulté de mise en cache de la plus récente symbole de rechercher conséquent, vous pourriez vous faire de même (cache de la plus récente recherche de résultat) si votre table de symboles ont été mis en œuvre comme unmap(mais il ne serait probablement pas beaucoup d'avantage pour le cache dans le cas de l'utilisation d'unmap). Avec unmapvous auriez l'avantage supplémentaire que les non-cache symbole look ups serait beaucoup plus performant que la recherche dans unevector(en supposant que levectorn'est pas le tri - et de garder un vecteur trié peut être coûteux si vous avez à faire le tri plus d'une fois).Prendre Neil conseils;
mapest généralement une bonne structure de données pour la table des symboles, mais vous devez vous assurer que vous utilisez correctement (et pas de l'ajout de symboles accidentellement).Vous dites: "Si la variable, toujours à l'aide de vecteur est la première fois, je peux stocker son entier exact de la position dans le vecteur avec elle.".
Vous pouvez faire de même avec la carte: la recherche de la variable à l'aide
findet stocker lesiteratorpointant vers elle au lieu de la position.Pour la recherche de valeurs, par une chaîne de clé, la carte, le type de données le plus approprié, comme mentionné par d'autres utilisateurs.
STL carte implémentations sont généralement mis en œuvre avec auto-équilibrage des arbres, comme le rouge noir de l'arbre structure de données, et de leurs opérations en O(logn) temps.
Mon conseil est d'envelopper la manipulation de la table de code en fonctions,
comme
table_has(name),table_put(name)ettable_get(name).De cette façon, vous pouvez changer l'intérieur de la table des symboles de la représentation facilement si vous avez de l'expérience
ralentir moment de l'exécution de la performance, de plus, vous pouvez intégrer dans ces routines cache des fonctionnalités plus tard.
Une carte à l'échelle de beaucoup mieux, ce qui sera un élément important. Cependant, n'oubliez pas que lorsque vous utilisez une carte, vous pouvez (à la différence d'un vecteur) de prendre des pointeurs et des références. Dans ce cas, vous pourriez facilement "cache" variables avec une carte tout aussi valablement comme un vecteur. Une carte est presque certainement le bon choix ici.