【C言語】1～100万までの数字をランダマイズする(1)

マイクロシミュレーションのコードを組む仕事を受けることになった。10年前にやったのとほぼ同じ内容なのだが、前回はPerlで組んで、すごく時間がかかったので、今度はCで組むことになった。

とりあえずVisual Studio Community 2017を入れた。このGUIで作業するのではなくて、cl.exeというコマンドラインでコンパイルできる。Cのソースをfoo.cppとして、開発者コマンドプロンプト上で

cl /EHse foo.cpp

とすれば、foo.objとfoo.exeが生成される。その後exeファイルを起動すればよい。

さて、サンプルプログラムを作るのだが、実際の処理でも使う、70～130万件のデータを順次処理する際に、その順番をランダマイズする必要がある。Perlだと、

use strict;
use List::Util;
my @data = List::Util::shuffle (1..1000000);

で済んでしまうことにてこずってしまった。

配列を静的に確保するとprintfが効かなくなる？

以下のようなコードを作って問題なくコンパイルはできたが、起動しても何も表示されない。起動から終了まで数秒かかる。

#include <stdio.h>
#include <stdlib.h>

void main() {

	int i;
	int seekno[1000000];

	for (i=0; i<1000000; i++) {
		seekno[i] = i;
	}

	for(i=0; i<1000000; i++) {
		int j = rand() % 1000000;
		int t = seekno[i];
		seekno[i] = seekno[j];
		seekno[j] = t;
	}

	// シャッフル後の配列の冒頭10件を表示してみる
	for (i=0; i<10; i++) {
		printf(" %6d", seekno[i]);
	}
	printf("\n");

}

結局この原因はわからないまま、ポイントを使うことにした。

#include <stdio.h>
#include <stdlib.h>

void main() {

	int i;
	int *seekno;
	seekno = (int *)malloc(1000000 * sizeof(int));

	for (i=0; i<1000000; i++) {
		seekno[i] = i;
	}

	for(i=0; i<1000000; i++) {
		int j = rand() % 1000000;
		int t = seekno[i];
		seekno[i] = seekno[j];
		seekno[j] = t;
	}

	// シャッフル後の配列の冒頭10件を表示してみる
	for (i=0; i<10; i++) {
		printf(" %6d", seekno[i]);
	}
	printf("\n");


}

すると、数字が偏ってる問題はあるが、とりあえず表示されるようにはなった。

 971489 914808 990918 974833 922197 975988 971877 966486 987919 967308

srand()を呼び忘れた

次に、上記のプログラムを何度実行しても、同じ結果になることに気づいた。おかしい…

それで、いろいろ調べていたところ、srand()を呼ぶ必要があることに気づいた！

Perlではrandを呼び出したときに自動的にsrandも呼び出されるようになったのだが、すっかり当たり前になっていて忘れてしまっていた。あらためてこれをいちいち指定しなければならないと考えると不便に感じた。Cだから仕方がないのか。

rand()の挙動が違う

Perlでは、randは、0～1の間の浮動小数点数をランダムに返す関数だが、Cでは、0～RAND_MAXまでの整数をランダムに返す。なので、0～Nまでの数を返すようにするためには、Nで割った剰余を求める方法が使われるようだ。

当方の環境で、RAND_MAXは32767であった。

上記のコードで、結果が偏っている原因がわかった。int  j = rand() % 1000000 は、結局のところ、0 <= j < 32767 の数しか返さない。

それで、Perlのrandの挙動になるようなコードに書き換えたところ、偏りはほぼなくなった。

	for(i=0; i<1000000; i++) {
		int j = (int)(rand() * 1000000.0 / RAND_MAX);
		int t = seekno[i];
		seekno[i] = seekno[j];
		seekno[j] = t;
	}

  1251 563585 193304 808740 585009 479873 350291 895962 822840 746604

 (2)につづく