java - Collat​​z 和其他序列 : how to get more precision easily and avoid segfault?

Question

这是我从一些旧的 Java 代码创建的一个简单的 C 程序(我的第一个 C 程序，所以很好 ;))。这比相应的 Java 代码运行得快得多，但 Java 允许我在它崩溃之前更精确(我也在 Java 中使用 longs)。

令我惊讶的是，直到输入超过 170,000,000，Java 代码才崩溃。 C 代码无法处理超过 1,050,000 的任何内容。有什么建议可以让这个 C 代码在不需要一些疯狂的库的情况下运行得更好吗？谢谢!

#include <stdio.h>
#include <string.h> /* lets me use memset */
#include <stdlib.h> /* home of strtoull */

/* segfault 11 after 1047993 (Not anymore!!) */ 

unsigned long long getnext( unsigned long long x );

unsigned long long getnext( unsigned long long x )
{
    if (x == 1) { return 1; }
    if (x % 2 == 0) { return x/2; }
    return (3 * x + 1);
}

int main(int argc, char *argv[])
{
    int argind;
    for ( argind = 0; argind < argc; argind++ )
    {
        unsigned long long intrange;
        intrange = strtoull(argv[argind], NULL, 10);

       /** Improper allocation of memory. Fixed directly below. Thanks Marcus!
        * unsigned long long lengths[intrange+1];
        * memset(lengths, 0, sizeof(lengths));
        */ 

        unsigned long long *lengths= malloc((intrange+1) * sizeof(unsigned long long)); /* ptr points to mem. location of lengths array. */
        memset(lengths, 0, (intrange+1) * sizeof(unsigned long long));

        unsigned long long longestlen[2];
        unsigned long long seqindex;
        unsigned long long origdex;

        longestlen[0] = 0;
        longestlen[1] = 0;

        for (origdex = 2; origdex <= intrange; origdex++) 
        {
            seqindex = origdex;
            while ( seqindex > 1 )
            {
                lengths[ origdex ] += 1;
                seqindex = getnext(seqindex);

                if ( seqindex <= intrange )
                {
                    if ( lengths[ seqindex ] > 0)
                    {
                        lengths[ origdex ] =  lengths[ origdex ] + lengths[ seqindex ];
                        if ( lengths[origdex] > longestlen[1] ) { longestlen[0] = origdex; longestlen[1] = lengths[origdex]; }
                        seqindex = 1;
                        continue;
                    }
                }
            }
        }
        if(longestlen[0] > 0 ){ printf("Longest Collatz sequence for first %llu positive integers found at %llu with length %llu. \n", intrange, longestlen[0], longestlen[1]); }

    }
    return 0 ;
}

Answer 1

如果你让你的程序通过调试器运行(在我的例子中:

gcc -o collatz -g collatz.c
gdb --args collatz 2000000
$run
...segfault at memset(lengths,0,sizeof(lengths))...

),当您尝试访问长度时，您会发现您的段错误发生了!

关键是你为数组做动态内存分配是错误的；这在 C 中有点棘手(这就是为什么我通常建议来自其他语言的人学习现代 C++ 而不是 C)。

你应该这样做

unsigned long long *lengths = malloc(...);

给你新分配的内存。

此外，sizeof(lengths) 是错误的，因为那将是指向数组开头地址的指针的大小。请改用 sizeof(unsigned long long)。当然，您的代码必须读取 memset(lengths, 0, sizeof(unsigned long long)*(intrange+1)) 以设置 intrange+1 倍数unsigned long long 占 0 字节的字节数。

有关malloc 的详细信息，如果您在具有man 的系统上，则可以使用man malloc；通常，您必须在使用后“释放”使用 malloc 分配的内存。在你的情况下，程序终止时它会自动完成，但对于更复杂的软件，不会调用 free(ptr) 你通过 type *ptr = malloc(.. .) 在您不再需要该内存之后就是内存泄漏。

同样，这是一个非常典型的 C 语言问题。如果您使用 C++ 编写代码，您将能够使用诸如 std::vector 之类的东西来为您提供具有自动构造和值填充功能的可变大小数组，而几乎不会对性能造成任何影响，它将在离开声明它的范围时自动释放。