Dictionary verbesserungsfähig?

13/08/2009 - 19:08 von Jens Duczmal | Report spam
Guten Abend zusammen,

ich habe da ein paar ganz einfache Zeilen Quellcode
von denen ich mir eigentlich sicher bin, das die so gut sind.
Trotzdem würde ich das gerne nochmal von Euch verifizieren lassen.

Ich habe ein IEnumerable<Student> von Studenten (Daten.Studenten).
Und es soll am Bildschirm ausgegeben werden, wie viele Studenten
jeweils aus welchem Ort kommen.

Was Besseres als dies mit einem Dictionary zu lösen, viel mir nicht ein.

public void Iteration(){
Dictionary<String, int> result = new Dictionary<String, int>();
foreach (var s in Daten.Studenten) {
if (!result.ContainsKey(s.Ort))
result.Add(s.Ort, 1);
else
result[s.Ort]++;
}

foreach (var s in result)
Console.WriteLine(s.Key + " " + s.Value.ToString());
}


Der Grund für meine merkwürdige Frage ist folgender:

Ich arbeite im Rahmen einer Abschlusarbeit an einem Vergleich
zwischen normalen Iterationen und LINQ.

LINQ ist bekanntlich mind. um den Faktor 2 langsamer.
Bis auf dieses Beispiel. Hier ist LINQ etwa 2 mal schneller
und wenn ich ein SortedDictionary nehme, fàllt der Unterschied
noch weeeeit größer aus.

Das macht mich halt stutzig und daher vermute ich einen ganz
üblen Anfàngerfehler im Code oben. So recht mag ich aber nicht daran
glauben :)

Danke schonmal im voraus.
LG,
Jens
 

Lesen sie die antworten

#1 Michael v. Fondern
15/08/2009 - 09:13 | Warnen spam
Hallo Jens,
Ich habe ein IEnumerable<Student> von Studenten (Daten.Studenten).
Und es soll am Bildschirm ausgegeben werden, wie viele Studenten
jeweils aus welchem Ort kommen.

Was Besseres als dies mit einem Dictionary zu lösen, viel mir nicht ein.

public void Iteration(){
Dictionary<String, int> result = new Dictionary<String, int>();
foreach (var s in Daten.Studenten) {
if (!result.ContainsKey(s.Ort))
result.Add(s.Ort, 1);
else
result[s.Ort]++;
}

foreach (var s in result)
Console.WriteLine(s.Key + " " + s.Value.ToString());
}




ich weiss zwar nicht, was intern bei der LINQ-Abfrage passiert. Ich habe
aber früher gelegentlich Dictionaries in C++ selber gebaut, so dass
ich hier eine Vermutung habe, was da passiert. Das Problem, dass ich
sehe, ist, dass bei dem obigen Code pro Iteration die interne
Hashfunktion für den String "s.Ort" zweimal oder sogar dreimal berechnet
wird.

- immer bei result.ContainsKey(s.Ort)
- dann entweder einmal bei "result.Add(s.Ort, 1)"
- oder sogar zweimal bei "result[s.Ort]++", denn das ist nur eine
Abkürzung für "result[s.Ort] = result[s.Ort] + 1"

Die Hashfunktion wird dann ausschlaggebend für die Laufzeit, wenn die
Strings eine gewisse Lànge haben, es kommt also sehr wohl auf die
konkreten Daten an!

Man kann das mit dem Standard-Dictionary auf "zweimal hashen" reduzieren:

int v;
if(!result.TryGetValue(s.Ort, out v))
result.Add(s.Ort, 1);
else
result[s.Ort]=v+1;

Noch schneller würde es aber gehen, wenn die Hashfunktion nur einmal
berechnet werden müsste, was ja eigentlich reichen sollte, schließlich
àndert sich s.Ort nicht. Dafür müsste aber das Dictionary eine Methode
in seiner API haben, die es meines Wissens nicht hat, nàmlich eine Art
"TryGetOrAddValue(key, out getValue, addValue)". Vielleicht arbeitet ja
die LINQ-Implementierung so, aber das ist natürlich reine Spekulation
meinerseits.

Grüße

- Michael -

Ähnliche fragen