gpt4 book ai didi

c++ - "Logically slower"算法原来更快,但为什么呢?

转载 作者:可可西里 更新时间:2023-11-01 18:39:37 25 4
gpt4 key购买 nike

我已经实现了两种不同的算法,它们的作用基本相同,检查节点树中一个节点到另一个节点的可见性,规则很简单——一个节点只有在另一个节点之前才对它可见同一个分支。

第一种方法沿着树从子节点到父节点,跳过父节点中的其他潜在子节点以获得两个节点的树索引,并使用一些基本逻辑来确定是否存在可见性。我决定首先使用这个方法,因为我已经有了处理其他事情所需的节点索引方法,并且我认为它可能会更快。

bool isVisibleTo(Node * accessor) {
QList<uint> accessedI = getIndex();
QList<uint> accessorI = accessor->getIndex();
if (accessedI.size() > accessorI.size()) {
return false;
} else if (accessedI.size() == accessorI.size()) {
for (int i = 0; i < accessedI.size() - 1; ++i) {
if (accessedI.at(i) != accessorI.at(i)) {
return false;
}
}
if (accessedI.last() > accessorI.last()) {
return false;
}
}
for (int i = 0; i < accessorI.size() - (accessorI.size() - accessedI.size()); ++i) {
if (accessedI.at(i) > accessorI.at(i)) {
return false;
}
}
return true;
}

第二个完全遍历树,从每个子节点到父节点等等,遍历更多的节点,我只能假设内存页和缓存行。

bool isVisibleTo2(Node * accessor) {
Node * node = accessor;
while (node) {
if (node == this)
return true;
if (node->_parent) {
uint i = node->_parent->_children.indexOf(node);
while (i) {
if (node->_parent->_children.at(--i) == this) {
return true;
}
}
}
node = node->_parent;
}
return false;
}

我预计这是大树的较慢算法。但事实证明,对于小树来说,它的速度要快 10-20 倍,并且随着树的大小增加,它在最后几次测试中始终保持 4 倍的速度,最后一次测试耗时约 20 分钟,涉及树中的 1000 万个节点(授予大部分时间是节点分配,实际可见性检查是几秒钟)。

那么这些性能数据是由于什么原因造成的?考虑到它们提供相同的结果(彻底检查 - 第二种方法没有保存任何工作)并且第一种方法涉及更少的内存跳跃,我认为它对缓存更友好,而且它可以只检查深度并做更短的时间评估?当然,它进行了两次遍历而不是一次遍历,但它们是直接从 child 到 parent 的,沿途跳过了其余的 child 。是的,我确实意识到第二种方法不需要一直往下走,但仍然......

编辑:我切换到-O3 编译,但数字没有改变。我还尝试将 getIndex 的列表更改为 vector ,但它实际上导致性能大幅下降,因为索引需要以相反的顺序插入,例如前置,这对于 vector 来说是非常低效的。

编辑 2:再次用 vector 进行快速测试,这次我放弃了前置,在返回之前进行了常规插入和反向操作,这使得 vector 解决方案稍微快一些,比完整遍历慢 8 倍方法“只”慢 6 倍。我怀疑 QList 分配可能是低性能的罪魁祸首,但看起来,还有更多原因。

最佳答案

如果我对您的理解正确,您在第一种情况下调用的 getIndex() 函数对所有树的遍历基本上与 isVisibleTo2() 相同。但是 isVisibleTo1() 有额外的 getIndex 操作,因此速度较慢。

关于c++ - "Logically slower"算法原来更快,但为什么呢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20123301/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com