Listen vergleichen...

[jens]

Gegeben z.B.:

Code: Alles auswählen

old = ["eins", "zwei", "drei", "veer"]
new = ["eins",         "drei", "vier"]

Raus kommen soll eine Liste wie diese:

Code: Alles auswählen

  eins
- zwei
  drei
- veer
+ vier

Nicht wirklich mit den +/- davor, aber eine Liste wie diese mit den Info's welches Element wurde hinzugefügt/weggenommen.

Ich könnte auf difflib.ndiff(old, new) zurück greifen. Damit würde ich mein Ziel schon näher kommen:

Code: Alles auswählen

diff = []
for line in difflib.ndiff(old, new):
    if line and not line.startswith("?"):
        diff.append(line)
print "\n".join(diff)

Das würde die Ausgabe von oben produzieren...

Aber ich habe nicht wirklich Strings zu vergleichen und würde die Info eingefügt/gelöscht/gleich lieber als "Attribut" haben...

Also ich hab ehr sowas:

Code: Alles auswählen

old = ["<obj 'eins'>", "<obj 'zwei'>", "<obj 'drei'>", "<obj 'veer'>"]
new = ["<obj 'eins'>",                 "<obj 'drei'>", "<obj 'vier'>"]

Und möchte dann eine der Objekte haben:

Code: Alles auswählen

[<obj 'eins'>,
<obj 'zwei'>,
<obj 'drei'>,
<obj 'veer'>,
<obj 'vier'>]

Und diese Objekte sollten dann ein Attribute über den Status haben.


Mit set(old).union(set(new)) hätte ich schon mal eine Liste mit allen zusammen. Über diese könnte ich iterieren und dann nachsehen, welche in old und new vorkommt und dann die Attribute hinzufügen. Aber das dumme, die Sortierung ist unschön:

Code: Alles auswählen

<obj 'drei'>
<obj 'eins'>
<obj 'vier'>
<obj 'zwei'>
<obj 'veer'>

Ideen?

[BlackJack]

@jens: Hast Du Dich in der `difflib` etwas weiter umgeschaut? `SequenceMatcher` scheint doch das zu sein was Du suchst, oder zumindest etwas was Du verwenden kannst. Anfang des DocStrings: „SequenceMatcher is a flexible class for comparing pairs of sequences of any type, so long as the sequence elements are hashable.”

Und die `get_opcodes()`-Methode liefert Informationen über die Operationen wie Ersetzen, Entfernen, Einfügen, und unverändert lassen von Slices, die man ausführen müsste um eine gegebene Sequenz in eine andere gegebene Sequenz zu überführen.

[jens]

Ja, damit hab ich schon rumgespielt aber noch keine Lösung gefunden.

[snafu]

@jens: Habe ich das richtig verstanden, dass dir die Methoden von `set()`-Objekten ausreichen und du jetzt im Grunde nur noch richtig sortieren willst?

[Hyperion]

Was haltet ihr hier von (nur mal so als Schnellschuss):

Code: Alles auswählen

#!/usr/bin/env python

from itertools import zip_longest, tee

def pairwise(iterable):
    """
    Aus der Doku zu `itertools`
    s -> (s0,s1), (s1,s2), (s2, s3), ...
    """
    a, b = tee(iterable)
    next(b, None)
    return zip_longest(a, b)
 
def compare(first, second):
    pf, ps = map(pairwise, (first, second))
    f, s = map(next, (pf, ps))
    while True:
        if f[0] != s[0]:
            if f[1] == s[0]:
                yield ("-", f[0])
                f = next(pf)
                continue
            elif f[0] == s[1]:
                yield("+", s[0])
                s = next(ps)
                continue
            elif f[1] == s[1]:
                yield ("-", f[0])
                yield ("+", s[0])
        else:
            yield (None, f[0])
        f = next(pf)
        s = next(ps)

def main():
    first = ["eins", "zwei", "drei", "veer"]
    second = ["eins",        "drei", "vier"]
    res = compare(first, second)
    print(list(res))
    
if __name__ == "__main__":
    main()

Edit: Ooops, da waren noch einige überflüssige Sachen drin. So ist es schon ein wenig kompakter.

[jens]

@jens: Habe ich das richtig verstanden, dass dir die Methoden von `set()`-Objekten ausreichen und du jetzt im Grunde nur noch richtig sortieren willst?

Nicht ganz. Denn es fehlt noch die Information, welcher Eintrag hinzugefügt/gelöscht/gleich ist...

[jens]

@Hyperion: Ja das scheint genau das zu machen, das ich brauche... Allerdings mußte ich zip_longest durch izip_longest ersetzten. Den zip_longest gibt es wohl erst ab python 3k, wobei es bei http://docs.python.org/py3k/library/ite ... ip_longest nicht dabeisteht...

[Hyperion]

@Jens: Ja, ich vergaß zu erwähnen, dass ich das für Python3 implementiert hatte. In Py3 gibt es ja auch kein `izip` mehr, da die Built-in Funktion `zip` dazu geworden ist. Insofern wurden da einige Namen konsolidiert, da idR. verstärkt auf Generatorfunktionen gesetzt wird; z.B. auch bei `range` (vs. `xrange` in Py2).

[jens]

Deine Version funktioniert auch nicht in allen Fällen:

Code: Alles auswählen

old = ["1", "2", "3", "veer",          "7", "8", "9"]
new = ["1",      "3", "vier", "5", "6",          "9"]

mit dem hier:

Code: Alles auswählen

for line in difflib.ndiff(old, new):
    if line and not line.startswith("?"):
        print line

Kommt das raus:

Code: Alles auswählen

  1
- 2
  3
- veer
+ vier
- 7
- 8
+ 5
+ 6
  9

Mit deinem code:

Code: Alles auswählen

(None, '1')
('-', '2')
(None, '3')
('-', '8')
('+', '6')
(None, '9')

Eine Lösung mit set() und union:

Code: Alles auswählen

def compare1(first, second):
    result = []
    for item in set(first).union(set(second)):
        tag = None
        if item not in first:
            tag = "+"
        elif item not in second:
            tag = "-"
        result.append((tag, item))
    return result

for line in compare1(old, new):
    print line

Die Ausgabe ist aber deutlich unübersichtlicher, weil die reihenfolge mehr durcheinander ist:

Code: Alles auswählen

('-', 'veer')
(None, '1')
(None, '3')
('-', '2')
('+', '5')
('-', '7')
('+', '6')
(None, '9')
('-', '8')
('+', 'vier')

EDIT: Wobei ob die Reihenfolge wirklich so wichtig ist weiß ich eh noch nicht genau... Denkbar wäre auch, das man einfach alles mit sort() regelt...

Zum Hintergrund: Es ist für https://github.com/jedie/django-reversion-compare für ein Vorher/Nachher Vergleich bei many2many Feldern...
Die Reihenfolge bestimmt sich dabei aus "ordering" des Models. Gut man könnte nun union machen, die Meta Angaben -/+/= anfügen und dann wieder so sortieren, wie es das Model vorgibt... Aber das ist doch recht kompliziert...

[jens]

Hab nun mal meine einfache Variante aufgenommen: https://github.com/jedie/django-reversi ... 664f554527

Wenn jemand noch eine Idee hat, wie man die Reihenfolge wie bei difflib beibehalten kann, immer raus damit

[Hyperion]

Stimmt, dass letzte `elif` war überflüssig:

Code: Alles auswählen

def compare(first, second):
    pf, ps = map(pairwise, (first, second))
    f, s = map(next, (pf, ps))
    while True:
        if f[0] != s[0]:
            if f[1] == s[0]:
                yield ("-", f[0])
                f = next(pf)
                continue
            elif f[0] == s[1]:
                yield("+", s[0])
                s = next(ps)
                continue
            yield ("-", f[0])
            yield ("+", s[0])
        else:
            yield (None, f[0])
        f = next(pf)
        s = next(ps)

Jetzt sollte es passen, außer, dass ich abwechselnd fehlende und hinzu gekommene Einträge ausgebe.

[BlackJack]

So könnte man das mit `difflib` machen:

Code: Alles auswählen

from difflib import SequenceMatcher


def diff(sequence_a, sequence_b):
    matcher = SequenceMatcher(a=sequence_a, b=sequence_b)
    for opcode, i, j, m, n in matcher.get_opcodes():
        if opcode == 'equal':
            yield (' ', sequence_a[i:j])
        elif opcode == 'delete':
            yield ('-', sequence_a[i:j])
        elif opcode == 'insert':
            yield ('+', sequence_b[m:n])
        elif opcode == 'replace':
            yield ('-', sequence_a[i:j])
            yield ('+', sequence_b[m:n])
        else:
            assert False, 'unknown opcode %r' % opcode


def main():
    old = ['1', '2', '3', 'veer', '7', '8', '9']
    new = ['1', '3', 'vier', '5', '6', '9']
    
    for operation, values in diff(old, new):
        for value in values:
            print operation, value


if __name__ == '__main__':
    main()

[jens]

@Hyperion: Dein letzter Stand will nicht, das kommt raus:

Code: Alles auswählen

None 9
- 9
None 9
- 9
+ 9
- 9
+ 9
- 9
+ 9
None 9

@BlackJack: Hervorragend, sowas ähnliches hatte ich zwar auch schon, aber es funktionierte noch nicht Danke!

Interessant ist, das die Reihenfolge etwas anders ist. Das mit ndiff:

Code: Alles auswählen

  1
- 2
  3
- veer
+ vier
- 7
- 8
+ 5
+ 6
  9

und das mit difflib.SequenceMatcher:

Code: Alles auswählen

  1
- 2
  3
- veer
- 7
- 8
+ vier
+ 5
+ 6
  9

[Hyperion]

@Jens: Komisch, bei mir kommt das heraus:

Code: Alles auswählen

   1
-  2
   3
-  veer
+  vier
-  7
+  5
-  8
+  6
   9

(Hab statt `None` mal auf `""` umgestellt.)

[jens]

Hatte wohl ein copy&paste Fehler...

Hier nochmal die Varianten zusammen + Ausgaben: https://gist.github.com/2647137

EDIT: Meine einfache set() Lösung noch dazugepackt.

[BlackJack]

@jens: Die Reihenfolge ist anders weil `ndiff` mehr macht; es diffed nicht nur die Zeilen als ganzes, sondern auch innerhalb der Zeilen. Du filterst ja die '?'-Zeilen aus. Während der Zeilenblock 7, 8 sich komplett von 5, 6 unterscheidet, unterscheiden sich 'veer' und 'vier' nur durch den zweiten Buchstaben. Das berechnet `ndiff` zusätzlich auch noch.

[jens]

Die "?" Angaben, welche Zeichen sich geändert haben, brauche ich nicht. Am Ende geht es um Objekte und die sind immer "komplett" anders

Die Reihenfolge "Sinnvoll" zusammen zu lassen, ist aber IMHO auch recht aufwendig. Im Grunde geht es nur so, das die Gleichenteile die Reihenfolge vorgeben...

Ist im Endeffekt wahrscheinlich eh nicht super wichtig. Die Kernfunktion reicht mir erstmal...