Ich bin dabei, eine benutzerdefinierte persistente Datenstruktur vom Typ Schlüsselwert zu entwickeln, um sie mit SqlLite und Berkley DB zu vergleichen. Bevor ich die Implementierung geschrieben habe, wollte ich die beste Datenstruktur für diese Zwecke finden. Ich schaute auf das Paar:
Ich wollte, dass die von mir ausgewählten Datenstrukturen ähnliche Leistungszahlen wie das .net-Wörterbuch haben.
Ich habe einen einfachen Test für eine Schleife mit 500k Iterationen für Einfügungen verwendet und die Stoppuhr verwendet, um Einfügungen und Schlüsselsuche zu messen:
Ich merke das
Einfügezeit: 7% langsamer als das .net-Wörterbuch.
Nachschlagezeit: 1000% langsamer als das .net-Wörterbuch. Dies ist sogar langsamer als die Lookup-Geschwindigkeit mit sqllite !! Ich habe versucht, den Test mit aktivierter Compiler-Optimierung durchzuführen und habe trotzdem ähnliche Ergebnisse erzielt.
Ich merke, dass ich Hashtables gegen Bäume usw. vergleiche, aber ich habe auf die Leistungsdiskrepanz zwischen allen Datenstrukturen hingewiesen.
Jeder hat irgendwelche Ideen
Zwei Gedanken:
Sie sollten sicherstellen, dass Sie nicht versehentlich JIT-Zeit in Ihre Tests einbeziehen - dies kann dem Ergebnis viel Zeit einbringen. Sie sollten zwei Läufe in derselben Ausführung ausführen und den ersten Lauf verwerfen.
Sie sollten sicherstellen, dass Sie nicht unter dem Debugger ausgeführt werden - dies kann die Leistungsergebnisse erheblich verzerren.
Nebenbei bemerkt, können Leistungsunterschiede, die Sie sehen, sehr wohl das Ergebnis der Leistungsunterschiede zwischen einer Hash-Tabelle und einem Baum sein. Eine Baumstruktur hat typischerweise eine O (n * log (n)) -Leistung im Durchschnitt für eine Suche. Ein ausgeglichener Baum kann das auf O (lon (n)) reduzieren. Hashtables können sich der O (1) -Zeit für Lookups nähern, wenn Hash-Kollisionen vermieden werden.
Ich würde mir auch vorstellen, dass die .NET-Dictionary-Klasse stark optimiert ist, da sie eine Brot-und-Butter-Datenstruktur für so viele verschiedene Dinge in .NET darstellt. Auch ein generisches Wörterbuch & lt; & gt; ist möglicherweise in der Lage, das Boxen zu vermeiden, und daher sehen Sie möglicherweise einige Leistungsunterschiede.
Wenn alles, was Sie brauchen, ein Nachschlagen ist, wird ein rot / schwarzer Baum nicht Ihre beste Datenstruktur sein. Es bietet eine Sortierung, die immer langsamer als eine Hashtabellensuche ist. Wenn Sie .net Dictionary mit einer vergleichbaren C5-Datenstruktur vergleichen möchten, würden Sie C5.HashDictionary verwenden.
Tags und Links c# dictionary tree