Einzelnen Beitrag anzeigen

Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
43.152 Beiträge
 
Delphi 12 Athens
 
#111

Re: Eindeutiger Vergleich für große Dateien gesucht

  Alt 6. Aug 2005, 19:37
Hab zwar den Code zum Dateivergleich noch nicht gefunden, aber ein Stringvergleich tut es doch auch.
Der Dateivergleich entsprach aber in etwa dem Inhalt der "If Length(S2) > 1 Then"-Bedingung.
(hauptsächlich Vergleich der Hash's und bei gleichem Hash nochmal einen byteweisen Vergleich der Daten,
damit das Problem gleicher Hash's, trotz unterschiedlicher Rohdaten nicht auftritt)

"S2 = Wortliste..." führt eine Funktion aus, welche die Bytes vergleicht und beim ersten Unterschied den Vergleich abbricht,
also die gesammten Stringdaten werden fast niemals verglichen/bearbeitet.

Und wenn man jetzt mal die beiden Varianten misst, dann wird eine erhebliche Steigerung der Geschwindigkeit dankt der Hash's auffallen.

Ein Vergleich ohne Hash's ist halt nur dann schneller, wenn nur ein einziger String, oder eben eine einzige Datei mit einem anderen String / einer anderen Datei verglichen wird.
Aber wenn man mehrere Strings/Dateien untereinander vergleicht, sieht das ganz anders aus, da ja sonst jeder String / jede Datei mehrfach eingelesen wird ... beim Hash hat mann dagegen einen netten kleinen Wert zum Vergleich ganz schnell zur Hand.

Warum hier unter Umständen nochmals die Strings/Dateien direkt miteinander Verglichen wird,
brauch ich dank Nico/Hagen ja nichtnochmal zu erklären.
z.B.
Zitat:
Wenn die Prüfsummen gleich sind, müssen die Daten nicht identisch sein.

Input: S
z.B. Inhalt einer TextDatei

Output: Wortliste
Liste aller enthaltenen Wörter
bestehend aus 0-9, A-Z, "_" und a-z


Delphi-Quellcode:
Var S, S2: AnsiString;
  i, i2, i3, L: Integer;
  H: LongWord;
  Wortliste: Array of Record
    Hash: LongWord;
    Wort: AnsiString;
  End;

Begin
  Wortliste := nil;
  L := Length(S);
  While (i <= L) and not (S[i] in ['0'..'9', 'A'..'Z', '_', 'a'..'z']) do Inc(i);
  While i <= L do Begin
    i2 := i;
    While (i2 <= L) and (S[i2] in ['0'..'9', 'A'..'Z', '_', 'a'..'z']) do Inc(i2);
    S2 := Copy(S, i, i2 - i);
    i := i2;
    If Length(S2) > 1 Then Begin
      H := CRC32(S2);
      i3 := -1;
      For i2 := High(Wortliste) downto 0 do
        If (H = Wortliste[i2].Hash) and (S2 = Wortliste[i2].Wort) Then Begin
          i3 := i2;
          Break;
        End;
      If i3 < 0 Then Begin
        i3 := Length(Wortliste);
        SetLength(Wortliste, i3 + 1);
        Wortliste[i3].Hash := H;
        Wortliste[i3].Wort := S2;
      End;
    End;
    While (i <= L) and not (S[i] in ['0'..'9', 'A'..'Z', '_', 'a'..'z']) do Inc(i);
  End;
End;

Delphi-Quellcode:
Var S, S2: AnsiString;
  i, i2, i3, L: Integer;
  Wortliste: Array of AnsiString;

Begin
  Wortliste := nil;
  L := Length(S);
  While (i <= L) and not (S[i] in ['0'..'9', 'A'..'Z', '_', 'a'..'z']) do Inc(i);
  While i <= L do Begin
    i2 := i;
    While (i2 <= L) and (S[i2] in ['0'..'9', 'A'..'Z', '_', 'a'..'z']) do Inc(i2);
    S2 := Copy(S, i, i2 - i);
    i := i2;
    If Length(S2) > 1 Then Begin
      i3 := -1;
      For i2 := High(Wortliste) downto 0 do
        If S2 = Wortliste[i2].Wort Then Begin
          i3 := i2;
          Break;
        End;
      If i3 < 0 Then Begin
        i3 := Length(Wortliste);
        SetLength(Wortliste, i3 + 1);
        Wortliste[i3] := S2;
      End;
    End;
    While (i <= L) and not (S[i] in ['0'..'9', 'A'..'Z', '_', 'a'..'z']) do Inc(i);
  End;
End;

In etwa so könnte es z.B. für Dateien aussehen:
Delphi-Quellcode:
List: Array of Record
  Hash: LongWord;
  FN: AnsiString;
End;


H := CRC32File(FileName);
i2 := -1;
For i := High(List) downto 0 do
  If (H = List[i].Hash) and CompareFile(FileName, List[i].FN) Then Begin
    i2 := i;
    Break;
  End;
If i2 < 0 Then Begin
  // Datei in die Liste eintragen
  i2 := Length(List);
  SetLength(List, i2 + 1);
  List[i2].Hash := H;
  List[i2].FN := FileName;
End Else Begin
  // eine Datei mit dem selben Inhalt existiert bereits
End;

PS: wie Hagen schon sagte, kann man jetzt noch die Dateigöße mit in den Vergleich mit einbeziehen, um nochmeh Geschwindigkeit rauszubekommen.
Aber so wie mein DemoCode aufgebaut ist, ist dieses nicht wirklich nötig, da ein weiteres Vergleichskriterium die gesammte Prozedur natürlich erstmal etwas verlangsamt
und die erhoffte Beschleunigung nur dann eintreten wird, wenn die Hash's gleich sind ... was ja auch nicht gerade oft vorkommt.
Ergo ist ein weiteres Vergleichskriterium, wie Größe/Datum... hierfür unnötig.
Aber wie gesagt, wenn man wiederum nur eine Datei mit einer anderen Vergleichen will, können witere Kriterien Wunder bewirken

PSS: was ich noch sagen bezöglich der maximalen Dateigröße sagen wollte ...
Viele Dateifunktionen arbeiten nur mit 32 Bit ... und obwohl die netten WinAPI-Funktionen auch 64 Bit verstehen können, wird dennoch (meistens) nur mit 32 Bit gearbeitet.
Also versagen die meisten Hashfunktionen schon bei Dateien über 2 GB.
Die Hashfunktionen mögen ja auch mit mehr als 2 GB umgehen können, aber wenn der Dateiinput dort aufgibt, bringt dieses nun auch nichts.

Und da die Dateien/Datenträger immer größer werden, sind mehr als 2 GB nichts exotisches mehr,
also hab ich meine UCC und demnach dir darin enthaltenen Hashfunktionen natürlich mit 64-Bit ausgestattet.


PS: Ja, das mit dem unverschämten Kopieren ist nicht nett und ich kann sowar ja auch nicht leiden.
Ich bin allerdings der Meinung, das es dabei nicht auf bestimmte Regionen ankommt, wie die Programmierer dort damit umgehen.

In meinem UCC habe ich zwar das Meißte selbst erstellt und an den entsprechenden Stellen, wo es nicht volltändig aus meiner Feder stammt, wird dieses dann auch erwähnt.




[add]
och menno ... immer dieser Hagen mit seinen Geheimnissen ... da denkt man mal, man hat 'nen Fehler in seinen Codes gefunden und dann behauptet der doch tatsächlich, das es angeblich richtig so sei
und wenn man dann die vielen Beiträge dort oben nochmal durchsieht, dann fällt einem auf, daß man sich die Arbeit mit den Codes auch hätte sparen können, weil einiges davon schonmal gesagt wurde

Ich muß unbedingt mal wieder etwas mehr Zeit hier verbringen ... denn bei solchen Themen fällt es doch stark auf, wenn man nicht ständig hier ist ... man kommt einfach nicht mehr hinterher -.-''

so, noch 2 Datei übrig
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
my Delphi wish list : BugReports/FeatureRequests
  Mit Zitat antworten Zitat