Quelle structure de données est la plus rapide pour l'insertion et la recherche d'éléments?

Question

J'écris un programme qui fera une compression de base en utilisant une table de recherche. Pour créer la table, je vais lire dans un fichier texte (taille 2MB), puis trouver les 255 mots les plus communs et les stocker dans un autre fichier texte. J'essaie d'utiliser un vecteur maintenant, mais l'exécution est lente à environ une minute d'exécution pour l'insérer dans le vecteur, le trier, puis afficher les 255 premiers éléments dans un autre fichier texte. L'insertion semble être problématique car je dois vérifier si elle existe déjà à l'intérieur du vecteur puis incrémenter un compteur s'il existe, ou ajouter l'élément à la fin du vecteur si ce n'est pas le cas. J'ai besoin de trouver un moyen efficace d'insérer des éléments dans une structure de données seulement quand ils ne sont pas déjà dans la structure de données (pas de doublons).

Answer 1

std::unordered_map est susceptible être le mieux à vos besoins, aucune garantie. Vous pouvez "ajouter une clé si et seulement si elle n'est pas déjà présente" simplement en utilisant operator[].

Vous ferez un passage sur la division de 2 Mo en mots et en comptant les fréquences (une recherche dans la structure par mot). Ensuite, utilisez std::partial_sort_copy (la version qui prend un comparateur) pour obtenir le top 255 par le nombre de fréquence à partir du unordered_map. Vous devez partial_sort_copy dans un vecteur ou un tableau, puis l'utiliser pour écrire le fichier.

Pour 2 Mo de données, tout ce qui est en quelques secondes est certainement plus lent qu'il ne devrait "l'être", et quelques secondes sont encore plus lentes que possible. Vous avez donc raison de vous préoccuper de votre vecteur, mais vous devez également définir votre code pour vous assurer qu'il s'agit vraiment du vecteur qui vous a coûté le temps, et non d'un autre problème.

Answer 2

Essayez d'utiliser STL map ou set il est beaucoup plus rapide que vecteur: voir here