c++ - 在 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 非常慢。初始构建不是大问题，因为树相当稳定，不需要经常重建。但是从文件加载树应该尽可能快。

完成此任务的最佳方法是什么？

将整棵树保存在具有相邻节点的单个内存块中一定会好得多。然后将减少序列化和反序列化以保存和加载整个 block ，我只需分配一次。

但要实现这一点，我必须重新实现 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

首先 - 分析您的应用程序，以便您知道什么需要时间 - 将怀疑基于新的，因为您已经在某处阅读它可能很慢或通过树的迭代是不够的。

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

也许你只是某处有缺陷？

或者也许在某个地方有一个您不记得导致问题的二次循环？ :)

衡量在您的案例中真正需要花费时间的事情，然后解决问题 - 这会为您节省大量时间，并且您会避免破坏设计/代码以修复在找到真正原因之前不存在的性能问题.