Bonjour les devs!
Aujourd'hui je suis confronté à un petit problème dont je n'ai pas assez de connaissance et de savoir pour le résoudre.
Pour résumer :
J'ai un algorithme qui utilise std::sort pour chaque mot parcouru dans une énorme liste. Avec std::sort, le programme tourne dans les 1675.2 millisecondes sur mon ordi très moyen. Sur un ordi doté d'un vrai processeur l'algo tourne en seulement 18 millisecondes!
J'ai changé std::sort en smoothsort (que j'ai implémenté, plutôt que j'ai trouvé sur Internet) et le résultat est meilleur sur ma machine : 1535.2 millisecondes. Cependant je ne l'ai pas fait tourner sur l'ordi doté de puissance (parce que ce n'est pas possible pour le moment).
Je me demandais si le temps d’exécution de l'algo avec smoothsort respecterait le tableau en croix : à savoir (18*1535.2)/1675.2 = 16.5 ms ; est-ce que c'est nécessairement vrai? Peut-être que ça dépend de comment l'algo smoothsort tourne sur la machine puissante.
Pour détailler :
Je fais en fait un algo qui prend en entrée une liste (de type vector) énorme de mots de la langue français (ou autre, peu importe), et qui pour chaque mot, le trie dans l'ordre alphabétique pour ainsi le stocker en tant que clef dans une unordered_map qui a pour valeur les indices des mots qui ont la même composition de lettres lorsqu'ils sont triés.
Clef = chaîne de caractères triée dans l'ordre alphabétique -> Valeur = liste d'indices des mots correspondant
Considérons N la taille de la liste (qui est très très grande) et k la taille moyennes d'un mot de la liste ; en utilisant std::sort la complexité moyenne est de k*log(k)*N ce qui correspond à 18 ms sur la machine puissante. Tandis qu'avec smoothsort la complexité est légèrement meilleur puisqu'elle est égale à la longueur du mot k lorsque les lettres sont déjà triées ; cependant je ne sais pas s'il y a une vraie différence lorsque le programme tourne sur l'ordi performant.
Mon but étant de trouver un algorithme rapide en moins de 11 ms!
Comme vous pouvez le remarquer, ce qui est assez coûteux en temps c'est le tri des lettres, puisque de toutes manières, nous sommes obligés de parcourir la liste de taille N au moins une fois.
Idéalement, la complexité doit être à peu près égal à N, mais les algo de tri ne sont pas les meilleurs pour atteindre cet idéal.
Ce que je voulais savoir c'est :
-Est-ce que le produit en croix s’applique au temps d’exécution de deux programmes sur deux processeurs : à savoir (18*1535.2)/1675.2 = 16.5 ms
-Qu'est-ce qui pourrait être plus efficace que de trier les lettres de chaque mot pour compter le nombre de mots qui ont le même nombre de lettres?
Partager