Liste vergleichend durchlaufen

boenz666

Hallo,

Ich habe folgende Problematik bei der ich mal einen Denkanstoß benötige, was die Realisierung anbelangt:

Mein Programm durchsucht jedes Verzeichnis auf jedem Datenträger des aktuellen Systems rekursiv und sammelt alle Bilddateien (FileInfo abhängig von der Extension)) in einer Liste. Aktueller Durchlauf ca. 30000 Bilddateien.

Diese Liste soll nun untersucht werden nach Duplikaten über die MD5 Summe, was auch schon einwandfrei implementiert wurde von mir und funktioniert.

Aktuell ist der Durchlauf jedoch sehr zeitaufwändig, da ich ein Objekt aus der Liste nehme und die Duplikatstreffer nicht aus der Liste ausfiltern kann zur Laufzeit ohne mir eine Exception einzufangen. Ich bin leider nicht bewandert in Linq, wobei es da sicherlich super Möglichkeiten gibt und suche nun nach einem Lösungsansatz, wie ich das bewerkstelligen kann.

Die einzige Idee, die ich habe ist, die Liste zu kopieren und das bereits durchsuchte Element auszuschließen, was die Suche schon beschleunigen würde.
Jedoch wird an der Stelle, an der ich das Listenelement aus der Kopie (copy) entferne merkwürdigerweise das Listenelement ebenfalls aus der Ursprungsliste (files) entfehrnt.

int index;

List<FileInfo> copy = new List<FileInfo>();
copy = files;

foreach (FileInfo file in files)
{
    index = files.IndexOf(file);
    for (int i = index; i < files.Count; i++)
    {
        if (CheckMD5(file, copy.ElementAt(i + 1)))
        {
            listBoxDuplicate.Add(file + " " + copy.ElementAt(i + 1));
                copy.RemoveAt(i + 1);
        }
    }
}

Ich habe das Gefühl, dass mein Lösungsansatz nicht die eleganteste Wahl ist, leider verfüge ich nicht über ausreichende Kenntnisse in Linq, was mir sicherlich eine einfach Lösung bieten würde über den where Parameter.

Du arbeitest ja auch nicht mit einer Kopie

List<FileInfo> copy = new List<FileInfo>();
copy = files;

Durch die zweite Zeile referenziert copy die gleiche Liste wie die Referenz files . Die neu erstellte Liste aus Zeile 1 geht verloren.

Zum Problem:
Arbeite mit einer HashSet<MyFileInfo> für eine eigene Klasse MyFileInfo (s.u.). Jetzt musst Du Deine ursprüngliche Liste nur einmal durchlaufen und prüfen ob eine Datei bereits in der HashSet vorhanden ist, falls nicht einfügen.

(Pseudocode)

class MyFileInfo
{
	System.IO.FileInfo i;
	MD5Sum sum;

	public MyFileInfo()
	{
		sum = CalcMD5();
	}
	public override int GetHashCode()
	{
		return sum.GetHashCode();
	}
	public override bool Equals(object obj)
	{
		return ((MyFileInfo)obj).sum == sum;
	}
}

boenz666

Vielen Dank für den eleganten Lösungsansatz

boenz666

Also ich habe das jetzt mal versucht umzusetzen, habe aber doch noch ein Problem, da Hashsets für mich komplett neu sind.

Meine Klasse für das FileInfo lautet folgendermaßen:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Security.Cryptography;

namespace ComparingTool
{
    public class MyFileInfo
    {
        public FileInfo file;
        byte[] sum;

        public MyFileInfo(string _file)
        {
            this.file = new FileInfo(_file);
            sum = CalcMD5();
        }

        public override int GetHashCode()
        {
            return sum.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            return ((MyFileInfo)obj).sum == sum;
        }

        private byte[] CalcMD5()
        {
            //Berechnung der MD5Summe
        }
    }
}

Soweit so gut, nun befülle ich meine Liste mit den MyFileInfo Objekten:

foreach (string f in Directory.GetFiles(subdir, "*.*").Where(s => //...
{
    MyFileInfo file = new MyFileInfo(f);
    files.Add(file);
}

Nun tue ich mich jedoch etwas schwer/blöd beim Füllen der Bilddateien in das HashSet:

HashSet<MyImageFile> myhashset = new HashSet<MyImageFile>();

foreach(MyImageFile file in files)
{
    if (!hashset.Contains(file))
        hashset.Add(file);
    else
       listBoxDuplikate.Items.Add(file.ToString());
    Application.DoEvents();
}

Ich hatte angenommen, dass die Contains-Methode die Equals-Methode des Hashset-Objektes abruft, aber da habe ich scheinbar noch irgendwo nen Fehler drin. Es wird nur die GetHashCode Methode aufgerufen und zwar beim Contains, sowie beim myhashset.Add

Ja, vorsicht, deine Checksum ist ein einfaches byte-Array. Bei Gleichheit mittels == Operator werden die Referenzen verglichen, nicht der Inhalt der Arrays. Ebenso haben zwei byte-Arrays mit identischem Inhalt einen unterschiedlichen HashCode per Default.

Es liegt hier an Dir einen "sinnvollen" HashCode zu berechnen der auf den Einträgen* des Arrays basiert, ebenso das Array elementweise zu vergleichen damit Equals funktioniert.

Das Phänomen das du beobachtest, nämlich dass Equals nicht aufgerufen wird, hat folgenden Grund: Zwei identische Objekte gemäß Equals müssen den gleichen Hashcode haben. Die Umkehrung gilt aber nicht. D.h. gültig muss sein Equals(lhs, rhs) => GetHashCode(lhs, rhs).
Damit gilt auch !GetHashCode(lhs, rhs) => !Equals(lhs,rhs).
Nun fügst Du Elemente in die Hashset ein und diese Collection prüft erstmal den Hashcode. Sie stellt fest, dass die byte-Arrays unterschiedliche Hashcodes haben und kann darauf schließen, dass sie damit nicht identisch sein können.

Wie gesagt, der Fehler liegt in der falschen Implementierung der beiden Methoden.

*Nicht auf allen Einträgen. Evtl. nur auf der Länge der Arrays. Der Hashcode soll schnell berechenbar sein.

Edit: Ich kann nicht mehr Rechtschreiben

hustbaer

µ schrieb:

*Nicht auf allen Einträgen. Evtl. nur auf der Länge der Arrays. Der Hashcode soll schnell berechenbar sein.

Nur auf der Länge? WTF?
Nein, bitte schon auf allen Einträgen!

Bzw. man könnte sich auch gleich das Leben einfacher machen und ein Dictionary<string, List<string>> verwenden.
Key = Hashcode, hex formatiert
Value = Liste mit Filenamen

hustbaer schrieb:

µ schrieb:

*Nicht auf allen Einträgen. Evtl. nur auf der Länge der Arrays. Der Hashcode soll schnell berechenbar sein.

Nur auf der Länge? WTF?
Nein, bitte schon auf allen Eintragen!

Ja in dem Fall war der Tipp daneben, weil die MD5 immer gleich lang sind. Hatte die ursprünglichen Bilddateien im Kopf...aber da gäbe es auch zu wenig Variation

boenz666

Ok, das mit der Länge des Arrays hatte mich schon verwirrt.

Zur urspürnglichen Problematik bin ich nun vollends durcheinander. Ich habe mir nun einige Beispiele für Hashsets durchgelesen und dazu auch was gelesen, aber ich schaffe es immernoch nicht, dass in meinem Programm zu realisieren. Das Objekt, welche mein Hashset-Objekt darstellt habe ich nun umgebaut, damit die Equals Methode nun richtig aufgerufen würde. Ist das soweit richtig?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Security.Cryptography;

namespace Image_Comparer
{
    public class ImageFile
    {
        public FileInfo file;
        byte[] sum;

        public ImageFile(string _file)
        {
            this.file = new FileInfo(_file);
            sum = CalcMD5();
        }

        public override int GetHashCode()
        {
            return sum.GetHashCode();
        }

        public override bool Equals(object obj)
        {
            FileInfo file2 = (FileInfo)obj;
            byte[] firstHash = MD5.Create().ComputeHash(this.file.OpenRead());
            byte[] secondHash = MD5.Create().ComputeHash(file2.OpenRead());

            for (int i = 0; i < firstHash.Length; i++)
            {
                if (firstHash[i] != secondHash[i])
                    return false;
            }
            return true;
        }

        public static bool operator ==(ImageFile file1, ImageFile file2)
        {
            return (file1.Equals(file2));

        }
        public static bool operator !=(ImageFile file1, ImageFile file2)
        {
            return (!file1.Equals(file2));
        }

        private byte[] CalcMD5()
        {
            try
            {
                byte[] hash = MD5.Create().ComputeHash(this.file.OpenRead());
                return hash;
            }
            catch (Exception ex)
            {
                return null;
            }
        }
    }
}

1. Du prüfst im Ctor nicht ob das File existiert bzw. zugegriffen werden kann. -> Möglicher Laufzeitfehler

2. Du berechnest im Ctor die Hash. Warum also berechnest Du die Hash erneut im Equals anstatt einfach "sum" zu benutzen?

3. Falscher cast:

FileInfo file2 = (FileInfo)obj;

Das gibt einen Laufzeitfehler wenn obj kein FileInfo ist. Richtig wäre:

FileInfo file2 = obj as FileInfo;

4. Du prüfst file2 in Equals nicht auf null -> Laufzeitfehler wenn es null ist.

5. Die Methode CalcMD5 macht Error-Hiding. Dies führt zu einem Laufzeitfehler in GetHashCode (NullReferenceException) falls es einen Fehler gab.

6. Du erzeugst unnötig mehrfache Instanzen von MD5 (Md5.Create())

7. Deine Operatoren prüfen ebenfalls nicht auf null -> möglicher Laufzeitfehler

Zusätzliche Minuspunkte für schlechte Naming Convention:
- Unterstich im Klassennamen
- Unterstrich am Anfang einer variablen
- Die variable vom Ctor sollte "filename" oder "filepath" heissen, nicht "file"

Ansonsten ist mir beim Durchsehen nichts aufgefallen.

boenz666

loks schrieb:

1. Du prüfst im Ctor nicht ob das File existiert bzw. zugegriffen werden kann. -> Möglicher Laufzeitfehler

Das tue ich bereits bei der Erzeugung der Liste in der Hauptklasse und muss ich dort auch tun, weil wenn das Verzeichnis dort nicht existiert würde ich einen Fehler bekommen, wenn ich in die Subverzeichnisse davon gehe. Oder sollte man das zweimal machen (beziehungsweise Zugriff erneut testen, da der Zeitpunkt leicht abweicht von der ersten Prüfung)?

loks schrieb:

6. Du erzeugst unnötig mehrfache Instanzen von MD5 (Md5.Create())

OK, ich erzeuge nun eine Instanz und verwende diese:

MD5 md5 = new MD5CryptoServiceProvider();
byte[] md5Hash = md5.ComputeHash(FileCheck);

loks schrieb:

7. Deine Operatoren prüfen ebenfalls nicht auf null -> möglicher Laufzeitfehler

Was soll ich in dem Fall machen, falls ein Wert null ist?
Ich kann ja keinen boolean zurückgeben. Also was würde man von einem Programm erwarten? Eine Exception?

loks schrieb:

Zusätzliche Minuspunkte für schlechte Naming Convention:

Unterstrich ist entfernt im Klassennamen. Das mit dem Unterstrich vor der Variable hat mir ein Ausbilder gezeigt und habe ich schon zigtausendmal im Netz gesehen. Aber ich werde es mir merken.

Dann liegt jetzt das Problem nur noch in der Verwendung des HashSets stimmts?

HashSet<ImageFile> hashset = new HashSet<ImageFile>();

foreach (ImageFile imgfile in imgfiles)
{
    if (...)
        lbDuplikate.Items.Add(imgfile.ToString());
    Application.DoEvents();
}

Ich weiß nun nicht, wie ich hier den Operator == einsetzen soll ohne die Hashset ebenfalls nochmal zu druchlaufen, was ich ja nicht mehr tun sollte/muss.