Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
Non
Le m de départ est l'enveloppe convexe plus un certain nombre déterminés par une première approximation.
Et ce m croît au fur et à mesure que des points répondant aux citères sont trouvés entre 2 sommets, dans une phase de rafinnement qui est celle qui me préoccupe ici.
Dans l'idéal la boucle serait assez simple. Dans la réalité il faut considérer qu'il faut être "fair" dans le traitement, pour ne pas privilégier un côté par rapport à un autre..
Ok, j'ai zappé un détail. Ton algo cherche quoi en définitive ? L'enveloppe convexe ou concave d'un nuage de points ?
tu veux dire b=m ?Envoyé par souviron34
s'il y a des éléments en commun dans les sous problèmes, alors "b" est plus petit que "a". Et la conclusion est que la complexité est en O(N^Log_b(a)).Maintenant, il est à peu près sûr qu'il y a des points en commun entre 2 "sous-problèmes". (et heureusement, sinon ce ne serait pas ni progressif, ni équitable) . Le but de cet algo est justement de le réduire au minimum.. en utilisant des maths et un code simple.
Tout ca sous réserve que tu puisses modéliser les opérations de ton algo sous la forme T(N)=a.T(N/b) + c.N
concave
oui
OK, ça correspond à la courbe expérimentale, non ?? (enfin, j'y comprend plus grand chose : O (m N^...) , non ?) (l'expression d'après la courbe de l'algo total, la double boucle, était O ( m (N 10^(1-logN)) ) )
Ce sont des opérations relativement simples (tests), plus quelques complexes (calcul du numérateur et dénominateur d'une intersection possible, calcul d'un angle entre 3 points), mais dont le flux est linéaire...
On ne pacoure plus de tableaux ou de listes. Pour chaque point examiné on utilise 3 points et on teste divers éléments.
On peut donc dire que les opérations sont en O(1) pour chaque point examiné (un nombre constant par point)
C'est ça que tu appelles "modéliser" ??
Je m'y perd avec le vocabulaire spécialisé...
Donc, en fait, ton algo fait ça : http://youtu.be/EpTgOC_XLRo
Oui. Je ne me suis intéressé qu'a la deuxième boucle (ce qui revient a traiter m comme une constante, et pas comme un paramètre d'entrée). Bref on appelle "m" fois une fonction (2nde boucle) qui fait "F(N)" opérations.
On considère que chaque opération se fait en temps constant O(1).
Le nombre d'opérations est estimé en considérant le problème comme du D&C. Le problème est décomposé en "a" sous-problèmes, chacun s'occupant d'une partie de la population (taille N). Les parties (chacune de taille N/b) ne sont pas disjointe, il y a des individus en commun.
D'où la complexité en nombre d'opération F(N) = O(N^Log_b(a))
La complexité totale de l'algo, 1ère bouche comprise est donc O(m.N^Log_b(a))
Log_b , c'est log en base b ou le log itéré b fois ?
Vu que là b = a = m, alors on aurait une expression...
OK. là je cromprend mieux
C'est donc du "fractional power" ?
N^Log_b a est équivalent à N 10^(1-a LogN) ??? (pas le même a, bien sûr)
Par contre, la "modélisation" de m en fonction de N est ... ?????? A part expérimentalement (pour l'algo le plus précis, on va de N quand N faible à N/10 par exemple pour N ~ 50 000, pour l'algo le moins précis de N à N/100 sur le même range) je ne sais absolument pas ce que je pourrais faire...
Mais enfin, là on a déjà bien avancé...
@Davcha : en un sens oui, mais beaucoup plus précis, visuellement correspondant à ce que l'oeil voit, et sans presque de consommation mémoire et de maths complexes (même pas de k-nearest neighbors, pas de tree, pas Delaunay ou Voronoi)... Aucune hypothèse sur les points, coordonnées en réel.
Log en base b.
oui.C'est donc du "fractional power" ?
et bien, ca m'en a tout l'air. Si je ne me goure pas N.10^(1-a.LogN) = 10.N^(1-a)N^Log_b a est équivalent à N 10^(1-a LogN) ??? (pas le même a, bien sûr)
Ok..
Super : log en base m de m, ça fait assez peu
Donc, en fractional power, est-ce que les best average et worst correspondent à :
best case : O(m) N quasi infini
worst case : O(mN) N petit
average case : O ( m N^c) avec la notation
?
Oui mes neurones et circuits divers ne se sont reconnctés que (encore une fois) ce matin en prenant mon café
Un très gros merci à toi
En fait, là ça n'est qu'une partie, mais il y en a 2 autres qui ont le même type de complexité, mais avec m à la place de N (donc beaucoup plus faibles), et du coup, le total de l'algo est avec cette complexité "fractional power"...
En dernier point, penses-tu que je puisse / doive appuyer la démonstration par un graphique comme le 2 ou le 4 , par exemple du temps total de l'algo en fonction de N, comme conclusion du paragraphe sur la complexité ?
Est-ce que je peux / dois conclure par :
"It behaves in O ( n log(n) ) (the exact equation is O (n n^c))"
ou
"It behaves in O ( n n^c ) (which in average behaves like O ( n log(n) )"
ou est-ce que je laisse juste "fractional power", en donnant la valeur numérique de l'exposant trouvée d'après le graphique ?
PS: vu l'aspect "sensible" de certains de mes posts ici, je vais juste en "éditer" un ou 2 pour les rendre un peu moins précis, maintenant que vous les avez lus et répondus.. Ce sera public d'ici peu, mais en attendant... (et je me ferais un plaisir de mettre les pointeurs soit ur Contribuez soit dans les FAQ)
PPS: un gros merci à vous, et en particulier à toi, Xavier, et toutes mes excuses pour être un peu dur à la comprenette avec ces notions et notations, qui me sont pas mal étrangères...
Pour moi, ce sont deux choses différentes.
La complexité en O(...) mesure le "comportement" de l'algorithme par rapport à la taille des données d'entrée (linéaire, logarithmique, linearithmique, exponentiel, ... ).
Les graphes mesurent la "performance" de l'algorithme pour des sets usuels/spécifiques de données d'entrée (nuage éparse, points d'attraction, cas dégénérés, ....)
... Ils sont pourtant révélateurs du comportement en fonction de la taille de l'entrée, non ?? (en tous cas pour le nombre de points pour l'étape dont je parlais ici. Mais également pour le temps en fonction de N, si on prend le temps comme relatif et non absolu)
Mais OK, donc je ne les inclue pas...
Il faudra cependant que j'en inclue pour "définir" le m attendu en fonction de N et des 2 autres paramètres d'entrée, car je n'ai absolument aucune théorie pour supporter un tel calcul...
Je ne sais même pas si il y a une théorie donnant le nombre de points d'une enveloppe convexe par rapport au nombre de points d'un nuage (je n'y crois guère, vu qu'on peut avoir le même nombre de points dans l'enveloppe avec un nuage de 10 points qu'avec un nuage de 500 000)
Là, pour un contour concave, il doit cependant y avoir une "certaine" relation entre les 2, en fonction des paramètres ... Puisque au pire on passerait par tous les points...
Ca dépend de tes données.
A priori, j'aurais tendance à dire que si tu fais une PCA, le 2nd plus grand axe te donne une information sur le nombre de points que tu vas devoir explorer par segment projeté sur le 1er plus grand axe.
Sinon... Le cas dont tu parles : 10 points sur l'enveloppe pour 500k dans le nuage, c'est un cas dégénéré où tu as plusieurs outliers, clairement.
Je ne sais pas ce qu'est une PCA..
Là je ne parlais de toutes façons pas du nbe de points utilisés, mais du nombre de points final dans l'enveloppe...
euh.....
1) je parlais de contour convexe
2) prend n'importe quel nuage de points et cherche son enveloppe convexe : quelque soit le nombre de point dans le nuage, tu auras sans doute dans les 20-30 points au grand max dans l'enveloppe... (bien sûr, ça peut être plus grand, mais c'est sans aucune commune mesure avec le nombre de points du nuage : et c'est ce que je dis : je ne voyais pas comment on peut trouver une théorie donnant le nombre de points ATTENDUS d'une enveloppe convexe en fonction du nombre de points du nuage)
PCA : principal component analysis.
Un ensemble de points étant donné, ça te permet de récupérer les axes (ou dimensions) qui présentent la variance la plus importante.
Sinon, tu prends ce nuage de points :
Tu as 200 points dans le nuage et 200 points dans l'enveloppe convexe. (Je parlais de l'enveloppe convexe aussi).
Et tu as un axe à angle, ce qui te demande de faire des calculs d'angles pour le tri, plus des calculs pour la PCA..
Pas terrible
ok, c'est le seul cas particulier pour une enveloppe convexe
(et ça n'existe pas trop dans la nature)
de toutes façons dans ce cas mon algo s'est arrêté au stade convexe, qui est en O(Nm), et donc en dans ce cas en O(N^2), comme la plupart des autres (j'utilise un algo connu)
Ce que je voulais dire c'est que EN DEHORS DE CE CAS, je ne connais aucune règle permettant de prédire le nombre de sommets de l'enveloppe convexe...
Sur l'image ci-dessous, tu dois en gros avoir le même nombre de sommets convexes, et pourtant les nombres varient grandement.. (et je peux te sortir des nuages avec 50 000 ou 100 000 points, même avec des clusters dedans, pour lesquels ce sera strictement identique)
On s'est mal compris. Pour moi les 2 informations sont importantes: la complexité et la mesure de performance. C'est simplement que l'une et l'autre ne montrent pas la même chose.
La complexité représente "la forme" de la courbe, mais comme on masque le facteur d'échelle ca ne donne pas du tout d'indication sur la performance.
Par exemple, tu peux avoir un algo qui fait 9874*N*Log(N) opérations, et un autre algo qui fait 3*N² opérations. Pour 1000 data en entrée, il y a un facteur 10 en faveur du second algo.
d'accord avec ça
Mais c'est la comparaison entre 2 algos..
Mais si tu dis que tu as une complexité en N log(N), et que tu traces une courbe donnant le temps d'éxécution de CET algo en fonction de N, avec des N couvrant des domaines logarithmiques, tu dois bien avoir la même forme, non ?
Sans comparer entre 2 algos différents.
Juste pour confirmer le calcul de la complexité par un graphe du temps, non ?
Si j'ai une compleixté en N^2, si je trace une corube avec le temps d'exécution pour 10,20, 30, ... 100, ..1000, je dois bien avoir une courbe de puissance (les opérations sont les mêmes pour chaque essai, il n'y a que le N qui change), sur laquelle je peux superposer une courbe "exacte" de puissance carrée mise à l'échelle, non ??
C'est ce que je voulais dire...
Enfin, en physique c'est comme ça qu'on procède pour vérifier une théorie..
Le graphe ne peut pas vraiment servir de preuve, mais plutot d'indication sur le comportement (et donc sur la complexité). Les résultats obtenus dépendent grandement des données d'entrées : on peut, sans le vouloir, utiliser un cas particulier (best ou worst) et en déduire des choses fausses.
Généralement, le graphe est plutôt une confirmation du "bon" comportement de l'algo sur des sets de données usuels/spécifiques.
OK. Bon. En physique on le voit à l'envers : à part les cas particuliers, si ça marche en moyenne, et que les écarts sont symétriques, c'est que c'est bon..
(n'avoir que des cas particuliers sur 30, 50, ou 100 "nuages" non synthétiques mais naturels(au sens propre, c'est à dire tirés de la nature et pas d'un programme qui les fabrique) , ça paraît hautement improbable)
Maintenant, il y a encore une chose qui me chiffone :
Si l'algo suit une loi de "fractional power", logiquement la puissance (comme d'ailleurs iniqué dans le lien) devrait être fixe.
Or là, on se rend compte que pour 10 c'est 1/2 N, pour 50 c'est 0.2 N, pour 30 000 c'est 0.01 N...
J'ai essayé cette après-midi de reproduire la formule N^(1-a) avec un "a" mesuré sur la courbe, et ça donne des trucs aberrants...
je ré-essaierais demain...
Je m'y perd.. Snifffffff...
Faut pas oublier que la notation O(...) donne seulement l'allure générale sous forme d'une courbe "dominante" (=un majorant). On cherche généralement a indiquer le "plus petit dominant" parmi la liste usuelle : O(1), O(log n), O(n^c) c<1, O(n), O(n log n), O(n^c) c>1, ...
Personne ne s'attend a ce que la formule donnée reflète exactement le nombre d'opération de l'algo.
Par contre, il est possible que ton algo soit dominé par une courbe plus basse ( comme (log n)^c ou log*(n) ), mais si on ne peut pas le prouver ca reste une conjecture. Vaut mieux dire qu'on est "O(n^c) c<1" parce qu'on peut le prouver, et indiquer que les mesures de perfs semblent indiquer qu'on est dessous.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager