Facteur de division dans une recherche dichotomique

Facteur de division dans une recherche dichotomique - Algo - Programmation

Marsh Posté le 11-09-2008 à 10:43:25    

Ca fait un peu longtemps que j'ai fini mes études, et j'ai eu tous les types de profs imaginables.
 
J'ai le souvenir encore frais qu'un jour on m'a dit qu'une recherche dichotomique  était encore plus optimisée si au lieu de couper l'espace de recherche à la moitié, on le coupe au tiers. (a chaque itération)
 
Je me souviens d'une preuve au tableau basée sur les suites géométriques statistiques. Ca se tenait, et en pratique ca marchait.
 
Mais maintenant que tout ca est loin derrière moi, j'aimerai retrouver un papier la dessus... est ce que l'un de vous aurais un lien, ou pourrait faire la preuve de cette hypothèse ?
 
En plus, c'est bon à ajouter dans vos algo, il suffit de changer un 2 en 3...

Reply

Marsh Posté le 11-09-2008 à 10:43:25   

Reply

Marsh Posté le 11-09-2008 à 11:37:03    

la complexité d'un parcours  est de l'ordre du log ( en base 2 ) , multiplié par le cout de chaque comparaison

 

si tu coupe en 3 , tu vas avoir un cout de l'ordre du log ( en base 3 ) multiplié par le cout de comparaison , tu gagne donc

 

mais l'avantage de couper en deux c'est que tu as d'un côté ce qui est plus grand et de l'autre ce qui est plus petit . Comment tu coupe en 3 , sans que le cout de l'opérateur de comparaison n'explose ?  


Message édité par flo850 le 11-09-2008 à 11:37:19
Reply

Marsh Posté le 11-09-2008 à 13:59:00    

Tu gagne certes mais l'operateur de selection en 3 parties doit avoir une méchante geule.

Reply

Marsh Posté le 11-09-2008 à 14:09:01    

hmpf, je viens de comprendre vos réponses par rapport à la question en haut.
 
j'avais compris qu'il coupait toujours en 2, avec un rapport 1/3 et 2/3, de façon à, quand on a de la chance, virer les 2/3 d'un coup.
 
sauf que déjà j'étais pas convaincu du gain, mais surtout je pigeais pas pourquoi vous trouviez ça compliqué (puisque dans ce cas c'est toujours > ou < :D)
 
bon, je retourne hiberner

Reply

Marsh Posté le 11-09-2008 à 14:10:05    

sinon, pour un tri dans un tableau avec pivot (quicksort) , on prefere coupé par nu pivot pris au hasard que de couper 'exactement' en deux  
c'est ce que qui donne les meilleurs resultats

Reply

Marsh Posté le 11-09-2008 à 14:16:11    

oui mais bon, y a toujours que 2 morceau et donc le sélecteur est simple.

Reply

Marsh Posté le 11-09-2008 à 14:34:32    

exactement,  et coupé au 1/3 apporte les mêmes contraintes que couper au 1/2 , ca change rien , ce sera toujours moins bon  que de couper au pifomètre

Reply

Marsh Posté le 17-09-2008 à 09:30:05    

C'est pas tout à fait ca, on ne coupe pas en 3, au coupe à 1 tiers !!!
 
On a ce qui est plus petit 1/3   d'un coté, et ce qui est plus grand 2/3 de l'autre.
 
Mais vous venez de me rappeler que le quicksort utilise un pivot aléatoire...
Enfin, le coup du 1/3 2/3  c'est toujours bon à prendre dans les algo embarqué ou on ne peut pas avoir de fonction rand... (dans les shaders par exemple)


Message édité par NounouRs le 17-09-2008 à 09:32:26
Reply

Marsh Posté le 17-09-2008 à 09:31:16    

alors pas d'interet  
mieux vaut faire confiance au chaos et couper au hasard

Reply

Marsh Posté le 17-09-2008 à 09:54:17    

sauf quand il n'y a pas de rand dispo comme le dit nounours ;)

Reply

Marsh Posté le 17-09-2008 à 09:54:17   

Reply

Marsh Posté le 17-09-2008 à 10:18:05    

pas de rand, tu coupe en 2 c'est strictement pareil.

Reply

Marsh Posté le 17-09-2008 à 11:33:01    

(après, je ne me prononce pas sur l'éventuelle optimisation du 1/3 2/3, nounours a l'air sûr de lui, même si ça me semble étrange, pour moi ça ne fait qu'augmenter l'écart type des ittérations, sans en changer la moyenne)

Reply

Marsh Posté le 17-09-2008 à 18:02:08    

exactement.

Reply

Marsh Posté le 23-10-2008 à 20:28:12    

Sinon si tu as n éléments tu peux couper en n, comme ça t'as qu'une itération... Mais n tests :D Couper en 2, 3 ou plus, c'est une histoire de compromis entre le temps nécessaire pour une itération, qui augmente avec le nombre de morceaux, et la profondeur moyenne de la recherche, qui diminue avec le nombre de morceaux.

Reply

Marsh Posté le 23-10-2008 à 21:25:26    

matafan a écrit :

Sinon si tu as n éléments tu peux couper en n, comme ça t'as qu'une itération... Mais n tests :D Couper en 2, 3 ou plus, c'est une histoire de compromis entre le temps nécessaire pour une itération, qui augmente avec le nombre de morceaux, et la profondeur moyenne de la recherche, qui diminue avec le nombre de morceaux.


 
La blague c'est que l'exemple classique de méta-prog, c'ets le tri à bulle sur N valeurs entièrement déroulé. Ca ressemble à ça, et on voit que tant que N < 10 on gagne genre 20%

Reply

Marsh Posté le 23-10-2008 à 22:06:10    

Je suis pas sur de bien comprendre votre histoire:
- couper en 2, en faisant 2 comparaisons, tu peux choisir parmi 4
- couper en 3, en faisant 2 comparaisons, tu peux choisir parmi 3
- couper en 4, en faisant 3 comparaisons, tu peux choisir parmi 4
 
euh, c'est moi, ou bien couper en 2 c'est la meilleure façon ? Parce qu'à diviser par n > 2, tu perds progressivement l'avantage de la dichotomie plus n grandit

Reply

Marsh Posté le 23-10-2008 à 22:07:47    

Joel F a écrit :


 
La blague c'est que l'exemple classique de méta-prog, c'ets le tri à bulle sur N valeurs entièrement déroulé. Ca ressemble à ça, et on voit que tant que N < 10 on gagne genre 20%


wof méta ou pas, quand tu implémentes un tri, dès que tu passes sur N petit, un tri par insertion ou de même complexité, ça casse tout. j'irais quand meme pas à faire un bulle :)

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed