尝试在打印数字的除数的递归函数上优化和了解运行时 [英] Trying to optimize and understand runtime on a recursive function that prints divisors of a number

问题描述

以下是打印数字除数的递归函数（必须是递归）。

没有注释掉的部分，程序的最坏情况是primes，while循环必须一直运行到n，所以运行时将是：O （n）。

对于注释部分，素数现在在O（sqrt（n））上运行，但在非素数的数字上变慢，循环应该在任何情况下更快地计数到除数。任何人都可以解释为什么运行时更慢？

如果任何人想检查自己，我已经包含时钟部分，这里有一些大的素材：1073676287。

 ＃include< iostream> 
 #include< math.h> 
 #include< ctime> 
 
 using namespace std; 
 
 void f（long long number）; 
 
 void main（）
 {
 clock_t begin = clock（）; 
 f（1844674407370955161）; 
 clock_t end = clock（）; 
 
 cout<< endl<< double（end-begin）/ CLOCKS_PER_SEC<< endl; 
} 
 
 
 void f（long long n）
 {
 long long divisor = 2; 
 long long sn = sqrt（n），i; 
 int trigger = 0; 
 
 if（n == 1）return; 
 
 // else if（n！= 1）
 // {
 // for（i = 2; i <= sn; i ++）
 / / {
 // if（n％i == 0）
 // trigger ++; 
 //} 
 // if（trigger == 0）divisor = n; 
 //} 
 
 while（（n％divisor）&&（n> divisor））
 divisor ++; 
 cout<<除数< ; 
 f（n / divisor）; 
} 
  

解决方案

问题：

问题很明显：您的注释 for 循环将执行递归调用1.641.428.459次，每次对 long long 执行模块操作。这需要一些时间！这解释了它是几乎3倍长（在我的电脑上大约40秒）

首先这个for循环是没有优化！以下：

  for（i = 1; i <= sn; i ++）
 ... 
 if（trigger == 0）divisor = n; 
  

可以简化，因为使用触发器只知道它是否为0：

  for（i = 1;！trigger&& i< = sn ; i ++）{//如果触发器设置，没有使用继续！ 
 if（n％i == 0）
 trigger ++; 
} 
 if（trigger == 0）divisor = n; 
  

通过此更改，您的其他代码会获得可接受的效果。然而，这个代码仍然不加速任何东西。总的来说，它仍然比没有100毫秒慢，大约15.5秒得到的结果。

B.Kernighan曾经说过不要干扰代码，找到更好的算法：看看你的隐藏代码和 for 循环，我们可以看到，在每次递归时都执行与 i 相同的计算，盯着1。但如果2或3或5不是第一次的除数，它不会是secont时间！因此，我们可以优化递归：

优化递归

，你得到的结果1.3秒相比15.5秒它的10倍以上：

  void f（long long number，long long last_divisor = 2）; // 2参数，默认为1 
 
 void f（long long n，long long last_divisor）
 {
 long long divisor = last_divisor; //我们不再从2开始
 long long sn = sqrt（n），i; 
 int trigger = 0; 
 
 if（n == 1）return; 
 
 else if（n！= 1）//如果给定数是素数，则优化
 {
 for（i = last_divisor;！trigger&& i& = sn; i ++）{//我们不再从1开始
 if（n％i == 0）
 trigger ++; 
} 
 if（trigger == 0）divisor = n; 
} 
 
 while（（n％divisor）&&（n> divisor））
 divisor ++; 
 cout<<除数< ; 
 f（n / divisor，divisor）; //告诉递归我们停止了！ 
} 
  

The following is a recursive function that prints the divisors of a number (it has to be recursive).

Without the commented out part, the program's worst case scenario are primes, the while loop will have to run all the way up to n, so the runtime would be: O(n).

With the commented part, primes now run on O(sqrt(n)) but it becomes slower on numbers that aren't primes, but that for loop should make counting up to a divisor faster in any case. Can anyone explain why the runtime is slower?

I've included the clock part if anyone want to check for themselves, here's some large prime: 1073676287.

#include<iostream>
#include <math.h>
#include <ctime>

using namespace std;

void f(long long number);

void main()
{
    clock_t begin = clock();
    f(1844674407370955161);
    clock_t end = clock();

    cout << endl << double(end - begin) / CLOCKS_PER_SEC << endl;
}


void f(long long n)
{
    long long  divisor = 2;
    long long sn = sqrt(n), i;
    int trigger = 0;

    if (n == 1) return;

    //else if (n != 1)
    //{
    //  for (i = 2; i <= sn; i++)
    //  {
    //      if (n%i == 0)
    //          trigger++;
    //  }
    //  if (trigger == 0)divisor = n; 
    //}

    while ((n % divisor) && (n > divisor))
        divisor++;
    cout << divisor << " ";
    f(n / divisor);
}

解决方案

Analysis of the problem:

The problem is obvious: Your commented for loop will be executed accross the recursive calls 1.641.428.459 times, performing each time a module operation on a long long. This needs some time ! This explain how it's almost 3 times as long (around 40s on my PC)

First this for loop is is not optimized at all ! The following:

  for (i = 1; i <= sn; i++) 
  ...
  if (trigger == 0) divisor = n; 

can be simplified, because trigger is used only to know if it's 0 or not:

  for (i = 1; !trigger && i <= sn; i++)  {  // if trigger is set, no use to continue !!
      if (n%i == 0)
          trigger++;  
  }
  if (trigger == 0) divisor = n; 

With this change, your additional code gains acceptable performance. However this code still doesn't accelarate anything. Overall it's still 100 ms slower than without, and around 15.5 seconds to get the results.

B.Kernighan has once said "Don't diddle code, find better algorithms": looking at your recusive code and the for loop, we can see that the same calculations with i, staring at 1 are done at every recursion. But if 2 or 3 or 5 was not a divisor the first time, it won't be the secont time either ! So we could optimize the recursion:

Optimized recursion

With the following code, you get the results 1.3 seconds compared to 15.5 seconds its more than 10 times faster:

void f(long long number, long long last_divisor=2);  // 2 parameters, 1 being by default

void f(long long n, long long last_divisor)
{
    long long  divisor = last_divisor;  // we don't start at 2 anymore 
    long long sn = sqrt(n), i;
    int trigger = 0;

    if (n == 1) return;

    else if (n != 1)//optimisation in case given number is a prime
    {
      for (i = last_divisor; !trigger && i <= sn; i++) { // we don't start at 1 anymore
          if (n%i == 0)
              trigger++;
      }
      if (trigger == 0)divisor = n; 
    }

    while ((n % divisor) && (n > divisor))
        divisor++;
    cout << divisor << " ";
    f(n / divisor, divisor);   // tell recursion where we've stopped !  
}

这篇关于尝试在打印数字的除数的递归函数上优化和了解运行时的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！