Discussion :

[greenHor]

Bonjour,
Mon but est d'améliorer la complexité de ma solution au problème suivant :
On a un tableau d'entiers t = [t1 < t2 ... < tn]. Le but est de compter le nombre de triplets ti , tk , tj tels que tk - ti = tj - tk.
Ma solution s'exécute en O(n²) (en Python):

s = 0
for k in range(1, n-2):

i,j = k-1, k+1

temp = 2 * t[k]

while i >= 0 and j < n:

if t[i] + t[j] == temp:

s+=1

i-=1

j+=1

elif t[i] + t[j] < temp:

j+=1

else:

i-=1

Par exemple, [1,3,4,5] va donner s = 2.

Y a-t-il une solution plus efficace ?
Merci

[wiwaxia]

Bonjour,

L'idée de partir de (k), puis d'élargir les bornes (i, j) est inattendue.
J'ai pratiqué un peu le Python, et la lecture de ton programme - pour autant que je l'ai bien compris - appelle deux remarques:
a) (k) ne varie-t-il pas entre (2) et (n - 1), puisqu'il est strictement compris entre (i) et (j), donc entre (1) et (n) ?

Code :

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

1
2
 ... On a un tableau d'entiers t = [t1 < t2 ... < tn] ... 
for k in range(1, n-2):

b) Le programme fonctionne-t-il correctement sur des listes très dissymétriques, par exemple:
t = (1, 4, 9, 16, 25, 36, 41, 49, 64, 81, 100) ?

La suite étant ordonnée, je serais spontanément parti des indices extrêmes; tu traduiras facilement ce qui suit:

Code :

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

1
2
3
4
5
6
7
8
9
FOR k:= 1 TO n DO u[k]:= 2 * t (k );
s:= 0;
FOR i:= 1 TO (n - 2) DO
  FOR j:= (i + 2) TO n DO
    BEGIN
      a:= t[i] + t[j]; 
      FOR k:= (i + 1) TO (j -1) DO
        IF (u[k]=a) THEN Inc(s)
 ...

Le calcul des valeurs doubles est consigné une fois pour toutes dans un second tableau (u) isotype de (t).
La complexité n'est sans doute pas diminuée, mais les calculs un peu plus rapides sur une plus longue liste.

[greenHor]

Merci de ta réponse
Effectivement, en fait t = [t0 < t1 ... < t(n-1)]
Donc le n-2 devient n-1 (le range va aller de 1 à n-2)

Ensuite, je pense qu'il fonctionne : pour le prouver, on peut d'abord dire que un élément "milieu" est forcément entre 1 et n-2:
-si tk-1 et tk+1 marchent, alors on incrémente s (premier cas) et on sais que tk-1 ne marchera avec rien d'autre (puisque les éléments sont distincts et triés) et c'est la même chose pour tk+1 -si tk-1 + tk+1 < 2*tk, alors on sais que tk+1 ne marchera avec rien à gauche de tk (puisque tout les ti avec i<k-1 sont plus petits que tk-1)
-on a la même chose pour le cas >

Merci pour ta proposition : à première vue elle est en n^3, mais je vois comment la passer en n².

[tbc92]

J'ai l'impression que la solution de Wiwaxia est beaucoup plus lente que la solution proposée par GreenHor.

La solution de GreenHor me paraît quasiment optimisée. On doit quand même pouvoir faire mieux en passant par des dictionnaires. Si on reprend les données de Wiwaxia, on va inverser le stockage, en disant Dico[1] = 1,Dico[4] = 2,Dico[9]=3 etc ...
Ainsi quand on a calculé 2*t[k] - t[i], on peut déterminer immédiatement si il existe un j tel que t[j] = 2*t[k]-t[i], plutôt que passer par une boucle. Mais par rapport à la solution de GreenHor, le bénéfice me paraît minime.

Si on veut,on doit aussi pouvoir stocker d'une part les t[i] impairs, et d'autre part les t[i] pairs... et ainsi, pouvoir aller plus vite. Si t[i] + t[j] = 2*t[k], forcément t[i] et t[k] sont de même parité. Mais le bénéfice paraît minime.

[greenHor]

Merci !
n² est vraiment trop pour moi, alors je pense que mon vrai problème (duquel découle celui-ci) a une solution plus rapide qui n'utilise pas cette simplification.

[tbc92]

Et par curiosité, n est de quel ordre de grandeur, et aussi, les t[k] sont de quel ordre de grandeur ?

[greenHor]

Les deux sont de l'ordre du million, et j'ai une seconde pour tout faire

[wiwaxia]

J'ai oublié de tenir compte de la nécessaire parité de la somme (ce qui automatiquement réalisé dans le cas de ton programme), et cela dispense d'effectuer la moitié (en gros) des vérifications:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
FOR k:= 1 TO n DO u[k]:= 2 * t (k );
s:= 0;
FOR i:= 1 TO (n - 2) DO
  FOR j:= (i + 2) TO n DO
    BEGIN
      a:= T[i] + t[j];
      IF (a MOD 2 =0) THEN 
        FOR k:= (i + 1) TO (j -1) DO
          IF (u[k]=a) THEN Inc(s)
 ... 
    END;

[greenHor]

Merci ! Je vois, mais avec un million, mon programme tourne en quelques minutes, alors qu'il faut que je passe à moins d'une seconde, alors il y a forcément une simplification avec le problème initial.

[tbc92]

Il faut que tu passes à moins d'une seconde .. parfois, mon patron me demande un outil pour aller de Paris à Marseille en 3 minutes, et je lui réponds : je n'ai pas de solution, désolé.
En terme d'algorithme, tu peux envisager un pré-traitement pour séparer les t[i] pairs des impairs, ça va diviser par quasiment 2 le temps de traitement, mais il faudra en plus ce pré-traitement, et ça va compliquer un peu le traitement. Personnellement, je ne vois vraiment pas d'autre amélioration.

Ensuite, il y a d'autres aspects. On ne met plus en cause l'algorithme, mais l'aspect purement I.T. Pour ces questions, il y a probablement des sous-forimes plus adaptés que le forum algorithme.

Ici, tu utilises du Python. Pour les boucles, Python est très lent comparé à du C par exemple. Je ne connais pas le ratio, mais à algorithme égal, en utilisant du C, tu vas nettement améliorer la performance. Est-ce que ça va suffire, je ne sais pas, mais je n'exclue pas.

Tu peux aussi passer par de la parallélisation. Par défaut, avec une boucle comme celle que tu proposes, tu as un seul processeur qui bosse. Si d'une façon ou un autre, tu confies un quart du boulot à chacun de tes 4 processeurs, tu divises le temps par 4. A vérifier, en regardant la charge des processeurs dans le gestionnaire de taches quand tu fais tourner ton programme actuel.


Dernier point, tu dis que tu as n = 1 Million de valeurs, comprises en gros entre 0 et 1 ou 2 millions... Et donc, tu as probablement des valeurs en doubles ou en triples ... Si tu as T[i]=T[i+1]=T[i+2] , tu vas recenser le triplet
(i,i+1,i+2) comme solution au problème, est-ce voulu ?

[greenHor]

Ahaha non non, je suis étudiant en maths et j'ai simplifié l'exo 5 de Prologin en ça, ce qui apparemment risque d'être insuffisant.
Je vais continuer à chercher, mais merci pour votre aide !

[wiwaxia]

Une variante de l'algorithme précédent, qui consiste à arrêter l'énumération de (k) dès que l'on a atteint ou dépassé la limite cherchée permet de réduire le temps de calcul d'un facteur ~ 2.4

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
     Nr:= 0; 
     FOR i:= 1 TO (Nval - 2) DO
       FOR j:= (i + 2) TO Nval DO
         BEGIN
           s:= L_1[i] + L_1[j];
           IF (s MOD 2 =0) THEN
             BEGIN
               k:= i+1;
               WHILE (L_2[k]<s) DO Inc(k);
               IF (L_2[k]=s) THEN Inc(Nr)
             END
         END;

Mais cela reste effectivement très lourd, le temps de calcul étant proportionnel à (N_val)³.

Par contre une 3^me version, dans laquelle on impose au 3^me paramètre (k) la valeur initiale médiane (i + j) DIV 2 réduit le temps d'un facteur ~ 30 à 64 (pour N_val = 4000 à 8000).

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
     Nr:= 0; 
     FOR i:= 1 TO (Nval - 2) DO
       FOR j:= (i + 2) TO Nval DO
         BEGIN
           s:= L_1[i] + L_1[j];
           IF (s MOD 2 =0) THEN
             BEGIN
               k:= (i + j) DIV 2;
               IF (L_2[k]>s) THEN REPEAT
                                    Dec(k)
                                  UNTIL (L_2[k]<=s)
                             ELSE WHILE (L_2[k]<s) DO Inc(k);
               IF (L_2[k]=s) THEN Inc(Nr)
             END
         END;

Mieux encore, l'augmentation du temps de calcul deviens moins rapide, celui-ci apparaissant désormais proportionnel à (N_val)².

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
 
Nval	     Ntrip  Version 1  Version 2  Version 3  Ntrip/Nval<sup>2</sup>
 
 1000	     45716     0.28 s     0.16 s     0.03 s     0.045716
 
 2000	    178846     2.30 s     1.03 s     0.05 s     0.044712
 
 4000	    719519    17.98 s     7.66 s     0.25 s     0.044970
 
 8000	   2856693   143.12 s    58.95 s     0.92 s     0.044636
 
10000      4466663                           1.48 s     0.044667
 
30000     40785915	                    17.43 s     0.045329
 
100000   454508146                         200.20 s     0.045451

Le nombre de triplets trouvés (i, k, j) apparaît lui aussi proportionnel à (N_val)²; il paraît donc difficile d'espérer un algorithme moins lourd, puisque le dénombrement des solutions implique de les énoncer une par une (à moins qu'une astuce de programmation ne permette leur regroupement).
Les résultats ont été obtenus à partie de séquences aléatoires strictement croissantes, définies par la relation de récurrence:
t[k + 1] = t[k] + 1 + Random(10) .

Le code initialement proposé par greenHor semble pour l'instant le meilleur.

[tbc92]

Peux-tu donner un lien vers l'énoncé original de l'exercice ?

[anapurna]

salut

si c'est des triplet un simple boucle avec un pas de 2 devrais suffir

K := 1;
While K <= N-1 do
Begin
if Tab[K-1] - Tab[K] = Tab[K] - Tab[K+1] Then
Selection(Tab,K)
Inc(K,2)
End;

[tbc92]

@Anapurna
Non, si on prend l'exemple donné au début, avec le jeu de données [1,3,4,5], il y a 2 solutions ... et ce sont les triplets (1,3,5) et (3,4,5).
Les 3 valeurs i,j,k ne sont donc pas forcément consécutives.
Pour un exercice de programmation, ça aurait été un peu trop simple.

[anapurna]

Salut

ok ... après je connais pas le niveau de développement demandé ^^
effectivement cela complexifie un peu le truc
je suppose qu'il ne cherche pas des valeur symétrique par rapport au pivot non plus ?

bon on sais que k et la valeur pivot
donc la recherche d'un cote et de l'autre seras limite par cette valeur pivot

IMin => K-1..0 (GAUCHE)
IMax =< K+1..N (DROITE)
On sais que la liste est trié par ordre croissant

EcartMin := Tab[K] - Tab[K-IMin]
EcartMax := Tab[K+IMax] - Tab[K]
la recherche est valide que si (EcartMin <= EcartMax) et que Imax est entre K+1..N
tes boucle de recherche peuvent etre inverse des que tu depasse la moitie du tableau
il est préférable de faire tes recherche sur la parti la plus petite

je verrais bien un truc dans ce genre la

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
S :=0
While K < N-1 do 
begin
   if  K < (N DIV 2) Then 
   BEGIN
       I := K-1
       While  I > 0 do 
       BEGIN 
         IMIN :=  TAB[K]-TAB[I]
         IMAX :=  TAB[K+1]-TAB[K]
         J:= K+1 
         While IMAX <=  IMIN Do 
         BEGIN
            IMAX :=  TAB[J]-TAB[K]
            IF IMAX =  IMIN Then 
               S := S+1;
            INC(J)
         END
          DEC(I)
       END
   END
   ELSE
   BEGIN
       J := K+1
       While  J < N do 
       BEGIN 
         I:= K-1 
         IMIN :=  TAB[K]-TAB[I]
         IMAX :=  TAB[J]-TAB[K]
         While IMAX >=  IMIN Do 
         BEGIN
            IMIN :=  TAB[K]-TAB[I]
            IF IMAX =  IMIN Then 
               S := S+1;
            DEC(I)
         END
          INC(J)
       END
   END; 
END;

[greenHor]

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
Crêpes parfaites – Qualification 2018
 
Niveau 5
Énoncé
 
Joseph Marchand se lance un défi, il doit produire une crêpe tout en se promenant sur la plage, promenade qui doit satisfaire certaines contraintes qu'il a définies à l'avance.
 
Il a commencé par dessiner des disques à certains endroits sur le sol qu'il numérote de 0 à N - 1, le disque 0 correspondant à l'emplacement de son stand à crêpes. Sur chacun d'entre eux, il plante une pancarte indiquant 2 directions pointant chacune vers respectivement 2 autres emplacements.
 
Sa promenade doit commencer à l'instant 0 au niveau de son stand et à chaque disque rencontré il doit prendre une des deux directions indiquées selon le critère suivant :
 
    la première si le nombre de 1 dans l'écriture binaire du nombre de disques déjà rencontrés est pair
 
    la seconde sinon
 
Joseph tient à ce que sa crêpe soit parfaite, pour cela il faut impérativement qu'elle soit retournée pile au milieu du temps de cuisson. Pour pouvoir réaliser une telle crêpe il faut donc qu'il se trouve au niveau de son stand aux instants T, T+t puis T+2t où T est l'instant de début de cuisson, et t la durée de mi-cuisson, cela sachant qu'il met exactement une seconde (il est très rapide) pour se déplacer d'un disque à l'autre.
 
À l'instant 0 il met en marche sa poêle, et il ne peut pas lancer directement la cuisson d'une crêpe, il lui faudra attendre au moins son prochain retour sur son stand. Par ailleurs, comme il n'est pas infatigable, Joseph arrêtera sa promenade après la seconde L (il peut encore arrêter la cuisson d'une crêpe à cet instant).
 
Combien Joseph a-t-il de manières différentes de réaliser une crêpe parfaite ?
Entrée
 
La première ligne contiendra 2 entiers L et N, la durée de sa promenade et le nombre de disques qu'il a tracés sur le sol. N lignes suivront, la i-ème d'entre elles contiendra 2 entiers qui correspondront dans l'ordre aux 2 directions sur le i-ème disque.
Sortie
 
Vous afficherez un seul entier : le nombre de manières différentes pour Joseph de réaliser une crêpe parfaite pendant sa promenade.
Contraintes
 
    1≤N≤2 500
    1≤L≤2 000 000
 
Attention ! Il n'y a pas de tests de performance pour ce problème, c'est à dire que pour valider les tests de correction il faut déjà avoir la bonne complexité (ie une solution correcte mais trop lente sera jugée non valide).
Contraintes d'exécution
 
Utilisation mémoire maximum
    64000 kilo-octets
Temps d'exécution maximum
    1000 millisecondes
 
Exemples d'entrée/sortie
 
Exemple d'entrée
 
    9 3
    1 2
    1 2
    0 0
 
Exemple de sortie
 
    1
 
Commentaire
 
    Joseph commence à compter :
 
        0 a un nombre pair (0) de bits à 1, il va donc au disque 1
        1 a un nombre impair (1) de bits à 1, il va donc au disque 2
        2 a un nombre impair (1) de bits à 1, il va donc au disque 0 (son stand à crêpe)
        3 a un nombre pair (2) de bits à 1, il va donc au disque 1
        4 a un nombre impair (1) de bits à 1, il va donc au disque 2
        5 a un nombre pair (2) de bits à 1, il va donc au disque 0 (son stand à crêpe)
        6 a un nombre pair (2) de bits à 1, il va donc au disque 1
        7 a un nombre impair (3) de bits à 1, il va donc au disque 2
        8 a un nombre impair (1) de bits à 1, il va donc au disque 0 (son stand à crêpe)
 
    Joseph peut donc commencer à faire cuire une crêpe après 3 secondes, il retombera sur son stand à crêpe 3 secondes plus tard pour la retourner et enfin, 3 secondes après pour la manger.
 
Exemple d'entrée
 
    11 3
    0 1
    2 0
    0 1
 
Exemple de sortie
 
    5
 
Commentaire
 
    Les 5 manières de cuire une crêpe parfaite sont :
 
        3s par côté en commençant à T=1
        1s par côté en commençant à T=9
        3s par côté en commençant à T=4
        4s par côté en commençant à T=3
        2s par côté en commençant à T=7

Voilà voilà, le problème est beaucoup plus compliqué et je vais devoir faire ça autrement qu'en listant les retours à 0 bêtement.
Merci pour vos aides !

[tbc92]

L'énoncé du problème est compliqué. Mais le volume de données est a priori moindre que ce que tu disais.
Si tu as 1000 disques, et 2000000 secondes, Joseph va passer 'statistiquement' 2000 fois par le disque n°0. Tu as donc 2000 nombres compris entre 0 et 2000000.

Ce que je ferais :

Tb est un tableau de L booléens ( L = 2000000 au max
TB2 est un tableau de 0 entiers. // On va allouer des enregistrementq dans ce tableau autant que nécessaire (à chaque passage par le disque n°0).

On parcours le circuit du marchand de crèpes.
A chaque fois qu'il passe par le disque n°0, on fait :

Code :

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

1
2
3
tb[i]= 1  // i = le chronomètre.
nb_passages_par_0 ++
tb2[nb_passages_par_0] = i

Et immédiatement, on essaie de voir si on peut 'finir la cuisson d'une crèpe' :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
j = nb_passages_par_0 -1 ; ok = vrai
tantque ok = vrai
  instant_j = tb2[j]
  k = 2*instant_j - i 
  si k <= 0 alors 
      ok = faux
  sinon
      si tb[k] = 1 alors compteur ++
  fin
  j--
fin

[wiwaxia]

Si l'on avait été immédiatement informés de la dégustation de crêpes, on aurait pu s'attaquer sainement au problème après quelques bolées de cidre.

La suite (s[t]) des (L + 1) positions successives de la randonnée sur les (N) disques vérifie une relation de récurrence utilisant
a) la position actuelle (s[k]), ainsi que les correspondances figurant dans le tableau initial,
b) la suite booléenne de Prouhet-Thue-Morse,
et l'on cherche les retours au stand de crêperie (s = 0) à des instants également espacés, donc des triplets d'entiers (i, j, k) vérifiant:
s[i] = s[j] = s[k] = 0 ; 2*j = i + k .

Le dénombrement des triplets est réalisable par récurrence, en ajoutant les éventuels nouveaux qui associent l'instant actuel (k)
à deux instants antérieurs (i = k - 2*h , j = k - h); par exemple en codant:

Code :

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

1
2
3
4
5
6
7
8
9
10
Inc(k);
IF (S[k]=0) THEN
  BEGIN
    i:= k; j:= k;
    WHILE (i>2) DO 
      BEGIN
        Dec(i, 2); Dec(j);
        IF ((s[i]=0) AND (s[j]=0)) THEN Inc(Ntrip)
      END
  END;

La bouteille de chouchen est encore à moitié pleine, il me faut un remontant .

[wiwaxia]

L'étude la plus rapide des longs parcours envisagés oblige à recourir à une programmation dynamique, et à considérer l'ensemble des (N) positions possibles du randonneur comme un graphe polycyclique, dont chaque sommet comporte deux pointeurs orientés vers les directions associées.
Les instructions suivantes permettent de construire l'objet considéré, les directions étant déterminées par un procédé arithmétique (au lieu d'un choix manuel, comme dans l'énoncé du sujet).

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
 CONST NmaxP = 10;
 
 TYPE P_Point = ^Point;
      Point = RECORD  Valeur: Word;
                      Suiv_1, Suiv_2: P_Point  END;
      LstP = ARRAY[0..(NmaxP - 1)] OF P_Point;
 
 PROCEDURE InitDir(VAR Gr_: LstP);
   VAR h, i, j, k: Word;
   BEGIN
     FOR k:= 0 TO (NmaxP - 1) DO New(Graphe[k]);
     FOR k:= 0 TO (NmaxP - 1) DO
       WITH Gr_[k] DO
         BEGIN
           Valeur:= k;
           h:= 3 * k; i:= (h + 1) MOD NmaxP; Suiv_1:= Gr_[i];
           h:= 7 * k; j:= (h + 2) MOD NmaxP; Suiv_2:= Gr_[j]
         END
   END;
 
  InitDir(Graphe);

La suite de Prouhet-Thue-Morse, quant à elle, résulte du doublement réitéré en 19 étapes du doublet initial (True, False), avec inversion systématique des termes; La longueur finale du tableau est de 2²⁰ = 1048576 .
Son comportement remarquable peut être vérifié sur l'observation des 128 premières et 128 dernières valeurs.

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
 
 CONST B_20 = 1048576; // = 2^20
 
 TYPE LstB = ARRAY[0..(B_20 - 1)] OF Bool;
 
 VAR Morse: LstB;
 
 PROCEDURE InitM(VAR M_: LstB);
   VAR i: Byte; k, Min, Max: Z_32;
   BEGIN
     E(1015); Wt(12, 15, 'Min   Max - 1');
     Min:= 1; //Max:= 2;
     M_[0]:= True; M_[1]:= False;
     FOR i:= 1 TO 19 DO
       BEGIN
         Max:= 2 * Min; Min:= Max; Max:= 2 * Min;
         FOR k:= Min TO (Max - 1) DO M_[k]:= NOT M_[k - Min];
       END
   END;
 
  InitM(Morse);

__