生成一亿个互不相同的数

为什么是一亿

1 从编译器&操作系统考虑
在ubuntu12.04 + g++4.6.3的实验中,32位的操作系统只能开出1<<28的数组,在64位操作系统中这一数值是1<<30;
如果采用STL中的bitset,那么32位操作系统中最大能开出1<<31,在64位操作系统中开出1<<34(如果再大ld会报错);
以上的数组都是在程序的global scope中开出,空间在程序的DATA 或者 BSS 段,且这两个段都取决与所用的操作系统。
2 从磁盘空间考虑
1<<30个数需要的空间为1<<32Bytes = 4GB

生成指定范围内所有互不相同的数

解法的一般思路:
1. 将需要生成的数顺序存放,随机生成下标,取出对应下标的值,将最后的数填补到刚刚的下标对应的位置上,修改随机数生成的下标,循环此过程。
2. 将需要生成的数顺序存放,随机生成下标,标记该数已被访问,循环直到所有数都被标记。
3. 随机生成指定范围内的一个数,标记该数,循环此过程,直到所有该范围的数都被标记。

用什么标记

  1. 直接用数组标记;array[Upper_bound]
  2. 用STL中的bitset;bitset<(Upper_bound/32)>,内存需求是方法1的1/32;
  3. 使用位向量;使用数组,但是每个数组元素标记32个需要生成的数,因为sizeof(int) = 4, 总共4B * 8bits/B = 32 bits; 所以内存需求和bitset一样,该方法的具体代码为(摘自编程珠玑): ```C++ #define BITSEPRWORD 32 #define SHIFT 5 #define MASK 0x1F

int a[1 +100000000/BITSEPRWORD];
int set(int i) { a[i>>SHIFT] |= (1<<(i&MASK));}
int clr(int i) { a[i>>SHIFT] &= ~(1<<(i&MASK));}
itn test(int i) { return a[i>>SHIFT] & (1<<(i&MASK));}

# 实例
一种基于位向量和rand()的实现方法

define BITSWORD 32

define SHIFT 5

define MASK 0x1f

define SET(A,POS) (A[POS>>SHIFT] |= (1<<(POS&MASK)))

define CLR(A,POS) (A[POS>>SHIFT] &= ~(1<<(POS&MASK)))

define TEST(A,POS) (A[POS>>SHIFT] & (1<<(POS&MASK)))

define MAX (0x1ULL<<27)

unsigned a[1+MAX/BITSWORD]={0};
int main()
{
unsigned r,ans=0;
long long tick = 0, confilicts =0;
while(ans <MAX)
{
r = rand()%MAX;
tick++;
bool in = TEST(a,r);
if(!in)
{
SET(a,r);
ans++;
}
else
confilicts++;
}
cout<<tick/1024/1024<<"M"<<endl;
cout<<confilicts/1024/1024<<"M"<<endl;
return 0;
}

以上算法的结果为:

182.29 S //执行时间
2479 M //总共生成的随机数,M=1024*1024
2351 M //冲突的个数

也就是说,为了生成一千万个数,rand执行了2479M次,而且只生成了一千万个。

下面是一种改进的算法,对于每次生成的随机数,如果之前已经生成过了,那么根据遍历找到第一个没有被标记的数,然后输出。

define BITSWORD 32

define SHIFT 5

define MASK 0x1f

define SET(A,POS) (A[POS>>SHIFT] |= (1<<(POS&MASK)))

define CLR(A,POS) (A[POS>>SHIFT] &= ~(1<<(POS&MASK)))

define TEST(A,POS) (A[POS>>SHIFT] & (1<<(POS&MASK)))

define MAX (0x1ULL<<30)

unsigned a[1+MAX/BITSWORD]={0};
int main()
{
unsigned r,ans=0;
long long tick = 0;
long long confilicts =0;
while(ans {
r = rand()%MAX;
tick++;
bool in = TEST(a,r);
if(!in)
{
SET(a,r);
ans++;
}
else
{
unsigned pos=1;
long long inc;
while(r {
inc = pos*pos;
if((r+inc)>MAX || (r-inc)<0)
break;
if(!TEST(a,r+inc))
{
SET(a,r+inc);
ans++;
break;
}
else if(!TEST(a,r-inc))
{
SET(a,r-inc);
ans++;
break;
}
pos++;
}
if((r+inc)>MAX || (r-inc)<0)
confilicts++;
}
}

cout<<"total random: "<<tick/1024<<"k"<<endl;
cout<<"confilicts: "<<confilicts<<endl;
return 0;

}

以上算法结果:

732.19 S
1049039k
474631