Discussion :

[trihanhcie]

Bonjour,

Je suis peu rouillé niveau algo...
Supposons une matrice 2d avec des 0 et 1.

Je cherche à connaitre le nombre de groupe de 1 qui sont contenus dans la matrice. Les "1" font parti d'un meme groupe s'ils sont adjacents (horizontalement, verticalement ou oblique).

Exemple:
1 0 0 1
1 0 1 0
0 0 1 0
1 0 0 0

Retournerait 3

Quel est la meilleure manière de procéder. Je pensais créer une autre matrice ou je sauvegarderais les "index" que j'ai déjà parcouru mais je me demande si c'est la bonne méthode.

Merci

[Invité]

salut,

tu as plus simple.

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
 
    nbGroupe = 0
    pour chaque ligne
        pour chaque colonne
            si ta case courante est un 0 tu skip
            sinon
                groupeExistant = false
                pour les cases adjacentes (de la ligne du dessus, ou celle de droite) as candidate
                    si candidate==1 alors
                        //notre case courante appartient à ce groupe
                        groupeExistant = true
                    finsi
                finpour
                si groupeExistant == false alors
                    //cest le tout premier 1 isolé
                    nbGroupe++
                finsi
            finsi
        finpour
    finpour

[Flodelarab]

Bonjour

@galerien69 : Pardon, rien de personnel, mais je ne crois pas que ça marche.
Exemple:
1 0 0 1
1 1 1 0
0 0 1 0
1 0 0 0
A la première ligne, tu vas créer 2 groupes, alors qu'il s'agit du même (qui va se relier par la suite).


Personnellement, je ferais un système de coloriage.
Une case contenant un 1 prend un nombre et colorie tous ces voisins (égaux à 1) de ce nombre.
Le résultat est le plus grand nombre moins un.
Dans l'exemple initial, tu aurais les groupes 2, 3, 4. Donc, nombre de groupes: 3.

[Invité]

hello Flodelarab,

mais je ne crois pas que ça marche.

et tu as absolument raison

j'etais parti sur considérer des chaines (comme au go) donc comprendre chaque el d'une même chaine pointe vers la même valeur
lorsque deux chaines se rencontre (idem on compare la valeur pointée de deux cel "candidate" et celles-ci diffèrent), on met à jour la valeur pointée des deux pointeurs respectifs vers la même valeur (et on soustrait 1 au compte du nombre de chaine) puis dans l'euphorie de la simplification je m'y suis perdu.

je vais qd même tenter de corriger l'algorithme du premier poste (je suis convaincu qu'il n'y a pas besoin d'autant d'espace utilisé (pointeur à chaque fois) et qu'il n'y a pas non plus besoin de masques binaires pour représenter l'union de chaine par case)

edit: version corrigée de l'algo du premier poste. Je laisse le code.
Dans les grandes lignes:
meme check des cellules adjacentes (sauf que sur cellule de gauche au lieu de droite..)
etude du pattern
xxx
x1
avec le merge de chaine en fonction des valeurs de x (même idée de coloriage que Flodelarab sauf qu'appliqué à un plus petit motif)

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
 
    var nbGroupes=0;
    var id=0;//le premier id que nous allouerons vaudra 1
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)==0)continue;
            if(i==0){
                if(j==0){
                    nbGroupes++;
                    id++
                    P(i,j,id)
                }else{
                    //si i==0 on regarde pas les cases adjacentes du dessus... donc seul check sur case de gauche
                    if(M(i,j-1)){
                        P(i,j,M(i,j-1));
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)  
                    }
                }
            }else{
                if(j==0){
                    var oneOrOther = M(i-1,j)||M(i-1,j+1)
                    //si j==0 il y a au maximum une chaine
                    if(oneOrOther){
                        P(i,j,oneOrOther)
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)
                    }
                }else{
                    //trois cas: nouvelle chaine, existe 1 chaine, existent deux chaines distinctes
                    var c1 = null;//représente la valeur de la première chaine
                    var c2 = null;
                    var candidates = [M(i,j-1), M(i-1,j-1), M(i-1,j), M(i-1,j+1)]; //resp à gauche et les trois du haut
                    candidates.forEach(x=>{
                        if(x==0)return;
                        if(c1==null||x==c1){
                            c1 = x;
                        }else{
                            c2=x;
                        }
                    })
                    if(c2){
                        //la chaine "c1" prend les coeffs de la chaine c2
                        //on ne considere que les coeff de la ligne courante avant lel courant
                        //ainsi que ceux depuis la colonne "à droite" de lel courant sur la ligne précédente
                        //car c'est le seul cas ou on peut avoir deux chaines distinctes
                        //0  0  2
                        //1 <-  ^
                        nbGroupes--;
                        for(var j1 = 0; j1<=j; ++j1){
                            if(M(i,j1)==c1){
                                P(i,j1,c2)
                            }
                        }
                        for(var j1 = j+1; j1<m[i].length; ++j1){
                            if(M(i-1,j1)==c1){
                                P(i-1,j1)=c2
                            }
                        }
                    }else{
                        if(c1){
                            P(i,j,c1)
                        }else{
                            nbGroupes++
                            id++
                            P(i,j,id)
                        }
                    }
                }
            }
        }
    }
    return nbGroupes;
}
 
 
 
//useless below
var assert = require('assert');
function test(s,exp){
    var m = s.split('\n').map(x=>x.trim()).filter(x=>x.length).map(x=>x.split(/\s+/).map(y=>parseInt(y)));
    assert.equal(run(m), exp);
    return m;
}
/*
var m;
s = `
1 0 1
1 0 1
1 1 1
`;
test(s, 1)
 
s = `
1 0 1
0 1 1
0 1 0
`;
test(s, 1)
 
s = `
1 0 1
0 0 0
0 1 0
`;
test(s, 3)
 
 
s = `
1 0 1
0 0 0
0 1 0
`;
test(s, 3)
 
s =`
1 0 0 1
1 1 1 0
0 0 1 0
1 0 0 0
`
test(m,2)
 
 
s =`
1 0 0 1
1 0 1 0
0 0 1 0
1 0 0 0
`
test(s,3)*/
 
s = `
1 1 0 1
1 1 0 1
0 0 1 0
1 0 0 0
`
console.log(test(s, 2))//merge deux chaines

@flodelarab
je n'ai compris ta version qu'apres, mais effectivement, elle simplifie bcp l'algo

[trihanhcie]

Merci !!

La solution de Flodelrab me parle... mais je ne suis pas sur de l'algo
Par exemple,

1 0 0 1
1 0 1 1
1 0 0 0
0 0 0 1

M(0,0) = 1 ainsi M(1,0)
M(0, 3) = 2 car il n'a pas ete colorie et M(1,2) = 2 et M(1,3) = 2
M(1, 0) = 1 donc M(2,0)= 1
M(3,3) = 3 car il n'a pas ete colorie.

est ce que j'ai manque quelque chose?

[Flodelarab]

est ce que j'ai manque quelque chose?

Oui, le recoloriage.
Ce qui n'arrive pas si tu fais une récursivité.
Sinon, un groupe pourra être bicolore, tricolore... ou pire.

Je modifie un peu ton exemple:

1 0 0 1 0
1 0 1 1 0
1 0 0 0 1
0 0 1 0 0

M(0,0) = 2. Ainsi M(0,1) = 2. Ainsi M(0,2) = 2.
M(3,0) = 3. Ainsi M(2,1) = 3, M(3,1) = 3. Ainsi M(4,2) = 3
M(2,3) = 4.

2 0 0 3 0
2 0 3 3 0
2 0 0 0 3
0 0 4 0 0

Et pour être bien clair, tu vas traiter les voisins des voisins, avant de traiter les voisins.

[trihanhcie]

Je ne comprends pas trop ou est la faille dans ce que j'ai dit (ou alors je me suis mal exprime)

1 0 0 1 0
1 0 1 1 0
1 0 0 0 1
0 0 1 0 0

- Au 1e 1 que je trouve:

2 0 0 1 0
2 0 1 1 0
1 0 0 0 1
0 0 1 0 0

- je continue de parcourir la ligne jusqu au prochain >= 1 s'il existe et je colorie ses voisins. Si = 1, je colorie d'une autre couleur et je teste les voisins = 1 pour les colorier de la meme couleur

2 0 0 3 0
2 0 3 3 0
1 0 0 0 1
0 0 1 0 0

- A la ligne suivante, je teste >= 1. si > 1, cela veut dure que l element a deja ete colorie et je vais colorier les voisins de la meme couleur

2 0 0 3 0
2 0 3 3 0
2 0 0 0 1
0 0 1 0 0

- A la ligne j = 1, je continue de chercher >= 1 et colorie les 1. ici, M(1,2) = 3 et il n'y a pas d elements = 1. M(1,3) = 3 et M(2,4) = 1 donc je colorie M(2,4) = 3

2 0 0 3 0
2 0 3 3 0
2 0 0 0 3
0 0 1 0 0

- je continue j = 2, aucun element = 1
- je continue j = 3, M(3,2) = 1, donc M(3, 2) = 4

[Flodelarab]

Et quand 2 et 3 se rencontrent ? Que fais-tu ? (Ce qui n'est pas le cas ici)

[wiwaxia]

Bonjour,

Il faut apparemment dénombrer dans la matrice les séquences d'au moins deux termes positifs consécutifs, disposés horizontalement, verticalement ou parallèlement à l'une des diagonales.

L'inventaire des groupes dans une ligne de la matrice envisagée:

Code :

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

1
2
3
TYPE TabE = ARRAY[1..Nt, 1..Nt] OF Type_Entier;
VAR Mat: TabE;
// ... Initiallisation de la matrice

pourrait par exemple s'effectuer comme suit:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Nh:= 0;
 
FOR i:= 1 TO Nt DO                                               // Enumération des lignes
  BEGIN
    Nseq:= 0; N11:= 0;
    FOR j:= 1 TO (Nt - 1) DO          
      IF (Mat[i, j]=1) THEN
        IF (Mat[i, j + 1)=1) THEN BEGIN
                                    Inc(N11);                  // Comptage des doublets (1, 1)
                                    IF (N11=1) THEN Inc(Nseq)  // Comptage exclusif des séquences de 2 (1)
                                  END
                             ELSE N11:= 0;                     // Fin de la séquence de (1)
    Inc(Nh, Nseq)
  END;

fournissant ainsi le nombre (Nh) de "groupes" en disposition horizontale.

Les autres inventaires (Nv, Nd1, Nd2) ne devraient pas poser de difficulté.

[anapurna]

salut

on peut certainement l’amélioré mais de façon brut je l'aurait vu ainsi

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
procedure ChercheEtPeintVoisin(var Mat : TMat;Lig,Col,Couleur : Integer);
begin
  If ((Col >= low(Mat)) and (Col <= high(Mat)) )Then
   if((Lig >= low(Mat[0])) and (Lig <= high(Mat[0]))) Then
   begin
     if Mat[Col,Lig] = 1 Then
     begin
       Mat[Col,Lig] := Couleur;
       ChercheEtPeintVoisin(Mat,Lig-1,Col-1,Couleur);
       ChercheEtPeintVoisin(Mat,Lig-1,Col,Couleur);
       ChercheEtPeintVoisin(Mat,Lig-1,Col+1,Couleur);
       ChercheEtPeintVoisin(Mat,Lig,Col-1,Couleur);
       ChercheEtPeintVoisin(Mat,Lig,Col+1,Couleur);
       ChercheEtPeintVoisin(Mat,Lig+1,Col-1,Couleur);
       ChercheEtPeintVoisin(Mat,Lig+1,Col,Couleur);
       ChercheEtPeintVoisin(Mat,Lig+1,Col+1,Couleur);
     end;
   end;
end;
 
Procedure Process(var Mat : TMat)
var
 Col,Lig : integer;
begin
  For Col := low(Mat) To High(Mat) do
    For Lig := low(Mat[Col]) To High(Mat[Col]) do
    begin
      If  Mat[Col,Lig] = 1 Then
      begin
        Inc(Couleur);
        ChercheEtPeintVoisin(Mat,Lig,Col,Couleur);
      end;
    end;
end;

[Invité]

concernant l'algo que j'ai proposé, on peut faire mieux:

au lieu de propager la valeur d'une des chaines mergés sur toute la "frontière" (semi ligne gauche et au dessus à droite)

on peut mettre en place un historique de merge.
A chaque merge, on peut regarder si il existe déjà un merge des deux id (auquel cas on ne fait rien) sinon on tranche 1 au nb de chaines allouées

si on considère la structure

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
 
m:id->chaineIds //ou typiquement m est de type map(int=>array(int))
merge(id_i, id_j)
    a=id_i, b=id_j //moins fatiguant à ecrire
    si a > m.size && b > m.size
        s = [a,b]
        m[a] = s
        m[b] = s
    si a < m.size && b < m.size
        //merging
        //on veut merger les chaines "fusionnées" sur b dans celles de a
        //on les prends toutes de m[b] et on les fait pointer sur celles de a
        //lorsqu'on les ajoutera dans celles de a le "fast" access sera tt le temps à jour pour //tous ces référents
        m[b].forEach(pointee=>{
            m[pointee] = m[a]
        })
        m[a].append_all(m[b])
    si a < m.size && b > m.size
        m[a].append(b)
        m[b] = m[a]
    //dernier cas trivial

Donc normalement on parcourt la matrice une seule fois.
à chaque "1" on étudie le pattern

xxx
x1


Si 0 chaine, on fait une alloc on se met à jour soi-même
Si 1 chaine, on defaulte l'id de cette chaine sur soi-même
Si 2 chaine, on defaulte la valeur d'en haut à droite sur soi-même et on appele merge
l'idée est que le domaine de "gauche" sera principalement de même valeur que notre cellule de gauche. Le domaine de droite de la cellule haut droite.


Exemple:
0203
020333
221 //partie du domaine qui vaut 3 à droite de 1
20

Sur la gauche du 1, si 1 prend la valeur 3, comme nous parcourons de gauche à droite, il faudrait backpropager la valeur trois pour eviter l'appel à merge, alors que si ns prenons 2, pas d'appel merge. même chose pour la droite, si 1 prenait la valeur 2, il faudrait la propager à droite mais si il prend la valeur trois, pas de merge.

Il y a bien les cas où il y aura deux appels à merge. Certes.
2222222
2000002
2003302
2211111

Je postule que cet algorithme est plus rapide que celui de Flodelarab car
sur son algo, à chaque visite du voisin
il y a 8 potentiels check/coloriage

Dans celui que je propose, il yen a 4 pour chaque "1" PLUS l'eventuel appel à merge qui coute cher mais que je ne suis pas capable d'evaluer...

A tester

[anapurna]

salut
essaye cette grille avec ta recherche

Code :

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

1
2
3
4
5
 
((1,0,0,1,0,1,0),
 (1,0,1,1,0,0,1),
 (1,0,0,0,1,1,0),
 (0,0,1,0,0,0,0));

tu comprendra pourquoi nous devons vérifier toutes les direction

[trihanhcie]

Ah en effet, avec cet exemple, mon algo marche pas!

Est-ce que cela signifie qu on est oblige de colorier tout un groupe tant qu il y a encore "1" proche du groupe?
Si c'est le cas, en effet, une fonction récursive semble etre la meilleure (seule?) manière.

Je vais tenter cela!

Merci

[Invité]

Hello,

j'ai testé un peu les trois approches
naive (ma premiere approche)
merger(avec une map au lieu de ecrire la matrice pour faire la frontière)
flo (pour le parcourt en profondeur)

merger a l'air pas trop mal SAUF quand N grandit


code: (nodejs v9.11)
il faut splitter les fichiers si vs voulez runner

Code js :

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
 
//--------------flo.js--------------
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
    var nbGroupes = 1;
    function explore(i,j,id){
        P(i,j,id)
        var x = [i-1, i-1, i-1, i  , i+1, i+1, i+1, i]
        var y = [j-1, j  , j+1, j+1, j+1, j  , j-1, j-1]
        for(var idx = 0; idx<x.length; ++idx){
            var a = x[idx]
            var b = y[idx]
            if(a<0 || a >= m.length){
                continue
            }
            if(M(a,b)==1){
                explore(a,b, id)    
            }
        }
    }
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)!=1)continue;
            nbGroupes++
            explore(i,j, nbGroupes)
        }
    }
    return nbGroupes-1;
}
 
module.exports = {
    run:run
}\n//-----end flo.js-----
//--------------merger.js--------------
 
function toString(m){
    return m.map(r=>{
        return r.map(x=>{
            if(x<10){
                x = ' '+x;
            }
            return x;
        }).join(' ')
    }).join('\n')
}
 
 
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
    var h = {}
    var nbMerges = 0;
    function merge(a,b){
        if(h[a]){
            if(h[b]){
                if(h[a]==h[b]){
                    return; //this relation already exists!
                }
                h[b].forEach(el=>{
                    h[el] = h[a]
                    h[a].push(el)
                })
            }else{
                h[b] = h[a]
                h[a].push(b)
            }
        }else{
            if(h[b]){
                h[a] = h[b]
                h[b].push(a)
            }else{
                h[a] = [a,b]
                h[b] = h[a]
            }
        }
        nbMerges++;
    }
    var nbGroupes=0;
    var id=1;//le premier id que nous allouerons vaudra 2
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)==0)continue;
            if(i==0){
                if(j==0){
                    nbGroupes++;
                    id++
                    P(i,j,id)
                }else{
                    //si i==0 on regarde pas les cases adjacentes du dessus... donc seul check sur case de gauche
                    if(M(i,j-1)){
                        P(i,j,M(i,j-1));
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)  
                    }
                }
            }else{
                if(j==0){
                    var oneOrOther = M(i-1,j)||M(i-1,j+1)
                    //si j==0 il y a au maximum une chaine
                    if(oneOrOther){
                        P(i,j,oneOrOther)
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)
                    }
                }else{
                    //trois cas: nouvelle chaine, existe 1 chaine, existent deux chaines distinctes
                    var c1 = M(i,j-1) || M(i-1,j-1) || M(i-1,j);//représente la valeur de la première chaine
                    var c2 = M(i-1,j+1)
                    if(c1){
                        if(c2){
                            if(c1==c2){
                                P(i,j,c1)
                            }else{
                                merge(c1,c2)
                                P(i,j,c2)
                            }
                        }else{
                            P(i,j,c1)
                        }
                    }else{
                        if(c2){
                            P(i,j,c2)
                        }else{
                            nbGroupes++
                            id++
                            P(i,j,id)
                        }
                    }
                }
            }
        }
    }
 
    return nbGroupes - nbMerges;
}
 
module.exports = {
    run:run
}\n//-----end merger.js-----
//--------------naive.js--------------
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
 
    var nbGroupes=0;
    var id=1;//le premier id que nous allouerons vaudra 2
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)==0)continue;
            if(i==0){
                if(j==0){
                    nbGroupes++;
                    id++
                    P(i,j,id)
                }else{
                    //si i==0 on regarde pas les cases adjacentes du dessus... donc seul check sur case de gauche
                    if(M(i,j-1)){
                        P(i,j,M(i,j-1));
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)  
                    }
                }
            }else{
                if(j==0){
                    var oneOrOther = M(i-1,j)||M(i-1,j+1)
                    //si j==0 il y a au maximum une chaine
                    if(oneOrOther){
                        P(i,j,oneOrOther)
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)
                    }
                }else{
                    //trois cas: nouvelle chaine, existe 1 chaine, existent deux chaines distinctes
                    var c1 = M(i,j-1) || M(i-1,j-1) || M(i-1,j);//représente la valeur de la première chaine
                    var c2 = M(i-1,j+1)
                    if(c1){
                        if(c2){
                            if(c1==c2){
                                P(i,j,c2)
                            }else{
 
                                nbGroupes--;
                                for(var j1 = 0; j1<=j; ++j1){
                                    if(M(i,j1)==c1){
                                        P(i,j1,c2)
                                    }
                                }
                                for(var j1 = j+1; j1<m[i].length; ++j1){
                                    if(M(i-1,j1)==c1){
                                        P(i-1, j1, c2)
                                    }
                                }
                                P(i,j,c2)
                            }
                        }else{
                            P(i,j,c1)
                        }
                    }else{
                        if(c2){
                            P(i,j,c2)
                        }else{
                            nbGroupes++
                            id++
                            P(i,j,id)
                        }
                    }
 
                }
            }
        }
    }
    return nbGroupes;
}
 
module.exports = {
    run:run
}\n//-----end naive.js-----
//--------------stress.js--------------
var merger = require('./merger');
var naive = require('./naive');
var flo = require('./flo');
var assert = require('assert')
 
 
function toString(m){
    return m.map((r,i)=>{
        return r.map(x=>{
            if(x<10){
                return ' '+x;
            }
            return x;
        }).join(' ')
    }).join('\n')
}
function stress(){
    var m = [];
    var N = process.argv.splice(2)[0]||20;
    for(var i = 0; i<N; ++i){
        m[i] = [];
        for(var j = 0; j<N; ++j){
            var r = Math.random();
            m[i][j] = r < 0.5? 0:1;
        }
    }
 
    var nbGroups;
    var res = [{n:'naive', m: naive}, {n: 'merger', m: merger}, {n: 'flo', m:flo}].map(x=>{
        var tmp = JSON.parse(JSON.stringify(m))
        console.time(x.n)
        var r = x.m.run(tmp)
        nbGroups = r;
        console.timeEnd(x.n)
        return r;
    })
    assert(res.every(x=>x==nbGroups), 'all solutions returned the same nb of groups')
 
}
stress()
\n//-----end stress.js-----
//--------------tester.js--------------
var assert = require('assert');
function testall(runner){
    function test(s,exp){
        var m = s.split('\n').map(x=>x.trim()).filter(x=>x.length).map(x=>x.split(/[\s,]+/).map(y=>parseInt(y)>=1?1:0));
        assert.equal(runner.run(m), exp);
        return m;
    }
 
    var m;
 
    s = `
    1 0 1
    1 0 1
    1 1 1
    `;
    test(s, 1)
 
    s = `
    1 0 1
    0 1 1
    0 1 0
    `;
    test(s, 1)
 
    s = `
    1 0 1
    0 0 0
    0 1 0
    `;
    test(s, 3)
 
 
    s = `
    1 0 1
    0 0 0
    0 1 0
    `;
    test(s, 3)
 
    s =`
    1 0 0 1
    1 1 1 0
    0 0 1 0
    1 0 0 0
    `
    test(s,2)
 
 
    s =`
    1 0 0 1
    1 0 1 0
    0 0 1 0
    1 0 0 0
    `
    test(s,3)
 
    s = `
    1 1 0 1
    1 1 0 1
    0 0 1 0
    1 0 0 0
    `
    test(s, 2)//merge deux chaines
 
    s=`
    1,0,0,1,0,1,0
    1,0,1,1,0,0,1
    1,0,0,0,1,1,0
    0,0,1,0,0,0,0
    `
    test(s, 3)
 
 
    //multi merge
    s=`
    1,1,1,0,1,1,1
    1,0,1,0,1,0,1
    0,1,0,0,0,1,0
    1 1 1 1 1 0 0
    `
    test(s, 1)
 
    s=`
    2 0 2 0 3 3 0 0 4 4
    2 2 2 3 3 3 3 0 4 4
    2 0 3 3 0 0 0 0 0 0
    0 3 3 0 0 5 0 0 0 6
    3 3 0 3 5 0 5 5 6 6
    0 0 3 5 0 5 0 6 0 0
    0 0 0 3 5 5 0 0 6 0
    0 0 3 0 0 0 0 6 0 6
    7 0 3 3 0 8 6 0 6 0
    7 0 3 3 0 0 0 6 0 0
    `
    test(s, 3)
 
 
    s=`
    0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1
    1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0
    0 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0
    0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1
    1 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 1 0 1
    0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 0 0 1
    0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1
    1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0
    0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1
    1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1
    0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0
    0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 0 1 0 1
    0 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1
    1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0
    0 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1
    1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1
    1 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 0
    0 1 1 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 0
    0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0
    0 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0
    `
    test(s,6)
}
 
testall(require('./merger'))
testall(require('./naive'))
testall(require('./flo'))\n//-----end tester.js-----

qq runs:

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
102
103
104
105
106
107
108
 
N=20
for i in $(seq 1 5);do node stress.js 20; echo '----';done
naive: 0.281ms
merger: 0.294ms
flo: 0.367ms
----
naive: 0.280ms
merger: 0.294ms
flo: 0.358ms
----
naive: 0.287ms
merger: 0.296ms
flo: 0.377ms
----
naive: 0.283ms
merger: 0.271ms
flo: 0.354ms
----
naive: 0.282ms
merger: 0.292ms
flo: 0.378ms
 
N=50
naive: 1.689ms
merger: 0.695ms
flo: 1.875ms
----
naive: 1.732ms
merger: 0.706ms
flo: 1.849ms
----
naive: 1.643ms
merger: 0.733ms
flo: 1.888ms
----
naive: 1.711ms
merger: 0.692ms
flo: 1.931ms
----
naive: 1.669ms
merger: 0.689ms
flo: 1.853ms
----
 
 
N=100
naive: 7.312ms
merger: 1.918ms
flo: 6.148ms
----
naive: 7.370ms
merger: 2.052ms
flo: 7.285ms
----
naive: 7.363ms
merger: 2.219ms
flo: 6.670ms
----
naive: 7.405ms
merger: 2.308ms
flo: 5.298ms
----
naive: 7.568ms
merger: 2.331ms
flo: 5.590ms
----
 
 
N=300 (bcp de temps perdu ds la call stack)
naive: 18.864ms
merger: 15.241ms
flo: 25.761ms
----
naive: 17.924ms
merger: 17.018ms
flo: 26.869ms
----
naive: 17.704ms
merger: 21.909ms
flo: 25.706ms
----
naive: 22.318ms
merger: 17.014ms
flo: 25.852ms
----
naive: 19.330ms
merger: 17.148ms
flo: 27.600ms
----
 
pour N >300, segfault flo 
pour N==2000
naive: 2250.131ms
merger: 12512.227ms
----
naive: 2277.181ms
merger: 13485.446ms
----
naive: 2267.673ms
merger: 13363.765ms
----
naive: 2276.136ms
merger: 13305.371ms
----
naive: 2280.025ms
merger: 13158.966ms
----

edit2: nouvelle version pr merge: je reset les id de l'historique qui ne sont plus accessibles (les ids accessibles sont ceux de la ligne qui vient d'être remplie)
les perf sont globalement pas top sauf à partir de n=2000 (et intuité plus...)
grossomodo: du temps perdu sur le stockage des write de la ligne en cours, sur le cleaning de l'historique, et tjs sur la construction de l'historique (comme intuité)
il faudrait tester la transformation de lalgo flo en iteratif mais bon, la biere tape un peu

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
 
//--------------mergerForget.js--------------
 
function toString(m){
    return m.map(r=>{
        return r.map(x=>{
            if(x<10){
                x = ' '+x;
            }
            return x;
        }).join(' ')
    }).join('\n')
}
 
 
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    var putIds = new Set;
    var testAdd = 0;
    function P(i,j,v){
        var s = Date.now();
        putIds.add(v);
        testAdd += Date.now()-s;
        m[i][j]=v;
    }
    var h = {}
    var nbMerges = 0;
    var testMerge = 0;
    function merge(a,b){
        var tmp = Date.now();
        if(h[a]){
            if(h[b]){
                if(h[a]==h[b]){
                    return; //this relation already exists!
                }
                h[b].forEach(el=>{
                    h[el] = h[a]
                    h[a].push(el)
                })
            }else{
                h[b] = h[a]
                h[a].push(b)
            }
        }else{
            if(h[b]){
                h[a] = h[b]
                h[b].push(a)
            }else{
                h[a] = [a,b]
                h[b] = h[a]
            }
        }
        nbMerges++;
        testMerge += Date.now()-tmp;
    }
    var testCopyDest = 0;
    var id=1;//le premier id que nous allouerons vaudra 2
    for(var i = 0;i<m.length; ++i){
        //cleanup unreachable ids
        var dest = {};
        if(putIds.size > 80){
            var startCpy = Date.now();
            putIds.forEach(aid=>{
                if((aid in dest) && dest[aid].length > 1){
                    return;
                }
                dest[aid] = [aid];
                if(!(aid in h)){
                    return;
                }
                h[aid].filter(el=>{
                    //if el has already been "merged", do not treat it
                    //otherwise only copy el if it belongs to the last treated line
                    if( !(el in dest) && putIds.has(el) ){
                        dest[el] = dest[aid];
                        dest[aid].push(el);
                    }
                })
            })
            putIds = new Set;
            h = dest;
            testCopyDest+= Date.now()-startCpy;
        }
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)==0)continue;
            if(i==0){
                if(j==0){
                    id++
                    P(i,j,id)
                }else{
                    //si i==0 on regarde pas les cases adjacentes du dessus... donc seul check sur case de gauche
                    if(M(i,j-1)){
                        P(i,j,M(i,j-1));
                    }else{
                        id++
                        P(i,j,id)
                    }
                }
            }else{
                if(j==0){
                    var oneOrOther = M(i-1,j)||M(i-1,j+1)
                    //si j==0 il y a au maximum une chaine
                    if(oneOrOther){
                        P(i,j,oneOrOther)
                    }else{
                        id++
                        P(i,j,id)
                    }
                }else{
                    //trois cas: nouvelle chaine, existe 1 chaine, existent deux chaines distinctes
                    var c1 = M(i,j-1) || M(i-1,j-1) || M(i-1,j);//représente la valeur de la première chaine
                    var c2 = M(i-1,j+1)
                    if(c1){
                        if(c2){
                            if(c1==c2){
                                P(i,j,c1)
                            }else{
                                merge(c1,c2)
                                P(i,j,c2)
                            }
                        }else{
                            P(i,j,c1)
                        }
                    }else{
                        if(c2){
                            P(i,j,c2)
                        }else{
                            id++
                            P(i,j,id)
                        }
                    }
                }
            }
        }
    }
    /*console.log('test copydest ', testCopyDest)
    console.log('testAdd Time ', testAdd)
    console.log('testMerge Time ', testMerge)*/
    return id -1 - nbMerges;
}
 
module.exports = {
    run:run
}
//-----end mergerForget.js-----

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
 
----200----
naive: 17.670ms
merger: 18.066ms
mergerForget: 35.590ms
naive: 17.502ms
merger: 17.987ms
mergerForget: 31.392ms
naive: 16.693ms
merger: 20.771ms
mergerForget: 35.482ms
naive: 17.774ms
merger: 17.816ms
mergerForget: 31.595ms
naive: 16.730ms
merger: 17.824ms
mergerForget: 33.298ms
----1000----
naive: 489.066ms
merger: 963.584ms
mergerForget: 500.768ms
naive: 491.864ms
merger: 975.527ms
mergerForget: 480.421ms
naive: 474.104ms
merger: 998.700ms
mergerForget: 479.219ms
naive: 475.543ms
merger: 907.141ms
mergerForget: 477.028ms
naive: 538.096ms
merger: 989.281ms
mergerForget: 520.923ms
----2000----
naive: 3370.161ms
merger: 23845.734ms
mergerForget: 2554.934ms
naive: 3389.500ms
merger: 23708.351ms
mergerForget: 2609.643ms
naive: 3393.870ms
merger: 23738.250ms
mergerForget: 2595.792ms
naive: 3430.813ms
merger: 24196.615ms
mergerForget: 2597.641ms
naive: 3478.731ms
merger: 24158.428ms
mergerForget: 2604.635ms

[Invité]

Plusieurs nouvelles approches...
1. chain.js
C'est la toute première idée de ce thread:
chaque "cellule allouée" est un pointeur.
à chaque prise de valeur d'une cellule adjacente on stocke le pointeur.
L'algorithme de merge est similaire à ..merger.js
Au lieu de faire un lookup de le dic, on accèdes aux éléments "mergés" directement par la valeur pointee

2. floUnrec.js
La version bete derecursivée

3. floUnrec2.js
Même chose mais on fait moins de check sur les bordures de la matrice...

4. floUnrec3.js
Au lieu de construire le tableau d'index complet tout le temps, on encode la formation des offsets i,j dans l'index stockée

Conclusions:
pour N<10, l'approche naive est la meilleure
pour N<200, l'approche merger est la meilleure (peu de lookup, et moins couteux qu'un remplacement de lignes)
pour N<1000, l'approche chain est la meilleure (pas de lookup)

A noter sur les version dérécursivées de l'algo flo, à partir de N=200, floUnrec3 se comporte mieux que mes trois premières approches proposées
(naive et merger/mergerForget)

Code js :

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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
 
//--------------mergerForget.js--------------
 
function toString(m){
    return m.map(r=>{
        return r.map(x=>{
            if(x<10){
                x = ' '+x;
            }
            return x;
        }).join(' ')
    }).join('\n')
}
 
 
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
    var nbMerges = 0;
    var testMerge = 0;
    function merge(a,b){
        var tmp = Date.now();
        if(a.v.length < b.v.length){
            [a,b] = [b,a]
        }
        b.v.forEach(el=>{
            el.v = a.v;
            a.v.push(el)
        })
        b.v = a.v;
        nbMerges++;
        testMerge += Date.now()-tmp;
    }
    var id=1;//le premier id que nous allouerons vaudra 2
    function Cell(id){
        this.id = id;
        this.v = [this];
    }
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)==0)continue;
            if(i==0){
                if(j==0){
                    id++
                    P(i,j, new Cell(id))
                }else{
                    //si i==0 on regarde pas les cases adjacentes du dessus... donc seul check sur case de gauche
                    if(M(i,j-1)){
                        P(i,j,M(i,j-1));
                    }else{
                        id++
                        P(i,j,new Cell(id))
                    }
                }
            }else{
                if(j==0){
                    var oneOrOther = M(i-1,j)||M(i-1,j+1)
                    //si j==0 il y a au maximum une chaine
                    if(oneOrOther){
                        P(i,j,oneOrOther)
                    }else{
                        id++
                        P(i,j,new Cell(id))
                    }
                }else{
                    //trois cas: nouvelle chaine, existe 1 chaine, existent deux chaines distinctes
                    var c1 = M(i,j-1) || M(i-1,j-1) || M(i-1,j);//représente la valeur de la première chaine
                    var c2 = M(i-1,j+1)
                    if(c1){
                        if(c2){
                            if(c1.v==c2.v){
                                P(i,j,c1)
                            }else{
                                merge(c1,c2)
                                P(i,j,c2)
                            }
                        }else{
                            P(i,j,c1)
                        }
                    }else{
                        if(c2){
                            P(i,j,c2)
                        }else{
                            id++
                            P(i,j,new Cell(id))
                        }
                    }
                }
            }
        }
    }
    return id -1 - nbMerges;
}
 
module.exports = {
    run:run
}
//-----end mergerForget.js-----
//--------------flo.js--------------
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
    var nbGroupes = 1;
    function explore(i,j,id){
        P(i,j,id)
        var x = [i-1, i-1, i-1, i  , i+1, i+1, i+1, i]
        var y = [j-1, j  , j+1, j+1, j+1, j  , j-1, j-1]
        for(var idx = 0; idx<x.length; ++idx){
            var a = x[idx]
            var b = y[idx]
            if(a<0 || a >= m.length){
                continue
            }
            if(M(a,b)==1){
                explore(a,b, id)    
            }
        }
    }
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)!=1)continue;
            nbGroupes++
            explore(i,j, nbGroupes)
        }
    }
    return nbGroupes-1;
}
 
module.exports = {
    run:run
}
//-----end flo.js-----
//--------------floUnrec2.js--------------
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
    var nbGroupes = 1;
    function explore(ai,aj,id){
        var stack = [[ai,aj,0]];
        while(stack.length){
            var [i,j,sIdx] = stack.pop();
            P(i,j,id)
            if(i==0){
                if(j==0){
                    x = [i  , i+1, i+1]
                    y = [j+1, j+1, j  ]
                }else if(j==m[0].length-1){
                    x = [i+1, i+1, i  ]
                    y = [j  , j-1, j-1]
                }else{
                    x = [i  , i+1, i+1, i+1, i  ]
                    y = [j+1, j+1, j  , j-1, j-1]
                }
            }else if(i==m.length-1){
                if(j==0){
                    x = [i-1, i-1, i  ]
                    y = [j  , j+1, j+1]
                }
                if(j==m[0].length-1){
                    x = [i-1, i-1, i  ]
                    y = [j-1, j  , j-1]
                }else{
                    x = [i-1, i-1, i-1, i  , i  ]
                    y = [j-1, j  , j+1, j+1, j-1]
                }
            }else{
                if(j==0){
                    x = [i-1, i-1, i  , i+1, i+1]
                    y = [j  , j+1, j+1, j+1, j  ]
                }else if(j==m[0].length-1){
                    x = [i-1, i-1, i+1, i+1, i  ]
                    y = [j-1, j  , j  , j-1, j-1]
                }else{
                    x = [i-1, i-1, i-1, i  , i+1, i+1, i+1, i  ]
                    y = [j-1, j  , j+1, j+1, j+1, j  , j-1, j-1]
                }
            }
            for(var idx = sIdx; idx<x.length; ++idx){
                var a = x[idx]
                var b = y[idx]
                if(M(a,b)==1){
                    stack.push([i,j,idx+1]);
                    stack.push([a,b,0]);
                    break;
                }
            }
        }
    }
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)!=1)continue;
            nbGroupes++
            explore(i,j, nbGroupes)
        }
    }
    return nbGroupes-1;
}
 
module.exports = {
    run:run
}
//-----end floUnrec2.js-----
//--------------floUnrec3.js--------------
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
    var nbGroupes = 1;
    function explore(ai,aj,id){
        var stack = [[ai,aj,0]];
        while(stack.length){
            var [i,j,sIdx] = stack.pop();
            P(i,j,id)
            for(var idx = sIdx; idx<9; ++idx){
                var modJ = idx%3;
                var modI = (idx-modJ)/3;
                var a = i+modI-1;
                var b = j+modJ-1;
                if(a<0 || a >= m.length|| b<0 || b>=m[0].length){
                    continue
                }
                if(M(a,b)==1){
                    stack.push([i,j,idx+1]);
                    stack.push([a,b,0]);
                    break;
                }
            }
        }
    }
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)!=1)continue;
            nbGroupes++
            explore(i,j, nbGroupes)
        }
    }
    return nbGroupes-1;
}
 
module.exports = {
    run:run
}
//-----end floUnrec3.js-----
//--------------floUnrec.js--------------
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
    var nbGroupes = 1;
    function explore(ai,aj,id){
        var stack = [[ai,aj,0]];
        while(stack.length){
            var [i,j,sIdx] = stack.pop();
            P(i,j,id)
            var x = [i-1, i-1, i-1, i  , i+1, i+1, i+1, i]
            var y = [j-1, j  , j+1, j+1, j+1, j  , j-1, j-1]
            for(var idx = sIdx; idx<x.length; ++idx){
                var a = x[idx]
                var b = y[idx]
                if(a<0 || a >= m.length){
                    continue
                }
                if(M(a,b)==1){
                    stack.push([i,j,idx+1]);
                    stack.push([a,b,0]);
                    break;
                }
            }
        }
    }
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)!=1)continue;
            nbGroupes++
            explore(i,j, nbGroupes)
        }
    }
    return nbGroupes-1;
}
 
module.exports = {
    run:run
}
//-----end floUnrec.js-----
//--------------mergerForget.js--------------
 
function toString(m){
    return m.map(r=>{
        return r.map(x=>{
            if(x<10){
                x = ' '+x;
            }
            return x;
        }).join(' ')
    }).join('\n')
}
 
 
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    var putIds = new Set;
    var testAdd = 0;
    function P(i,j,v){
        var s = Date.now();
        putIds.add(v);
        testAdd += Date.now()-s;
        m[i][j]=v;
    }
    var h = {}
    var nbMerges = 0;
    var testMerge = 0;
    function merge(a,b){
        var tmp = Date.now();
        if(h[a]){
            if(h[b]){
                if(h[a]==h[b]){
                    return; //this relation already exists!
                }
                h[b].forEach(el=>{
                    h[el] = h[a]
                    h[a].push(el)
                })
            }else{
                h[b] = h[a]
                h[a].push(b)
            }
        }else{
            if(h[b]){
                h[a] = h[b]
                h[b].push(a)
            }else{
                h[a] = [a,b]
                h[b] = h[a]
            }
        }
        nbMerges++;
        testMerge += Date.now()-tmp;
    }
    var testCopyDest = 0;
    var id=1;//le premier id que nous allouerons vaudra 2
    for(var i = 0;i<m.length; ++i){
        //cleanup unreachable ids
        var dest = {};
        if(putIds.size > 80){
            var startCpy = Date.now();
            putIds.forEach(aid=>{
                if((aid in dest) && dest[aid].length > 1){
                    return;
                }
                dest[aid] = [aid];
                if(!(aid in h)){
                    return;
                }
                h[aid].filter(el=>{
                    //if el has already been "merged", do not treat it
                    //otherwise only copy el if it belongs to the last treated line
                    if( !(el in dest) && putIds.has(el) ){
                        dest[el] = dest[aid];
                        dest[aid].push(el);
                    }
                })
            })
            putIds = new Set;
            h = dest;
            testCopyDest+= Date.now()-startCpy;
        }
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)==0)continue;
            if(i==0){
                if(j==0){
                    id++
                    P(i,j,id)
                }else{
                    //si i==0 on regarde pas les cases adjacentes du dessus... donc seul check sur case de gauche
                    if(M(i,j-1)){
                        P(i,j,M(i,j-1));
                    }else{
                        id++
                        P(i,j,id)
                    }
                }
            }else{
                if(j==0){
                    var oneOrOther = M(i-1,j)||M(i-1,j+1)
                    //si j==0 il y a au maximum une chaine
                    if(oneOrOther){
                        P(i,j,oneOrOther)
                    }else{
                        id++
                        P(i,j,id)
                    }
                }else{
                    //trois cas: nouvelle chaine, existe 1 chaine, existent deux chaines distinctes
                    var c1 = M(i,j-1) || M(i-1,j-1) || M(i-1,j);//représente la valeur de la première chaine
                    var c2 = M(i-1,j+1)
                    if(c1){
                        if(c2){
                            if(c1==c2){
                                P(i,j,c1)
                            }else{
                                merge(c1,c2)
                                P(i,j,c2)
                            }
                        }else{
                            P(i,j,c1)
                        }
                    }else{
                        if(c2){
                            P(i,j,c2)
                        }else{
                            id++
                            P(i,j,id)
                        }
                    }
                }
            }
        }
    }
    /*console.log('test copydest ', testCopyDest)
    console.log('testAdd Time ', testAdd)
    console.log('testMerge Time ', testMerge)*/
    return id -1 - nbMerges;
}
 
module.exports = {
    run:run
}
//-----end mergerForget.js-----
 
//--------------merger.js--------------
 
function toString(m){
    return m.map(r=>{
        return r.map(x=>{
            if(x<10){
                x = ' '+x;
            }
            return x;
        }).join(' ')
    }).join('\n')
}
 
 
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
    var h = {}
    var nbMerges = 0;
    function merge(a,b){
        if(h[a]){
            if(h[b]){
                if(h[a]==h[b]){
                    return; //this relation already exists!
                }
                h[b].forEach(el=>{
                    h[el] = h[a]
                    h[a].push(el)
                })
            }else{
                h[b] = h[a]
                h[a].push(b)
            }
        }else{
            if(h[b]){
                h[a] = h[b]
                h[b].push(a)
            }else{
                h[a] = [a,b]
                h[b] = h[a]
            }
        }
        nbMerges++;
    }
    var nbGroupes=0;
    var id=1;//le premier id que nous allouerons vaudra 2
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)==0)continue;
            if(i==0){
                if(j==0){
                    nbGroupes++;
                    id++
                    P(i,j,id)
                }else{
                    //si i==0 on regarde pas les cases adjacentes du dessus... donc seul check sur case de gauche
                    if(M(i,j-1)){
                        P(i,j,M(i,j-1));
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)  
                    }
                }
            }else{
                if(j==0){
                    var oneOrOther = M(i-1,j)||M(i-1,j+1)
                    //si j==0 il y a au maximum une chaine
                    if(oneOrOther){
                        P(i,j,oneOrOther)
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)
                    }
                }else{
                    //trois cas: nouvelle chaine, existe 1 chaine, existent deux chaines distinctes
                    var c1 = M(i,j-1) || M(i-1,j-1) || M(i-1,j);//représente la valeur de la première chaine
                    var c2 = M(i-1,j+1)
                    if(c1){
                        if(c2){
                            if(c1==c2){
                                P(i,j,c1)
                            }else{
                                merge(c1,c2)
                                P(i,j,c2)
                            }
                        }else{
                            P(i,j,c1)
                        }
                    }else{
                        if(c2){
                            P(i,j,c2)
                        }else{
                            nbGroupes++
                            id++
                            P(i,j,id)
                        }
                    }
                }
            }
        }
    }
 
    return nbGroupes - nbMerges;
}
 
module.exports = {
    run:run
}
//--------------naive.js--------------
function run(m){
    //m(i,j), i représente la ligne et j la colonne
    function M(i,j){
        return m[i][j]
    }
    function P(i,j,v){
        m[i][j]=v;
    }
 
    var nbGroupes=0;
    var id=1;//le premier id que nous allouerons vaudra 2
    for(var i = 0;i<m.length; ++i){
        for(var j = 0;j<m[i].length; ++j){
            if(M(i,j)==0)continue;
            if(i==0){
                if(j==0){
                    nbGroupes++;
                    id++
                    P(i,j,id)
                }else{
                    //si i==0 on regarde pas les cases adjacentes du dessus... donc seul check sur case de gauche
                    if(M(i,j-1)){
                        P(i,j,M(i,j-1));
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)  
                    }
                }
            }else{
                if(j==0){
                    var oneOrOther = M(i-1,j)||M(i-1,j+1)
                    //si j==0 il y a au maximum une chaine
                    if(oneOrOther){
                        P(i,j,oneOrOther)
                    }else{
                        nbGroupes++;
                        id++
                        P(i,j,id)
                    }
                }else{
                    //trois cas: nouvelle chaine, existe 1 chaine, existent deux chaines distinctes
                    var c1 = M(i,j-1) || M(i-1,j-1) || M(i-1,j);//représente la valeur de la première chaine
                    var c2 = M(i-1,j+1)
                    if(c1){
                        if(c2){
                            if(c1==c2){
                                P(i,j,c2)
                            }else{
 
                                nbGroupes--;
                                for(var j1 = 0; j1<=j; ++j1){
                                    if(M(i,j1)==c1){
                                        P(i,j1,c2)
                                    }
                                }
                                for(var j1 = j+1; j1<m[i].length; ++j1){
                                    if(M(i-1,j1)==c1){
                                        P(i-1, j1, c2)
                                    }
                                }
                                P(i,j,c2)
                            }
                        }else{
                            P(i,j,c1)
                        }
                    }else{
                        if(c2){
                            P(i,j,c2)
                        }else{
                            nbGroupes++
                            id++
                            P(i,j,id)
                        }
                    }
 
                }
            }
        }
    }
    return nbGroupes;
}
 
module.exports = {
    run:run
}
//-----end naive.js-----
//--------------stress.js--------------
var assert = require('assert')
 
 
function toString(m){
    return m.map((r,i)=>{
        return r.map(x=>{
            if(x<10){
                return ' '+x;
            }
            return x;
        }).join(' ')
    }).join('\n')
}
function stress(){
    var m = [];
    var nbRuns = 5;
    for(var i = 0; i<N; ++i){
        m[i] = [];
        for(var j = 0; j<N; ++j){
            var r = Math.random();
            m[i][j] = r < 0.5? 0:1;
        }
    }
 
    var nbGroups;
    var res = [
        {n:'naive', m: require('./naive')}, 
        {n: 'merger', m: require('./merger')}, 
        {n: 'mergerForget', m: require('./mergerForget')},
        {n: 'chain', m: require('./chain')},
        {n: 'flo', m:require('./flo')},
        {n: 'floUnrec', m:require('./floUnrec')},
        {n: 'floUnrec2', m:require('./floUnrec2')},
        {n: 'floUnrec3', m:require('./floUnrec3')}
    ].map(x=>{
        var tmp = JSON.parse(JSON.stringify(m))
        var startTime = process.hrtime();
        try{
        var r = x.m.run(tmp)
        }catch(e){
            x.timed = 'N/A';
            x.timedNum = 1e8;
            x.nbGroups = nbGroups;//cheating
            return x;
        }
        x.timed = process.hrtime(startTime);
        x.timedNum = x.timed[0]*1000+(x.timed[1]/1000000)
        x.timed = x.timedNum.toFixed(3)+' ms';
        nbGroups = r;
        x.nbGroups = r;
        return x;
    })
    assert(res.every(x=>x.nbGroups==nbGroups), 'all solutions returned the same nb of groups')
    return res;
 
}
function bench(){
    for(var i = 0; i<5; ++i){
        var s='';
        var res = stress();
        var colLength = Math.max(...res.map(x=>Math.max(x.n.length, x.timed.length)))
        if(i==0){
            s+='i|'
            s+=res.map(x=>{
                return x.n.padStart(colLength, ' ');
            }).join('|');
            s+='\n'
        }
        s+=i+'|';
        var minRun = 0;
        var minj;
        var arr = res.map((x,j)=>{
            if(!minRun || x.timedNum < minRun){
                minRun = x.timedNum;
                minj = j;
            }
            return x.timed.padStart(colLength, ' ');
        });
        arr[minj] = '*'+arr[minj].substring(1);
        s+=arr.join('|');
        console.log(s)
    }
}
var N = process.argv.splice(2)[0]||20;
bench();
//-----end stress.js-----
//--------------tester.js--------------
var assert = require('assert');
function testall(runner){
    function test(s,exp){
        var m = s.split('\n').map(x=>x.trim()).filter(x=>x.length).map(x=>x.split(/[\s,]+/).map(y=>parseInt(y)>=1?1:0));
        assert.equal(runner.run(m), exp);
        return m;
    }
 
    var m;
 
    s = `
    1 0 1
    1 0 1
    1 1 1
    `;
    test(s, 1)
 
    s = `
    1 0 1
    0 1 1
    0 1 0
    `;
    test(s, 1)
 
    s = `
    1 0 1
    0 0 0
    0 1 0
    `;
    test(s, 3)
 
 
    s = `
    1 0 1
    0 0 0
    0 1 0
    `;
    test(s, 3)
 
    s =`
    1 0 0 1
    1 1 1 0
    0 0 1 0
    1 0 0 0
    `
    test(s,2)
 
 
    s =`
    1 0 0 1
    1 0 1 0
    0 0 1 0
    1 0 0 0
    `
    test(s,3)
 
    s = `
    1 1 0 1
    1 1 0 1
    0 0 1 0
    1 0 0 0
    `
    test(s, 2)//merge deux chaines
 
    s=`
    1,0,0,1,0,1,0
    1,0,1,1,0,0,1
    1,0,0,0,1,1,0
    0,0,1,0,0,0,0
    `
    test(s, 3)
 
 
    //multi merge
    s=`
    1,1,1,0,1,1,1
    1,0,1,0,1,0,1
    0,1,0,0,0,1,0
    1 1 1 1 1 0 0
    `
    test(s, 1)
 
    s=`
    2 0 2 0 3 3 0 0 4 4
    2 2 2 3 3 3 3 0 4 4
    2 0 3 3 0 0 0 0 0 0
    0 3 3 0 0 5 0 0 0 6
    3 3 0 3 5 0 5 5 6 6
    0 0 3 5 0 5 0 6 0 0
    0 0 0 3 5 5 0 0 6 0
    0 0 3 0 0 0 0 6 0 6
    7 0 3 3 0 8 6 0 6 0
    7 0 3 3 0 0 0 6 0 0
    `
    test(s, 3)
 
 
    s=`
    0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1
    1 0 1 0 1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0
    0 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1 0 1 1 0
    0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 1
    1 0 0 0 0 1 0 0 1 0 0 1 1 1 0 0 1 1 0 1
    0 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 0 0 1
    0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1
    1 0 1 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 0 0
    0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1
    1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 1
    0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0
    0 1 1 0 0 0 1 0 1 1 0 1 1 1 0 1 0 1 0 1
    0 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1
    1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 0
    0 1 0 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1
    1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1
    1 1 1 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 0
    0 1 1 0 1 1 0 0 1 1 1 1 1 1 0 1 0 0 1 0
    0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0
    0 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0
    `
    test(s,6)
 
}
 
//testall(require('./merger'))
//testall(require('./chain'))
//testall(require('./naive'))
//testall(require('./flo'))
testall(require('./floUnrec'))
testall(require('./floUnrec2'))
testall(require('./floUnrec3'))
//testall(require('./mergerLazy'))
//-----end tester.js-----

qq résultats:

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
 
for i in $(echo '5 10 50 100 500 1000'|sed 's/ /\n/');do echo "----N=$i----";node stress.js $i;done
----N=5----
i|       naive|      merger|mergerForget|       chain|         flo|    floUnrec|   floUnrec2|   floUnrec3
0|    0.224 ms|    0.252 ms|    0.348 ms|    0.582 ms|*   0.207 ms|    0.308 ms|    0.471 ms|    0.282 ms
1|*   0.014 ms|    0.018 ms|    0.024 ms|    0.044 ms|    0.026 ms|    0.046 ms|    0.054 ms|    0.042 ms
2|*   0.011 ms|    0.033 ms|    0.016 ms|    0.041 ms|    0.023 ms|    0.037 ms|    0.034 ms|    0.037 ms
3|*   0.011 ms|    0.012 ms|    0.017 ms|    0.040 ms|    0.029 ms|    0.052 ms|    0.060 ms|    0.048 ms
4|*   0.011 ms|    0.012 ms|    0.018 ms|    0.046 ms|    0.029 ms|    0.050 ms|    0.051 ms|    0.050 ms
----N=10----
i|       naive|      merger|mergerForget|       chain|         flo|    floUnrec|   floUnrec2|   floUnrec3
0|    0.295 ms|    0.287 ms|    0.406 ms|    0.628 ms|*   0.283 ms|    0.459 ms|    0.629 ms|    0.446 ms
1|*   0.042 ms|    0.047 ms|    0.073 ms|    0.091 ms|    0.110 ms|    0.207 ms|    0.234 ms|    0.223 ms
2|    0.063 ms|*   0.040 ms|    0.064 ms|    0.075 ms|    0.108 ms|    0.239 ms|    0.216 ms|    0.223 ms
3|*   0.042 ms|    0.044 ms|    0.066 ms|    0.077 ms|    0.118 ms|    0.221 ms|    0.226 ms|    0.225 ms
4|*   0.036 ms|    0.058 ms|    0.059 ms|    0.078 ms|    0.094 ms|    0.187 ms|    0.191 ms|    0.190 ms
----N=50----
i|       naive|      merger|mergerForget|       chain|         flo|    floUnrec|   floUnrec2|   floUnrec3
0|    2.752 ms|*   1.312 ms|    1.886 ms|    1.512 ms|    3.416 ms|    8.297 ms|    9.207 ms|   19.649 ms
1|    1.262 ms|*   1.008 ms|    1.534 ms|    1.036 ms|    2.846 ms|   21.889 ms|    8.154 ms|   18.695 ms
2|    0.857 ms|    0.656 ms|    1.494 ms|    0.808 ms|    0.631 ms|    1.272 ms|    0.697 ms|*   0.498 ms
3|    1.003 ms|    0.711 ms|    1.065 ms|    0.892 ms|    1.083 ms|    1.219 ms|    2.256 ms|*   0.536 ms
4|    3.659 ms|    3.001 ms|    1.020 ms|    0.877 ms|*   0.444 ms|    0.929 ms|    1.661 ms|    0.907 ms
----N=100----
i|       naive|      merger|mergerForget|       chain|         flo|    floUnrec|   floUnrec2|   floUnrec3
0|   14.247 ms|*   4.046 ms|    7.445 ms|    4.154 ms|   10.697 ms|   27.818 ms|   25.072 ms|   21.004 ms
1|    9.312 ms|*   4.672 ms|    7.243 ms|    5.961 ms|   12.401 ms|   26.237 ms|   23.487 ms|   20.918 ms
2|   10.358 ms|    2.833 ms|    4.640 ms|    2.639 ms|*   2.192 ms|    3.302 ms|   49.539 ms|    2.894 ms
3|   10.080 ms|    4.494 ms|    6.121 ms|    4.529 ms|    3.990 ms|    5.533 ms|    6.406 ms|*   3.219 ms
4|    0.798 ms|*   0.523 ms|    1.967 ms|    2.809 ms|    2.009 ms|    4.611 ms|    2.241 ms|    1.386 ms
----N=500----
i|       naive|      merger|mergerForget|       chain|         flo|    floUnrec|   floUnrec2|   floUnrec3
0|   79.072 ms|   81.197 ms|  125.544 ms|*  33.574 ms|         N/A|   95.706 ms|  151.997 ms|   61.235 ms
1|   77.894 ms|   78.996 ms|  114.487 ms|*  42.192 ms|         N/A|   93.389 ms|  157.990 ms|   73.660 ms
2|   64.385 ms|   85.848 ms|  100.232 ms|*  32.508 ms|         N/A|   93.062 ms|  128.168 ms|   66.846 ms
3|   57.281 ms|   78.046 ms|   88.486 ms|*  18.227 ms|         N/A|   88.657 ms|  127.992 ms|   75.526 ms
4|   56.792 ms|   90.672 ms|   89.867 ms|*  18.947 ms|         N/A|   94.074 ms|  131.775 ms|   64.280 ms
----N=1000----
i|       naive|      merger|mergerForget|       chain|         flo|    floUnrec|   floUnrec2|   floUnrec3
0|  456.059 ms|  914.560 ms|  469.776 ms|*  75.038 ms|         N/A|  319.247 ms|  393.977 ms|  245.059 ms
1|  469.018 ms|  959.324 ms|  481.659 ms|*  93.892 ms|         N/A|  368.351 ms|  410.677 ms|  254.531 ms
2|  413.475 ms|  984.540 ms|  448.264 ms|*  81.352 ms|         N/A|  318.276 ms|  399.826 ms|  317.413 ms
3|  408.906 ms|  891.445 ms|  453.831 ms|*  73.449 ms|         N/A|  366.814 ms|  416.535 ms|  248.729 ms
4|  403.562 ms|  890.305 ms|  432.970 ms|*  72.053 ms|         N/A|  330.597 ms|  409.124 ms|  279.548 ms

[Flodelarab]

Code :

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

for i in $(echo '5 10 50 100 500 1000'|sed 's/ /\n/');do echo "----N=$i----";node stress.js $i;done

Je crois que je préfère mourir que de voir cela

Code :

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

for i in 5 10 50 100 500 1000;do echo "----N=$i----";node stress.js $i;done

Simplement. Non ?

Remplacer l'espace par un retour à la ligne ne sert à rien.
Et utiliser une substitution de commande pour écrire ce que tu peux écrire naturellement n'est pas plus adroit.

[Invité]

Simplement. Non ?

terrible!

depuis tant d'années j'y allais à coup de sed ou tr...

[pseudocode]

Bonsoir,

Le problème posé s'appelle le dénombrement (ou l'étiquetage) des "composantes connexes".
Il y a différents exemples d'algo dans la rubrique "contribuez" de ce forum.

[trihanhcie]

Merci pour votre aide!

[anapurna]

salut

pour la version de flo il y a moyen
de gagner de temps en prenant un pas de deux dans la boucle
forcement si c'est ton voisin tu le trouve sinon tu n'as pas besoin de le parcourir

de plus la boucle principal peut être divisé par deux
en cherchant a chaque tour les deux extrêmité

Code :

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

1
2
3
 
    Lig := IPos mod High(Mat);
    Col := IPos Div High(Mat[0]);

et

Code :

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

1
2
3
 
     Lig := (CountTot-IPos) mod High(Mat);
     Col := (CountTot-IPos) Div High(Mat[0]);