optimization - 在 Mathematica 中传递具有大量数据的变量是否会占用大量内存和时间？

Question

我正在编写一个基于 Ukkonen 算法在 Mathematica 中构建后缀树的算法。

我的问题是，将我的整个树结构(我存储在一个列表中)传递给一个函数来搜索，因为我必须在算法？

例如，我有一个搜索特定节点的子节点的函数，我使用 Select搜索整棵树的函数。

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

但是我需要访问树，那么将整个树结构传递给函数是否合理？因为似乎没有一种方法可以使整个笔记本的变量成为全局变量。还是有一些替代方法可以解决这个问题？

Answer 1

不，传递表达式不需要额外的内存。与函数式语言一样，Mathematica 对象是 immutable :它们不能被修改，而是在您使用某些函数转换它们时创建一个新对象。这也意味着如果你不转换它们，它们就不会被复制，无论你在函数之间传递了多少。

从用户的角度来看，Mathematica 表达式是树，但我相信它们在内部存储为 directed acyclic graphs ，即相同的子表达式只能在内存中存储一​​次，无论它在完整表达式中出现多少次(参见例如 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[] 具有误导性，因为它没有报告实际使用的物理内存，而是在不允许公共(public)子表达式共享相同内存时使用的内存:

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

需要注意的一个有趣点:如果您删除 f[...]来自 s , 并使两者 s和 t一个普通的数字数组，则不会发生这种内存共享，内存使用量将跃升至 ~400 MB。

无论您制作 tree getChildren 的全局变量或参数，它不会对内存使用产生影响。