75

既知の複雑さの境界を持つ純粋に機能的なマップなどのデータ構造仕様が与えられると、いくつかの実装から選択する必要があります。正しいものを選択する方法についてはいくつかの伝承があります。たとえば、一般的に赤黒木は高速であると考えられていますが、AVL 木は多くのルックアップを伴うワークロードでより優れたパフォーマンスを発揮します。

  1. この知識 (セット/マップに関連する) の体系的なプレゼンテーション (公開された論文) はありますか? 理想的には、実際のソフトウェアで実行される統計分析を見たいと思っています。たとえば、マップの使用には N 種類の典型的な種類があると結論付け、それぞれの入力確率分布をリストします。

  2. 入力のさまざまな分布でマップと設定のパフォーマンスをテストする体系的なベンチマークはありますか?

  3. 適応アルゴリズムを使用して、実際の使用状況に応じて表現を変更する実装はありますか?

4

1 に答える 1

5

これらは基本的に研究テーマであり、結果は一般的に結論の形で示され、統計データは隠されています。ただし、独自のデータに対して統計分析を行うことはできます。

ベンチマークについては、実装の詳細をよく確認してください。

質問の 3 番目の部分は非常に主観的な問題であり、実際の意図は実装時には決してわからない可能性があります。ただし、perl などの言語は、すべての操作に対して高度に最適化されたソリューションを実装するために最善を尽くします。

以下が役立つかもしれません：Chris OkasakiによるPurely Functional Data Structures http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

于 2013-11-27T17:22:54.053 に答える