Duplikate in STL Container und ein Knoten im Kopf

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Antworten
Benutzeravatar
Bebu
Beiträge: 562
Registriert: Mi Okt 21, 2009 6:19 pm
Wohnort: In der Nähe von Salzburg - Bin aber kein Österreicher!

Duplikate in STL Container und ein Knoten im Kopf

Beitrag von Bebu » Di Jan 03, 2012 8:12 am

Der Titel ist Programm. Seit zwei Tagen grüble ich, wie ich einen ordentlichen Algorithmus für die Duplikate hinbekommen. Folgende Datenstrukturen bilden den Rahmen der Handlung:

Code: Alles auswählen

/**
      *HandleDuplicates is used to say, what to do
      *with founded Duplicates
      */
    enum HandleDuplicates
    {
      Empty, ///Default value
      Keep, ///Keep file
      MarkAsKeep, /// Mark file as "keep" in the database
      Delete ///delete file from hdd
    };

    /**
      *DupHandle represents a single file, paired with a message, which says
      *to do with it.
      */
    typedef std::pair<Dedupe::FileInfo, HandleDuplicates> DupHandle;

    /**
      *DuplicateGroup represents Files with the same hash value
      */
    typedef std::vector<DupHandle> DuplicateGroup;

    /**
      *Duplicates represents all founded Duplicates, cleanly grouped to
      *process it to the user
      */
    typedef std::vector<DuplicateGroup> Duplicates;
So weit die Infrastruktur. Ich hole mir jetzt alle Dateien aus der Datenbank und will alle Duplikate herausgreifen und in die obigen Datenstrukturen einsortieren, damit das ganze dann ans Userinterface übergeben werden kann und der User entscheidet, wie es weiter geht. Die richtigen Dateien einfach per SQL Abfrage zu suchen, halte ich für ziemlich langsam, weil jedesmal ein Plattenzugriff erfolgt. Wie könnte so ein Algorithmus aussehen? Ich habe schon ein paar Ansätze im Kopf, aber vielleicht fällt jemandem ja eine elegantere Lösung ein.
Wer immer nach dem Unerreichbaren jagt, der wird irgendwann auf die Schnauze fallen!

Benutzeravatar
cloidnerux
Moderator
Beiträge: 3123
Registriert: Fr Sep 26, 2008 4:37 pm
Wohnort: Ram (Gibts wirklich)

Re: Duplikate in STL Container und ein Knoten im Kopf

Beitrag von cloidnerux » Di Jan 03, 2012 11:43 am

Klingt nach Sortierten Datenstrukturen, vlt sogar Hashbäume.
Dann müsstest du alle Einträge aus der SQL-Datenbank holen und z.B nach Dateigröße oder Hash sortieren.
Wenn das fertig ist, müssten ähnliche, bzw gleiche Dateien beieinander sein. Diese dann herauszusuchen dürfte nicht so schwer sein.

Dann vlt noch ein Wort zum Zeitrahmen: es ist ok wenn es auch mal länger als ein paar Sekunden dauert.
Redundanz macht wiederholen unnötig.
quod erat expectandum

Benutzeravatar
Bebu
Beiträge: 562
Registriert: Mi Okt 21, 2009 6:19 pm
Wohnort: In der Nähe von Salzburg - Bin aber kein Österreicher!

Re: Duplikate in STL Container und ein Knoten im Kopf

Beitrag von Bebu » Di Jan 03, 2012 12:42 pm

Gut, das ist ziemlich nahe an der Variante, die ich momentan in Arbeit habe, deswegen auch der Thread über die Lambdafunktion.
Wer immer nach dem Unerreichbaren jagt, der wird irgendwann auf die Schnauze fallen!

Antworten