在c中存储已知序列

Question

我正在 C 语言中的 Project Euler #14 工作，并发现得出基本算法；然而，对于大量数据（例如需要的 2,000,000 个数据），它的运行速度慢得令人难以忍受；我猜想是因为它必须一遍又一遍地生成序列，即使应该有一种方法来存储已知序列（例如，一旦我们到达 16，我们从以前的经验知道下一个数字是 8、4、2 ，则 1)。

我不太确定如何使用 C 的定长数组来做到这一点，但一定有一个好方法（我确信这是非常有效的）。提前致谢。

这是我目前拥有的，如果有帮助的话。

#include <stdio.h>
#define UPTO 2000000

int collatzlen(int n);

int main(){
    int i, l=-1, li=-1, c=0;
    for(i=1; i<=UPTO; i++){
        if( (c=collatzlen(i)) > l) l=c, li=i;
    }
    printf("Greatest length:\t\t%7d\nGreatest starting point:\t%7d\n", l, li);
    return 1;
}

/* n != 0 */
int collatzlen(int n){
    int len = 0;
    while(n>1) n = (n%2==0 ? n/2 : 3*n+1), len+=1;
    return len;
}

Answer 1

你原来的程序在我的机器上需要 3.5 秒。对你来说是不是慢得难以忍受？

我的又脏又丑的版本需要0.3秒。它使用全局数组来存储已经计算的值。并在以后的计算中使用它们。

int collatzlen2(unsigned long n);
static unsigned long array[2000000 + 1];//to store those already calculated

int main()
{
    int i, l=-1, li=-1, c=0;
    int x;
    for(x = 0; x < 2000000 + 1; x++) {
        array[x] = -1;//use -1 to denote not-calculated yet
    }

    for(i=1; i<=UPTO; i++){
        if( (c=collatzlen2(i)) > l) l=c, li=i;
    }
    printf("Greatest length:\t\t%7d\nGreatest starting point:\t%7d\n", l, li);

    return 1;
}

int collatzlen2(unsigned long n){
    unsigned long len = 0;
    unsigned long m = n;
    while(n > 1){
        if(n > 2000000 || array[n] == -1){ // outside range or not-calculated yet
            n = (n%2 == 0 ? n/2 : 3*n+1);
            len+=1;
        }
        else{ // if already calculated, use the value
            len += array[n];
            n = 1; // to get out of the while-loop
        }
    }
    array[m] = len;
    return len;
}

Answer 2

鉴于这本质上是一个一次性程序（即一旦您运行它并得到答案，您将不会在多年内支持它:)，我建议使用一个全局变量来保存序列的长度已经计算过：

int lengthfrom[UPTO] = {};

如果您的最大大小是几百万，那么我们谈论的是兆字节内存，它应该很容易立即装入 RAM。

上面的代码将在启动时将数组初始化为零。在您的程序中 - 对于每次迭代，检查数组是否包含零。如果确实如此，您将不得不继续进行计算。如果没有 - 那么您知道继续进行会进行更多的迭代，因此只需将其添加到您到目前为止已完成的数字中即可完成。当然，然后将新结果存储在数组中。

不要试图对这种大小的数组使用局部变量：这将尝试在堆栈上分配它，而堆栈不够大并且可能会崩溃。

另外 - 请记住，在这个序列中，值会上升和下降，因此您需要在程序中处理这个问题（可能是让数组比 UPTO 值长，并使用 assert() 以防止索引大于数组的大小）。

Answer 3

如果我没记错的话，你的问题不是一个慢的算法：你现在拥有的算法对于 PE 要求你做的事情来说已经足够快了。问题是溢出：有时您最终会将数字乘以 3 多次，最终会超过可以存储在有符号 int 中的最大值。使用无符号整数，如果仍然不起作用（但我很确定它可以），请使用 64 位整数（long long）。

这应该运行得非常快，但如果你想做得更快，其他答案已经解决了这个问题。