Algorithmus für Datei-Umbenennen?

[Benmik]

Ich stehe vor dem Problem, Dateien in einem Verzeichnis umzubenennen und dabei das Problem von Dateinamenkollisionen möglichst effizient zu lösen.

Es wird ein Grund-Dateiname erstellt und eine fortlaufende Zahl in frei konfigurierbarer Weise (Position, Stellen, Startzahl, Vornullen) eingefügt. Anzahl und Auswahl der umzubenennenden Dateien können völlig variieren. Die umbenannten Dateien bilden dann einen homogenen Block mit gleichem Grundnamen und fortlaufender Nummer. Also in etwa das, was die zahlreichen Datei-Umbenenner so machen, mit dem Unterschied, dass es sein kann, dass eine Datei innerhalb des Blocks auf eine neue Position soll. Dann sollen die Dateinamen innerhalb des Blocks entsprechend angepasst werden.

Ich habe nicht den Überblick über die ganze Programmvielfalt, aber die Umbenenner, die ich kenne, machen es sich einfach und stellen bei Kollisionen schlicht die Arbeit ein. Das geht besser.

Mein bisheriger Ansatz:

Alle Dateinamen sind in einer TObjectList<TDateiInfo>. TDateiInfo ist eine Klasse mit einer Reihe Feldern, von denen hier nur "Dateiname" und "DateinameNeu" interessant sind. Die ObjectList verfügt über die notwendigen Funktionen zum Sortieren, Vergleichen und BinarySearch.

Von der ObjectList werden zwei weitere Instanzen erzeugt. In die eine kommen alle Dateien außerhalb des Blocks, in die andere die umzubenennenden, wobei in "DateinameNeu" dann auch gleich der neue Dateiname gespeichert wird. Bei jedem neuen Dateinamen wird in beiden Listen gesucht, ob der entsprechende Name schon vorhanden ist. Ist dies in der "Außenliste" der Fall, wird abgebrochen, da dieser Zustand nicht reparierbar ist. Gibt es auch "intern" keine Duplikate, dann ist die Sache einfach, es wird einfach ruckizucki durchbenannt.

Natürlich geht es hier nur um den zweiten Fall. Klar ist, dass es Kombinationen gibt, wo die Vergabe eines temporären Dateinamens unumgänglich ist. Und genau das will ich durch "intelligentes" Umbenennen auf das unvermeidbare Maß (am besten natürlich Null) drücken.

Und das ist letztlich meine Frage: Gibt es für sowas einen schlauen Algorithmus?

[Sir Rufo]

Du kannst es dir etwas einfacher machen.

Die TObjectList<T> kann auch auf Gleichheit prüfen. Dazu gibts du bei der Erzeugung der Liste System.Generics.Collections.TObjectList.Create einen System.Generics.Defaults.IComparer mit an.

In diesem Falle wirst du auf TDateiInfo.DateinameNeu vergleichen wollen.

Delphi-Quellcode:

list := TObjectList<TDateiInfo>.Create( TComparer<TDateiInfo>.Construct(
  function ( const L, R: TDateiInfo ): Integer
  begin
    Result := CompareStr( L.DateinameNeu, R.DateinameNeu );
  end ) );

// alle Dateien in die Liste eintragen

di := TDateiInfo.Create( 'SomeName.jpg' );

// prüfen, ob es diesen Eintrag schon gibt (wird über den Comparer ermittelt)
while list.Contains( di ) do
begin
  di.DateinameNeuAndersMachen();
end;

list.Add( di );

// Wenn fertig

for di in list do
  di.RenameTheFile();

[Benmik]

Muss ich mir erstmal zu Gemüte führen, vielen Dank.
Allerdings bin ich schockiert:

KEIN INTERFACE ???

[Sir Rufo]

IComparer<T>

[p80286]

Zitat von Benmik:

dass eine Datei innerhalb des Blocks auf eine neue Position soll.

Falls Du das mit der Position der Datei ernst meinst, verabschiede Dich davon. Du hast allerhöchstens eine Position innerhalb einer (Namens)Liste.

Gruß
K-h

[Namenloser]

Zitat von Benmik:

Und das ist letztlich meine Frage: Gibt es für sowas einen schlauen Algorithmus?

Du kannst das Problem als Graph darstellen: Die Knoten sind die Dateinamen (alte sowie neue), jede Umbenennung ist eine gerichtete Kante. Im Endeffekt läuft es dann darauf hinaus, Kreise in dem Graphen zu finden (einen schlauen Algorithmus dafür findest du auf Wikipedia ). Pro Kreis musst du einen temporären Dateinamen einfügen. Das ist die minimale Anzahl.

[Benmik]

Ich habe mir jetzt selber eine Lösung gebastelt. Der Schlauheitsgrad ist ungewiss, aber jedenfalls funktioniert sie. Bei ca. 1.400 Dateien (SSD, ältere CPU) benötigt sie zwischen 10 und 350 Millisekunden. Die besondere Herausforderung war, dass ich sie für ein Bildprogramm brauche, bei dem die Bilder auf einer Übersicht auf neue Positionen gezogen werden können, wobei die Dateinamen automatisch angepasst werden.

Der Algorithmus funktioniert so, dass die Dateien des Verzeichnisses zunächst getrennt werden nach denen, die umbenannt werden sollen, und den anderen (so vorhanden). Dabei wird für die umzubenennenden Dateien gleich der zukünftige Name ermittelt und gespeichert. Es wird geprüft, ob es Kollisionen gibt; bei solchen mit "äußeren" Dateien ist sogleich Schluss.

Danach wird in einer Schleife versucht umzubenennen. Erfolgreich umbenannte Dateien werden aus der Liste entfernt, die somit immer kleiner wird. Schluss ist hier, wenn entweder alle Dateien umbenannt werden konnten oder bei einem abgeschlossenen Durchlauf keine erfolgreichen Umbenennungen mehr möglich waren.

Danach wird mit temporären Umbenennungen gearbeitet bis zum hoffentlich guten Ende.

Der unten stehende Code ist herausoperiert und daher unvollständig und zum Teil simplifiziert; er dient nur zur Verdeutlichung des Algorithmus. Unter Umständen habe ich auch ein paar Anpassungen vergessen.

Die "Contains"-Lösung von Sir Rufo iteriert über alle Elemente der Liste; da ist eine BinarySearch sicher schneller. Ich habe auch eine Interface-Lösung von hier verwendet ("Replacing SHFileOperation With IFileOperation To Process Multiple File Operations In One Call"), aber mit dieser Lösung lief eine simple Umbenennung 50 - 300 Mal langsamer. Der Hinweis von Namenloser ist nichts für meine Preisklasse.

Delphi-Quellcode:

type

TSortArt    = (soNachDatname,soNachUmbName);

TDateiInfo = class(TObject)
  Datname       : string;
  Daterw        : string;
  UmbName       : string;
end;

TDateiListe = class(TObjectList<TDateiInfo>)
  private
    function  VergleicheDatname(const L,R:TDateiInfo):Integer;
    function  VergleicheUmbName(const L,R:TDateiInfo):Integer;
  protected
    function  getItem(Index: Integer): TDateiInfo; virtual;
    procedure setItem(Index: Integer; Objekt: TDateiInfo); virtual;
  public
    procedure Sort(SortArt:TSortArt);
    function  SucheDatName(const DatName:string;var P:Integer):Boolean;
    function  SucheUmbName(const UmbName:string):Boolean;
  end;

const Verz = 'C:\temp\';

function  BenenneBilderUm:Boolean;
var BInfo,UmbInfo:TDateiInfo;
    InDatUmbListe,InDatVerzListe:Boolean;
    DatUmbListe,DatVerzListe:TDateiListe;
const Zusatz = '$$$$';
//------------------------------------------------------------------------------------------------------------------------------------------
  procedure PrüfeDateinamenKollisionen;
  var DatNr,AnzUmb,p:integer; DatnameNeu:string;
  begin
    // Erstelle jeweils eine Liste der umzubenennenden Dateien und der im Zielverz vorhandenen (ggfs. übrigen) Dateien
    AnzUmb := 0;
    // Ordne alle Dateien der einen oder der anderen Liste zu
    For DatNr := 1 to Dateiliste.Count do begin
      BInfo := Dateiliste[DatNr - 1];
      If SollUmbenanntWerden then begin
        Inc(AnzUmb);
        DatnameNeu := ErmittleDatnameNeu(AnzUmb);
        BInfo.UmbName := DatnameNeu;
        DatUmbListe.Add(BInfo);
      end else begin
        BInfo.UmbName := '';
        DatVerzListe.Add(BInfo);
      end;
    end;
    DatUmbListe.Sort(soNachUmbName);
    // Doppelte Dateinamen durch Umbenennen innerhalb der umzubenennenden Dateien kann gehandhabt werden, bei den anderen nicht
    For DatNr := 1 to DatUmbListe.Count do begin
      If DatUmbListe.SucheDatName(Dateiliste[DatNr - 1].UmbName,p)
        then InDatUmbListe := True;
      InDatVerzListe := DatVerzListe.SucheDatName(Dateiliste[DatNr - 1].UmbName,p);
      If InDatVerzListe
        then break;
    end;
    If InDatVerzListe
      then Showmessage('Die Benennung der Dateien in der gewählten Form kollidiert mit vorhandenen Dateinamen im Zielverzeichnis.');
  end;
//------------------------------------------------------------------------------------------------------------------------------------------
  function  BenenneDateiUm(DatnameAlt,DatnameNeu:string):Boolean; overload;
  begin
    Result := SameText(DatnameAlt,DatnameNeu) or (not FileExists(DatnameNeu) and RenameFile(DatnameAlt,DatnameNeu));
  end;
//------------------------------------------------------------------------------------------------------------------------------------------
  function  BenenneDateiUm(Info:TDateiInfo;MitZusatz:Boolean = False):Boolean; overload;
  var DatnameAlt,DatnameNeu:string;
  begin
    DatnameAlt := Verz + Info.Datname + Info.Daterw;
    If MitZusatz
      then DatnameNeu := VUmbn.ZielVerz + Info.Datname + Zusatz + Info.Daterw
      else DatnameNeu := VUmbn.ZielVerz + Info.Umbname + Info.Daterw;
    Result := BenenneDateiUm(DatnameAlt,DatnameNeu);
    If Result and not MitZusatz then begin
      Info.DatName := Info.UmbName;
      Info.UmbName := '';
      DatUmbListe.Remove(Info);
    end;
  end;
//------------------------------------------------------------------------------------------------------------------------------------------
  function  VergebeNeueDateinamen:Boolean;
  var DatNr,AnzUmb,p:integer;
  begin
    DatUmbListe.Sort(soNachDatName);
    Try
      // Erster Angriff von unten - alles umbenennen, was geht
      Repeat
        AnzUmb := DatUmbListe.Count;
        For DatNr := DatUmbListe.Count downto 1 do
          Result := BenenneDateiUm(DatUmbListe[DatNr - 1]);
      Until (DatUmbListe.Count = 0) or (AnzUmb = DatUmbListe.Count);
      // Im Idealfall ist hier schon Schluss - wenn nicht, liegen Dateikollisionen vor
      If DatUmbListe.Count > 0 then begin
        Repeat
          // Ausgangswert; "Repeat" wird solange wiederholt, wie sich hier etwas tut (DatUmbListe.Count sinkt)
          AnzUmb := DatUmbListe.Count;
          For DatNr := DatUmbListe.Count downto 1 do begin
            BInfo := DatUmbListe[DatNr - 1];
            // Handelt es sich um eine temporär umbenannte Kollisionsdatei?
            If EndsText(Zusatz,BInfo.Datname) then begin
              If DatUmbListe.SucheDatName(BInfo.UmbName,p) then begin
                UmbInfo := DatUmbListe[p];
                BenenneDateiUm(UmbInfo);
              end else begin
                BenenneDateiUm(BInfo);
              end;
            // der "störende" Gegenpart wird gesucht und durch Umbenennung aus dem Weg geräumt
            end else if DatUmbListe.SucheDatName(BInfo.UmbName,p) then begin
              UmbInfo := DatUmbListe[p];
              If BenenneDateiUm(UmbInfo,True) then begin
                UmbInfo.Datname := UmbInfo.Datname + Zusatz;
                // jetzt ist der Weg frei
                BenenneDateiUm(BInfo);
              end;
            end else begin
              BenenneDateiUm(BInfo);
            end;
          end;
        Until (DatUmbListe.Count = 0) or (AnzUmb = DatUmbListe.Count);
      end;
    Except
      Result := False;
      Fehlerbehandlung;
      exit;
    End;
    Result := (DatUmbListe.Count = 0);
    If not Result
      then Showmessage('Von ' + IntToStr(Dateiliste.Count) + ' Dateien konnten ' + IntToStr(DatUmbListe.Count) + ' nicht umbenannt werden.');
  end;
//------------------------------------------------------------------------------------------------------------------------------------------
begin
  PrüfeDateinamenKollisionen;
  VergebeNeueDateinamen;
end;

[BUG]

Zitat von Benmik:

Der Schlauheitsgrad ist ungewiss, aber jedenfalls funktioniert sie.

Das ist das Wichtigste

Zitat von Namenloser:

Das ist die minimale Anzahl.

Der Graph, der da herauskommt hat interessante Eigenschaften: jeder Knoten kann nur einen Vorgänger haben (da sonst mehrere Dateien den gleichen Zielnamen hätten). Damit sollte jede ungerichteten Zusammenhangskomponent nur einen Kreis haben können.
In dem Fall könntest du mit einer Tiefensuche (finde Vorgänger, füge temporäre Umbenennung ein wenn du einen Kreis findest) vielleicht wirklich die optimale Lösung finden

Disclaimer: Graphentheorie und Bier ... das rat ich dir.