1

Erlang のバイナリ ツリーの実装で遊んでいます。アイデアを提供するコードの一部を次に示します。

-record(node, {key, value, left, right}).

% ...

insert(Tree, {Key, Value}) when Key == Tree#node.key ->
    #node{key=Key,
          value=Value,
          left=Tree#node.left,
          right=Tree#node.right};

insert(Tree, {Key, Value}) when Key > Tree#node.key ->
    Tree#node{right=insert(
        Tree#node.right, {Key, Value})};

% ...

ここで、新しいキーと値をツリーに挿入すると、ノードが挿入 (または変更) された新しいツリーが返されます。

質問: VM は実際にツリーと GC を古いものにコピーしますか (これは非効率的です)、または古いブランチへの参照をコピーして、新しいキーの影響を受けるノード/ブランチのみを変更しますか?

関連している：

4

1 に答える 1

3

式 Tree#node{right=...} は、'right' フィールドを除いて Tree と同じエントリを含む新しいレコード (タプル) を作成します。各エントリは 1 つの機械語を使用します。エントリがアトム、整数、または空のリストのような「即時」である場合、すべての情報はその単語にあります。それ以外の場合、エントリは実際のデータ (タプルやバイナリなど) へのタグ付きポインターです。いずれの場合も、その単語だけが新しいレコードにコピーされます。Erlang は、メッセージを送信している場合を除き、「ディープ コピー」を行いません。(ETS テーブルにデータを保存するのは、データをテーブルに送信するのと同じように動作することに注意してください。) 古い Tree レコードだけがガベージになります。

于 2013-09-04T11:07:12.397 に答える