распределение Уменьшения памяти C++

Question

У меня есть проблемы придумывают с хорошей стратегией для уменьшения выделения памяти для следующей задачи:

Я построение дерева. В начале у меня есть только корень, который содержит некоторые данные (список (std::vector) индексов). Я разделяю две части, где часть индексов переходит к левому ребенку, а другая часть идет вправо. Я не знаю, сколько будет идти влево/вправо. Однажды, я закончил обработку корня, мне больше не нужно хранить индексы для него. На самом деле, меня интересуют только те, у кого есть листья. Кроме того, дополнительные данные могут быть добавлены в каждый раскол! Итак, если корень имеет 20 элементов, то после разделения левый может иметь 12 элементов и правый. 10.

В каждом узле я сохраняю std::vector, который содержит эти индексы. Когда я добавляю элементы, I 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(); 

} 

Answer 1

Если каждый узел должен поддерживать сам список динамического, то вы можете использовать std::vector::reserve() перед вызовом всех этих push_back() с.

Если, однако, вся длина определена после того, как вы установили корень, и этот начальный вектор остался неизменным, а затем вы просто «разделили его» между каждым узлом, тогда сами узлы могут просто удерживать указатели на данные внутри начальный вектор —, тем самым устраняя почти все распределения вокруг этой структуры данных.

Answer 2

В принципе, если вы не можете reserve векторы на основе некоторых эвристик, вы пали жертвой Schlemiel's algorithm (мягкий вариант, хотя, потому что геометрический рост обеспечивает O (N) времени сложности на 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. Несмотря на то, что вам нужно повторять два индекса, тяжелый подъем (геометрические вычисления) выполняется исключительно в первом цикле.