2 Dictionary zusammenfügen
Guten Tag,
Ich möchte zwei Dictionary zusammenfügen. Der Key Typ ist immer int und der Value Type immer double.
Der folgende Code macht genau was ich will, aber viel zu langsam. Dictionary 3 beinhaltet alle Keys von Dictonary 1 und 2.
// Example for Dictionary 1
Dictionary<int, double> dict1 = new Dictionary<int, double>();
dict1[0] = 12.1;
dict1[2] = 13.1;
// Example for value 1
double v1 = 2.0;
// Example for Dictionary 2
Dictionary<int, double> dict2 = new Dictionary<int, double>();
dict2[2] = 4.9;
dict2[6] = -11.8;
// Example for value 2
double v2 = -1.0;
// Init dict 3
Dictionary<int, double> dict3 = new Dictionary<int, double>();
// Merge Dictionary
foreach (int id1 in dict1.Keys)
{
double dict2_id1_v;
if (dict2.TryGetValue(id1, out dict2_id1_v))
{
dict3[id1] = dict1[id1] * v1 + dict2_id1_v * v2;
}
else
{
dict3[id1] = dict1[id1] * v1;
}
}
foreach (int id2 in dict2.Keys)
{
if (!dict3.ContainsKey(id2))
{
dict3[id2] = dict2[id2] * v2;
}
}
// Dictionary 3 should look like that for the given example
// dict3[0] = 24.2
// dict3[2] = 26.2 - 4.9 = 21.3
// dict3[6] = 11.8
Anmerkungen am Rande:
- Dictionary 1 und 2 darf nicht verändert werden.
- Jeder einzelne Dictionary (dict1 und dict2) kann bei mir mehr als 1000 Einträge haben (mit zum Teil gleichen oder auch unterschiedlichen Keys).
- Das Zusammenfügen der beiden Dictionary muss ich mehrere 1000 mal durchführen.
Fragen:
- Hat jemand eine schnelle / bessere Lösung als ich?
- Könnte man das Zusammenfügen auch mit LINQ machen? Wenn ja bitte helfen. Wäre dies schneller?
- Gibt es eine Lösung ohne Dictionary für das Problem?
Gruss Wollmich
Spontan würde ich sagen du kannst mal versuchen deine Variablen Deklarationen auserhalb der schleifen zu machen also immer die selbe Vaiabele zu verwenden also zb
double dict2_id1_v;
außerhalb der foreach zu deklariren
Wir Arbeiten eigendlich nicht wir nehmen nur das geld
Danke für den Tipp, wie blöde von mir.
Bringt aber leider nur weniger als ein Prozent mehr Performance. X(
Ich denke wirklich viel Zeit braucht dem Dictionary 3 jedesmal im Loop einen neuen Wert hinzu zu fügen. Kann man den Dictionary 3 nicht auf eine bestimmte Grösse initializieren, wie zum Beispiel bei einem Array?
Gruss Wollmich
Hallo wollmich,
Kann man den Dictionary 3 nicht auf eine bestimmte Grösse initializieren, wie zum Beispiel bei einem Array?
klar kann man, einfach über einen Parameter des Konstruktors.
Dann kannst du in
if (!dict3.ContainsKey(id2))
versuchen dict3 durch dict1 zu ersetzen, was vermutlich aber auch nicht viel bringt.
Wie sieht es denn mit den Keys aus? Welche Zahlen können da vorkommen? Wie groß ist der maximale Wert? Kann es negative Werte geben? Je nachdem wie die Antwort ausfällt, kannst du evtl. Dictionary durch ein Array bzw. zwei Arrays ersetzen.
Ansonsten sieht deine Implementierung schon ziemlich optimal aus.
herbivore
Vielen Dank, für den Tipp.
Wenn ich Dictionary 3, wie folgt initaliziere
// Init dict 3
Dictionary<int, double> dict3 = new Dictionary<int, double>(dict1.Count);
habe ich einen Performace Gewinn von ca. 25% 👍
Leider kenne ich die genaue Länge von Dictionary 3 nicht im Voraus. Sie ist aber im Minimum die von Dictionary 1 oder 2. Zuerst zu schauen, welches der beiden Eingangs Dictionary's grösser ist, kostet mehr Performance als es bringt, darum nehme ich die Länge von Dictionary 1 als Startwert.
Zu 80% und mehr haben Dictionary 1 und 2 die gleichen Keys.
versuchen dict3 durch dict1 zu ersetzen, was vermutlich aber auch nicht viel bringt.
Werde ich auch noch ausprobieren. Denke aber es wird nichts bringen.
Wie sieht es denn mit den Keys aus? Welche Zahlen können da vorkommen? Wie groß ist der maximale Wert? Kann es negative Werte geben? Je nachdem wie die Antwort ausfällt, kannst du evtl. Dictionary durch ein Array bzw. zwei Arrays ersetzen.
- Keine negative Werte
- 0 ... 2147483647 (im Regelfall aber selten über 10000)
- Wie würde die Lösung mit Arrays aussehen? Wäre das nicht eine Speicherverschwendung?
Gruss Wollmich
Hallo wollmich,
Wäre das nicht eine Speicherverschwendung?
deshalb ja die Frage nach dem maximalen Wert. 🙂
Wie würde die Lösung mit Arrays aussehen?
Das würde von den genauen Umständen abhängen, der Verteilung der Keys, der Reihenfolge, in der sie eingetragen und abgefragt werden, usw. Grundsätzlich ist die Dictionary-Lösung nicht schlecht, aber du scheint ja den letzten Rest an Performance herauskitzelen zu wollen/müssen. Und da ein Array-Zugriff per Index schneller ist als ein Dictionary-Zugriff per Key, gibt es da gewisses Optimierungspotential. Ob man dieses auch ausschöpfen kann, steht in auf einem anderen Blatt. Wenn die Keys sehr dicht liegen, könnte ein Array günstiger sein. Im einfachsten Fall würde man die Keys direkt als Array-Index verwenden.
herbivore
Hallo mollmich,
du verwendest als Keys ja Integer werte, nun ist es nicht nur möglich zu sagen ob zwei integer werte gleich sind oder nicht, sondern, da wir durch ≤ eine Halbordnung besitzen, können wir sie sogar anordnen!
Das solltest du ausnutzen
Ich weiß zwar nich, wo genau du deine Dictionarys her bekommst, aber wenn du auch darauf einfluss hast, dann geht folgendes:
ne Struktur definieren mit Int-Key und double-Value (meintewegen nimmste auch gleich KeyValuePair<int,double> )
du sorgst dafür dass deine beiden dictionarys jetzt keiner mehr sind, sondern Arrays von diesen Strukturen (Paaren von int/double) und zwar aufsteigend sortiert nach dem Key
Du "joinst" die Listen analog zum Merge-Schritt im Sortierverfahren Merge-Sort
Du gehst also beide Listen parallel durch (mit zwei indizes).
Den einen Index solange erhöhen, wie das Element aus Liste 1 kleiner ist als das aktuelle aus Liste 2.
Falls es größer wird, dann auf den andern Index springen, und den so lange erhöhen, bis das Element aus Liste 2 wieder größer ist als das aus Liste 1... usw...
so gehst du beide Listen parallel sortiert durch und kannst dabei (wenn zwei gleiche auftrete) ihre gewichtete Summe in das neue Array schreiben, bzw nur den einen Wert.
Davor müsstest du evtl quasi den selben Algo schonmal durchlaufen lassen um zu bestimmen, wie lang dein verschmolzenes Array sein muss.
Kannst natürlich auch "raten" mit (a.lenght + b.length) nur is das im Allgemeinen ja Verschwendung, weil die Listen ja gleiche Keys beinhalten können/werden.
Das ganze hat zwar auch "nur" O(n) Laufzeitkomplexität, aber darunter gehts eh nicht, also zählt nur die reale Laufzeit- und die sollte bei reinen Array-zugriffen einfach mal schnell sein.
Einzige Wermutstropfen du musst nur dafür sorgen, dass die Anfangs Listen sortiert sind. Die Ergebnisliste is ja dann auch sortiert... und wenn du dann zwei ergebnislisten wieder verknüpfst, bleiben die ja sortiert.
Also wie ich finde, ne akzeptable Forderung.
beste Grüße
zommi
ich hätte es jetzt so gleöst:
// Example for Dictionary 1
Dictionary<int, double> dict1 = new Dictionary<int, double>();
dict1[0] = 12.1;
dict1[2] = 13.1;
// Example for value 1
double v1 = 2.0;
// Example for Dictionary 2
Dictionary<int, double> dict2 = new Dictionary<int, double>();
dict2[2] = 4.9;
dict2[6] = -11.8;
// Example for value 2
double v2 = -1.0;
// Init dict 3 nachtrag: laut deiner aussage sind 80% der keys gleich
//ansonsten kann man die multiplikation auch weglassen.
int count = Convert.ToInt32(dict1.Count * 1.2);
Dictionary<int, double> dict3 = new Dictionary<int, double>(count);
// Merge Dictionary
foreach (KeyValuePair<int, double> kvp in dict1)
{
//ich habe gesehen das du beim merge, den value verdoppelst.. wenn dem so ist dann nimm keine multiplikation sondern lieber addition
dict3.Add(kvp.Key, kvp.Value + kvp.Value);
}
double temp = 0.0;
foreach (KeyValuePair<int, double> kvp in dict2)
{
temp = kvp.Value * -1.0;
if (!dict3.ContainsKey(kvp.Key))
{
dict3.Add(kvp.Key, temp);
}
else
{
dict3[kvp.Key] += temp;
}
}
Value 1 und Value 2 haben natürlich nicht nur fix den Wert 2 und -1. Dies sollten eigentlich nur Beispiele für Werte sein. Value 1 und 2 können irgendeinen double Wert haben. Werde noch probieren ob das mit Key Value Pair etwas bringt.
Zuerst möchte ich aber die Lösung mit Arrays, welche 'zommi' vorgeschlagen hat, noch aus probieren, aber nicht mehr heute. Meine Keys wären eigentlich schon sotiert, da ganz am Anfang Dictionary 1 und Dictionary 2 je maximal nur eine Element haben.
Ich werde den Code posten sobald ich ihn geschrieben und getestet habe.
Gruss Wollmich
Hallo zommi,
Bin gerade daran den Code mit den Arrays zu schreiben und frage mich was mehr Sinn macht:
Je ein Array int für die Keys und ein Array double für die Values oder deine vorgeschlagende <key, value> Pair?
Ich denke zwei Array wären schneller, oder was denkst du?
Gruss Wollmich
Hallo wollmich,
ich persönlich würde ein Array mit einer gemeinsamen Struktur verwenden.
Find ich so eine Paar-Struktur "logischer", kompakter, objektorientierter. Außerdem könnte man so relativ leicht die Funktionen von Array.***() verwenden, wie Sort, BinarySearch, etc.
Man bräuchte bloß die IComparable schnittstelle zu implementieren.sollte sogar die 1-Array-Variante schneller sein.
Du betrachtest ja zu nem festen Zeitpunkt sowohl die ints als auch die doubles mit dem selben Index.
Wenn diese nun in verschiedenen Arrays liegen, liegen die auch an ganz verschiedenen Speicheradressen im Ram.
Wenn sie als Struktur kompakt hintereinanderweg im Ram stehn, könnte ich mir vorstellen, dass es aufgrund dieser räumlichen Lokalität seltener zu einem Cache-Miss kommt.
Also die CPU eben besser cachen kann.
Wenn man diesen Aspekt außen vor lässt, sollten von den reinen Prozessorinstruktionen beide Varianten gleich schnell ablaufen.
Die zwei Arrayvariante benötigt natürlich immer 2 Array-Index-Zugriffe.
(2 Additionen und 2 Speicherzugriffe)
und die mit dem strukt benötigt eben 1 Addition und (um von int auf den double-werte zu kommen eine Inkrementation, also auch eine Addition - da die ja als Struktur direkt hintereinander gespeichert werden) und insgesamt auch 2 Speicherzugriffen.
Aber ich könnte mir vorstellen, dass wegen dem besseren caching noch etwas an Performance rauszukitzeln ist 🙂
beste Grüße
zommi
PS: (ich will bei deinem Name immer Wollmilch schreiben, wie die Eierlegende ***-Sau 😉 )
So ich habe den Code mit der Array Lösung nun mal geschrieben und aufgeteilt. Ich hoffe, dies hilft der Verständlichkeit.
Teil 1: Beispiele für meine beiden Dictionary / Arrays:
// Example for Dictionary 1
KeyValuePair<int, double>[] adict1 = new KeyValuePair<int, double>[2];
adict1[0] = new KeyValuePair<int, double>(0, 12.1);
adict1[1] = new KeyValuePair<int, double>(2, 13.1);
// Example for value 1
double v1 = 2.0;
// Example for Dictionary 2
KeyValuePair<int, double>[] adict2 = new KeyValuePair<int, double>[2];
adict2[0] = new KeyValuePair<int, double>(2, 4.9);
adict2[1] = new KeyValuePair<int, double>(6, -11.8);
// Example for value 2
double v2 = -1.0;
Teil 2: Nun die Anzahl der gemeinsamen Keys herausfinden:
// Findout numbers of keys
int i1 = 0, i2 = 0;
int n1 = adict1.Length, n2 = adict2.Length;
int n3 = 0;
int key_i1, key_i2;
for (int temp = 0; temp < (n1 + n2); n3++)
{
if ((i1 < n1) & (i2 < n2))
{
key_i1 = adict1[i1].Key;
key_i2 = adict2[i2].Key;
if (key_i1 == key_i2)
{
i1++; i2++; temp++; temp++;
}
else
{
if (key_i1 < key_i2)
{
i1++; temp++;
}
else
{
i2++; temp++;
}
}
}
else
{
temp++;
}
}
Teil 3: Die beiden Arrays zusammenfügen:
// Init dict 3
KeyValuePair<int, double>[] adict3 = new KeyValuePair<int, double>[n3];
// Merge Dictionary
i1 = 0; i2 = 0;
KeyValuePair<int, double> kvp_i1, kvp_i2;
for (int i3 = 0; i3 < n3; i3++)
{
if (i1 < n1)
{
kvp_i1 = adict1[i1];
if (i2 < n2)
{
kvp_i2 = adict2[i2];
if (kvp_i1.Key == kvp_i2.Key)
{
adict3[i3] = new KeyValuePair<int, double>(kvp_i1.Key, kvp_i1.Value * v1 + kvp_i2.Value * v2);
i1++; i2++;
}
else
{
if (kvp_i1.Key < kvp_i2.Key)
{
adict3[i3] = new KeyValuePair<int, double>(kvp_i1.Key, kvp_i1.Value * v1);
i1++;
}
else
{
adict3[i3] = new KeyValuePair<int, double>(kvp_i2.Key, kvp_i2.Value * v2);
i2++;
}
}
}
else
{
adict3[i3] = new KeyValuePair<int, double>(kvp_i1.Key, kvp_i1.Value * v1);
i1++;
}
}
else
{
kvp_i2 = adict2[i2];
adict3[i3] = new KeyValuePair<int, double>(kvp_i2.Key, kvp_i2.Value * v2);
i2++;
}
}
Und habe nun ein paar Fragen:
- Geht das irgendwie mit weniger Zeilen? Was vorher mit ca. 50 Zeilen ging braucht jetzt fast 90.
- Mich stören die vielen ineinander verschachtelten if Abfragen vorallem in Teil 3. Sind aber nach meiner Meinung nach alle nötig.
- Gibt es eine bessere Möglichkeit die Anzahl der Keys (n3) in Teil 2 raus zu finden?
Gruss Wollmich
PS: Zu meinen Namen. War mein erster Benutzername auf einem Computer Netzwerk (Novell ca. 1994). Damals gab es noch Namensbeschränkungen (DOS 8.3 Zeichen). Die ersten vier Buchstaben sind der Anfang meines Nachnamens und die nächsten vier die meines Vornamens, welcher im übrigen Michael ist.
Hallo wollmich,
- Geht das irgendwie mit weniger Zeilen? Was vorher mit ca. 50 Zeilen ging braucht jetzt fast 90.
- Mich stören die vielen ineinander verschachtelten if Abfragen vorallem in Teil 3. Sind aber nach meiner Meinung nach alle nötig.
ist doch nichts ungewöhnliches, dass geschwindigkeitsoptimierter Code (wesentlich) länger bzw. komplizierter ist.
Gibt es eine bessere Möglichkeit die Anzahl der Keys (n3) in Teil 2 raus zu finden?
int n3 = n1 + n2; // speed vs. space
herbivore
Das Wichtigste habe ich ja ganz vergessen bei meinem Array Code:
Der Code mit Arrays läuft ca. 90% schneller als der ursprüngliche Code mit Dictionarys (ohne init). 😁
Now we're talking ... 8)
Wenn ich meinen Code nochmals um den Faktor 10 beschleunigen könnte ...
Vielen Dank an alle für die Mithilfe.
Weitere Verbesserungsvorschläge sind jederzeit willkommen.
Gruss Wollmich
Hallo Wollmilch,
ich hab einen kleinen Test durchgeführt und bin drauf gekommen, dass du mit einem Struct Array noch ein kleines bisschen mehr Zeit sparen könntest 🙂
Hier das Hilfs-Struct:
public struct KeyValueStruct<T, K>
{
public T Key;
public K Value;
}
und hier der Code mit dem ich verglichen habe:
int size = 10000000;
var watch = Stopwatch.StartNew();
KeyValueStruct<int, double>[] array = new KeyValueStruct<int, double>[size];
for (int i = 0; i < size; i++)
{
array[i].Key = i;
array[i].Value = i * 0.5;
}
watch.Stop();
Console.WriteLine("Time for struct array: " + watch.Elapsed);
watch = Stopwatch.StartNew();
KeyValuePair<int, double>[] array2 = new KeyValuePair<int, double>[size];
for (int i = 0; i < size; i++)
{
array2[i] = new KeyValuePair<int, double>(i, i * 0.5);
}
watch.Stop();
Console.WriteLine("Time for class array: " + watch.Elapsed);
Lg XXX
Danke für den Tipp
In meiner Anwendung habe ich es mit zwei Arrays gelöst. Der weiter oben gepostete Code ist nur ein Beispiel mit <key, value> Pair. Ich weiss, das ist nicht sehr schön (sorry zommie), aber ich habe meine Gründe. Es kann in meiner Anwendung vorkommen, dass ich nur ein 'Dictionary' (nur dict 1 und kein dict 2) habe und nur die Values mit einem Wert (v1) multiplizieren muss. Habe ich nun seperate Arrays, kann ich das ganze Key Array auf einmal meinem neuen 'Dictionary' (dict 3) zuweisen. Ich denke, dies ist schneller. Keine Kopie der einzelnen Elemente im Key Array.
Die Lösung mit zwei Arrays ist praktisch gleich schnell wie die mit der Struct.
int[] keys = new int[size];
double[] values = new double[size];
for (int i = 0; i < size; i++)
{
keys[i] = i;
values[i] = i * 0.5;
}
Ich habe da noch eine 'klitze kleine' Frage. Ist mir schon fast etwas peinlich ....
Wie funktioniert die Stopwatch? Sorry Off Topic.
using System.Diagnostic;
...
var watch = Stopwatch.StartNew();
Wieso kann ich das nicht compilieren? Könnte es daran liegen, dass ich auf meinen Laptop nur die Express Edition von Visual Studio 2008 habe?
Gruss Wollmich
Hallo wollmich,
beachte [Hinweis] Wie poste ich richtig? Punkt 1.2. Deshalb nur in aller Kürze: Express oder nicht, spielt keine Rolle, aber du musst .NET 3.5 verwenden.
herbivore
Hi, ich habe dein Problem mal versucht mit Linq zu lösen,
ob dies schneller ist, weiß ich jedoch nicht.
Vielleicht kannst du's ja mal testen und bescheid geben
Dictionary<int, double> dict1 = new Dictionary<int, double>();
dict1[0] = 12.1;
dict1[2] = 13.1;
// Example for value 1
double v1 = 2.0;
// Example for Dictionary 2
Dictionary<int, double> dict2 = new Dictionary<int, double>();
dict2[2] = 4.9;
dict2[6] = -11.8;
// Example for value 2
double v2 = -1.0;
// Init dict 3
Dictionary<int, double> dict3 = new Dictionary<int, double>();
// Merge Dictionary
IEnumerable<KeyValuePair<int, double>> result =
from id1 in dict1.Keys
select dict2.ContainsKey(id1) ? new KeyValuePair<int, double>(id1, dict1[id1] * v1 + dict2[id1] * v2) :
new KeyValuePair<int, double>(id1, dict1[id1] * v1);
dict3.Concat(result);
result =
from id2 in dict2.Keys
where !dict3.ContainsKey(id2)
select new KeyValuePair<int, double>(id2, dict2[id2] * v2);
dict3.Concat(result);
Vielen Dank auch für diese LINQ Lösung,
Ich habe da aber ein Problem:
System.Console.WriteLine("result.Count {0}", result.Count());
dict3.Concat(result);
System.Console.WriteLine("dict3.Count {0}", dict3.Count);
Bei der ersten from select Abfrage sollte dict3 genau soviel Elemente wie result haben. dict3.Count ist aber immer 0. Das result stimmt, aber aus dict3.Concat(result) funktioniert nicht wie es sollte.
foreach (KeyValuePair<int, double> temp in result)
dict3[temp.Key] = temp.Value;
Mache ich folgendes funktioniert es wie es sollte. Gibt aber natürlich (ein unnötiger Loop) eine ca 50% schlechtere Performance als die ursprünglich publizierte Lösung.
Wieso geht Concat nicht?
Gruss Wollmich
Weil Concat nicht auf die collection angewendet wird sondern eine neue erzeugt, welche dann zurückgegeben wird.
Lg XXX
Hallo,
In meiner Anwendung habe ich es mit zwei Arrays gelöst. Der weiter oben gepostete Code ist nur ein Beispiel mit <key, value> Pair. Ich weiss, das ist nicht sehr schön (sorry zommie), aber ich habe meine Gründe. Es kann in meiner Anwendung vorkommen, dass ich nur ein 'Dictionary' (nur dict 1 und kein dict 2) habe und nur die Values mit einem Wert (v1) multiplizieren muss. Habe ich nun seperate Arrays, kann ich das ganze Key Array auf einmal meinem neuen 'Dictionary' (dict 3) zuweisen. Ich denke, dies ist schneller. Keine Kopie der einzelnen Elemente im Key Array.
Also böse bin ich dir wohl kaum 😁
Dennoch versteh ich dein Argument nicht,
dann auch ein Array aus Structs kannst du komplett kopieren.
(beispielsweise mit Array.Copy(...))
Und danach kannst du dieses neue Array durchgehen und an jeder Position den Value des Struct **dict3_.value *= v1;[/b] verändern.
Sollte dann wieder gleich schnell sein 😉
Aber wir auch immer, im Prinzip sollte beides gleich schnell sein.
Nimm einfach das, was bei dir besser rein passt.
Mich würde dann mal der komplette Code interessieren.
(Zumindest von den beiden Hauptschleifen, die dann die Arrays verschmelzen)
Die oben publizierste ist ja anscheinend mit Structs, die du nun nich verwendest.
Vielleicht gibts noch was am Code zu optimieren 😉
beste Grüße
zommi