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

Question

我正在处理一棵不太小的树形结构（它是Burkhard-Keller-Tree，在内存中占用> 100 MB），使用C ++实现。每个节点的子指针都存储在QHash中。

每个节点x有n个孩子y [1] ... y [n]，到孩子的边缘带有编辑距离d（x，y [i]）标签，因此使用哈希来存储节点是一个显而易见的解决方案。

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

我也希望将其序列化并反序列化到文件中（我目前使用QDataStream）。树只需建立一次，然后不再更改。

构建树和反序列化相当缓慢。我以明显的方式加载树：递归地构建每个节点。由于使用new运算符单独创建许多节点，我认为这是次优的。我在某个地方读到，new非常慢。初始构建不是一个大问题，因为树相当稳定，不必经常重建。但是从文件加载树应尽可能快。

最好的方法是将整个树保存在单个内存块中，与相邻节点一起。然后，序列化和反序列化将被减少为保存和加载整个块，我只需要分配一次。

但是，要实现此操作，我必须重新实现QHash，据我所知。

你会怎么做来加速反序列化？

补充：

感谢您建议进行一些分析。以下是结果：

重新从文件中重建树时

 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并查看其底层运作吗？我认为最好的解决方案是一个哈希对象，可以通过单个读写操作进行序列化，而无需重建内部数据结构。

- WolfgangP

---

你需要快速访问特定节点 y[i] 吗？尝试使用 QList 而不是 QHash，在涉及 I/O 时应该更快。 - rpg

Answer 1

首先，对您的应用程序进行配置文件，以了解哪些操作需要时间。不要仅仅因为您在某个地方读到“新”会很慢，或者遍历树时不够，在怀疑性的基础上。

可能是IO操作 - 也许您的文件格式不正确/低效。

也许你只是有一个缺陷？

或者可能有一个二次循环的问题，你不记得导致问题？ :)

测量在您的情况下真正花费时间的内容，然后处理问题 - 这将节省大量时间，并避免在找到真正原因之前破坏您的设计/代码以修复不存在的性能问题。

- RnR

---

+1. 我完全同意。在优化之前一定要进行性能分析。即使你的猜测是正确的，你也会准确地知道你为某个优化获得了多少收益。 - neuro

每个节点都通过重载的“<<”运算符存储到QDataStream中。这是存储Qt对象的推荐方式。不，没有二次循环。我进行了一些分析，结果证明了我的假设是错误的（请参见编辑后的问题）。 - WolfgangP

Answer 2

另一种方法是在加载时序列化指针并在恢复时还原它们。我的意思是：

序列化：

```html

Serializing:

```

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

- davidnr

Answer 3

我强烈推荐使用boost序列化库。它应该可以与您正在使用的解决方案兼容。

- Maciek

---

我赞同这个观点：Boost是一个不错的解决方案，并且可以自动处理所有子/父关系。鉴于基准测试显示QHash（当前用于子/父关系的解决方案）占用了大部分时间，值得进一步研究。此外，Boost在广泛的平台上都可用。然而，我不知道Boost在QT中的表现如何。 - DrYak

Answer 4

序列化/反序列化的绝对最快方法是将一块连续的内存写入磁盘，正如您所说。如果您更改了树结构以创建此内容（可能使用自定义分配例程），那么这将非常容易。

不幸的是，我对QHash不太熟悉，但从看它的样子来看，它似乎是哈希表而不是树。我是否误解了您的意思？您是否使用它来映射重复节点？

我会使用分析器（我曾经使用Quantify，现在称为Rational PurifyPlus，但有很多在此处列出）来查找您使用时间的位置，但我猜测问题要么是多个内存分配而不是单个分配，要么是多个读取而不是单个读取。为了解决这两个问题，您可以提前知道（因为您存储了它），需要多少个节点，然后编写/读取正确长度的节点数组，其中每个指针都是数组中的索引，而不是内存中的指针。

- Nick Fortescue

---

树的每个节点都有一个键和指向其叶子节点的哈希表。每个叶子节点由任意数量的引用解除引用。准确地说，节点x具有n个叶子节点y_1...y_n，从x到y_i的每条边都标记有从d（x，y_i）计算出的编辑距离（请参见http://en.wikipedia.org/wiki/BK-tree）。 - WolfgangP

Answer 5

另一个解决方案是使用自己的内存分配器，它将使用连续的内存空间。然后，您将能够按原样转储内存并重新加载它。这是平台（即大端/小端，32位/64位）敏感的。

- Drakosha

---

这个想法不太好：你提到了一些问题，但实际上这也与编译器、优化级别以及调试/发布有关 - 更不用说将来扩展树和处理迁移的问题了。 - RnR

+1 偏移量：通过适当的抽象层次，这是完全可能的 - 例如使用迭代器，并存储偏移量而不是指针。特别是对于“构建一次，永不修改”的区域分配器非常高效。平台可移植性确实是一个问题，但它可能无法解决OP的问题。 - peterchen

Answer 6

正如你所说，使用new分配对象可能会很慢。可以通过分配对象池并使用预先分配的对象来改善这种情况，直到池用尽为止。你甚至可以通过重载相关类的new/delete运算符，将其实现为后台工作。

- user231967

Answer 7

使用重载的new()和delete()运算符进行自己的内存分配是一种低成本的选择（开发时间）。 然而，这只影响内存分配时间，而不影响构造函数的时间。 你的结果可能会有所不同，但值得一试。

- Dénes Tarján

Answer 8

我来详细解释一下我的评论：

由于您的分析表明QHash序列化需要最长的时间，我认为将QHash替换为QList在反序列化速度方面会有显著的改善。

QHash序列化只输出键/值对，但反序列化构造了一个哈希数据结构！

即使您说您需要快速查找子节点，我仍建议您尝试用QList代替QHash进行测试。如果每个节点的子节点不多（比如少于30个），即使使用QList，查找速度也应该足够快。如果您发现QList不够快，您仍然可以将其用于（反）序列化，等树加载完成后再转换为哈希。

- rpg