J'utilise C++, disons que je veux stocker 40 noms d'utilisateur, je vais simplement utiliser un tableau. Cependant, si je veux stocker 40000 noms d'utilisateur est-ce encore une bonne idée en termes de vitesse de recherche? Quelle structure de données devrais-je utiliser pour améliorer cette vitesse?sélection de la structure de données
Vous devez spécifier les exigences d'insertion et de retrait. Est-ce que les choses doivent être enlevées et insérées au hasard dans la séquence?
Aussi, pourquoi l'exigence de rechercher séquentiellement? Faites-vous des recherches qui ne conviennent pas pour une recherche de table de hachage? Pour le moment je suggérerais un deque ou un list. Souvent, il est préférable de choisir un conteneur avec l'interface qui permet l'implémentation la plus simple pour votre algorithme et de ne modifier le choix que si la performance est insuffisante et qu'une alternative fournit l'accélération nécessaire. Un vector a deux avantages principaux, il n'y a pas de surcharge de mémoire par objet, bien que les vecteurs vont sur-allouer pour empêcher la copie fréquente et les objets sont stockés de manière contiguë, donc l'accès séquentiel a tendance à être rapide. Ce sont aussi ses inconvénients. Les vecteurs de croissance nécessitent une réallocation et une copie, et l'insertion et le retrait de n'importe quel autre endroit que la fin du vecteur nécessitent également une copie. Le stockage contigu peut générer des problèmes pour les vecteurs comportant un grand nombre d'objets ou de grands objets, car les exigences de stockage contigu peuvent être difficiles à satisfaire même avec une fragmentation de la mémoire légère.
Un list ne nécessite pas de stockage contigu mais les noeuds de liste ont généralement une surcharge par objet de deux pointeurs (dans la plupart des implémentations). Cela peut être significatif dans la liste des objets très petits (par exemple dans une liste de pointeurs, chaque noeud a 3 fois la taille de l'élément de données). L'insertion et la suppression au milieu d'une liste sont très bon marché et les nœuds de liste n'ont jamais besoin d'être déplacés en mémoire une fois créés. Un dequedeque utilise un stockage fragmenté, donc il a un faible coût par objet similaire à un vecteur, mais ne nécessite pas de stockage contigu sur tout le conteneur, donc il n'a pas le même problème avec les espaces mémoire fragmentés. C'est souvent un très bon choix pour les collections et est souvent négligé. Std :: vector et std :: list semblent bons pour cette tâche.
Vous pouvez utiliser un tableau si vous connaissez le nombre maximum d'enregistrements à l'avance.
Si vous n'avez besoin que d'une recherche et d'un stockage séquentiels, alors list est le conteneur approprié. En outre, vector ne serait pas un mauvais choix.
std :: list est un mauvais choix si seulement un accès séquentiel est requis, car il a un temps système plus important que le vecteur ou le deque. liste est seulement un bon choix si insérer/supprimer au milieu est nécessaire. –
J'ai testé la liste sur un appareil portatif. La liste contenait 70 000 chaînes. J'ai dû «recueillir» et rechercher les données progressivement. La recherche était ** très ** rapide. J'ai également testé le vecteur et la carte. Eh bien, la liste a gagné dans mon cas. C'est vraiment un problème dépendant de la * solution *. –
Je parlais de surcharge de mémoire. Bien sûr, si une allocation supplémentaire par article est abordable, alors ce n'est pas une préoccupation, alors peut-être que le «mauvais choix» surestime le cas. Mais je ne pense pas qu'il soit juste de l'appeler le «conteneur approprié» non plus, puisque vous payez pour quelque chose que vous n'utilisez pas. –
En règle générale, préférez vector à list ou, diety interdisent, tableau de style C. Une fois le vecteur rempli, assurez-vous qu'il est correctement ordonné à l'aide de l'algorithme sort. Vous pouvez ensuite rechercher un enregistrement particulier en utilisant find, binary_search ou lower_bound. (Vous n'avez pas besoin de trier pour utiliser find.)
Sérieusement, sauf si vous êtes dans un environnement à contraintes de ressources (plate-forme intégrée, téléphone ou autre). Utilisez un std::map, économisez l'effort de tri ou de recherche et laissez le conteneur s'occuper de tout. Ce sera probablement une structure arborescente triée, probablement équilibrée (par exemple rouge-noir), ce qui signifie que vous obtiendrez de bonnes performances de recherche. À moins que la taille de vos données soit proche de la taille d'un ou deux pointeurs, le temps de mémoire de la structure de données que vous choisissez est négligeable.Votre carte graphique a probablement plus de mémoire que vous allez utiliser pour les données auxquelles vous pensez.
Comme d'autres ont dit il y a très peu de bonnes raisons d'utiliser le tableau de vanille, si vous ne voulez pas utiliser une map utilisation std::vector ou std::list selon que vous devez insérer/supprimer des données (=> Liste) ou non (= > vector)
Considérez également si vous avez vraiment besoin de toutes ces données en mémoire, que diriez-vous de le mettre sur le disque via sqlite. Ou même utiliser sqlite pour l'accès en mémoire. Tout dépend de ce que vous devez faire avec vos données.
Je ne vois pas pourquoi vous utiliseriez un tableau - la taille n'est pas le problème. –