Discussion :

[Cecilka]

Voilà, tout est dit dans le titre. Je voudrais savoir selon vous quel est le meilleur algorithme pour trier un nombre conséquent de chaînes de caractères (2 à 4 millions, mettons) dans l'ordre lexicographique.
Merci

[Matthieu Brucher]

Tri par fusion, non ?

[ToTo13]

Bonjour,

quel est le taille de tes chaines de caractères ?

Si elles ne sont pas tres longues...
une méthode valable dans cette situation est de trier caractère par caractères :
- Tu choisis un algo de tri (quicksort par exemple) et tu tries tous les mots en ne regardant que le caractère i dans la chaine de caractère.
- Tu répètes cette opération en commencant par la fin du mot pour que le tri fonctionne.
- Il faut juste penser à gérer ne fait que les mots n'ont pas la même taille.

[TanEk]

Si tu ne dois juste que trier, prends le quicksort. Si tu dois trier et garder trier (insérer, enlever des chaînes, etc.) utilises un arbre binaire (mais je ne pense pas que ce soit le cas ici).

[gangsoleil]

Bonjour,

Comme l'ont dit les autres personnes, il faut que tu te bases sur un algo comme quicksort.

Ensuite, tu peux chercher non pas à améliorer l'algo, mais à l'appliquer sur tout ou partie de la chaine.

Par exemple si tes chaines ont de très nombreuses différences dans les premiers caractères, il vaut mieux essayer de trier en se bassant d'abord sur les premier caractères.
En revanche, si tu as des chaines ayant une grande probabilité d'avoir le même début, il ne sera pas intéressant de tester systématiquement tous les caractères en commencant par le début.

Il faut donc que tu cherches des points communs ou des différences à tes chaines, pour pouvoir en tirer des heuristiques, qui te permettront d'améliorer le temps de traitment au final.

[Graffito]

Bonjour,

Pour trier simplement, un algo de sort comme indiqué dans les réponses précédentes.

Par contre, si on doit faire des recherches et des insertions, je préconiserais un arbre comme celui de l'exemple ci-dessous (plutot qu'un arbre binaire) :

Avec les les mots :

• A
• AME
• AMI
• AMOUR
• BUT
• CE

on aurait la structure suivante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
#
|
A------------B-------C
|            |       |
*-M          U       E
   |         |       |
   E--I--O   T       *
   |  |  |   | 
   *  *  U   *
         |
         R 
         |
         *

Le caractère * indique la fin du mot.

[panda31]

J'avoue que c'est beau ! Mais un arbre binaire peut faire l'affaire à mon sens. En effet, si tu as un grand nombre de mots comme indiqué dans la requête
de Cecilka, tu vas avoir un nombre inquiétant de branches non ? Ton arbre binaire de recherche pourra quant à lui se limiter en largeur...

[Graffito]

Bonjour,

Mais un arbre binaire peut faire l'affaire à mon sens. En effet, si tu as un grand nombre de mots comme indiqué dans la requête de Cecilka, tu vas avoir un nombre inquiétant de branches non ?

Le nombre de fils d'un noeud est au maximum égal au nombre de symboles de l'alphabet. En pratique, chaque noeud aura un nombre de fils de l'ordre de 1 à 10 et la profondeur des branches correspond à la longueur des mots. Donc, en se basant sur une moyenne de 6 fils par noeud, la recherche/insertion d'un mot de 10 lettres se fera en 10 x 6/2 = 30 comparaisons de noeuds, ce qui represente, à vue de nez, 2 à 4 fois plus que pour un arbre binaire équilibré (AVL). Mais, c'est pas cher payé par rapport au "couts" d'équilibrage de l'AVL lors des insertions/suppressions.

[panda31]

Et bien merci pour ton explication grâce à ce beau calcul de complexité !

[zul]

Pour ameliorer un peu la structure proposé par graffito, tu peux utiliser ce qu'on appelle des arbre de patricia ( patricia tree / radix tree ) ce qui revient a "paquer" ensemble esl branches communes ( cad au lieu d'avoir -b-u-t, tu as un noeud but ) : ca reduit la complexite spatiale.

Si la complexite spatiale n'est pas importante, dans chaque noeud, tu peux stocker un tableau de 26 caractères. La recherche se fait alors en O(n) n longueur de la chaine ou O(1) si tu considere que les chaines sont bornées.