La mémoire de chaques structures a été alloué avec un malloc, je ne suis
donc pas dans le cas d'une liste de structure stocké dans un tableau. (
genre struct toto[xx];), de ce fait, je ne peux utiliser qsort().
Quelqu'un pourait-il me proposer une routine rapide pour ce traitement?
Il faut dans la mesure du possible éviter de changer les données de place et ne bouger que les adresses.
C'est ce que fait le tri/insersion
-- Emmanuel The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html The C-library: http://www.dinkumware.com/refxc.html
"It's specified. But anyone who writes code like that should be transmogrified into earthworms and fed to ducks." -- Chris Dollin CLC
Harpo
Emmanuel Delahaye wrote:
Harpo wrote on 11/09/05 :
Il faut dans la mesure du possible éviter de changer les données de place et ne bouger que les adresses.
C'est ce que fait le tri/insersion
J'ai un programme où il y a une chose comme ça, c'est un programme pour tester mes listes, en fait il insère ou modifie les élements que l'on veut mettre dans la liste, ça me paraît raisonnable pour de petites listes, disons, au pif, une centaine d'éléments.
Je ne me rappelle plus bien toutes les théories à ce sujet, mais il est simple de comprendre qu'un algo dont le temps d'exécution est proportionnel au nombre de données est préférable à un algo dont le temps d'exécution est proportionnel au carré ( par exemple ) de ce nombre, le fait de ne pas reopier les données joue dans le même rapport que l'incidence du nombre de données. Le gain d'une bonne implémentation de l'algo est généralement une fonction plus ou moins linéaire, ce qui veut dire que tu vas diviser le temps de son exécution par disons 10, mais quand son temps d'exécution n'est pas une fonction linéaire du nombre de données, l'importance de la bonne implémentation va décroître alors que le choix d'un bon algorithme va croître lorsque le nombre de données augmente. i.e. A quoi ça sert de diminuer par 10 le temps d'exécution s'il peut être multiplié par 100 ou 1000 en raison du choix de l'algo ?
Mon conseil : choisir un bon algorithme et bien l'implémenter. Mon second conseil : Se demander si quelqu'un ne l'a pas fait avant vous.
Emmanuel Delahaye wrote:
Harpo wrote on 11/09/05 :
Il faut dans la mesure du possible éviter de changer
les données de place et ne bouger que les adresses.
C'est ce que fait le tri/insersion
J'ai un programme où il y a une chose comme ça, c'est un programme pour
tester mes listes, en fait il insère ou modifie les élements que l'on
veut mettre dans la liste, ça me paraît raisonnable pour de petites
listes, disons, au pif, une centaine d'éléments.
Je ne me rappelle plus bien toutes les théories à ce sujet, mais il est
simple de comprendre qu'un algo dont le temps d'exécution est
proportionnel au nombre de données est préférable à un algo dont le
temps d'exécution est proportionnel au carré ( par exemple ) de ce
nombre, le fait de ne pas reopier les données joue dans le même rapport
que l'incidence du nombre de données.
Le gain d'une bonne implémentation de l'algo est généralement une
fonction plus ou moins linéaire, ce qui veut dire que tu vas diviser le
temps de son exécution par disons 10, mais quand son temps d'exécution
n'est pas une fonction linéaire du nombre de données, l'importance de
la bonne implémentation va décroître alors que le choix d'un bon
algorithme va croître lorsque le nombre de données augmente.
i.e. A quoi ça sert de diminuer par 10 le temps d'exécution s'il peut
être multiplié par 100 ou 1000 en raison du choix de l'algo ?
Mon conseil : choisir un bon algorithme et bien l'implémenter.
Mon second conseil : Se demander si quelqu'un ne l'a pas fait avant
vous.
Il faut dans la mesure du possible éviter de changer les données de place et ne bouger que les adresses.
C'est ce que fait le tri/insersion
J'ai un programme où il y a une chose comme ça, c'est un programme pour tester mes listes, en fait il insère ou modifie les élements que l'on veut mettre dans la liste, ça me paraît raisonnable pour de petites listes, disons, au pif, une centaine d'éléments.
Je ne me rappelle plus bien toutes les théories à ce sujet, mais il est simple de comprendre qu'un algo dont le temps d'exécution est proportionnel au nombre de données est préférable à un algo dont le temps d'exécution est proportionnel au carré ( par exemple ) de ce nombre, le fait de ne pas reopier les données joue dans le même rapport que l'incidence du nombre de données. Le gain d'une bonne implémentation de l'algo est généralement une fonction plus ou moins linéaire, ce qui veut dire que tu vas diviser le temps de son exécution par disons 10, mais quand son temps d'exécution n'est pas une fonction linéaire du nombre de données, l'importance de la bonne implémentation va décroître alors que le choix d'un bon algorithme va croître lorsque le nombre de données augmente. i.e. A quoi ça sert de diminuer par 10 le temps d'exécution s'il peut être multiplié par 100 ou 1000 en raison du choix de l'algo ?
Mon conseil : choisir un bon algorithme et bien l'implémenter. Mon second conseil : Se demander si quelqu'un ne l'a pas fait avant vous.
Richard Delorme
Je me suis fait repérer...
Si tu connais le nombre d'éléments de la liste, tu alloues un tableau dans lequel tu charges les pointeurs vers les éléments de la liste , tu tries ce tableau de pointeurs avec qsort, tu reprends le tableau sequentiellement pour refaire les chaînages dans la liste. Si tu ne connais pas le nombre d'éléments, il faut d'abord les compter pour allouer le tableau avant de faire la même chose.
Il y a certainement mieux, mais ce n'est pas compliqué à programmer et d'une performance acceptable. La solution d'Emdel est correcte pour des listes pas très grandes. Sinon, beaucoup d'algorithmes de tri sont sans doute applicables. Il faut dans la mesure du possible éviter de changer les données de place et ne bouger que les adresses.
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à boire. Adapter les structures de données à qsort doit sans doute être aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce que le web regorge d'exemples déjà écrit) de novo un algorithme de tri. Pour les petites listes, le tri par insertion est particulièrement indiquée parce que l'insertion est facile avec une liste chainée. Pour les grandes listes, le tri par fusion (qui ressemble au quicksort) est particulièrement indiquée parce que la fusion de deux listes chainées est facile (on relie la fin de la première au début de la seconde).
En fait les listes chainées ont quasiment été conçu pour ces algorithmes de tri et utiliser qsort avec montre quelque part une mauvaise conception. Soit on utilise des tableaux et qsort soit on utilise des listes chainées et l'algorithme qui va bien avec. Sinon c'est chercher midi à quatorze heure.
-- Richard
Je me suis fait repérer...
Si tu connais le nombre d'éléments de la liste, tu alloues un tableau
dans lequel tu charges les pointeurs vers les éléments de la liste , tu
tries ce tableau de pointeurs avec qsort, tu reprends le tableau
sequentiellement pour refaire les chaînages dans la liste.
Si tu ne connais pas le nombre d'éléments, il faut d'abord les compter
pour allouer le tableau avant de faire la même chose.
Il y a certainement mieux, mais ce n'est pas compliqué à programmer et
d'une performance acceptable. La solution d'Emdel est correcte pour des
listes pas très grandes. Sinon, beaucoup d'algorithmes de tri sont sans
doute applicables. Il faut dans la mesure du possible éviter de changer
les données de place et ne bouger que les adresses.
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à
boire. Adapter les structures de données à qsort doit sans doute être
aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce
que le web regorge d'exemples déjà écrit) de novo un algorithme de tri.
Pour les petites listes, le tri par insertion est particulièrement
indiquée parce que l'insertion est facile avec une liste chainée. Pour
les grandes listes, le tri par fusion (qui ressemble au quicksort) est
particulièrement indiquée parce que la fusion de deux listes chainées
est facile (on relie la fin de la première au début de la seconde).
En fait les listes chainées ont quasiment été conçu pour ces algorithmes
de tri et utiliser qsort avec montre quelque part une mauvaise
conception. Soit on utilise des tableaux et qsort soit on utilise des
listes chainées et l'algorithme qui va bien avec. Sinon c'est chercher
midi à quatorze heure.
Si tu connais le nombre d'éléments de la liste, tu alloues un tableau dans lequel tu charges les pointeurs vers les éléments de la liste , tu tries ce tableau de pointeurs avec qsort, tu reprends le tableau sequentiellement pour refaire les chaînages dans la liste. Si tu ne connais pas le nombre d'éléments, il faut d'abord les compter pour allouer le tableau avant de faire la même chose.
Il y a certainement mieux, mais ce n'est pas compliqué à programmer et d'une performance acceptable. La solution d'Emdel est correcte pour des listes pas très grandes. Sinon, beaucoup d'algorithmes de tri sont sans doute applicables. Il faut dans la mesure du possible éviter de changer les données de place et ne bouger que les adresses.
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à boire. Adapter les structures de données à qsort doit sans doute être aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce que le web regorge d'exemples déjà écrit) de novo un algorithme de tri. Pour les petites listes, le tri par insertion est particulièrement indiquée parce que l'insertion est facile avec une liste chainée. Pour les grandes listes, le tri par fusion (qui ressemble au quicksort) est particulièrement indiquée parce que la fusion de deux listes chainées est facile (on relie la fin de la première au début de la seconde).
En fait les listes chainées ont quasiment été conçu pour ces algorithmes de tri et utiliser qsort avec montre quelque part une mauvaise conception. Soit on utilise des tableaux et qsort soit on utilise des listes chainées et l'algorithme qui va bien avec. Sinon c'est chercher midi à quatorze heure.
-- Richard
Harpo
Richard Delorme wrote:
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à boire. Adapter les structures de données à qsort doit sans doute être aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce que le web regorge d'exemples déjà écrit) de novo un algorithme de tri.
Je ne suis pas d'accord, cela doit faire une 30aine de lignes de C alors qu'implémenter un algorithme demandrait bien plus. Si ça vous plait d'implémenter des algos de tris c'est votre problème, mais je ne vois pas l'intérêt de passer une journée ou plus à développer ce qui peut être fait en une heure peinard. Ceci dit, développez un tri sur les listes chaînées en implémentant un algo et venez comparer ce que l'on peut faire avec qsort(), il n'est pas certain que vous gagniez une micro-seconde de CPU chaque année, il me semble clair que vous y passeriez un certain temps.
Richard Delorme wrote:
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à
boire. Adapter les structures de données à qsort doit sans doute être
aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce
que le web regorge d'exemples déjà écrit) de novo un algorithme de
tri.
Je ne suis pas d'accord, cela doit faire une 30aine de lignes de C alors
qu'implémenter un algorithme demandrait bien plus.
Si ça vous plait d'implémenter des algos de tris c'est votre problème,
mais je ne vois pas l'intérêt de passer une journée ou plus à
développer ce qui peut être fait en une heure peinard.
Ceci dit, développez un tri sur les listes chaînées en implémentant un
algo et venez comparer ce que l'on peut faire avec qsort(), il n'est
pas certain que vous gagniez une micro-seconde de CPU chaque année, il
me semble clair que vous y passeriez un certain temps.
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à boire. Adapter les structures de données à qsort doit sans doute être aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce que le web regorge d'exemples déjà écrit) de novo un algorithme de tri.
Je ne suis pas d'accord, cela doit faire une 30aine de lignes de C alors qu'implémenter un algorithme demandrait bien plus. Si ça vous plait d'implémenter des algos de tris c'est votre problème, mais je ne vois pas l'intérêt de passer une journée ou plus à développer ce qui peut être fait en une heure peinard. Ceci dit, développez un tri sur les listes chaînées en implémentant un algo et venez comparer ce que l'on peut faire avec qsort(), il n'est pas certain que vous gagniez une micro-seconde de CPU chaque année, il me semble clair que vous y passeriez un certain temps.
Richard Delorme
Richard Delorme wrote:
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à boire. Adapter les structures de données à qsort doit sans doute être aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce que le web regorge d'exemples déjà écrit) de novo un algorithme de tri.
Je ne suis pas d'accord, cela doit faire une 30aine de lignes de C alors qu'implémenter un algorithme demandrait bien plus.
20 lignes pour celui ce tri par insertion (il trie des coups du meilleur au plus mauvais pour un jeu d'othello) :
pi = movelist->move->next; while ((i = pi->next) != NULL) { pj = movelist->move; do { j = pj->next; if (j->val < i->val) { pj->next = i; pi->next = i->next; i->next = j; i = pi; break; } pj = j; } while (pj != pi); pi = i; } }
Ceci dit, développez un tri sur les listes chaînées en implémentant un algo et venez comparer ce que l'on peut faire avec qsort(), il n'est pas certain que vous gagniez une micro-seconde de CPU chaque année, il me semble clair que vous y passeriez un certain temps.
La fonction que j'ai écrite ci-dessus est appelée des centaines de milliers de fois chaque seconde par un programme qui tourne 24 heures sur 24, 7 jours sur 7. Par rapport à qsort, le gain CPU est de plusieurs mois chaque année.
-- Richard
Richard Delorme wrote:
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à
boire. Adapter les structures de données à qsort doit sans doute être
aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce
que le web regorge d'exemples déjà écrit) de novo un algorithme de
tri.
Je ne suis pas d'accord, cela doit faire une 30aine de lignes de C alors
qu'implémenter un algorithme demandrait bien plus.
20 lignes pour celui ce tri par insertion (il trie des coups du meilleur
au plus mauvais pour un jeu d'othello) :
pi = movelist->move->next;
while ((i = pi->next) != NULL) {
pj = movelist->move;
do {
j = pj->next;
if (j->val < i->val) {
pj->next = i;
pi->next = i->next;
i->next = j;
i = pi;
break;
}
pj = j;
} while (pj != pi);
pi = i;
}
}
Ceci dit, développez un tri sur les listes chaînées en implémentant un
algo et venez comparer ce que l'on peut faire avec qsort(), il n'est
pas certain que vous gagniez une micro-seconde de CPU chaque année, il
me semble clair que vous y passeriez un certain temps.
La fonction que j'ai écrite ci-dessus est appelée des centaines de
milliers de fois chaque seconde par un programme qui tourne 24 heures
sur 24, 7 jours sur 7. Par rapport à qsort, le gain CPU est de plusieurs
mois chaque année.
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à boire. Adapter les structures de données à qsort doit sans doute être aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce que le web regorge d'exemples déjà écrit) de novo un algorithme de tri.
Je ne suis pas d'accord, cela doit faire une 30aine de lignes de C alors qu'implémenter un algorithme demandrait bien plus.
20 lignes pour celui ce tri par insertion (il trie des coups du meilleur au plus mauvais pour un jeu d'othello) :
pi = movelist->move->next; while ((i = pi->next) != NULL) { pj = movelist->move; do { j = pj->next; if (j->val < i->val) { pj->next = i; pi->next = i->next; i->next = j; i = pi; break; } pj = j; } while (pj != pi); pi = i; } }
Ceci dit, développez un tri sur les listes chaînées en implémentant un algo et venez comparer ce que l'on peut faire avec qsort(), il n'est pas certain que vous gagniez une micro-seconde de CPU chaque année, il me semble clair que vous y passeriez un certain temps.
La fonction que j'ai écrite ci-dessus est appelée des centaines de milliers de fois chaque seconde par un programme qui tourne 24 heures sur 24, 7 jours sur 7. Par rapport à qsort, le gain CPU est de plusieurs mois chaque année.
-- Richard
Charlie Gordon
"Richard Delorme" wrote in message news:4324794b$0$303$
Richard Delorme wrote:
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à boire. Adapter les structures de données à qsort doit sans doute être aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce que le web regorge d'exemples déjà écrit) de novo un algorithme de tri.
Je ne suis pas d'accord, cela doit faire une 30aine de lignes de C alors qu'implémenter un algorithme demandrait bien plus.
20 lignes pour celui ce tri par insertion (il trie des coups du meilleur au plus mauvais pour un jeu d'othello) :
pi = movelist->move->next; while ((i = pi->next) != NULL) { pj = movelist->move; do { j = pj->next; if (j->val < i->val) { pj->next = i; pi->next = i->next; i->next = j; i = pi; break; } pj = j; } while (pj != pi); pi = i; } }
Ceci dit, développez un tri sur les listes chaînées en implémentant un algo et venez comparer ce que l'on peut faire avec qsort(), il n'est pas certain que vous gagniez une micro-seconde de CPU chaque année, il me semble clair que vous y passeriez un certain temps.
La fonction que j'ai écrite ci-dessus est appelée des centaines de milliers de fois chaque seconde par un programme qui tourne 24 heures sur 24, 7 jours sur 7. Par rapport à qsort, le gain CPU est de plusieurs mois chaque année.
Cela dépend énormément des données : ton algorithme a une complexité quadratique, ce qui signifie qu'il prend un temps proportionnel au carré de la longueur de la liste, le cas le pire étant celui de la liste déjà triée (!). En revanche la complexité de qsort est n * log(n) ce qui est bien plus favorable pour des valeurs de n suffisamment grandes. Quelle est en moyenne la taille de tes listes ?
Note de plus que ton implémentation plante si la liste est vide. La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus efficace. Enfin il est facile d'accélérer le cas pathologique de la liste déjà partiellement ou totalement triée.
pi = movelist->move->next; if (pi == NULL) return; for (; (i = pi->next) != NULL; pi = i) { if (i->val >= pi->val) continue; for (pj = movelist->move; (j = pj->next) != i; pj = j) { if (j->val < i->val) { pj->next = i; pi->next = i->next; i->next = j; i = pi; break; } } } }
A toi de voir si cela change les performances.
Chqrlie.
"Richard Delorme" <abulmo@nospam.fr> wrote in message
news:4324794b$0$303$7a628cd7@news.club-internet.fr...
Richard Delorme wrote:
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à
boire. Adapter les structures de données à qsort doit sans doute être
aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce
que le web regorge d'exemples déjà écrit) de novo un algorithme de
tri.
Je ne suis pas d'accord, cela doit faire une 30aine de lignes de C alors
qu'implémenter un algorithme demandrait bien plus.
20 lignes pour celui ce tri par insertion (il trie des coups du meilleur
au plus mauvais pour un jeu d'othello) :
pi = movelist->move->next;
while ((i = pi->next) != NULL) {
pj = movelist->move;
do {
j = pj->next;
if (j->val < i->val) {
pj->next = i;
pi->next = i->next;
i->next = j;
i = pi;
break;
}
pj = j;
} while (pj != pi);
pi = i;
}
}
Ceci dit, développez un tri sur les listes chaînées en implémentant un
algo et venez comparer ce que l'on peut faire avec qsort(), il n'est
pas certain que vous gagniez une micro-seconde de CPU chaque année, il
me semble clair que vous y passeriez un certain temps.
La fonction que j'ai écrite ci-dessus est appelée des centaines de
milliers de fois chaque seconde par un programme qui tourne 24 heures
sur 24, 7 jours sur 7. Par rapport à qsort, le gain CPU est de plusieurs
mois chaque année.
Cela dépend énormément des données : ton algorithme a une complexité
quadratique, ce qui signifie qu'il prend un temps proportionnel au carré de la
longueur de la liste, le cas le pire étant celui de la liste déjà triée (!). En
revanche la complexité de qsort est n * log(n) ce qui est bien plus favorable
pour des valeurs de n suffisamment grandes. Quelle est en moyenne la taille de
tes listes ?
Note de plus que ton implémentation plante si la liste est vide.
La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus
efficace.
Enfin il est facile d'accélérer le cas pathologique de la liste déjà
partiellement ou totalement triée.
"Richard Delorme" wrote in message news:4324794b$0$303$
Richard Delorme wrote:
Ecrire un algorithme de tri en C, ce n'est quand même pas la mer à boire. Adapter les structures de données à qsort doit sans doute être aussi compliqué (en nombre de lignes) que réécrire (ou recopier parce que le web regorge d'exemples déjà écrit) de novo un algorithme de tri.
Je ne suis pas d'accord, cela doit faire une 30aine de lignes de C alors qu'implémenter un algorithme demandrait bien plus.
20 lignes pour celui ce tri par insertion (il trie des coups du meilleur au plus mauvais pour un jeu d'othello) :
pi = movelist->move->next; while ((i = pi->next) != NULL) { pj = movelist->move; do { j = pj->next; if (j->val < i->val) { pj->next = i; pi->next = i->next; i->next = j; i = pi; break; } pj = j; } while (pj != pi); pi = i; } }
Ceci dit, développez un tri sur les listes chaînées en implémentant un algo et venez comparer ce que l'on peut faire avec qsort(), il n'est pas certain que vous gagniez une micro-seconde de CPU chaque année, il me semble clair que vous y passeriez un certain temps.
La fonction que j'ai écrite ci-dessus est appelée des centaines de milliers de fois chaque seconde par un programme qui tourne 24 heures sur 24, 7 jours sur 7. Par rapport à qsort, le gain CPU est de plusieurs mois chaque année.
Cela dépend énormément des données : ton algorithme a une complexité quadratique, ce qui signifie qu'il prend un temps proportionnel au carré de la longueur de la liste, le cas le pire étant celui de la liste déjà triée (!). En revanche la complexité de qsort est n * log(n) ce qui est bien plus favorable pour des valeurs de n suffisamment grandes. Quelle est en moyenne la taille de tes listes ?
Note de plus que ton implémentation plante si la liste est vide. La boucle do/while n'a aucun intérêt : une boucle while ou for serait plus efficace. Enfin il est facile d'accélérer le cas pathologique de la liste déjà partiellement ou totalement triée.
pi = movelist->move->next; if (pi == NULL) return; for (; (i = pi->next) != NULL; pi = i) { if (i->val >= pi->val) continue; for (pj = movelist->move; (j = pj->next) != i; pj = j) { if (j->val < i->val) { pj->next = i; pi->next = i->next; i->next = j; i = pi; break; } } } }
A toi de voir si cela change les performances.
Chqrlie.
Harpo
Richard Delorme wrote:
20 lignes pour celui ce tri par insertion
Oui, il n'est pas très aéré et il est adapté à une structure particulière, un ordre de tri figé etc.
(il trie des coups du meilleur au plus mauvais pour un jeu d'othello) :
(...)
La fonction que j'ai écrite ci-dessus est appelée des centaines de milliers de fois chaque seconde par un programme qui tourne 24 heures sur 24, 7 jours sur 7.
Vous jouez trop à othello.
Par rapport à qsort, le gain CPU est de plusieurs mois chaque année.
Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les listes qui font 1 ou 2 éléments.
Richard Delorme wrote:
20 lignes pour celui ce tri par insertion
Oui, il n'est pas très aéré et il est adapté à une structure
particulière, un ordre de tri figé etc.
(il trie des coups du
meilleur au plus mauvais pour un jeu d'othello) :
(...)
La fonction que j'ai écrite ci-dessus est appelée des centaines de
milliers de fois chaque seconde par un programme qui tourne 24 heures
sur 24, 7 jours sur 7.
Vous jouez trop à othello.
Par rapport à qsort, le gain CPU est de
plusieurs mois chaque année.
Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les
listes qui font 1 ou 2 éléments.
Oui, il n'est pas très aéré et il est adapté à une structure particulière, un ordre de tri figé etc.
(il trie des coups du meilleur au plus mauvais pour un jeu d'othello) :
(...)
La fonction que j'ai écrite ci-dessus est appelée des centaines de milliers de fois chaque seconde par un programme qui tourne 24 heures sur 24, 7 jours sur 7.
Vous jouez trop à othello.
Par rapport à qsort, le gain CPU est de plusieurs mois chaque année.
Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les listes qui font 1 ou 2 éléments.
Charlie Gordon
"Harpo" wrote in message news:4324c20f$0$20167$
Richard Delorme wrote:
20 lignes pour celui ce tri par insertion
Oui, il n'est pas très aéré et il est adapté à une structure particulière, un ordre de tri figé etc.
cela ne serait pas difficile à generaliser avec un pointeur de fonction de comparaison.
La fonction que j'ai écrite ci-dessus est appelée des centaines de milliers de fois chaque seconde par un programme qui tourne 24 heures sur 24, 7 jours sur 7.
Vous jouez trop à othello.
A moins qu'il ne s'agisse d'une boucle infinie ;-)
Par rapport à qsort, le gain CPU est de plusieurs mois chaque année.
Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les listes qui font 1 ou 2 éléments.
Non, c'est effectivement un tri par insertion (complexité n^2), nettement plus efficace que bubble sort (n^3 ?), mais moins que qsort (n.log(n)), mergesort(n.log(n)) et que le tri par distribution (n). Ce dernier etant peut-être applicable dans ce cas précis, quelles sont les valeurs possibles de val dans des elements de liste ?
-- Chqrlie.
"Harpo" <trashcan@hotmail.com> wrote in message
news:4324c20f$0$20167$8fcfb975@news.wanadoo.fr...
Richard Delorme wrote:
20 lignes pour celui ce tri par insertion
Oui, il n'est pas très aéré et il est adapté à une structure
particulière, un ordre de tri figé etc.
cela ne serait pas difficile à generaliser avec un pointeur de fonction de
comparaison.
La fonction que j'ai écrite ci-dessus est appelée des centaines de
milliers de fois chaque seconde par un programme qui tourne 24 heures
sur 24, 7 jours sur 7.
Vous jouez trop à othello.
A moins qu'il ne s'agisse d'une boucle infinie ;-)
Par rapport à qsort, le gain CPU est de
plusieurs mois chaque année.
Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les
listes qui font 1 ou 2 éléments.
Non, c'est effectivement un tri par insertion (complexité n^2), nettement plus
efficace que bubble sort (n^3 ?), mais moins que qsort (n.log(n)),
mergesort(n.log(n)) et que le tri par distribution (n). Ce dernier etant
peut-être applicable dans ce cas précis, quelles sont les valeurs possibles de
val dans des elements de liste ?
Oui, il n'est pas très aéré et il est adapté à une structure particulière, un ordre de tri figé etc.
cela ne serait pas difficile à generaliser avec un pointeur de fonction de comparaison.
La fonction que j'ai écrite ci-dessus est appelée des centaines de milliers de fois chaque seconde par un programme qui tourne 24 heures sur 24, 7 jours sur 7.
Vous jouez trop à othello.
A moins qu'il ne s'agisse d'une boucle infinie ;-)
Par rapport à qsort, le gain CPU est de plusieurs mois chaque année.
Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les listes qui font 1 ou 2 éléments.
Non, c'est effectivement un tri par insertion (complexité n^2), nettement plus efficace que bubble sort (n^3 ?), mais moins que qsort (n.log(n)), mergesort(n.log(n)) et que le tri par distribution (n). Ce dernier etant peut-être applicable dans ce cas précis, quelles sont les valeurs possibles de val dans des elements de liste ?
-- Chqrlie.
Jean-Marc Bourguet
"Charlie Gordon" writes:
Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les listes qui font 1 ou 2 éléments.
En pratique le bubble sort (ou le shaker sort qui est une variante) est bien adapte aux cas ou les donnees sont quasiment triees: il peut avoir un comportement en n sous certaines conditions alors qu'un quick sort -- mal implemente -- peut meme exhiber un comportement quadratique . Un bon professionnel -- puisque le terme a ete lance -- va donc l'utiliser dans certains cas.
Non, c'est effectivement un tri par insertion (complexité n^2), nettement plus efficace que bubble sort (n^3 ?),
bubble sort est aussi du n^2 (facile a montrer: a chaque passe au moins un element en plus est a sa place terminale)
mais moins que qsort (n.log(n)),
qsort c'est difficile a dire, il n'y a pas de contrainte. L'implementation classique est un quick sort qui a une complexite quadratique egalement dans le pire cas (attention, suivant la maniere de choisir le pivot, et les caracteristiques des donnees, le pire cas peut arriver de maniere certaine dans des cas courants) mais n log n en moyenne. J'ai deja vu decrite des implementations recourant au heap sort (garanti n log n -- mais avec une constante relativement mauvaise) si elles remarquent que la recursion a l'air de prendre un mauvais bout.
A+
-- Jean-Marc FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc Site de usenet-fr: http://www.usenet-fr.news.eu.org
"Charlie Gordon" <news@chqrlie.org> writes:
Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les
listes qui font 1 ou 2 éléments.
En pratique le bubble sort (ou le shaker sort qui est une variante)
est bien adapte aux cas ou les donnees sont quasiment triees: il peut
avoir un comportement en n sous certaines conditions alors qu'un quick
sort -- mal implemente -- peut meme exhiber un comportement
quadratique . Un bon professionnel -- puisque le terme a ete lance --
va donc l'utiliser dans certains cas.
Non, c'est effectivement un tri par insertion (complexité n^2),
nettement plus efficace que bubble sort (n^3 ?),
bubble sort est aussi du n^2 (facile a montrer: a chaque passe au
moins un element en plus est a sa place terminale)
mais moins que qsort (n.log(n)),
qsort c'est difficile a dire, il n'y a pas de contrainte.
L'implementation classique est un quick sort qui a une complexite
quadratique egalement dans le pire cas (attention, suivant la maniere
de choisir le pivot, et les caracteristiques des donnees, le pire cas
peut arriver de maniere certaine dans des cas courants) mais n log n
en moyenne. J'ai deja vu decrite des implementations recourant au
heap sort (garanti n log n -- mais avec une constante relativement
mauvaise) si elles remarquent que la recursion a l'air de prendre un
mauvais bout.
A+
--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org
Ca ressemble à un bubble sort, c'est un excellent algo de tri pour les listes qui font 1 ou 2 éléments.
En pratique le bubble sort (ou le shaker sort qui est une variante) est bien adapte aux cas ou les donnees sont quasiment triees: il peut avoir un comportement en n sous certaines conditions alors qu'un quick sort -- mal implemente -- peut meme exhiber un comportement quadratique . Un bon professionnel -- puisque le terme a ete lance -- va donc l'utiliser dans certains cas.
Non, c'est effectivement un tri par insertion (complexité n^2), nettement plus efficace que bubble sort (n^3 ?),
bubble sort est aussi du n^2 (facile a montrer: a chaque passe au moins un element en plus est a sa place terminale)
mais moins que qsort (n.log(n)),
qsort c'est difficile a dire, il n'y a pas de contrainte. L'implementation classique est un quick sort qui a une complexite quadratique egalement dans le pire cas (attention, suivant la maniere de choisir le pivot, et les caracteristiques des donnees, le pire cas peut arriver de maniere certaine dans des cas courants) mais n log n en moyenne. J'ai deja vu decrite des implementations recourant au heap sort (garanti n log n -- mais avec une constante relativement mauvaise) si elles remarquent que la recursion a l'air de prendre un mauvais bout.
A+
-- Jean-Marc FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc Site de usenet-fr: http://www.usenet-fr.news.eu.org
Jean-Marc Bourguet
Zorro writes:
Zorro wrote:
Bonjour,
Je voudrais trier man qsort
qsort() directement avec une liste chainé? on sent le professionel..
Pourquoi pas? On va garder uniquement les cles et les pointeurs vers l'enregistrement en batissant le tableau, resultat: les donnees sont bien compacte, sans risque de resonnance dans le cache si on s'y prend bien. C'est nettement mieux que d'aller trasher les caches ou pire le disque.
A+
-- Jean-Marc FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc Site de usenet-fr: http://www.usenet-fr.news.eu.org
Zorro <zorro271-1@yahoo.fr> writes:
Zorro wrote:
Bonjour,
Je voudrais trier
man qsort
qsort() directement avec une liste chainé? on sent le professionel..
Pourquoi pas? On va garder uniquement les cles et les pointeurs vers
l'enregistrement en batissant le tableau, resultat: les donnees sont
bien compacte, sans risque de resonnance dans le cache si on s'y prend
bien. C'est nettement mieux que d'aller trasher les caches ou pire le
disque.
A+
--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org
qsort() directement avec une liste chainé? on sent le professionel..
Pourquoi pas? On va garder uniquement les cles et les pointeurs vers l'enregistrement en batissant le tableau, resultat: les donnees sont bien compacte, sans risque de resonnance dans le cache si on s'y prend bien. C'est nettement mieux que d'aller trasher les caches ou pire le disque.
A+
-- Jean-Marc FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc Site de usenet-fr: http://www.usenet-fr.news.eu.org
