Какой самый быстрый способ десериализации дерева в C ++

Question

Я работаю с не такой маленькой древовидной структурой (это дерево Беркхарда-Келлера,> 100 МБ в памяти), реализованной на C ++. Указатели на дочерние элементы каждого узла хранятся в QHash.

Каждый узел x имеет n дочерних элементов y [1] ... y [n], ребра для дочерних элементов помечены с помощью расстояния редактирования d (x, y [i]), поэтому для хранения узлов используется хеш является очевидным решением.

class Node {
    int value;
    QHash<int, Node*> children;
    /* ... */
};

Я также хочу сериализовать и десериализовать его в файл (в настоящее время я использую QDataStream). Дерево просто строится один раз и не меняется тогда.

Построить дерево и десериализовать его довольно медленно. Я загружаю дерево очевидным способом: рекурсивно собирая каждый узел. Я думаю, что это неоптимально из-за множества узлов, которые создаются отдельно с помощью оператора new. Я где-то читал, что new довольно медленно. Первоначальная сборка не является большой проблемой, потому что дерево довольно стабильно и его не нужно перестраивать очень часто. Но загрузка дерева из файла должна быть максимально быстрой.

Какой лучший способ сделать это?

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

Но чтобы реализовать это, мне пришлось бы повторно реализовать QHash, AFAIK.

Что бы вы сделали, чтобы ускорить десериализацию?

Добавление

Спасибо за ваше предложение сделать некоторые профилирования. Вот результаты:

При восстановлении дерева из файла

 1 % of the time is consumed by my own new calls
65 % is consumed by loading the QHash objects (this is implemented by the 
     Qt Library) of each node
12 % is consumed by inserting the nodes into the existing tree
20 % is everything else

Так что, определенно, не мои новые вызовы вызывают задержку, а перестраивают объекты QHash на каждом узле. В основном это делается с помощью:

 QDataStream in(&infile);
 in >> node.hash;

Должен ли я копаться в QHash и смотреть, что там происходит под капотом? Я думаю, что лучшим решением будет объект хэширования, который можно сериализовать с помощью одной операции чтения и записи без необходимости перестраивать внутреннюю структуру данных.

Answer 1

Прежде всего - профилируйте ваше приложение, чтобы вы знали, что занимает время - основывать подозрение на новом, потому что вы где-то читали, оно может быть медленным или на итерации по дереву недостаточно.

Возможно, это операции ввода-вывода - возможно, формат вашего файла неправильный / неэффективный.

Может быть, у вас просто где-то есть дефект?

Или, может быть, где-то есть квадратичная петля, о которой вы не помните, вызывая проблемы? :)

Измерьте, что действительно занимает время в вашем случае, и затем подойдите к проблеме - это сэкономит вам много времени, и вы избежите взлома вашего дизайна / кода, чтобы устранить проблемы с производительностью, которые не существуют, прежде чем найти реальную причину .

Answer 2

Другим подходом будет сериализация ваших указателей и восстановление их при загрузке. Я имею в виду:

Сериализация:

nodeList = collectAllNodes();

for n in nodelist:
 write ( &n )
 writeNode( n ) //with pointers as-they-are.

десериализация:

//read all nodes into a list.
while ( ! eof(f))
    read( prevNodeAddress)
    readNode( node )
    fixMap[prevNodeAddress] = &node;
    nodeList.append(node);

//fix pointers to new values.
for n in nodeList:
    for child in n.children:
        child->node = fixMap[child->node]

Таким образом, если вы не вставляете и не удаляете новые узлы, вы можете выделить вектор один раз и использовать эту память, сокращая ваше выделение для карт (как сказал rpg, это может быть быстрее со списками или даже векторами).

Answer 3

Абсолютно быстрый способ сериализации / десериализации - это запись блока непрерывной памяти на диск, как вы говорите. Если вы изменили свою древовидную структуру, чтобы создать это (возможно, с помощью пользовательской процедуры размещения), это было бы очень просто.

К сожалению, я не очень знаком с QHash, но, глядя на него, он выглядит скорее как Hashtable, а не как дерево. Я тебя неправильно понял? Используете ли вы это для отображения дублирующих узлов?

Я бы использовал профилировщик (я использовал Quantify, теперь он называется Rational PurifyPlus, но здесь есть много , перечисленных здесь ), чтобы найти, где вы используете время, но я думаю, это или несколько выделений памяти, а не одно выделение, или несколько чтений, а не одно чтение. Чтобы решить обе эти проблемы, вы заранее знаете (потому что храните его), сколько узлов вам нужно, а затем пишите / читаете массив узлов правильной длины, где каждый указатель является указателем в массиве, а не указателем в памяти. .

Answer 4

Я настоятельно рекомендую библиотеку boost для сериализации . Он должен работать с решениями, которые вы используете.

Answer 5

Я немного расширю свой комментарий:

Поскольку ваше профилирование предполагает, что сериализация QHash занимает больше всего времени, я считаю, что замена QHash на QList даст значительное улучшение, когда речь идет о скорости десериализации.

Сериализация QHash просто выводит пары ключ / значение, но десериализация создает хеш-структуру данных!

Даже если вы сказали, что вам нужен быстрый поиск детей, я бы порекомендовал вам попробовать заменить QHash на QList> в качестве теста. Если для каждого узла не так много дочерних элементов (скажем, менее 30), поиск все равно должен быть достаточно быстрым, даже с QList. Если вы обнаружите, что QList недостаточно быстр, вы все равно можете использовать его только для (de) сериализации, а затем преобразовать в хеш после загрузки дерева.

Answer 6

Ваше собственное выделение памяти с перегруженными операторами new () и delete () является недорогим вариантом (время разработки). Однако это влияет только на время выделения памяти, а не на время Ctor. Ваш пробег может отличаться, но стоит попробовать.

Answer 7

Как вы сказали, размещение объектов с новым может быть медленным. Это можно улучшить, выделяя пул объектов, а затем используя предварительно выделенные объекты, пока пул не будет исчерпан. Вы могли бы даже реализовать это для работы в фоновом режиме, перегрузив операторы new / delete рассматриваемого класса.

Answer 8

Другим решением будет использование вашего собственного распределителя памяти, который будет использовать непрерывное пространство памяти. Тогда вы сможете сбросить память как есть и загрузить ее обратно. Он чувствителен к платформе (т.е. с прямым порядком байтов / младшим, 32 бит / 64 бит).