c# - 递归与迭代速度的不一致

Question

我制作了一个程序来比较迭代速度与递归速度，以实现非常简单的操作。我注意到一些我无法解释的奇怪现象。根据处理的值的数量，迭代或递归更快。但它并不一致。

• 对于大约 10，迭代速度更快。
• 对于大约 100，迭代速度更快。
• 对于大约 200，递归更快。
• 对于大约 1000，递归更快。
• 对于大约 5000，迭代速度更快。
• 对于大约 10000，迭代速度更快。
• 除此之外，递归会遇到堆栈溢出，因此无法测试更高的级别。

为什么对于较低和较高的可测试量迭代过程更快，但对于介于两者之间的那些则不然？

我对此缺乏更深入的了解，如果有人能向我解释一下，我将不胜感激。

这里是给那些想自己测试它的人的代码。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Compare_Recursive_Iterative
{
    class Program
    {
        static void Main(string[] args)
        {
            // Amount of values processed.
            long testNumber = 200;
            // Variables to measure time taken.
            double timeIterative, timeRecursive, timeTotal;

            // Iterative process + time elapsed calculation
            DateTime start = DateTime.Now;
            long retVal = 0;
            for(long i = 1; i <= testNumber; i++)
            {
                retVal = 0;
                for (long x = 1; x <= i; x++)
                { 
                    retVal += x;
                }
                Console.WriteLine("For " + i + ": " + retVal);
            }
            TimeSpan timeDiff = DateTime.Now - start;
            timeIterative = timeDiff.TotalMilliseconds;

            // Recursive process + time elapsed calculation
            DateTime start2 = DateTime.Now;
            for (long i = 1; i <= testNumber; i++)
            {
                Console.WriteLine("For " + i + ": " + calculate(i));
            }
            timeDiff = DateTime.Now - start2;
            timeRecursive = timeDiff.TotalMilliseconds;

            // Results to console.
            Console.WriteLine("Iterative: " + timeIterative + "ms /// Recursive: " + timeRecursive + "ms");
            timeDiff = DateTime.Now - start;
            timeTotal = timeDiff.TotalMilliseconds;
            Console.WriteLine("Total time needed: " + timeTotal + "ms");
            Console.WriteLine("Iterative - Recursive: " + (timeIterative - timeRecursive) + "ms");
            Console.Read();
        }


        // Recursive method
        static long calculate(long x)
        {
            if (x <= 1)
                return x;
            else
                return x + calculate(x - 1);
        }

    }
}

Answer 1

大部分时间将花费在您的示例中的 Console.WriteLine 中，它必须做更多的工作而不是添加一些它的工作，所以您的测量是没有意义的，如果您想测量然后

1) 确保你只测量你想测量的东西(不要写入任何输出，你在测试后这样做)

2) 至少使用秒表，DateTime.Now 一点都不精确

3) 将两个测试隔离在各自的函数中，并在测试前分别调用一次，以确保您没有测量预热时间。

4) 大量调用这两个函数(可能是 1000 次？)，然后记下每个函数的最小/最大/平均时间

5) 确保您没有在系统上执行任何其他操作，并且没有任何密集运行(在运行时禁用防病毒软件等)。

6) 同样非常非常重要，不要在 Debug模式下进行测试，先切换到发布!!! Debug模式在某些情况下会大大减慢速度，而在其他情况下几乎不会减慢速度，这意味着功能 A 在调试中可能比 B 快得多，而在发布时则相反。也不要使用附加的调试器进行测试，只需从文件夹中启动 exe。

因为您没有执行第 1 步，这就是导致您出现问题的原因，因为所有时间都花得很好，几乎在您自己的代码之外，还有其他要点，因此您可以考虑所有这些而不是在此处进行问答。

制作了一个示例向您展示，可能并不完美，但更接近基准测试的样子，还请注意，如果您真的想比较内联测试(与递归哪个必须是函数)

void Main()
{
var TargetNumber = 2000;
var TestRuns = 10;
//warmup both methods
calculate(100);
TestIterative(100);

Stopwatch sw = new Stopwatch();

var RecursiveTimes = new List<long>();

for(int run = 1;run<=TestRuns;run++)
{
    sw.Restart();
    for (int i = 1; i <= TargetNumber; i++)
    {
        calculate(i);
    }
    sw.Stop();
    RecursiveTimes.Add(sw.ElapsedMilliseconds);
}

var IterativeTimes = new List<long>();

for(int run = 1;run<=TestRuns;run++)
{
    sw.Restart();
    for (int  i = 1; i <= TargetNumber; i++)
    {
        TestIterative(i);
    }
    sw.Stop();
    IterativeTimes.Add(sw.ElapsedMilliseconds);
}

Console.WriteLine("Iterative : " + IterativeTimes.Average() + " ms on average. Min and max : " + IterativeTimes.Min() + " / " + IterativeTimes.Max());
Console.WriteLine("Recursive : " + RecursiveTimes.Average() + " ms on average. Min and max : " + RecursiveTimes.Min() + " / " + RecursiveTimes.Max());  
}

static long TestIterative(long x)
{
    long retVal = 0;
    for (long y = 1; y <= x; y++)
    { 
        retVal += y;
    }
    return retVal;
}

static long calculate(long x)
{
    if (x <= 1)
        return x;
    else
        return x + calculate(x - 1);
}

另请注意，我将您要测试的数字(从 0 到 TargetNumber)与测试运行的数量分开，因为它们没有理由链接(TestRuns)，以便您可以多次测试一个小集或一个大集几次。

如您所见，所有输出都移到了程序的末尾，因为它很昂贵并且您不想对其进行测量，即使将时间添加到列表中也是在计时区域之外完成的，我正在计时每个测试(不在测试中)，因为时间太短，我们最终会得到很多零。

还有一个很好的基准测试是用可用数据测试实际可用代码的基准测试，不要尝试对什么都不做的代码进行“微基准测试”，你不能真正地对在硬件上添加一些东西所花费的时间进行基准测试每秒做十亿次。

一个很好的经验法则，除非它使你的代码变得非常复杂，否则总是去迭代，而不是为了性能(但它确实更好)但主要是因为如果你没有理由让自己堆栈溢出可以避免。