Eindeutiger Vergleich für große Dateien gesucht

[FriFra]

:shock: Das war ja mehr als ich erwartet hab... Danke negah :)

Eins ist mir allerdings aufgefallen... die CompareFile Funktion die du vor Deiner unit gepostet hast, ist bei mir deutlich schneller als die aus der FileCompare.pas. Ich hab das ganze über mehrere Dateien laufen lassen und komme mit der Funktion aus dem Thread auf 10s und mit der aus der unit auf 70s :gruebel: ... ich hab mir den Code aus der unit noch nicht näher angesehen, ist mir halt nur aufgefallen ;)

[himitsu]

Zitat:

Zitat von dahead

wie darf ich das verstehen?

na weil er viele seiner Codes nur für sich selbst zu machen schweint ...
jedenfalls veröffentlich er einiges nicht. (um sein DEC macht er ja auch so ein großes Geheimnis)
Aber bei Einigem kann man ihn ja auch verstehen.


So, aber nun muß ich wirklich los :cry:

[dahead]

@himitsu:

Zitat:

na weil er viele seiner Codes nur für sich selbst zu machen schweint ...

hehe

ich meinte damit egtl. eher warum er meint, dass er nichts besseres zu tun hat. das kann ich mir egtl. nicht vorstellen.

und klar, wenn jemand viel zeit in einen code investiert, gibt er/sie ihn klar nicht einfach so raus. ist verständlich.

@FriFra:

wenn du mit "CompareFile" die MMF Methode meinst, negaH hat in FileCompare.pas den binären vergleich verwendet, also keine memory mapped files. (CompareFile1 war die binäre variante).

[FriFra]

ja, das wars ;) ... nur das HashFile bremst das ganze bei mir extrem aus. Wenn ich ausschliesslich mit der MMF Methode vergleiche ist das ganze wesentlich schneller als über Hash. Ich weiss im Moment nicht so recht, wo der Vorteil/Sinn von diesem Hash-Vergleich liegen soll :gruebel:

[dahead]

naja, folgendes beispiel:

du willst 1000 dateien mit der mmf methode auf gleichheit prüfen. das dauert relativ lange. wenn du aber vorher bereits via md4/md5 oder sonstwas eine checksumme erstellst (was schnell geht), brauchst du nachher nur noch die dateien mit gleichen checksummen via mmf inhaltlich prüfen.

hoffe du konntest mir folgen.

edit: vielleicht sagt dir folgender code mehr als obiges:

Delphi-Quellcode:

      if (ItemI.fFileSize > 0) and (ItemF.fFileSize > 0) then
       if ItemI.fFileSize = ItemF.fFileSize then
        if ItemI.Hash = ItemF.Hash then
         a.) if CompareNormalFilesFileStreamStatic(ItemI.fFullFilename, ItemF.fFullFilename) = True then
         b.) if CompareMemoryMappedFiles(ItemI.fFullFilename, ItemF.fFullFilename) = True then
          doppelt

[negaH]

Zitat:

nein, ich meine die Werte für die Berechnung ... aber ich kann mich auch im Moment irren und es war bei der CRC32-Berechnung ... wenn ich daheim bin, werde ich da sicherheitshalber nochaml nachgucken.

Jo in der CRC32 Routine sind einige Bytes mehr in der Lookup Tabelle als nötig wären, das bleibt aber mein Geheimnis ;)

Zitat:

a, das wars ... nur das HashFile bremst das ganze bei mir extrem aus. Wenn ich ausschliesslich mit der MMF Methode vergleiche ist das ganze wesentlich schneller als über Hash. Ich weiss im Moment nicht so recht, wo der Vorteil/Sinn von diesem Hash-Vergleich liegen soll

Vorsicht ! Ich dachte auch erst das MMF's saumäßig überlegen sind, denkste. Das du so große Unterschiede bemerkst, zumindestens wars bei mir so, liegt daran das das OS bei MMF's diese sehr lange im Speicher belässt, selbst wenn man alle Handles geschlossen hat. Der erste Scan einer ungecachten Datei über MMF's dauerte dann bis zu 55 Sekunden, der zweite Scann (nach einige anderen Dateien) der selben Datei dauerte dann aber nurnoch 7 Sekunden.
Ließ dir mal obigen Link zu Borland Page genauer durch, dort wird das "Problem" beschrieben.

Desweiteren muß man stark differnezieren. Meine jetzigen Routinen vergleichen zwei IDENTISCHE Dateien langsammer als wenn man sie sofort per Binärem Scan vergleichen würde. Das ist absolut korrekt so, denn man zieht ja im schlechtesten Falle vorher noch zweimal einen MD Hash. Wenn diese gleich sind muß nochmals ein binärer Vergleich nachgeschoben werden. Wie aber im Source beschieben sind zwei absolut gleiche Dateien in einem durschnittlichen Dateiaufkommen sehr sehrunwahscheinlich. Wenn man aber schon vorher weis das die zu vergleichenden Dateien mit hoher Wahrscheinlichkeit identisch sind dann sollte man sofort mit CompareFilePhysical() arbeiten. Aber im Normalfalle sind sie sehr sehr unwahscheinlich identisch.

Zitat:

na weil er viele seiner Codes nur für sich selbst zu machen schweint ...

ICH bin für MICH Programmierer und eigentlich schon bekannt dafür viele meine Sourcen besonders hier in der DP mit anderen zu teilen. Und mal davon abgesehen meine ich das meine Sourcendie ich mit anderen teile keine "Abfallprodukte" darstellen, also eine gewisse Qualität besitzen.
Nee, den Schuh muß ich mir nicht anziehen.

Zitat:

ich meinte damit egtl. eher warum er meint, dass er nichts besseres zu tun hat. das kann ich mir egtl. nicht vorstellen.

Ja ich hätte schreiben sollen "Sarkasums on" .... "Sakrasmus off" ;)
Ich bin freiberuflicher Programmierer und muß Geld verdienen, mehr als jeder Angestellte. Meine Aussage bezog sich also darauf das ich diese Unit auch für ein kommerzielles Projekt benötigt habe und somit durch glücklichen Zufall am selben Thema arbeiten konnte ;) Normaleweise hätte ich also dazu keine Zeit gehabt.

[dahead]

@negaH:

ich meinte das nicht negativ, im gegenteil. wie gesagt, mit deinem wissen, was alleine das mmf thema anbelangt, konnte ich mir eben nicht vorstellen, dass du "nichts besseres" zu tun hast. ich bin sehr froh darüber, dass du dir dabei so viel mühe gemacht hast.

ich glaube niemand wollte dir unterstellen, dass deine offenen sourcen abfallprodukte sind, ganz im gegenteil. ich schätze wenn du dich nicht bei dem thema beteiligt hättest, hätte ich bis heute nicht gewusst was mmf überhaupt ist.

in diesem sinne, nochmals danke für die hilfe.

edit:

Zitat:

Jo in der CRC32 Routine sind einige Bytes mehr in der Lookup Tabelle als nötig wären, das bleibt aber mein Geheimnis Wink

evtl. ein copyright hinweis? oder hätte ich mir den kommentar verkneifen sollen?

[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

[negaH]

Zitat:

evtl. ein copyright hinweis? oder hätte ich mir den kommentar verkneifen sollen?

Nöö kann jeder wissen, SOLLTE jeder gute Programmierer auch aus dem Source erkennen müssen ! Das denoch in sovielen kommerziellen Produkten meine Copyright's auftauchten ist schon ein Wunder, ein Wunder das es soviele "schlechte" Programmierer gibt die einfach 1 zu 1 andere Source, hm raub-kaufen. Immerhin DEC ist zwar Freeware, d.h. aber nicht das man ohne meine Zustimmung DEC einfach mal so kommerziell benutzen darf.

Aber im Falle der CRC32 ist mein Copyright wirklich ziemlich stupide und eigentlich offensichtlich versteckt worden, wirklich ein Wunder das du bisher der einzigste Programmierer bist der mich darauf anspricht.

Die richtigen Signaturen sind aber bei weitem besser getarnt ;) Es gibt also noch mehr im DEC zu entdecken !

Gruß Hagen

PS: das fällt mir doch ne lustige Episode ein. Eines Tages bekomme ich ne Mail ob man mein DEC kaufen könnte. Eine Firma hat entdeckt das in ihren Binaries mein Copyright drinnen war (lesbar selbstverständlich). Sie hatte sich eine kleine Software gebaut die mein Copyright aus der EXE nach dem kompilieren raus-patchte. Nun, sie hatten aber auch meine kompletten Sourcen vor sich liegen, nur fanden sie mein Copyright nicht im Source !!
Tja, irgendwann waren sie es wohl leide jedesmal ihre Programme patchen zu müssen und mailten mich eben an.

[dahead]

hehe. ja, so gehts, wenn man sich nichtmal genau ansieht, was man verwendet/kopiert.

daher habe ich auch oben erwähnt, dass ich ungern den kompletten source von jemand anderem einfach übernehme.