Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Membre actif
    Inscrit en
    février 2006
    Messages
    522
    Détails du profil
    Informations forums :
    Inscription : février 2006
    Messages : 522
    Points : 263
    Points
    263

    Par défaut Nombre de "groupes" dans une matrice 2D

    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

  2. #2
    Invité
    Invité(e)

    Par défaut

    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

  3. #3
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 288
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 288
    Points : 7 750
    Points
    7 750

    Par défaut

    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.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  4. #4
    Invité
    Invité(e)

    Par défaut

    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
    Dernière modification par Invité ; 28/08/2018 à 22h29.

  5. #5
    Membre actif
    Inscrit en
    février 2006
    Messages
    522
    Détails du profil
    Informations forums :
    Inscription : février 2006
    Messages : 522
    Points : 263
    Points
    263

    Par défaut

    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?

  6. #6
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 288
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 288
    Points : 7 750
    Points
    7 750

    Par défaut

    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.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  7. #7
    Membre actif
    Inscrit en
    février 2006
    Messages
    522
    Détails du profil
    Informations forums :
    Inscription : février 2006
    Messages : 522
    Points : 263
    Points
    263

    Par défaut

    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

  8. #8
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 288
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 288
    Points : 7 750
    Points
    7 750

    Par défaut

    Et quand 2 et 3 se rencontrent ? Que fais-tu ? (Ce qui n'est pas le cas ici)
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  9. #9
    Membre expérimenté

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    740
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 72
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 740
    Points : 1 453
    Points
    1 453
    Billets dans le blog
    5

    Par défaut Nombre de "groupes" dans une matrice 2D

    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é.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  10. #10
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 729
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 729
    Points : 4 408
    Points
    4 408

    Par défaut

    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;
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  11. #11
    Invité
    Invité(e)

    Par défaut

    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

  12. #12
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 729
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 729
    Points : 4 408
    Points
    4 408

    Par défaut

    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
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

  13. #13
    Membre actif
    Inscrit en
    février 2006
    Messages
    522
    Détails du profil
    Informations forums :
    Inscription : février 2006
    Messages : 522
    Points : 263
    Points
    263

    Par défaut

    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

  14. #14
    Invité
    Invité(e)

    Par défaut

    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
    Dernière modification par Invité ; 31/08/2018 à 23h22.

  15. #15
    Invité
    Invité(e)

    Par défaut

    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
    Dernière modification par dourouc05 ; 01/09/2018 à 17h08.

  16. #16
    Expert éminent Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    septembre 2005
    Messages
    3 288
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : septembre 2005
    Messages : 3 288
    Points : 7 750
    Points
    7 750

    Par défaut

    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.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.
    Votre problème est résolu ? Cliquez sur en bas de page.

    Linux, grep/sed/awk/xml... et autres fichiers plats, Java, C++

  17. #17
    Invité
    Invité(e)

    Par défaut

    Simplement. Non ?
    terrible!

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

  18. #18
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    décembre 2006
    Messages
    10 054
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 46
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : décembre 2006
    Messages : 10 054
    Points : 15 743
    Points
    15 743

    Par défaut

    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  19. #19
    Membre actif
    Inscrit en
    février 2006
    Messages
    522
    Détails du profil
    Informations forums :
    Inscription : février 2006
    Messages : 522
    Points : 263
    Points
    263

    Par défaut

    Merci pour votre aide!

  20. #20
    Expert confirmé
    Avatar de anapurna
    Homme Profil pro
    Développeur informatique
    Inscrit en
    mai 2002
    Messages
    2 729
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Arts - Culture

    Informations forums :
    Inscription : mai 2002
    Messages : 2 729
    Points : 4 408
    Points
    4 408

    Par défaut

    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]);
    Nous souhaitons la vérité et nous trouvons qu'incertitude. [...]
    Nous sommes incapables de ne pas souhaiter la vérité et le bonheur, et sommes incapables ni de certitude ni de bonheur.
    Blaise Pascal
    PS : n'oubliez pas le tag

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [2008R2] Problème de nombre de colonnes dans une matrice
    Par cana13 dans le forum SSRS
    Réponses: 5
    Dernier message: 17/11/2011, 12h51
  2. Nombre de colonnes dans une matrice
    Par kimTunisia dans le forum Débuter
    Réponses: 9
    Dernier message: 27/07/2011, 13h30
  3. [Débutant] calculer nombre des 1 dans une matrice
    Par angel_tn dans le forum Images
    Réponses: 3
    Dernier message: 02/05/2010, 08h33
  4. Nombre de 1 dans une matrice
    Par Wargment dans le forum MATLAB
    Réponses: 2
    Dernier message: 05/10/2009, 15h51
  5. Réponses: 5
    Dernier message: 22/09/2006, 16h07

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo