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