Mathematica中的树数据结构

Question

我主要使用mathematica作为数学工作台,并编写相对较小的ad-hoc程序.然而,我正在设计一个我打算在Mathematica中编程的系统.我需要将数据存储在树中,并搜索和遍历树.虽然我知道如何实现树,但我更喜欢标准的,经过测试的代码.我在Mathematica用户维基上查看了基本数据结构的类型.我没有找到,尽管Mathematica文档中有一个小例子.

现在问我的问题:

1. 是否有可用的数据结构(开源)包？

2. 您在数据结构方面使用了什么方法？逐步开发自己的util包？

(这不是一个问题,只是一个评论.也许......缺乏(大量可用的)开源软件包是Mathematica没有应有的动力的原因.我害怕鸡/蛋问题.)

Answer 1

在Mathematica中,你所做的大部分工作都是基于表达式.表达式自然具有树形结构.对于深度优先遍历(这可能是最常见的),然后你可以使用像功能Scan,Map,Cases等的差异WRT较为传统的语言是,有没有简单的方法,以保护个人节点的身份在一个表达式树,因为Mathematica中没有指针.此外,对于Mathematica中惯用的表达式的许多操作都会复制整个表达式,只需要在几个地方修改它,因为表达式是不可变的.

使用不可变的Mathematica表达式作为树仍然有几个优点.一个是因为它们是不可变的,只要看一下它们就很容易理解它们存储的东西(状态和行为并不混合).另一个是有效的通用功能,例如Map,MapIndexed或Scan遍历它们.例如,访客设计模式是不可见的 - 它只是Map[f,tree,Infinity]内置于语言中.另外,还有一些内置的功能,如Cases,Replace,ReplaceAll,等,允许一个写得很简洁,声明代码解构树,找到与某些语法或满足一定条件,等树木件由于树木不仅限于从列表构建并从不同的头构建,可以有效地使用它来编写非常简洁的树处理代码.最后,通过探索和自下而上编程的精神,可以非常轻松地构建您想要的任何树结构,从而更轻松地执行实验和原型设计,从而缩短开发周期并最终实现更好的设计.

也就是说,您当然可以实现"有状态"(可变)树数据结构.我怀疑,它通常尚未完成的真正原因是,与构建,修改和遍历这样一棵树相关的性能损失,因为它将在每一步都经历一个完整的符号评估过程(有关详细信息,请参阅此帖子) ).有关如何在Mathematica上下文中使用二进制搜索树以获得高效代码的2个示例,请参阅此处的帖子(通用符号设置)和此处(在编译代码的上下文中).对于在Mathematica中以惯用方式构建数据结构的一般方法,我推荐使用Roman Maeder的书:"Mathematica中的编程","Mathematica程序员I和II",特别是"Mathematica中的计算机科学".在后者中,他详细讨论了如何在Mathematica中实现二叉搜索树.编辑正如@Simon提到的,@Daniel Lichtblau的谈话也是一个很好的资源,它展示了如何构建数据结构并使其高效.

关于在Mathematica中实现数据结构的一般方法,它将包含一些状态,这里是从我的帖子中提取的一个简单示例,在这个 Mathgroup线程中 - 它实现了一个"对"数据结构.

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扩展,例如classes.mRoman Maeder 的包(源代码在他的"Mathematica Programmer"一书中),Objectica商业包和其他几个.但是,直到Mathematica本身提供有效的机制(可能基于某种指针或参考机制)来构建可变数据结构(如果这种情况发生),可能会出现与此类数据结构的顶级实现相关的大量性能损失在mma.此外,由于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本机数据结构和函数的对比,并且很好地说明了本文开头讨论的要点.

Answer 2

我主要使用mathematica作为数学工作台,并编写相对较小的ad-hoc程序.

Mathematica对此非常擅长.

您在数据结构方面使用了什么方法？逐步开发自己的util包？

我避免在Mathematica中创建自己的数据结构,因为它无法有效地处理它们.具体而言,Mathematica中的一般数据结构往往比其他地方慢10-1,000倍,这极大地限制了它们的实际用途.例如,在计算红黑树的深度范围时,Mathematica比F#慢100倍.

使用列表的逻辑编程是Mathematica通常比其他编译语言慢几个数量级的一个示例.以下Mathematica程序使用链表来解决n-queens问题:

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

使用Mathematica解决8-queens问题需要10.5s,使用F#需要0.07s.因此在这种情况下,F#比Mathematica快150倍.

Stack Overflow问题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.