Что самый быстрый путь состоит в том, чтобы десериализовать дерево в C++
Я работаю с не так маленькая древовидная структура (это - Burkhard-Keller-Tree,> 100 МБ в памяти), реализованный в C++. Указатели на детей каждого узла хранятся в QHash.
Каждый узел x имеет n детей y [1]... y [n], края детям маркированы расстоянием редактирования d (x, y [я]), таким образом использование хеша для хранения узлов является очевидным решением.
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 и посмотреть, что продолжается под капотом там? Я думаю, что лучшим решением был бы объект хеша, который может быть сериализирован с единственной операцией чтения и операцией записи без потребности восстановить внутреннюю структуру данных.
8 ответов
Другой подход - сериализовать ваши указатели и восстановить их при загрузке. Я имею в виду:
Сериализация:
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, он может быть быстрее со списками или даже векторами).
Абсолютно самый быстрый способ сериализации / десериализации - это записать блок непрерывной памяти на диск, как вы говорите. Если вы измените свою древовидную структуру для ее создания (возможно, используя специальную процедуру распределения), это будет очень просто.
К сожалению, я не так хорошо знаком с QHash, но, глядя на него, он выглядит как Hashtable, а не как дерево. . Я вас неправильно понял? Вы используете это для сопоставления повторяющихся узлов?
Я бы использовал профилировщик (раньше я использовал Quantify, теперь называемый Rational PurifyPlus, но здесь много перечислено ), чтобы найти, где вы используете время, но я предполагаю, что это либо несколько выделений памяти, а не одно выделение, либо несколько чтений, а не одно чтение. Чтобы решить обе эти проблемы, вы заранее знаете (потому что храните его), сколько узлов вам нужно,
Другое решение - использовать собственный распределитель памяти, который будет использовать непрерывное пространство памяти. Тогда вы сможете выгрузить память как есть и загрузить ее обратно. Это зависит от платформы (т. Е. С прямым порядком байтов / прямым порядком байтов, 32- и 64-разрядными).
Я настоятельно рекомендую библиотеку ускоренной сериализации . Он должен работать с решениями, которые вы используете.
Как вы сказали, размещение объектов с помощью new может быть медленным. Это можно улучшить, выделив пул объектов, а затем используя предварительно выделенные объекты, пока пул не будет исчерпан. Вы даже можете реализовать это для работы в фоновом режиме, перегрузив операторы new / delete соответствующего класса.
I'll expand my comment a bit:
Since your profiling suggests that the QHash serialization takes the most time, I believe that replacing QHash with a QList would yield a significant improvement when it comes to deserialization speed.
The QHash serialization just outputs the key/value pairs, but the deserialization constructs a hash data structure!
Even if you said that you need the fast child lookup, I would recommend that you try replacing QHash with a QList > as a test. If there aren't many children for each node (say, less than 30), the lookup should still be fast enough even with a QList. If you find that QList is not fast enough, you could still use it just for (de)serializaton and later convert to a hash once the tree has been loaded.
Прежде всего - профилируйте ваше приложение так, чтобы вы знали, на что требуется время - основываясь на подозрении на новом, потому что вы где-то прочитали, что оно может быть медленным или на итерации через дерево недостаточно.
Возможно, это операции ввода-вывода - возможно, ваш формат файла не корректен/неэффективен.
Возможно, у вас просто где-то есть дефект?
Или, возможно, где-то есть квадратичный цикл, о возникновении которого вы не помните? :)
Измерьте, что на самом деле занимает время в вашем случае, а затем подойдите к проблеме - это сэкономит вам много времени и вы избежите нарушения дизайна/кода для исправления проблем с производительностью, которых не существует, прежде чем найти реальную причину.
.Собственное выделение памяти с перегруженным оператором new() и delete() - недорогой вариант (время разработки). Однако это влияет только на время выделения памяти, а не на время работы Ctor. Ваши пробеги могут варьироваться, но стоит попробовать.
.