Удалить на очень глубоком дереве

Question

Я строю набор суффиксов (к сожалению, нет времени для правильной реализации дерева суффиксов) для набора из 10 символов.Строки, которые я хочу проанализировать, будут довольно длинными (до 1М символов).Дерево строится без каких-либо проблем, однако я сталкиваюсь с некоторыми, когда пытаюсь освободить память после того, как с ней покончено.

В частности, если я настроил свой конструктор и деструктор как таковой (гдеCNode.child - это указатель на массив из 10 указателей на другие CNodes, а count - это простое целое число без знака):

CNode::CNode(){
    count = 0;
    child = new CNode* [10];
    memset(child, 0, sizeof(CNode*) * 10);
}

CNode::~CNode(){
    for (int i=0; i<10; i++)
        delete child[i];
}

При попытке удалить корневой узел я получаю переполнение стека.Возможно, я ошибаюсь, но я вполне уверен, что это происходит из-за слишком большого количества вызовов деструкторов (каждый деструктор вызывает до 10 других деструкторов).Я знаю, что это неоптимально как по пространству, так и по времени, однако предполагается, что это быстрое и грязное решение повторяющейся проблемы с подстрокой.

tl; dr :как можно освободить память, занятую очень глубоким деревом?

Спасибо, что уделили время.

Answer 1

Один из вариантов - выделить из большого буфера, а затем полностью освободить этот буфер.

Например (не проверено):

class CNodeBuffer {
    private:
        std::vector<CNode *> nodes;

    public:
        ~CNodeBuffer() {
            empty();
        }

        CNode *get(...) {
            CNode *node = new CNode(...);
            nodes.push_back(node);
            return node;
        }

        void empty() {
            for(std::vector<CNode *>::iterator *i = nodes.begin(); i != nodes.end(); ++i) {
                delete *i;
            }

            nodes = std::vector<CNode *>();
        }
};

Если указатель на std::vector элементы стабильны, вы можете сделать вещи немного проще и просто использовать std::vector<CNode>.Это требует тестирования.

Answer 2

Я думаю, что в этом случае может помочь очистка в ширину, если поместить всю информацию об обратном отслеживании в стэк, а не в предоставленный ОС стек.Это все еще не решит проблему создания этого деструктора.

Псевдокод:

void CNode::cleanup()
{
    std::deque<CNode*> nodes;
    nodes.push_back(this);
    while(!nodes.empty())
    {
        // Get and remove front node from deque.
        // From that node, put all non-null children at end of deque.
        // Delete front node.
    }
}

Answer 3

Вы собираетесь сделать довольно много удалений.Это займет много времени, потому что вы получите доступ к памяти очень случайным образом.Однако в этот момент вам больше не нужна древовидная структура.Следовательно, я бы сделал два прохода.В первом проходе создайте std::vector<CNode*> и reserve() достаточно места для всех узлов вашего дерева.Теперь вернитесь к дереву и скопируйте все CNode * в ваш вектор.На втором этапе сортируйте их (!).Затем на третьем шаге удалите их все.Второй шаг технически необязателен, но, вероятно, делает третий шаг намного быстрее.Если нет, попробуйте сортировку в обратном порядке.

Answer 4

Рассматривали ли вы просто увеличение размера вашего стека?

В visual studio вы делаете это с / FNUMBER, где NUMBER - размер стека в байтах.Вам также может потребоваться указать / STACK: резерв [, принятие].

Answer 5

Вы инициализируете память для самих узлов?Из того, что я вижу, ваш код выделяет память только для указателей, а не для фактических узлов.

Что касается вашего вопроса, попробуйте итерацию по дереву итеративным способом, а не рекурсивно.К сожалению, рекурсия плоха, она хороша только тогда, когда она на бумаге, а не в коде.