自己参照フィールドを含むMPIで構造を作成するにはどうすればよいですか？

Question

私はそれ自身の中から構造を参照することができる必要があるバイナリツリーを作成したいと思います。

ツリーは私はMPIでこれを行うことができますどのようにフォーム

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

のでしょうか？

Answer 1

MPIにはポインタ型はありません。意味がありません。 MPIプロセスはアドレス空間を完全に分離しているため、別のランクに転送するとポインタが無駄になります。

分散コンピューティングに関しては、データ構造を根本的に再考する必要があります。私は、この問題についての詳細をあまり詳しく述べない限り、一般的な勧告を出すことはできません。

Answer 2

この種の質問はここではa lotとなります。私たちはおそらく正規の質問を書くべきです。

Zulanが指摘しているように、ポインタはメモリが割り当てられたプロセス外では意味がありませんので、一般的にはできません。 MPIについては忘れて、単にデータをディスクに書き込むことを想像してください。ポインタ値だけでは、ツリー構造を再構築する助けにはならないでしょう。

しかし、ツリー構造とグラフ構造は非常に便利で、分散メモリコンピューティングでも広く使用されているため、（ネットワークを介して他のプロセスやディスクに）相対的にシリアル化できるデータを表現する方法が必要です効率的なのユースケース。

高さ（グラフの度合いなど）が変更された構造が非常に動的な場合、リンクされたツリータイプの表現でデータをメモリに保持し、送信する必要があるチャンクをシリアル化する必要に応じて配列を作成します。一方、ツリーの構造が比較的安定していれば、計算のためにもデータを配列表現に保つことが理にかなっています。

いずれにしても、意味のある方法でデータをシリアル化できる必要があります。バイナリツリーを使用する場合は、次の点を考慮してください。

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

これを線形配列で表現するにはいくつかの方法があります。どちらが最善かは、必要なものによって決まります。

まず、完全なバイナリツリー（すべての2 ^（高さ+1）-1ノード）を表すか、存在するノードのみを表すかどうかを決定する必要があります。サブツリーの端。最初は高速でスペース効率が良いの場合あなたのツリーは完全でバランスがとれていて、明示的に子ノードまたは親ノードのインデックスを計算できるという利点があります。効率的であれば効率的ですが、明示的な計算上の利点が失われます。 （これらの長所と短所は、密度の高い行列と疎な行列表現とでは同じですが、これは一般的なトレードオフです）。以下では、完全なバイナリツリーを表現していないと仮定しています。

次に、ツリー内の位置を配列の線形次数の位置に変換する方法を決定する必要があります。標準的な表現は、プリオーダーです：

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

かで次

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

またはポストオーダー

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

3の周りにそれらを送信するために素敵である、連続したサブツリーを保ちます;プレオーダーは、サブツリーを簡単に見つけることができるため、多くのアプリケーションで便利ですが、使用する順序は、使用する順序/データを検索する順序と一致する必要があります。

しかし、完全対疎な表現、線形順序を計算する方法、および配列表現を計算のネイティブ表現として使用するかどうかは、コミュニケーションのためにその表現に単にシリアライズするだけですあなたはどのように構造を使うのでしょうか。