7

特定のアルゴリズムをテストするためのテスト プラットフォームをコーディングする必要があります。システムは、入力と 3 次元によって定義可能であると想定されています。ネットワーク オン チップと同様に、それらを接続するためのノードとリンクの両方の要素があります。ノード間の次元とリンクのために、どのデータ構造を使用するかを理解するのに苦労しました - array[x][y][z] のような 3 次元配列は、リンクを追加するときに欠点のあるポインターとして扱いにくいです。ノードを接続します (構造内にいくつかの null 値の穴を残します)。二分探索木はグリッド型なので実現が難しいです。このため、リンクを実装しやすいリンクリストを作成することを考えました。(最終的なテスト プラットフォームは、以下のプレゼンテーションのようなものになるはずです) ここでは、通信スケジュールが含まれているため、すべてのリンクもマッピングされています。

01-------02-------03
| \      | \      | \
|  10----|--11----|--12
|  | \   |  | \   |  | \
|  |  19-|--|--20-|--|--21
04-------05-------06 |  |
| \   |  | \|  |  | \|  |
|  13----|--14----|--15 |
|  | \|  |  | \|  |  | \|
|  |  22-|--|--23-|--|--24
07-------08-------09 |  |
  \|  |    \|  |    \|  |
   16-------17-------18 |
     \|       \|       \|
      25-------26-------27

この種のタスクに適した C++ の構造のタイプについて、どなたか助けていただけないでしょうか。完成したプログラムは、x、y、z の次元パラメーターが与えられると、そのような構造を生成できるはずです。

現在、大まかなアウトラインは次のようになります

>class Node{
>  public:
>   Link* north;
>   Link* east;
>   Link* south;
>   Link* west;
>   Link* up;
>   Link* down;
>   //will contain a node specific scheduler
>}
>
>class Link{
>
>   Node* A;
>   Node* B;
>   //will contain a link specific scheduler
>}

編集 22.01.2013

まず第一に、3 次元ネットワーク オン チップ タイプのマルチプロセッサ システムをシミュレートするテスト プラットフォームとして。このシステムが満たさなければならないタスクは、特定のアルゴリズムをテストして、タスクをこれらのノード (各ノードがプロセッサ コアに接続されている場所) にマップできるようにすることです。これに照らして、私が述べたようにテスト専用であるため、メモリ消費は問題にならない可能性があります。このため、システムにはノードとリンクの両方が必要です。同時に（リンク上の通信は他のすべての通信をブロックします。これが、クラスタイプのノード/リンクにスケジューラーが含まれると書いた理由です）

4

1 に答える 1

11

それは、その構造に対して実行する操作の種類に大きく依存します。検索を行う必要がありますか? もしそうなら、価値ベースかポジションベースか？それに変換を実行する必要がありますか？すべての要素に繰り返し、順番にアクセスする必要がありますか? グリッド内の位置に基づいて要素にアクセスする必要がありますか? あなたの構造はまばらですか、それとも密ですか？

さらに、作成時間、検索時間、ナビゲーション時間、または変換時間を最小限に抑えたいですか? これはすべて、決定を下すための基本的な情報を提供します。

次のような理由から、ノードとリンクに基づくソリューションには行きません。

  1. メモリ消費の点で高価です(余分なリンク ポインターのため)。
  2. 複雑さの点で高価です（すべてのノードをナビゲートするにはすべてのリンクをたどる必要があるため、ランダムアクセスはありません）。
  3. データ局所性の点で高価です(ノードは個別に割り当てられ、ヒープ全体の個別のアドレスに分散されます。これにより、多くのキャッシュ ミスが発生し、プログラムが遅くなります)。
  4. エラーが発生しやすい(特に、生のポインターを使用していて、スマート ポインターのメモリ オーバーヘッドを負担したくない場合は、リンクを台無しにするのは簡単です)

要件についてあまり知らなくても、Boost.MultiArrayをご覧になることをお勧めします。

自分で物事をやりたい場合は、(要件についてあまり知らずに) を使用することをお勧めしますvector<vector<vector<double>>>。これは比較的単純で、サイズが固定されておらず、実行時にサイズを変更できるため、添え字演算子を介した O(1) アクセスと、データの局所性 (ここには複数のベクトルがあるため、 1 つのベクトルからデータにアクセスする限り、パフォーマンスは問題ありません)。

単純な C スタイルの多次元配列も可能ですが、本質的に安全ではないため、私があなたの場合は最後の手段になります (また、構造が巨大な場合、連続したメモリ ブロックを割り当てることは不可能かもしれません)。 .

于 2013-01-21T15:47:28.623 に答える