Discussion :

[Currahee]

Bonjour,

Quelqu'un connaitrait-il un algorithme permettant la comparaison de deux tableaux triés. Je m'explique:

Les deux Tableaux ont chacun deux colonnes : la premiere représente un identifiant, la seconde un libellé

L'algo doit permettre de :
- recenser dans le deuxième tableau les nouveaux enregistrements (nouveaux identifiants)
- recenser les enregistrements du premier tableau qui ont été supprimés
- quand un enregistrement existe dans les deux tableaux, regarder s'il a été modifié (comparaison sur la colonne libellé)

On m'a dit que c'était possible sur une seule passe, mais je ne trouve pas l'algo sur le net et ai du mal à le retrouver par moi-même

Merci d'avance à ceux qui connaissent cet algo

[Nemerle]

Tes tableaux sont-ils TRIES par rapport à la 1ière colonne??

[Currahee]

Tes tableaux sont-ils TRIES par rapport à la 1ière colonne??

Oui c'est ça

[Nemerle]

Tu as 2 tableaux T1 et T2.Rapidement, tu prends deux entiers i=j=1:

- tu regardes si T1.ID[i] = T2.ID[i].
- Si oui, tu checkes si il y a eu modification du libellé. Ensuite tu fais i=i+1, j=j+1
- Si non, il y a eu suppression! Ensuite tu fais i=i+1

Quand tout T1 est lu, les éléments de T2 qui restent sont les nouveaux!

[Currahee]

Tu as 2 tableaux T1 et T2.Rapidement, tu prends deux entiers i=j=1:

- tu regardes si T1.ID[i] = T2.ID[i].
- Si oui, tu checkes si il y a eu modification du libellé. Ensuite tu fais i=i+1, j=j+1
- Si non, il y a eu suppression! Ensuite tu fais i=i+1

Quand tout T1 est lu, les éléments de T2 qui restent sont les nouveaux!

Imaginons l'apparition d'un nouvel élément dans le nouveau tableau (ici B):

vieux(0, 0) = "A"
vieux(1, 0) = "C"
vieux(2, 0) = "D"
vieux(3, 0) = "E"
.....

nouveau(0, 0) = "A"
nouveau(1, 0) = "B"
nouveau(2, 0) = "C"
nouveau(3, 0) = "D"
nouveau(4, 0) = "E"
.....

Premier coup A = A je verifie le libelle puis i+1 , j+1
Deuxieme coup avec ta proposition : C <> B donc C a disparu ce qui est faux à cause de l'insertion de B qui a décalé C au rang suivant

[souviron34]

pseudocode :

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
Ouvrir les 2 fichiers
 
lire ligne vieux
         chercher dans nouveau si ligne
                si NOT ligne
                       disparu
                sinon
                    si ligne modifiée
                        modification
                    fin
                fin
 
stocker dernier id
 
fermer vieux
 
chercher dernier id vieux dans nouveau
de (dernier id+1) à fin
         nouveau

[Currahee]

pseudocode :

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
Ouvrir les 2 fichiers
 
lire ligne vieux
         chercher dans nouveau si ligne
                si NOT ligne
                       disparu
                sinon
                    si ligne modifiée
                        modification
                    fin
                fin
 
stocker dernier id
 
fermer vieux
 
chercher dernier id vieux dans nouveau
de (dernier id+1) à fin
         nouveau

J'ai pas testé mais ça semble interessant, à ceci près que tu n'indiques pas la récupération des nouveaux enregistrements. A fignoler donc.

Pendant que tu postais, j'ai moi même reréfléchi au pb : solution dans post suivant

[Currahee]

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
 
    i = 0    ' Indice associé au vieux tableau
    j = 0    ' Indice associé au nouveau tableau
 
    'Recherche du tableau contenant le plus d'enregistrement
    ' ... imax ...
    ' ... jmax ...
 
    If imax > jmax Then
       max = imax
    Else
       max = jmax
    End If
 
    While i <> max And j <> max
      If vieux(i, 0) = nouveau(j, 0) Then
        If vieux(i, 1) = nouveau(i, 1) Then
          MsgBox "Enregistrement " & vieux(i, 0) & " identique"
        Else
          MsgBox "Enregistrement " & vieux(i, 0) & " modifié"
        End If
        i = i + 1
        j = j + 1
      ElseIf vieux(i, 0) < nouveau(j, 0) Then
        If vieux(i, 0) <> "" Then
          MsgBox "Enregistrement " & vieux(i, 0) & " supprimé"
          i = i + 1
        Else
          MsgBox "Enregistrement " & nouveau(j, 0) & " ajouté"
          j = j + 1
        End If
      ElseIf vieux(i, 0) > nouveau(j, 0) Then
        If nouveau(j, 0) <> "" Then
          MsgBox "Enregistrement " & nouveau(j, 0) & " ajouté"
          j = j + 1
        Else
          MsgBox "Enregistrement " & vieux(j, 0) & " supprimé"
          i = i + 1
        End If
      End If
    Wend

Voilà ma solution ou je pense avoir géré les effets de bords (vieux tableau contient plus d'éléments que le nouveau et réciproquement).

J'ai testé chez moi, ça semble OK, mais si vous voyez une grosse erreur n'hésitez pas à me taper sur les doigts

[Nemerle]

Imaginons l'apparition d'un nouvel élément dans le nouveau tableau (ici B):

vieux(0, 0) = "A"
vieux(1, 0) = "C"
vieux(2, 0) = "D"
vieux(3, 0) = "E"
.....

nouveau(0, 0) = "A"
nouveau(1, 0) = "B"
nouveau(2, 0) = "C"
nouveau(3, 0) = "D"
nouveau(4, 0) = "E"
.....

Premier coup A = A je verifie le libelle puis i+1 , j+1
Deuxieme coup avec ta proposition : C <> B donc C a disparu ce qui est faux à cause de l'insertion de B qui a décalé C au rang suivant

ok, c'est pas la peine de Si c'est des VRAIS identifiants, tu ne peux pas créer un identifiant entre A et C

Maintenant, si tu veux que je t'aide, car cet algo est tellement simple qu'un 1iere année d'info sait le faire, je peux rajouter 3 lignes pour fare fonctionner le truc. Ou bien je peux me brosser les cheveux...

[souviron34]

J'ai pas testé mais ça semble interessant, à ceci près que tu n'indiques pas la récupération des nouveaux enregistrements. A fignoler donc.

Faut lire jusqu'au bout

[Currahee]

ok, c'est pas la peine de Si c'est des VRAIS identifiants, tu ne peux pas créer un identifiant entre A et C

Maintenant, si tu veux que je t'aide, car cet algo est tellement simple qu'un 1iere année d'info sait le faire, je peux rajouter 3 lignes pour fare fonctionner le truc. Ou bien je peux me brosser les cheveux...

Cool le c'était pas méchant C'est simplement que l'algo proposé ne répondait totalement pas à ma recherche et que je me demandais si on s'était bien compris. Si j'avais mal exprimé ma demande, avec par exemple l'utilisation visiblement inappropriée à la situation du terme identifiant, je m'en excuse.

Si ton algo était incomplet et que tu le savais, il suffisait de me dire "tiens base de l'algo à compléter"...

J'ai réussi à mettre en forme l'algo que je désirai, je l'ai posté pour que les forumeurs en profitent, même si comme je l'ai mis dans mon premier post j'imagine bien évidemment que j'ai pas inventé la poudre, et que cet algo existe depuis des lustres... J'ai même suggéré que mon algo puisse être en partie faux car je ne suis pas un "vrai informaticien" et que donc des cas particuliers ont pu m'échapper...

Je viens sur le forum demander gentiment de l'aide, j'essaye d'expliquer clairement ma demande, je poste la solution quand je la trouve par moi-même, je vois pas ou j'ai mérité une aggression...

Merci pour ton aide,

Cordialement

[Nemerle]

Pas de soucis, c'était juste pour te dire d'éviter les !! Je reprends:

Tu as 2 tableaux T1 et T2.Rapidement, tu prends deux entiers i=j=1:

- tu regardes si T1.ID[i] = T2.ID[i] :
- Si oui, tu checkes si il y a eu modification du libellé. Ensuite tu fais i=i+1, j=j+1
- Si non, tu regardes si T1.ID[i] < T2.ID[i] :
- Si oui, il y a eu suppression! Ensuite tu fais i=i+1
- Si non (on a donc T1.ID[i] > T2.ID[i]), il y a eu création dans T2. Tu fais j=j+1


Si tu as fini T1 et qu'il reste des T2, ce sont des créations.
Si tu as fini T2 et qu'il reste des T1, ce sont des suppressions.