我如何在 MPI 中创建一个包含自引用字段的结构？

Question

我想创建一个二叉树，为此我需要能够从自身内部引用结构。

树的形式是

    struct tree
    {
     int val; 
     struct tree *lchild, *rchild;
    };

我如何在 MPI 中执行此操作？

Answer 1

MPI 中没有指针类型 - 它没有任何意义。 MPI 进程具有完全独立的地址空间，因此指针在转移到另一个级别时将毫无用处。

您应该从根本上重新考虑与分布式计算相关的数据结构。如果没有关于该问题的更多详细信息，我无法给出一般性建议。

Answer 2

这里 a lot 出现了这种问题，以至于我们可能应该尝试写一个规范的问题。

正如 Zulan 指出的那样，指针在分配内存的进程之外没有意义，因此通常无法做到这一点。暂时忘掉 MPI，想象一下将数据写入磁盘 - 指针值本身对重建树结构没有任何帮助。

但是树和图结构非常有用，甚至在分布式内存计算中也被广泛使用，因此您需要一种表示可以序列化（通过网络到另一个进程或磁盘）的数据的方法，即相对高效 for your use-case.

如果您的结构非常动态 - 包括高度（或度数，对于图形）变化 - 将数据保存在 linked-tree 类型表示的内存中并仅序列化需要的块可能是有意义的在需要时被发送到一个数组中。另一方面，如果树的结构保持相对稳定，即使在计算中也将数据保留在数组表示中可能是有意义的。

无论哪种方式，您都需要能够以某种有意义的方式序列化数据。坚持二叉树，考虑以下几点：

            A
           / \
          /   \
         B     E
        / \   / \
       C   . .   F
      / \       / \
     D   .     .   .
    / \
   .   .

您可以通过多种方式在线性数组中表示它；哪个最好看你需要什么。

首先，您必须决定是表示完整的二叉树（所有 2^(height+1)-1 个节点）还是仅表示那些存在的节点，树的末尾有显式空节点表示子树的末端；第一个更快并且更 space 高效如果你的树将接近完整和平衡，并且具有能够显式计算 [= 的索引的优势54=] 或 parents 给定节点索引，其中第二个更 space 有效，如果不是，但您失去了显式可计算性优势。（这些优缺点对于密集矩阵表示与稀疏矩阵表示是相同的；这是一组常见的权衡）。在下面，我假设您不代表完整的二叉树。

然后你要决定如何将树中的位置转换为数组的线性顺序的位置；规范表示是 pre-order:

A B C D . . . . E . F . .

或in-order

. D . C . B . A . E . F .

或post-order

. . D . C . B . . . F E A

这三个子树保持连续，这很适合发送它们； pre-order 对于很多应用程序来说都很好，因为它可以很容易地找到子树，但是您使用的顺序应该与您 using/searching 数据的顺序相匹配。

但各种选择的最佳决策 - 完整表示与稀疏表示、计算线性排序的方法，以及是否使用数组表示作为计算的本机表示与仅序列化到该表示以进行通信 - 全部归结为您将如何使用这些结构。

我如何在 MPI 中创建一个包含自引用字段的结构？

How can i create a structure in MPI, that contains self referential fields?

tree

mpi

self-reference