为什么第一个定时函数总是用“秒表”测量得更快

问题描述 投票：0回答：3

我试图确定 C# 中迭代或递归更快。然而，在一个简单的测试中，我似乎无法使用 StopWatch 获得可靠的结果。

代码：

internal class Program
    {
        // The factorial of a number is the product of all the
        // integers from 1 to that number.
        // For example, the factorial of 6 is 1*2*3*4*5*6 = 720
        // Factorial is not defined for negative numbers, and the factorial of zero is one, 0! = 1 
        static void Main(string[] args)
        {
            Console.WriteLine("Please Enter a Number:");

            //read number from user
            int number = Convert.ToInt32(Console.ReadLine());
            
            double sw1Elapsed = 0d;
            double sw2Elapsed = 0d;
            double factorial = 0d;
            double factorial2 = 0d;

            Stopwatch sw = new Stopwatch();
            sw.Reset(); 
            for (int i = 0; i < 6; i++)
            {
                sw.Restart();
                factorial = Factorial(number);
                sw.Stop();
                sw1Elapsed = sw1Elapsed + sw.Elapsed.TotalMilliseconds;

                sw.Restart();
                factorial2 = FactorialByRecursion(number);
                sw.Stop();
                sw2Elapsed = sw2Elapsed + sw.Elapsed.TotalMilliseconds;

                //print the factorial result
                Console.WriteLine("Iteration:");
                Console.WriteLine("Factorial of " + number + " = " + factorial.ToString());
                Console.WriteLine("Iteration Time taken = " + sw1Elapsed);
                Console.WriteLine();
                Console.WriteLine("Recursion:");
                Console.WriteLine("Factorial of " + number + " = " + factorial2.ToString());
                Console.WriteLine("Recursion Time taken = " + sw2Elapsed);
                Console.WriteLine("-----------------------------------------------------\n");
            }
        }


        public static double Factorial(int number)
        {
            if (number == 0)
                return 1;

            double factorial = 1;
            
            for (int i = number; i >= 1; i--)
            {
                factorial = factorial * i;
            }
            return factorial;
        }

        public static double FactorialByRecursion(int number)
        {
            if (number == 0)
                return 1;
            return number * FactorialByRecursion(number - 1);//Recursive call

        }
    }
}

所以有两个函数以两种不同的方式做同样的事情。

这些产生了这些结果：

Please Enter a Number: 6 Iteration: Factorial of 6 = 720 Iteration Time taken = 0.3171
Recursion: Factorial of 6 = 720 Recursion Time taken = 0.0616
-----------------------------------------------------
Iteration: Factorial of 6 = 720 Iteration Time taken = 0.3172
Recursion: Factorial of 6 = 720 Recursion Time taken =
0.061700000000000005
-----------------------------------------------------
Iteration: Factorial of 6 = 720 Iteration Time taken =
0.31739999999999996
Recursion: Factorial of 6 = 720 Recursion Time taken =
0.06180000000000001
-----------------------------------------------------
Iteration: Factorial of 6 = 720 Iteration Time taken =
0.31749999999999995
Recursion: Factorial of 6 = 720 Recursion Time taken =
0.06190000000000001
-----------------------------------------------------
Iteration: Factorial of 6 = 720 Iteration Time taken =
0.31759999999999994
Recursion: Factorial of 6 = 720 Recursion Time taken =
0.06200000000000001
-----------------------------------------------------
Iteration: Factorial of 6 = 720 Iteration Time taken =
0.3177999999999999
Recursion: Factorial of 6 = 720 Recursion Time taken =
0.062100000000000016
-----------------------------------------------------
C:\Users\Dev\source\repos\SimpleRecursion\SimpleRecursion\bin\Debug\net6.0\SimpleRecursion.exe (process 26992) exited with code 0. To automatically close the console when debugging stops, enable Tools->Options->Debugging->Automatically close the console when debugging stops. Press any key to close this window . . .

但是，如果我将第二个函数移动到循环中第一个函数的上方，那么可能是：

static void Main(string[] args)
        {
            Console.WriteLine("Please Enter a Number:");

            //read number from user
            int number = Convert.ToInt32(Console.ReadLine());
            
            double sw1Elapsed = 0d;
            double sw2Elapsed = 0d;
            double factorial = 0d;
            double factorial2 = 0d;

            Stopwatch sw = new Stopwatch();
            sw.Reset(); 
            for (int i = 0; i < 6; i++)
            {
                sw.Restart();
                factorial2 = FactorialByRecursion(number);
                sw.Stop();
                sw2Elapsed = sw2Elapsed + sw.Elapsed.TotalMilliseconds;

                sw.Restart();
                factorial = Factorial(number);
                sw.Stop();
                sw1Elapsed = sw1Elapsed + sw.Elapsed.TotalMilliseconds;

                //print the factorial result
                Console.WriteLine("Iteration:");
                Console.WriteLine("Factorial of " + number + " = " + factorial.ToString());
                Console.WriteLine("Iteration Time taken = " + sw1Elapsed);
                Console.WriteLine();
                Console.WriteLine("Recursion:");
                Console.WriteLine("Factorial of " + number + " = " + factorial2.ToString());
                Console.WriteLine("Recursion Time taken = " + sw2Elapsed);
                Console.WriteLine("-----------------------------------------------------\n");
            }
        }

那么结果就变成：

Please Enter a Number:
6
Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.0571

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.1066
-----------------------------------------------------

Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.0571

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.1069
-----------------------------------------------------

Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.0572

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.1071
-----------------------------------------------------

Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.0572

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.1073
-----------------------------------------------------

Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.0572

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.10750000000000001
-----------------------------------------------------

Iteration:
Factorial of 6 = 720
Iteration Time taken = 0.057300000000000004

Recursion:
Factorial of 6 = 720
Recursion Time taken = 0.10770000000000002
-----------------------------------------------------


C:\Users\Dev\source\repos\SimpleRecursion\SimpleRecursion\bin\Debug\net6.0\SimpleRecursion.exe (process 26100) exited with code 0.
To automatically close the console when debugging stops, enable Tools->Options->Debugging->Automatically close the console when debugging stops.
Press any key to close this window . . .

谁能解释一下经过时间的差异以及为什么/发生了什么？

我想说的是，无论哪个函数调用首先放在循环中，都会通过秒表产生最佳时间。我问这是为什么？ （顺便说一句，如果使用 int 作为阶乘，它的作用是相同的）。

c# recursion iteration stopwatch
3个回答
3
投票

我想说的是，无论循环中首先调用哪个函数，都会通过秒表产生最佳时间。我就问这是为什么？

这是一个好问题，但你必须意识到所有这些数字都非常荒谬。 “为什么 A 的一万倍左右的数字总是比 B 的大？” （老实说！）与阶乘无关——你的问题重点在于阶乘。

技术上：

尝试简单地做

empty

Restart(); Stop() 对，你会发现问题出在你测量时间的方法上。换句话说，对于您关心的时间段，

Stopwatch
似乎完全不合适。我不是 .NET 专家 - 但在我看来，它没有使用硬件高分辨率计时器，并且 
ElapsedMilliseconds
可能会导致上下文切换（从执行应用程序的代码到执行内核的代码） ），如果您在 
Consele.WriteLine
之后刚刚脱离内核上下文，这可以解释较小的结果。
代码方面：


在像 C# 这样的命令式语言中，这种平面线性操作的递归是否比循环更快实际上从来都不是问题——事实并非如此；在最好的情况下，编译器可以优化递归，使其与循环一样高效。这只是因为与两个整数相乘相比，“调用函数”和“从函数返回”具有
显着
的开销。在某些情况下，高度优化的编译器可能会实现尾递归优化，其中它认识到并非所有函数状态都需要保存（“推入堆栈”）。
因此，计算功能是在此类编程语言中“不”递归执行什么操作的经典示例。这通常也是向学习者展示的第一个例子——因为，出于我不清楚的原因，有些书坚持向那些不会使用递归算法的人解释递归算法，因为他们缺乏对它们适合的数据结构的理解。
    




我正在尝试确定 C# 中迭代或递归更快



      

      
      
      

      

        

          

            

              
2
投票

              
            

          

        

        
这取决于具体的用例。没有涵盖所有用例的通用规则。


对于简单的任务，例如对列表中的所有数字求和，迭代几乎肯定会更快，因为您避免了为每个项目调用方法的开销。


对于更复杂的任务，比如遍历树，它会变得更加复杂。您可以使用显式 
stack
 而不是用于管理方法调用的隐式堆栈，将递归实现转换为迭代。这可能会更快，因为压入/弹出堆栈的方法调用可能是内联的。另一方面，CPU 在处理调用堆栈方面进行了高度优化，因为它们在大多数语言中使用，这在某些情况下可能会给它带来优势。


另一个因素是开发时间，有些任务通过递归更容易解决，让您可以花更多时间优化其他可能更重要的部分。在许多情况下，递归和迭代之间的差异足够小，因此并不重要。

您还需要检查您的测量方式，您应该至少



在发行版中运行（不附加任何调试器）


进行“热身”运行以避免测量抖动时间。在分层编译的情况下可能会运行很多次预热
确保测试运行足够长的时间以最小化测量方差。通常通过重复测试 1000 次。


    

  1. 但更好的方法是使用
    2. Benchmark.Net
  2. ，它可以完成上述所有操作，甚至更多，以确保测试结果可靠。但您需要测试实际的现实世界任务。进行一些综合测试并宣布其中一个作为所有任务的获胜者是错误的。
    3. 
    
  3. 

    4. 

评论中已经提到了，但是使用基准测试工具来处理这样的事情；例如
https://benchmarkdotnet.org/
    



      

      
      
      

      

        

          

            

              
-2
投票

              
            

          

        

        



      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.