15

Ukkonen のアルゴリズムに基づいて、Mathematica でサフィックス ツリーを構築するためのアルゴリズムをコーディングしています。

私が持っている問題は、ツリー構造全体（リストに保存したもの）を関数に渡して検索することで、プログラムでいくつかの関数を複数回使用する必要があるため、多くのメモリと時間を費やすことになります。アルゴリズム？

たとえば、特定のノードの子を検索する関数があり、そのSelect関数を使用してツリー全体を検索します。

getChildren[parentID_] := Select[tree, #[[3]] == parentID &];

ただし、ツリーにアクセスする必要があるため、ツリー構造全体を関数に渡すのは合理的ですか? 変数をノートブック全体にグローバルにする方法はないようです。または、これを回避する別の方法はありますか?

4

2 に答える 2

24

いいえ、式を渡すために余分なメモリは必要ありません。関数型言語ではよくあることですが、Mathematica オブジェクトは不変です。変更することはできません。代わりに、何らかの関数を使用してオブジェクトを変換すると、新しいオブジェクトが作成されます。これはまた、それらを変換しなければ、関数間でいくら渡してもコピーされないことを意味します。

ユーザーの観点から見ると、 Mathematica の式は木ですが、内部的に有向非巡回グラフとして保存されていると思います。つまり、同じ部分式は、完全な式に何回出現しても、メモリに一度だけ保存される可能性があります(例を参照)。のドキュメント ページShare[])。

説明する例を次に示します。

まず、余分なメモリを消費しないようにしますIn:Out

In[1]:= $HistoryLength = 0;

メモリ使用量を確認します。

In[2]:= MemoryInUse[]
Out[2]= 13421756

かなりの量のメモリを消費する式を作成してみましょう。

In[3]:= s = f@Range[1000000];

In[4]:= MemoryInUse[]
Out[4]= 17430260

この式を100回繰り返します...

In[5]:= t = ConstantArray[s, 100];

...そして、メモリ使用量がほとんど増加していないことに注意してください。

In[6]:= MemoryInUse[]
Out[6]= 18264676

ByeCount[]実際に使用された物理メモリは報告されていませんが、共通の部分式が同じメモリを共有することが許可されていない場合に使用されるメモリであるため、誤解を招く可能性があります。

In[7]:= ByteCount[t]
Out[7]= 400018040

注意すべき興味深い点: から を削除f[...]しs、 と の両方sをt単純な数値配列にすると、このメモリ共有は発生せず、メモリ使用量は最大 400 MB に跳ね上がります。

treeグローバル変数を作成しても の引数をgetChildren作成しても、メモリ使用量に違いはありません。

于 2011-11-30T10:58:12.510 に答える
4

Szabolcsの回答に加えて、データを変更する必要がある場合は、参照渡しに関するこの質問が役立つ場合があります。

関数間でのデータの受け渡しに関する簡単な質問

于 2011-11-30T11:16:19.363 に答える