Laden...

Add() von SortedList<string, Object> ab 100.000 Einträge extrem langsam?

Erstellt von Taki Haki vor 13 Jahren Letzter Beitrag vor 13 Jahren 2.781 Views
Taki Haki Themenstarter:in
168 Beiträge seit 2005
vor 13 Jahren
Add() von SortedList<string, Object> ab 100.000 Einträge extrem langsam?

Hallo,

vielleicht kann mir jemand für mein Problem bzw. das Verhalten eine plausible Antwort geben.

Ich habe eine SortedList<string, Object> und fülle die Liste in einer Schleife.

Ab ca. 100.000 Einträge bricht die Performance der SortedList extrem ein. Wenn der Key vom Typ int ist die SortedList auch ab 100.000 Einträgen nicht recht schnell.

Mein Code

            int count = 100000;

            SortedList<string, MyObject> list1 = new SortedList<string, MyObject>();
            for (int i = 0; i < count; i++)
                list1.Add(i.ToString(), new MyObject(i, i.ToString()));

Daten von ein paar Testläufen
===================
25.000 Einträge = 349ms
50.000 Einträge = 774ms
75.000 Einträge = 1134ms
100.00 Einträge = 1323ms
110.00 Einträge = 4257ms
120.00 Einträge = 6919ms
...
200.00 Einträge = ~32000ms

Bis 100.000 verhält sich die Liste noch recht linear aber danach bricht sie dann zusammen was die Performance angeht. Das ganze passiert auch nur bei string-keys.

Kann mir jemand das Verhalten erklären? Liegt das ganze an der internen Struktur?

mfg Taki

1.361 Beiträge seit 2007
vor 13 Jahren

Hi,

hast du mal nen Vergleich mit SortedDictionary<string, Object> gemacht?

Liegt das ganze an der internen Struktur? Vielleicht verrät der .NET Reflector ja etwas.

beste Grüße
zommi

U
282 Beiträge seit 2008
vor 13 Jahren

Naja, in der Doku von Sorted Liste steht:

SortedList wird als ein Array von Schlüssel-Wert-Paaren implementiert, das anhand des Schlüssels sortiert wird. Jedes Element kann als KeyValuePair-Objekt abgerufen werden

Also muss der vermutlich jedes mal, wenn du was in der Mitte einfügst, den hinteren teil des Arrays (oder gar alles) umkopieren. Unschön....

Ich denke, für deinen Code is Sorted Dictionary besser geeignet. Oder du packst (weil sorted list glaub ich schneller bei späteren abfragen ist) alles in ein normales Dictionary und steckst da in den Konstruktor der sorted list.

Taki Haki Themenstarter:in
168 Beiträge seit 2005
vor 13 Jahren

Hi,

danke für die Hinweise!

Das Problem mit dem umkopieren beim Einfügen und Entfernen in eine SortedList habe ich nach ein wenig Recherche auch im Netz gefunden 😁

Den Link Time complexity overview: Dictionary classes kann ich nur empfehlen.

Werde zukünftig statt der SortedList das SortedDictionary benutzen und ansonsten das Dictionary. Für mein Programm reicht mir sogar das Dictionary, was einen riesen boost gebracht hat.

Von 5mins auf 30sec 😁

U
282 Beiträge seit 2008
vor 13 Jahren

Dann noch als Hinweis zu dem Dictionary: Initialisier es direkt mit der richtigen größe, das bringt nochmal Performance.

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Uwe81,

die Größe anzugeben bringt im Schnitt nicht mehr als Faktor 2. Da hier die Laufzeit noch ca. 30sec beträgt, könnte es schon ein bisschen was bringen.

Normalerweise bringen konstante Faktoren in der Praxis aber keinen spürbaren Effekt, erst recht nicht, wenn sie so niedrig sind. Konstante Faktoren ändern nichts an der Aufwandklasse.

Im Vergleich mit der hier erfolgten Reduzierung der Aufwandsklasse von O(n^2) auf O(n) kann man konstane Faktoren normalerweise vernachlässigen.

herbivore

U
282 Beiträge seit 2008
vor 13 Jahren

die Größe anzugeben bringt im Schnitt nicht mehr als Faktor 2

Klar, aber ich sehe nicht, wie man hier bei einem normalen Dictionary noch die Performance erhöhen will. Darum war ja auch der erste Tipp, eben von der Sorted Lit zu einem Sorted Dictionary oder alles auf einmal zu befüllen....

Normalerweise bringen konstante Faktoren in der Praxis aber keinen spürbaren Effekt, erst recht nicht, wenn sie so niedrig sind.

Naja, die ganze Geschichte mit Parallelisierung bringen auf normalen PCs i.d.r. nur maximal einen Faktor 2 bis 8. Und wird dennoch vorangetrieben.
Ich habe eher die Erfahrung gemacht, das an kritischen Stellen (nach Profiling) über Tuning eben doch noch einiges zu erreichen ist. Wenn bei einem Algorithmus in dem Teil, der 90% der Laufzeit ausmacht, noch ein Faktor 4 drin steckt , ist es eben doch spürbar (läuft der Algo in der Mittagspause oder den ganzen Vormittag über)...

Erinnert mich an meine Diplomarbeit. Ich habe einen Algorithmus mit Linearer Laufzeit, dummerweise war die multiplikative Konstante 10^150000000000... Irgendwie war der nicht effizient.

Aber du hast schon recht. Erstmal sollte man saubere Algorithmen bzw. Datenstrukturen verwenden, dann sich - wenn nötig - um die Konstanten Faktoren kümmern.

A
69 Beiträge seit 2010
vor 13 Jahren

Du verwendest hier eine SortedList für massives hinzufügen unsortierter Daten. Warum unsortiert? Weil strings eine andere Sortierung haben als reine Integers. Da du den integer hochzählst und zum string machst, erreichst du eine unsortierte reihenfolge. z.B würde die liste für 10, 11, 12, 101, 111 so aussehen:

10
101
11
111
12

Die SortedList hat aber ein großes Problem beim hinzufügen von unsortierten Daten. Siehe: [Übersicht] .NET Framework 2.X Auflistungen (Collections) punkt 9

Alternativ gilt für unsortierten daten: [Übersicht] .NET Framework 2.X Auflistungen (Collections) punkt 8

3.971 Beiträge seit 2006
vor 13 Jahren

SortedList (und auch SortedDictionary) macht nur Sinn, wenn ich Daten zum Beispiel aus einer Benutzereingabe heraus hinzufüge und die Daten anschließend wieder sortiert ausgeben lassen möchte

Wenn ich eine unsortierte Liste sortieren möchte, nutze ich List.Sort oder Array.Sort. So hab ich das Sortieren nur einmal und nicht n-mal.

Es gibt 3 Arten von Menschen, die die bis 3 zählen können und die, die es nicht können...

A
69 Beiträge seit 2010
vor 13 Jahren

SortedList (und auch SortedDictionary) macht nur Sinn, wenn ich Daten zum Beispiel aus einer Benutzereingabe heraus hinzufüge und die Daten anschließend wieder sortiert ausgeben lassen möchte

Genau dann, amcht SortedList keinen sinn. Denn genau dann verwendet man lieber eine List und ruft vor der ausgabe List.Sort auf.

SortedList macht genau dann sinn, wenn die Auflistung immer und zu jeder Zeit Sortiert sein muss. Unabhängig davon wann und wie Elemente hinzugefügt/entfernt werden. Zugegeben, diese Anforderung hat man nciht oft aber wenn, dann ist es gut, das es diese Auflistungsform gibt.

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo ihr beiden,

es muss einem gar nicht auf die Sortierung ankommen, um SortedList zu verwenden. Die Frage, ob die Einträge einer Liste sortiert ist, hat ja schon alleine darauf Einfluss, wie schnell die verschiedenen Operationen auf der Liste ausgeführt werden können. Wenn man also selten einfügt, aber oft nach Einträgen sucht, kann eine SortedList sinnvoll sein, selbst wenn man die Liste alles ganzes nie sortiert braucht.

Insofern ist die Wahl der passenden Collection mehr eine Frage der Operationen, die man darauf ausführen will. Deshalb ist aus meiner Sicht die Tabelle aus dem Link, den Taki Haki gepostet hat, das eigentliche Entscheidungskriterium:

Den Link
>
kann ich nur empfehlen.

herbivore