Mathematica中的树数据结构
我主要使用mathematica作为数学工作台和编写相对较小的特别程序。 然而，我正在设计一个我打算在Mathematica中编程的系统。 我需要将数据存储在树中，然后搜索并遍历树。 尽管我知道如何实现树，但我更喜欢标准的，经过测试的代码。 我研究了Mathematica用户维基上的基本数据结构。 我没有找到，尽管Mathematica文档中有一个小例子。
现在回答我的问题：
是否有可用于某处的数据结构的（开源）包？
你在数据结构方面使用了什么方法？ 逐渐开发你自己的util包？
（这不是一个问题，只是一句话，也许......缺乏（很多可用的）开源软件包是Mathematica没有应有的动力的原因。恐怕鸡鸡蛋问题。）
在Mathematica中，你所做的大部分工作都是基于表达式。 表达式自然具有树形结构。 对于深度优先遍历（可能最常见），可以使用Scan ， Map ， Cases等功能。与传统语言不同的是，没有简单的方法来保存表达式中单个节点的标识树，因为在Mathematica中没有指针。 此外，对于Mathematica中习惯用语的表达式的许多操作，只需要在几个地方对其进行修改即可复制整个表达式，因为表达式是不可变的。
使用不可变的Mathematica表达式作为树仍然有几个优点。 其中之一是，因为它们是不可变的，所以通过查看它们可以很容易地理解它们存储的内容（状态和行为没有混合）。 另一个是有效的通用功能，例如Map ， MapIndexed或Scan ，它们遍历它们。 例如，访客设计模式是不可见的 - 它只是内置在语言中的Map[f,tree,Infinity] 。 此外，还有一些内置函数，如Cases ， Replace ， ReplaceAll等，它们允许编写非常简洁的声明代码来解构树，查找具有某种语法或满足某些条件的树。由于树不是仅限于从列表构建，并且从不同的头部构建，可以有效地使用它来编写非常简洁的树处理代码。 最后，根据探索性和自下而上的编程精神，轻松构建任何所需树形结构的自由可使执行实验和原型事件变得更容易，从而缩短开发周期并最终实现更好的设计。
也就是说，你当然可以实现“有状态”（可变）的树型数据结构。 我怀疑，构建，修改和遍历这样一棵树会带来的性能下降，因为它会在每一步都进行全面的符号化评估过程（请参阅这篇文章以获取更多关于该树的更多细节） ）。 举例来说，例如，如何在Mathematica上下文中为二元搜索树使用相当高效的代码，请参阅我的帖子（通用符号设置）和这里（在编译代码的上下文中）。 对于通常在Mathematica中构建数据结构的方法，我推荐Roman Maeder的书籍：“Mathematica编程”，“Mathematica程序员I和II”，特别是“Mathematica中的计算机科学”。 在后者中，他详细讨论了如何在Mathematica中实现二叉搜索树。 编辑@Simon提到，@Daniel Lichtblau的谈话也是一个很好的资源，它展示了如何构建数据结构并使其高效。
关于在Mathematica中实现数据结构的一般方法，它将包含一些状态，下面是一个在Mathgroup线程中从我的帖子中提取的简单示例 - 它实现了“pair”数据结构。
Unprotect[pair, setFirst, getFirst, setSecond, getSecond, new, delete];
ClearAll[pair, setFirst, getFirst, setSecond, getSecond, new, delete];
Module[{first, second},
first[_] := {};
second[_] := {};
pair /: new[pair[]] := pair[Unique[]];
pair /: pair[tag_].delete[] := (first[tag] =.; second[tag] =.);
pair /: pair[tag_].setFirst[value_] := first[tag] = value;
pair /: pair[tag_].getFirst[] := first[tag];
pair /: pair[tag_].setSecond[value_] := second[tag] = value;
pair /: pair[tag_].getSecond[] := second[tag];
Format[pair[x_Symbol]] := "pair[" <> ToString[Hash[x]] <> "]";
];
Protect[pair, setFirst, getFirst, setSecond, getSecond, new, delete];
以下是您如何使用它的方法：
pr = new[pair[]];
pr.setFirst[10];
pr.setSecond[20];
{pr.getFirst[], pr.getSecond[]}
{10, 20}
创建一个新的对象列表：
pairs = Table[new[pair[]], {10}]
{"pair[430427975]", "pair[430428059]", "pair[430428060]", "pair[430428057]",
"pair[430428058]", "pair[430428063]", "pair[430428064]", "pair[430428061]",
"pair[430428062]", "pair[430428051]"}
设置字段：
Module[{i},
For[i = 1, i <= 10, i++,
pairs[[i]].setFirst[10*i];
pairs[[i]].setSecond[20*i];]]
检查字段：
#.getFirst[] & /@ pairs
{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}
#.getSecond[] & /@ pairs
{20, 40, 60, 80, 100, 120, 140, 160, 180, 200}
在我提到的文章中有一个更详细的讨论。 以这种方式创建的“对象”的一个主要问题是没有自动垃圾收集功能，这可能是为什么在顶级Mathematica中实施的OOP扩展本身并没有真正起飞的主要原因之一。
Mathematica有几种OOP扩展，例如Roman Maeder的classes.m包（源文件在他的“Mathematica编程器”一书中）， Objectica商业软件包和其他几个。 但是，除非Mathematica本身能够为构建可变数据结构（如果发生这种情况）提供有效的机制（可能基于某种指针或引用机制），否则可能会有与此类数据结构的顶级实现相关的巨大性能下降在妈妈。 另外，由于mma是基于不变性作为核心思想之一，因此使可变数据结构与Mathematica编程的其他习惯用法很相符并不容易。
编辑
下面是一个简单的有状态树实现，沿着上面的例子：
Module[{parent, children, value},
children[_] := {};
value[_] := Null;
node /: new[node[]] := node[Unique[]];
node /: node[tag_].getChildren[] := children[tag];
node /: node[tag_].addChild[child_node, index_] :=
children[tag] = Insert[children[tag], child, index];
node /: node[tag_].removeChild[index_] :=
children[tag] = Delete[children[tag], index];
node /: node[tag_].getChild[index_] := children[tag][[index]];
node /: node[tag_].getValue[] := value[tag];
node /: node[tag_].setValue[val_] := value[tag] = val;
];
一些使用示例：
In[68]:= root = new[node[]]
Out[68]= node[$7]
In[69]:= root.addChild[new[node[]], 1]
Out[69]= {node[$8]}
In[70]:= root.addChild[new[node[]], 2]
Out[70]= {node[$8], node[$9]}
In[71]:= root.getChild[1].addChild[new[node[]], 1]
Out[71]= {node[$10]}
In[72]:= root.getChild[1].getChild[1].setValue[10]
Out[72]= 10
In[73]:= root.getChild[1].getChild[1].getValue[]
Out[73]= 10
有关使用此可变树数据结构的一个非平凡示例，请参阅我的这篇文章。 它还面临着更多重用Mathematica原生数据结构和函数的方法，并很好地说明了本文开头讨论的要点。
我主要使用mathematica作为数学工作台和编写相对较小的特别程序。
Mathematica真的擅长于此。
你在数据结构方面使用了什么方法？ 逐渐开发你自己的util包？
我避免在Mathematica中创建自己的数据结构，因为它无法有效地处理它们。 具体而言，Mathematica中的一般数据结构往往比其他地方慢10至1000倍，这极大地限制了它们的实用性。 例如，在计算红黑树的深度范围时，Mathematica比F＃慢100倍。
使用列表进行逻辑编程是Mathematica比其他编译语言慢一个数量级的例子。 以下Mathematica程序使用链表来解决n皇后问题：
safe[{x0_, y0_}][{x1_, y1_}] :=
x0 != x1 && y0 != y1 && x0 - y0 != x1 - y1 && x0 + y0 != x1 + y1
filter[_, {}] := {}
filter[p_, {h_, t_}] := If[p[h], {h, filter[p, t]}, filter[p, t]]
search[n_, nqs_, qs_, {}, a_] := If[nqs == n, a + 1, a]
search[n_, nqs_, qs_, {q_, ps_}, a_] :=
search[n, nqs, qs, ps,
search[n, nqs + 1, {q, qs}, filter[safe[q], ps], a]]
ps[n_] :=
Fold[{#2, #1} &, {}, Flatten[Table[{i, j}, {i, n}, {j, n}], 1]]
solve[n_] := search[n, 0, {}, ps[n], 0]
这是等效的F＃：
let safe (x0, y0) (x1, y1) =
x0<>x1 && y0<>y1 && x0-y0<>x1-y1 && x0+y0<>x1+y1
let rec filter f = function
| [] -> []
| x::xs -> if f x then x::filter f xs else filter f xs
let rec search n nqs qs ps a =
match ps with
| [] -> if nqs=n then a+1 else a
| q::ps ->
search n (nqs+1) (q::qs) (filter (safe q) ps) a
|> search n nqs qs ps
let ps n =
[ for i in 1..n do
for j in 1..n do
yield i, j ]
let solve n = search n 0 [] (ps n) 0
solve 8
解决8皇后问题需要Mathematica 10.5和F＃0.07s。 所以在这种情况下，F＃比Mathematica快150倍。
堆栈溢出问题Mathematica“链接列表”和性能给出了一个更极端的例子。 将该Mathematica代码简单地转换为F＃可以提供等效的程序，其运行速度比Mathematica快4,000到200,000倍：
let rand = System.Random()
let xs = List.init 10000 (fun _ -> rand.Next 100)
Array.init 100 (fun _ ->
let t = System.Diagnostics.Stopwatch.StartNew()
ignore(List.length xs)
t.Elapsed.TotalSeconds)
具体来说，Mathematica需要0.156s到16s来执行一次迭代，而F＃则需要42μs到86μs。
如果我真的想留在Mathematica中，那么我会对Mathematica的一些内置数据结构（例如Dispatch 。