2

我很难想出一个好的策略来减少以下问题的内存分配：

我正在建造一棵树。一开始，我只有包含一些数据的根（std::vector索引列表（））。我分成两部分，其中一部分索引到左孩子，另一部分到右孩子。我不知道有多少人会去左/右。有一次，我完成了对根的处理，我不再需要为它存储索引。事实上，我只对那些叶子感兴趣。此外，可以在每次拆分时添加其他数据！所以，如果根有 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()s 之前使用。

但是，如果在设置根后确定了整个长度并且初始向量保持不变，然后您只是在每个节点之间“拆分”它，那么节点本身可以​​简单地保存指向初始向量内数据的指针——从而消除了几乎所有围绕这个数据结构的分配。

于 2016-02-09T12:53:54.533 回答
0

基本上，如果你不能reserve基于一些启发式的向量，你就会成为Schlemiel 算法的牺牲品（虽然是一个更温和的版本，因为几何增长确保了n连续插入的 O(n) 时间复杂度而不是 O(n^2)）。

但是，如果您首先检查节点的索引并记录给定的索引是否应该转到左子节点、右子节点或两者兼而有之，那么您可以摆脱恒定数量的分配。还要跟踪左/右子节点的索引计数：

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]);
}

这样你只做 3 次分配，即foo, leftNodes, rightNodes。尽管您必须对索引进行两次迭代，但繁重的工作（几何计算）仅在第一个循环中完成。

于 2016-02-09T13:23:44.117 回答