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

现在重复这个表达式一百次......

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 的答案之外，如果您确实需要修改数据，您可能会发现这个问题在 pass-by-reference 上很有用：

关于在函数之间传递数据的简单问题

于 2011-11-30T11:16:19.363 回答