3

私は、4 次元データ、つまり 3D 空間内の位置にあるいくつか (3 ～ 30) の変数を使用する心臓シミュレーション ツールに取り組んでいます。

現在、シミュレートする組織の外側にある 3D ボックス内のポイントの 2/3 以上を残す組織ジオメトリを追加しているため、他のポイントではなくアクティブなポイントを効率的に保存する方法が必要です。

重要なのは、次のことができる必要があることです。

  • 制約された 3D ボックス内のすべてのアクティブ ポイントを反復処理します (イテレータ、おそらく?)
  • 1 つの点にアクセスしたら、その直交する近傍 (x、y、z) +/- 1 を見つけます。

それはおそらく複数の質問です！私の主な関心事は、まばらなデータを効率的に表現する方法です。

私はCを使用しています。

4

3 に答える 3

5

どのくらいの頻度でティッシュを追加し、どれくらいの時間がかかりますか?

1 つの簡単な解決策は、一方から他方へのポインタを含むリンク リスト + ハッシュを使用することです。

意味：

  1. 関連するすべてのポイントとそのデータを含むリンクされたリストを保存します
  2. このデータに簡単にアクセスできるようにハッシュを保存します: キー = 座標、データ = リンクされたリストへのポインター。

操作の実装は次のようになります:
ボックスの追加:完全な連結リストを調べ、関連する要素のみを "作業" 連結リストに取り込みます。
反復:
"作業" 連結リストを調べます。ハッシュで。

複雑さ:
追加: O(n)、次の要素を見つけるために O(1) を反復、隣接 O(1) 平均 (ハッシュによる)。

于 2009-08-12T11:33:42.680 に答える
2

単純な配列インデックスを使用する場合は、mmap() を使用して POSIX システムで疎配列を作成できます。

float (*a)[500][500];

a = mmap(0, (size_t)500 * sizeof a[0], PROT_READ | PROT_WRITE,
    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

if (a && (void *)a != MAP_FAILED)
{
    /* a is now 500 x 500 x 500 sparse array of floats */

次に、好きなように a[x][y][z] にアクセスするだけで、実際には、アクセスされた各ページに実際のメモリのみが割り当てられます。配列はゼロバイトに初期化されます。

システムに MAP_ANONYMOUS がない場合は、/dev/zero からマッピングすることで同じ効果を得ることができます。

多くのシステムでは、スワップ領域が (使用されていなくても) アレイ全体のために予約されていることに注意してください。

于 2009-08-12T14:04:19.477 に答える
1

まず、あなたの本当の要件が何であるかを検討する価値があると思います。「できるだけスペース効率の良い方法でアクティブなポイントを保存し、他のポイントを保存しない」だけでなく、ある程度の「隣接するポイントを近くのメモリ位置に保存して、適切なキャッシュ動作が得られるようにする」こともあると思います。 「検索が効率的にできるようにポイントを保存する」。

そうは言っても、ここに私が提案するものがあります。完全な 3D 領域をすべて同じサイズの立方体ブロックに分割します。ブロックごとに、ブロック内のすべてのポイントを密な配列に格納します。これには、各ポイントが組織領域内にあるかどうかを表すブール値の isTissue 配列が含まれます。ポイントを含むブロックのみを割り当てます。割り当てられていないブロックの NULL ポインターを使用して、ブロックへのポインターの (密な) 配列を作成します。

したがって、(i,j) のポイントを見つけるには、まず ii=i/ブロックサイド、jj=j/ブロックサイズを計算し、次に (ii,jj) のブロックへのポインター テーブルを調べて、次のブロックを見つけます。あなたのポイントが含まれています。そのポインターが NULL の場合、ポイントは組織内にありません。null でない場合は、そのブロックの (i mod blocksize, j mod blocksize) を見て、(i,j) ポイントがあります。その isTissue フラグをチェックして、それが「現在」のポイントかどうかを確認できます。

ブロックの境界を越える隣接点の計算を行う回数を最小限に抑えることと、ブロック内にあって組織領域には含まれない点の数を最小限に抑えることとの間のバランスとして、ブロック サイズを選択する必要があります。少なくとも、ブロックの行をキャッシュラインの長さにする必要があると思います。おそらく、最適値はそれよりもかなり大きいですが、ジオメトリによっては多少異なります。

3D ボックス内のすべてのポイントを反復処理するには、各ポイントのルックアップを行うか、(より効率的に) ボックスが接触しているブロックを特定し、ボックス内にあるブロック内の領域を反復処理して、 isTissue が false のもの。

ブロックの割り当て解除と再割り当てを頻繁に行っている場合は、ブロックを「未使用」プールにドロップしてブロックを「割り当て解除」し、ブロックを再割り当てするのではなく、そのプールからブロックを引き出すことをお勧めします。これには、これらのブロックのすべてのポイントが既に「存在しない」に設定されているという利点もあります (ブロックの割り当てを解除したため)。したがって、それらを初期化する必要はありません。

経験豊富な読者は、これと並列計算用のデータをレイアウトする方法との類似点に気付くでしょう。非常に大きなシミュレーションの場合、ブロックを複数のノードに簡単に分散でき、ブロック間の計算のためにノード間通信を行うだけで済みます。この種のアプリケーションでは、(ジオメトリ用の) 小さいブロックを含むメタ ブロック (クロスノード通信用) がある場合、ネストされたレベルのブロックを実行すると便利な場合があります。

于 2009-08-12T19:11:53.750 に答える