wolfram-mathematica - Mathematica 中的树数据结构

Question

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

现在我的问题:

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

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

(不是一个问题，只是一个评论。也许......缺乏(很多可用的)开源包是 Mathematica 没有应有的势头的原因。恐怕是先有鸡还是先有蛋的问题。)

Answer 1

在 Mathematica 中，您所做的大部分工作都是基于表达式。表达式自然具有树结构。对于深度优先遍历(这可能是最常见的)，您可以使用像 Scan 这样的函数。 , Map , Cases等等。与更传统的语言的区别在于，没有简单的方法来保存表达式树中单个节点的身份，因为 Mathematica 中没有指针。此外，当您只需要在几个地方修改它时，对 Mathematica 中惯用的表达式的许多操作会复制整个表达式，因为表达式是不可变的。

使用不可变的 Mathematica 表达式作为树仍然有几个优点。一个是，因为它们是不可变的，只需查看它们就很容易理解它们存储的内容(状态和行为不是混合的)。另一个是有高效通用的功能如Map , MapIndexed或 Scan ，遍历它们。例如，访问者设计模式是 invisible - 只是Map[f,tree,Infinity] , 内置于语言中。此外，还有 Cases 等内置函数。 , Replace , ReplaceAll等，它允许人们编写非常简洁和声明性的代码来解构树，找到具有特定语法或满足某些条件的树的片段等。由于树不仅限于从列表构建和从不同的头部构建，一个可以有效地使用它来编写非常简洁的树处理代码。最后，本着 exploratory and bottom-up programming 的精神，可以非常轻松地构建您想要的任何树状结构的自由使得进行实验和原型(prototype)事物变得更加容易。 ，这缩短了开发周期并最终导致更好的设计。

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

关于在 Mathematica 中实现包含一些状态的数据结构的一般方法，这里是从我在 this 中的帖子中提取的一个简单示例。 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.m Roman Maeder 的包(来源在他的“Mathematica Programmer”一书中)， Objectica商业包，以及其他几个。但是，除非 Mathematica 本身提供有效的机制(可能基于某种指针或引用机制)来构建可变数据结构(如果发生这种情况)，否则可能会出现与此类数据结构的顶级实现相关的巨大性能损失在 mm。此外，由于 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

有关使用这种可变树数据结构的一个重要示例，请参阅 this我的帖子。它还将这种方法与更大量重用 Mathematica 原生数据结构和函数的方法进行了对比，并很好地说明了本文开头讨论的要点。