Discussion :

[laurent_ott]

Bonjour à vous tous.
J'ai développé un algorithme de tri qui me semble assez performant.
D'après mes tests, il est même plus rapide que QSort sur les chaines de caractères volumineuses.
Mais il est écrit en VBA et je voudrais savoir s'il est aussi performant dans d'autres langages, par exemple en C, que je ne maitrise pas.
Je recherche donc des volontaires piqués par la curiosité.
Je vous renvoie à cette documentation qui explique tout : https://hal.archives-ouvertes.fr/hal-01154432/document
Le fichier EXCEL source (et aussi pour faire vos tests) est en pièce jointe dans : https://hal.archives-ouvertes.fr » (recherchez avec le mot clé : QuickRanking).

Merci d'avance pour vos remarques.

[dourouc05]

Selon le point de vue, ce n'est pas difficile d'être plus rapide que le tri rapide : sa complexité algorithmique en temps dans le pire cas est , alors que la complexité optimale du tri est plutôt ; si tu connais un peu les données à trier, tu peux choisir un algorithme qui fonctionne mieux sur ce type de données, voire en écrire une variante (par exemple, si tes données sont à peu près triées : http://www.geeksforgeeks.org/nearly-sorted-algorithm/).

As-tu effectué une analyse plus théorique de la performance de ton algorithme ? L'avantage d'une telle analyse, c'est qu'elle permet de comparer des algorithmes en ignorant les questions de langage : si la complexité est faible, tu peux t'attendre à avoir un algorithme plus rapide… sur de très grands volumes de données (analyse asymptotique). (En tout cas, je n'en vois pas de trace dans ton document, pas même le mot "complexité".)

[picodev]

Bonjour,
pour affiner les dires de Dourouc, il parle de complexité de type temporelle en terme de comparaisons, ce qui ne concerne que les algorithmes de tri par comparaison entre éléments. Il existe des algorithmes de tri qui ne sont pas des algorithmes de tri par comparaison entre élément → bucket sort, radix sort par exemple, leur complexité temporelle est en O(n).

Tu t'es donné du mal pour écrire ton article, mais je suis frustré. Je ne vois aucun algorithme. Je vois un exemple, du code VBA (beaucoup de code VBA) mais aucun algorithme.
La première chose à faire est sans doute de donner le pseudo code de ton algo, car sinon c'est très rébarbatif …

[laurent_ott]

Merci pour ta réponse.
En effet je ne suis pas mathématicien et je suis incapable d'expliquer cet algorithme en ces termes. Ce qui nuit à sa notoriété car la lecture du document donne l'impression d'un amateurisme ridicule. Je vous remercie de me pardonner cette faiblesse et de passer outre.

Pour répondre à ta deuxième remarque, je propose ici un algorithme qui est générique, pas spécifique à une situation donnée, un passe partout : "liste idéalement aléatoire ou liste fortement classée, données volumineuses ou de taille réduite données numériques ou alphanumériques, la réalité se situe souvent entre ces extrêmes".

Enfin, j'ai simplifié un peu la présentation, car c'est sûr qu'il est "facile" d'être plus rapide que QSort sur des chaînes de caractères (surtout si elles sont déjà partiellement triées), sauf que j'ai aussi comparé mon algorithme avec la version de QSort optimisée pour ce traitement : "QuickSort_AndRank, qui ne déplace pas directement les données mais déplace les références des indices des données. D’où un gain de temps sur les traitements des données alphanumériques volumineuses car l’on déplace des entiers de 4 octets et non plus des chaînes de caractères de longueurs variables".

Pour répondre à ta remarque, je ne pense pas que la seule notion de complexité théorique suffise. Car d'après mon expérience, ce qui prend du temps de traitement, c'est aussi l'usage des conditions (if Then, Do Loop, etc.), et le déplacement des variables.
Par exemple, pour la recherche dichotomique, dans un premier temps j'ai utilisé une boucle "Do... Loop While". Mais une boucle "For i = 1 to log(n)/log(2)... Next" est bien plus rapide. Pour une même complexité théorique.

Du moins en VBA. Voir la synthèse de la page 16. Est-ce le cas en C ? C'est ce que je souhaiterais savoir.

[DonQuiche]

Bonjour, de ce que j'ai vu ton algorithme est une simple variante du tri par insertion, dans laquelle on utilise une liste chaînée plutôt que de permuter les éléments. J'ai le regret de t'apprendre qu'il n'y a là rien de bien neuf.

Et le tri par insertion est justement connu pour être efficace lorsque les données sont déjà partiellement triées.

[anapurna]

salut

en regardant le programme vba tout ceci est bien confus des boucle dans tout les sens des goto en veut tu en voila
je ne suis vraiment pas certain que le tout soit d'une optimisation total

Tu Fait des recherche dichotomique tu scinde tes donné en sous éléments tout ceci ressemble fortement a un trie fusion si je me souvient bien

[laurent_ott]

ça ressemble à un tri par fusion, oui. Ça ressemble ainsi à un tri par indexation. Mais alors comment expliquez vous sa rapidité. Quant aux GOTO, c'est justement pour gagner en vitesse, même si ça ne fait pas joli ni professionnel. Et le plus c'est que l'algorithme retourne le classement, en conservant l'ordre d'origine en cas d'égalités. Je reconnais qu'il ne donne pas envie d'y passer du temps pour l'implémenter en C. Merci pour vos remarques très pertinentes. je réfléchis à vous faire un pseudo code même si je n'y connais rien.

[DonQuiche]

ça ressemble à un tri par fusion, oui. Ça ressemble ainsi à un tri par indexation. Mais alors comment expliquez vous sa rapidité.

Comme je te l'ai expliqué, le tri par insertion est très efficace pour les données partiellement triées.

Et j'insiste : d'après ton PDF ça ne ressemble pas seulement à un tri par insertion, c'est bel et bien un tri par insertion. Je n'ai pas regardé le code en revanche.

"QuickSort_AndRank, qui ne déplace pas directement les données mais déplace les références des indices des données. D’où un gain de temps sur les traitements des données alphanumériques volumineuses car l’on déplace des entiers de 4 octets et non plus des chaînes de caractères de longueurs variables".

Un type chaîne de caractères est en fait une référence vers une chaîne. La chaîne n'est donc pas copiée, seulement sa référence qui fait 4 octets en 32 bits (8 en 64).

Pour répondre à ta remarque, je ne pense pas que la seule notion de complexité théorique suffise.

En général c'est vrai : il faut aussi regarder les motifs des accès mémoire. Mais dans le cas présent la performance de ton algorithme s'explique grâce à la seule complexité théorique sur des listes partiellement triées.

Car d'après mon expérience, ce qui prend du temps de traitement, c'est aussi l'usage des conditions (if Then, Do Loop, etc.), et le déplacement des variables.

En général ce sont les accès mémoire qui dominent les performances. Les branchements conditionnels ne sont plus tellement importants sur les CPU récents.

Par exemple, pour la recherche dichotomique, dans un premier temps j'ai utilisé une boucle "Do... Loop While". Mais une boucle "For i = 1 to log(n)/log(2)... Next" est bien plus rapide. Pour une même complexité théorique.

Un léger gain aurait été possible, un fort gain paraît plus douteux. Je t'encourage à vérifier.