Schnelles Suchen nach Dateien

[GFEMajor]

Liebe Delphi Experten.
Ich habe wieder ein (für mich) großes Problem.

Ich arbeite immer noch an meiner Musiksuche, mit der ich Titel auf der Festplatte suchen kann.
Ich hab das ganze schonmal in Java umgesetzt und es so gemacht:
Alle Dateinamen in den Hauptspeicher lesen und dann dort suchen.

Jetzt wollte ich es in Delphi genauso machen, aber es geht einfach nicht schnell genug.
Ich suche mit FindFirst/FindNext usw alle Dateien in einem Wurzelverzeichnis und speichere die Dateinamen und den Pfad in einem Array vom Typ FileEntry (definition unten).
Es funktioniert zwar, aber viel zu langesam. Ich hab ca. 100.000 Dateien die hinzugefügt werden müssen.
Die Länge des Arrays setz ich schon ganz am Anfang, um es nicht jedes mal machen zu müssen, wenn ein Element hinzugefügt wird.

Hier mal die betreffenden Code Zeilen:

Delphi-Quellcode:

RFileEntry = packed record
 FileName: string[255];
 FilePath: string;
end;

procedure FindAllFiles(var FileEntrys : array of RCRSFileEntry; RootFolder: string; Mask: TStrings = nil; Recurse: Boolean = True);
var
  SR: TSearchRec;
  i: Integer;
  Item: RFileEntry;
begin
  RootFolder := IncludeTrailingPathDelimiter(RootFolder);
  if Mask = nil then
  begin
    Mask := TStringList.Create;
    Mask.Add('*.*');
  end;
  if Recurse then
    if FindFirst(RootFolder + '*.*', faAnyFile, SR) = 0 then
    try
      repeat
        if SR.Attr and faDirectory = faDirectory then // Verzeichnis
        begin
          if (SR.Name <> '.') and (SR.Name <> '..') then
          begin
            FindAllFiles(FileEntrys, RootFolder + SR.Name, Mask, Recurse);
          end;
        end else // Datei gefunden
        begin
          for i:= 0 to Mask.Count-1 do   // schauen ob sie in der Maske ist
          begin
            if ExtractFileExt(SR.Name) = ExtractFileExt(Mask[i]) then
            begin
              Item.FileName := SR.Name;
              Item.FilePath := RootFolder;
              AddFileToFileList(Item);
            end;
          end;
        end;
      until FindNext(SR) <> 0;
    finally
      FindClose(SR);
    end;
end;

procedure AddFileToFileList(Item : RFileEntry);
begin
  Files[aktLength] := Item;
  Inc(aktLength);
end;

Files ist dabei eine Propery der Komponente, die das einlesen übernimmt.

Grund warum ich alles in den Speicher lade ist die Performance beim Suchen. Die eigentlich Suche soll richtig schnell gehen, da bei mir schon bei der Eingabe des Suchwortes (wenn 3-4 buchstaben eingegeben wurden) automatisch gesucht werden soll. Darum ist mit die Performance beim Suchen sehr wichtig.

Falls es eine (schnelle) Möglichkeit gibt direkt auf den Dateinamen zu suchen wäre ich auch zufrieden.
Vielleicht fällt ja jemand etwas ein, wie ich die ganze Sache beschleunigen kann. Zur Zeit braucht das einlesen ca. 30 min-1 Stunde (hab noch nicht genau gemessen). Das ist aber auf jeden Fall viel zu lange. Zeiten bis 5 Minuten (für das einladen) wären für mich noch akzeptabel.

LG und schonmal vielen Dank

[mkinzler]

Nimm keinen Array, sondern eine verkettete Liste

[GFEMajor]

Ok, ich werd es mal Testen, aber warum sollte eine verkettete Liste schneller sein?
Ich leg ja das Array schon vor dem Einladen an. Es existieren also schon alle Einträge (nur ohne die richtigen Werte ;)). Und zur Laufzeit weise ich dann die Werte zu.

Bei einer List müsste ich in jedem Durchlauf ein Element anlegen und Zeiger setzen.

Edit:
----

Ich hab jetzt mal noch ne kleinere Zeitmessung gemacht. uUnd zwar mit folgendem Code:

Delphi-Quellcode:

procedure TCRSDataSourceFile.FindAllFiles(var FileEntrys : array of RCRSFileEntry; RootFolder: string; Mask: TStrings = nil; Recurse: Boolean = True);
var
  SR: TSearchRec;
  i: Integer;
  Item: RCRSFileEntry;
begin
  RootFolder := IncludeTrailingPathDelimiter(RootFolder);
  if Mask = nil then
  begin
    Mask := TStringList.Create;
    Mask.Add('*.*');
  end;
  if Recurse then
    if FindFirst(RootFolder + '*.*', faAnyFile, SR) = 0 then
    try
      repeat
        if SR.Attr and faDirectory = faDirectory then // Verzeichnis
        begin
          if (SR.Name <> '.') and (SR.Name <> '..') then
          begin
            FindAllFiles(FileEntrys, RootFolder + SR.Name, Mask, Recurse);
          end;
        end else // Datei gefunden
        begin
          aktLength := 0;
        end;
      until FindNext(SR) <> 0;
    finally
      FindClose(SR);
    end;
end;

Es wird also nichts mit den Dateien gemacht. Nur jede einmal angefasst. Und da dauert das einlesen von 10.000 Elementen schon 3 Minute lang. Ich denke also, der Beschränkende Faktor ist entweder die Festplattengeschwindigkeit oder Die Funkntionen FindFist/FindNext usw.
Oder habt ihr eine andere Idee?

[Hawkeye219]

Hallo,

einige Dinge sind mir aufgefallen:

1. Du verwendest für den Dateinamen einen ShortString - warum? Beim Übertragen in den Record müssen so immer 256 Bytes bewegt werden, während bei der Verwendung dynamischer Strings wahrscheinlich nur ein Referenzzähler erhöht werden muss.

2. Bei jedem Vergleich der Extensions rufst du die Funktion ExtractFileExt auf, obwohl sich die Extensions in der Liste während der Suche nicht ändern. Vielleicht wäre es günstiger, für die Liste die Sortierung einzuschalten und mittels TStringList.IndexOf zu suchen. Damit hättest du gleichzeitig das Problem der Groß-/Kleinschreibung erschlagen.
Falls du an deiner Suchschleife festhalten möchtest, solltest du sie übrigens nach einem Fund abbrechen. Warum weiter suchen, wenn die Datei schon als "bekannt" identifiziert wurde?

3. Wenn die Routine ohne Maske aufgerufen wird, erzeugt sie intern eine Stringliste. Dieses Objekt wird aber nie freigegeben.

Diese Hinweise werden sicher nicht alle Performanceprobleme lösen, aber vielleicht sind dennoch nützlich. An FindFirst/FindNext wirst du kaum vorbeikommen.

Ich habe deinen letzten Code übrigens einmal (unverändert) auf meine externe Festplatte losgelassen. Nach 145 Sekunden hattte er knapp 100.000 Dateien gefunden (Core2Duo, 2.4 GHz).

Gruß Hawkeye

[GFEMajor]

Ich hab auch das Problem gefunden, warum es so lange dauert. Ich hatte die Optimierung im Compiler ausgeschaltet (mach ich oft im Entwicklungsmodus, damit nicht irgendwelche wichtigen variablen zur Debugzeit "wegoptimiert" werden).
Optimierung an und das einladen geht in wenigen Sekunden :).
Die Anregungen werd ich mir zu Herze nehmen und die Sachen noch anpassen :).

Vielen dank auf jeden fall.

[Meflin]

Zitat:

Zitat von GFEMajor

Ich hatte die Optimierung im Compiler ausgeschaltet (mach ich oft im Entwicklungsmodus, damit nicht irgendwelche wichtigen variablen zur Debugzeit "wegoptimiert" werden

Wenn sie wirklich wichtig sind, dann können sie eigentlich nicht wegoptimiert werden :zwinker:

[Bernhard Geyer]

Ein kleines Const bring auch etwas bei funktionsparameter deren SizeOf > 4 Byte ist:

procedure AddFileToFileList(const Item : RFileEntry);

[GFEMajor]

Zitat:

Zitat von Meflin

Zitat:

Zitat von GFEMajor

Ich hatte die Optimierung im Compiler ausgeschaltet (mach ich oft im Entwicklungsmodus, damit nicht irgendwelche wichtigen variablen zur Debugzeit "wegoptimiert" werden

Wenn sie wirklich wichtig sind, dann können sie eigentlich nicht wegoptimiert werden :zwinker:

Nicht unbedingt wichtig für die Ausführung, aber manchmal wichtig für das Verständnis um Fehler zu finden ;).

[mkinzler]

So werden z.B. oft beim Debuggen, für das Verständis, die Fehlersuche wichtige Variablen wegoptimiert

[thkerkmann]

Zitat:

Zitat von mkinzler

So werden z.B. oft beim Debuggen, für das Verständis, die Fehlersuche wichtige Variablen wegoptimiert

:wiejetzt: Äh, hast Du an diesem Satz irgendwas wegoptimiert ?