Listen bearbeiten und vergleichen

Mawilo · Donnerstag 15. April 2004, 11:05

Hallo,

ich möchte zwei Dateien miteinander vergleichen und die Unterschiede in eine neue Datei schreiben. Dazu müssen die beiden Dateien aber erst bearbeitet werden.
Die Dateien haben beide immer folgenden Aufbau:
Route; OrtAb; ZeitAb; OrtAn; ZeitAn; Gültigkeit
Bsp: 12345; AA; 08:15; ZZ; 10:20; 12345..

Das Problem ist, dass erst in beiden Listen mehrere Einträge zusammengefasst werden müssen, um die Listen vergleichbar zu machen.

zB: aus
12345; AA; 08:15; LL; 09:40; 12345.. und
12345; LL; 09:45; OO; 10:02; 12345.. und
12345; OO; 10:05; ZZ; 10:20; 12345.. muss
12345; AA; 08:15; ZZ; 10:20; 12345.. werden.

Nur Zeilen mit dem selben Wert Route dürfen zusammengefasst werden.
Der Wert Gültigkeit (1=Mo, 2=Di, Punkt = nicht gültig) muss als kleinster gemeinsamer Nenner verstanden werden. Die Zeilen dürfen nur an den gültigen Tagen zusammengefasst werden.
Und zu allem Übel muss auch noch die Mitternachtsgrenze beachtet werden.
Bsp: aus

12345; AA; 22:15; CC; 23:40; 1234567 und
12345; CC; 23:43; EE; 23:58; 12345.. und
12345; EE; 00:03; GG; 00:40; 12345.. muss

12345; AA; 22:15; GG; 00:40; 12345.. und
12345; AA; 22:15; CC; 23:40; .....67 werden

Ist eine Route (Teilstück oder komplett)an einigen oder allen Tagen doppelt vorhanden, so soll die Doppelung ignoriert werden.

Wenn das geschafft ist, sollen beide Listen miteinander verglichen werden und alle Unterschiede in eine Datei geschrieben werden.

Gibt es in Python Module, die so etwas komfortabel erledigen? Da ich keine Erfahrung mit so komplexen Dingen habe, bin ich für jeden Lösungsansatz dankbar.

Stephan

Dookie · Donnerstag 15. April 2004, 13:47

Hi Stephan,

Python bietet schon sehr mächtige Werkzeuge zur Listenverarbeitung. Bei Deinem sehr speziellen Problem wirst Du aber um selber programmieren nicht rum kommen.

Ich würde mir für die Zeilen eine eigene Klasse erstellen.

Code: Alles auswählen

class RouteLine(object):
    __slots__ = ["route", "ort_ab", "zeit_ab", "ort_an", "zeit_an", "gueltig"]
    
    def __init__(self, arg):
        if isinstance(arg, basestring):
            l = arg.split(';')
            self.route   = l[0].strip()
            self.ort_ab  = l[1].strip()
            self.zeit_ab = l[2].strip()
            self.ort_an  = l[3].strip()
            self.zeit_an = l[4].strip()
            self.gueltig  = l[5].strip() # hier eventuell mit einem Set arbeiten!
        else:
            self.route    = arg.route
            self.ort_ab  = arg.ort_ab
            self.zeit_ab = arg.zeit_ab
            self.ort_an  = arg.ort_an
            self.zeit_an = arg.zeit_an
            self.gueltig  = arg.gueltig

    def __str__(self):
        return "; ".join([self.route, self.ort_ab, self.zeit_ab, self.ort_an, self. zeit_an, self.gueltig])

    def is_joinable(self, other):
        return self.route == other.route and ... # weitere Bedingungen damit  zusammengefasst werde kann.

    def join(self, others):
        res = [RouteLine(self)]
        for other in others:
            if is_joinalble(self, other):
                if not is_joinable(res[-1], other): # hier passts nicht mehr dazu
                    res.append(RouteLine(self)) # neue Zeile wird gebraucht
                res[-1].ort_an = other.ort_an
                res[-1].zeit_an = other.zeit_an
                ... # Gültigkeit noch bearbeiten
        return res # gibt liste mt 1 oder mehreren Routen-Zeilen zurück

Dies mal nur als Ansatz. Ist so natürlich noch nicht lauffähig.

Gruß

Dookie

Mawilo · Freitag 16. April 2004, 07:34

Hallo Dookie,

vielen Dank für Deine Idee. Das ist schon ein schwerer Brocken für einen Anfänger wie mich. Kannst Du noch ein paar Erklärungen zu der Klasse schreiben?

Stephan

Dookie · Freitag 16. April 2004, 18:14

Hi Stephan,

ich hab mir dein Problem nochmal genauer angeschaut.
Besonders Problematisch wirds, da aus 2 Zeilen beim Zusammenlegen bis zu 3 Zeilen entstehen können.
z.B.: aus
12345; AA; 08:15; LL; 09:40; 1234.. und
12345; LL; 09:45; OO; 10:02; ..3456.
wird
12345; AA; 08:15; LL; 09:40; 12.....
12345; AA; 08:15; OO; 10:02; ..34...
12345; LL; 09:45; OO; 10:02; ....56.

Wenn dann noch weitere Zeilen dazukommen muss noch geprüft werden, wo sich diese am Besten hinzunehmen lassen.

Ich schau mir das am Wochenende nochmal an, vielleicht komm ich auf eine elegantere Lösung.

Gruß

Dookie

Dookie · Freitag 16. April 2004, 20:14

so hab mal ein Script gemacht, das mit Deinen Beispielen funktioniert.

Code: Alles auswählen

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
from sets import Set

class Route(list):
    """ Spezielle Liste für Routen """
    # --- Properties: damit kann auf die Elemente auch als Attribute zugegriffen werden ---
    def get_route(self):
        return self[0]
    def set_route(self, value):
        self[0] = value
    route = property(get_route, set_route)

    def get_gueltig(self):
        return Set([int(x) for x in self[5] if x.isdigit()])
    def set_gueltig(self, value):
        self[5] = "".join([x in value and str(x) or "." for x in xrange(1,8)])
    gueltig = property(get_gueltig, set_gueltig, doc="returns gueltig as Set")

    #--- special Methoden ---
    def __init__(self, *args, **kw):
        if isinstance(args[0], basestring):
            super(Route, self).__init__(*args[1:], **kw)
            # String an ";" in Liste zerlegen und Elemente strippen
            l = [x.strip() for x in args[0].split(';')]
            for x in l:
                self.append(x)
        else:
            super(Route, self).__init__(*args, **kw)
            if isinstance(args[0][-1], Set):
                self.gueltig = args[0][-1]
        
    def __str__(self):
        return "; ".join(self)

    #--- routen Methoden ---
    def is_joinable(self, other):
        """ Teste ob self mit other zusammengelegt werden kann """
        return self.route == other.route and bool(self.gueltig & other.gueltig)

    def join(self, other):
        """ zwei Routen zusammenlegen """
        result = []
        sgs = self.gueltig # Gültigkeit von self
        ogs = other.gueltig # Gültigkeit von other
        if sgs == ogs: # Gültigkeiten sind gleich
            result.append(Route([self[0], self[1], self[2],
                                 other[3], other[4], self[5]]))
        else: # Gültigkeiten sind ungleich
            sgsa = sgs - ogs
            if sgsa: # Gültigkeiten nur in self
                result.append(Route([self[0], self[1], self[2],
                                     self[3], self[4], sgsa]))
            sgsb = sgs & ogs
            if sgsb: # Gültigkeiten in self und in other
                result.append(Route([self[0], self[1], self[2],
                                     other[3], other[4], sgsb]))
            sgsc = ogs - sgs
            if sgsc: # Gültigkeiten nur in other
                result.append(Route([other[0], other[1], other[2],
                                     other[3], other[4], sgsc]))
        return result

    def multijoin(self, others):
        """ self mit mehreren anderen Routen zusammenlegen """
        result = [Route(self)]
        for other in others:
            if result[0].is_joinable(other):
                result = result[0].join(other)+result[1:]
            elif len(result) > 1 and result[1].is_joinable(other):
                result = result[:1] + result[1].join(other) + result[2:]
            elif len(result) > 2 and result[2].is_joinabel(other):
                result = result[:2] + result[2].join(other)
        return result

if __name__ == "__main__":
    import sys
    mycoding = sys.getfilesystemencoding()

    zeilen = ["12345; AA; 22:15; CC; 23:40; 1234567",
              "12345; CC; 23:43; EE; 23:58; 12345..",
              "12345; EE; 00:03; GG; 00:40; 12345.."]

    # Zeilen in Routen wandeln
    routen = [Route(x) for x in zeilen]
    for i in routen:
        print i
    print u"zusammengeführt zu:".encode(mycoding)
    neu = routen[0].multijoin(routen[1:])
    for i in neu:
        print i
    print
    zeilen = ["12345; AA; 08:15; LL; 09:40; 12345..",
              "12345; LL; 09:45; OO; 10:02; 12345..",
              "12345; OO; 10:05; ZZ; 10:20; 12345.."]
    routen = [Route(x) for x in zeilen]
    for i in routen:
        print i
    print u"zusammengeführt zu:".encode(mycoding)
    neu = routen[0].multijoin(routen[1:])
    for i in neu:
        print i
    print

Bei Fragen, schneide die Zeilen aus und stelle die Fragen dazu. Ich weiss ja nicht was Dir schon klar ist und was nicht und ich habe nicht die Lust jede Zeile einzeln zu kommentieren.

Gruß

Dookie

Dookie · Freitag 16. April 2004, 20:36

Ich hab die Methode multijoin() noch verbessert.

Code: Alles auswählen

    def multijoin(self, others):
        """ self mit mehreren anderen Routen zusammenlegen """
        result = [Route(self)]
        for other in others:
            i = 0
            while i < len(result):
                if result[i].is_joinable(other):
                    tmp = result[i].join(other)
                    result[i] = tmp[0]
                    if len(tmp) > 1:
                        result = tmp[1:]+result #nochmal geändert
                        i += len(tmp)-1
                i += 1
        return result

Gruß

Dookie

hans · Freitag 16. April 2004, 20:39

Wenn ich das richtig sehe, sind bei drei Teilstrecken folgende Streckenkombinationen sinnvoll.

Code: Alles auswählen

Die Ausgangsbasis:
12345; AA; 08:15; LL; 09:40; 12345...
12345; LL; 09:45; OO; 10:02; 12345..
12345; OO; 10:05; ZZ; 10:20; 12345..

Die möglichen Strecken:
AA-LL
AA-OO
AA-ZZ
LL-OO
LL-ZZ
OO-ZZ

Ich hoffe, dass ich das bis dahin richtig verstanden habe.

Wenn ich dich richtig verstanden habe, dann kann die Strecke AA-ZZ sowohl aus einer Direktverbindung als als auch aus einer Kombination beliebiger Teilstrecken bestehen. Ich hoffe, dass das bis hierhin auch richtig ist.

Die zweite Liste beinhaltet nur komplette Routen. und diese sollen mit den möglichen routen verglichen werden. Was soll da eigentlich verglichen werden? Die reine Fahrtzeit, die Gesamtfahrzeit mit Aufenthalt, ....?

@Dookie

Ich weiß nicht, wenn mir in der Firma jemand so eine Aufgabe stellen würden, würde ich sofort in ner Datenbank an zu wühlen fangen, in diesem Fall nicht mit MySQL. Habe soetwas in der Richtung aber noch nie Programmiert. Vielleicht übersehe ich aber auch etwas und würde Schiffbruch erleiden.

Hans

Dookie · Freitag 16. April 2004, 20:49

Hi hans,

also von den Strecken hat er gar nicht gesagt, daß die auch noch berücksichtigt werden müssen. Dann wirds wirklich eher ein Fall für eine Datenbank.
Ich dachte die Routen sind schon durch den ersten Eintrag fesstgelegt und es brauchen nur noch die Tage an denen die Gültigkeit besteht berücksichtigt werden.
Komplex wird das ganze auf jeden Fall. Ob mit oder ohne Datenbank.

Gruß

Dookie

Mawilo · Samstag 17. April 2004, 07:44

Hi Dookie, hi hans,

vielen Dank für Eure Ideen.
Mein erster Ansatz war, die Daten in eine temporäre Datei zu schreiben und dort erst mal zu sortieren. Beim Zusammenfassen sollte das dann in etwa so gehen:
1. Bedingung: Wert Route muss gleich sein
2. Bedingung: Die Gültigkeit muss stimmen

Nun wird im Idealfall die Route geschrieben. Danach AbOrt und AbZeit, wobei dieser Eintrag über AbZeit gwählt wird (der erste (niedrigste) Wert). Als nächstes wird der Wert AnOrt und AnZeit gesucht. Das ist dann der letzte (höchste) Wert von AnZeit. Zum Schluß wird dann die Gültigkeit geschrieben. Es kann also vorkommen, dass zwischenliegende Zeilen ignoriert werden. Das muss man allerdings für jede mögliche Gültigkeit machen

Ich hoffe, dass macht mein Problem etwas klarer.

Stephan

Dookie · Samstag 17. April 2004, 10:44

Hi Stephan,

Mein erster Ansatz war, die Daten in eine temporäre Datei zu schreiben und dort erst mal zu sortieren.

Keine gute Idee, in einer Datei zu sortieren ist wohl das ineffizienteste was es gibt.
Folgende Methode bei der Klasse Route z.B. vor __str__ eingefügt. und Du kannst eine Liste mit Routen einfach mit liste.sort() sortieren.

Code: Alles auswählen

    def __cmp__(self, other):
        return (cmp(other[0], self[0]) or # Route
                cmp(other[5], self[5]) or  # Gueltigkeit
                cmp(other[2], self[2]) or  # Zeit an
                cmp(other[4], self[4])) # Zeit ab

Ansonst, Beispiele sagen mehr als 1000 missverständliche Worte.

Gruß

Dookie

Mawilo · Freitag 23. April 2004, 15:27

Hi Dookie,

ich habe mal etwas mit dem Code gespielt und folgende Beispiele verwendet:

Code: Alles auswählen

zeilen = ["7022;DSN;06:52;DME;08:37;.....67",
              "7022;DPI;07:32;DH;07:58;12345..",
              "7022;DH;08:00;DME;08:37;12345.."]

und:

Code: Alles auswählen

zeilen = ["7000;DH;04:30;DN;04:36;12345..",
              "7000;DH;04:30;DME;05:09;.....67",
              "7000;DH;04:30;DCW;04:56;1234567",
              "7000;DH;04:30;DN;04:36;1234567"]

Die Routlist sieht im Original so aus (kleiner Ausschnitt):

Code: Alles auswählen

7000;DH;04:30;DN;04:36;12345..
7000;DH;04:30;DME;05:09;.....67
7001;DH;04:30;DRK;04:36;1234567
7000;DH;04:30;DCW;04:56;1234567
7000;DH;04:30;DN;04:36;1234567
7001;DH;04:30;DSA;05:25;12345..
7001;DH;04:30;DSN;05:37;.....67
7001;DH;04:30;DPI;04:57;1234567
7001;DH;04:30;DRAT;05:12;1234567
7003;DN;04:51;DPI;05:27;.....67
7009;DME;05:20;DPI;06:27;.....67
7012;DPI;06:02;DME;07:09;.....67
7014;DH;07:00;DN;07:06;1234567
7018;DPI;07:02;DME;08:09;.....67
7021;DN;07:21;DH;07:28;12345..
7021;DH;07:30;DSN;08:37;1234567
7022;DSN;06:52;DME;08:37;.....67
7022;DPI;07:32;DH;07:58;12345..
7022;DH;08:00;DME;08:37;12345..
7023;DME;07:20;DPI;08:27;.....67
7023;DH;08:05;DPI;08:34;12345..
7025;DN;08:21;DH;08:28;1234567
7025;DH;08:30;DSN;09:37;1234567
7026;DPI;08:02;DME;09:09;.....67
7027;DME;08:20;DPI;09:27;.....67
7027;DH;09:00;DPI;09:27;12345..
7028;DSN;07:52;DME;09:37;.....67
7028;DH;09:00;DME;09:37;12345..
7029;DME;08:50;DH;09:28;12345..
7029;DH;09:30;DSN;10:37;12345..
7031;DME;09:20;DPI;10:34;.....67
7031;DH;10:05;DPI;10:34;12345..

Das Ergebnis ist noch nicht so, wie es sein sollte. Im ersten Beispiel müssten zwei Zeilen als Ergebnis rauskommen:
7022;DSN;06:52;DME;08:37;.....67 und
7022;DPI;07:32;DME;08:37;12345..

Im zweiten Beispiel wir es noch komplizierter, da müsste das Ergebnis aus folgenden zwei Zeilen bestehen:
7000;DH;04:30;DME;05:09;.....67 und
7000;DH;04:30;DCW;04:56;12345..

Ich sollte mich wahrscheinlich doch mal mit 'ner Datenbank anfreunden

@Hans

in diesem Fall nicht mit MySQL

Warum sollte ich nicht mit MySQL arbeiten? Das ist die einzigste Datenbank, mit der ich schon mal bisschen "rumgemacht" habe.

Stephan

hans · Freitag 23. April 2004, 18:58

MySql war bisher immer schwach was referentielle Integrität (prüft, ob gelöscht werden darf oder nicht), SubQueries, etc anbelangt. Dafür ist die Dantenbank aber schnell. Bevor ich jetzt Prügel beziehe, meine Kenntnisse sind seit 3.x nicht mehr wesentlich erweitert worden. Ich glaube, es ist gerade Version 5.0 rausgekommen. Also, wenn sich da etwas getan hat, her mit den Infos.

Bin eigentlich ziemlich begeistert von Firebird, auch wenns mit der ODBC / JDBC Installation doch einige Konfusionen gab, sowohl in Windows als auch unter Linux. Aber mittlerweile hab ich das im Griff einschließlich Zugriff mit Delphi. Habe da eine Sales Datei mit ca 800.000 Records, da kann man sich schon mal so richtig dran austoben.

Hans