1

这是一个关于估计效率背后的原则的问题。在我的一个项目中，我遇到了这种情况：一个函数获取两个正整数并返回两者中的最小值。我想知道我通常使用的这种方法（我计算步数）是否是一种估算效率的准确方法，是否还有其他方法，或者我是否应该始终简单地比较它们的运行速度。

Function(int a, int b)
{
    int lowest = a - b;                   //3 steps, allocating, assigning and calculating
    lowest = lowest * lowest / lowest;    //3 steps, 2 in calculating, 1 in assigning
    //6 steps total

    return lowest;
}

Function(int a, int b)
{
    int lowest;        //1 step in allocating
    if(a > b){         // 2 steps, 1 in comparing, 1 in picking the outcome
        lowest = b;        // 1 step in assigning
                           // Total 4 steps
    }else{
        lowest = a;        // 1 step in assigning
                           // Total 4 steps
    }
    return lowest;
}

在这种情况下，我会选择功能 2，因为它的步骤似乎更少。

4

2 回答 2

0

对于这种大小的函数，几乎可以肯定这无关紧要，因为无论如何该函数都会运行得如此之快。

但是，对于大型计算，该方法绝对是合理的。事实上，像这样计算“步数”是计算机科学子领域“算法分析”的基础。

在实践中，您需要更多的步骤才能真正做到这一点 - 至少数十万，除非这些步骤异常昂贵。

于 2016-10-30T11:17:22.320 回答
0

计算步数是一种分析算法渐近效率的方法。这是衡量算法扩展到更大输入的程度的衡量标准。

但是，为了比较两个函数的速度，对于固定的输入大小，我们确实需要查看它们实际执行的速度。计算步数在这里充其量只是一个粗略的指南，因为：

  1. 执行的步骤不是 C++ 语句，而是它们编译成的机器代码指令
  2. 即使您的 C++ 语句每个都编译为相同数量的指令（它们可能不会），但指令并不都需要相同数量的时钟周期来执行
  3. 即使它们确实都具有相同的名义延迟，这些函数也可能会被内联，这意味着孤立地考虑它们并不是那么有用。您需要知道它们如何影响每个调用站点的优化代码

关于哪些操作可能比其他操作慢，有很多经验法则，但唯一可以确定的方法是在尽可能重现您的真实用例的设置中进行测量。

笔记

在此特定代码中：

  • 版本 1 看起来不会给出正确的结果，但忽略了这一点 - 它有更多的步骤，但它们主要是整数算术，它经过大量优化并且通常很快

  • 版本 2 的步骤更少，但其中一个步骤是分支 (if)，这在历史上一直很慢。

    一些架构允许两个分支（if 和 else）同时执行，这可能会再次加快速度。它还可能导致分支预测溢出，并对其他代码产生连锁反应，从而减慢其他代码的速度。

于 2016-10-30T11:46:29.620 回答