Juste un avis perso : le retour de la fonction bsearch est peu exploitable.
Bien souvent, face à une liste croissante, on ne se préoccupe pas
essentiellement de savoir si un élément donné s'y trouve ou ne s'y
trouve pas, on cherche à savoir où il est placé dans la liste (et
éventuellement hors de la liste à gauche ou à droite). Or, quel que soit
l'algorithme utilisé par bsearch (recherche séquentielle ou
dichotomique), bsearch serait en mesure sans coût supplémentaire
excessif de donner cette position. Hélas bsearch se contente de donner
une réponse binaire. Et je trouve particulièrement agaçant d'avoir à me
recoder un truc aussi classique qu'une recherche dichotomique, pas vous ?
Si la valeur n'est pas trouvee, faire ++ et -- sur NULL, ca marche pas trop bien.
Ah, enfin !
Jean-Marc Bourguet
candide writes:
Jean-Marc Bourguet a écrit :
> Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a > std::equal_range en C++;
D'après la doc C++ que je viens de regarder, c'est plus ou moins ça.
> mais il faut retourner plus qu'une simple > position.
Une position suffit (l'ordre est total) après c'est une question de convention (le plus ou le plus grand, peu importe). Mais surtout, et c'est ça que j'ai du mal à comprendre, c'est que ça ne coûterait _rien de plus_ à bsearch de nous sortir cette position puisque forcément il la calcule.
Un equivalent de lower_bound ou upper_bound alors?
Ca couterait a l'utilisation normale (chez moi; j'utilise des structures plus complexes qu'un tableau trie si ce que tu desires est necessaire; note que les fonctions du C++ sont valables pour autre chose que des tableaux) un test supplementaire pour savoir si ce que bsearch retourne est un element trouve ou bien la position ou il faudrait mettre un element non trouve.
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
candide <candide@free.invalid> writes:
Jean-Marc Bourguet a écrit :
> Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a
> std::equal_range en C++;
D'après la doc C++ que je viens de regarder, c'est plus ou moins ça.
> mais il faut retourner plus qu'une simple
> position.
Une position suffit (l'ordre est total) après c'est une question de
convention (le plus ou le plus grand, peu importe). Mais surtout, et c'est
ça que j'ai du mal à comprendre, c'est que ça ne coûterait _rien de plus_ à
bsearch de nous sortir cette position puisque forcément il la calcule.
Un equivalent de lower_bound ou upper_bound alors?
Ca couterait a l'utilisation normale (chez moi; j'utilise des structures
plus complexes qu'un tableau trie si ce que tu desires est necessaire; note
que les fonctions du C++ sont valables pour autre chose que des tableaux)
un test supplementaire pour savoir si ce que bsearch retourne est un
element trouve ou bien la position ou il faudrait mettre un element non
trouve.
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
> Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a > std::equal_range en C++;
D'après la doc C++ que je viens de regarder, c'est plus ou moins ça.
> mais il faut retourner plus qu'une simple > position.
Une position suffit (l'ordre est total) après c'est une question de convention (le plus ou le plus grand, peu importe). Mais surtout, et c'est ça que j'ai du mal à comprendre, c'est que ça ne coûterait _rien de plus_ à bsearch de nous sortir cette position puisque forcément il la calcule.
Un equivalent de lower_bound ou upper_bound alors?
Ca couterait a l'utilisation normale (chez moi; j'utilise des structures plus complexes qu'un tableau trie si ce que tu desires est necessaire; note que les fonctions du C++ sont valables pour autre chose que des tableaux) un test supplementaire pour savoir si ce que bsearch retourne est un element trouve ou bien la position ou il faudrait mettre un element non trouve.
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
Marc Boyer
On 2008-10-01, candide wrote:
Marc Boyer a écrit :
Sauf que bsearch ne travaille pas avec des listes,
J'ai employé le terme de liste dans un sens informel, ça ne change rien au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà, et en C encore plus.
mais avec des tableaux, et qu'avec l'arithméique des pointeurs, quand tu as l'adresse d'une donnée (et son type), ben, t'a les voisins...
Je vois pas ce que l'arithmétique des pointeurs vient faire là-dedans. Tu n'as pas compris ma question.
Bien sûr que j'ai les voisins si bsearch répond != NULL. Mais si bsearch te renvoie NULL, c'est quoi le voisin ?????? pourtant il existe et dans sa recherche, bsearch le rencontre mais dans sa réponse, il l'ignore.
Ah, c'était ça ta demande.
Ce que je dis là ne me parait pas bien compliqué à comprendre.
Ce que tu dis dans ce message ci en effet. Mais je n'avais pas compris avec les messages précédents. Et Jean-marc non plus puisque std::range_equal ne correspond pas à ce que tu demandes.
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Tu fais une fixation ou quoi ?
Non, mais j'ai des réflexes d'informaticien.
Avant d'aller faire tes courses au supermarché, tu te fais un _tableau_ de courses ? Bon moi je fais une liste.
Oui, mais chaque domaine spécialise un certain nombre de termes. En info, une liste, c'est une liste chainée. Un truc qui va de [0,n-1] dans T (avec T un type), sans présumer de la représentation interne, on appelle plutôt ça une séquence il me semble.
C'est quoi une liste pour toi ? une liste chainée ? Ça reste une succession d'objets, je vois donc pas le problème.
Ben, le problème de faire une recherche dichotomique dans une liste.
Marc Boyer -- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. André Maurois)
On 2008-10-01, candide <candide@free.invalid> wrote:
Marc Boyer a écrit :
Sauf que bsearch ne travaille pas avec des listes,
J'ai employé le terme de liste dans un sens informel, ça ne change rien
au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au
sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà, et en C
encore plus.
mais avec des
tableaux, et qu'avec l'arithméique des pointeurs, quand tu as
l'adresse d'une donnée (et son type), ben, t'a les voisins...
Je vois pas ce que l'arithmétique des pointeurs vient faire là-dedans.
Tu n'as pas compris ma question.
Bien sûr que j'ai les voisins si bsearch répond != NULL. Mais si bsearch
te renvoie NULL, c'est quoi le voisin ?????? pourtant il existe et dans
sa recherche, bsearch le rencontre mais dans sa réponse, il l'ignore.
Ah, c'était ça ta demande.
Ce que je dis là ne me parait pas bien compliqué à comprendre.
Ce que tu dis dans ce message ci en effet. Mais je n'avais
pas compris avec les messages précédents. Et Jean-marc non plus
puisque std::range_equal ne correspond pas à ce que tu demandes.
D'ailleurs, une recherche dichotomique dans une liste, ça
va être dur...
Tu fais une fixation ou quoi ?
Non, mais j'ai des réflexes d'informaticien.
Avant d'aller faire tes courses au
supermarché, tu te fais un _tableau_ de courses ? Bon moi je fais une
liste.
Oui, mais chaque domaine spécialise un certain nombre de termes.
En info, une liste, c'est une liste chainée.
Un truc qui va de [0,n-1] dans T (avec T un type), sans présumer
de la représentation interne, on appelle plutôt ça une séquence
il me semble.
C'est quoi une liste pour toi ? une liste chainée ? Ça reste une
succession d'objets, je vois donc pas le problème.
Ben, le problème de faire une recherche dichotomique dans une
liste.
Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)
Sauf que bsearch ne travaille pas avec des listes,
J'ai employé le terme de liste dans un sens informel, ça ne change rien au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà, et en C encore plus.
mais avec des tableaux, et qu'avec l'arithméique des pointeurs, quand tu as l'adresse d'une donnée (et son type), ben, t'a les voisins...
Je vois pas ce que l'arithmétique des pointeurs vient faire là-dedans. Tu n'as pas compris ma question.
Bien sûr que j'ai les voisins si bsearch répond != NULL. Mais si bsearch te renvoie NULL, c'est quoi le voisin ?????? pourtant il existe et dans sa recherche, bsearch le rencontre mais dans sa réponse, il l'ignore.
Ah, c'était ça ta demande.
Ce que je dis là ne me parait pas bien compliqué à comprendre.
Ce que tu dis dans ce message ci en effet. Mais je n'avais pas compris avec les messages précédents. Et Jean-marc non plus puisque std::range_equal ne correspond pas à ce que tu demandes.
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Tu fais une fixation ou quoi ?
Non, mais j'ai des réflexes d'informaticien.
Avant d'aller faire tes courses au supermarché, tu te fais un _tableau_ de courses ? Bon moi je fais une liste.
Oui, mais chaque domaine spécialise un certain nombre de termes. En info, une liste, c'est une liste chainée. Un truc qui va de [0,n-1] dans T (avec T un type), sans présumer de la représentation interne, on appelle plutôt ça une séquence il me semble.
C'est quoi une liste pour toi ? une liste chainée ? Ça reste une succession d'objets, je vois donc pas le problème.
Ben, le problème de faire une recherche dichotomique dans une liste.
Marc Boyer -- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. André Maurois)
Marc Boyer
On 2008-10-01, candide wrote:
Marc Boyer a écrit :
Sauf que bsearch ne travaille pas avec des listes,
J'ai employé le terme de liste dans un sens informel, ça ne change rien au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà, et en C encore plus.
mais avec des tableaux, et qu'avec l'arithméique des pointeurs, quand tu as l'adresse d'une donnée (et son type), ben, t'a les voisins...
Je vois pas ce que l'arithmétique des pointeurs vient faire là-dedans. Tu n'as pas compris ma question.
Bien sûr que j'ai les voisins si bsearch répond != NULL. Mais si bsearch te renvoie NULL, c'est quoi le voisin ?????? pourtant il existe et dans sa recherche, bsearch le rencontre mais dans sa réponse, il l'ignore.
Ah, c'était ça ta demande.
Ce que je dis là ne me parait pas bien compliqué à comprendre.
Ce que tu dis dans ce message ci en effet. Mais je n'avais pas compris avec les messages précédents.
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Tu fais une fixation ou quoi ?
Non, mais j'ai des réflexes d'informaticien quand je suis sur fclc.
Avant d'aller faire tes courses au supermarché, tu te fais un _tableau_ de courses ? Bon moi je fais une liste.
Oui, mais chaque domaine spécialise un certain nombre de termes. En info, une liste, c'est une liste chainée. Un truc qui va de [0,n-1] dans T (avec T un type), sans présumer de la représentation interne, on appelle plutôt ça une séquence il me semble.
C'est quoi une liste pour toi ? une liste chainée ? Ça reste une succession d'objets, je vois donc pas le problème.
Ben, le problème de faire une recherche dichotomique dans une liste.
Marc Boyer -- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. André Maurois)
-- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. André Maurois)
On 2008-10-01, candide <candide@free.invalid> wrote:
Marc Boyer a écrit :
Sauf que bsearch ne travaille pas avec des listes,
J'ai employé le terme de liste dans un sens informel, ça ne change rien
au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au
sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà, et en C
encore plus.
mais avec des
tableaux, et qu'avec l'arithméique des pointeurs, quand tu as
l'adresse d'une donnée (et son type), ben, t'a les voisins...
Je vois pas ce que l'arithmétique des pointeurs vient faire là-dedans.
Tu n'as pas compris ma question.
Bien sûr que j'ai les voisins si bsearch répond != NULL. Mais si bsearch
te renvoie NULL, c'est quoi le voisin ?????? pourtant il existe et dans
sa recherche, bsearch le rencontre mais dans sa réponse, il l'ignore.
Ah, c'était ça ta demande.
Ce que je dis là ne me parait pas bien compliqué à comprendre.
Ce que tu dis dans ce message ci en effet. Mais je n'avais
pas compris avec les messages précédents.
D'ailleurs, une recherche dichotomique dans une liste, ça
va être dur...
Tu fais une fixation ou quoi ?
Non, mais j'ai des réflexes d'informaticien quand je suis
sur fclc.
Avant d'aller faire tes courses au
supermarché, tu te fais un _tableau_ de courses ? Bon moi je fais une
liste.
Oui, mais chaque domaine spécialise un certain nombre de termes.
En info, une liste, c'est une liste chainée.
Un truc qui va de [0,n-1] dans T (avec T un type), sans présumer
de la représentation interne, on appelle plutôt ça une séquence
il me semble.
C'est quoi une liste pour toi ? une liste chainée ? Ça reste une
succession d'objets, je vois donc pas le problème.
Ben, le problème de faire une recherche dichotomique dans une
liste.
Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)
Sauf que bsearch ne travaille pas avec des listes,
J'ai employé le terme de liste dans un sens informel, ça ne change rien au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà, et en C encore plus.
mais avec des tableaux, et qu'avec l'arithméique des pointeurs, quand tu as l'adresse d'une donnée (et son type), ben, t'a les voisins...
Je vois pas ce que l'arithmétique des pointeurs vient faire là-dedans. Tu n'as pas compris ma question.
Bien sûr que j'ai les voisins si bsearch répond != NULL. Mais si bsearch te renvoie NULL, c'est quoi le voisin ?????? pourtant il existe et dans sa recherche, bsearch le rencontre mais dans sa réponse, il l'ignore.
Ah, c'était ça ta demande.
Ce que je dis là ne me parait pas bien compliqué à comprendre.
Ce que tu dis dans ce message ci en effet. Mais je n'avais pas compris avec les messages précédents.
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Tu fais une fixation ou quoi ?
Non, mais j'ai des réflexes d'informaticien quand je suis sur fclc.
Avant d'aller faire tes courses au supermarché, tu te fais un _tableau_ de courses ? Bon moi je fais une liste.
Oui, mais chaque domaine spécialise un certain nombre de termes. En info, une liste, c'est une liste chainée. Un truc qui va de [0,n-1] dans T (avec T un type), sans présumer de la représentation interne, on appelle plutôt ça une séquence il me semble.
C'est quoi une liste pour toi ? une liste chainée ? Ça reste une succession d'objets, je vois donc pas le problème.
Ben, le problème de faire une recherche dichotomique dans une liste.
Marc Boyer -- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. André Maurois)
-- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. André Maurois)
candide
Jean-Marc Bourguet a écrit :
candide writes:
Jean-Marc Bourguet a écrit :
Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a std::equal_range en C++;
D'après la doc C++ que je viens de regarder, c'est plus ou moins ça.
mais il faut retourner plus qu'une simple position.
Une position suffit (l'ordre est total) après c'est une question de convention (le plus ou le plus grand, peu importe). Mais surtout, et c'est ça que j'ai du mal à comprendre, c'est que ça ne coûterait _rien de plus_ à bsearch de nous sortir cette position puisque forcément il la calcule.
Un equivalent de lower_bound ou upper_bound alors?
Oui, ça doit être ça, mais je connais pas le C++ : "life is too short ..." tu connais la suite.
Ca couterait a l'utilisation normale (chez moi; j'utilise des structures plus complexes qu'un tableau trie si ce que tu desires est necessaire; note que les fonctions du C++ sont valables pour autre chose que des tableaux) un test supplementaire pour savoir si ce que bsearch retourne est un element trouve ou bien la position ou il faudrait mettre un element non trouve.
Oui, ça couterait, un chouilla par rapport à l'exécution complète de l'algorithme et ça rapporterait pas mal.
Jean-Marc Bourguet a écrit :
candide <candide@free.invalid> writes:
Jean-Marc Bourguet a écrit :
Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a
std::equal_range en C++;
D'après la doc C++ que je viens de regarder, c'est plus ou moins ça.
mais il faut retourner plus qu'une simple
position.
Une position suffit (l'ordre est total) après c'est une question de
convention (le plus ou le plus grand, peu importe). Mais surtout, et c'est
ça que j'ai du mal à comprendre, c'est que ça ne coûterait _rien de plus_ à
bsearch de nous sortir cette position puisque forcément il la calcule.
Un equivalent de lower_bound ou upper_bound alors?
Oui, ça doit être ça, mais je connais pas le C++ : "life is too short
..." tu connais la suite.
Ca couterait a l'utilisation normale (chez moi; j'utilise des structures
plus complexes qu'un tableau trie si ce que tu desires est necessaire; note
que les fonctions du C++ sont valables pour autre chose que des tableaux)
un test supplementaire pour savoir si ce que bsearch retourne est un
element trouve ou bien la position ou il faudrait mettre un element non
trouve.
Oui, ça couterait, un chouilla par rapport à l'exécution complète de
l'algorithme et ça rapporterait pas mal.
Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a std::equal_range en C++;
D'après la doc C++ que je viens de regarder, c'est plus ou moins ça.
mais il faut retourner plus qu'une simple position.
Une position suffit (l'ordre est total) après c'est une question de convention (le plus ou le plus grand, peu importe). Mais surtout, et c'est ça que j'ai du mal à comprendre, c'est que ça ne coûterait _rien de plus_ à bsearch de nous sortir cette position puisque forcément il la calcule.
Un equivalent de lower_bound ou upper_bound alors?
Oui, ça doit être ça, mais je connais pas le C++ : "life is too short ..." tu connais la suite.
Ca couterait a l'utilisation normale (chez moi; j'utilise des structures plus complexes qu'un tableau trie si ce que tu desires est necessaire; note que les fonctions du C++ sont valables pour autre chose que des tableaux) un test supplementaire pour savoir si ce que bsearch retourne est un element trouve ou bien la position ou il faudrait mettre un element non trouve.
Oui, ça couterait, un chouilla par rapport à l'exécution complète de l'algorithme et ça rapporterait pas mal.
Jean-Marc Bourguet
candide writes:
Oui, ça couterait, un chouilla par rapport à l'exécution complète de l'algorithme et ça rapporterait pas mal.
Non seulement ca coute, mais ca complique l'utilisation.
Mais, c'est ou nos opinions different: ca ne m'aurait jamais rapporte rien du tout.
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
candide <candide@free.invalid> writes:
Oui, ça couterait, un chouilla par rapport à l'exécution complète de
l'algorithme et ça rapporterait pas mal.
Non seulement ca coute, mais ca complique l'utilisation.
Mais, c'est ou nos opinions different: ca ne m'aurait jamais rapporte rien
du tout.
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
Oui, ça couterait, un chouilla par rapport à l'exécution complète de l'algorithme et ça rapporterait pas mal.
Non seulement ca coute, mais ca complique l'utilisation.
Mais, c'est ou nos opinions different: ca ne m'aurait jamais rapporte rien du tout.
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
candide
Marc Boyer a écrit :
J'ai employé le terme de liste dans un sens informel, ça ne change rien au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà,
"Plein de choses", ça se discute parce que ça dépend du point de vue ou de la hauteur où tu te places. Un algorithme change-t-il vraiment si la structure de données est une liste ou un tableau ? Le tri par insertion ou le tri fusion s'implémentent plus facilement avec une liste certes mais il me semble que la complexité n'est pas modifiée, la liste va juste t'épargner des recopies mais les algorithmes dans leur principe restent strictement identiques. Idem quand tu travailles avec des graphes, que tu travailles avec des matrices d'adjacence ou des listes d'adjacence, l'algorithme de Dijkstra reste l'algorithme de Disjstra. Idem pour les nuances qu'on peut faire entre itératif et récursif, un DFS reste un DFS.
et en C encore plus.
De toute façon en C, la notion de liste chainée n'existe pas officiellement. Et puis un jour faudra qu'on discute des réels avantages des listes chaînées, je trouve ça souvent très couteux (multiples malloc et free faits séquentiellement).
Ben, le problème de faire une recherche dichotomique dans une liste.
Oui, d'accord, dans le sens où on n'a plus d'accès direct.
Marc Boyer a écrit :
J'ai employé le terme de liste dans un sens informel, ça ne change rien
au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au
sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà,
"Plein de choses", ça se discute parce que ça dépend du point de vue ou
de la hauteur où tu te places. Un algorithme change-t-il vraiment si la
structure de données est une liste ou un tableau ? Le tri par insertion
ou le tri fusion s'implémentent plus facilement avec une liste certes
mais il me semble que la complexité n'est pas modifiée, la liste va
juste t'épargner des recopies mais les algorithmes dans leur principe
restent strictement identiques. Idem quand tu travailles avec des
graphes, que tu travailles avec des matrices d'adjacence ou des listes
d'adjacence, l'algorithme de Dijkstra reste l'algorithme de Disjstra.
Idem pour les nuances qu'on peut faire entre itératif et récursif, un
DFS reste un DFS.
et en C
encore plus.
De toute façon en C, la notion de liste chainée n'existe pas
officiellement. Et puis un jour faudra qu'on discute des réels avantages
des listes chaînées, je trouve ça souvent très couteux (multiples malloc
et free faits séquentiellement).
Ben, le problème de faire une recherche dichotomique dans une
liste.
Oui, d'accord, dans le sens où on n'a plus d'accès direct.
J'ai employé le terme de liste dans un sens informel, ça ne change rien au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà,
"Plein de choses", ça se discute parce que ça dépend du point de vue ou de la hauteur où tu te places. Un algorithme change-t-il vraiment si la structure de données est une liste ou un tableau ? Le tri par insertion ou le tri fusion s'implémentent plus facilement avec une liste certes mais il me semble que la complexité n'est pas modifiée, la liste va juste t'épargner des recopies mais les algorithmes dans leur principe restent strictement identiques. Idem quand tu travailles avec des graphes, que tu travailles avec des matrices d'adjacence ou des listes d'adjacence, l'algorithme de Dijkstra reste l'algorithme de Disjstra. Idem pour les nuances qu'on peut faire entre itératif et récursif, un DFS reste un DFS.
et en C encore plus.
De toute façon en C, la notion de liste chainée n'existe pas officiellement. Et puis un jour faudra qu'on discute des réels avantages des listes chaînées, je trouve ça souvent très couteux (multiples malloc et free faits séquentiellement).
Ben, le problème de faire une recherche dichotomique dans une liste.
Oui, d'accord, dans le sens où on n'a plus d'accès direct.
Marc Boyer
On 2008-10-01, candide wrote:
Marc Boyer a écrit :
J'ai employé le terme de liste dans un sens informel, ça ne change rien au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà,
"Plein de choses", ça se discute parce que ça dépend du point de vue ou de la hauteur où tu te places.
Je ne connais pas tant de points de vue que cela en algorithmique.
Un algorithme change-t-il vraiment si la structure de données est une liste ou un tableau ?
Ben, une recherche par dichotomie dans un tableau, c'est O(log n), et dans une liste chainée, c'est O(n).
Le tri par insertion ou le tri fusion s'implémentent plus facilement avec une liste certes mais il me semble que la complexité n'est pas modifiée, la liste va juste t'épargner des recopies mais les algorithmes dans leur principe restent strictement identiques. Idem quand tu travailles avec des graphes, que tu travailles avec des matrices d'adjacence ou des listes d'adjacence, l'algorithme de Dijkstra reste l'algorithme de Disjstra. Idem pour les nuances qu'on peut faire entre itératif et récursif, un DFS reste un DFS.
Enumerer les cas où les différences sont faibles ne dit pas que les choses sont identiques. Dans un tableau, un acces quelconque est en O(1) et une insertion en O(n), et l'inverse pour les listes. Si un algo fait autant d'insertion que d'accès, ça donnera la même chose. De même, s'il fait des acces "en séquence" et pas d'insertion.
et en C encore plus.
De toute façon en C, la notion de liste chainée n'existe pas
Dans la norme C, non. Mais dans les programmes en C, souvent, il y en a. Idem pour des choses comme "complexité", "performance', etc.
Et puis un jour faudra qu'on discute des réels avantages des listes chaînées, je trouve ça souvent très couteux (multiples malloc et free faits séquentiellement).
Si tu veux.
Marc Boyer -- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. André Maurois)
On 2008-10-01, candide <candide@free.invalid> wrote:
Marc Boyer a écrit :
J'ai employé le terme de liste dans un sens informel, ça ne change rien
au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au
sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà,
"Plein de choses", ça se discute parce que ça dépend du point de vue ou
de la hauteur où tu te places.
Je ne connais pas tant de points de vue que cela en algorithmique.
Un algorithme change-t-il vraiment si la structure de données est
une liste ou un tableau ?
Ben, une recherche par dichotomie dans un tableau, c'est O(log n),
et dans une liste chainée, c'est O(n).
Le tri par insertion
ou le tri fusion s'implémentent plus facilement avec une liste certes
mais il me semble que la complexité n'est pas modifiée, la liste va
juste t'épargner des recopies mais les algorithmes dans leur principe
restent strictement identiques. Idem quand tu travailles avec des
graphes, que tu travailles avec des matrices d'adjacence ou des listes
d'adjacence, l'algorithme de Dijkstra reste l'algorithme de Disjstra.
Idem pour les nuances qu'on peut faire entre itératif et récursif, un
DFS reste un DFS.
Enumerer les cas où les différences sont faibles ne dit pas que
les choses sont identiques.
Dans un tableau, un acces quelconque est en O(1) et une insertion
en O(n), et l'inverse pour les listes.
Si un algo fait autant d'insertion que d'accès, ça donnera la même
chose. De même, s'il fait des acces "en séquence" et pas d'insertion.
et en C encore plus.
De toute façon en C, la notion de liste chainée n'existe pas
Dans la norme C, non. Mais dans les programmes en C, souvent, il y
en a. Idem pour des choses comme "complexité", "performance', etc.
Et puis un jour faudra qu'on discute des réels avantages
des listes chaînées, je trouve ça souvent très couteux (multiples malloc
et free faits séquentiellement).
Si tu veux.
Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)
J'ai employé le terme de liste dans un sens informel, ça ne change rien au problème, ce qui compte c'est qu'on ait une succession d'"objets" (au sens informel encore).
Et pourtant ça change plein de choses, en algorithmique déjà,
"Plein de choses", ça se discute parce que ça dépend du point de vue ou de la hauteur où tu te places.
Je ne connais pas tant de points de vue que cela en algorithmique.
Un algorithme change-t-il vraiment si la structure de données est une liste ou un tableau ?
Ben, une recherche par dichotomie dans un tableau, c'est O(log n), et dans une liste chainée, c'est O(n).
Le tri par insertion ou le tri fusion s'implémentent plus facilement avec une liste certes mais il me semble que la complexité n'est pas modifiée, la liste va juste t'épargner des recopies mais les algorithmes dans leur principe restent strictement identiques. Idem quand tu travailles avec des graphes, que tu travailles avec des matrices d'adjacence ou des listes d'adjacence, l'algorithme de Dijkstra reste l'algorithme de Disjstra. Idem pour les nuances qu'on peut faire entre itératif et récursif, un DFS reste un DFS.
Enumerer les cas où les différences sont faibles ne dit pas que les choses sont identiques. Dans un tableau, un acces quelconque est en O(1) et une insertion en O(n), et l'inverse pour les listes. Si un algo fait autant d'insertion que d'accès, ça donnera la même chose. De même, s'il fait des acces "en séquence" et pas d'insertion.
et en C encore plus.
De toute façon en C, la notion de liste chainée n'existe pas
Dans la norme C, non. Mais dans les programmes en C, souvent, il y en a. Idem pour des choses comme "complexité", "performance', etc.
Et puis un jour faudra qu'on discute des réels avantages des listes chaînées, je trouve ça souvent très couteux (multiples malloc et free faits séquentiellement).
Si tu veux.
Marc Boyer -- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. André Maurois)
candide
Jean-Marc Bourguet a écrit :
Mais, c'est ou nos opinions different: ca ne m'aurait jamais rapporte rien du tout.
Dois-je comprendre tu n'as jamais dû réimplémenter en C une recherche dichotomique pour des besoins spécifiques ?
Jean-Marc Bourguet a écrit :
Mais, c'est ou nos opinions different: ca ne m'aurait jamais rapporte rien
du tout.
Dois-je comprendre tu n'as jamais dû réimplémenter en C une recherche
dichotomique pour des besoins spécifiques ?
