Duplikate in einer Liste finden

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
schumatscher
User
Beiträge: 8
Registriert: Donnerstag 27. Dezember 2018, 14:53

Ich habe eine Liste mit Integer-Einträgen (so ca. 5000 Stück) und möchte nun Duplikate herausfinden.
Wer kann mir hier die schnellste Möglichkeit der Suche aufzeigen.
Mit

Code: Alles auswählen

if set([x for x in lfdNummern if lfdNummern.count(x) >1]): 
    ergebnis =  set([x for x in lfdNummern if lfdNummern.count(x) >1])              
    with open("error_log.txt", "a+") as errorlog:
        error_text = ("Doppelte Nummer: " + str(ergebnis)
        error_text = str(error_text)
        errorlog.write(error_text)

bekomme ich zwar ein Ergebnis, habe aber das Gefühl, dass dies sehr lange dauert.
Benutzeravatar
snafu
User
Beiträge: 6738
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Würde ich in etwa so machen:

Code: Alles auswählen

def get_unique(items):
    seen = set()
    for item in items:
        if item in seen:
            write_log(f'Duplicate: {item}')
        else:
            seen.add(item)
    return seen
f-Strings gehen ab Python 3.6, andernfalls sollte format() verwendet werden.
Benutzeravatar
__blackjack__
User
Beiträge: 13079
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@schumatscher: Das dauert in der Tat zu lange, weil es unnötigerweise quadatische Laufzeit hat, das heisst bei 5000 Elementen wird jedes Element 25 Millionen mal verwendet. Und da Du das sogar zweimal machst, sind es 50 Millionen mal.

Schau Dir mal `collections.Counter` an.

Was denkst Du was die vorletzte Zeile in dem gezeigten Quelltext bewirkt‽

Schau mal in den Style Guide for Python Code bezüglich der Schreibweise von Namen in Python. `lfdNummern` sollte eher `lfd_nummern` heissen, beziehungsweise `laufende_nummern` wenn man verständlicheren Quelltext haben möchte.
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
Benutzeravatar
snafu
User
Beiträge: 6738
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

@schumatscher:
Nur damit dein eigentliches Ziel klarer wird: Willst du wissen, welche Elemente mehr als einmal vorkommen oder willst du eine von Duplikaten bereinigte Liste haben? Oder beides?
schumatscher
User
Beiträge: 8
Registriert: Donnerstag 27. Dezember 2018, 14:53

Code: Alles auswählen

def checkeDuplikat():
    pfad = ("C:\meinPfad")
    laufende_nummern = []
    for item in os.listdir(pfad):       
        with open (item) as textfile:
            for line in textfile:
                laufende_nummern.append(line[1])
                if [item for item, count in collections.Counter(laufende_nummern).items() if count >1]:
                    ergebnis = [item for item, count in collections.Counter(laufende_nummern).items() if count >1]
                    print("Doppelte Nummer: ", ergebnis , " in der Datei ",  item)
                    with open("error_log.txt", "a+") as errorlog:
                        error_text = (str(item) + " Doppelte Nummer: " + str(ergebnis) +"\n")
                        errorlog.write(error_text)
            laufende_nummern = []

liefert nun zuverlässig die Werte; jetzt habe ich das Gefühl, dass es deutlich schneller funktioniert - ich werde die Zeit später mal messen.

Die doppelten Nummern werden jetzt aber mehrfach ausgegeben - das kann ich mir durch die Schleifenaufrufe erklären, wie kann ich aber die Schleifen vermeiden?
Ich muss ja zu Beginn jede Datei in meinem Verzeichnis öffnen (Zeile 5), für jede Zeile öffne ich die Datei (Zeile 6) und dann durchlaufe ich die einzelnen Zeilen und füge die Nummern der Liste bei.
Ganz unten leere ich die Liste und fange wieder mit der nächsten Zeile an.

@snafu: ich möchte die Duplikate finden und in der Error.log ausgeben; die Einträge in den Dateien dürfen dabei nicht verändert werden.
Benutzeravatar
__blackjack__
User
Beiträge: 13079
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@schumatscher: Das ist ziemlich sicher nicht der Code den Du tatsächlich verwendest, oder Du hast nicht überprüft ob der Funktioniert. Oder die laufende Nummer ist tatsächlich in jeder Zeile das zweite Zeichen, und nur das.

Das die Nummern mehrfach ausgegeben werden liegt an der falschen Reihenfolge in der Dein Code abläuft. Du willst das nicht für jede Zeile aufs neue Prüfen sondern erst alle Nummern einlesen und *dann* *einmal* die Prüfung auf Duplikate machen.

Und diese Liste solltest Du auch wenn es jetzt effizienter geschieht, nur *einmal* erstellen.

'+' im Dateimodus ist in 99,9% der Fälle falsch. Bei Textdateien wage ich zu behaupten, das es in 100% der Fälle falsch ist. Ich würde die Datei auch nur einmal öffnen, und nicht für jede verarbeitete Datei öffnen und schliessen.


`laufende_nummern` wird an den falschen Stellen an eine leere Liste gebunden. Wenn man das kurz vor Gebrauch macht, muss man das nur an *einer* Stelle im Code machen.

`item` ist hier ein ziemlich generischer Name – das geht besser.

Die Klammern um die Zeichenkette bei der Zuweisung von `pfad` sind überflüssig.

Pfade und Dateinamen sind oft gute Kandidaten für Konstanten, damit man die nicht im ganzen Quelltext verteilt suchen muss und einfach anpassen kann.

Zusammenstückeln von Zeichenketten und Werten mittels ``+`` und `str()` ist eher BASIC als Python. In Python gibt es dafür Zeichenkettenformatierung mit der `format()`-Methode oder in aktuellen 3er-Versionen f-Zeichenketten.
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
schumatscher
User
Beiträge: 8
Registriert: Donnerstag 27. Dezember 2018, 14:53

Die Ausgangsdatei hat das Format
PLZ, Ort;12345;...;...;
PLZ, Ort;3,4,5,6,;...;...;
PLZ, Ort;12345;...;...;

Die Dateien werden jeden Tag neu geschrieben.
In den Dateien befinden sich häufig Daten aus der Vorgängerdatei (heißt: es ändert sich nicht jeder Eintrag)
Meine Aufgabe ist nun, Duplikate innerhalb einer Datei zu finden und auszugeben.
Da ich die Ergebnisse in einer log-Datei ausgeben möchte, öffne ich die Datei nach jeder Schleife, anschließend leere ich
meine Liste "laufende_nummern" und starte wieder von vorn.
Wenn jemand noch eine Idee hat, wie ich die Suche effektiver gestalten kann, gerne...
Im Vergleich zu meinem ersten Versuch hat sich die Laufzeit mit dem u.s. Code aber schon verringert

Code: Alles auswählen

import collections
pfad = "C:\Pfad\"
def checkDuplikat():       
    laufende_nummern = []
    for datei in os.listdir(pfad):
        with open (datei) as textfile:
            for line in textfile:
                laufende_nummern.append(line.split(";")[1])
            if [i for i, count in collections.Counter(laufende_nummern).items() if count >1]:
                ergebnis = [i for i, count in collections.Counter(laufende_nummern).items() if count >1]
                with open("error_log.txt", "a") as errorlog:
                    error_text = ("{0} Doppelte Nummer: {1}\n").format(datei, ergebnis)
                    errorlog.write(error_text)
            laufende_nummern = []
Sirius3
User
Beiträge: 17741
Registriert: Sonntag 21. Oktober 2012, 17:20

Ein einfaches Umstellen von ein paar Zeilen, macht die Sache schon viel schöner:

Code: Alles auswählen

import collections
PFAD = "C:\Pfad"

def check_duplicates():
    with open("error_log.txt", "a") as errorlog:
        for datei in os.listdir(PFAD):
            laufende_nummern = []
            with open (datei) as textfile:
                for line in textfile:
                    laufende_nummern.append(line.split(";")[1])
            ergebnis = [i for i, count in collections.Counter(laufende_nummern).items() if count >1]
            if ergebnis:
                error_text = ("{0} Doppelte Nummer: {1}\n").format(datei, ergebnis)
                errorlog.write(error_text)
Sirius3
User
Beiträge: 17741
Registriert: Sonntag 21. Oktober 2012, 17:20

Wobei das Erzeugen einer Liste dann gar nicht mehr nötig ist:

Code: Alles auswählen

def check_duplicates():
    with open("error_log.txt", "a") as errorlog:
        for datei in os.listdir(PFAD):
            with open(os.path.join(PFAD, datei)) as lines:
                laufende_nummern = collections.Counter(
                    line.split(";")[1] for line in lines
                )
            ergebnis = [i for i, count in laufende_nummern.items() if count >1]
            if ergebnis:
                error_text = "{0} Doppelte Nummern: {1}\n".format(datei, ", ".join(ergebnis))
                errorlog.write(error_text)
schumatscher
User
Beiträge: 8
Registriert: Donnerstag 27. Dezember 2018, 14:53

@sirius: Vielen Dank für die Tipps. Die Umstellung hat noch einmal einen (wenn auch dezenten) Effekt auf die Performance gehabt. Da ich aber davon ausgehe, dass die Anzahl der Dateien zukünftig deutlich ansteigen wird, ist dieser Effekt wahrscheinlich nicht unerheblich.
Nebenbei habe ich nun den kompletten Code anhand Eurer Tipps überarbeitet - und auch hier: durch das lediglich einmalige Öffnen der error_log.txt sieht der gesamte Code deutlich sauberer aus.
schumatscher
User
Beiträge: 8
Registriert: Donnerstag 27. Dezember 2018, 14:53

Hallo,
ich muss den Thread doch noch einmal eröffnen.
Das mit den doppelten Einträgen in der Liste hat ja super mit collections funktioniert.
Jetzt bräuchte ich allerdings noch etwas:
Wenn ich in einer Zeile meiner Textdatei einen doppelten Eintrag habe, dann muss ich jetzt noch wissen, ob die Werte der doppelten Zeilen an Position 3 (die Positionen sind getrennt durch „;“) addiert größer als 1440 (Minuten) sind.
Da ich jetzt schon einiges mit Schleifen und Abspeichern in Listen u.a. versucht habe (und ich immer enttäuscht wurde), habe ich mich vorerst dazu entschieden die Prüfung durchzuführen, in dem ich die Daten, die ich in eine Sqlite3-Datenbank gespeichert habe, von dort auszulesen und zu prüfen (Die Daten müssen für die weitere Bearbeitung sowieso in die Datenbank - und mit einer sql-Abfrage habe ich das Problem recht schnell gelöst.
Ich habe aber das mulmige Gefühl, dass das ein sehr umständlicher Weg ist, der mich, umso mehr Dateien ich bekomme, enorm viel Zeit bzw. Performance kostet.
Hier mal eine Zeile aus meiner Beispieldatei:
Name, Vorname; 123456789;500;450
Name, Vorname; 123456789;500;1000

...und genau um die Summe der beiden letzten Integers in den Zeilen geht es mir - hier im Beispiel ist die Summe 1450 und damit größer als 1440 --> dies sollte jetzt ein Meldung geben..


Vielen Dank schon mal im Voraus an das Forum...
Sirius3
User
Beiträge: 17741
Registriert: Sonntag 21. Oktober 2012, 17:20

Ich verstehe nicht, was Du nun als Ergebnis brauchst? Duplicate? Die Summe? Eine Meldung für alle Zeilen >1400 oder nur, dann, wenn es Duplicate sind?
schumatscher
User
Beiträge: 8
Registriert: Donnerstag 27. Dezember 2018, 14:53

Ursprüngliche habe ich nur nach Duplikaten gesucht. Im Verlauf ist mir dann aber aufgefallen, dass es durchaus Duplikate geben darf, wenn die Summe der Zeiten unter 1440 bleiben.
In der Ausgabe soll nun die Nummer (es handelt sich um eine MitarbeiterID) und die Gesamtsumme der in den Duplikaten gelisteten Zeiten sein, wenn sie größer als 1440 Minuten ist.
Sirius3
User
Beiträge: 17741
Registriert: Sonntag 21. Oktober 2012, 17:20

Also sollen alle Zeilen ignoriert werden, aber der Zeile, wo die Summe der dritten Spalte größer als 1440 wird. Oder sollen alle Zeilen ignoriert werden, bei denen die Summe insgesamt 1440 größer wird? Oder sollen alle bis auf die Erste Zeile?
schumatscher
User
Beiträge: 8
Registriert: Donnerstag 27. Dezember 2018, 14:53

Habe es so versucht..

Code: Alles auswählen

 self.ergebnis = [i for i, count in collections.Counter(self.listeNummern).items() if count > 1]

...

maxZeit = []
    with open(self.datei) as textfile:
        for item in self.ergebnis:
            for item in self.ergebnis:
                summezeit = 0
                    for line in textfile:
                        if item == (line.split(";")[1]):
                            summezeit += int(line.split(";")[3])
                            maxZeit.append(summezeit)
    print("MaxZeit:", maxZeit)
bekomme aber immer nur die beiden Zeiten der ersten Duplikate in der Liste ausgegeben.
In meinem Beispiel war die Textdatei
enlang,Gee;0012945;1440;800;
enlang,Gee;0012945;140;300;
uth,Lhar;001295;1000;500;
uth,Lhar;001295;1000;200;

Die Ausgabe ist [800, 1100] - erwartet habe ich [1100, 700]
... ich bin verwirrt... :cry:
Benutzeravatar
sparrow
User
Beiträge: 4187
Registriert: Freitag 17. April 2009, 10:28

Hilft es dann überhaupt noch, festzustellen ob ein Eintrag doppelt vorhanden ist?
Ich würde ein dict aufbauen. Schlüssel ist die Mitarbeiternummer, Wert ein Tupel (anzahl_einträge, gesehen_minuten)
Dann hast du die Daten gruppiert und brachst hinterher nur noch das dict durchlaufen und entsprechend die Einträge bewerten.
Sirius3
User
Beiträge: 17741
Registriert: Sonntag 21. Oktober 2012, 17:20

@schumatscher: die Einrückungen sind kaputt, das läuft also gar nicht. Die doppelte for-Schleife über `item` sieht auch falsch aus. Über ein Fileobjekt kann man nur einmal iterieren, so dass die innere Schleife auch nur beim ersten Lauf durchlaufen wird.
Du mußt auch vorher bei der Verarbeitung ansetzen. Lade die gesamte Datei in ein Wörterbuch, aber statt der Anzahl mit einer Liste von Zeiten. Dann kannst Du nachträglich auch die Summen ausrechnen und mit den Werten weiterarbeiten.
Benutzeravatar
__blackjack__
User
Beiträge: 13079
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Die IDs mit mehr als 1440 Minuten könnte man so ermitteln:

Code: Alles auswählen

#!/usr/bin/env python3
from collections import defaultdict


def main():
    id2minutes = defaultdict(int)
    with open('test.txt') as lines:
        for line in lines:
            row = line.split(';')
            id2minutes[row[1]] += int(row[3])
    
    ids = [id_ for id_, minutes in id2minutes.items() if minutes > 1440]
    print(ids)


if __name__ == '__main__':
    main()
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
schumatscher
User
Beiträge: 8
Registriert: Donnerstag 27. Dezember 2018, 14:53

@sirius: Du hast natürlich vollkommen recht. Die Einrückungen sind total panne und die beiden Schleifen ebenfalls (ich hatte den Code kopiert, ursprünglich waren ein paar Zeilen auskommentiert... :roll: Sorry für meine Schludrigkeit

@__blackjack__ : Deine Methode hat funktioniert (muss jetzt nur noch mal etwas tiefer in die collections gucken um es ganz zu verstehen)
Antworten