Meilleure structure de données pour stocker un million de valeurs?

Question

S'il vous plaît mentionner la complexité temporelle et la meilleure structure de données pour stocker ces valeurs, lorsque les valeurs sont les suivantes:

1. Entiers
2. Cordes (dictionnaire comme le tri)

Je sais Counting sort est préférable quand les entiers sont en une petite gamme.

Merci.

Editer: Désolé, j'ai posé une question un peu différente. La vraie question est de savoir quelle serait la meilleure structure de données pour stocker ces valeurs, si les entiers sont des numéros de téléphone (et les chaînes sont des noms) et ensuite trouver le meilleur algorithme de tri.

Answer 1

Regardez: Btrees et red-black trees.

Vous devriez être capable de trouver des implémentations open source de chacun d'entre eux. (Remarquez, je suppose que vous voulez maintenir une structure triée, plutôt que simplement trier une fois et oublier.)

Answer 2

algorithmes de tri lien wiki: Sorting Algorithm Wiki

tri fusion et tri rapide sont assez bons, ils sont n log n dans le meilleur des cas.

Answer 3

Que diriez-vous d'un heap? Relativement facile à mettre en œuvre et assez rapide. Pour les chaînes, vous pouvez utiliser un Trie avec quelque chose comme trier en rafale qui est censé être l'algorithme de tri de chaînes le plus rapide de sa catégorie.

Answer 4

Pour la plupart des algorithmes de tri, il existe une version en place, un simple tableau peut donc suffire. Pour les chaînes, vous pouvez envisager un http://en.wikipedia.org/wiki/Trie, ce qui pourrait économiser de l'espace. Le bon algorithme de tri dépend de nombreux facteurs, par ex. si les résultats peuvent déjà être triés ou partiellement triés. Bien sûr, si vous avez juste quelques valeurs différentes, Countingsort, Bucketsort etc. peuvent être utilisés.

Answer 5

Sur une machine 32 bits, un million d'entiers peut contenir un tableau de 4 millions d'octets. 4 Mo n'est pas tout ça; 500 fois plus de mémoire dans ce système (et ce n'est pas si costaud selon les standards modernes). Un million de chaînes aura la même taille, à l'exception de l'espace de stockage pour ces chaînes; pour les chaînes courtes, il n'y a toujours pas de problème, alors insérez tout. Vous pouvez même avoir un tableau de pointeurs vers des structures contenant un entier et une référence à une chaîne; Tout ira bien. Ce n'est que lorsque vous manipulez beaucoup plus de données que cela (par exemple, un milliard d'éléments) que vous devez prendre des mesures spéciales, au niveau de la structure des données.

Pour le tri que beaucoup de choses, choisissez un algorithme O (n log n) au lieu de celui qui est O (n ). Les algorithmes O ( n) ne sont utiles que lorsque vous disposez d'espaces clés particulièrement compacts, ce qui est plutôt rare en pratique. Le choix de l'algorithme de l'ensemble qui est dans O ( n log n) est une question de vitesse d'équilibrage et d'autres bonnes propriétés telles que la stabilité.

Si vous faites cela pour de vrai, utilisez une base de données avec des index appropriés au lieu de vous étourdir avec tout cela à la main.