Autor Beitrag
georgeboy
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Fr 18.12.20 08:39 
Hallo zusammen, ein Problem: Ich arbeite mit Dictionary<TKey, TValue>. Als TKey möchte in int[], und als TValue int nehmen.

ausblenden C#-Quelltext
1:
2:
3:
4:
Dictionary<int[], int> dict = new Dictionary<int[], int>(); 
dict.Add(new int[] { 2457 }, 10);
dict.Add(new int[] { 7892 }, 20);
dict.ContainsKey(new int[] { 2457 }) // ergibt false !


Klar weil ArrayTyp ein Verweistyp ist. Da gib es noch die Eigenschaft Comparer, komme da aber nicht zurecht. Könntet Ihr mir mal eine kurze Lösung geben ? Meine erste Lösung wäre die kurzen Arrays ( Länge < 30 ) in Strings zu verwandeln, und als TKey String nehmen, aber unschön ! Wäre schön ..


Moderiert von user profile iconTh69: Topic aus WinForms verschoben am Fr 18.12.2020 um 09:09
Moderiert von user profile iconTh69: C#-Tags hinzugefügt
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 4366
Erhaltene Danke: 940

Win10
C#, C++ (VS 2015/17/19)
BeitragVerfasst: Fr 18.12.20 09:24 
Dann schau dir mal das Beispiel zum IEqualityComparer<T> an. Du kannst dann als Implementierung von Equals die Methode SequenceEquals benutzen: C# SequenceEqual Method bzw. How to compare two arrays in C# if they are Equal or Not.
Von der eigenen Comparer-Klasse erzeugst du dann eine Instanz und übergibst sie dem Dictionary-Objekt als Konstruktor Parameter.

PS: Dies gilt aber nur für Arrays, die in der Reihenfolge auch übereinstimmen (also {2457} wäre ungleich {7542} usw.).
Ralf Jansen
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4507
Erhaltene Danke: 929


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: Fr 18.12.20 12:35 
Könntest du kurz erklären wozu genau? Dann kann ich zumindest beurteilen ob ein Dictionary überhaupt die richtige Wahl ist.
georgeboy Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Fr 18.12.20 12:52 
Ich habe eine grosse Menge von kleinen Arrays ( Länge < 30 ), in einem grossen Array ( Länge über 10^6 ), die verzeigert sind, das heisst wenn ich ein kleines Array habe und daraus eine neues bilde, möchte ich seinen Index vom neuen ( im grossen Array ) schnell berechnen. Möglichst mit Hash-Technik.
Ralf Jansen
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4507
Erhaltene Danke: 929


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: Fr 18.12.20 13:04 
OK. Die kleinen Arrays im Dictionary sind konstant und die Reihenfolge in den Arrays ist relevant?

Dann könnte ein Dictionary funktionieren. Würde dann aber vermutlich eine eigene Klasse erstellen die ein Array ist oder eins enthält und dort die entsprechenden Equality und Hash Methoden implementieren die das Dictionary benötigt und diese dann als Key verwenden.
georgeboy Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Fr 18.12.20 13:06 
Wie man Equals einbaut ist klar, aber GetHashCode? Wozu? Dictionary hat doch eine eigene Hash-Funktion! Oder muss man diese von Fall zu Fall selber bauen? Ich möchte IEqualityComparer<int[]> verwenden.

Moderiert von user profile iconTh69: C#-Tags hinzugefügt
Moderiert von user profile iconTh69: Plenks entfernt.
Ralf Jansen
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4507
Erhaltene Danke: 929


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: Fr 18.12.20 13:45 
Dictionary hat keine Hashfunktion für Keys. Die muss der Key schon mitbringen oder sie wird eben extra extern implementiert.
Du hast gesehen das IEqualityComparer auch verlangt dort GetHashcode zu implementieren? Das ist der für den Key wenn der Key das nicht selbst richtig macht (was in deinem Fall das Problem ist da du bei Arrays halt die Speicheradresse als Hashcode bekommst).
georgeboy Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Fr 18.12.20 13:54 
Wie könnte ich die Funktion GetHashCode(), für den TKey: int[] überschreiben? Die Quersumme kann es nicht sein, wegen Quersumme(new int[] { 123 }) == Quersumme(new int[] { 132 }). Am besten aus new int[] { 567,8 } den String: "5678" machen und den TKey als String!

Moderiert von user profile iconTh69: C#-Tags hinzugefügt
georgeboy Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Fr 18.12.20 14:54 
Quersumme & 0xFF geht doch, die Kollisionsauflösung musste Dictionary selber machen, Sorry ... Schöne Weihnachten und bleibt gesund ! Danke !
Ralf Jansen
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4507
Erhaltene Danke: 929


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: Fr 18.12.20 15:30 
Die Kollisionsauflösung wäre die Implementierung von Equals ;)

Erst wenn der Hash gleich ist zieht Equals (denn mit Hashes kann man nur Ungleichheit feststellen aber nicht Gleichheit). Du könntest auch in GetHashCode immer eine Konstante liefern so das immer Equals aufgerufen. Das funktioniert ist halt nur langsam. Umso besser GetHashcode(streuender) implementiert wird umso schneller das Dictionary.
georgeboy Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Fr 18.12.20 17:48 
Ich habe es getestet mit Dictionary<int[], int>. Hat funktioniert! Danke!

ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
public class EqKlasse : IEqualityComparer<int[]>
    {
        public bool Equals(int[] b1, int[] b2)
        {
            if (b1.Length != b2.Length) return false;
            bool gleich = true;
            for (int i = 0; i < b1.Length; i++)
                if (b1[i] != b2[i]) gleich = false;
            return gleich;
        }

        public int GetHashCode(int[] bx)
        {
            int HashCode = 0;
            for (int i = 0; i < bx.Length; i++)
                HashCode += bx[i];
            return HashCode & 0xFF;
            
        }
    }


Moderiert von user profile iconTh69: C#-Tags hinzugefügt
Ralf Jansen
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4507
Erhaltene Danke: 929


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: Fr 18.12.20 18:17 
Das mit dem 0xFF verstehe ich nicht. Warum nur 1 Byte für den Hash verwenden und sich auf 256 verschiedene Hashwerte begrenzen?

In aktuellen Frameworks (Net Core 3 oder Net 5) könnte man die HashCode Klasse nutzen.

ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
public int GetHashCode(int[] bx)
{
    var hash = new HashCode();
    foreach (var value in bx)
        hash.Add(value);
    return hash.ToHashCode();
}
georgeboy Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Fr 18.12.20 18:24 
Das war nur bei meinem Beispiel-Programm auf 0xFF gesetzt. Ich arbeite mit VS2008 und VS2019. Gib es für VS2008 eine bessere Hash-Funktion ? Für Arrays der Länge 30 ?
Ralf Jansen
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4507
Erhaltene Danke: 929


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: Fr 18.12.20 18:39 
Für ältere Frameworks gibt es andere "Magie" ;)
Scheinbar haben Arrays schon eine gute GetHashCode Methode implementiert. Sie ist nur hinter dem explizit implementierten IStructuralEquatable Interface versteckt.

ausblenden C#-Quelltext
1:
2:
3:
4:
public static int GetHashCode(int[] bx)
{
    return ((IStructuralEquatable)bx).GetHashCode(EqualityComparer<int>.Default);
}
georgeboy Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Sa 19.12.20 07:14 
Muss ich noch studieren ...
georgeboy Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Sa 19.12.20 16:21 
Ergibt die Hashfunktion bei Dictionary<stringint> für Stringpermutationen den selben Wert? Möchte die Hashfunktion für Dictionaray<int[], int> gerne selber schreiben. Die Quersumme ist nicht geeignet, meine Arrays sind oft gleiche Folgen von Zahlen, mit Nullen dazwischen! Habe noch keine Idee. IStructuralEquatable muss ein Verweis eingebunden werden: System.Collections; - C# meckert trotzdem.

Moderiert von user profile iconTh69: C#-Tags hinzugefügt
georgeboy Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Sa 19.12.20 16:57 
Folgende Idee:

ausblenden C#-Quelltext
1:
2:
3:
4:
5:
6:
7:
public int GetHashCode(int[] bx)
        {
            int HashCode = 0;
            for (int i = 0; i < bx.Length; i++) // bx.Length <= 20 
                HashCode += bx[i] << i;
            return HashCode & 0xFFFFFF;
        }


Kann man bei Dictionary für den Hashfunktionswert-Typ anstelle "int" auch "long" nehmen ? Geht bei Dictionary<stringint> die Quersumme in die Hashfunktion ein ? Ist der Hashfunktionswert von "1234" gleich "1324" ?
Th69
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Moderator
Beiträge: 4366
Erhaltene Danke: 940

Win10
C#, C++ (VS 2015/17/19)
BeitragVerfasst: Sa 19.12.20 17:19 
Die Hash-Funktion sollte nicht zu performancelastig sein (im Vergleich zur Equals-Methode). Sie dient nur als schneller Vorvergleich, um nicht jedesmal die Equals-Methode aufzurufen.
M.E. ist deine bisherige Hash-Funktion nicht so toll, da du dort das ganze Array durchläufst (was dann bei der Equals-Methode noch mal passiert).
Was du aber sicherstellen mußt, ist, daß deine Hash-Funktion bei als gleich anzusehenden Werten auch denselben Hashwert erzeugt (d.h. wenn du in der Equals-Methode z.B. auch Permutationen als gleich ansiehst, so muß auch schon die Hashfunktion dies berücksichtigen).
georgeboy Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 103



BeitragVerfasst: Sa 19.12.20 17:34 
Ja das sehe ich ein, "Equals" müsste bei einer Ungleichheit am Index i, sofort abbrechen. Aber bei der Hash-Funktion muss doch das ganze Array durchlaufen werden, sonst gibt es ja viel zu viele Kollisionen, oder verstehe ich da was nicht richtig. Meine Arrays sind Folgen von Zahlen mit Nullen dazwischen, immer in der gleichen Reihenfolge ( Es können Zahlen gelöscht sein aber es gibt keine Permutationen ). Das mit den Permutationen interessiert mich nur für Dictionary<stringint>.
Ralf Jansen
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4507
Erhaltene Danke: 929


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: Sa 19.12.20 20:56 
Zitat:
Das mit den Permutationen interessiert mich nur für Dictionary<string, int>.


Das ist kein Hexenwerk und kannst du doch einfach ausprobieren? Ruf von ein paar strings die du vergleichen willst einfach GetHashCode auf und gib denn z.B. auf der Konsole aus. Der Aufwand misst sich nicht mal in Minuten.

Zitat:
Aber bei der Hash-Funktion muss doch das ganze Array durchlaufen werden, sonst gibt es ja viel zu viele Kollisionen, oder verstehe ich da was nicht richtig


Zuviel ist aber relativ wieviel ist zu viel? Ich hatte absichtlich die vorhandene Implementierung in der Array Klasse verlinkt. Dort hat man sich dazu entschiedenen sich maximal die letzten 8 Elemente in einem Array anzuschauen und aus diesen den Hash zu generieren.
Denn Entwicklern war das scheinbar ausreichend für die meisten Fälle. Ich vermute mal in deinem Fall ist es kein Problem auch über alle zu iterieren. Aber im Zweifel ist ja genug Raum, wenn man eine Beschleunigung benötigt, an der Anzahl der betrachteten Arrayelemente zu schrauben.