c++ - for循环在大数字上崩溃

Question

我有一个问题。我必须编写一个程序来计算随机生成的数字表的碰撞(碰撞测试)。例如表 [1,2,2,3,4,5,5,5,6] 有 3 次冲突。

我的问题是，每当我尝试将数字 n 增加到例如 int n = 5191401; 时，我的程序就会崩溃。怎么了？为什么它停止工作？我需要大量的随机数(例如 10^14)。

这是我的代码:

#include <iostream>
#include <gsl/gsl_rng.h>
#include <stdlib.h>
#include<cmath>

using namespace std;

int compare(const void * a, const void * b)
{
    return ( *(int*)a - *(int*)b );
}

int main (void)
{
    unsigned int seed=10540000;
    gsl_rng * r=gsl_rng_alloc (gsl_rng_minstd);
    gsl_rng_set(r,seed);
    gsl_rng_env_setup();
    int lPrzedzialow=400000000;
    int n = 519140;
    int z,lKolizji=0;
    int lwKomorkach[n-1];
    double dlPrzedzialu=1./(lPrzedzialow);

    for (int i = 0; i < n; i++)
    {
        lwKomorkach[i]=floor(gsl_rng_uniform (r)/dlPrzedzialu)+1;
    }

    qsort (lwKomorkach, n, sizeof(int), compare);

    for(z=0;z<=n-1;z++)
    {
        if(lwKomorkach[z+1]==lwKomorkach[z])
        {
            lKolizji++;
        }
    }

    cout<<endl<<lKolizji<<endl;
    gsl_rng_free (r);

    return 0;
}

Answer 1

您的问题有两个方面。

1) 您在声明数组时使用了非标准的 C++ 语法。

2) 访问数组时很可能越界。

为了解决第一个问题，这行代码不是标准的C++。

int lwKomorkach[n-1];

C++ 中的数组必须使用编译时常量声明。此外，如果 n-1 很大，您就有超过预留堆栈空间量的风险。

缓解这种情况的方法是使用 std::vector:

#include <vector>
//...
std::vector<int> lwKomorkach(n-1);

一旦你有了这个，那么为了确保你不会越界，你可以使用 std::vector::at() 函数来检查边界:

for (int i = 0; i < n; i++)
{
    lwKomorkach.at(i) = floor(gsl_rng_uniform (r)/dlPrzedzialu)+1;
}

如果 i 超出范围，您将得到一个 std::out_of_range 异常，而不是“崩溃”或更糟，不会崩溃并相信您的程序当它确实不能正常工作时却能正常工作。您应该在其他 for 循环中应用相同的测试。

一旦解决了边界问题，就可以将代码从 at() 更改为使用 [ ]，因为边界错误已解决。

最后一个问题是qsort的使用。请改用 std::sort。 std::sort 更易于使用(无需强制转换)，更容易被编译器优化，并且适用于任何类型(而 qsort 仅适用于 POD 或 C 兼容类型)。

#include <algorithm>
//...
std::sort(lwKomorkach.begin(), lwKomorkach.end());