4

指の木に関しては、この論文で見られ、 Eric Lippert によるこの投稿で言及されています。

各指のある種のリンクされたリスト構造とは対照的に、明示的なタプル配置が使用される理由がわかりません。つまり、One(x), Two(x, y), Three(x, y, z), Four(x, y, z, a)最適ではない deque オブジェクトと do を定義するだけでなく、なぜ定義するのLessOptimalDeque.AddLeft(x)でしょうか。

どういうわけか遅いですか？つまり、一部のノード/ノードのグループのメモリを再利用するデータ構造を使用できますか?

論文では、次のようにも言及されています。

演習 1. 上記のプレゼンテーションでは、簡単にするために数字をリストとして表しました。より正確で効率的な実装では、型を使用します 

data Digit a = One a  
| Two a a
| Three a a a
| Four a a a a

Digit のこの定義を使用するには、上記の定義を作り直してください。

なぜそれがより効率的であるかはわかりません。それは作者が使用していた関数型言語に関連するものだけですか?それ以外の場合は、上で提案したデータ構造を使用して行うこともできますか?

編集
ここに画像の説明を入力

このように指を実装するのはどうですか？

4

1 に答える 1

2

これが Haskell でより効率的である理由を確認するには、次のようにします。

data Digit a
           = One a  
           | Two a a
           | Three a a a
           | Four a a a a

これよりも（ベクトルの明らかなエンコーディング）：

data List a = One a
            | Many a (List a) -- a linked list of at least one element.

Digitaと a の割り当てに必要なヒープ構造を観察できますList。

Four 'x' 'y' 'z' 'd'

対

Many 'x' (Many 'y' (Many 'z' (One 'd')))

前者の場合、3 つのコンストラクターを保存します。後者では、構造体の末尾 (おそらく無限) に追加のヒープ オブジェクトを割り当てる必要があります。一般に、構造体のサイズは最も外側のコンストラクターでエンコードされるため、この表現ではO(n-1)Digit少ないヒープ セルが割り当てられます。結果として、O(1)のサイズも決定できます。

于 2012-07-02T15:05:55.727 に答える