在C++中反序列化树的最快方法是什么

Question

我正在使用C++实现的一个不那么小的树结构(它是一个Burkhard-Keller-Tree,内存> 100 MB).指向每个节点的子节点的指针存储在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

另一种方法是序列化指针并在加载时恢复它们。我是说：

序列化：

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 所说，使用列表甚至向量可能会更快）。