Kleiner Duplikate-finder

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

Kleiner Duplikate-finder

Beitragvon nuss » Freitag 6. März 2009, 03:22

Hi, ich möchte hier ganz gerne mal mein
neustes Project vorstellen, einen Duplikat-finder,
der auch soweit schon funktioniert.

Der Kern des Programms und IMHO am interressantesten ist cache.py.
In dpfind.py stecken die Funktionen die nötig sind, um Duplikate zu finden.
In cachesettings.py stecken wie der name schon sagt die settings ^^
und in main.py nur die ui.

abhängigkeiten sind lxml, python 2.6 ( nur mit 2.6 getestet )
und optional psyco

cache.py
cachesettings.py
dpfind.py
main.py

Es würde mich freuen mal ein paar meinungen zu hören, was noch
verbesserungswürdig ist, und was bleiben kann wie's ist ;)
BlackJack

Beitragvon BlackJack » Freitag 6. März 2009, 11:22

@nuss: Werden `Content`, `File`, und `Folder` aus `cache` überhaupt irgend wo wirklich sinnvoll eingesetzt? Das Programm scheint überall auf XML-Datenstrukturen zu operieren. Was ich nicht machen würde, da das Format zur Serialisierung der Daten von der Programmlogik getrennt sein sollte. Für das finden von Duplikaten sollte es unerheblich sein, ob der Cache in XML, JSON, oder einer SQL-Datenbank gespeichert wird.

Weisst Du was für eine Laufzeit die `remove()`-Methode auf der `ElementTree`-Baumstruktur hat? Es kann sein, dass `remove_old_folders()` sehr ineffizient ist. Ausserdem würde ich dringend prüfen ob man dort gefahrlos Elemente löschen kann während man über die Struktur gleichzeitig mit einer ``for``-Schleife iteriert.

Bei Namen wie `fentry` sollte man sich überlegen die Abkürzungen sein zu lassen und tatsächlich `folder_entry` zu schreiben. Oder vielleicht `file_entry`!? Dann kann man sich das Raten beim lesen sparen. :-)

Es gibt ein paar mal das Muster, dass in einer Schleife ein bestimmter Eintrag linear gesucht wird. Das dürfte das Programm unverhältnismässig verlangsamen. Eine Abbildung von Pfad auf Eintrag ist *wesentlich* effizienter. Das ist wohl an dieser Stelle auch ein Nebeneffekt davon, dass XML als internes Datenformat verwendet wird, statt passende Strukturen zu verwenden.

Das ganze funktioniert so mit XML übrigens nicht mit den Dateinamen. In Dateinamen können im schlimmsten Fall beliebige Bytewerte ausser '/' und dem Nullbyte vorkommen, und selbst Dateinamen im gleichen Verzeichnis können unterschiedlich kodiert sein. Man kann an der Stelle also nicht mit Unicode arbeiten, denn zumindest unter Unix sind Dateinamen keine Zeichenketten, sondern einfach nur Byteketten. Da können auch Werte unter Bytewert 32 vorkommen, mit denen XML ebenfalls Probleme hat.

Wenn ich mir `dpfind.md5sum()` anschaue, weiss ich, dass man das Programm besser nicht auf eine Verzeichnishierarchie anwenden sollte, in der CD-Images oder gar DVD-Images liegen. ;-)

Das bei Einträgen die nicht den Typ Datei haben, implizit `None` zurück gegeben wird, ist unschön. Entweder explizit `None` liefern, oder besser eine Ausnahme auslösen.

Mit regulären Ausdrücken wird in `get_path()` und `get_spezific()` mit Kanonen auf Spatzen geschossen. `get_path()` holt auch keinen Pfad, sondern Einträge *zu* einem Pfad. Der Name ist also irreführend. Die Funktion liesse sich auch schön kurz mit einer "list comprehension" ausdrücken:

Code: Alles auswählen

def get_path(entry, path):
    path = os.path.realpath(path)
    return [f for f in entry if f.get('path').startswith(path)]


`get_spezific()` ist wieder so ein Fall, wo man eigentlich eine Abbildung von Pfadname auf Eintrag haben möchte, statt einer langsamen linearen Suche.

Was macht `get_file()`?

Warum werden Funktionsargumente teilweise komplett in Grossbuchstaben geschrieben? Das ist normalerweise eine Konvention, um Konstanten zu kennzeichnen.

Was bedeutet der Präfix `py` bei `pycache`?

In `find_equals()` macht sich wieder bemerkbar, dass direkt auf dem Serialisierungsformat operiert wird, weil da zum Beispiel Dateigrössen als Zeichenketten behandelt werden.

Das Befüllen von `equalFilesizes` ist zu kompliziert und zu tief geschachtelt. In beiden Zweigen wird zum Beispiel auf die Dateigrösse 0 getestet und jeweils das gleiche gemacht. Den Test sollte man nur einmal machen und weiter nach oben ziehen. Und wenn man zwei verschachtelte ``if``-Anweisungen hat, bei der die innere nur noch eine weitere Bedingung überprüft, kann man die auch zu einer zusammenfassen und die Tests mit ``and`` verknüpfen.

Explizites vergleichen mit `True` oder `False` in einer Bedingung ist redundant und sollte vermieden werden. Um zu testen ob ein Schlüssel in einem `dict` vorhanden ist, sollte man nicht die `keys()`-Methode aufrufen, die extra für den Test eine Liste mit allen Schlüsseln erstellt und in der dann *linear* sucht.

Das befüllen liesse sich letztendlich in dieser Richtung formulieren:

Code: Alles auswählen

    size2entries = dict()
    for folder in folders:
        for file_entry in folder:
            file_size = file_entry.size
            if not list_zero_sizes and file_size == 0:
                continue
            size2entries.get(file_size, list()).append(file_entry)


Ab Python 2.5 würde ich ein `collections.defaultdict` für `size2entries` verwenden.

Aus dieser Struktur würde ich die Einträge mit weniger als zwei Dateien nicht explizit entfernen, sondern einfach nur die mit mehr als einer Datei weiter verarbeiten. Ähnlich wie der letzte Quelltextabschnitt, lässt sich das auch kompakter schreiben:

Code: Alles auswählen

    hash2entries = dict()
    for size, file_entries in size2entries:
        if len(file_entries) > 1:
            for file_entry in file_entries:
                hash2entries.get(md5sum(file_entry), list()).append(file_entry)


Den Hashwert könnte man mit in den Cache aufnehmen und nur aktualisieren, wenn sich das Datum der letzten Veränderung verändert hat. Wenn man das nicht macht, ist der Hashwert eigentlich gar nicht nötig, weil Vergleichen der Dateiinhalte genau so lange dauert. In beiden Fällen müssen die Dateien komplett eingelesen werden. Bei Vergleichen der Dateiinhalte ist man eventuell sogar schneller, weil man beim ersten Unterschied abbrechen kann.

Und vergleichen muss man sowieso, wenn man sichergehen will, das zwei unterschiedliche Dateien nicht nur zufällig die gleiche Grösse und den gleichen Hashwert besitzen. Ich weiss das ist extrem unwahrscheinlich, aber wenn's zum Beispiel um das automatische Löschen von Duplikaten geht, hätte ich die zusätzliche Sicherheit schon ganz gerne, denn Murphy schlägt ja genau in solchen Fällen gerne zu.

`print_readable()` liest sich sehr komisch. Es wird eine "list comprehension" verwendet, wo eigentlich eine ``for``-Schleife hin gehört, weil die nur wegen der Seiteneffekte da ist, aber die Liste selbst nicht gebraucht wird.

Dann wird von einer Abbildung von Hashwert auf Objekte in eine andere Abbilung "umgepackt" wobei die Werte dort Listen mit Dictionaries mit jeweils nur einem Eintrag sind. Was soll das!? Die Längeninformation ist ausserdem redundant, weil die in jeder Liste immer gleich sein sollte, sonst könnten die Datein ja nicht den selben Inhalt haben.

Für Optionen und Hilfetexte gibt's das `optparse`-Modul.

`validate_options()` braucht dringend Dokumentation. Ich habe jedenfalls auch beim zweiten mal Lesen nicht verstanden was das macht.

In der ``while``-Schleife zur Verarbeitung der Optionen ist zu viel Redundanz und der Test auf die '--help'-Option funktioniert so nicht. Die Bedingung ist immer wahr, weil nichtleere Zeichenketten "wahr" sind.

Ausserdem scheinst Du das überhaupt nicht getestet zu haben, denn es gibt in dem Namensraum kein `load()`!
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

Beitragvon nuss » Freitag 6. März 2009, 13:52

doch hab ich mehrfach getestet, und funktioniert tadellos,
kann aber sein, dass ich noch 1 oder 2 sachen verändert habe, befor ich's reingestellt habe.

Dann mach ich mich mal an die Arbeit, um das zu verbessern.

edit: Warum würdest du md5sum nicht über deine DVD oder ISO - Sammlung laufen lassen ??? wegen dem anderen Filesystem, in Isos ??
edit: loool habs jetzt erst geschnallt ^^

aber noch was anderes, wie soll ich die pfade denn dann codieren,
wenn nicht in unicode? ascii kommt logischerweise nicht in Frage..
hex ? nicht xml verwenden sondern lieber pickeln ?
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

Auf ein neues

Beitragvon nuss » Freitag 6. März 2009, 17:04

Hier ist zwar noch kein algo zum finden von duplikaten dabei,
aber der kern ist überarbeitet, kleiner und schneller ^^

http://paste.pocoo.org/show/106721/
lunar

Beitragvon lunar » Freitag 6. März 2009, 20:11

Pfade setzt man mit os.path.join zusammen, für Wahrheitswerte nutzt man boolsche Literale und Fehler innerhalb von Funktionen werden durch Ausnahmen und nicht durch boolsche Rückgabewerte an den Aufrufer weitergegeben. Wir sind hier schließlich nicht in C ...

Wenn man etwas wie eine Funktion behandelt, dann sollte man es auch als Funktion implementieren. Das betrifft die Klasse "Dir". Eigentlich sind alle Klassen ziemlich sinnlos, da man sie auch gut durch Funktionen und Standard-Datenstrukturen ersetzen kann.
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Samstag 7. März 2009, 10:58

Zum Einsatz der Hash-Funktion möchte ich anmerken, dass es keine gute Idee ist, die Daten komplett in den Speicher zu ziehen. Besser ist es, die Datei in Blöcken von z.B. 8k zu laden, und über `update()` dem Message Digest hinzuzufügen.

Wenn du die Datei schon am Wickel hast und gelesen hast, kennst du ja auch ihre Länge. Diese würde ich sofort vorne an den Digest anfügen. Dann musst du später nur diese Werte vergleichen.

Ich würde mich übrigens beim Finden von Duppletten nicht auf MD5 verlassen sondern abschließend noch die Dateien mit dem selben Digest Byte-für-Byte vergleichen - wenigstens optional.

Ach ja, und bitte stottere nicht bei Boolschen Ausdrücken: Diese müssen nicht nochmals explizit mit `True` oder `False` verglichen werden.

Stefan
nuss
User
Beiträge: 53
Registriert: Donnerstag 28. August 2008, 11:36

Beitragvon nuss » Donnerstag 19. März 2009, 21:26

so ist jetzt n bisschen her, seit dem ich das letzte mal was drann gemacht habe, aber hab dass ganze nochmal überarbeitet :wink:

Es sind jetzt keine Objecte mehr im Code vorhanden, das ganze funktioniert komplett mit dictionarys und beim erstellen von md5summen werden keine ganzen Dateien mehr eingelesen, sondern nur noch Teile.
Ausserdem geht das cachen von Verzeichnissen deutlich schneller und verursacht weniger Cpulast.

Nur das erstellen von md5summen, dauert "ewig"... , verursacht allerdings meistens auch nur sehr wenig Cpulast.

Den Code habe ich jetzt schon vor bestimmt 1 oder 2 wochen geschrieben,
weiß daher immoment nicht gaanz genau, wies funktioniert ( wär mal n grund besser zu dokumentieren, was ich schreibe ;) )

Eingeschlafen ist das Project, weil ich immer keinen bock drauf habe, mich mit Gui programmierung zu beschäftigen, und das finden von duplicaten dauert auch deutlich zu lange.

cache.py
dpfind.py

eine vernünftige main.py habe ich immoment nicht, die folgt aber noch :oops:

edit: und besonders gut getestet ists auch nicht
sma
User
Beiträge: 3018
Registriert: Montag 19. November 2007, 19:57
Wohnort: Kiel

Beitragvon sma » Samstag 21. März 2009, 09:59

nuss hat geschrieben:Nur das erstellen von md5summen, dauert "ewig"... , verursacht allerdings meistens auch nur sehr wenig Cpulast.

Dann läuft da etwas falsch. Den Digest zu brechnen sollte 100% Last erzeugen. Wenn die CPU da nicht genug zu tun hat, so fütterst du nicht schnell genug Daten ein, würde ich vermuten. `create_md5` sieht auf den ersten Blick allerdings ok aus...

Stefan

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder