Dateiliste gefiltert erstellen

[DieDolly]

Der Titel klingt vielleicht etwas komisch. Aber grob erklärt.

Mit Winapi.Windows.FindFirstFileEx, ganz normal wie man das so kennt, gehe ich durch ein Verzeichnis. Zu jeder Datei und jedem Verzeichnis erstelle ich ein Objekt, welches in eine Liste kommt. Das funktioniert rasend schnell und reicht mir vollkommen so wie es ist.

Ich möchte aber bevor ein Objekt überhaupt erstellt wird prüfen, ob der Dateiname bei dem FindFirstFileEx() gerade dran ist in einer zweiten Liste vorkommt. Falls ja, soll das Objekt am Ende nicht erzeugt werden.

Die zweite Liste enthält nur halbe Pfade also beispielsweise so
Sub1\Sub2\File1.exe
FileX.exe
Sub1\FileY.exe

Das Hauptverzeichnis speichere ich dort nicht mit, da das zu große Dateien zum Speichern geben würde.

Wie kann ich mit Winapi.Windows.FindFirstFileEx() nun Dateien aussortieren, die in der zweiten Liste vorkommen?
Bei 1000 Dateien dauert das aktuell 4 Sekunden, wenn ich 400 davon aussortieren lassen möchte. Ohne Aussortieren dauert das Erzeugen der Objekte rund 10 Millisekunden.

[Nathan]

Ich würde zum Filtern nicht mehr direkt die WinAPI verwenden sondern nur noch TDirectory.GetFiles.

Delphi-Quellcode:

ListOfFromFiles := TDirectory.GetFiles(FCopyFrom, '*', TSearchOption.soAllDirectories, Predicate);

Predicate kann dann noch mehr filtern. Beispiel:

Delphi-Quellcode:

  Predicate :=
    function(const Path: string; const SearchRec: TSearchRec): Boolean
    begin
      Result := not string(SearchRec.Name).IsEmpty;
    end;

[DieDolly]

Wie lässt sich GetFiles mit meiner zweiten Liste kombinieren?

[himitsu]

* Ein MatchText, direkt auf's Array, geht ja nicht, für TeilStrings.
* Am Einfachsten mit EndsText, aber ich würde noch ein '\' davor hängen, weil

Delphi-Quellcode:

EndsText('FileX.exe', 'C:\dir\FileX.exe') = True
EndsText('FileX.exe', 'C:\dir\absadsadFileX.exe') = True
EndsText('\' + 'FileX.exe', 'C:\dir\absadsadFileX.exe') = False

wobei hier natürlich wäre direkt

Delphi-Quellcode:

if ExtractFilenName('C:\dir\FileX.exe') = 'FileX.exe'

besser
bzw.

Delphi-Quellcode:

if MatchText(ExtractFilenName('C:\dir\FileX.exe'), ['FileX.exe', Xyz.exe])

aber

Delphi-Quellcode:

EndsText('dir\FileX.exe', 'C:\dir\FileX.exe') = True
EndsText('dir\FileX.exe', 'C:\absadsaddir\FileX.exe') = True
EndsText('\' + 'dir\FileX.exe', 'C:\absadsaddir\FileX.exe') = False

Delphi-Quellcode:

FileNamenArray := TDirectory.GetFiles('C:\dir', '*.*', TSearchOption.soAllDirectories, 
  procedure (const Path: string; const SearchRec: TSearchRec): Boolean
  begin
    // SearchRec.Name = nur der Dateiname
    // TPath.Combine(Path, SearchRec.Name) = vollsändiger Pfad
    Result := True wenn Pfad im ergebnis sein soll.
    // es geht auch Result := False; und selbst irgendwo in einer externen Liste speichern oder direkt verarbeiten
  end);

[DieDolly]

Zitat:

EndsText('FileX.exe', 'C:\dir\absadsadFileX.exe') = True

EndsText kann ich nicht nehmen, weil ein FileX.exe in der Filterliste gilt nur im Hauptverzeichnis, nirgendwoanders.

Der Teilstring ist kein Problem. Ich kann das Hauptverzeichnis einfach vorne dranhängen!

[DieDolly]

Ich stelle mir gerade die Frage, ob es nicht eigentlich schneller wäre die Dateiliste einfach zu erzeugen ohne irgendwas rauszufiltern.
Kann man dann beide Listen miteinander vergleichen und Einträge aus Dateiliste löschen die in Filterliste vorhanden sind, ohne jeden Eintrag von beiden Listen miteinander zu vergleichen?

Beispiel:
Dateiliste (existierende Dateien):
C:\File1.exe
C:\File2.exe
C:\File3.exe
C:\Sub1\Sub2\File1.exe
C:\FileX.exe
C:\Sub1\FileY.exe
C:\File4.exe
C:\File5.exe

Filterliste (auf Dateiliste anwenden):
C:\Sub1\Sub2\File1.exe
C:\FileX.exe
C:\Sub1\FileY.exe

Am Ende dürfte also nur übrig bleiben:
C:\File1.exe
C:\File2.exe
C:\File3.exe
C:\File4.exe
C:\File5.exe

[tomkupitz]

Hallo,

bau dir eine einfache HashListe mit HashItems (mit Key=Dateiname und Path-Eigenschaft im HashItem). Der Vergleich letztendlich geht dann super schnell.

Beste Grüße

[DieDolly]

Ich kann das System nicht mehr umstellen. Eine neue Liste kann ich erstellen weil ich dann wochenlang beschäftigt wäre alles abzuändern.

Die Listen sind nicht das Problem, das Erstellen ist superschnell. Das vergleichen dauert ewig, deswegen meine Idee oben. Bitte durchlesen.

[tomkupitz]

Ok, wie findest du File1.exe von Liste1 in Liste2 ?

[DieDolly]

Anders erklärt.

Die Dateiliste A wird von Winapi.Windows.FindFirstFileEx() erstellt. Das sind alle Dateien in einem Verzeichnis.
Filterliste B sind ein paar Einträge von Dateien, die am Ende nicht in A landen sollen.

Das funktioniert ja alles schon, aber ist langsam. Weil jeder Fund von Winapi.Windows.FindFirstFileEx() iteriert die komplette Liste B durch.

Meine Idee wäre jetzt, die Dateiliste A erstmal ohne Filterung komplett zu erstellen und erst danach A und B zu vergleichen.

Alles aus B soll dann aus A verschwinden.

Fast vergessen. Da die Liste A Objekte enthält, muss ich da nicht zwangsläufig Einträge rauslöschen. Man könnte auch einfach eine Flag setzen, sodass die im späteren Verlauf ignoriert werden. Das würde der vorhandene Code zulassen.

Zusammengefasst:
beide Listen existieren, das Zusammenstellen der Listen ist rasendschnell und schnell genug.
Es hapert nur beim Vegleich.

Weil Wenn Liste A 15.000 Einträge hat und B 1000, sind das, wenn man jeden Eintrag mit jedem vergleicht, sehr viele Vergleiche, viele davon mehr als unnötig.

[himitsu]

HashListe oder einfach nur eine sortierte Liste ... da lässt sich schneller finden,
selbst wenn man eine TStringList benutzt.

TStringList.Sorted=True und TStringList.IndexOf
TDictionary<>
TArray<string> mit TArray.BinarySearch<string> (zum Suchen, aber auch zum "sortierten" Einfügen), bzw. TArray.Sort<string>
...

Zitat:

Zitat von DieDolly (Beitrag 1526069)

EndsText kann ich nicht nehmen, weil ein FileX.exe in der Filterliste gilt nur im Hauptverzeichnis, nirgendwoanders.

Dann mußt du wohl deine Pfade zu RelativenPfaden machen.
und dann kannst'e mit MatchText oder TArray.BinarySearch oder

ExtractRelativePath
TPath.IsPathRooted
siehe https://docwiki.embarcadero.com/RADS...ation_Routines
oder

oder ReplaceStr ähhh

Delphi-Quellcode:

ReplaceText(FullFileName, 'C:\root\', '')

[b][\b]
oder

Delphi-Quellcode:

Delete(FullFileName, 1, Length('C:\root\'));

(natrürlich aufpassen, falls nicht in diesem Pfad)
oder ...


https://stackoverflow.com/questions/...aths-in-delphi

[DieDolly]

Da sind mir zu viele "oder" in dem Text. Zuviel Stress. Ich lasse alles so wie es ist :P

[tomkupitz]

Zitat:

Weil Wenn Liste A 15.000 Einträge hat und B 1000, sind das, wenn man jeden Eintrag mit jedem vergleicht, sehr viele Vergleiche, viele davon mehr als unnötig.

Aber diese unnötigen Vergleiche verhinders du ja mit der HashListe.

vorhanden:

ListeB

File20
..
File30

von ListeB HashListe erstellen (oder gleich als Hash halten)


---

wird geade erstellt:

ListeA

File1 -> HashIndex berechnen und in ListeB im Index gucken => nicht da, kann in ListeA bleiben
..
File20 - HashIndex berechnen und in ListeB im Index gucken -> vorhanden, kann aus ListA raus
..
File100

ggf. Dateiname und Pfad wie oben erwähnt trennen und bei Vergleich nutzen.

Deine Suche dauert zu lange.

[DieDolly]

Ich kann nicht auf eine HashListe umstellen. Das geht einfach nicht mehr...

Wie sähe denn ein kleines Beispiel aus basierend auf Winapi.Windows.FindFirstFileEx()?

Vielleicht kann ich das anders lösen, ohne vorhandenen Code groß abändern zu müssen.
Meine Idee:
- Mit Winapi.Windows.FindFirstFileEx() Liste A erstellen und in HashListe packen.
- Liste B in HashListe packen (die steht in einer Textdatei).
Beide vergleichen.

Mit dem Rest von Liste A die Objekte erstellen.

Aber ich kann mir nicht vorstellen, wie das mit der HashListe funktioniert.

Meinst du sowas? https://www.delphipraxis.net/1159090-post3.html

[tomkupitz]

Beispiel mit Kollisionsprüfung (verkettete Liste):

Code:

unit Unit1;

interface

uses
  Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
  Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls;

type
  THashItem = class(TObject)
  public
    Key: string;

    Next: THashItem;
  end;

  THashList = class(TObject)
  private
    FItems: array of THashItem;

    function GetCount: Integer;
    function GetItem(Index: Integer): THashItem;
  public
    constructor Create(Count: Integer);
    destructor Destroy; override;

    function CreateHash(AKey: string): Integer;

    function Add(AKey: string): Boolean;
    procedure Clear;

    function Find(AKey: string): Integer;

    property Count: Integer read GetCount;
    property Items[Index: Integer]: THashItem read GetItem;
  end;

  TForm1 = class(TForm)
    ListBox1: TListBox;
    ListBox2: TListBox;
    Label1: TLabel;
    Label2: TLabel;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

constructor THashList.Create(Count: Integer);
begin
  inherited Create;

  SetLength(FItems, Count);
end;

destructor THashList.Destroy;
begin
  Clear;

  Finalize(FItems);

  inherited Destroy;
end;

//

function THashList.GetCount: Integer;
begin
  result:=Length(FItems);
end;

function THashList.GetItem(Index: Integer): THashItem;
begin
  if (Index>-1) and (Index<Length(FItems)) then
    result:=FItems[Index]
  else
    result:=nil;
end;

//

function THashList.Add(AKey: string): Boolean;
var i: Integer;

    Item: THashItem;

begin
  i:=CreateHash(AKey);

  if (i>-1) and (i<Length(FItems)) then
  begin
    if FItems[i]=nil then
    begin
      FItems[i]:=THashItem.Create;
      FItems[i].Key:=AKey;
    end;

    Item:=FItems[i];

    while Item.Key<>AKey do
    begin
      if Item.Next=nil then
      begin
        Item.Next:=THashItem.Create;
        Item.Next.Key:=AKey;
      end;

      Item:=Item.Next;
    end;

    if Item.Key=AKey then
    begin
      result:=True;
      Exit;
    end
  end;

  result:=False;
end;

procedure THashList.Clear;
var i: Integer;

    Item, Next: THashItem;

begin
  for i:=0 to High(FItems) do
    if FItems[i]<>nil then
    begin
      Item:=FItems[i];

      while Item<>nil do
      begin
        Next:=Item.Next;

        Item.Free;

        Item:=Next;
      end;

      FItems[i]:=nil;
    end;
end;

//

function THashList.Find(AKey: string): Integer;
var i: Integer;

    Item: THashItem;

begin
  i:=CreateHash(AKey);

  if (i>-1) and (i<Length(FItems)) then
  begin
    Item:=FItems[i];

    while (Item<>nil) and (Item.Key<>AKey) do
      Item:=Item.Next;

    if (Item<>nil) and (Item.Key=AKey) then
    begin
      result:=i;
      Exit;
    end;
  end;

  result:=-1;
end;

//

function THashList.CreateHash(AKey: string): Integer;
var i: Integer;

begin
  result:=-1;

  if Length(AKey)=0 then
    Exit;

  result:=ord(AKey[1]) mod Length(FItems);

  for i:=2 to Length(AKey) do
    result:=(result*128+ord(AKey[i])) mod Length(FItems);
end;

//

var
  hl: THashList;

procedure TForm1.FormCreate(Sender: TObject);
var i: Integer;

begin
  hl:=THashList.Create(50);

  //ListeB

  for i:=20 to 30 do
    hl.Add('File'+IntToStr(i));

  //ListeA

  for i:=0 to 100 do
    if hl.Find('File'+IntToStr(i))=-1 then
      ListBox1.Items.Add('File'+IntToStr(i))
    else
      ListBox2.Items.Add('File'+IntToStr(i));
end;

procedure TForm1.FormDestroy(Sender: TObject);
begin
  hl.Free;
end;

end.

###
object Form1: TForm1
  Left = 0
  Top = 0
  Caption = 'Form1'
  ClientHeight = 433
  ClientWidth = 622
  Color = clBtnFace
  Font.Charset = DEFAULT_CHARSET
  Font.Color = clWindowText
  Font.Height = -12
  Font.Name = 'Segoe UI'
  Font.Style = []
  OnCreate = FormCreate
  OnDestroy = FormDestroy
  TextHeight = 15
  object Label1: TLabel
    Left = 32
    Top = 24
    Width = 32
    Height = 15
    Caption = 'ListeA'
  end
  object Label2: TLabel
    Left = 247
    Top = 24
    Width = 31
    Height = 15
    Caption = 'ListeB'
  end
  object ListBox1: TListBox
    Left = 32
    Top = 56
    Width = 209
    Height = 329
    ItemHeight = 15
    TabOrder = 0
  end
  object ListBox2: TListBox
    Left = 247
    Top = 56
    Width = 209
    Height = 329
    ItemHeight = 15
    TabOrder = 1
  end
end

[DieDolly]

Ich habe das jetzt etwas anders gemacht. Mittels Winapi.Windows.FindFirstFileEx() hole ich mir alle Dateien und füge die in einen HashTable ein der so deklartiert ist

Delphi-Quellcode:

type
 TFileHashTable = TDictionary<string, TWin32FindData>;

var FileHashTable: TFileHashTable;

// hinzufügen
FileHashTable.Add(RootFolder + lfdStruct.cFileName, lfdStruct);

So hole ich Einträge die in Liste B sind aus Liste A raus

Delphi-Quellcode:

for i := 0 to ListeB.Count - 1 do
 begin
  if not FileHashTable.ContainsKey(RootFolder + ListeB.Strings[i]) then
   FileHashTable.Remove(RootFolder + ListeB.Strings[i]);
 end;

Aus dem was in FileHashTable jetzt übrig bleibt, möchte ich die Objekte erzeugen. Nur vielleicht stehe ich gerade auf dem Schlauch. Wie iteriere ich durch FileHashTable ?

[tomkupitz]

Du nimmst erstmal alle auf und entfernst dann die aus ListeB. Besser ist Einträge aus ListeB erst gar nicht in ListeA aufzunehmen.

Du durchsuchst ja FileHashTable mit FileHashTable.ContainsKey, soweit ok. Aber ich weiß nicht wie (schnell) ContainsKey sucht.

[DieDolly]

Zitat:

Du nimmst erstmal alle auf und entfernst dann die aus ListeB. Besser ist Einträge aus ListeB erst gar nicht in ListeA aufzunehmen.

So war es ja vorher und das war elendig langsam. Bei meinen Testdaten und mit dem alten Code hat das rund 4 Sekunden gedauert. Mit dem neuen Code jetzt nur noch wenn überhaupt 0,1 Sekunden.
Klar hat der neue Code nachteile. So kann ich keine Wildcards mehr verwenden, weil Strings 1zu1 abgeglichen werden. Aber besser der Code ist schnell.

Hier grob erklärt was ich jetzt mache

- Winapi.Windows.FindFirstFileEx() holt mir alle Dateien eines Verzeichnisses und fügt diese in meine Liste HashListe ein

Delphi-Quellcode:

type TFileHashTable = TDictionary<string, TWin32FindData>; var FileHashTable: TFileHashTable;

- ist das getan, gehe ich durch meine Liste B. Alles was in der fixen Liste B ist, wird aus der HashListe entfernt

Delphi-Quellcode:

for i := 0 to ListeB.Count - 1 do
 begin
  if FileHashTable.ContainsKey(RootFolder + ListeB.Strings[i]) then // ich bin mir nicht sicher, ob <Liste>.Remove selber nochmal prüft, ob der String vorhanden ist.
   FileHashTable.Remove(RootFolder + ListeB.Strings[i]);
 end;

- jetzt ist die HashListe bereinigt (alle Pfade aus Liste B sind jetzt nicht mehr dort drin)
- jetzt die Einträge der HashListe in meine eigentliche Liste A überführen, mit der ich weiterarbeite

Delphi-Quellcode:

for Key in FileHashTable.Keys do
 begin
  ...
 end;

Ja, Wildcards wären jetzt schön. Aber ich bin erstmal zufrieden.

[KodeZwerg]

Hallo DieDolly, ich bin mir nicht sicher ob das hier schneller ist aber so mache ich es.

Delphi-Quellcode:

program Project12;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.Classes,
  System.SysUtils,
  Generics.Collections;

type
  TTrieFilter = class
  private
    FChildren: TObjectDictionary<Char, TTrieFilter>;
    FIsWord: Boolean;
  public
    constructor Create;
    destructor Destroy; override;
    procedure AddWord(const Word: string);
    function ContainsWord(const Word: string): Boolean;
  end;

constructor TTrieFilter.Create;
begin
  FChildren := TObjectDictionary<Char, TTrieFilter>.Create([doOwnsValues]);
  FIsWord := False;
end;

destructor TTrieFilter.Destroy;
begin
  FChildren.Free;
  inherited;
end;

procedure TTrieFilter.AddWord(const Word: string);
var
  Node: TTrieFilter;
  Ch: Char;
  ChildNode: TTrieFilter;
begin
  Node := Self;
  for Ch in Word do
  begin
    if not Node.FChildren.TryGetValue(Ch, ChildNode) then
    begin
      ChildNode := TTrieFilter.Create;
      Node.FChildren.Add(Ch, ChildNode);
    end;
    Node := ChildNode;
  end;

  if not Node.FIsWord then
    Node.FIsWord := True;
end;

function TTrieFilter.ContainsWord(const Word: string): Boolean;
var
  Node: TTrieFilter;
  Ch: Char;
begin
  Node := Self;
  for Ch in Word do
  begin
    if Node.FChildren.ContainsKey(Ch) then
    begin
      Node := Node.FChildren[Ch];
      if Node.ContainsWord(Copy(Word, 2, Length(Word) - 1)) then
        Exit(True)
      else
        Exit(False);
    end;
  end;

  Result := Node.FIsWord;
end;

var
  SLDaten, SLFilter, SLOutput: TStringList;
  Trie: TTrieFilter;
  I: Integer;
begin
  try
    SLFilter := TStringList.Create;
    SLDaten := TStringList.Create;
    SLOutput := TStringList.Create;
    Trie := TTrieFilter.Create;
    try
      // beispielhaft deine filter liste
      SLFilter.Add('Sub1\Sub2\File1.exe');
      SLFilter.Add('FileX.exe');
      SLFilter.Add('Sub1\FileY.exe');

      // hier die klasse mit den filtern befüllen
      for I := 0 to Pred(SLFilter.Count) do
        Trie.AddWord(SLFilter[I]);

      // das hier überspringen und gleich zum filtern weiter
      // stell dir vor das ist deine dateiliste
      // ps: die reihenfolge ist absolute irrelevant
      SLDaten.Add('c:\Hallo DieDolly\Sub1\Sub2\File1.exe');
      SLDaten.Add('WasAuchImmerFileX.exeHierSteht, es triggert');
      SLDaten.Add('\\\Sub2\FileY.exe'); // das ist das einzige was übrig bleibt


      // Filter den input raus
      for I := 0 to Pred(SLDaten.Count) do
        if not Trie.ContainsWord(SLDaten[I]) then
          SLOutput.Add(SLDaten[I]);

      // darstellen was übrig blieb
      for I := 0 to Pred(SLOutput.Count) do
        WriteLn(SLOutput.Strings[I]);

    finally
      SLDaten.Free;
      SLFilter.Free;
      SLOutput.Free;
      Trie.Free;
    end;
    ReadLn;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.

Gerne würde ich ein paar brauchbare Benchmark Resultate sehen im Vergleich zu dem THashItem falls Dir meine Klasse gefällt.