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 ?
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 ?
Je ne comprends pas. bsearch retourne un pointeur vers l'element 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:
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 ?
Je ne comprends pas. bsearch retourne un pointeur vers l'element 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
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 ?
Je ne comprends pas. bsearch retourne un pointeur vers l'element 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
Pierre Maurette
candide, le 01/10/2008 a écrit :
Bonjour,
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 ?
?? Vous ne confondriez pas le retour de bsearch(), un void* pointant vers l'élément ou un élément trouvé, ou (void*) si pas trouvé, et le prototype de la fonction de comparaison à fournir à bsearch() ?
-- Pierre Maurette
candide, le 01/10/2008 a écrit :
Bonjour,
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 ?
??
Vous ne confondriez pas le retour de bsearch(), un void* pointant vers
l'élément ou un élément trouvé, ou (void*) si pas trouvé, et le
prototype de la fonction de comparaison à fournir à bsearch() ?
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 ?
?? Vous ne confondriez pas le retour de bsearch(), un void* pointant vers l'élément ou un élément trouvé, ou (void*) si pas trouvé, et le prototype de la fonction de comparaison à fournir à bsearch() ?
-- Pierre Maurette
Pierre Maurette
(supersedes )
candide, le 01/10/2008 a écrit :
Bonjour,
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 ?
?? Vous ne confondriez pas le retour de bsearch(), un void* pointant vers l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le prototype de la fonction de comparaison à fournir à bsearch() ?
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 ?
??
Vous ne confondriez pas le retour de bsearch(), un void* pointant vers
l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le
prototype de la fonction de comparaison à fournir à bsearch() ?
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 ?
?? Vous ne confondriez pas le retour de bsearch(), un void* pointant vers l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le prototype de la fonction de comparaison à fournir à bsearch() ?
-- Pierre Maurette
candide
Pierre Maurette a écrit :
?? Vous ne confondriez pas le retour de bsearch(), un void* pointant vers l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le prototype de la fonction de comparaison à fournir à bsearch() ?
Non, je ne confonds pas. La réponse de bsearch est binaire dans la mesure où si la clé n'est pas trouvée elle renvoie NULL et elle renvoie la position de la clé dans le cas inverse.
Mais dans la pratique, ainsi au hasard :
*) exemple 1 : on a une grande liste de nombres premiers et on eut l'utiliser pour écrire une fonction nextPrime ;
*) exemple 2 : on veut écrire un solveur de Boggle
quand on a une liste triée, on cherche souvent non pas à savoir si la clé est ou pas dans la liste mais à connaitre le ou les voisins immédiats de la clé. Pour répondre à cette question, on doit faire exactement ce que fait l'algorithme bsearch (en supposant qu'il s'agisse d'une recherche dichotomique ce que d'ailleurs la norme n'impose pas) donc le potentiel de l'implémentation bsearch n'est pas exploité. Ce n'est même pas que l'interface soit à reprendre, c'est plutôt le retour de bsearch qui ne me convient pas.
Pierre Maurette a écrit :
??
Vous ne confondriez pas le retour de bsearch(), un void* pointant vers
l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le
prototype de la fonction de comparaison à fournir à bsearch() ?
Non, je ne confonds pas. La réponse de bsearch est binaire dans la
mesure où si la clé n'est pas trouvée elle renvoie NULL et elle renvoie
la position de la clé dans le cas inverse.
Mais dans la pratique, ainsi au hasard :
*) exemple 1 : on a une grande liste de nombres premiers et on eut
l'utiliser pour écrire une fonction nextPrime ;
*) exemple 2 : on veut écrire un solveur de Boggle
quand on a une liste triée, on cherche souvent non pas à savoir si la
clé est ou pas dans la liste mais à connaitre le ou les voisins
immédiats de la clé. Pour répondre à cette question, on doit faire
exactement ce que fait l'algorithme bsearch (en supposant qu'il s'agisse
d'une recherche dichotomique ce que d'ailleurs la norme n'impose pas)
donc le potentiel de l'implémentation bsearch n'est pas exploité. Ce
n'est même pas que l'interface soit à reprendre, c'est plutôt le retour
de bsearch qui ne me convient pas.
?? Vous ne confondriez pas le retour de bsearch(), un void* pointant vers l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le prototype de la fonction de comparaison à fournir à bsearch() ?
Non, je ne confonds pas. La réponse de bsearch est binaire dans la mesure où si la clé n'est pas trouvée elle renvoie NULL et elle renvoie la position de la clé dans le cas inverse.
Mais dans la pratique, ainsi au hasard :
*) exemple 1 : on a une grande liste de nombres premiers et on eut l'utiliser pour écrire une fonction nextPrime ;
*) exemple 2 : on veut écrire un solveur de Boggle
quand on a une liste triée, on cherche souvent non pas à savoir si la clé est ou pas dans la liste mais à connaitre le ou les voisins immédiats de la clé. Pour répondre à cette question, on doit faire exactement ce que fait l'algorithme bsearch (en supposant qu'il s'agisse d'une recherche dichotomique ce que d'ailleurs la norme n'impose pas) donc le potentiel de l'implémentation bsearch n'est pas exploité. Ce n'est même pas que l'interface soit à reprendre, c'est plutôt le retour de bsearch qui ne me convient pas.
Marc Boyer
On 2008-10-01, candide wrote:
Pierre Maurette a écrit :
Vous ne confondriez pas le retour de bsearch(), un void* pointant vers l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le prototype de la fonction de comparaison à fournir à bsearch() ?
Non, je ne confonds pas. La réponse de bsearch est binaire dans la mesure où si la clé n'est pas trouvée elle renvoie NULL et elle renvoie la position de la clé dans le cas inverse.
Mais dans la pratique, ainsi au hasard :
*) exemple 1 : on a une grande liste de nombres premiers et on eut l'utiliser pour écrire une fonction nextPrime ;
*) exemple 2 : on veut écrire un solveur de Boggle
quand on a une liste triée, on cherche souvent non pas à savoir si la clé est ou pas dans la liste mais à connaitre le ou les voisins immédiats de la clé.
Sauf que bsearch ne travaille pas avec des listes, 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...
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
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:
Pierre Maurette a écrit :
Vous ne confondriez pas le retour de bsearch(), un void* pointant vers
l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le
prototype de la fonction de comparaison à fournir à bsearch() ?
Non, je ne confonds pas. La réponse de bsearch est binaire dans la
mesure où si la clé n'est pas trouvée elle renvoie NULL et elle renvoie
la position de la clé dans le cas inverse.
Mais dans la pratique, ainsi au hasard :
*) exemple 1 : on a une grande liste de nombres premiers et on eut
l'utiliser pour écrire une fonction nextPrime ;
*) exemple 2 : on veut écrire un solveur de Boggle
quand on a une liste triée, on cherche souvent non pas à savoir si la
clé est ou pas dans la liste mais à connaitre le ou les voisins
immédiats de la clé.
Sauf que bsearch ne travaille pas avec des listes, 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...
D'ailleurs, une recherche dichotomique dans une liste, ça
va être dur...
Marc Boyer
--
Si tu peux supporter d'entendre tes paroles
Travesties par des gueux pour exciter des sots
IF -- Rudyard Kipling (Trad. André Maurois)
Vous ne confondriez pas le retour de bsearch(), un void* pointant vers l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le prototype de la fonction de comparaison à fournir à bsearch() ?
Non, je ne confonds pas. La réponse de bsearch est binaire dans la mesure où si la clé n'est pas trouvée elle renvoie NULL et elle renvoie la position de la clé dans le cas inverse.
Mais dans la pratique, ainsi au hasard :
*) exemple 1 : on a une grande liste de nombres premiers et on eut l'utiliser pour écrire une fonction nextPrime ;
*) exemple 2 : on veut écrire un solveur de Boggle
quand on a une liste triée, on cherche souvent non pas à savoir si la clé est ou pas dans la liste mais à connaitre le ou les voisins immédiats de la clé.
Sauf que bsearch ne travaille pas avec des listes, 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...
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Marc Boyer -- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. André Maurois)
Jean-Marc Bourguet
Marc Boyer writes:
On 2008-10-01, candide wrote: > Pierre Maurette a écrit : > >> Vous ne confondriez pas le retour de bsearch(), un void* pointant vers >> l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le >> prototype de la fonction de comparaison à fournir à bsearch() ? > > Non, je ne confonds pas. La réponse de bsearch est binaire dans la > mesure où si la clé n'est pas trouvée elle renvoie NULL et elle renvoie > la position de la clé dans le cas inverse. > > Mais dans la pratique, ainsi au hasard : > > *) exemple 1 : on a une grande liste de nombres premiers et on eut > l'utiliser pour écrire une fonction nextPrime ; > > *) exemple 2 : on veut écrire un solveur de Boggle > > quand on a une liste triée, on cherche souvent non pas à savoir si la > clé est ou pas dans la liste mais à connaitre le ou les voisins > immédiats de la clé.
Sauf que bsearch ne travaille pas avec des listes, 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...
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a std::equal_range en C++; mais il faut retourner plus qu'une simple position.
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 <Marc.Boyer@cert.onera.fr.invalid> writes:
On 2008-10-01, candide <candide@free.invalid> wrote:
> Pierre Maurette a écrit :
>
>> Vous ne confondriez pas le retour de bsearch(), un void* pointant vers
>> l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le
>> prototype de la fonction de comparaison à fournir à bsearch() ?
>
> Non, je ne confonds pas. La réponse de bsearch est binaire dans la
> mesure où si la clé n'est pas trouvée elle renvoie NULL et elle renvoie
> la position de la clé dans le cas inverse.
>
> Mais dans la pratique, ainsi au hasard :
>
> *) exemple 1 : on a une grande liste de nombres premiers et on eut
> l'utiliser pour écrire une fonction nextPrime ;
>
> *) exemple 2 : on veut écrire un solveur de Boggle
>
> quand on a une liste triée, on cherche souvent non pas à savoir si la
> clé est ou pas dans la liste mais à connaitre le ou les voisins
> immédiats de la clé.
Sauf que bsearch ne travaille pas avec des listes, 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...
D'ailleurs, une recherche dichotomique dans une liste, ça
va être dur...
Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a
std::equal_range en C++; mais il faut retourner plus qu'une simple
position.
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
On 2008-10-01, candide wrote: > Pierre Maurette a écrit : > >> Vous ne confondriez pas le retour de bsearch(), un void* pointant vers >> l'élément ou un élément trouvé, ou (void*)0 si pas trouvé, et le >> prototype de la fonction de comparaison à fournir à bsearch() ? > > Non, je ne confonds pas. La réponse de bsearch est binaire dans la > mesure où si la clé n'est pas trouvée elle renvoie NULL et elle renvoie > la position de la clé dans le cas inverse. > > Mais dans la pratique, ainsi au hasard : > > *) exemple 1 : on a une grande liste de nombres premiers et on eut > l'utiliser pour écrire une fonction nextPrime ; > > *) exemple 2 : on veut écrire un solveur de Boggle > > quand on a une liste triée, on cherche souvent non pas à savoir si la > clé est ou pas dans la liste mais à connaitre le ou les voisins > immédiats de la clé.
Sauf que bsearch ne travaille pas avec des listes, 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...
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a std::equal_range en C++; mais il faut retourner plus qu'une simple position.
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, Jean-Marc Bourguet wrote:
Marc Boyer writes:
On 2008-10-01, candide wrote: > Pierre Maurette a écrit : > > Mais dans la pratique, ainsi au hasard : > > *) exemple 1 : on a une grande liste de nombres premiers et on eut > l'utiliser pour écrire une fonction nextPrime ; > > *) exemple 2 : on veut écrire un solveur de Boggle > > quand on a une liste triée, on cherche souvent non pas à savoir si la > clé est ou pas dans la liste mais à connaitre le ou les voisins > immédiats de la clé.
Sauf que bsearch ne travaille pas avec des listes, 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...
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a std::equal_range en C++; mais il faut retourner plus qu'une simple position.
Je ne sais pas ce qu'il veut exactement, mais bon, c'est quand même pas très difficile à faire à partir de bsearch. Un coup de ++, un coup de --...
Marc -- 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, Jean-Marc Bourguet <jm@bourguet.org> wrote:
Marc Boyer <Marc.Boyer@cert.onera.fr.invalid> writes:
On 2008-10-01, candide <candide@free.invalid> wrote:
> Pierre Maurette a écrit :
>
> Mais dans la pratique, ainsi au hasard :
>
> *) exemple 1 : on a une grande liste de nombres premiers et on eut
> l'utiliser pour écrire une fonction nextPrime ;
>
> *) exemple 2 : on veut écrire un solveur de Boggle
>
> quand on a une liste triée, on cherche souvent non pas à savoir si la
> clé est ou pas dans la liste mais à connaitre le ou les voisins
> immédiats de la clé.
Sauf que bsearch ne travaille pas avec des listes, 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...
D'ailleurs, une recherche dichotomique dans une liste, ça
va être dur...
Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a
std::equal_range en C++; mais il faut retourner plus qu'une simple
position.
Je ne sais pas ce qu'il veut exactement, mais bon, c'est quand même
pas très difficile à faire à partir de bsearch. Un coup de ++, un coup de --...
Marc
--
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 wrote: > Pierre Maurette a écrit : > > Mais dans la pratique, ainsi au hasard : > > *) exemple 1 : on a une grande liste de nombres premiers et on eut > l'utiliser pour écrire une fonction nextPrime ; > > *) exemple 2 : on veut écrire un solveur de Boggle > > quand on a une liste triée, on cherche souvent non pas à savoir si la > clé est ou pas dans la liste mais à connaitre le ou les voisins > immédiats de la clé.
Sauf que bsearch ne travaille pas avec des listes, 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...
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a std::equal_range en C++; mais il faut retourner plus qu'une simple position.
Je ne sais pas ce qu'il veut exactement, mais bon, c'est quand même pas très difficile à faire à partir de bsearch. Un coup de ++, un coup de --...
Marc -- Si tu peux supporter d'entendre tes paroles Travesties par des gueux pour exciter des sots IF -- Rudyard Kipling (Trad. André Maurois)
candide
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).
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.
Je reprends l'exemple idiot déjà cité : je veux implémenter nextPrime à partir de la liste suivante
Je demande à bsearch si 50 est dans la liste, il va faire une recherche dichotomique et il va finir par voir que 50 est entre t[14] et t[15]. Mais il va me répondre NULL, ce qui est une perte d'information car s'il me répondait par exemple 15 (enfin plutôt un pointeur vers l'élément numéroté 15 du tableau des nombres premiers ci-dessus), je saurais immédiatement si 50 est dans le tableau (suffit de comparer 50 avec t[15]) mais surtout j'aurais une information beaucoup plus consistante que NULL ! je saurais que nextPrime(50)=t[15], et ça pour le même prix.
Ce que je dis là ne me parait pas bien compliqué à comprendre.
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Tu fais une fixation ou quoi ? Avant d'aller faire tes courses au supermarché, tu te fais un _tableau_ de courses ? Bon moi je fais une liste. C'est quoi une liste pour toi ? une liste chainée ? Ça reste une succession d'objets, je vois donc pas le problème.
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).
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.
Je reprends l'exemple idiot déjà cité : je veux implémenter nextPrime à
partir de la liste suivante
Je demande à bsearch si 50 est dans la liste, il va faire une recherche
dichotomique et il va finir par voir que 50 est entre t[14] et t[15].
Mais il va me répondre NULL, ce qui est une perte d'information car s'il
me répondait par exemple 15 (enfin plutôt un pointeur vers l'élément
numéroté 15 du tableau des nombres premiers ci-dessus), je saurais
immédiatement si 50 est dans le tableau (suffit de comparer 50 avec
t[15]) mais surtout j'aurais une information beaucoup plus consistante
que NULL ! je saurais que nextPrime(50)=t[15], et ça pour le même prix.
Ce que je dis là ne me parait pas bien compliqué à comprendre.
D'ailleurs, une recherche dichotomique dans une liste, ça
va être dur...
Tu fais une fixation ou quoi ? Avant d'aller faire tes courses au
supermarché, tu te fais un _tableau_ de courses ? Bon moi je fais une
liste. C'est quoi une liste pour toi ? une liste chainée ? Ça reste une
succession d'objets, je vois donc pas le problème.
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).
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.
Je reprends l'exemple idiot déjà cité : je veux implémenter nextPrime à partir de la liste suivante
Je demande à bsearch si 50 est dans la liste, il va faire une recherche dichotomique et il va finir par voir que 50 est entre t[14] et t[15]. Mais il va me répondre NULL, ce qui est une perte d'information car s'il me répondait par exemple 15 (enfin plutôt un pointeur vers l'élément numéroté 15 du tableau des nombres premiers ci-dessus), je saurais immédiatement si 50 est dans le tableau (suffit de comparer 50 avec t[15]) mais surtout j'aurais une information beaucoup plus consistante que NULL ! je saurais que nextPrime(50)=t[15], et ça pour le même prix.
Ce que je dis là ne me parait pas bien compliqué à comprendre.
D'ailleurs, une recherche dichotomique dans une liste, ça va être dur...
Tu fais une fixation ou quoi ? Avant d'aller faire tes courses au supermarché, tu te fais un _tableau_ de courses ? Bon moi je fais une liste. C'est quoi une liste pour toi ? une liste chainée ? Ça reste une succession d'objets, je vois donc pas le problème.
Jean-Marc Bourguet
Marc Boyer writes:
On 2008-10-01, Jean-Marc Bourguet wrote: > Marc Boyer writes: >> On 2008-10-01, candide wrote: >> > Pierre Maurette a écrit : >> > >> > Mais dans la pratique, ainsi au hasard : >> > >> > *) exemple 1 : on a une grande liste de nombres premiers et on eut >> > l'utiliser pour écrire une fonction nextPrime ; >> > >> > *) exemple 2 : on veut écrire un solveur de Boggle >> > >> > quand on a une liste triée, on cherche souvent non pas à savoir si la >> > clé est ou pas dans la liste mais à connaitre le ou les voisins >> > immédiats de la clé. >> >> Sauf que bsearch ne travaille pas avec des listes, 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... >> >> D'ailleurs, une recherche dichotomique dans une liste, ça >> va être dur... > > Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a > std::equal_range en C++; mais il faut retourner plus qu'une simple > position.
Je ne sais pas ce qu'il veut exactement, mais bon, c'est quand même pas très difficile à faire à partir de bsearch. Un coup de ++, un coup de --...
Si la valeur n'est pas trouvee, faire ++ et -- sur NULL, ca marche pas trop bien.
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 <Marc.Boyer@cert.onera.fr.invalid> writes:
On 2008-10-01, Jean-Marc Bourguet <jm@bourguet.org> wrote:
> Marc Boyer <Marc.Boyer@cert.onera.fr.invalid> writes:
>> On 2008-10-01, candide <candide@free.invalid> wrote:
>> > Pierre Maurette a écrit :
>> >
>> > Mais dans la pratique, ainsi au hasard :
>> >
>> > *) exemple 1 : on a une grande liste de nombres premiers et on eut
>> > l'utiliser pour écrire une fonction nextPrime ;
>> >
>> > *) exemple 2 : on veut écrire un solveur de Boggle
>> >
>> > quand on a une liste triée, on cherche souvent non pas à savoir si la
>> > clé est ou pas dans la liste mais à connaitre le ou les voisins
>> > immédiats de la clé.
>>
>> Sauf que bsearch ne travaille pas avec des listes, 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...
>>
>> D'ailleurs, une recherche dichotomique dans une liste, ça
>> va être dur...
>
> Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a
> std::equal_range en C++; mais il faut retourner plus qu'une simple
> position.
Je ne sais pas ce qu'il veut exactement, mais bon, c'est quand même
pas très difficile à faire à partir de bsearch. Un coup de ++, un coup de --...
Si la valeur n'est pas trouvee, faire ++ et -- sur NULL, ca marche pas trop
bien.
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
On 2008-10-01, Jean-Marc Bourguet wrote: > Marc Boyer writes: >> On 2008-10-01, candide wrote: >> > Pierre Maurette a écrit : >> > >> > Mais dans la pratique, ainsi au hasard : >> > >> > *) exemple 1 : on a une grande liste de nombres premiers et on eut >> > l'utiliser pour écrire une fonction nextPrime ; >> > >> > *) exemple 2 : on veut écrire un solveur de Boggle >> > >> > quand on a une liste triée, on cherche souvent non pas à savoir si la >> > clé est ou pas dans la liste mais à connaitre le ou les voisins >> > immédiats de la clé. >> >> Sauf que bsearch ne travaille pas avec des listes, 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... >> >> D'ailleurs, une recherche dichotomique dans une liste, ça >> va être dur... > > Je crois qu'il voudrait que bsearch se comporte d'une maniere similaire a > std::equal_range en C++; mais il faut retourner plus qu'une simple > position.
Je ne sais pas ce qu'il veut exactement, mais bon, c'est quand même pas très difficile à faire à partir de bsearch. Un coup de ++, un coup de --...
Si la valeur n'est pas trouvee, faire ++ et -- sur NULL, ca marche pas trop bien.
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
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.
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.
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.