Compare Files -> Optimieren

[cherry]

Hi @all

hier wahrscheinlich mein letzter Beitrag in diesem Jahr...

Ich habe mir ein kleines Programm geschrieben das rekursiv Dateien von zwei beliebigen Ordnern auf die Aktualität
überprüft und das Ergebnis in ein StringGrid schreibt...

Nun soweit ich es getestet habe funktioniert das ganze auch, bin aber mit der Geschwindikeit nicht zufrieden...
Ich habe einen Geschwindikeitsvergleich mit dem Tool "Total Commander" gemacht und musste feststellen das mein Programm für
den gleichen Vergleich immer etliche Sekunden länger braucht. [-> Vergleich mit 9591 Dateien in über 1000 Ordnern]

Kurz zum Aufbau meines Programms:

Zuerst werden beide angegebenen Ordner rekursiv nach Dateien abgesucht, das Ergebnis wird in einem Array festgehalten.
Anschliessend werden die beiden Arrays verglichen...

Viellecht müsste man die Methodik grundsätzlich überdenken?!
Bin auf Eure verbesserungsvorschläge gespannt!


Im Anhang das ganze Projekt...

Guten Rutsch ins neue Jahr

[p80286]

Hallo Cherry,

Ich hab gerdade kein Delphi zur Hand darum nur eine theoretische Überlegung:

zunächst, was willst Du mit dem Vergleich erreichen?
1) Du suchst gleiche Dateien mit gleichem Inhalt/gleichem Namen
2) Du suchst unterschiedliche Dateien in Verzeichnissen, die wahrscheinlich gleich oder weitestgehend gleich sind.

Im ersten Fall steckst Du alle Dateinamen und die Dateigrößen in eine Tlist, sortierst nach der Größe und löschst alle Sätze wo es für die Größe keine Doublette gibt. Soll auch der Name gleich sein löschst Du auch die mit unterschiedlichen Namen. Was übrig bleibt, sind die vielleicht doppelten.
Die nimmst Du Dir paarweise und liest die ersten 512...2048 Byte in zwei Arrays ein. Die Größe ist davon abhängig welche Dateien Du vergleichen willst, sprich wo wahrscheinlich der erste Unterschied auftaucht.
Was danach noch übrig bleibt, davon erstellst du eine Prüfsumme (Hash) und wenn die gleich ist,dann hast Du eine inhaltsgleiche Datei.

Im zweiten Fall erstellst Du zwei Listen, eine für das Quell- und eine für das Zielverzeichnist. Aus der Liste des Quellverzeichnisses generierst Du eine weitere Liste,die dem Inhalt des Zielverzeichnisses entsprechen sollte.
vergleiche die Sollliste mit der Zielliste und Du erhälst die Dateien/Dateinamen die nur im Ziel oder Quellverzeichnis enthalten sind.
Die übrigen vergleichst Du nach dem gleichen Schema wie oben, nur das Du diesmal die gleichen Dateien verwirfst und die ungleichen behälst.

Grüße K-H

[Luckie]

Zitat von cherry:

Anschliessend werden die beiden Arrays verglichen...

Und genau das ist der entscheidende Punkt. WIE vergleichst du? Vergleichst du Byte für Byte oder bildest du über die Dateien einen Hash und verglechst den oder was machst du?

[alzaimar]

Man muss sowieso nur die Dateien vergleichen, die eventuell identisch sein könnten. Dateien unterschiedlicher Größe und/oder unterschiedlichen Datums sind eh verschieden. Per Hash würde ich dann auch nicht vergleichen, sondern bis zum auftreten des ersten ungleichen Zeichens. Das dürfte schneller sein.

[p80286]

Hallo zusammen und ein gutes neues Jahr,

@alzaimar
auf das gleiche/ungleiche Datum würde ich nicht vergleichen, da mir vor ein paar Jahren ein Novell-Server das Dateidatum "zerbröselt" hat. Auf's Bit gleiche Dateien hatten aus ungeklärten Gründen auf dem Server eine Stunde "Nachlauf", die dann zum Ausgleich beim kopieren auf den Client eine Stunde "Vorlauf" bekamen. Auch wenn die Zeit zwischen zwei Rechner nicht ordentlich syncronisiert, bekommst Du Probleme, darum Finger weg vom Datum(Zeit).

was den Vergleich angeht, hast Du Recht, wenn zu erwarten ist, daß der überwiegende Teil der Dateien ungleich ist. Ist die Zahl der gleichen größer, oder der Unterschied liegt erst am "Ende", dann ist ein Hash schneller. (Zumindestens wenn ein erklecklicher Teil über 5-10 MB liegt)

Grüße
K-H

[stahli]

so mache ich das:
(vorab Größe vergleichen und dann blockweise erstes unterschiedliches Zeichen suchen)

Delphi-Quellcode:

procedure TDCustom.CompareFileNow;
const
  BS = 1000;
type
  TBB = array[1..BS] of Byte;
var
  S1, S2: String;
  F1, F2: File of Byte;
  B1, B2: TBB;
  F: Boolean;
  R1, R2, I: Integer;
begin
...
          S1 := FileName;
          S2 := PathCompare + CompareFileName;
          if (S1 <> '') and (S2 <> '') and (S1 <> S2) then
          begin
            if FileExists(S1) then
            begin
              ...
              if FileExists(S2) then
              begin
                F := True;
                AssignFile(F1, S1);
                Reset(F1);
                AssignFile(F2, S2);
                Reset(F2);
                if FileSize(F1) = FileSize(F2) then
                begin
                  repeat
                    BlockRead(F1, B1, Length(B1), R1);
                    BlockRead(F2, B2, Length(B2), R2);
                    if R1 = R2 then
                    begin
                      for I := 1 to R1 do
                      begin
                        if B1[I] <> B2[I] then
                        begin
                          F := False;
                          Break;
                        end;
                      end;
                    end
                    else
                    begin
                      F := False;
                    end;
                  until (not F) or (Eof(F1) and Eof(F2));
                end
                else
                begin
                  F := False;
                end;
                CloseFile(F1);
                CloseFile(F2);
                FFileIsValue := F; // <---
              end;
            end;
          end
          else
...
end;

stahli

[alzaimar]

Zitat von p80286:

auf das gleiche/ungleiche Datum würde ich nicht vergleichen

Es kann aber trotzdem sein, das sie unterschiedlich sind. Du beschreibst hier ein 'false positive' Ereignis, das nicht zu einem Fehler führt, sondern nur zu einem unnötigem Vergleich. WTF.

Zitat von p80286:

Ist die Zahl der gleichen größer, oder der Unterschied liegt erst am "Ende", dann ist ein Hash schneller. (Zumindestens wenn ein erklecklicher Teil über 5-10 MB liegt)

Das verstehe ich nicht.
Bei einer Hashberechnung lese ich eine Datei *vollständig* ein und berechne einen Wert. Das mache ich für beide Dateien.
Bei einem Dateivergleich lese ich auch beide Dateien Stück-für-Stück ein und vergleiche sie. Wo soll da der Geschwindigkeitsvorteil bei der Hashberechnung sein? Sind Hashbberechnungen neuerdings schneller als Vergleiche? Außerdem breche ich doch sowieso beim ersten ungleichen Byten ab. Bei einer angenommenen Gleichverteilung der Unterschiede lese ich also im Mittel nur 50% der Dateien ein. Der Einzige Vorteil eines Hashes wäre, wenn eine Datei A mit mehreren Dateien verglichen werden muss. Dann hätte ich einen Geschwindigkeitsvorteil.
Im Übrigen bedeuten identische Hashes ja nicht notwendigerweise identische Inhalte. Die Wahrscheinlichkeit ist zwar 'eher' gering, aber rein mathematisch gesehen ist ein Dateivergleich per Hash ungenügend, ergo stimmt die E/A-Relation nicht, mithin ist das Programm dann beweisbar falsch.

[p80286]

hallo alzaimar,

beim Datum hab ich mich wohl falsch ausgedrückt. Meine Annahme war
gleiche Größe und unterschiedliches Datum=unterschiedliche Datei
und das war falsch! Ich mußte also die Datei selbst vergleichen.

Wie Du richtig ausgeführt hast, ist der Hash nur dann schneller wenn eine Datei mehrmals an einem Vergleich beteiligt ist. Dies ist bei mir der Fall, da z.b. bei drei Dateien mit der gleichen Größe jede Datei mit jeder anderen also (1 mit 2 und 3) und (2 mit 3) verglichen wird.
Aber vielen Dank für die Anregung.
Ich denke an der Vergleichslogik kann ich noch eine Menge feilen.
Was den "Hash" angeht, verwende ich einen Prüfsummenalgorithmus, der vor Urzeiten mal in der Dr. Dobbs gestanden hat, der nach meinen Erfahungen für Dateien gleicher Größe bei ungleichem Inhalt auch ungleiche Werte produziert.
Ich hab auch mal den "Adler" ausprobiert, aber bei dem sind Fehler aufgetreten.
Mit MD5 habe ich auch noch keine Fehler erhalten, aber der ist etwas langsamer als "Dr.Dobbs".

Da ich z.Zt. weit weg bin von meinem Delphi, kann ich nicht konkreter werden.


@stahli:
Entschuldigung Dich hätte ich beinahe vergessen. Du solltest BS ein wenig vergrößern.
Ich glaube an die Magie der 2erPotenzen also 4096,8192 usw.
versuchs mal damit

Grüße
K-H

[cherry]

Anscheinend liegen einige Missverständtnisse vor...

Ich will in erster Linie die Dateien zweier nahezu identischen Ordnern auf ihre Aktualität überprufen. Und das übers Datum und nicht über den Inhalt der Dateien...

Das ganze habe ich auch bereits realisiert, nur scheint mir meine Methodik nicht optimal da es offensichtlich auch schneller geht...

Werft doch einfach mal einen Blick auf den Code...

Delphi-Quellcode:

...

// ]]] START COMPARING [[[
procedure TFormMain.Compare;
var
  i,j,c,tmpIndex,tmpIndex2:Integer;
  Dir:String; // Directory Name
  arChecked: array of Integer;
begin

  ClearStringGrid;
  SetLength(arFileRec1,0);
  SetLength(arFileRec2,0);
  SetLength(arChecked,0);
  Dir:='';
  c:=0; // files count
  abort:=false;

  GetTreeList(DirectoryListBox1.Directory, DirectoryListBox1.Directory, '*', CbSubDirs.Checked, True, arFileRec1);
  GetTreeList(DirectoryListBox2.Directory, DirectoryListBox2.Directory, '*', CbSubDirs.Checked, False, arFileRec2);

  for i := low(arFileRec1) to high(arFileRec1) - 1 do
  begin

//    Application.ProcessMessages;
//    if abort then
//      exit;

    if (Dir <> arFileRec1[i].Dir) then
    begin
      Dir:=arFileRec1[i].Dir;
      Write(0,Dir,True);
    end;
    Write(0,arFileRec1[i].Name,True);
    Write(1,IntToStr(arFileRec1[i].Size));
    Write(2,DateTimeToStr(arFileRec1[i].Date));
    tmpIndex:=ArFileRecIndexOfDirName(arFileRec2,arFileRec1[i].DirName);
    Inc(c);
    if (tmpIndex <> -1) then
    begin
      // remember the values already checked ...
      SetLength(arChecked,Length(arChecked)+1);
      arChecked[Length(arChecked)-1]:=tmpIndex;
      // at least compare date values ...
      case CompareDate(arFileRec1[i].Date,arFileRec2[tmpIndex].Date) of
        fdsNewer: begin Write(3,'>'); end;
        fdsOlder: begin Write(3,'<'); end;
        fdsSameDate: begin Write(3, '=') end;
      end;
      Write(4,DateTimeToStr(arFileRec2[tmpIndex].Date));
      Write(5,IntToStr(arFileRec2[tmpIndex].Size));
      Write(6,arFileRec2[tmpIndex].Name);
    end
    else
    begin
      Write(3,'>');
      tmpIndex2:=arFileRecIndexOfDir(arFileRec2,arFileRec1[i].Dir,0);
      if tmpIndex2 <> -1 then
      begin
        for j := tmpIndex2 to high(arFileRec2) - 1 do
        begin
          if not IntArray_Contains(arChecked,j) then
          begin
            if arFileRecIndexOfDir(arFileRec2,arFileRec1[i].Dir,j) <> -1 then
            begin
              if (arFileRecIndexOfDirName(arFileRec1,arFileRec2[j].DirName) = -1)
                and (arFileRec1[i].Dir = arFileRec2[j].Dir) then
              begin
                Write(3,'<',True);
                Write(4,DateTimeToStr(arFileRec2[j].Date));
                Write(5,IntToStr(arFileRec2[j].Size));
                Write(6,arFileRec2[j].Name);
                // remember the values already checked ...
                SetLength(arChecked,Length(arChecked)+1);
                arChecked[Length(arChecked)-1]:=j;
                Inc(c);
              end
            end
            else
              break;
          end;
        end;
      end;
    end;
  end;

  Dir:='';

  // maby there exists folders unique on the right ...
  for i := low(arFileRec2) to high(arFileRec2) - 1 do
  begin

//    Application.ProcessMessages;
//    if abort then
//      exit;

    if not IntArray_Contains(arChecked,i) then
    begin
      if (Dir <> arFileRec2[i].Dir) then
      begin
        Dir:=arFileRec2[i].Dir;
        Write(0,Dir,True);
      end;
      Write(3,'<',True);
      Write(4,DateTimeToStr(arFileRec2[i].Date));
      Write(5,IntToStr(arFileRec2[i].Size));
      Write(6,arFileRec2[i].Name);
      Inc(c);
    end;
  end;

  Statusbar1.Panels[0].Text := ' files found: '+IntToStr(c);
  BtnCompare.Enabled:=True;
  BtnAbort.Enabled:=False;

end; 

...

Das ganze Projekt ist wie gesagt im ersten Beitrag gepostet...

[p80286]

hallo Cherry,

Ich habe z.Zt. keine Möglichkeit Deinen Code herunter zu laden, darum nur so aus der Hüfte:
Du verwendest sehr viele write, und die kosten Zeit!

grüße
K-H