4

作为一个学习项目，我正在努力用一个 Chapel 实现来替换 perl 中一个有点慢的程序。我已经掌握了算法，但我正在努力寻找引用 Chapel 中数据的最佳方式。我可以直接翻译，但似乎我错过了更好的方法。

现有计划详情：

  • 我有一个包含约 32000 个节点和约 210 万条边的图。状态保存在数据文件中，但它作为守护进程运行，将数据保存在内存中。
  • 每个节点都有一个数字 ID（由另一个系统分配），并具有由字符串、整数和布尔值定义的各种其他属性。
  • 边缘是有方向的，并且有几个布尔值归因于它们。
  • 我有一个与我无法更改的守护进程交互的外部系统。它发出请求，例如“添加具有这些属性的节点 (int)”、“查找从节点 (int) 到节点 (int) 的最短路径”或“从节点 (int) 添加边到节点 (int,整数，整数）”

在 Perl 中，该程序使用具有公共整数 ID 的散列来表示节点和边缘属性。我当然可以用关联数组在 Chapel 中复制它。

有没有更好的方法将这一切捆绑在一起？我一直在尝试围绕定义每个项目的不透明节点和边缘的方法来解决问题，但努力研究如何以简单的方式使用整数 ID 引用它们。

如果有人可以提供一种理想的方式来执行以下操作，它将为我提供所需的推动力。

  • 创建两个节点，其 xx 属性由整数 ID 标识。
  • 使用 xx 属性在两者之间创建一条边
  • 响应请求“显示节点（int）的xx属性”

干杯，谢谢。

4

1 回答 1

4

如您所料，在 Chapel 中有多种方法可以解决此问题，尽管我认为鉴于您的历史方法和外部系统的界面，关联域和数组绝对是一种合适的方法。具体来说，考虑到您希望通过整数 ID 引用节点，这使得关联域/数组成为自然匹配。

对于 Chapel 新手：关联域本质上是任意值的集合，就像本例中的整数节点 ID 集合。关联数组是从关联域的索引到给定类型的元素（变量）的映射。本质上，域表示键，数组表示键值存储或哈希表中的值。

为了表示节点和边本身，我将采用使用 Chapel 记录的方法。这是我的节点记录：

record node {
  var id: int;

  var str: string,
      i: int,
      flag: bool;

  var edges: [1..0] edge;
}

如您所见，它将其存储id为一个整数、各种类型的任意属性字段（一个字符串str、一个整数i和一个布尔值flag——您可能会为您的程序想出更好的名称），以及一个边数组，我一秒钟后会返回。请注意，每个节点可能需要也可能不需要存储其 ID……也许在您拥有该节点的任何上下文中，您已经知道它的 ID，在这种情况下存储它可能是多余的。我在这里存储它只是为了向您展示可以，而不是因为您必须这样做。

回到边缘：在你的问题中，听起来好像边缘可能有自己的整数 ID 并存储在与节点相同的池中，但在这里我采取了不同的方法：根据我的经验，给定一个节点，我通常想要从它引出的一组边，所以我让每个节点存储一个其传出边的数组。在这里，我使用了一个密集的一维边数组，它最初是空的（1..0在 Chapel 中是一个空范围，因为1 > 0）。如果你想给每个边一个唯一的 ID，你也可以使用一个关联的边数组。或者您可以完全从节点数据结构中删除边并将它们全局存储。如果您更喜欢不同的方法，请随时提出后续问题。

这是我表示边缘的记录：

record edge {
  var from, to: int,
      flag1, flag2: bool;
}

前两个字段 (from和to) 表示边连接的节点。与上面的节点 ID 一样，该from字段可能是多余的/不必要的，但为了完整起见，我将其包含在此处。这两个标志字段旨在表示您将与边缘关联的数据属性。

接下来，我将创建关联域和数组来表示节点 ID 集和节点本身：

var NodeIDs: domain(int),
    Nodes: [NodeIDs] node;

这里，NodeIDs是表示节点的整数 ID 的关联域（集）。 Nodes是一个关联数组，它从这些整数映射到类型值node（我们在上面定义的记录）。

现在，转向您的三个操作：

创建两个节点，其 xx 属性由整数 ID 标识。

以下声明n1使用 Chapel 为未定义自己的记录提供的默认记录构造函数/初始化程序创建了一个节点变量，该变量以一些任意属性命名：

var n1 = new node(id=1, "node 1", 42, flag=true);

然后我可以将它插入到节点数组中，如下所示：

Nodes[n1.id] = n1;

此分配有效地添加n1.id到NodeIDs域并复制n1到 中的相应数组元素中Nodes。这是一个创建第二个匿名节点并将其添加到集合中的分配：

Nodes[2] = new node(id=2, "node 2", i=133);

请注意，在上面的代码中，我假设您要明确选择每个节点的 ID（例如，也许您的数据文件建立了节点 ID？）。另一种方法（此处未显示）可能是在使用全局计数器创建节点时自动确定它们（如果您正在并行创建它们，则可能是原子计数器）。

填充完节点后，我们可以串行或并行迭代它们（这里我是并行执行的；替换forall为for将使它们串行）：

writeln("Printing all node IDs (in an arbitrary order):");
forall nid in NodeIDs do
  writeln("I have a node with ID ", nid);

writeln("Printing all nodes (in an arbitrary order):");
forall n in Nodes do
  writeln(n);

这些循环打印 ID 和节点的顺序是任意的，原因有两个：（1）它们是并行循环；(2) 关联域和数组以任意顺序存储它们的元素。

使用 xx 属性在两者之间创建一条边

node由于我将边与节点相关联，因此我采用了在将向其添加边的类型上创建方法的方法：

proc node.addEdge(to: int, flag1: bool, flag2: bool) {
  edges.push_back(new edge(id, to, flag1, flag2));
}

此过程将目标节点 ID 和属性作为其参数，使用该信息创建一条边（并将源节点的 ID 作为from字段提供），并使用push_back()矩形数组上的方法将其添加到边列表中。

然后我调用此例程三次，为节点 2 创建一些边（包括冗余和自边，因为到目前为止我只有两个节点）：

Nodes[2].addEdge(n1.id, true, false);
Nodes[2].addEdge(n1.id, false, true);
Nodes[2].addEdge(2, false, false);

此时，我可以遍历给定节点的所有边，如下所示：

writeln("Printing all edges for node 2: (in an arbitrary order):");
forall e in Nodes[2].edges do
  writeln(e);

这里，任意打印顺序只是由于使用了并行循环。如果我使用串行for循环，我将按照添加的顺序遍历边缘，因为使用一维数组来表示它们。

响应请求“显示节点（int）的xx属性”

您现在可能已经知道了，但是我可以通过索引Nodes数组来获得节点的任意属性。例如，表达式：

...Nodes[2].str...

会给我节点 2 的字符串属性。这是我编写的一个小助手例程，用于获取（并打印）一些不同的属性）：

proc showAttributes(id: int) {
  if (!NodeIDs.member(id)) {
    writeln("No such node ID: ", id);
    return;
  }

  writeln("Printing the complete attributes for node ", id);
  writeln(Nodes[id]);

  writeln("Printing its string field only:");
  writeln(Nodes[id].str);
}

这里有一些调用它：

showAttributes(n1.id);
showAttributes(2);
showAttributes(3);

我正在努力用 Chapel 实现替换 perl 中一个有点慢的程序

鉴于速度是您查看 Chapel 的原因之一，一旦您的程序正确，请使用--fast标志重新编译它以使其快速运行。

于 2017-09-14T17:41:34.573 回答