C++编译需要永远

Question

我在Windows下用gcc编译器编译了下面的简短C++代码

#include <iostream>

#define MAXN 1000000009

using namespace std;

bool prime[MAXN] = {true};

int main()
{
    for (int p = 2; p * p <= MAXN; ++p)
        if (prime[p])
        {
            cout << p << "\n";

            for (int i = p * p; i <= MAXN; i += p)
                prime[i] = false;
        }

    return 0;
}

上面打印素数小于与埃拉托色尼的筛和1E9的代码没有任何错误,但我注意到,编译过程会花费更长的时间比其他的我的C++程序编译,花了大约几分钟,并没有错误完成消息.为了验证,我再次编译时获得了相同的结果.甚至更奇怪,在编译之后,代码没有打印任何东西并返回退出代码为0.我不明白发生了什么.是什么原因导致了这种奇怪

Answer 1

首先,它不是一个复杂的(你的程序不是一流的,而是简单的),而是一个汇编.

在我的Linux桌面上(在Debian/Sid下使用i5-4690s和GCC 8),使用g++ p.cc -o p.bin不太理想的代码进行编译需要大约8.2秒(当然不是永远).

为什么需要这么多？因为你有一个初始化但是巨大的全局变量(你prime的布尔数组).因此编译器必须生成一个巨大的二进制可执行文件(大约一千兆字节,其中大部分是.data段).

如果您没有静态地初始化该全局,而只是在您的main函数内部,通过具有

bool prime[MAXN];
int main() {
  prime[2] = true;

生成的可执行文件变得很小 - 约17K字节 - (因为现在prime位于.bss段中),编译时间约为0.45秒.

如果你想初始化所有的元素prime,你应该使用一个for循环(或者一些std::memset,初始化元素的范围时相同的值).

你应该在编码之前考虑更多.阅读素数和素数测试.你不需要这么大的prime 数组,因为你循环? MAXN时间(这是你需要的最大索引),即31623次.因此,您只能声明bool prime[32000];(并将程序更改为仅使用该范围内的元素).

实际上,当你需要大量内存时,你最好使用堆内存.

如果使用C++编码,请利用其标准容器.

当然,阅读如何调试小程序.

顺便说一下,你的程序非常低效.运行大约需要10秒(p.bin > /tmp/p.out与重定向一样,/tmp/p.out需要3401行).为了进行比较,BSD primes程序(在/usr/games/primes我的Debian上)在运行时primes 2 31608 > /tmp/pp.out需要不到2毫秒的时间来生成完全相同的输出文件,因此运行速度比您的快5000倍.

由nm评论你的原始程序有未定义的行为(你应该害怕),因为该primes[MAXN]元素不存在(你有一个缓冲区溢出)但你错误地使用它.因此,更换内<= MAXN用< MAXN或声明bool prime[MAXN+1];