Performance von InMemory-Operationen steigern

Hallo zusammen,

nehmen wir an, ich habe eine Liste von Elementen mit mehreren Integer und String Properties.
Die Liste liegt im Speicher und ich möchte nun auf diese Liste sehr performant Operationen durchführen (z.B. sortieren nach einer Property, oder nach einer Property filtern).

In der Datenbank würde mir bei diesen Operationen ein Index helfen. Den Index-Zugriff kann ich in c# auch nachbauen, indem ich die Liste sortiere, die Grenzen meiner Where Bedingung durch binäre Suche ermitteln und dann mit einer for-Schleife die Elemente auslesen.

Meine Frage ist nun, ob es hierfür im Framework schon irgendetwas vorgefertigtest gibt, sozusagen eine Indizierte Liste, oder etwas ähnliches?

Hallo Christoph K.,

Den Index-Zugriff kann ich in c# auch nachbauen,

Geht, aber mit passenden Baum-Strukturen.

Generell ist der Datentyp einer der wichtigsten Faktoren für gute Leistung, da so die Aufwandsklasse gesenkt werden kann.

im Framework schon irgendetwas vorgefertigtest gibt, sozusagen eine Indizierte Liste, oder etwas ähnliches?

In System.Collections.Generic stecken schon ein paar Klassen drin, wie SortedList<T>, SortedDictionary<K,V>, usw. Betrachte aber immer auch die Aufwandsklasse für die Operationen, welche du zu verwenden versuchst. O(1) ist besser als O(log n) und das ist besser als O(n) od. O(n²).

mfG Gü

@Christoph K.
Wie gfoidl schon schreibt gibt es die Sorted Klassen.
Hier wäre aber z.B. die Frage ob du die Daten immer sortiert brauchst.
Ist dies der Fall sind diese Klassen für dich der beste Ansatz.
Wenn du aber nur z.B. in bestimmten Situationen die Daten sortieren musst, kannst du dir eine Sort Methode schreiben und diese auf die Liste anwenden bzw. direkt Sort mit anonymen Delegate aufrufen.

T-Virus

Wie muss ich die SortedList denn ansprechen, dass sie mir die Performance-Vorteile bringt?

Im Moment habe ich es mit folgendem Code Probiert:

var items2 = sortedList.Where(x => x.Key > 100000 && x.Key < 100000 * 3).ToList();

Das dauert ungefährt 3mal so lang, als wenn ich eine normale Liste nehme 😕 ?

@Christoph K.
Wenn du nur die Daten filtern willst, dann wird dir Sorted Liste keine Vorteile bringen, da diese "nur" die Reihenfolge der Elemente durch eine entsprechende Sortierung garantiert.
Deine Where Abfrage muss am Ende durch alle Elemente durchlaufen, was du ja nicht willst.
Hier wäre es fast Ratsam eine eigene Filtermethode mit einer For Schleife zu programmieren, die dann selbst abbricht wenn der gesuchte Bereich überschritten wird.
Where und andere Methoden laufen i.d.R. über die gesamte Liste, was bei Liste mit definierten Bereichen teilweise verbrannte Zeit ist.

Entsprechend bau dir lieber auf eine Methode die deine Logik abbildet aber beim überschreiten deiner Werte abbricht.
Das spart dir bei großen Listen und häufigen Suchen viel Zeit.
Vielleicht hat jemand noch einen besseren Ansatz.

Gäbe es den eine Möglichkeit, die Daten schon vor dem speichern in Listen zu teilen.
Und zwar so, dass du deine Daten schon aufgeteilt in die Wertebereiche hast?
Dann kannst du dir Sortieren und Filtern sparen.

T-Virus

Hi,
* das Sortieren is nur dann sinnvoll wenn du mehrmals Elemente in dieser Liste suchen musst. Wenn du nur einmal Werte aus der Liste lesen willst ist ein Linq.Where schneller da das Sortieren entfällt.
* bei einer SortedList könntest du den Index des ersten Elementes geben lassen der den Kriterien entspricht und den Index des ersten der den Kriterient nicht mehr entspricht (der erste der größer ist als der Suchbereich). Dann kannst du zwischen den beiden Indizies iterieren.

Hallo Christoph K.,

dass sie mir die Performance-Vorteile bringt?

Hast du dazu auch in der :rtfm: nachgeschaut? Dort steht (wenn ich mich recht erinnere) klar drinnen, dass es kein Allheilmittel ist -- und indirekt dass es für deinen Fall eh nicht geeignet ist. Doku lesen lohnt sich 😉

Gäbe es den eine Möglichkeit, die Daten schon vor dem speichern in Listen zu teilen.
Und zwar so, dass du deine Daten schon aufgeteilt in die Wertebereiche hast?

Und daher auch mein Vorschlag zu Baum-Strukturen in der vorigen Antwort. So kannst du den/die Index/e abbilden und die Zugriffe sind dann nahezu trivial.
Jedes andere Vorgehen ist "Murks" und bildet nur umständlich eine gute Datenstruktur nach. Es ist nicht nur aus Lust und Laune so, dass "alle" Datenbanken Baum-Strukturen für den Index verwenden (bei alle bitte die " nicht übersehen).

Da es aber viele Bäume gibt, musst du selbst einen passenden für deine Problemstellung finden. Es hängt u.a. auch davon ab ob mehr gelesen wie geschrieben wird, usw.

mfG Gü

Okay, ich dachte nur es gäbe vorgefertigte Methoden im Framework.

@gfoidl: In wie fern bietet ein Baum Vorteile gegenüber einer binären Suche? Der Aufwand dürfte doch bei beiden log(n) sein, oder ?

Der Begriff "Binärsuche" sagt nichts über dessen Implementierung aus.
Was also willst Du mit einem Tree vergleichen?

Hast Du, wie gfoidl Dich gebeten hat, einfach mal die Doku gelesen?
Lass Dir doch nicht immer alles auf dem Präsentierteller servieren. Wir sind nicht die Boten.

Hast Du, wie gfoidl Dich gebeten hat, einfach mal die Doku gelesen?

=> Ja, mit der Erkenntnis, das die SortedList einfach nur sortierte Einträge enthält, aber keine Query-Methoden bietet, die die Sortierung effizient nutzen. Daher suche ich ja weiter.

Unter binärer Suche verstehe ich folgenden Algorithmus:

1. Nehme das mittlere Element der sortierten Liste.
2. Gucke ob der Gesuchte Wert größer oder kleiner deines Suchwertes ist.
3. Mache das gleiche entweder mit der rechten oder der linken Hälfte.

Hallo Christoph K.,

hab deinen Edit nicht bemerkt, erst durch die Folgeantworten.

In wie fern bietet ein Baum Vorteile gegenüber einer binären Suche?

Naja, hast du dich mit Bäumen ein wenig auseinandergesetzt? Dann ergibt sich die Antwort dazu von selbst.

Es lassen sich Operationen wie Filtern besser abbilden bzw. lassen sich die Treffer einfacher ermitteln. Außerdem ist es möglich mehrere "Indexe" anzulegen.
Aber schau dir zuerst die Theorie dazu an und entscheide selbst.

Oder du lässt dich einfach empirisch überzeugen: SQL Server verwendet einen B*-Baum (wenn ich mich nicht täusche) für die Indexe. Wäre eine binäre Suche besser bzw. passender, so würde das wohl so umgesetzt worden sein.

PS: das mit der binären Suche hast du schon so richtig wiedergegeben. Der Aufwand davon ist O(log n).

mfG Gü