15

しばらく前に、FingerTrees に関する記事(付随する Stack Overflow Questionも参照) に出くわし、そのアイデアをファイルに入れました。私はついにそれらを利用する理由を見つけました。

私の問題は、Data.FingerTree パッケージの端が少し腐っているように見えることです。さらに、データ構造を利用する Containers パッケージのData.Sequenceは、(おそらくより良い) バージョンを再実装しますが、それをエクスポートしません。

この構造は理論的には有用であると思われますが、実際の使用や注目はあまりないようです。実際問題として FingerTree が役に立たないことに人々は気付きましたか、それともこのケースは十分な注意が払われていないのでしょうか?

さらに説明:

優れた連結特性を持つテキストを保持するデータ構造を構築することに興味があります。さまざまなフラグメントから HTML ドキュメントを作成することを考えてみてください。ほとんどのビルド済みソリューションはバイト文字列を使用しますが、Unicode テキストを適切に処理するものが本当に必要です。現時点での私の計画は、Data.Text フラグメントを FingerTree にレイヤー化することです。

(offset,length) 操作を使用してコピーせずにスライスを取得する Data.Vector からのトリックも借りたいと思います。Data.Text.Text にはこれがデータ型に組み込まれていますが、これは効率的な uncons および unsnoc 操作にのみ使用されます。FingerTree では、この情報は非常に簡単にvツリーの注釈または注釈になる可能性があります。

4

3 に答える 3

17

特にフィンガー ツリーに関する質問に答えると、配列に比べて固定コストが比較的高く、効率的な連結を実現する他の方法よりも複雑であるという問題があると思います。Builder には、チャンクを追加するためのより効率的なインターフェイスがあり、通常はすぐに利用できます (@informatikr の回答のリンクを参照してください)。がチャンクData.Text.Lazyのリンク リストで実装さData.Text.Lazyれ、ビルダーから を作成しているとします。多くのチャンク (おそらく 50 以上) を持っているか、リストの最後近くのデータに繰り返しアクセスしていない限り、フィンガー ツリーの高い一定コストはおそらく価値がありません。

実装はパフォーマンス上のData.Sequence理由から特化されており、fingertreeパッケージによって提供される完全なインターフェイスほど一般的ではありません。そのため、エクスポートされません。以外に使用することは実際には不可能Sequenceです。

また、モノイド注釈はかなり重要な抽象化の障壁の背後にあるため、多くのプログラマーがモノイド注釈を実際に使用する方法について途方に暮れているのではないかと思います。他のデータ型と比較してどのように役立つかがわからないため、多くの人はそれを使用しません。

Chung- chieh Shan の単語数に関するブログ シリーズ(その 2 、その 3、その 4 ) を読むまでは、よくわかりませんでした。これは、アイデアが実際のコードで確実に使用できるという証拠です。

あなたの場合、部分的な結果の検査と効率的な追加の両方が必要な場合は、フィンガーツリーを使用する方がビルダーよりも優れている場合があります。Textビルダーの実装によっては、 に変換したり、ビルダーにさらにものを追加したり、再度 に変換したりするなど、多くの繰り返し作業を行うことになる場合がTextあります。ただし、使用パターンによって異なります。

私のsplaytreeパッケージに興味があるかもしれません。これは、モノイド アノテーションを備えたスプレイ ツリーと、それらの上に構築されたいくつかの異なる構造を提供します。splay ツリー自体を除いて、SetおよびRangeSetモジュールには多かれ少なかれ完全な API がありSequenceます。モジュールのほとんどは、私がテストに使用したスケルトンです。これは、探しているものに対する「バッテリーを含む」ソリューションではありません (繰り返しますが、@informatikr の回答がそれらを提供します) が、モノイド注釈を試してみたい場合は、Data.FingerTree. すべての要素を順番にトラバースすると (または最後までこっそりとスノックするなど)、スプレイ ツリーのバランスが崩れる可能性があることに注意してください。

于 2012-06-22T10:16:52.937 に答える
9

John Lato の回答に加えて、フィンガー ツリーのパフォーマンスに関する具体的な詳細をいくつか追加します。

大まかな要約は次のとおりです。

  • Data.Sequenceには優れた定数因子と漸近線があります:[]リストの先頭 (両方のデータ構造に O(1) 漸近線がある場合) にアクセスする場合とほぼ同じ速度であり、リストの他の場所 (Data.Sequenceの対数漸近線[]が の線形を打ち負かす場所) にアクセスする場合と同じくらい高速です。漸近）。

  • Data.FingerTreeは と同じ漸近線を持ちますが、Data.Sequence約 1 桁遅くなります。

リストと同様に、フィンガー ツリーは要素ごとのメモリ オーバーヘッドが高いため、チャンクと組み合わせてメモリとキャッシュの使用を改善する必要があります。実際、これを行うパッケージはいくつかあります ( yi、trifecta、rope )。Data.FingerTreeパフォーマンスを近づけることができれば、値のフィンガー ツリーを実装しData.Sequenceた型を期待したいと思います。このような型は のストリーミング動作を失いますが、改善されたランダム アクセスと連結パフォーマンスの恩恵を受けます。（同様に、 と を見たいと思います。）Data.Text.SequenceData.TextData.Text.LazyData.ByteString.SequenceData.Vector.Sequence

これらを現在実装する上での障害は、フィンガー ツリーの効率的で汎用的な実装が存在しないことです (これについて詳しく説明する以下を参照してください)。1の効率的な実装を作成するにはData.Text.Sequence、 に特化したフィンガー ツリーを完全に再実装する必要がTextありData.Text.LazyますText。残念ながら、finger tree はリストよりもはるかに複雑なので (特に連結!)、これはかなりの量の作業になります。

したがって、私が見る限り、答えは次のとおりです。

  • 特殊なフィンガーツリーは素晴らしいですが、実装には多くの作業が必要です
  • チャンクされたフィンガー ツリー (例: Data.Text.Sequence)は素晴らしいものですが、現時点では のパフォーマンスが低いためData.FingerTree、一般的なケースではチャンク リストの実行可能な代替手段にはなりません。
  • ビルダーとチャンクリストは、チャンクフィンガーツリーの多くの利点を実現するため、一般的なケースでは十分です。
  • ビルダーとチャンクリストが十分でないまれなケースでは、私たちは歯を食いしばり、チャンクフィンガーツリーの貧弱な定数係数 (yi と trifecta など) に我慢します。

効率的で汎用的なフィンガー ツリーの障害

Data.Sequenceとの間のパフォーマンス ギャップの多くは、 のData.FingerTree2 つの最適化によるものですData.Sequence。

これらの最適化は、ジェネリック アンパッキングにデータ ファミリをData.FingerTree使用し、GHC のインライナーとスペシャライザーを利用するという一般的なケースに適用できます。私のfingertree-unboxed パッケージを参照してください。残念ながら、これらの手法には重大な問題がいくつかあります。Data.Sequence

  • 一般的なアンパックのデータ ファミリは、多くのインスタンスを定義する必要があるため、ユーザーにとって不快です。この問題に対する明確な解決策はありません。

  • finger ツリーは、GHC のスペシャライザがうまく処理できない多形再帰を使用します ( 1 , 2 )。これは、メジャー型を十分に特殊化するには、INLINEGHC が大量のコードを生成する原因となる多くのプラグマが必要であることを意味します。

これらの問題のため、Hackage でパッケージをリリースすることはありませんでした。

于 2012-06-23T02:03:41.177 に答える
7

Finger Treeの質問を無視し、詳細な説明にのみ応答します。

どちらも高速連結を可能にします。スライスについては、それが問題を解決するために重要である場合、理想的なパフォーマンスが得られない可能性があります。

于 2012-06-22T09:03:50.690 に答える