問題タブ [finger-tree]

高速な連結操作と編集操作を備えた文字列の表現が必要です。「Ropes: an Alternative to Strings」という論文を読みましたが、1995 年以降、この分野で大きな改善はありましたか?

編集: 以前に検討した可能性の 1 つは、文字列を葉として持つ2 ～ 3 本の指の木を使用することですが、詳細な分析は行っていません。これにより、ロープの逆とは対照的に、償却された一定時間の両端の追加/削除と対数 (小さい文字列のチャンクの数) の連結が得られます。

Clojure の新しい contrib ライブラリ グループにはfinger tree ライブラリがあります。クロージュアのフィンガーツリーのユースケースは何ですか? clojure の他の永続的なデータ構造 (ベクトル、セット、マップ、永続キューなど) の代わりにフィンガー ツリーを使用する必要がある場合。

The Joy of Clojureは、低コストの挿入と削除が必要なインデックス付きコレクションに Finger ツリーを使用できると述べています。また、「データ構造のスイス アーミー ナイフ」とも呼ばれています。この例は非常に高く評価されます。

私はこのリンク（下部近く）で説明されているツリーデータ構造を調査してきました：

http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/

このデータ構造はフィンガーツリーである可能性があると述べられています。しかし、フィンガーツリーについてさらに調査した結果、フィンガーツリーをフィンガーツリーにする「フィンガー」が不足していることがわかりました。代わりに、これは単なる注釈付きの二分木（サブツリーサイズで注釈が付けられている）のようです。

私自身の実装の参照として使用できるこのデータ構造の既存の実装（任意の言語）を知っていますか（ただし、機能的なプログラミング言語での実装ではないことが望ましい）？

または、サブツリーサイズの注釈を既存のツリーデータ構造に後付けするための最適な方法は何でしょうか。

ありがとう！

Comonadsでのこのstackoverflowqestionで始まった昨日のWikibenderは、FingerTreesに関するMarkCCの記事に行き着きました。

Reduceこの記事では、彼は型クラスを多用しています。彼はこの型クラスについて、非常に一般的で頻繁に使用されるライブラリであるかのように書いていますが、ハッキングでは見つけることができず、コードを実際に理解するのに十分なドキュメントも見つかりません。

Reduce誰かが型クラスが何をしているのか、演算子(-<)と演算子がどのように機能するのか、そして(>-)記事（以下にコピー）のコードについて何を教えてくれるのかを理解するのを手伝ってもらえますか？

正しく行われたフィンガーツリーからのコードリスト（私は願っています） ：

リスト1：ノードのインスタンス宣言

リスト2：FingerTreeのインスタンス宣言

リスト3：データ型

私は自分の本やインターネット上のいくつかのサイトをよく調べましたが、自分の答えについて完全には確信が持てません.

存在する反転の数に関して、InsertionSort と FingerTreeSort (RB ツリーに基づく) の漸近的な実行時間を与える必要があります。InsertionSort は O(n+INV) 時間で実行され、FingerTreeSort は O(n+n*lg(INV/n+1) で実行されます。INV = 0、n、n^1.5、および n^2/ の漸近的なランタイムを指定する必要があります。 4.

私が思いついたのは、InsertionSort が O(n)、O(n)、O(n^2)、O(n^2) で実行されるということです。

これは正しいです？なぜだめですか？(特に INV = n と n^1.5 についてはよくわかりません)

FingerTreeSort の場合: O(n*lg(n))、O(n*lg(n))、O(n*lg(sqrt(n)))、O(n*lg(n^2))

FingerTreeSort のすべてについて疑問がありますが、これらはあるべきだと私が考える方法です。適切な漸近ランタイムを見つけるにはどうすればよいですか? たとえば、FingerTreeSort と n^1.5 の場合、一般的なランタイムにプラグインして O(n+n*lg (sqrt(n)+1) であり、漸近的であるため、+1 や +n などの下位の数値を無視して O(n*lg(sqrt(n))) を得ることができます。これは正しい方法ですか? ?

この質問に答えてくださった方々に、あらかじめ感謝いたします。私はそれを大いに感謝します:)

ps。Javaで書いていますが、質問には関係ありません。

しばらく前に、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ツリーの注釈または注釈になる可能性があります。

明らかに漸近的に、可能なすべての操作Seqと同じかそれ以上のパフォーマンスを発揮します。[]ただし、その構造はリストよりも複雑であるため、サイズが小さい場合は、オーバーヘッドが一定であるため、速度が低下する可能性があります。特に、いくらか知りたいのですが。

1. <|比較してどれくらい遅い:ですか？
2. Seqフォールドオーバー/トラバースと比較して、フォールドオーバー/トラバースはどれくらい遅いですか[]（フォールディング/トラバース機能のコストを除く）？
3. \xs x -> xs ++ [x]遅くなるサイズ（概算）は|>？
4. ++遅くなるサイズ（概算）は><？
5. viewlリストのパターンマッチングと比較して、結果の呼び出しとパターンマッチングのコストはいくらですか？
6. -elementリストと比較して、n-elementはどのくらいのメモリを占有しますか？（要素によって占有されているメモリはカウントせず、構造のみをカウントします。）Seqn

償却された複雑さについて話しているので、測定するのは難しいことは知っていますSeqが、少なくともいくつかの大まかな数値を知りたいと思います。

効率的なランダムな挿入と削除を可能にする永続的なシーケンシャル データ構造を探しています。次の実装が見つかりました。

• clojure.data.finger-tree (counted-double-list の実装)
• wgjo.data.cljs
• フレクスベック

過去 2 年間、clojure.data.finger-tree にはあまり活動がなく、他のものは比較的新しいものだったので、誰かがこれらのいずれかを本番環境で使用した経験があるかどうか、および私が持っている代替手段があるかどうか疑問に思っていました。見落とした。

Finger Tree の論文: http://www.soi.city.ac.uk/~ross/papers/FingerTree.html は Data.Sequence ライブラリの基礎です: https://www.haskell.org/ghc/docs /7.6.1/html/libraries/containers-0.5.0.0/Data-Sequence.html#g:10

しかし、このライブラリは、サイズの注釈が付けられたフィンガー ツリーの関数しか提供していないようです。クライアントが使用する他の注釈を提供することはできません。特に、sort 関数は「SortSeq」ではなく、別の Seq を返します。

この論文で説明されているすべての機能を提供する FingerTrees の既存の haskell 実装はありますか?

少しグーグルで検索して、Finger Treesに関する論文を見つけました。これは、適切な漸近的な複雑さで優先キューを実装するために使用できますが、それらは非常に複雑ですが、それでも私が見つけることができる最も単純なものです.

Haskell で高速優先キューを実装できる単純なデータ構造はありますか? 初心者のプログラマーに説明できるように、簡単に 考えてください。