我认为您的代码并不像您预期的那样需要内存。它确实打破和改革了列表，但它倾向于保持大多数子列表完好无损。
正如其他人所说，使用 Hold 包装器和/或 HoldXXX 属性可能会做得更好，以便模拟引用调用。
有关某些相关数据结构实现的硬核方法，请参阅
http://library.wolfram.com/infocenter/MathSource/7619/
相关代码在笔记本 Hemmecke-final.nb 中（之所以如此命名，是因为它实现了 R. Hemmecke 和合著者的 toric Groebner 基算法）。
我尝试使用 Hold... 属性重新实现，但我不是很擅长，当代码向我发起攻击时我放弃了它（错过了，但杀死了我的 Mathematica 会话）。因此，我有一个使用未记录的“原始”Mathematica 数据类型的实现，该数据类型是惰性的，因此可以进行引用调用行为。
所讨论的结构称为“expr bag”，因为通用 Mathematica 数据结构是“expr”。它就像一个列表，但 (1) 它可以在一端增长（尽管不能缩小）并且 (2) 像其他原始表达式类型（例如版本 8 中的图形）一样，它具有可以通过提供的函数访问和/或更改的组件（一个API，可以这么说）。它的底层“元素”是惰性的，因为它们可以引用任何 expr（包括包本身），并且可以按照我将在下面指出的方式进行操作。
上面的第一项提供了实现 Sow/Reap 的底层技术。这是第二个对下面的代码感兴趣的地方。最后，我将在解释数据结构的过程中加入一些评论，因为没有正式的文档。
我或多或少地保留了与原始代码相同的样式，特别是它仍然是一个在线版本（也就是说，元素不需要在一开始就全部进入，而是可以单独添加）。改了几个名字。使基本结构类似于
节点（边界框、值、零或四个子节点）
如果有子节点，则 value 字段为空。box 和 value 字段由通常的 Mathematica List 表达式表示，尽管使用专用头并使其更类似于 C 结构样式可能是有意义的。在命名各种字段访问/设置功能时，我确实做了类似的事情。
一个警告是，这种原始数据类型消耗的内存开销比例如列表要多得多。所以我下面的变体将使用比最初发布的代码更多的内存。不是渐近的，只是通过一个常数因子。此外，在访问或设置元素值方面，它需要一个恒定的开销因子，而不是一个可比较的 C 结构。所以它不是灵丹妙药，只是一种行为不应该产生渐近意外的数据类型。
AppendTo[$ContextPath, "Internal`"];
makeQuadTreeNode[bounds_] := Bag[{bounds, {}, {}}]
(*is pt inside box?*)
insideBox[pt_, box_] :=
And @@ Thread[box[[1]] <= (List @@ pt) <= box[[2]]]
(*split bounding box into 4 children*)
splitBox[{{xmin_, ymin_}, {xmax_, ymax_}}] :=
Map[makeQuadTreeNode, {{{xmin, (ymin + ymax)/2}, {(xmin + xmax)/2,
ymax}}, {{xmin,
ymin}, {(xmin + xmax)/2, (ymin + ymax)/2}}, {{(xmin + xmax)/2,
ymin}, {xmax, (ymin + ymax)/2}}, {{(xmin + xmax)/
2, (ymin + ymax)/2}, {xmax, ymax}}}]
bounds[qt_] := BagPart[qt, 1]
value[qt_] := BagPart[qt, 2]
children[qt_] := BagPart[qt, 3]
isLeaf[qt_] := value[qt] =!= {}
isSplit[qt_] := children[qt] =!= {}
emptyNode[qt_] := ! isLeaf[qt] && ! isSplit[qt]
(*qtInsert #1-return input if pt is out of bounds*)
qtInsert[qtree_, pt_] /; ! insideBox[pt, bounds[qtree]] := qtree
(*qtInsert #2-empty node (no value,no children)*)
qtInsert[qtree_, pt_] /; emptyNode[qtree] := value[qtree] = pt
(*qtInsert #2-currently a leaf (has a value and no children)*)
qtInsert[qtree_, pt_] /; isLeaf[qtree] := Module[
{kids = splitBox[bounds[qtree]], currval = value[qtree]},
value[qtree] = {};
children[qtree] = kids;
Map[(qtInsert[#, currval]; qtInsert[#, pt]) &, kids];
]
(*qtInsert #4-not a leaf and has children*)
qtInsert[qtree_, pt_] := Map[qtInsert[#, pt] &, children[qtree]];
getBoxes[ee_Bag] :=
Join[{bounds[ee]}, Flatten[Map[getBoxes, children[ee]], 1]]
getPoints[ee_Bag] :=
Join[{value[ee]}, Flatten[Map[getPoints, children[ee]], 1]]
qtDraw[qt_] := Module[
{pts, bboxes},
pts = getPoints[qt] /. {} :> Sequence[];
bboxes = getBoxes[qt];
Graphics[{EdgeForm[Black], Hue[0.2], Map[Disk[#, 0.01] &, pts],
Hue[0.7], EdgeForm[Red],
FaceForm[], (Rectangle @@ #) & /@ bboxes}, Frame -> True]]
这是一个例子。我会注意到缩放是合理的。也许 O(n log(n)) 左右。绝对比 O(n^2) 好。
len = 4000;
pts = RandomReal[{0, 2}, {len, 2}];
qt = makeQuadTreeNode[{{0.0, 0.0}, {2.0, 2.0}}];
Timing[Do[qtInsert[qt, pts[[i]]], {i, 1, len}]]
{1.6, Null}
一般的 expr 包注释。这些都是旧的，所以我不声称这一切仍然如所示。
这些函数存在于 Internal` 上下文中。
Bag 创建一个 expr 包，可以选择使用预设元素。
BagPart 获取 expr 包的部分，类似于普通 expr 的 Part。也可用于 lhs，例如重置一个值。
StuffBag 将元素附加到包的末尾。
我们还有一个 BagLength。用于迭代袋子。
由于两个原因，这些功能非常有用。
首先，这是在 Mathematica 中制作可扩展表的好方法。
其次，对包的内容进行评估，然后将其放入原始 expr 中，因此被屏蔽。因此，可以将它们用作“指针”（在 C 意义上）而不是对象，这不需要 Hold 等。这里有一些例子：
a = {1,2,a} (* gives infinite recursion *)
如果我们改为使用袋子，我们会得到一个自引用结构。
In[1]:= AppendTo[$ContextPath, "Internal`"];
In[2]:= a = Bag[{1,2,a}]
Out[2]= Bag[<3>]
In[3]:= expr1 = BagPart[a, All]
Out[3]= {1, 2, Bag[<3>]}
In[4]:= expr2 = BagPart[BagPart[a, 3], All]
Out[4]= {1, 2, Bag[<3>]}
In[5]:= expr1 === expr2
Out[5]= True
这在 Mathematica 中很难以任何其他方式模拟。需要以某种不太透明的方式使用稀疏表（散列）。
这是一个相关示例，未完全调试。我们基本上实现了一个链表，可以破坏性地修改尾部、替换子列表等。
tail[ll_] := BagPart[ll,2]
settail[ll_, ll2_] := BagPart[ll,2] = ll2
contents[ll_] := BagPart[ll,1]
setcontents[ll_, elem_] := BagPart[ll,1] = elem
createlinkedlist[elems__] := Module[
{result, elist={elems}, prev, el},
result = Bag[{elist[[1]],Bag[]}];
prev = result;
Do [el = Bag[{elist[[j]],Bag[]}];
settail[prev, el];
prev = el,
{j,2,Length[elist]}];
result
]
In[18]:= tt = createlinkedlist[vv,ww,xx]
Out[18]= Bag[<2>]
In[20]:= BagPart[tt,All]
Out[20]= {vv, Bag[<2>]}
所以 tt 是一个链表，第一个元素是 vv，下一个元素本身就是一个链表，等等。我没有使用 Lisp 术语（car/cdr 等），因为我无法回忆 Lisp 的列表操作是否具有破坏性。但你得到了一般的想法。
沿着类似的思路，我使用 expr 包来实现二叉树。这很有用，因为我们可以在恒定时间内进行破坏性更改（假设我们已经在插入/删除点上有一个“句柄”），而且 expr 包的“原始”性质意味着我们完全避免了 Mathematica 的无限求值语义。
也许是另一个应用程序。
Pointer = Internal`Bag
Contents[aa_Pointer, j_Integer] /;0<j<=Internal`BagLength[aa] :=
Internal`BagPart[aa,j]
SetContents[aa_Pointer, j_Integer, e_] /; 0<j<=Internal`BagLength[aa] :=
Internal`BagPart[aa,j] = e
SetContents[aa_Pointer, j_Integer, e_] /; j>BagLength[aa] :=
(Do[Internal`StuffBag[aa,Null], {k,Internal`BagLength[aa]+1,j-1}];
Internal`StuffBag[aa,e])
尝试
a = Bag[{1,2,a,6,t,y,99,Bag[{a,q,3,r,a,5,t}]}]
expr1 = BagPart[a, All]
expr2 = BagPart[BagPart[a, 3], All]
Contents[a, 4]
SetContents[a, 7, Contents[a,7]+5]
SetContents[a,11,33]
Daniel Lichtblau Wolfram 研究
