Bei einer Datenstrukturspezifikation wie einer rein funktionalen Karte mit bekannten Komplexitätsgrenzen muss zwischen mehreren Implementierungen gewählt werden. Es gibt einige Folklore, wie man die richtige auswählt, zum Beispiel werden Rot-Schwarz-Bäume im Allgemeinen als schneller angesehen, aber AVL-Bäume haben eine bessere Leistung bei Arbeitslasten mit vielen Suchvorgängen.
Gibt es eine systematische Darstellung (veröffentlichtes Papier) dieses Wissens (in Bezug auf Sets / Karten)? Idealerweise würde ich mir wünschen, dass statistische Analysen mit der tatsächlichen Software durchgeführt werden. Es könnte beispielsweise zu dem Schluss kommen, dass es N typische Arten der Kartennutzung gibt, und die Eingangswahrscheinlichkeitsverteilung für jede auflisten.
Gibt es systematische Benchmarks, die die Leistung testen und die Leistung für verschiedene Verteilungen von Eingaben festlegen?
Gibt es Implementierungen, die adaptive Algorithmen verwenden, um die Darstellung abhängig von der tatsächlichen Verwendung zu ändern?
canihazresourcezFrage, mit anderen Worten, eine Crowd-Sourcing-Internetsuche). In jedem Fall kommt eine flüchtige Google-Suche mit diesem: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.9196Antworten:
Dies sind im Wesentlichen Forschungsthemen, und die Ergebnisse werden im Allgemeinen in Form von Schlussfolgerungen angegeben, während die statistischen Daten verborgen sind. Man kann jedoch statistische Analysen seiner eigenen Daten durchführen.
Gehen Sie für die Benchmarks besser die Implementierungsdetails durch.
Der dritte Teil der Frage ist eine sehr subjektive Angelegenheit, und die tatsächlichen Absichten sind zum Zeitpunkt der Implementierung möglicherweise nie bekannt. Sprachen wie Perl geben jedoch ihr Bestes, um für jeden Vorgang hochoptimierte Lösungen zu implementieren.
Folgendes könnte hilfreich sein: Rein funktionale Datenstrukturen von Chris Okasaki http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
quelle