Eindeutiger Vergleich für große Dateien gesucht

[negaH]

Nochmal was zur Performance, da es hier um grundsätzliche Verständnissprobleme die unter Programmieren sehr häufig vorkommen geht.

Mal als Beispiel alles ein bischen idealisert dargestellt.

Wir gehen mal davon aus das auf einer HD eine Million Dateien gespeichert wurden. Nun sollen alle Duplikate gefunden werden. Alle Dateien zusammen sind 1 Terrabyte groß. Von diesen Dateien sind 10% mit gleicher Dateigröße zueinander und von diesen sind nur 0.1% absolut identisch zueinander.

So per MMF's=Binärem Dateivergleich benötige ich pro Mb 10 Sekunden.
Einen Hash über diese Datei zu erzeugen benötige ich 5 Sekunden, also die Hälfte der Zeit da ich ja nur eine Datei statt zwei einlesen muß.


Die Aufgabe ist es nun 10% von 1 Million = 100000 Dateien untereinander zu vergleichen. Per Hash ziehe ich 100000 mal eine Prüfsumme und vergleiche diese untereinander. Das dauert 100000 *5 = 500.000 Sekunden. von diesen1 100.000 Dateien wissen wir das aber nur 0.1% wirklich identisch zueinander sind. Nach 500.000 Sekunden müssen wir also noch 100 Dateien tatsächlich binär vergleichen, was 100 * 10 Sekunden= 1.000 Sekunden dauert. Wird kommane auf 501.000 Sekunden um per Hash-Methode alle 100 identischen Dateien zu finden.

Nun per MMF's=binärem Drekt vergleich. Wir haben wieder 100.000 Dateiem mit gleicher Größeum vergleichen jede dieser 100.000 mit jeder anderen der 100.000 Dateien, ergibt 10^9 Vergleich a 10 Sekunden, macht 10^10 Sekunden die man benötigen würde um die 100 identischen Dateien zu finden.

D.h. selbst wenn 1 Vergleich per Hash + Binärem Vergleich also 20 Sekunden dauert, im gegensatz zu 1* 10 Sekunde pro binärem Vergleich, so ändert sich dieses Ratio ganz ganz gewaltig wenn man vom NORMAL-Fall ausgeht, nämlich das von 1 Million Dateien tatsächlich nur 100 identisch sind.

Man muß also als Programmierer sehr genau die Wahrchenlichkeiten des Auftratens bestimmter Ereignisse berücksichtigen und dann einen Optimierungsweg einschalgen der diese Wahrscheinlichkeiten auch aktiv berücksichtigt.

Exakt darin liegt das Geheimnis viel Algorithmen, zb. JPEG,MP3,Suchalgorithmen etc. pp. Ansich sind sie alle im Grunde aufwendig oder verlustbehaftet aber das stört nicht weil sie im Normalfalle eben bei den wahscheinlichst auftauchenden Daten enorm schnell und effektiv sind.

Gruß Hagen