cerhu > comp.lang.* > comp.lang.c

Arnaud Leconte (13/07/2004, 00h05)
Bonjour,

La fonction bsearch renvoit le premier element trouvé qui verifie la
clef fournit, existe t il une fonction qui rammenne l'element de plus faible
indice ?

J'en profite pour poser une question plus subjective, Qui prend le plus
de temps et dans quelle proportion :
une comparaison
une affectation
un calcul (somme, par ex)
un appel de fonction.
Est ce que le nombre, la taille des elements inlfue ?

Peux t on tracer le temps d'execution des differentes fct ? Ou au
minimum avoir une proportion temps cpu vs accés disque ?

Arnaud.
Alexandre BACQUART (13/07/2004, 01h34)
Arnaud Leconte wrote:
> Bonjour,
> J'en profite pour poser une question plus subjective, Qui prend le plus
> de temps et dans quelle proportion :
> une comparaison
> une affectation
> un calcul (somme, par ex)
> un appel de fonction.


La norme ne parle pas de ça.

Il n'y a pas de règle absolue, mais généralement, et en prenant le cas
simple des entiers, comparaison et affectation sont idem. Pour la somme
et la soustraction, ca prend aussi le même temps que les 2 premiers (en
cablé, la comparaison est une soustraction, la soustraction est une
addition). Par contre la multiplication et particulièrement la division
peuvent être lentes. Inutile de dire qu'avec des flottants sans FPU,
tous les calculs sont lents (relativement aux entiers bien-sûr). Pour
les appels de fonctions, ils sont plus couteux que des calculs d'entiers
(voire peut-être flottant avec FPU), mais aujourd'hui, je trouve que ça
reste assez négligeable (sauf peut-être dans une boucle parcourue des
millions de fois par seconde, là ça mérite réflexion). Dans tous ces
cas, si tu rajoutes une indirection, cela sera bien-sûr généralement un
poil plus lent (pointeur d'entiers, floattant ou de fonctions).

Avec les structures plus complexes, ben... devine :)

Mais il n'y a pas vraiment de règles, cela dépend souvent aussi du
contexte, de ce qui est en cache, de la façon dont le compilo va s'en
sortir pour optimiser ton code, etc... les opérations que tu cites sont
des opérations bas-niveau dont la durée est bien souvent (pour les 3
premières en tous cas) de l'ordre du cycle machine. Si la petite
différence de vitesse entre ces opérations devient un critère important
pour la performance de ton programme, il te reste à faire toi-même les
boucles en assembleur ou à revoir les parties critiques en les rendant
plus digestes pour les optimisations du compilo (mais là, c'est un
problème plus complexe).

> Est ce que le nombre, la taille des elements inlfue ?


Oui.

> Peux t on tracer le temps d'execution des differentes fct ?


Oui, on fait cela avec un profiler (je ne connais pas la traduction
française, si elle existe). Mais il faudrait déjà pour ça savoir quel
est ton environnement.
Horst Kraemer (13/07/2004, 08h43)
On Tue, 13 Jul 2004 00:05:03 +0200, "Arnaud Leconte"
<arnaud> wrote:

> Bonjour,
> La fonction bsearch renvoit le premier element trouvé qui verifie la
> clef fournit, existe t il une fonction qui rammenne l'element de plus faible
> indice ?


int comp(const void*a, const void*b);
foo array[N];
foo key;

foo *p = bsearch(&key, array, N, sizeof *array, comp);
while (p>array && comp(&key,p-1)==0) --p;
AG (13/07/2004, 09h15)
Arnaud Leconte wrote:
[..]
> Peux t on tracer le temps d'execution des differentes fct ? Ou au
> minimum avoir une proportion temps cpu vs accés disque ?
> Arnaud.

C'est le genre de mesures que donne un profiler.
Horst Kraemer (13/07/2004, 12h30)
On Tue, 13 Jul 2004 08:43:50 +0200, Horst Kraemer
<horst.kraemer> wrote:

> int comp(const void*a, const void*b);
> foo array[N];
> foo key;
> foo *p = bsearch(&key, array, N, sizeof *array, comp);
> while (p>array && comp(&key,p-1)==0) --p;


Pardon

if (p) while (p>array && comp(&key,p-1)==0) --p;
Laurent Deniau (13/07/2004, 13h47)
Horst Kraemer wrote:
> On Tue, 13 Jul 2004 08:43:50 +0200, Horst Kraemer
> <horst.kraemer> wrote:
> Pardon
> if (p) while (p>array && comp(&key,p-1)==0) --p;


vraisemblablement pas necessaire, p>array fait la meme chose.

a+, ld.
Arnaud Leconte (13/07/2004, 20h33)
Merci, mais c a peu pres ce que je fais, ce n'est pas genant si dans mon
tableau j'ai n series de 2,3 elements identiques mais si j'ai 2 3 series de
n élements identiques, je perds une grande parti de l'interet de cette
fonction non ?

Avec mes differents clients, j'aurais a peu pres toutes les representations
possibles.

Et je dois avouer que je ne sais plus comment accelerer mon programme, au
depart il prenait 2700heures en temps estimées, apres avoir optimisé les
accés disque, je suis passé a 3h. mais comme il doit tourner chaque nuit,
j'aimerais passé en deca de la barre des 2heures.

Sachant que mon tableau doit avoir en moyenne 700 / 800 élèments, et que la
fonction bsearch est appellé 4000 / 5000 fois pour chaque article et que
j'ai aproximativement 700.000 articles a traiter.

Arnaud

PS : désolé laurent pour le mail privée. fausse manip

"Laurent Deniau" <Laurent.Deniau> wrote in message
news:fu61
[..]
Horst Kraemer (13/07/2004, 20h48)
On Tue, 13 Jul 2004 13:47:07 +0200, Laurent Deniau
<Laurent.Deniau> wrote:

> Horst Kraemer wrote:
> vraisemblablement pas necessaire, p>array fait la meme chose.


peut-etre p>array fait la meme chose avec beaucoup de compilateurs -
mais selon la norme du langage C le comportement de 'p>array' est
indéfini si un des pointeurs est nul.
Dominique Baldo (13/07/2004, 20h56)
Arnaud Leconte nous disait
> Et je dois avouer que je ne sais plus comment accelerer mon programme, au
> depart il prenait 2700heures en temps estimées, apres avoir optimisé les
> accés disque, je suis passé a 3h. mais comme il doit tourner chaque nuit,
> j'aimerais passé en deca de la barre des 2heures.
> Sachant que mon tableau doit avoir en moyenne 700 / 800 élèments, et que la
> fonction bsearch est appellé 4000 / 5000 fois pour chaque article et que
> j'ai aproximativement 700.000 articles a traiter.


C'est plus un problème algorithmique qu'un problème de C

Si tu utilisais des tables de hashage ca accélèrerait sans doute les
recherches ... et vu le nombre d'articles si tu utilisait une Base de
Donnée plutot qu'un programme en C ca serait peut être plus approprié

.... mais j'ai peut être mal compris ton problème.
Arnaud Leconte (13/07/2004, 21h50)
Mon principale problème c que quoi que je fasse c une usine a gaz

J'utilise effectivement une base de donnée (oracle)
Je vais chercher les infos dans oracle,
Je les traite
et j'insere le resultat dans oracle.

Au début je pensais tout faire en PL/SQL mais quand j'ai vu la complexité de
l'algo et le nombre de calcul, me suis dit que le proC serait plus puissant,
et plus simple (C ou il est possible de faire des appel SQL grace a un
precomplilateur qui transforme le source en c)

J'ai commencé par :
diminuer le nombre de requettes sql, analyser leur coup, créer les
indexs avec les experts DBA de ma boite.
utiliser au plus possible les fonctions de recherche et de trie du
C.

Mais c encore un peu long. Il me reste deux solutions lineariser mon algo
qui est recursif. Or j'ai pas bcp de temps devant moi, et je n'ai aucune
idée de comment y arriver ou grapiller ce que je peux sur le C.

Merci pour votre aide,
Arnaud.

"Dominique Baldo" <dominiquebaldo> wrote in message
news:9b82
[..]
Arnaud Leconte (13/07/2004, 22h57)
NULL = faux dans la norme ?
ou c juste que null est supposé à 0 ?

Arnaud.

"Horst Kraemer" <horst.kraemer> wrote in message
news:8idm
[..]
Laurent Deniau (14/07/2004, 10h26)
Horst Kraemer wrote:
> On Tue, 13 Jul 2004 13:47:07 +0200, Laurent Deniau
> <Laurent.Deniau> wrote:
> peut-etre p>array fait la meme chose avec beaucoup de compilateurs -
> mais selon la norme du langage C le comportement de 'p>array' est
> indéfini si un des pointeurs est nul.


Rien trouve de tel dans 6.3.2.3 et 6.5.9.

Chapitre(s) et verset(s)?

a+, ld.
Horst Kraemer (14/07/2004, 10h26)
On Tue, 13 Jul 2004 22:57:16 +0200, "Arnaud Leconte"
<arnaud> wrote:

> NULL = faux dans la norme ?
> ou c juste que null est supposé à 0 ?


Tu parles de

if (p)

???

L'explication exacte est:

if (p)

est équivalent à

if (p!=0)

par définition de la norme.

C.a.d. la veleur de p est comparée à 0. Par un autre définition de la
norme la comparaison d'un pointeur à 0 ou à l'expressioin (void*)0 (0
peut être remplacé par une constante intégrale quelconque qui a la
valeur 0) donne le résultat 'égal` si p est un pointeur nul et
'inégal' si p pointe vers un objet 'légal`.

Cela veut donc dire que dans ton sens "NULL est faux" ou bien qu'un
pointeur nul est traité comme s'il contenait un 0.

void *p = 0;

produit un pointeur nul. Mais cela ne veut pas dire que p contient
"tous le bits 0" (bien que c'est le cas pour beaucoup de systemes,
entre eux les systemes 'PC'). C'est un astuce du langage C qui produit
assez de confusion. La structure interne d'un "pointeur nul" est
défini par le systéme (compilateur). Un pointeur nul pourrait étre
représenté p.ex. par les bits 0xFFFFFFFF. Mais le programmeur ne doit
pas connaitre cette représentation. Si un pointeur nul est représenté
par 0xFFFFFFFF, alors

void *p = 0;

affecte 'physiquement' cette valeur au pointeur. Et la comparaison

p == 0

est "vraie" dans ce système si p contient 0xFFFFFFFF.

[
On peut toujours remplacer 0 par NULL. Dans les contextes

p=0;
if(p==0);
int * p[2] = {0,0};

où un pointeur est affecté, initialisé ou comparé, les écritures 0 et
NULL sont 100% équivalentes. Donc l'usage de la macro NULL ne sert à
rien en ce qui concerne l'*effet*. Elle existe pour des raisons
historiques et elle ne sert qu'à documenter au lecteur qu'on à faire à
un pointeur. NULL est défini en principe ou bien comme 0 ou bien comme
(void*)0. Mais cette définition ne dit toujours rien au sujet de la
"vraie" valeur d'un pointeur nul. Elle pourrait toujours être
0xFFFFFFFF.
]
Laurent Deniau (14/07/2004, 10h50)
Laurent Deniau wrote:
> Horst Kraemer wrote:
> Rien trouve de tel dans 6.3.2.3 et 6.5.9.


Oups 6.5.8 pas 6.5.9
Horst Kraemer (14/07/2004, 11h10)
On Wed, 14 Jul 2004 10:26:21 +0200, Laurent Deniau
<Laurent.Deniau> wrote:

> Horst Kraemer wrote:
> Rien trouve de tel dans 6.3.2.3 et 6.5.9.


> Chapitre(s) et verset(s)?


C'est un peu caché derrière la terminologie;-) La norme exique que les
pointeurs qu'on compare par < <= > >= soient des pointeurs vers des
*objets* qui pointent dans le même *tableau* ou bien vers la position
n+1 si n est la taille tu tableau. Un pointeur nul ne pointe pas vers
un objet. Tout ce que la norme ne permet pas littéralement ou dont
elle n'explique pas l'effet (en disant p.ex. que le résultat est
défini par l'implémentation ou qu'il est indéterminé) a un
comportement indéfini.

Discussions similaires
Problème avec bsearch()

Retour de la fonction bsearch

Exception avec bsearch

Personne ne sait pour l'exception de bsearch ?


Fuseau horaire GMT +2. Il est actuellement 12h11. | Privacy Policy