Discussion :

[Nemerle]

Petit problème qui s'est posé à notre team de dèv., on a une soluce, à voir si c'est optimal en temps de calculs

Considérez une liste L[1]...L[N] d'entiers avec disons N= 100 millions; la forme de cette liste a la propriété suivante: il existe une unique valeur maximale C tel que

- x<y<C entraîne L[x]>=L[y]>=L[C]
- C<x<y entraîne L[C]<=L[x]<=L[y]

Comment trouver le plus rapidement possible C ??

[Jean-Marc.Bourguet]

J'ai l'impression que tu t'es goure dans l'enonce. D'apres ce que tu dis ta liste est triee et n'importe quel indice peut etre C.

Liste pour moi implique un acces sequentiel, est-ce bien le cas?

[Nemerle]

désolé, corrigé: simplement la liste décroit de 1 à C puis croit de C à 100 millions

Pour liste, en fait c'est un array

[Graffito]

Bonjour,

Comment trouver le plus rapidement possible C ??

Une bonne petite recherche dichotomique. (je peux détailler si nécessaire).

[FrancisSourd]

Oui, une recherche dichotomoque sur les L[x+1]-L[x] trouve ton C en O(log N). On ne peut pas faire mieux si on ne connaît pas plus de propriétés "a priori" sur la liste.

[Nemerle]

Bien, maintenant qu'on est tous d'accord, je précise, dans l'algo a implémenter:

- la "forme" du tableau L est connue, mais aucune de ses valeurs n'est connue a priori. Je m'explique: si vous avez besoin de L[500] par exemple, vous devez appeler une fonction qui vous calcule la valeur et qui prend 1/1000 seconde; une fois calculée, vous pouvez la stocker si vous désirez la réutiliser.

- il y a différents "codes" pour implémenter une dichotomie, il faudrait le plus rapide.

J'aimerais bien voir un bout d'algo...

[Jean-Marc.Bourguet]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
begin := ...
beginV := T[begin]
onepastlast :=...
while begin+1 /= onepastlast loop
   mid := (begin+onepastlast)/2
   v := T[v]
   if v < beginV then
      beginV := v
      begin := mid
   else
      onepastlast = mid
   end if
end loop

le resultat se trouve dans begin.

[Nemerle]

La condition

Code :

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

begin+1 /= onepastlast

est en fait

Code :

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

begin+1 <= onepastlast

, c'est ça??

Dans tous les cas, ca ne marche pas:

Code :

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

1
2
3
4
5
if v < beginV then
      beginV := v
      begin := mid
   else
      onepastlast = mid

Exemple sur la liste 50 20 30 40 50 60

begin=1
one past last=6

A la première itération, mid=3 et comme 30<50, tu te places dans l'intervalle
begin=mid=3 et onepastlast=6, et tu as raté le minimum 20 pour 2 ...

[PulkoMandy]

Il ne faut pas comparer les nombres eux-mêmes, mais le signe de la différence de deux nombres consécutifs.
On peut donc faire une recherche dichotomique en considérant des couples d'éléments dont on peut dire s'ils sont du côté croissant ou du côté décroissant.
Avec un souci s'il y a égalité quand même... dans ce cas on peut chercher dans les nombres à côté jusqu'à en trouver un différent mais je ne suis pas sûr de la méthode la plus appropriée... est il probable ou fréquent d'avoir beaucoup de valeurs identiques successives?

[Nemerle]

oui

[PRomu@ld]

La méthode de jean-marc ne semble fonctionner que pour un tableau croissant (au sens large).

En fait tu peux adapter la méthode en comparant tes nombres par trois :

tu regarde le nombre du début de ton intervalle, celui du milieu et celui de la fin de l'intervalle.

Pour ton exemple ça devrait donner ça :

50 20 30 40 50 60

Tu regardes 50, 30 et 60. Ca décroit dans l'intervalle [1..3] et ça croit dans l'intervalle [3..6], il faut donc que tu cherches dans l'intervalle [1..3]

Ce qui donne :

50 20 30

Ca décroit dans l'intervalle [1..2] et ça croit dans l'intervalle [2..3], tu regardes donc dans l'intervalle [1..2] soit donc :

50 20

Comme il s'agit d'un intervalle simple, le tout est de prendre le plus petit des deux (intuitivement je dirais que c'est toujours le nombre de droite de l'ensemble mais j'ai un doute).

Ca fonctionne sur ton exemple mais en général ça doit être un peu différent notament aux cas particuliers. Par exemple, si tu as des valeurs comme ceci :

10 5 20 30 40 50 70

Ici, mid c'est 3 et c'est croissant dans l'intervalle [1..3] et dans l'intervalle [3.6]. Il faut donc choisir l'intervalle [1..3].

Par contre autre cas particulier plus embêtant :

50 40 30 20 10 60 70

Ici, si on suit ce que j'ai dis au début on devrait choisir le premier intervalle. Il faut donc trouver quelque chose d'un poil plus performant.

Je pense qu'il faut en plus de l'étude des points particuliers s'interresser aux valeurs qui sont situées de part et d'autre de ton millieu, ça résout le problème du choix d'intervalle (en tout cas pour les cas particuliers que j'ai trouvé).

Reste à voir s'il n'y a pas de cas particuliers que je n'aurai pas vu, mais je pense que l'idée peut être là.

Pour la complexité, je pense qu'aux constantes près on doit être dans le même ordre de grandeur qu'une recherche dichotomique sur un tableau trié.

[Nemerle]

je vous proposerai notre algo lundi prochain (je pars en déplacement)

Les idées de prom@ld vont dans le bon sens, avec 1 ou 2 points à ajouter.

[Jean-Marc.Bourguet]

Idee principale: on maintient b <= Sol < e et min l'indice qui a eu l'evaluation la plus petite. On fait tout evoluer sur le principe

On peut reduire e a l'indice le plus petit superieur a b ayant une evaluation superieure a l'evaluation de b (phase d'initialisation uniquement)

On peut reduire e a l'indice le plus petit superieur a min ayant une evaluation superieure a l'evaluation de min.
On peut augmenter b jusqu'a un de plus que l'indice le plus grand inferieur a min ayant une evaluation superieure a l'evaluation de min.

Ca se trouve bien par dicotomie cette fois et on a donc une nouvelle valeur pour min (ou une valeur initiale pour la phase d'initialisation).

Quand on tombe sur un plateau apparent, on fait une recherche sequentielle.

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
b :=           -- indice minimal valide
e :=           -- un de plus que l'indice maximal valide
-- on maintient partout l'invariant b <= Sol < e
bV := T(b)
min := b       -- indice qui a eu l'evaluation la plus petite
minV := bV
 
-- faisont en sorte que e soit le premier indice avec une valeur plus grande
-- que celle evaluee en b
while bb+1 /= e loop
   m := (bb+e)/2
   mV := T(m)
   if mV > bV then
      e := m
   else
      if mV < minV then
         minV := mV
         min := m
      end if
      bb := m
      bbV := mV
   end if
end loop
 
-- des qu'on a b+1 == e, on a trouve
while b + 1 /= e loop
   if minV == bV then
      -- on a potentiellement un plateau, parcourons le avec des pas
      -- de plus en plus petit jusqu'a trouve un point bas
      s := 2
      while b + s < e loop
         s := 2*s
      end loop
      while min == b and s /= 1 loop
         m := b + s/2
         while min == b and m < e loop
            mV := T(m)
            if mV < minV then
               -- on a trouve un point bas, mettons tout a jour en reduisant
               -- l'intervalle de recherche au maximum
               min := m
               minV := T(m)
               b := m - s/2
               bV := T(b)
               if b+s < e then
                  e = b+s
               end if
            end if
            m := m + s
         end loop
         s := s/2
      end loop
      if min == b then
         -- on n'a pas trouve de point bas, c'est qu'on a bien un plateau,
         -- solution arbitraire: le premier point de l'intervalle trouve
         -- (qui n'est pas necessairement le premier point du plateau)
         e := b+1
      end if
   else
      pivot := min
      pivotV := minV
      -- faisons en sorte que b soit le plus grand indice inferieur a pivot
      -- avec une evaluation superieur a pivotV
      ee := min
      while b+1 /= ee loop
         m := (b+ee)/2
         mV := T(m)
         if mV > pivotV then
            b := m
            bV := mV
         else
            if mV < minV then
               min := m
               minV := mV
            end if
            ee := m
         end if
      end loop
      -- et on peut augmenter b de 1 sans casser l'invariant (et ca assure
      -- que l'algo se termine)
      b := b+1
      bV := T(b)
      -- faisont en sorte que e soit le plus petit indice superieur a pivot
      -- avec une evaluation superieur a pivotV
      bb := pivot
      while bb+1 /= e loop
         m := (bb+e)/2
         mV := T(m)
         if mV > pivotV then
            e := m
         else
            if mV < minV then
               minV := mV
               min := m
            end if
            bb := m
            bbV := mV
         end if
       end loop
   end if
end loop

[coyotte507]

Moi voici ma solution:

Tu mets déjà 2 variables, BorneInf et BorneSup. Ce sont des tableaux à deux dimensions qui contiennent les bornes de l'intervalles sur lequel tu travailles, ainsi que leur valeur.

On diminue borneSup et augmente borneInf au fur et à mesure des calculs.

Pour faire simple, voila l'algo:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
Si borneSup - 1 = BorneInf, alors tu compares les valeurs de borneSup et borneInf pour savoir qui possède C
 
Tu prend la valeur qui correspond à l'indice moyen de l'intervalle [borneSup - BorneInf]
  >Si elle est supérieure à celle de borneInf, cet indice moyen devient la nouvelle BorneSup et tu reprends du début
  >Si elle est supérieure à celle de borneSup, dans ce cas cet indice moyen devient la nouvelle BorneInf et tu reprends du début
 
  >Sinon tu prends la valeur de l'indice moyen +1 et tu obtiens le sens de variations en ce point précis du tableau
    >Si ca décroit, indiceMoyen +1 devient la nouvelle borneInf et tu reprends du début
    >Si ca croit, indiceMoyen devient la nouvelle borneSup et tu reprends du début
  finsi
finsi

Algo assez simple, entièrement rédigé en francais. Le seul points qu'il faut rajouter dans la derniere phase au cas ou les deux points sont identiques:

vérifier si on peut continuer d'explorer l'intervalle sans collision avec les bornes, reprendre le bloc avec IndiceMoyen -1 et IndiceMoyen+1 et ainsi de suite jusqu'à ce qu'ils ne soient plus identiques.

Si c'est dur à comprendre je le ferais plus clair mais la j'y vais