递归和迭代的速度性能 - 为什么它们对于不同的"小"数字都以相同的速度运行？

Question

我正在尝试优化我拥有的代码.为了做到这一点,我编写了这段代码来看看递归与迭代的效果.代码"计数"到10到n次幂.

public Form1()
{
    InitializeComponent();
    Stopwatch sw = new Stopwatch();
    sw.Start();
    recurse(4);
    //iterate(4);
    sw.Stop();
    Text = sw.Elapsed.TotalMilliseconds.ToString();
}

void recurse(int i)
{
    if (i < 1) return;
    for (int x = 0; x < 10; x++) recurse(i - 1);
}

void iterate(int i)
{
    i = (int)System.Math.Pow(10, i);
    for (int x = 0; x < i; x++) ;
}

我得到了这个意想不到的结果:当n为1到4时,递归和迭代的速度大约为0.5 ms. - 而不是4比1慢1000倍,这是我的预期.只有更大的数字才开始具有更直观的速度,迭代也比递归更快.

为什么相同的速度10倍和10,000倍？

Answer 1

即使你在两种情况下都纠正了代码来计算相同的东西,也不要在一次运行中测试这样的东西.除非测试本身至少花费一秒钟,否则你不会得到正确的结果.运行一百万次,然后划分总时间.当你测试的东西只需要几毫秒或者两秒时,你应该确保测试需要足够长的时间来忽略冷缓存的差异,.Start()和.Stop()调用的时间,小的GC延迟同时,确保实际工作比空计数循环花费更多的时间(for(many times) recurse(x)足够高x,for本身不相关)

一次运行0.5ms的结果在这里或多或少没有意义.此外,如果它是一种jitted语言,我建议在测试之前调用相同的函数,以确保它已经编译 - 否则会增加开销.

TL; DR - 函数周围发生的其他事情的开销高于函数执行的时间.