重複無の乱数発生

重複無の乱数を発生するためのプログラムです。

重複無の乱数発生について、本来ならば一度発生した乱数を配列に登録していき、すでに登録されている乱数が発生されればその乱数は破棄する等の手順をとりますが、そうすると、必要な乱数の数よりも多い計算回数を必要とします。

そこで、乱数発生の数を必要な数値の数と同じにし、判定の手順も必要としないアルゴリズムを以下のように考えて見ました。

下記のプログラムで、 

int flg_a[RAND_N];
は変数用の変換テーブルであり、必要な乱数の数(RAND_N)をこの変換テーブルを利用することにより次第に減らしていく工夫を取っています。全ての数が発生すれば必要な数が0になります。

このアルゴリズムでは、変換テーブルの変換の変換手順や配列の準備が必要な点、膨大な数の乱数発生には対処しているとは言えませんが、乱数を発生する数は最大必要な乱数の数と全く同じであり、不必要な乱数を破棄することがありませんので、多少は高速なアルゴリズムになると思います。

下のプログラムでは、通常のアルゴリズムと比較した時間も表示するようになっています。必要な乱数の数は10000としています。

重複無の乱数発生(list_28.c) 
//-----------------------------------------------------------------
// rand_nodp.c :
//    重複無の乱数発生: 発生数が大きいときの考慮
//    配列にランダムな数列を挿入[重複なし]
//                 Last Update: <2004/11/26 22:04:36 A.Murakami>
//-----------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#include <unistd.h>

#define RAND_N 10000
//#define LIST_NUM
//-----------------------------------------------------------------
enum RANDOM_OPTION {
    RAND_NODP1 = 0,
    RAND_NODP2 = 1
};
//-----------------------------------------------------------------
void set_random(int rndopt,int rand_n,int* data);
int rintv(double value);
int random(int max,unsigned long* idum);
double calc_cps();
inline unsigned long long int RDTSC(void);
//-----------------------------------------------------------------

int main()
{
    int i;
    double cpers=calc_cps(); // 時間測定設定
    int data[RAND_N];
    clock_t t1,t2;
    //--------------------------------------------------
    // 変換テーブルの使用
    //--------------------------------------------------
    t1 = clock(); // 開始
    set_random(RAND_NODP1,RAND_N,data);
    t2 = clock(); // 終了
    // 処理時間
    printf("time of loop = %d clock, %lf[sec]\n",
           t2-t1,(double)((t2-t1)/cpers));
#ifdef LIST_NUM
    for(i=0;i<RAND_N;i++) printf("%d  ",data[i]);
    printf("\n");
#endif
    //--------------------------------------------------
    // 乱数発生: 通常
    //--------------------------------------------------
    t1 = clock(); // 開始
    set_random(RAND_NODP2,RAND_N,data);
    t2 = clock(); // 終了
    // 処理時間
    printf("time of loop = %d clock, %lf[sec]\n",
           t2-t1,(double)((t2-t1)/cpers));
#ifdef LIST_NUM
    for(i=0;i<RAND_N;i++) printf("%d  ",data[i]);
    printf("\n");
#endif
    return 0;
}
//-----------------------------------------------------------------
// 配列にランダムな数列を挿入[重複なし]
//-----------------------------------------------------------------
void set_random(int rndopt,int rand_n,int* data)
{
    int i,val,rcnt=0;
    unsigned long idum = time(NULL); // 乱数発生初期化
    memset(data,0,sizeof(int)*rand_n);
    //--------------------------------------------------
    // 変換テーブルを用いた乱数発生
    //--------------------------------------------------
    if(rndopt == RAND_NODP1){
        int rn = rand_n-1;
        // 変換テーブル
        int* flg_a=(int*)calloc(rand_n,sizeof(int));
        // 変換テーブル準備 
        for(i=0;i<rand_n;i++) flg_a[i]=i;
        // 重複無乱数の発生
        while(rn!=-1){
            val = random(rn,&idum);
            data[rcnt++] = flg_a[val];
            // 変換テーブルの更新
            for(i=val;i<rn;i++) flg_a[i]=flg_a[i+1];
            // 乱数発生数を減らす
            rn--;
        }
        free(flg_a);
    }
    //--------------------------------------------------
    // 通常
    //--------------------------------------------------
    else {
        while(rcnt<rand_n){
            int flg = 0;
            val = random(rand_n-1,&idum);
            for(i=0;i<rcnt;i++){
                if(data[i]==val){ flg=1; break; }
            }
            if(!flg) data[rcnt++]=val;
        }
    }
}
//-----------------------------------------------------------------
// 乱数発生用
//-----------------------------------------------------------------
// double型データをint型へ
int rintv(double value)
{
    if(value > 0) return (int)(value + 0.5);
    else return (int)(value - 0.5);
}
// 0〜max までの乱数の発生(int型)
int random(int max,unsigned long* idum)
{
    *idum=(*idum)*1103515245 + 12345;
    return rintv(max * ((double)(*idum/65536 % 32768) / (double)32767));
}
//-----------------------------------------------------------------
// 時間計測用
//-----------------------------------------------------------------
// １秒間のクロック数計測
double calc_cps()
{
    struct timeval tv1,tv2;
    unsigned long long tsc1,tsc2;
    gettimeofday(&tv2,NULL); tsc2=RDTSC();
    usleep(250);
    gettimeofday(&tv1,NULL); tsc1=RDTSC();
    return (double)(tsc1-tsc2)/((tv1.tv_sec-tv2.tv_sec)*1000000
                                +(tv1.tv_usec-tv2.tv_usec));
}
// 時間測定用
inline unsigned long long int RDTSC(void)
{
    unsigned int h,l;
    /* read Pentium cycle counter */
    __asm__(".byte 0x0f,0x31":"=a" (l),"=d" (h));
    return ((unsigned long long int)h<<32)|l;
}

result 
time of loop = 330 clock, 0.249716[sec]   --> 変換テーブルを用いた乱数発生
time of loop = 3014 clock, 2.280742[sec]  --> 通常
inserted by FC2 system