在Mathematica中传递带有大量数据的变量会花费大量内存和时间吗？

Question

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

我的问题是,将我的整个树结构(我已经存储在一个列表中)传递给一个要搜索的函数,为我的程序花费了大量的内存和时间,因为我必须多次使用一些函数.算法？

例如,我有一个搜索特定节点的子节点的Select函数,我使用该函数搜索整个树.

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

但是我需要访问树,所以将整个树结构传递给函数是否合理？因为似乎没有办法让整个笔记本变量全局变量.或者是否有其他方法来解决这个问题？

Answer 1

不,它不会花费额外的内存来传递表达式.与函数式语言一样,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,它都不会对内存使用产生影响.