生成一亿个互不相同的数

为什么是一亿

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. 随机生成指定范围内的一个数,标记该数,循环此过程,直到所有该范围的数都被标记。

    用什么标记

  4. 直接用数组标记;array[Upper_bound]

  5. 用STL中的bitset;bitset<(Upper_bound/32)>,内存需求是方法1的1/32;

  6. 使用位向量;使用数组,但是每个数组元素标记32个需要生成的数,因为sizeof(int) = 4, 总共4B * 8bits/B = 32 bits; 所以内存需求和bitset一样,该方法的具体代码为(摘自编程珠玑):

#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 <MAX)
    {
        r = rand()%MAX;
        tick++;
        bool in = TEST(a,r);
        if(!in)
        {
            SET(a,r);
            ans++;
        }
        else
        {
            unsigned pos=1;
            long long inc;
            while(r<MAX)
            {
                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