2

次の問題のメモリ割り当てを減らすための適切な戦略を考え出すのに苦労しています:

ツリーを作成中です。std::vector最初は、いくつかのデータ (インデックスのリスト ())を含むルートしかありません。インデックスの一部が左の子に、残りの部分が右の子に移動する 2 つの部分に分割します。左/右にいくつ行くかわかりません。ルートの処理が完了すると、ルートのインデックスを保存する必要がなくなります。実際、私は葉のものだけに興味があります。さらに、分割ごとにデータを追加可能！したがって、ルートに 20 個の要素がある場合、分割後、左の要素は 12 個、右の要素は 10 個になる可能性があります。

各ノードで、std::vectorこれらのインデックスを含む を保持します。要素を追加するとき、push_back()多くのメモリ割り当てにつながる要素です。

インデックスを維持するための良い戦略は何ですか?

この質問は、SBVH データ構造の生成に関連しています。

コード：

struct Node {
     std::vector<unsigned> indices_;
     // ... some other stuff here
}
void partition(Node* node) {
    Node* left = new Node();
    Node* right = new Node();
    float axis = findSplitPosition(node);

    for(size_t i = 0; i < node->indices_.size(); ++i) {
        if (index is strictly left on axis) {
            left->indices_.push_back(node->indices_[i]);
        } else if(index is strictly right on axis) {
            right->indices_.push_back(node->indices_[i]);
        } else {
            // it intersects the axis -> add to left and right
            left->indices_.push_back(node->indices_[i]);
            right->indices_.push_back(node->indices_[i]);
        }
    }

    // root indices no longer needed
    node->indices_.clear();

}
4

2 に答える 2

3

各ノードが動的std::vector::reserve()リスト自体を維持する必要がある場合は、それらすべてを呼び出す前に使用できますpush_back()。

ただし、ルートを設定すると全体の長さが決定され、その初期ベクトルは変更されず、各ノード間で「分割」するだけで、ノード自体は初期ベクトル内のデータへのポインターを単純に保持できます—これにより、このデータ構造に関するほぼすべての割り当てが不要になります。

于 2016-02-09T12:53:54.533 に答える
0

reserve基本的に、いくつかのヒューリスティックに基づいてベクトルを取得できない場合は、シュレミエルのアルゴリズムのn犠牲になります (幾何学的成長により、O (n^2) ではなく連続挿入でO(n) 時間の複雑さが保証されるため、より穏やかなバージョン)。

ただし、最初にノードのインデックスを調べて、指定されたインデックスが左側のサブノード、右側のサブノード、またはその両方に移動する必要があるかどうかを記録すると、一定数の割り当てを回避できます。また、左右のサブノードのインデックス数を追跡します。

struct Foo {
    bool goesIntoLeft;
    bool goesIntoRight;
};

std::vector<Foo> foo;
foo.reserve(node->_indices.size());
int leftCount = 0;
int rightCount = 0;
for (auto i = 0; i < node->_indices.size(); ++i) {
    if (index goes into left) {
        foo.push_back({ true, false });
        ++leftCount;
    } else if (index goes into right) {
        foo.push_back({ false, true });
        ++rightCount;
    } else { // goes into both
        foo.push_back({ true, true });
        ++leftCount;
        ++rightCount;
    }
}

std::vector<Node> leftNodes;
leftNodes.reserve(leftCount);
std::vector<Node> rightNodes;
rightNodes.reserve(rightCount);

for (auto i = 0; i < node->_indices.size(); ++i) {
    if (foo[i].goesIntoLeft) leftNodes.push_back(nodes._indices[i]);
    if (foo[i].goesIntoRight) rightNodes.push_back(nodes._indices[i]);
}

fooこの方法では、 、leftNodes、 の3 つの割り当てのみを行いますrightNodes。インデックスを 2 回反復処理する必要がありますが、手間のかかる作業 (幾何学的計算) は最初のループでのみ行われます。

于 2016-02-09T13:23:44.117 に答える