"逻辑上更慢"的算法结果更快,但为什么呢？

Question

我已经实现了两种基本相同的不同算法,检查节点树中从一个节点到另一个节点的可见性,规则很简单 - 如果节点沿着同一个分支在它之前,则该节点只对另一个节点可见.

第一种方法从树到父,在父树中跳过其他潜在的子节点以获取两个节点的树索引,并使用一些基本逻辑来确定是否存在可见性.我决定首先选择这个,因为我已经拥有了我需要的节点索引的方法,我认为它可能更快.

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万个节点(授予大部分时间是节点分配,实际可见性检查是几秒钟).

那么这些绩效数据到底是什么？考虑到它们提供相同的结果(彻底检查 - 第二种方法没有保存工作),第一种方法涉及更少的内存跃点,我认为它更加缓存友好,而且它只能检查深度并做得更短评价？当然,它会进行2次遍历,而不是一次,但是它们直接与父级相关,在此过程中会跳过其余的孩子.是的,我确实意识到第二种方法不需要一直向下,但仍然......

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

编辑2:再次使用向量进行快速测试,这次我在报废之前取消了前置并进行了常规插入和反向操作,这使得向量解决方案稍微快一点,从完全遍历方法慢到8倍"只"慢了6倍.我怀疑QList分配可能是低性能的主要罪魁祸首,但看起来,还有更多的东西.

Answer 1

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