Comparaison de Tableaux

Version imprimable

21/02/2007, 15h23
Currahee

Comparaison de Tableaux

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 :oops: et ai du mal à le retrouver par moi-même :?

Merci d'avance à ceux qui connaissent cet algo ;)
21/02/2007, 15h26
Nemerle

Tes tableaux sont-ils TRIES par rapport à la 1ière colonne??
21/02/2007, 15h34
Currahee

Citation:

Envoyé par Nemerle

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

Oui c'est ça
21/02/2007, 15h41
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!
21/02/2007, 15h52
Currahee

Citation:

Envoyé par 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!

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 :?

pseudocode :

Code:

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

Citation:
Envoyé par souviron34
pseudocode :
Code:

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

Code:

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 ;)

22/02/2007, 00h38
Nemerle

Citation:

Envoyé par Currahee

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...
22/02/2007, 02h19
souviron34

Citation:

Envoyé par Currahee

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 :roll:
22/02/2007, 10h39
Currahee

Citation:

Envoyé par Nemerle

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 8O 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
23/02/2007, 11h14
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.