Discussion :

[souviron34]

Y'a juste un truc qui m'intrigue, c'est si on a plein de valeurs très proches et que le log les rend égales (parce qu'on est sur des double). Tu risques de pas pouvoir trouver la bonne valeur.

précision double en 32 bits = 10^-17.

Si c'est un log, pour que 2 logs soient identiques il faudrait que la différence soit inférieure à 0.5 10^-17... et donc que les valeurs soient séparées par moins de 10^(0.5 10^-17)...

Là mes neurones me lâchent pour savoir ce que ça ferait de réelle différence sur les valeurs d'origine...

Quand on est dans des basses valeurs, plus la différence est petite plus l''écart est grand.. Quand on est sur des grandes (ou très grandes) valeurs, là le log écrase..

J'avais pensé améliorer encore en remplaçant les valeurs (déjà positives) par un intervalle "raisonnable" en diviisant par (max-min) et multipliant par une valeur arbitraire (la moyenne ??)..

Sinon, une indication de ce que tu dis : si je prends le log(log) et non le log, tout marche et je passe de 20 à 12 itérations pour le dernier tableau. Par contre, si je met log(log(log))), je remonte à 16 itérations... avec un résultat faux (500030). Et avec un log4, c'et pire..

Il y a donc effectivement une influence...

Maintenant, pas assez calé ni envie pour pousser ça plus loin..

À chaque itération tu élimines au moins une valeur du tableau, et t'espères en moyenne* en éliminer la moitié. C'est donc du O(N*min(N, log(M)/log(d1/d2))) ou un truc du genre. C'est donc au pire du O(N²).

Sans doute, comme le tri en quicksort..

Cependant, tu admettras qu'en partant de la moyenne et explorant de chaque côté, on a de bonnes chances que ça soit nettement plus efficace qu'un tri.... (il suffit de regarder le dernier tableau sur un millon de points : quel que soit l'ordre des points, dans mon algo ça ne changerait rien... Par contre tu passeras de log(N) à N dans le tri... Et tous les autres cas se résolvent en une seule passe, au maxi 2..)

Disons que la différence est que je n'élimine pas des extrêmes, comme l'algo cité par pseudocode, mais que j'explore le voisnage de la valeur la plus probable.. les positions possibles étant limitées dans le voisnage du centre... et à chaque fois une partie plus grande (en principe) du tableau est éliminée...qu'on se décale dans un sens ou dans l'autre...

Donc non, je "n'élimine pas une valeur". J'élimine 90% du tableau en moyenne dès la première passe..

Comme je disais dans un autre post, le pire cas serait sans doute que toutes les valeurs soient du même ordre de grandeur... Du coup, le décalage de la fenêtre dans laquelle on regarde contiendrait en moyenne le même nombre de points;.. Mais j'ai la flemme de pousser plus loin...

[pseudocode]

Disons que la différence est que je n'élimine pas des extrêmes, comme l'algo cité par pseudocode, mais que j'explore le voisnage de la valeur la plus probable.. les positions possibles étant limitées dans le voisnage du centre... et à chaque fois une partie plus grande (en principe) du tableau est éliminée...qu'on se décale dans un sens ou dans l'autre...

C'est le principe du Bucket Sort (ou plutot de sa variante Histogram sort). Ranger les valeurs dans des "Buckets" et trouver le bucket qui contient le médian est très rapide.

Le median est la valeur qui sépare l'histogramme en 2 volumes égaux. C'est à dire la valeur "m" telle que la fonction de répartition soit égale à 0.5. Il suffit donc de trouver le premier bucket tel que la somme (i=0...k) {bucket[i]} dépasse la moitié de la population.

C'est la technique qu'on utilise pour trouver le median d'intensité dans les image.

[mat1554]

rebonjour,


Voila la version finale en C# de mon algorithme

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public double determinerMedianeV9(int[] tab, out double moyenne, out int plusPetit)
{
    /*
    * On initialise nos valeurs
    */
    int Indice = 0, nPP = 0, Tempo = -1, Total = 0;
    double Med = 0;
    int MedPos = NbrElement/2, Comparant = 0;
 
    /*
    * On détermine si notre tableau est Pair ou impair
    */
    bool isPair = false;
    if (NbrElement%2 == 0)
    {
        isPair = true;
    }
 
    /*
    * On parcourt le tableau pour calculer le total et ainsi détermine la médiane.
    */
    while (Indice < NbrElement)
    {
        Total += tab[Indice];
        Comparant = 0; 
        /*
        * On parcourt le tableau avec l'indice courant pour calculer 
        * le nombre de valeur inférieur. 
        */
	    while (Comparant < NbrElement)
        {
            if (tab[Comparant] < tab[Indice])
            {
                nPP++;
            }
            Comparant++;
        }
 
        /*
        * On détermine si notre valeur est la médiane ou pas
        */
        if (!isPair)
        {
            if (nPP == MedPos)
            {
                Med = tab[Indice];
            }
        }
        else
        {
            if ((nPP == MedPos) && (Tempo == -1))
            {
                Tempo = tab[Indice];
            }
            else if ((nPP == MedPos-1) && (Tempo == -1))
            {
                Tempo = tab[Indice];
            }
            else if ((nPP == MedPos) && (Tempo > -1))
            {
                Med = (double) (Tempo+tab[Indice]) / 2;
            }
            else if ((nPP == MedPos-1) && (Tempo > -1))
            {
                Med = (double) (Tempo+tab[Indice]) / 2;
            }   
        }
        nPP = 0;
        Indice++;
    }
    /*
    * On calcul notre moyenne en fonction du total obtenu
    */
    moyenne = (double) Total / NbrElement;
 
    /*
    * On détermine maintenant le nombre de valeur inférieur à la moyenne.
    */
    plusPetit = 0;
    foreach (int E in tab)
    {
        if (E < moyenne)
        {
            plusPetit++;
        }
    }
    /*
    * On retourne maintenant la médiane
    */
    return Med;
}

Puis, la version sous forme d'algo

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
Module determinerMediane(int[] tab, out moyenne, out int plusPetit)
Indice <-- 0
Npp <--0
Tempo <--1
Total <--0
Med <--0.0

NbrElement <--Nombre d’élément du tableau
MedPos <--NbrElement/2

isPair <--faux
Si (NbrElement mod 2 = 0) alors
		isPair = true

Pour  (Indice < NbrElement)
Total <--total + tab[indice]
	Comparant <--0

	Pour (Comparant < NbrElement)
		Si (tab[Comparant] < tab[Indice]
			nPP <--nPP + 1
		comparant <--comparant + 1
	
	Si (isPair = faux)
		Si (nPP = MedPos)
			Med <--tab[Indice]
  	     Sinon
		Si (nPP = MedPos) && (Tempo = -1)
			Tempo <-- tab[indice]
		  Sinon si (nPP = MedPos-1) && (Tempo = -1)
			Tempo <-- tab[indice]
		  Sinon si (nPP = MedPos) && (Tempo > -1)
			Med <-- (Tempo + tab[Indice]) / 2
		  Sinon si (nPP = MedPos-1) && (Tempo > -1)
			Med <-- (Tempo + tab[Indice]) / 2
		Npp <--0
		Indice <--Indice + 1


Moyenne <--total / NbrElement
plusPetit <-- 0

pour chaque Element du tableau
	if (Element < Moyenne)
	       plusPetit <-- plusPetit + 1
retourner Med

Cependant, je n'ai jamais été trop fort pour calculer la vitesse d’exécution et c'est trucs là..

Je me demandais donc, comment on détermine ces 2 question la :

1. Quelle est la vitesse d’exécution de votre algorithme dans le meilleur des cas?
2. Quelle est la vitesse d’exécution de votre algorithme dans le pire cas?

Selon moi, vu que je parcours 1 fois le tableau au complet : O(n).
Puis que das ce parcours, je parcours a nouveau : O(n)
Et à la fin je parcours encore : O(n)

Donc, j'aurais 3 fois O(n³) ?

[Celelibi]

précision double en 32 bits = 10^-17.

Si c'est un log, pour que 2 logs soient identiques il faudrait que la différence soit inférieure à 0.5 10^-17... et donc que les valeurs soient séparées par moins de 10^(0.5 10^-17)...

Là mes neurones me lâchent pour savoir ce que ça ferait de réelle différence sur les valeurs d'origine...

Hum. Pour commencer les double sont sur 64 bits, même si ta machine est en 32 bits. Par définition, ce sont des flottants double précision. Et on ne peut pas caractériser la précision des flottants IEEE 745 par un simple interval.
Les flottants se basent sur une représentation "scientifique" du genre 4.321*10^42. Sauf que là c'est en binaire : 1.M * 2^E. Avec M les bits après la virgule et e l'exposant. M et E (ainsi que le signe) sont les informations stockées dans un flottant. (1.M ça veut dire "un bit à 1 avant la virgule, puis tous les bits de M après la virgule".)

Avec les double on a 52 bits de mantisse et 11 bits d'exposant.
Si l'exposant vaut 0, on a bien une précision de 10^-16, mais si l'exposant vaut 6, on n'a plus qu'une précision de 10^-10.


Bref, il se passe quoi quand on prend le log d'un nombre n de la forme n = a*2^b ? (Je vais prendre le log en base 2 parce que c'est plus simple.)
(Si les calculs sont chiants : le résultat final est un peu plus bas.)

log(n) = log(a*2^b) = log(a) + b
Et ce nombre, on essaye de l'écrire sous la forme c * 2^d.
Si n >= 1, le log est positif :
d = int(log(log(a) + b)) // = log(b) pour un n >= 2, mais je met pas la démo ici.
c = (log(a) + b) / 2^d
c = (log(a) + b) / b // si n >= 2
c = log(a) + 1

(Si 0 > n > 1, le log est négatif, et les calculs sont similaires donc je les met pas ici. Si 1 >= n > 2, alors b = 0 et les calculs sont plus simples. Et de toutes façons, tu ne prends le log que de valeurs supérieures ou égales à 1.)

Du coup, si on prend le log d'un nombre très proche, juste supérieur d'un epsilon e = 2^-x, de combien seront éloignés ces nombres après log ?
log((a+e) * 2^b) = log(a+e) + b
d' = int(log(log(a+e) + b))
c' = (log(a+e) + b) / 2^d'
c' = (log(a+e) + b) / b // si n >= 2 et a+e < 2
c' = log(a+e) / b + 1

Si a+e < 2 (ce qui est probable vu que e est petit et que 1 < a < 2), alors d' = d.
Si on calcule leur différence :
(je fais les calculs en live, y'a peut-être des erreurs et peut-être que ça ne mène à rien. :p)
delta = c' - c
delta = (log(a+e) / b + 1) - (log(a) / b + 1)
delta = log(a+e) / b - log(a) / b
delta = (log(a+e) - log(a)) / b
delta = log((a+e)/a) / b
delta = log(e/a + 1) / b
delta = e / a / b // car log(x) est approximativement x-1 au voisinage de x = 1.
delta = e / (a * b)


Et donc, si on a après l'opération log, une différence entre deux valeurs de 2^-52 (la plus petite différence qu'on peut avoir entre deux double). Quelle est la différence entre les deux valeurs avant log ?
2^-52 = delta
2^-52 = e / (a * b)
2^-52 * a * b = e
2^-52 * 2^log(a * b) = e
2^(log(a * b)-52) = e
2^(log(a)+log(b)-52) = e

Or 1 <= a < 2. Donc 0 <= log(a) < 1
Donc :
e ~ 2^(log(b)-52)


Rappelle de l'expression de départ :
(a+e) * 2^b

Résultat :
On peut interpréter ça en disant que le nombre de bit de précision qu'on perd en appliquant un log est proportionnelle au log de l'exposant du nombre.
Par exemple, en prenant le log d'une valeur autour de 2^4000, le nombre de bits de précision qui sont perdus est de 12.


(Bon, finalement je m'en suis pas trop mal sorti sur les calculs. )

Et surtout, ce qui est important de noter, c'est que ce n'est pas à ton algo de décider si une différence de 2^-52 est négligeable et peut être ignorée. Il y a des applications scientifiques dont l'erreur de précision a été minutieusement analysée et où chaque bit est important.



Cela dit, dans ton dernier algo, vu que tu élimines au moins une valeur à chaque fois, tu es au moins en O(N²), je pense que tu peux te passer de l'étape log du tableau.

Quand on est dans des basses valeurs, plus la différence est petite plus l''écart est grand.. Quand on est sur des grandes (ou très grandes) valeurs, là le log écrase..

Sauf que tu fais un log uniquement sur des valeurs supérieures à 1. Donc on ne fait qu'"écraser".

Sans doute, comme le tri en quicksort..

Le quickselect est en O(N) en moyenne. (Contrairement au tri quicksort, qui lui est en O(N*log(N)) en moyenne.) "En moyenne" signifiant qu'on suppose que les valeurs sont bien mélangées. Et il y a des variantes d'algo de sélection qui sont en O(N) dans tous les cas. Tout comme il existe des tris en O(N*log(N)) dans tous les cas.
La seule contrainte du quickselect ou ses variantes est qu'il faut trier partiellement le tableau.

Cependant, tu admettras qu'en partant de la moyenne et explorant de chaque côté, on a de bonnes chances que ça soit nettement plus efficace qu'un tri....

C'est probable, oui. Mais ce qui me dérange, c'est de ne pas savoir ce qu'est "le cas moyen" qui te permet de dire que t'as une bonne complexité "en moyenne".

[souviron34]

Hum. Pour commencer les double sont sur 64 bits, même si ta machine est en 32 bits. Par définition, ce sont des flottants double précision. Et on ne peut pas caractériser la précision des flottants IEEE 745 par un simple interval.

C'est pourtant ce qui est conceptualisé par la constante DBL_EPSILON ou FLT_EPSILON

Avec les double on a 52 bits de mantisse et 11 bits d'exposant.
Si l'exposant vaut 0, on a bien une précision de 10^-16, mais si l'exposant vaut 6, on n'a plus qu'une précision de 10^-10.
...
Résultat :
On peut interpréter ça en disant que le nombre de bit de précision qu'on perd en appliquant un log est proportionnelle au log de l'exposant du nombre.
Par exemple, en prenant le log d'une valeur autour de 2^4000, le nombre de bits de précision qui sont perdus est de 12.
...
(Bon, finalement je m'en suis pas trop mal sorti sur les calculs. )
...
Et surtout, ce qui est important de noter, c'est que ce n'est pas à ton algo de décider si une différence de 2^-52 est négligeable et peut être ignorée. Il y a des applications scientifiques dont l'erreur de précision a été minutieusement analysée et où chaque bit est important.

Je suis d'accord, mais une appli qui cherche la médiane de nombres séparés par 2^-52 sans les avoir mis dans une bonne échelle au préalalble est vouée à l'échec de toutes façons pratiquement quelles que soient les opérations qu'on fera subir aux éléments.. :qe ce soit médiane, log, additions, soustraction, division, etc etc... aie:

A part en cryptographie, je ne connais aucune appli qui manipule volontairement des chiffres réels avec ces exposants...

On se ramène toujours à une échelle correcte... Soit en mettant le 2^-52 en constante multiplicative et en ayant le tableau des facteurs, soit en ramenant à une puiiance commune et justement "médiane" ou "moyenne" du champs des valeurs possibles....

(et quand je prends tes exemples, qu'on ait 2^4000 à 12 bits près ne changerait en rien le résultat, ni même si il y avait plusieurs valeurs du même tonneau)

C'est bien la raison pour laquelle j'ai pris les logs : après ta remarque (justifiée) sur mon traitement par dichotomie sur les valeurs, je me suis dit que ce qui comptait dans le tri c'était purement une fonction croissante de ces valeurs, quelle qu'elle soit... La VALEUR de cette fonction n'é pas d'importance, du moment qu'elle est croissante, puisqu'on ne cherche pas une interpolation, mais une position...

Au début je pensais chercher la valeur médiane de l'ensemble sous-tendu par le tableau (et non pas du tableau tel quel), donc en moyenne ma "médiane" ainsi définie tombait forcément entre 2 valeurs...D'où la dichotomie sur les valeurs... Après ta remarque et une re-lecture de la définition, c'est bien une posiition dans le tableau qu'on cherche . Et dans ce cas raisonner sur le log est équivalent à raisonner sur les valeurs sous-tendues par les logs...

Cela dit, dans ton dernier algo, vu que tu élimines au moins une valeur à chaque fois, tu es au moins en O(N²), je pense que tu peux te passer de l'étape log du tableau.

Je ne crois pas : à la première étape j'élimine 50%. A la seconde 90% de ce qui reste..

Et si, le log est utile, sinon tu a les résultats du dessus (52 itérations pour le tableau 7).

C'est probable, oui. Mais ce qui me dérange, c'est de ne pas savoir ce qu'est "le cas moyen" qui te permet de dire que t'as une bonne complexité "en moyenne".

Moi ce qui me dérange c'est cette focalisation sur une valeur de compleité qui ne prend pas en compte le vrai nombre d'opérations, puisque les facteurs constants sont cachés...

Quand tu regardes l'algo, fais le tourner sur tout un tas de cas différents, et tu verras...

Pour moi la "moyenne" c'est justement l'inverse des cas particuliers (mais je suis physicien et non mathématicen ).

• Comme j'ai dit, le pire cas serait sans doute un cas où globalement tous les points seraient à moy+epsilon... (peut-être du style une sinusoide très longue, avec énormément de cycles)
  
• Le meilleur serait où valeur correspondant à moyenne = milieu direct (voir les exemples plus haut : 1 itération = meilleur cas).
  
• Un cas assez représentatif de la moyenne me semblerait donc être le dernier tableau...
  
  Si on prend 500000 points, on a 14 itérations, 1000000 on en a 20 (12 avec le lg2)... J'ai pas testé plus loin... Mais en doublant on n'augmente que de un peu moins d'1/3 le nb d'itérations.. J'ai pas ma calc scientifique, là, et j'ai pas testé plus loin.. J'essaierais demain... En sortant le plot log-log..

[souviron34]

C'est le principe du Bucket Sort (ou plutot de sa variante Histogram sort). Ranger les valeurs dans des "Buckets" et trouver le bucket qui contient le médian est très rapide.
....
C'est la technique qu'on utilise pour trouver le median d'intensité dans les image.

ça me rassure, je suis pas encore tout à fait à ranger chez les séniles Bien que je ne connaissais pas cette technique, je retrouve le raisonnement tout seul ...

[mat1554]

personne pour répondre à ma dernière question j'existe vous savez

[Celelibi]

C'est pourtant ce qui est conceptualisé par la constante DBL_EPSILON ou FLT_EPSILON

Il s'agit de la différence entre 1 et le nombre "suivant" représentable en double ou float.

Je suis d'accord, mais une appli qui cherche la médiane de nombres séparés par 2^-52 sans les avoir mis dans une bonne échelle au préalalble est vouée à l'échec de toutes façons pratiquement quelles que soient les opérations qu'on fera subir aux éléments.. :qe ce soit médiane, log, additions, soustraction, division, etc etc... aie:

La stabilité numérique de certains algo tient à quelques décimales. Il existe des outils qui aident à la preuve de ces algo (j'en connais qu'un, c'est astrée.)
Notamment les algos qui tournent pendant des heures parce qu'ils contrôlent un processus physique, ça serait dommage qu'ils divergent à cause d'un algo de calcul de médiane qui a bouffé 3 bits.

Et justement, la médiane est censée être (sur les tableaux de taille impaire) une valeur du tableau. Il n'est pas question d'opération numérique, juste de sélection d'une des valeurs. Donc on est en droit d'attendre la bonne valeur au bit près pour un calcul de médiane.

A part en cryptographie, je ne connais aucune appli qui manipule volontairement des chiffres réels avec ces exposants...

À ma connaissance, en crypto on utilise plutôt des grands entiers que des flottants.

Je ne crois pas : à la première étape j'élimine 50%. A la seconde 90% de ce qui reste..

Je disais "au moins" dans le sens "Au moins, sinon mieux" = "au pire".
Au pire c'est du O(N²) parce que tu peux n'éliminer qu'une seule valeur à la fois.

Moi ce qui me dérange c'est cette focalisation sur une valeur de compleité qui ne prend pas en compte le vrai nombre d'opérations, puisque les facteurs constants sont cachés...

Oh bien, ça peut se calculer aussi mais c'est plus chiant. :p
Mais ces facteurs c'est souvent du détail d'implémentation.

Pour moi la "moyenne" c'est justement l'inverse des cas particuliers (mais je suis physicien et non mathématicen ).

Je dois bien dire que j'ai surtout une définition intuitive de ce qu'est "le cas moyen". D'ailleurs, avis aux matheux qui passeraient par là.


Sinon, en cherchant des cas foireux (parce que j'aime ça, je devrait en faire mon métier :p), je pensais tester ça :
{-2^1000, 1, 2, 3, 4} pour que les petites valeurs soient "écrasées" par le log.

Mais en fait ça donne comme résultat 0 sur celui-là aussi :
{0, 10, 11, 12, 13}

Et je dois dire que ce soir j'ai un peu la flemme de chercher pourquoi ça foire. ^^

[Celelibi]

personne pour répondre à ma dernière question j'existe vous savez

Non, ton algo est certainement pas en O(N³).

La question à se poser c'est : la boucle qui fait le plus de tours, elle en fera combien ?

Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
for (i = 0; i < N; i++) {
    printf("boucle1\n");
 
    for (j = 0; j < N; j++) {
        printf("boucle2\n");
    }
}
 
for (i = 0; i < M; i++) {
    printf("boucle3\n");
}

Combien de fois s'affiche "boucle1" ? Combien de fois s'affiche "boucle2" ? Et "boucle3" ?

Si t'es capable de donner le nombre total de printf, tu auras la complexité de cet algo.
Et si la boucle2 avait commencé à j = i ?

[mat1554]

Autrement dis, dans mon cas. Je parcours 1 fois le tableau, mais pour chacun de ces parcours je le parcours à nouveau.

Donc O(n²). Puisque 2 fois O(n) ? Aie aie aie... moi et l'évaluation lol xD.


Sinon, je vais testé ton printf, demain et éditer mon message.

[souviron34]

Il s'agit de la différence entre 1 et le nombre "suivant" représentable en double ou float.

Pas tout à fait... Il s'agit de la différence minimale entre 2 nombres flottants..

Si on teste : if ( a = b ), on aura toujoours OUI si la différence est inférieure à ce nombre..

La stabilité numérique de certains algo tient à quelques décimales.

Tu parles bien de décimales ....

10^-52 n'est pas une décimale utilisée

J'ai déjà eu l'occasion de le démontrer dans un autre post; exprimer la taille de l'Univers an Angströms ne ferait que 35 chiffres,.... Mais n'aurait strictement aucune signification...

En tant que physicien, les "grands nombres" et autres équivalents ne sont qu'une vue de l'esprit (sauf en crypto).

Tout problème se ramène à une échelle cohérente et représentable par des doubles "normaux"... Tout algo qui ne le fait pas est absurde dans son principe...

Echelles, ordres de grandeurs, et précisions.....

Si on reprend l'exemple de l'Univers ci-dessus, oui on pourrait l'écrire en angstroms... SAUF QUE l'imprécision initiale est de la 100 aine de millions d'années-lumières... Vu qu'une année-lumière est environ 10 000 milliards de kilomètres., soit 10^13 km, c'est à dire 10^16 m, soit 10^25 angstroms, la taille de l'Univers étant en gros de 13.7 milliards d'années-lumière, soit 13.7 10^34 angstroms, l'imprécision est de 10^32.............. Il n'y a donc réellement qu'un facteur 1000 à tenir compte....

Et c'est pareil pour tous les problèmes... utiliser la bonne unité et tenir compte de la précision des données réelles...

A part en maths théoriques, des écarts de 10^-52 n'ont strictement aucune signiifcation (si ce sont des écarts).. Tout programme censé aura remis dans une échelle cohérente.... Tout prgramme utilisant des valeurs n'ayant pas de rapport avec la précision de mesure est aberrant...

Je sais que c'est à la mode d'enseigner les grands nombres et l'utilisation de bibliothèques spécialisées, mais c'est une totale absurdité, sauf en crypto...

[souviron34]

Sinon, en cherchant des cas foireux (parce que j'aime ça, je devrait en faire mon métier :p), je pensais tester ça :
{-2^1000, 1, 2, 3, 4} pour que les petites valeurs soient "écrasées" par le log.

Mais en fait ça donne comme résultat 0 sur celui-là aussi :
{0, 10, 11, 12, 13}

Et je dois dire que ce soir j'ai un peu la flemme de chercher pourquoi ça foire. ^^

J'ai trouvé, et c'est encore une fois le cas particulier où on sort du premier coup.. J'avais négligé un cas .... celui où on est sur la moyenne pile, mais où c'est asymétrique...

Bon alors voici le code corrigé :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

Resultat :

Moyenne 0.584856 et 1 iterations pour mediane
Tableau 1 mediane 2

Moyenne 0.415836 et 1 iterations pour mediane
Tableau 2 mediane 2

Moyenne 0.400515 et 1 iterations pour mediane
Tableau 3 mediane 2

Moyenne 0.345053 et 1 iterations pour mediane
Tableau 4 mediane 1.5

Moyenne 60.482 et 1 iterations pour mediane
Tableau 5 mediane 2

Moyenne 0.0752575 et 1 iterations pour mediane
Tableau 6 mediane 0

Moyenne 0.15563 et 1 iterations pour mediane
Tableau 7 mediane 2e-16

Moyenne 5.566 et 20 iterations pour mediane
Tableau 8 mediane 499998

Moyenne 0.876129 et 1 iterations pour mediane
Tableau 9 mediane 10

Moyenne 2.40191 et 1 iterations pour mediane
Tableau 10 mediane 1

Et voici un plot des tests avec 2 configurations :

D'une part une série de tableaux (1,2,3,.......k, 2^1000) (rouge), puis une série de tableaux (1,2,random entre 1 et 2, .......) (bleu).

Il y a un cas qui ne se termine jamais : quand tous les éléments ou presque sont égaux à la moyenne... (par exemple {1,2,1.5,1.5,1.5,1.5.....})

Le plot trace le nombre d'itérations en fonction du nombre de points d'entrée..

On voit donc que ça tend vers une constante (environ 27) (l'échelle est en log-log), et donc asymptotiquement O(N). ou O(N log*N)
(ou bien comme je disais plus haut O(N log(log(N) ??).


Est-ce que ça vaudrait une publication ??

.

[mat1554]

Pour mon temps d’exécution, j'ai ajouté comme tu avais dis une variable Boucle, qui contre le nombre de passage dans chacun d'elle.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
public double determinerMedianeV9(int[] tab, out double moyenne, out int plusPetit)
    {
        /*
        * On initialise nos valeurs
        */
        int Indice = 0, nPP = 0, Tempo = -1, Total = 0;
        double Med = 0;
        int MedPos = NbrElement/2, Comparant = 0;
        // Test pour vitesse éxecution
        int Boucle1 = 0;
        int Boucle2 = 0;
        int Boucle3 = 0;
 
        /*
        * On détermine si notre tableau est Pair ou impair
        */
        bool isPair = false;
        if (NbrElement%2 == 0)
        {
            isPair = true;
        }
 
        /*
        * On parcourt le tableau pour calculer le total et ainsi détermine la médiane.
        */
        while (Indice < NbrElement)
        {
            Total += tab[Indice];
            Comparant = 0; 
            // Test bouclage 1
            Boucle1++;
 
            /*
            * On parcourt le tableau avec l'indice courant pour calculer 
            * le nombre de valeur inférieur. 
            */
	        while ((Comparant < NbrElement) && (Med == 0))
            {
                // Test bouclage 2
                Boucle2++;
                if (tab[Comparant] < tab[Indice])
                {
                    nPP++;
                }
                Comparant++;
            }
 
            /*
            * On détermine si notre valeur est la médiane ou pas
            */
            if (!isPair)
            {
                if (nPP == MedPos)
                {
                    Med = tab[Indice];
                }
            }
            else
            {
                if ((nPP == MedPos) && (Tempo == -1))
                {
                    Tempo = tab[Indice];
                }
                else if ((nPP == MedPos-1) && (Tempo == -1))
                {
                    Tempo = tab[Indice];
                }
                else if ((nPP == MedPos) && (Tempo > -1))
                {
                    Med = (double) (Tempo+tab[Indice]) / 2;
                }
                else if ((nPP == MedPos-1) && (Tempo > -1))
                {
                    Med = (double) (Tempo+tab[Indice]) / 2;
                }   
            }
            nPP = 0;
            Indice++;
        }
        /*
        * On calcul notre moyenne en fonction du total obtenu
        */
        moyenne = (double) Total / NbrElement;
 
        /*
        * On détermine maintenant le nombre de valeur inférieur à la moyenne.
        */
        plusPetit = 0;
        foreach (int E in tab)
        {
            // Test bouclage 3
            Boucle3++;
            if (E < moyenne)
            {
                plusPetit++;
            }
        }
 
        // On affiche nos boucle
        System.Console.WriteLine("Boucle 1 : " + Boucle1);
        System.Console.WriteLine("Boucle 2 : " + Boucle2);
        System.Console.WriteLine("Boucle 3 : " + Boucle3);
 
        /*
        * On retourne maintenant la médiane
        */
        return Med;
    }

Le résultats de mon OUT :

Boucle 1 : 6
Boucle 2 : 24
Boucle 3 : 6

Array contains 6 elements: 1 5 2 4 8 9
=======================================================================
Moyenne : 4,83333333333333
Mediane : 4,5
Plus Petit moyenne : 3
=======================================================================

Boucle 1 : 3
Boucle 2 : 6
Boucle 3 : 3

Array contains 3 elements: 4 2 1
=======================================================================
Moyenne : 2,33333333333333
Mediane : 2
Plus Petit moyenne : 2
=======================================================================

Boucle 1 : 8
Boucle 2 : 32
Boucle 3 : 8

Array contains 8 elements: 1 9 3 7 11 32 2 1
=======================================================================
Moyenne : 8,25
Mediane : 5
Plus Petit moyenne : 5
=======================================================================

Boucle 1 : 5
Boucle 2 : 25
Boucle 3 : 5

Array contains 5 elements: 6 5 2 3 4
=======================================================================
Moyenne : 4
Mediane : 4
Plus Petit moyenne : 2
=======================================================================

Boucle 1 : 6
Boucle 2 : 36
Boucle 3 : 6

Array contains 6 elements: 9 3 6 1 7 4
=======================================================================
Moyenne : 5
Mediane : 5
Plus Petit moyenne : 3
=======================================================================

Boucle 1 : 2
Boucle 2 : 4
Boucle 3 : 2

Array contains 2 elements: 3 1
=======================================================================
Moyenne : 2
Mediane : 2
Plus Petit moyenne : 1
=======================================================================

Boucle 1 : 2
Boucle 2 : 4
Boucle 3 : 2

Array contains 2 elements: 1 7
=======================================================================
Moyenne : 4
Mediane : 4
Plus Petit moyenne : 1
=======================================================================

Boucle 1 : 3
Boucle 2 : 3
Boucle 3 : 3

Array contains 3 elements: 2 6 1
=======================================================================
Moyenne : 3
Mediane : 2
Plus Petit moyenne : 2
=======================================================================

Boucle 1 : 3
Boucle 2 : 6
Boucle 3 : 3

Array contains 3 elements: 2 4 6
=======================================================================
Moyenne : 4
Mediane : 4
Plus Petit moyenne : 1
=======================================================================

Boucle 1 : 4
Boucle 2 : 12
Boucle 3 : 4

Array contains 4 elements: 1 2 4 5
=======================================================================
Moyenne : 3
Mediane : 3
Plus Petit moyenne : 2
=======================================================================

Boucle 1 : 5
Boucle 2 : 15
Boucle 3 : 5

Array contains 5 elements: 2 4 8 16 32
=======================================================================
Moyenne : 12,4
Mediane : 8
Plus Petit moyenne : 3
=======================================================================

Boucle 1 : 1
Boucle 2 : 1
Boucle 3 : 1

Array contains 1 elements: 1
=======================================================================
Moyenne : 1
Mediane : 1
Plus Petit moyenne : 0
=======================================================================

Boucle 1 : 24
Boucle 2 : 432
Boucle 3 : 24

Array contains 24 elements: 1 2 5 66 33 22 11 88 55 4 2 6 1 1 8 2 1 8 9 2 22 36 37 21
=======================================================================
Moyenne : 18,4583333333333
Mediane : 8
Plus Petit moyenne : 15
=======================================================================

[souviron34]

En fait, c'est boucle1 et boucle2 qui comptent..

Pour chaque élément de N (boucle1) tu fais boucle2/N calculs..

Là, on voit que ta complexité est en O(N^2) avec un facteur constant variant entre 0.5 et 1:

Boucle 2 : 24
Array contains 6 elements: 1 5 2 4 8 9

Boucle 2 : 6
Array contains 3 elements: 4 2 1

Boucle 2 : 32
Array contains 8 elements: 1 9 3 7 11 32 2 1

Boucle 2 : 25
Array contains 5 elements: 6 5 2 3 4

Boucle 2 : 36
Array contains 6 elements: 9 3 6 1 7 4

Boucle 2 : 4
Array contains 2 elements: 3 1

Boucle 2 : 4
Array contains 2 elements: 1 7

Boucle 2 : 3
Array contains 3 elements: 2 6 1

Boucle 2 : 6
Array contains 3 elements: 2 4 6

Boucle 2 : 12
Array contains 4 elements: 1 2 4 5

Boucle 2 : 15
Array contains 5 elements: 2 4 8 16 32

Boucle 2 : 1
Array contains 1 elements: 1

Boucle 2 : 432
Array contains 24 elements

[mat1554]

D'Accord, merci.

En ayant 2 boucle qui sont parcouru au complet par obligation (soit #1 et #3) je me disais bien qu'elle n'était pas très importante, mais maintenant j'ai confirmation

Pire cas : O(n²) avec facteur 1
Meilleur cas : O(n²) avec facture ½.

Encore merci et bonne journée à vous.

[souviron34]

De rien

Il y a un cas qui ne se termine jamais : quand tous les éléments ou presque sont égaux à la moyenne... (par exemple {1,2,1.5,1.5,1.5,1.5.....})
.

Problème résolu : encore un cas particulier... Il faut modifier la condition d'arrêt de a "dichotomie". Le code ci-dessus a été modifié... (4 itérations quel que soit le nombre de points)

[Celelibi]

Pas tout à fait... Il s'agit de la différence minimale entre 2 nombres flottants..

Si on teste : if ( a = b ), on aura toujoours OUI si la différence est inférieure à ce nombre..

Non.
Le standard C89 dit

minimum positive floating-point number x such that 1.0 + x

Les standards C99 et C11 disent à la section 5.2.4.2.2

the difference between 1 and the least value greater than 1 that is representable in the
given floating point type, b^(1-p)

Et d'ailleurs, ta définition est fausse puisqu'on peut obtenir une différence bien plus petite sur des nombres plus petits (sans même parler des nombres dénormalisés).

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <float.h>
 
int main(void) {
	volatile double e = DBL_EPSILON; /* "volatile" pour forcer le compilateur à écrire les résultats en mémoire et ainsi éviter qu'il ne prenne la liberté de faire ses calculs sur des flottants étendues sans les tronquer */
	volatile double he = e / 2; /* half epsilon */
	volatile double x = 1e-100; /* Un nombre inférieur à 1 */
	volatile double xphe = x + he; /* On ajoute un demi-epsilon */
	volatile double diff = xphe - x; /* On soustrait pour voir si on retrouve notre demi epsilon */
 
	printf("e    %g\n", e);
	printf("he   %g\n", he);
	printf("x    %g\n", x);
	printf("xphe %g\n", xphe);
 
	if (xphe == x)
		printf("Indifférenciables\n");
	else
		printf("Différence de %g\n", diff);
 
	return 0;
}

J'ai l'impression que ce n'est pas clair pour toi comment fonctionne la précision des flottants. :S
Je ne pense pas pouvoir faire plus simple que dire que ça revient, dans la notation scientifique, à fixer le nombre de chiffres après la virgule. (Notation scientifique => un seul chiffre avant la virgule, et celui-ci est supérieur ou égal à 1.)
Par exemple, si j'ai 16 chiffres après la virgule, je peux faire la différence entre :
1.1234567890123456*10^-100 et 1.1234567890123457*10^-100, alors que la différence est de 10^-116.
Par contre, je ne pourrais pas différencier le 18eme chiffre :
1.123456789012345678*10^18 et 1.123456789012345679*10^18, alors qu'ici la différence est de +/-1.

Pour information, le plus petit double normalisé que l'on peut écrire (tout en ayant 16 décimales de précision) est de l'ordre de 10^-308.

Tu parles bien de décimales ....

10^-52 n'est pas une décimale utilisée

Oui, je parle de décimales. Mais il est assez aisé de convertir une précision binaire en décimal et inversement, du moment qu'on garde à l'esprit ma baffouille ci-dessus. (Au passage, on parlait de 2^-52 ou 10^-16. Pas 10^-52.)

Tout problème se ramène à une échelle cohérente et représentable par des doubles "normaux"... Tout algo qui ne le fait pas est absurde dans son principe...
[...]
A part en maths théoriques, des écarts de 10^-52 n'ont strictement aucune signiifcation (si ce sont des écarts).. Tout programme censé aura remis dans une échelle cohérente.... Tout prgramme utilisant des valeurs n'ayant pas de rapport avec la précision de mesure est aberrant...
[...]
Je sais que c'est à la mode d'enseigner les grands nombres et l'utilisation de bibliothèques spécialisées, mais c'est une totale absurdité, sauf en crypto...

J'admire tes grands principes universels et ta connaissance sans faille des besoins de tout en monde en terme de calculs.

Cela dit, je t'accorde qu'en physique, on ne s'amuse pas souvent à adresser un nanomètre sur des objets d'un ordre de grandeur de 10000km. Encore que... Tu as sûrement entendu parler de ces décimales qui changent tout ?

De mémoire, il faudrait mesurer la densité de l'univers à plus de 23 décimales pour déterminer son sens de courbure. (C'est un souvenir d'une slide y'a 7 ans, c'est peut-être faux.)
Ou encore l'évaluation de la température du fond diffus cosmologique qui présente des fluctuations qui ne sont observables qu'à partir d'une certaine précision. Et dont l'interprétation peut nous en apprendre pas mal sur l'univers. (Mais je laisse ça au cosmologistes.)

Plus proche de moi : la semaine dernière, un solveur de programme linéaire se plaignait que mon problème était non-borné. En effet, une erreur d'arrondi non voulue faisait que mon polytope n'était plus fermé. -> Je fixe la précision : le solveur trouve une solution.
Ou plus généralement en recherche opérationnelle (qui résout des problèmes très concrets), certaines méthodes peuvent nécessiter une bonne précision pour ne pas dire n'importe quoi.

Et c'est pareil pour tous les problèmes... utiliser la bonne unité et tenir compte de la précision des données réelles...

C'est exactement ce que je dis : Si j'ai déterminé que j'ai 16 décimales correctes dans mon tableau d'entrée et que j'ai besoin d'en garder 16 correctes, j'ai pas envie qu'un algo censé être exact me donne un résultat approximatif.

[Celelibi]

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
  double  d9[5]={0, 10, 11, 12, 13}, d10[5]={-2^1000, 1, 2, 3, 4};

Resultat :

Moyenne 2.40191 et 1 iterations pour mediane
Tableau 10 mediane 1

Je pensais plutôt à -2e1000 qu'à un xor (qui vaut -1002). ^^
Mais toujours est-il que ce résultat est faux. D'ailleurs, il est faux à partir de {-2, 1, 2, 3, 4}.

[souviron34]

J'admire tes grands principes universels et ta connaissance sans faille des besoins de tout en monde en terme de calculs.

Cela dit, je t'accorde qu'en physique, on ne s'amuse pas souvent à adresser un nanomètre sur des objets d'un ordre de grandeur de 10000km. Encore que... Tu as sûrement entendu parler de ces décimales qui changent tout ?

De mémoire, il faudrait mesurer la densité de l'univers à plus de 23 décimales pour déterminer son sens de courbure. (C'est un souvenir d'une slide y'a 7 ans, c'est peut-être faux.)

Juste pour terminer là-dessus : je crois que tu loupes le point essentiel...

Si la NASA, qui dispose des plus gros ordinateurs du monde, avec des téraflopsd e puissance de calcul, des TO de mémoire, et de préciion supérieures à 128 bits, n'y arrive pas, ce n'est pas à cause de difficultés de représenter les nombres... C'est à cause des mesures et de leur imprécision physique...

Quand Avogadro a sorti sa constante, Von Neumann n'était pas né, et pourtant il a sorti un truc de l'ordre de 10^23...

Comme :

Ou encore l'évaluation de la température du fond diffus cosmologique qui présente des fluctuations qui ne sont observables qu'à partir d'une certaine précision. Et dont l'interprétation peut nous en apprendre pas mal sur l'univers. (Mais je laisse ça au cosmologistes.)

Et pourtant Penzias & Wilson ont fait ça à 0.05 degrés près, sans ordinateurs...


Mais de toutes façons :

C'est exactement ce que je dis : Si j'ai déterminé que j'ai 16 décimales correctes dans mon tableau d'entrée et que j'ai besoin d'en garder 16 correctes, j'ai pas envie qu'un algo censé être exact me donne un résultat approximatif.

le problème est résolu : je ne passe plus par les logs, juste la tableau original

Donc plus de problèmes

Je pensais plutôt à -2e1000 qu'à un xor (qui vaut -1002). ^^
Mais toujours est-il que ce résultat est faux. D'ailleurs, il est faux à partir de {-2, 1, 2, 3, 4}.

Oui, mon erreur.. J'ai recopié ton tableau tel quel...

Et là aussi, un problème d'inattention..

Maintenant, je mettrais juste ici la sortie :

Moyenne 8 et 1 iterations pour mediane
Tableau 1 mediane 2

Moyenne 2 et 1 iterations pour mediane
Tableau 2 mediane 2

Moyenne 2 et 1 iterations pour mediane
Tableau 3 mediane 2

Moyenne 1.5 et 1 iterations pour mediane
Tableau 4 mediane 1.5

Moyenne 2.14302e+300 et 1 iterations pour mediane
Tableau 5 mediane 2

Moyenne 0.25 et 1 iterations pour mediane
Tableau 6 mediane 0

Moyenne 0.6 et 1 iterations pour mediane
Tableau 7 mediane 2e-16

Moyenne 1.07151e+295 et 2 iterations pour mediane
Tableau 8 mediane 499999.500000

Moyenne 9.2 et 1 iterations pour mediane
Tableau 9 mediane 11

Moyenne -2.14302e+300 et 1 iterations pour mediane
Tableau 10 mediane 2

Tout tableau du style (1,2,3,...k, x^1000) se résout en 2 itérations
Tout tableau du style (1,2, toute le reste =1.5) se résoud en 4 itérations.

Le worst-case semble être N points aléatoires, et le nombre d'itérations tend vers une constante (25) (voir figure).

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
 
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include "time.h"
 
 
/*
 * Retourne la valeur absolue d'un entier
 *
 */
int iabs(int n)
{
  if ( n >= 0 )
    return n ;
  else
    return -n ;
}
 
 
/*
 *
 * Calcul de la mediane
 *
 */
double Mediane ( double *tab, int N )
{
  int    milieu, i, m, n, Nit=0, Pair=0, Indice1, Indice2, Indice3, Indicemoy ;
  double minval=INT_MAX, maxval=-INT_MAX, maxval0 ;
  double Delta0, Delta1, Delta2, moy=0.0, Medi ;
 
 
  milieu = N/2 ;
  if ( (N % 2) == 0 )
    Pair = 1 ;
 
/*
--- Calcul min/max du tableau original
*/
  for ( i = 0 ; i < N ; i++ )
    {
      moy = moy + tab[i] ; /* Calcul de la moyenne */
 
      if ( tab[i] < minval )
	minval = tab[i] ;
      if ( tab[i] > maxval )
	maxval = tab[i] ;
    }
  maxval0 =maxval ;
  moy = moy / (double)N ;
 
 
 
/*
--- Selection du point le plus proche de la moyenne par valeur inférieure, par son indice
*/
  Delta0 = 0.99*minval ;
  Indicemoy = 0 ;
  for ( i = 0 ; i < N ; i++ )
    {
      if ( tab[i] <= moy )
	{
	  if ( tab[i] > Delta0 )
	    {
	      Delta0 = tab[i] ;
	      Indicemoy = i ;
	    }
	}
    }
 
 
/*
--- Calcul mediane
*/
  Medi = Delta0 ; /* Initialisation a la moyenne */
  Indice1 = Indicemoy ;
  Indice2 = Indicemoy ;
  Indice3 = Indicemoy ;
  while ( 1 )
    {
      Nit = Nit+1 ;
 
      /* Comptage des points <= mediane */
      m = 0 ;
      n = 0 ;
      Delta0 = 1.01*maxval ;
      Delta1 = 0.99*minval ;
      Delta2 = 0.99*minval ;
      for ( i = 0 ; i < N ; i++ )
	{
	  if ( tab[i] <= Medi ) /* Pour tout point <= a la mediane */
	    {
	      m = m + 1 ;
 
	      /* Cherche le point le plus proche en dessous*/
	      if ( (tab[i] < Medi) && (tab[i] > Delta1) ) 
		{
		  n = n + 1 ;
		  Delta1 = tab[i] ;
		  Indice1 = i ;
		}
 
	      /* Cherche le point exact */
	      if ( tab[i] > Delta2 ) 
		{
		  Delta2 = tab[i] ;
		  Indice3 = i ;
		}
	    }
	  else
	    {
	      /* Pour tout point > mediane, cherche le point le plus proche au dessus*/
	      if ( tab[i] < Delta0 )
		{
		  Delta0 = tab[i] ;
		  Indice2 = i ;
		}
	    }
	}
 
      /* Si on est a moins de 1 du milieu - ou si on a un cas degenere - on s'arrete */
      if ( (iabs(milieu-m) <= 1) || (n ==milieu) || ((Indice2 == Indice3) && (Indice1 == Indice2)) )
	{
	    break ;
	}
 
 
      /* Sinon on ajuste entre les 2 valeurs les plus proches */
      if ( m > milieu )
	{
	  maxval = Medi ;
	  Medi = (minval+Delta1)/2.0 ;
	}
      else
	{
	  minval = Medi ;
	  Medi = (Delta0+maxval)/2.0 ;
	}
    }
 
 
/*
--- Remet les vraies valeurs
*/
  if ( Nit == 1 )  /* Si on n'a pas bouclé plus qu'une fois, ajuste */
    {
      if ( (N%2) == 0 )
	Medi = tab[Indicemoy] ;
      else
	{
	  if ( m == milieu )
	    Medi = tab[Indice2] ;
	  else
	    if ( n == milieu )
	      Medi = tab[Indice1] ;
	    else
	      if ( (iabs(Indice1 - milieu) >= 2) || (iabs(Indice3 - milieu) >= 2) )
		{
		  Medi = tab[Indice2] ; /* Affecte la nouvelle valeur (inferieure) */
 
		  Delta0 = 1.01*maxval ; /* Cherche le point le plus proche par valeur superieure */
		  for ( i = 0 ; i < N ; i++ )
		    {
		      if ( tab[i] > Medi ) /* Pour tout point > a la mediane */
			{
			  /* cherche le point le plus proche au dessus*/
			  if ( tab[i] < Delta0 )
			    {
			      Delta0 = tab[i] ;
			      Indice2 = i ;
			    }
			}
		    }
 
		  Medi = tab[Indice2] ;
	      }
	    else
	      Medi = tab[Indicemoy] ;
	}
    }
  else
    {
      if ( m < milieu )
	Medi = tab[Indice2];  /* Si on a boucle */
      else
	Medi = tab[Indice3] ;
    }
 
 
/*
--- Ajustement pour tableau pair
*/
  if ( (N%2) == 0 )
    {
      /*Cherche le point le plus proche au dessus */
      Delta1 = maxval0 ;
      for ( i = 0 ; i < N ; i++ )
	{
	  if ( tab[i] > Medi )
	    {
	      if ( tab[i] < Delta1 )
		Delta1 = tab[i] ;
	    }
	}
 
      Delta0 = Medi ; /* Pour verification des cas degeneres */
      Medi = (Medi+Delta1)/2.0 ;
 
      /* Verification des cas degeneres */
      m = 0 ;
      for ( i = 0 ; i < N ; i++ )
	{
	  if ( tab[i] < Medi )
	    m = m + 1 ;
	}
 
      if ( m != milieu )
	Medi = Delta0 ;
    }
 
 
  fprintf ( stderr, "\n Moyenne %g et %d iterations pour mediane",moy,Nit);
  /*
  fprintf ( stderr, "\n%d %d",N,Nit);
  */
  return Medi ;
}
 
 
 
/*
 *
 *  TEST PROGRAMME
 *
 */
int main(int argc, char *argv[])
{
  int     i, N=10, Incr=10 ;
  double  d1[5]={0, 1, 2, 3, 34}, d2[5]={0, 1, 2, 3, 4}, d3[4]={0, 1, 3, 4} ;
  double  d4[4]={0, 1, 2, 3}, d5[5]={0, 1, 2, 3, 2}, d6[4]={0, 0, 0, 1} ;
  double  d7[5]={0, 1e-16, 2e-16, 1, 2}, d8[1000001];
  double  d9[5]={0, 10, 11, 12, 13}, d10[5]={-2^1000, 1, 2, 3, 4};
  double  *d=NULL, val ;
 
  d5[4] = pow ( 2, 1000.0);
  d10[0] = -d5[4] ;
 
  if ( argc > 1 )
    {
      d = malloc ( 10000001*sizeof(double) );
      if ( d == NULL )
	return 1 ;
 
      if ( strcmp ( argv[1], "M") == 0 )
	{
	  for ( N = 10 ; N <= 100000000 ; N=N+Incr )
	    {
	      if ( N == (10*Incr) )
		Incr = 10*Incr ;
 
	      for ( i = 0 ; i < N ; i++ )
		d[i] = (double)i ;
 
	      d[N-1] = d5[4] ;
	      val = Mediane(d,N);
	    }
	}
      else
	{
	  if ( strcmp ( argv[1], "R") == 0 )
	    {
	      for ( N = 10 ; N <= 10000000 ; N=N+Incr )
		{
		  if ( N == (10*Incr) )
		    Incr = 10*Incr ;
 
		  srand(time(NULL));
 
		  for ( i = 3 ; i < N ; i++ )
		    d[i] = 1.0 + ((double)rand()/(double)RAND_MAX) ;
 
		  d[0] = 1.0 ;
		  d[1] = 2.0 ;
 
		  val = Mediane(d,N);
		}
	    }
	  else
	    {
	      for ( N = 10 ; N <= 10000000 ; N=N+Incr )
		{
		  if ( N == (10*Incr) )
		    Incr = 10*Incr ;
 
		  srand(time(NULL));
 
		  for ( i = 3 ; i < N ; i++ )
		    d[i] = 1.5 ;
 
		  d[0] = 1.0 ;
		  d[1] = 2.0 ;
 
		  fprintf ( stderr, " # %g", Mediane(d,N));
		}
	    }
	}
 
      free(d);
    }
  else
    {
      for ( i = 0 ; i < 999999 ; i++ )
	d8[i] = (double)i;
 
      d8[999999] = d5[4] ;
      fprintf ( stderr, "\n Tableau 1 mediane %g\n",Mediane(d1,5));
      fprintf ( stderr, "\n Tableau 2 mediane %g\n",Mediane(d2,5));
      fprintf ( stderr, "\n Tableau 3 mediane %g\n",Mediane(d3,4));
      fprintf ( stderr, "\n Tableau 4 mediane %g\n",Mediane(d4,4));
      fprintf ( stderr, "\n Tableau 5 mediane %g\n",Mediane(d5,5));
      fprintf ( stderr, "\n Tableau 6 mediane %g\n",Mediane(d6,4));
      fprintf ( stderr, "\n Tableau 7 mediane %g\n",Mediane(d7,5));
      fprintf ( stderr, "\n Tableau 8 mediane %f\n",Mediane(d8,1000000));      
      fprintf ( stderr, "\n Tableau 9 mediane %g\n",Mediane(d9,5));
      fprintf ( stderr, "\n Tableau 10 mediane %g\n",Mediane(d10,5));
    }
 
return 0;
}

Maintenant, j'aimerais sans doute si un chercheur/ingénieur passait par là, et pouvait me confirmer et m'évaluer le prog pour savoir si une publi serait à l'ordre du jour....

Merrci..


.

[Celelibi]

Si la NASA, qui dispose des plus gros ordinateurs du monde, avec des téraflopsd e puissance de calcul, des TO de mémoire, et de préciion supérieures à 128 bits, n'y arrive pas, ce n'est pas à cause de difficultés de représenter les nombres... C'est à cause des mesures et de leur imprécision physique...

Tu passes à côté de mon point. Je dis simplement que rien ne te permet de dire que "un algo qui attend une précision de 2^-52 est foireux". Il y a des gens qui ont besoin de cette précision, ce n'est pas à toi de le décider. Point.

Et sinon, juste pour les ordres de grandeur : depuis 2008 tu peux avoir un TeraFLOPS dans ta carte graphique. En novembre dernier, la machine Titan atteignait 27 PetaFLOPS en pic (et 17 PetaFLOPS soutenus).

Le supercalculateur de la NASA n'est classé que 14eme du TOP500. Et de source officieuse, ça serait l'industrie pétrolière qui posséderait les plus gros supercalculateurs, mais ils ne se font pas classer dans le top500.

le problème est résolu : je ne passe plus par les logs, juste la tableau original

Donc plus de problèmes

Parfait. Voyons si je trouve encore des bugs. :p


Bien bien bien.
Je pense qu'il faudrait inverser tes constantes 0.99 et 1.01 si les min et max sont négatifs. Ou mieux : s'en passer.

Et sinon, que dirais-tu d'un tableau exponentiel ?

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
	double d12[1000];
		for (i = 0; i < sizeof(d12)/2/sizeof(*d12) - 1; i++) {
			d12[2 * i] = pow(2, i);
			d12[2 * i + 1] = d12[2 * i] - 1;
		}
 
		for (i = 1; i <= sizeof(d12)/sizeof(*d12); i++)
			Mediane(d12, i);

Qui, pour 1000 cases fait 122 itérations.


Je te met le plot du nombre d'itérations en fonction de la taille du tableau sus-cité.

Note que l'avant-dernier point (pour N = 2047) était aberrant (1 itération) je l'ai enlevé.


Voici donc ton worst-case. Boucle principale en O(N) donc complexité globale en O(N^2) au pire.

Et voilà les 3 lignes de code utilisées pour générer ce graphe :

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
	double d11[] = {-1, -0.99, 0}, d12[2048];
/* [...] */
		for (i = 0; i < sizeof(d12)/2/sizeof(*d12); i++) {
			d12[2 * i] = pow(2, i);
			d12[2 * i + 1] = d12[2*i] - 1;
		}
 
		for (i = 1; i <= sizeof(d12)/sizeof(*d12); i++)
			Mediane(d12, i);

Maintenant, j'aimerais sans doute si un chercheur/ingénieur passait par là, et pouvait me confirmer et m'évaluer le prog pour savoir si une publi serait à l'ordre du jour....

Bien... Je ne suis pas un chercheur confirmé, juste un petit doctorant. Donc en attendant un autre avis, je peux te donner le mien.
Publier sur un algo aussi courant que la recherche de médiane, ça me semble difficile. Il faudrait vraiment un état de l'art en béton pour prouver qu'il n'existe pas d'algo similaire ou meilleur ayant les mêmes propriétés (complexité et consommation de mémoire additionnelle).
Il faudrait aussi bétonner l'étude de la complexité moyenne (ce qui m'a l'air assez chaud vu que tu te bases toujours plus ou moins sur les valeurs du tableau et que ce sont des double).

Mais si tu réunis ces deux points : pourquoi pas ?