Schneller Speicher für Long-Werte

Guten Tag,

ich beschäftige mich gerade mit der Entwicklung einer Softwareinfrastruktur, in der Geschwindigkeit von zentraler Bedeutung ist. Ein zentraler Anwendungsfall besteht dabei im Speichern und Abrufen von Int64-Listen. Konkret geht es um folgende Operationen:
*Zahl hinzufügen (2 %) *Zahl entfernen (2 %) *Prüfung: Ist Zahl enthalten (96 %)

Die relativen Werte geben die Einzelhäufigkeiten der Operationen an. Der lesende Zugriff überwiegt demnach. Der Wertebereich der Zahlen kann zwischen 1 und 10.000.000 liegen, in der Regel liegt er allerdings zwischen 1 und 1.000.000.

Ganz einfach ließe sich dies natürlich mit einer List<long> realisieren:

List<long> list = new List<Long>();

// Hinzufügen
list.Add(12);

// Entfernen
list.Remove(12);

// Existenz prüfen
bool contains = list.Contains(12);

Ich habe allerdings die Befürchtung, dass dieses Verfahren bei großen Datenmengen Performance Einbußen zur Folge hat. Datenbanken sind ja darauf optimiert, solche Anfragen performant beantworten zu können. Wie sieht es hier bei C# und dem .NET Framework aus. Kann ich hier bereits auf fertige Strukturen zurückgreifen, welche mir weiterhelfen?

Ich bin für jeden Hinweis dankbar!

Robert

Zu aller erst ist eine sortierte Liste von großem Vorteil wenn du so oft prüfen musst ob ein Eintrag vorhanden ist. Z.B. mit SortedList<T>.

So kannst du effiziente Suchalgorithmen verwenden wie z.B. die binäre Suche.

Ein DBMS bietet jetzt natürlich mehr Features da ganze Tabellen auf der Harddisk indiziert liegen und das ganze System mit Funktionen aufwartet die möglichst geschickt von der Platte in den RAM zu hieven.

Allerdings ist mir nicht so ganz klar wie du das mit dem Wertebereich meinst: Hat die Liste dann 10.000.000 Einträge oder sind die einzelnen Zahlen so groß?

Hallo,

danke für deine schnelle Antwort!

Zu aller erst ist eine sortierte Liste von großem Vorteil wenn du so oft prüfen musst ob ein Eintrag vorhanden ist. Z.B. mit SortedList<T>.

Dies ist schon einmal ein guter Anhaltspunkt, vielen Dank! Habe mir kurz die Dokumentation auf MSDN dazu angeschaut, das hört sich schon einmal sehr vielversprechend an. Dem Anschein nach speichert die Liste allerdings Wertepaare (Schlüssel und Wert). Auf einen Teil könnte ich dabei verzichten. Gibt es eine Struktur, welche wirklich nur einfache Werte aufnimmt?

Allerdings ist mir nicht so ganz klar wie du das mit dem Wertebereich meinst: Hat die Liste dann 10.000.000 Einträge oder sind die einzelnen Zahlen so groß?

Meine Ausführungen beziehen sich wirklich auf den Bereich der Werte. Alle Zahlen liegen also wertmäßig zwischen 1 und 10.000.000. Zur Anzahl der in einer Liste enthaltenen Zahlen hatte ich vergessen, mich zu äußern. Diese kann im Extremfall auch bis zu 10.000.000 betragen, im Normalfall werden es allerdings simultan maximal 100.000 sein.

Gruß,

Robert

Hallo robblu,

bei der Verteilung der Zugriffe ganz klar Dictionary<> bzw. ab .NET 3.0 HashSet<>.

Evtl. ist ein bool-Array der Größe 10.000.001, bei der der Wert als Index verwendet wird und der bool Wert angibt, ob der Wert in der Liste enthalten ist, noch ein bisschen schneller.

BTW: Warum verwendest du longs, wenn die Werte locker in einen int passen?

herbivore

Evtl. ist ein bool-Array der Größe 10.000.001, bei der der Wert als Index verwendet wird und der bool Wert angibt, ob der Wert in der Liste enthalten ist, noch ein bisschen schneller.

Für so etwas würde ich her die BitArray-Klasse verwenden.