Mathematica中的树数据结构
我主要使用mathematica作为math工作台，编写相对较小的特定程序。 然而，我正在devise一个我打算在Mathematica中编程的系统。 我需要将数据存储在树中，然后search并遍历树。 虽然我知道如何实现树，但我更喜欢标准的，经过testing的代码。 我查看了Mathematica用户维基上的基本数据结构。 尽pipeMathematica文档中有一个小例子，但我没有find。
现在回答我的问题：
-
有什么地方可用的数据结构的（开源）包？
-
你用什么方法来处理数据结构？ 逐渐开发你自己的util包？
（这不是一个问题，只是一个说法，也许…缺乏（很多可用的）开源软件包是Mathematica没有应有的动力的原因。恐怕鸡鸡蛋问题。
在Mathematica中，你所做的大部分工作都是基于expression式的。 expression式自然具有树形结构。 对于深度优先遍历（可能是最常见的），您可以使用Scan ， Map ， Cases等function。与传统语言不同的是，没有简单的方法来保存expression式中单个节点的标识树，因为在Mathematica中没有指针。 此外，在Mathematica中，对于惯用语言的expression式的许多操作都会复制整个expression式，因为expression式是不可变的，因此只需在几处修改即可。
使用不可变的Mathematicaexpression式作为树仍然有几个优点。 一个是因为它们是不变的，所以只要看看它们就可以很容易地理解它们存储的内容（状态和行为不是混合的）。 另一个是有效的通用函数，如Map ， MapIndexed或者Scan ，遍历它们。 例如，访客devise模式是不可见的 – 它只是内置在语言中的Map[f,tree,Infinity] 。 另外，还有一些内置函数，例如Cases ， Replace ， ReplaceAll等等，它们允许编写非常简洁的声明性代码来解构树，find具有一定语法或满足某些条件的树。由于树不是只能从列表中构build，并且从不同的头部构build，可以有效地使用它来编写非常简洁的树处理代码。 最后，根据探索性和自下而上的编程精神，您可以非常轻松地构build任何所需树形结构，从而更容易地进行实验和原型制作 ，缩短了开发周期，最终实现了更好的devise。
这就是说，你当然可以实现“有状态”（可变）的树形数据结构。 我怀疑，构build，修改和遍历这样一棵树所带来的性能问题，一般还没有完成的真正原因，因为它将在每一步都经历一个完整的符号化评估过程。 ）。 举例来说，举例来说，一个二进制search树可以在Mathematica上下文中用于相当有效的代码，请参阅我的post（通用符号设置）和这里 （在编译代码的上下文中）。 对于在Mathematica中通常构build数据结构的一般方法，我推荐Roman Maeder的书籍：“Mathematica编程”，“Mathematica编程人员I和II”，特别是“Mathematica计算机科学”。 在后者中，他详细讨论了如何在Mathematica中实现二叉search树。 编辑 @Simon提到，@Daniel Lichtblau的谈话也是一个很好的资源，它展示了如何构build数据结构并使其高效。
关于在Mathematica中实现数据结构的一般方法，它将包含一些状态，下面是一个在Mathgroup线程中从我的post中提取的简单例子 – 它实现了一个“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}
创build一个新的对象列表：
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}
我在后面提到的是更详细的讨论。 以这种方式创build的“对象”的一个大问题是没有自动垃圾收集，这可能是为什么顶级Mathematica本身实现的OOP扩展并没有真正起飞的主要原因之一。
Mathematica有几个OOP扩展，例如Roman Maeder的classes.m包（源文件在他的“Mathematica编程器”一书中）， Objectica商业包和其他几个。 但是，除非Mathematica本身能够为构build可变数据结构（如果这种情况发生）提供有效的机制（可能基于某种指针或引用机制），否则可能会有与此类数据结构的顶级实现相关的巨大性能下降在妈妈。 而且，由于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作为math工作台，编写相对较小的特定程序。
Mathematica真的擅长于此。
你用什么方法来处理数据结构？ 逐渐开发你自己的util包？
我避免在Mathematica中创build自己的数据结构，因为它无法有效地处理它们。 具体而言，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 fx 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.5s和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＃则需要42s到86s。
如果我真的想留在Mathematica中，那么我就会把Mathematica的一些内置数据结构（例如Dispatch所有东西进行鞋拔。
