检查位集大小时出现分段故障
当我尝试运行下面的代码时,我得到一个分段错误。我尝试注释掉一些代码,发现条件为j < is_prime.size()
的WHILE循环才是罪魁祸首。这让我感到困惑,因为我在其上方的for循环中的相同值之间执行了相同的检查,但没有得到分段错误。
有人能给我解释一下这里有什么问题吗?
我在Linux64上使用的是GCC 4.8.2。
#include <bitset>
#include <iostream>
using namespace std;
const size_t max_pandigital = 987654321;
int main()
{
bitset<max_pandigital/3> is_prime;
is_prime.set(); // assume all numbers are prime
is_prime[0] = false; // 1 is not prime
for(size_t i = 1; i < is_prime.size(); i++) {
if(is_prime[i]) {
int n;
if(i%2 == 0) n = 3*i+1;
else n = 3*i+2;
size_t j = i;
if(j%2 == 0) j += n-2;
else j += n+2;
while(j < is_prime.size()) {
is_prime[j] = false;
if(j%2 == 0) j += n-2;
else j += n+2;
}
}
}
//cout << is_prime[899809363/3] << endl;
}
编辑:我实现了一些建议的更改。这是一个正常运行的版本-运行时间约为13秒。我认为最大的瓶颈是为布尔向量分配42MB。谢谢!
#include <iostream>
#include <vector>
using namespace std;
const size_t max_pandigital = 987654321;
int main()
{
vector<bool> not_prime(max_pandigital/3);
not_prime[0] = true; // 1 is not prime
for(size_t i = 1; i < not_prime.size(); i++) {
if(~not_prime[i]) {
int n;
if(i%2 == 0) n = 3*i+1;
else n = 3*i+2;
size_t j = i;
if(j%2 == 0) j += n-2;
else j += n+2;
while(j < not_prime.size()) {
not_prime[j] = true;
if(j%2 == 0) j += n-2;
else j += n+2;
}
}
}
cout << not_prime[899809363/3] << endl; // prime
cout << not_prime[100017223/3] << endl; // pseudoprime
}
解决方案
如果注释掉的是注释,并且我运行了您的代码,那么我会因为堆栈溢出而得到一个段错误。(即使代码仍然被注释掉,堆栈仍然溢出,这解释了您所看到的情况)。
典型系统默认的堆栈大小约为1 MB;但您的位集需要大约40 MB的存储空间。
要解决此问题,您可以:
- 动态分配位集
- 使用其他容器,如
vector<bool>
- 告诉您的环境使用更大的堆栈大小
动态分配的示例可能是:
unique_ptr< bitset<max_pandigital/3> > ip { new bitset<max_pandigital/3> };
auto &is_prime = *ip;
和代码的睡觉一致。
相关文章