geschickt Duplikat-Dateien eliminieren

[shakebox]

Tach! Nach laengerer Funkstille mal wieder ne Frage von mir:

Kurzfassung:
ich hab nen Ordner mit etlichen Dateien (einfache Textdateien) drin. Dieser Ordner fuellt und leert sich dynamisch. Dabei kann es vorkommen dass da Dateien gleichen Inhalts entstehen aber mit unterschiedlichem Dateinamen. Da ich anhand des Inhalts etwas abarbeite wuerde ich gerne vor dem Abarbeiten dafuer sorgen dass jeder Inhalt nur 1x vorkommt.

Wie kann ich also elegant alle diese Dateien unterschiedlichen Namens miteinander auf gleichen Inhalt ueberpruefen und Duplikate entfernen? Gibt es da clevere Methoden? Loest man sowas indem man in die Dateien hineinschaut oder mit nem MD5-Hash oder sowas? Wie geht man durch alle Dateien durch: laedt man die erste und vergleicht sie mit allen anderen, dann die zweite mit allen anderen, usw. oder gibt es dafuer elegantere Varianten?


Langversion falls jemand verstehen mag was ich da mache:
ich habe erstens eine Renderfarm die bestimmte Dinge rendert. Nach dem erfolgreichen Rendering sollen zwei andere Rechner mit dem gerenderten Zeugs was machen. Da aber 1. nicht immer alle Rechner parallel online sind und 2. meine Programmierkenntnisse nachwievor nur begrenzt sind hab ich das einfach ueber eine Warteschlange auf Ordner/Dateibasis geloest.

Die Renderfarm erzeugt einfach eine neue Datei namens XXXXX.queue in nem Ordner und schreibt da den Pfad zu den gerenderten Bildern rein. XXXXX ist dabei einfach ne durchlaufende Nummer. Ein Script auf dem jeweiligen weiterverarbeitenden Rechner schaut in den Ordner ob da Files drin sind und arbeitet die dann ab.

Soweit klappt das gut. Wenn aber der weiterverarbeitende Rechner mal einige Zeit nicht laeuft oder sowas dann sammeln sich viele Files an. Vor allem kann es vorkommen dass evtl. mehrfach die gleichen Dateien gerendert wurden. Geht jetzt das Weiterverarbeitungs-Script wieder online dann passiert es momentan logischerweise dass ganz stupide abgearbeitet wird und die gleichen Dateien mehrfach weiterverarbeitet werden. Da das aber zeitintensiv ist wuerde ich gerne vorher aussortieren damit jeder Zielpfad eben nur genau einmal vorkommt.

Hoffe das war halbwegs verstaendlich und freu mich auf Eure Ideen damit ich in Sachen Programmierung und dessen Verstaendnis mal wieder ein Stueck vorwaerts komme.

Danke und Gruss, Shakebox

[EyDu]

Ich würde das ganz primitiv machen:

Durch alle Dateien iterieren und den Hashwert des Inhalts (zu nächst der ersten k Zeichen) erstellen und in in Dictionary einordnen: Schlüssel ist ein Tupel aus Hashwert und Dateilänge, als Werte hast du eine Liste an Einträgen, welche zu dem Schlüssel passen.

Wenn du alle Dateien eingeordnet hast, betrachtest du alle Werte im Dictionary: Steht nur ein Wert in einer List, so handelt es sich in jedem Fall um ein Unikat. Stehen mehrere drin, musst du alle Einträge der Liste paarweise vergleichen.

[lunar]

Wenn du allerdings Einfluss auf Rendering-Farm und Verarbeitungsskript hast, wäre es vielleicht besser, die Kommunikation gleich so zu gestalten, dass Duplikate von vorne herein vermieden werden. Eine Datenbank würde sich imho anbieten. Die Rendering-Farm würde die Dateipfad in eine Tabelle eintragen, aus der das Verarbeitungsskript sie ausliest. Nach der Verarbeitung würde das Skript die verarbeiteten Dateinamen dann in eine eigene Tabelle eintragen. Liegen beide Tabellen in der selben Datenbank, reicht eine einzige Datenbankabfrage, um die anstehenden Dateien abzufragen, die noch nicht verarbeitet wurden.

[shakebox]

ha, den Hashwert als Schluessel zu verwenden und nicht den Filenamen oder sowas ist natuerlich genau die prima Idee auf die ich selbst mal wieder ueberhaupt nicht gekommen waere. Das in Kombination mit nem kleinen Modul das ich gefunden habe (http://thejaswihr.blogspot.com/2008/06/ ... -file.html) sollte mir glaub schon vollkommen weiterhelfen.

Danke fuer diesen Stupser in die richtige Richtung. Zeigt mal wieder wie wenig programmierlogisch ich noch denke und zweitens dass es sich eigentlich immer lohnt, Fragen zu stellen

[shakebox]

ja lunar, das ist sicher die eigentlich sinnvollere Loesung. Dafuer reicht momentan aber meine Faehigkeit noch nicht aus. Der Vorteil an der momentanen Loesung ist halt dass es voellig asynchron funktioniert. Wenn ich es ueber eine Datenbank loese muss diese dann natuerlich auch immer laufen und verfuegbar sein. Klar ist das eigentlich ohne Probleme machbar, erfordert aber halt einfach ein wenig "mehr" an Aufwand. Wird sicher irgendwann folgen, momentan ist es mir ne Hausnummer zu hoch.

Oder geht sowas auch ueber eine SQLite-Datenbank? Da braeuchte ich dann nicht noch nen Server der zusaetzlich dauerhaft laeuft. Aber klappt das mit parallelen Zugriffen auf eine SQLite-Datenbank von mehreren Rechnern aus? Oder kollidieren die miteinander?

[Defnull]

Ich hatte mal ein script geschrieben, das duplikate findet und die jeweils ältere Version löscht. Nicht schön, aber es funktioniert:

Code: Alles auswählen

import os, os.path, sys
import hashlib

def md5(fn):
  with open(fn) as f:
    hash = hashlib.md5(f.read()).digest()
  return hash

def dirwalk(dir, r=True):
  for f in os.listdir(dir):
    fullpath = os.path.join(dir,f)
    if r and os.path.isdir(fullpath) and not os.path.islink(fullpath):
      for x in dirwalk(fullpath, r):
        yield x
    elif not os.path.isdir(fullpath):
      yield fullpath

db = {}
for fn in dirwalk(sys.argv[1], False):
  h = md5(fn)
  if h in db:
    if os.path.getmtime(fn) > os.path.getmtime(db[h]):
      d = db[h]
      db[h] = fn
    else:
      d = fn
    #os.unlink(d)
    print "rm", repr(d)
  else:
    db[h] = fn

[shakebox]

und gleich noch ne Folgefrage zu der Loesung mit dem Dict:

bin leider im Umgang mit Dicts nicht so fit. Deshalb steh ich da grad auf dem Schlauch:

ich lege ja so z.B. ein Dict an mit dem Hashwert als Schluessel:

Code: Alles auswählen

hashdict[md5sum.md5('/pfad/zur/datei')] = '/pfad/zur/datei'

dann steht da aber ja ein String drin und keine Liste. Bei einer Liste kann ich aber ja per .append neue Elemente dranhaengen. Dazu muss aber ja schon ne Liste (zumindest eine leere) bestehen. Wie komm ich jetzt an die Liste, die ja dynamisch entstehen muss?

Muss ich da den Hashwert vorher erzeugen und dann ne Liste erzeugen mit diesem Namen falls es die noch nicht gibt und sonst eben an die Liste was appenden oder geht das eleganter? .append geht ja nur wenn ne Liste schon besteht, oder? Die wird ja nicht erzeugt wenn es sie noch nicht gibt.

Ihr merkt, meine Pythonkenntnisse sind leider nachwievor rudimentaer. Trotzdem ist es fuer mich halt der sinnvollste Weg, kleinere Probleme und Aufgaben die sich mir taeglich so stellen damit zu loesen und dabei halt Step by Step dazuzulernen. Danke fuer Eure Geduld!

[HWK]

Stichwort defaultdict oder für ältere Python-Versionen setdefault.
MfG
HWK

[shakebox]

Perfekt, jetzt hab ich schon mal ein Dict mit Hashwert als Schluessel und Listen der jeweiligen Files. Nun muss ich die nur noch durchgehen und loeschen. Das krieg ich hin.

Wieder sehr viel gelernt heute, inklusive ner sinnvollen Anwendung fuer Dicts, die ich bisher noch nie verwendet hatte. Danke allerseits, Ihr seid klasse!

[shakebox]

so, fertig funktionierend sieht das jetzt so aus:

Code: Alles auswählen

import os
from glob import glob
import md5sum
import collections

queuelist = glob(os.path.join('/mnt/libs/processing_queue_folder/2kplayer-queue', '*.queue'))
queuelist.sort()

hashdict = collections.defaultdict(list)

for datei in queuelist:
    hashdict[md5sum.md5(datei)].append(datei)

for hashwert in hashdict.keys():
    if len(hashdict[hashwert]) > 1:
        for datei in hashdict[hashwert][1:]:
            os.remove(datei)

vermutlich kann man das noch besser loesen, aber noch vor 3 Stunden haette ich nie gedacht dass sich sowas in so wenigen Zeilen loesen laesst. Bin immer wieder so positiv ueberrascht von Python. Jetzt wird das Ganze noch als Funktion in ein Modul gepackt damit ich es an mehreren Stellen verwenden kann und gut ist.

[lunar]

Darf man fragen, warum du die Liste vorher sortierst? Das ist eigentlich nicht nötig. Außerdem kann man die letzte Schleife mit ".itervalues()" (oder ".values()" bei Python 3) ein bisschen schöner gestalten. Die Überprüfung der Länge ist auch nicht nötig, weil ein Slice "von x bis ende" zu einer leeren Liste führt, wenn weniger Elemente in der alten Liste enthalten sind.

Code: Alles auswählen

for duplicates in hashdict.itervalues():
    for filename in duplicates[1:]:
        os.remove(filename)

[EyDu]

Wenn du das (sehr sehr sehr kleine) Risiko eingehst, dass Dateien mit dem selben Hashwert immer verschieden sind, dann kannst du dein Problem sogar noch einfacher über eine Menge lösen:

Code: Alles auswählen

import os
from glob import glob
import md5sum

queuelist = glob(os.path.join('/mnt/libs/processing_queue_folder/2kplayer-queue', '*.queue'))
queuelist.sort()

hashes = set()

for datei in queuelist:
    hash_value = md5sum.md5(datei)

    if hash_value in hashes:
        os.remove(datei)
    else:
        hashes.add(hash_value)

[cofi]

Das Dictionary ist eigentlich ueberfluessig. Ein ``set`` der Hashes und ein Membershiptesting beim iterieren ueber deine Globs - entfernen, falls drin, hinzufuegen, wenn nich - reicht imho.

Edit: Timing ist alles ...

[HWK]

Timing ist alles ...

Richtig. Ich hätte statt eines Sets aber einfach eine Liste genommen.
MfG
HWK

[lunar]

Timing ist alles ...

Richtig. Ich hätte statt eines Sets aber einfach eine Liste genommen.

Listen haben beim Suchen von Einträgen lineare Laufzeit, Mengen dagegen konstante. Wenn man nur wissen will, ob ein Element in einer Menge von Elementen enthalten ist, ist "set()" die sinnvollere Datenstruktur. Listen nimmt man, wenn die Ordnung wichtig ist, oder Index-Zugriffe benötigt werden.

[shakebox]

Ha, wunderbar. Nochmal klasse Hinweise zum guten Programmieren. Klingt alles logisch was Ihr da sagt. Werde ich nochmal genauer anschauen um es zu verstehen und dann meine Loesung nochmal umbauen. Danke!

[HWK]

Listen haben beim Suchen von Einträgen lineare Laufzeit, Mengen dagegen konstante. Wenn man nur wissen will, ob ein Element in einer Menge von Elementen enthalten ist, ist "set()" die sinnvollere Datenstruktur. Listen nimmt man, wenn die Ordnung wichtig ist, oder Index-Zugriffe benötigt werden.

Gut zu wissen.