Discussion :

[souviron34]

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.

A voir.. J'ai pas testé depuis que j'ai modifé... Mais c'étai pour tenir compte des cas dégénérés où la moyenne tombe pile sur un index.. Mais c'était avant d'avoir introduit le 3ième indice qui en tient compte Je vérifierais ça..

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.

OK

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 ?

Pour la mémoire additionnelle il n'y en a plus..

Ben disons que quand je vois que le top du top est de faire un tri, et que même si on arrive à O(NlogN) , d'une part il faut de la mémoire additionnelle, d'autre part dans les cas qui semblent moyens ça a quand même l'air très nettement plus puissant que ça, au moins d'un log en plus... (et je pencherais d'ailleurs pour log*, quand je vois que la courbe s'aplatit pour le cas random... Le cas random m'a l'air le "pire du moyen")

M'enfin, c'est ce que j'en dis, hein

En tous cas, tu vois, ça se fait sur le principe de base que j'avais évoqué au début (même si il a fallu quelques itérations de corrections )

[Celelibi]

Pour la mémoire additionnelle il n'y en a plus..

C'est bien de ça dont je parlais : avec un coût en mémoire additionnelle en O(1).

Ben disons que quand je vois que le top du top est de faire un tri, et que même si on arrive à O(NlogN) , d'une part il faut de la mémoire additionnelle, d'autre part dans les cas qui semblent moyens ça a quand même l'air très nettement plus puissant que ça, au moins d'un log en plus... (et je pencherais d'ailleurs pour log*, quand je vois que la courbe s'aplatit pour le cas random... Le cas random m'a l'air le "pire du moyen")

Justement non.
Le quickselect est en O(N) en moyenne. Et avec la variation "médiane des médianes" il reste en O(N) au pire. Le quickselect n'est pas un tri, c'est un tri partiel.
Par contre il nécessite de pouvoir permuter les éléments du tableau (ou d'en faire une copie).

Du coup je me dis qu'il y a peut-être moyen de rester sur du O(N) en temps et n'avoir qu'un O(log(N)) en espace additionnel.

[Celelibi]

Tiens, sinon, je crois que j'ai un algo en O(N*log(N)) en moyenne et O(N^2) au pire sans espace additionnel. C'est à dire comme un quicksort, mais sans toucher au tableau.

La différence avec le tiens, c'est que tu es en O(N*log(M)) en moyenne.

[souviron34]

C'est bien de ça dont je parlais : avec un coût en mémoire additionnelle en O(1).

Pour moi, c'est O(0).. O(1) c'est une constante... Je pense non nulle... Donc par exemple un hosto sur du 8bits, c'est 256 entiers.. ça c'est O(1)...

0, c'est 0.. Il n'y a pas de complexité à mon sens...

T
La différence avec le tiens, c'est que tu es en O(N*log(M)) en moyenne.

Très étrange, parce que quand tu regardes les plots, ça ressemble plus à logN....

Il me semble que les valeurs n'ont pas d'importance , puisque avec 2^1000 ou 500000 ou 500 on a le même résultat.... : le même nombre d'itérations, et que par contre le nombre crôit avec N..

Par contre, pour le reste je regarderais demain...


PS: et au cas où, cela fait 30 ans que j'ai été doctorant

[Celelibi]

Pour moi, c'est O(0).. O(1) c'est une constante... Je pense non nulle... Donc par exemple un hosto sur du 8bits, c'est 256 entiers.. ça c'est O(1)...

0, c'est 0.. Il n'y a pas de complexité à mon sens...

Bien, oui. Tu as un certain nombre de variables locales. Tu ne peux pas les ignorer, elles font parti de l'algo et prennent de la mémoire.
De même, si tu as un algo récursif il faut évaluer le nombre d'appels récursifs pour déterminer la consommation mémoire. C'est pour ça que le quicksort et le mergesort ont une consommation mémoire en O(log(N)).

Très étrange, parce que quand tu regardes les plots, ça ressemble plus à logN....

Il me semble que les valeurs n'ont pas d'importance , puisque avec 2^1000 ou 500000 ou 500 on a le même résultat.... : le même nombre d'itérations, et que par contre le nombre crôit avec N..

Je dois dire que la complexité de ton algo me perturbe pas mal. Tu fais bien une dichotomie sur les valeurs du tableau.
(minval+Delta0)/2 c'est bien une moyenne sur les bornes de ton intervalle. Donc la complexité c'est censé être du O(N*log(M)) avec M l'intervalle de valeurs. Mais le fait que tu prenne Delta0 et pas ton pivot précédent coupe la complexité à du O(N²).

Tiens, je vais essayer de reprendre mon pire cas de tout à l'heure et de faire varier l'intervalle de valeurs sans changer la taille du tableau.

Le code :

Code C :

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

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

En gros, je prend le tableau exponentiel, mais j'affecte l'exposant d'un coefficient inférieur ou égal à 1.

Et le nombre d'itération en fonction de la valeur max du tableau (ici plotté en log-log pour y voir quelque chose).

La dépendance me semble bien être logarithmique. Et la présence de "marches" de plus en plus grosses me semble amusante.

PS: et au cas où, cela fait 30 ans que j'ai été doctorant

Tu m'en vois ravi.
En physique j'imagine ?

[souviron34]

Et le nombre d'itération en fonction de la valeur max du tableau (ici plotté en log-log pour y voir quelque chose).
...
La dépendance me semble bien être logarithmique. Et la présence de "marches" de plus en plus grosses me semble amusante.

Euh... En log-log la courbe semble être un log, donc ce serait en log(log(M))...

En ce qui concerne les marches, c'est justement là où je pense intervient le log* (log star).. Et le fait que justement ce n'est pas une "vraie" dichotomie, mais "biaisée" puisque qu'on veut tomber sur un indice précis et non pas entre 2 valeurs...

Mais je vais ré-essayer avec tes exemples et mon idée d'avant (avant que je supprime le log). On pourrait toujours ajouter un paramètre donnant la précision max, et du coup ajouter un simple facteur multiplicatif avant de faire le log si vraiment on est dans les limites que tu disais plus haut...

Tu m'en vois ravi.
En physique j'imagine ?

Astrophysique... Et c'est bien pour ça que je te parlais d'échelles et de précision dans la réalité... J'ai évolué dans l'astrophysique, la cosmologie, la médecine, le traitement images, la météo, les trains, et la simulation aéronautique, et nulle part je n'ai vu de telles nécessités....

C'est la différence entre les maths pures et la physique : comme l'indique la signature de pseudocode "algorithme : méthode complexe pour résoudre un problème simple" Autant la théorie est très jolie, et peut amener à des impasses, autant la pratique est autre, et ce qui peut être considéré comme une impasse théorique n'en est absolument pas une dans la pratique.... car n'arrivant jamais.... pour des raisons pratiques

[Celelibi]

Euh... En log-log la courbe semble être un log, donc ce serait en log(log(M))...

Bien... Le log-log (j'entend : log sur les deux axes) préserve plus ou moins la forme des courbes.
Si je n'avais mis le log que sur l'axe des x on aurait vu un truc qui ressemble à une droite (avec des marches).

Et on peut montrer que dans l'espace log-log si on a un truc qui ressemble à une fonction log, alors c'est une fonction log dans l'espace linéaire.
Il suffit de poser que la transformation de coordonnées de l'espace log-log est X = 10^x et Y = 10^y.
On observe Y = log(X) sur le graphe en log-log, et on arrive aisément à y = log(x)+k.

Mais je vais ré-essayer avec tes exemples et mon idée d'avant (avant que je supprime le log). On pourrait toujours ajouter un paramètre donnant la précision max, et du coup ajouter un simple facteur multiplicatif avant de faire le log si vraiment on est dans les limites que tu disais plus haut...

Oui mais si tu changes encore d'algo je vais devoir encore trouver des exemples différents. :p

Astrophysique... Et c'est bien pour ça que je te parlais d'échelles et de précision dans la réalité... J'ai évolué dans l'astrophysique, la cosmologie, la médecine, le traitement images, la météo, les trains, et la simulation aéronautique, et nulle part je n'ai vu de telles nécessités....

Oui, tant que tu restes dans de la mesure physique.
Mais les flottants ne sont pas là que pour représenter des mesures. Ils peuvent aussi être un outil purement calculatoire pour résoudre un problème intrinsèquement discret.

Moi je suis un informatico-informaticien. Des problèmes NP-complets j'en croise tous les jours. Trouver le meilleur agencement d'un ensemble de tâches communicantes sur un réseau arbitraire de machines de manière à minimiser son temps d'exécution. Trouver où placer les données (et leurs réplicats) sur un cluster qui devra les traiter en entier. Trouver dans quel ordre effectuer les transferts d'un ensemble de machines A vers un ensemble de machines B de manière à ne saturer aucun lien réseau ni aucun switch et de manière à ce que ça termine au plus vite.

Et dans certains cas, pour trouver une solution satisfaisante à ces problèmes dans un temps raisonnable, on peut relâcher certaines contraintes et en faire un problème "continu" généralement plus facile à résoudre. Et les flottants qu'on manipule n'ont rien de physique. Ce ne sont que des artéfactes de calcul qu'on fera disparaître quand on retransformera les résultats en solution concrète (donc entière/discrète).

Et donc la précision nécessaire pour obtenir une solution acceptable peut être... quelconque. Ça dépend de la méthode de calcul.

[souviron34]

Moi je suis un informatico-informaticien. Des problèmes NP-complets j'en croise tous les jours. Trouver le meilleur agencement d'un ensemble de tâches communicantes sur un réseau arbitraire de machines de manière à minimiser son temps d'exécution. Trouver où placer les données (et leurs réplicats) sur un cluster qui devra les traiter en entier. Trouver dans quel ordre effectuer les transferts d'un ensemble de machines A vers un ensemble de machines B de manière à ne saturer aucun lien réseau ni aucun switch et de manière à ce que ça termine au plus vite.

Admettons, mais je ferais remarquer que :

Trouver le meilleur agencement d'un ensemble de tâches communicantes sur un réseau arbitraire de machines de manière à minimiser son temps d'exécution : avoir 2^52 tâches ou 2^52 machines est ..Comment dire.... délirant, non ?? (et même 2^52 données à traiter d'un coup)

Et c'est pareil pour les autres exemples..

Pour atteindre le delta que tu citais plus haut, il faudrait atteindre ce nombre... non ??



'fin bon, de toutes façons y'a truc qu'y faut que je regarde dans l'algo.. Je crois que j'ai oublié une condition d'arrêt... Intrinsquement, vu le "bias" de la dichotomie, ce devrait être terminé en quelques itérations tout au plus... J'ai dû louper une étape quelque part...



PS: au fait, on peut se passer des 0.99 et 1.01, sauf le 1.01 dans l'itération... il y a des cas particuliers où sinon le Delta0 est non défini (ou défini comme le max, alors qu'on veut le min du max)..

[Celelibi]

Admettons, mais je ferais remarquer que :

Trouver le meilleur agencement d'un ensemble de tâches communicantes sur un réseau arbitraire de machines de manière à minimiser son temps d'exécution : avoir 2^52 tâches ou 2^52 machines est ..Comment dire.... délirant, non ?? (et même 2^52 données à traiter d'un coup)

Et c'est pareil pour les autres exemples..

Pour atteindre le delta que tu citais plus haut, il faudrait atteindre ce nombre... non ??

Du tout. Ce n'est que du calcul intermédiaire.

Exemple simple dans la catégorie "mapping de tâches sur un réseau de machines" : Tu veux mettre des tâches de surveillance de la charge du réseau pour effectuer une migration de tâches si certaines communiquent beaucoup entre elles (pour les rapprocher, voire, les mettre sur la même machine).
Ces tâches de surveillance doivent - au total - avoir accès à tous les liens du réseau. Mais comme ça bouffe du CPU, t'as envie d'en mettre le minimum possible. Il s'agit d'une application pratique du problème de couverture de sommets (ou vertex cover en anglais).
Problème NP-Complet bien connu.

On peut le formuler comme un problème d'optimisation linéaire en nombres entiers. Toujours NP-Complet, mais là dessus on peut faire de la relaxation continue pour dire que les variables entières peuvent maintenant prendre n'importe quelle valeur réelle. Et on va donc pouvoir trouver une solution approchée en un temps polynômial (en moyenne) en utilisant un solveur de programme linéaire.
Ensuite on retrouve une solution à notre problème entier en arrondissant les variables à une solution admissible proche.

Voilà le genre d'astuce calculatoire où les flottants apparaissent "comme par magie".
Je pourrais aussi citer la théorie des tâches divisble où on suppose qu'on peut diviser une tâche de calcul en d'aussi petits morceaux qu'on veut. On se laisse aller à accepter qu'on puisse traiter pi/sqrt(2) octets sur une machine.

Ensuite, quand on a un problème en variables continue, là où la précision est importante, c'est quand on chercher la solution dans le modèle continue.

Regarde par exemple l'algo du simplexe pour résoudre les problèmes d'optimisation linéaires mono-critère sous contraintes linéaires (comme sus-cité). Cet algo considère que les contraintes sont des plans (ou plutôt des demi-espaces) par exemple 4*x - 8*y < 3 et que l'ensemble des contraintes forment un polytope (un truc qui ressemble à un polyèdre) dont on ne connaît pas les coordonnées des sommets à priori. On connaît uniquement les plans qui le délimitent.
Et là dessus, on essaye de maximiser (ou minimiser) une fonction affine.
Cet algo marche en se balandant d'arrête en arrête du polytope jusqu'à avoir une solution optimale. Et pour ça, il faut connaître les coordonnées des sommets, et pour connaître les coordonnées des sommets, il faut calculer l'intersection des différents plans.
Et si ces calculs manquent de précision, on risque de louper (par exemple) qu'un plan participe au sommet. Ou pire, on risque de ne pas trouver d'intersection entre deux plans quasiment parallèles, donc passer à côté d'une solution admissible. Ou le contraire, trouver une intersection qui n'est pas censée exister et donc créer une solution qui n'existe pas.

Mais si tu cherches juste des grands nombres, je peux te dire par exemple que le nombre de combinaisons admissibles dans certains problèmes peut être supérieur au nombre de particules dans l'univers... de plusieurs ordres de grandeur. Bien sûr on ne les explorera pas toutes, il faut en éliminer des gros paquets par des heuristiques. Et calculer ce nombre de manière exacte n'est généralement pas d'une grande aide... Encore que...
On pourrait imaginer des cas où on peut passer à une exploration exhaustive en dessous de 1000 combinaisons quand on a réussi à éliminer la quasi totalité des solutions très mauvaises.