1

バーンズハットのN体シミュレーションを実行したい（ウィキペディアの記事）。octreeの単一ノードが占めるメモリの量はわかっていますが、特定の数のパーティクルに対して最悪の場合のメモリ使用シナリオがどうなるかはわかりません。要するに、与えられた数の粒子に対して、八分木にいくつのノードが存在する可能性があるのだろうかと思います。八分木に割り当てるメモリの量を知るには、これを知る必要があります。

編集：

ああ、そして誰かが私にただの説明の代わりにコードを与えたいのなら、私はCで書いています。

私はこれを持っていますが、これは最悪のシナリオよりもはるかに悪いです。ただし、少なくとも十分なメモリを割り当てることが保証されています。誰かが私にもう少しメモリ効率の良いものを与えてくれることを願っています。

int KBH_worstcase(int particles)
{ // returns number of nodes required to store a number of particles in a worst case scenario
    int worst;
    unsigned int n;
    worst=1;
    n=1;
    while(n<particles)
    {
        n=n<<3;
        worst+=n;
    }
    return worst;
}
4

2 に答える 2

2

そのような適切な基準が存在するかどうかはわかりません。八分木は、シミュレーション中に変化する可能性のある粒子分布を考慮に入れます。したがって、ツリーの有効な深さは、パーティクルの数だけに依存することはできません。

誤った解決策の1つは、ツリーの深さ（またはノードの数）の境界を定義することです。このような場合、より多くの粒子を1つのセル（八分木の葉）にグループ化し、体と体の相互作用にフォールバックすることができます。ただし、ツリー構造をより細かく制御したい場合は、必要に応じて新しいノードを割り当てる機能がある方がよいでしょう。

于 2012-09-03T17:53:11.233 に答える
0

実際、四分木（または3次元の八分木）に必要なノード数の上限は、粒子の総数の対数によって制限されません。

通常、ノード内のスペースは4つの等しい象限に分割されます。ルートノードのバウンディングボックスと比較して、2つのパーティクルが互いに非常に接近している場合を考えてみます。ここでは、単一のパーティクルでノードに到達する前に、多くの内部ノードを作成する必要があることが簡単にわかります。以下のスケッチを参照してください。

ここに画像の説明を入力してください

多くの内部ノード-2つのポイントのみ

代わりに、2次元の上限は（頭のてっぺん）になります。

log4 w / m

ここで、wはルートノードのバウンディングボックスのサイズであり、mは任意の2つのパーティクル間の最短距離です。

ただし、任意の2点間の最短距離を計算すると、O（n ^ 2）の複雑さが発生するため、回避する必要があります。

代わりに、アルゴリズムを変更して、ツリーを最大深度dまでのみ構築することができます。これにより、メモリ消費が4 ^（d + 1）-1ノードに制限されます。

また、単純なO（n ^ 2）アルゴリズムにフォールバックするなど、複数のパーティクルを含むノードとの相互作用を注意深く処理する必要があります。

于 2015-03-29T20:06:03.047 に答える