配列のランダマイズに関するアルゴリズム

いきなり全然関係ないが、「らんだまいず」と打って一発変換で「乱打舞図」と出た。暴走族とか必殺技の名前かなんかかよ。（ちなみに、気になってググってみたら「もしかして：ランダマイズ」と出た。さすがGoogle先生。また、それとは別に「乱打舞」という和太鼓の演武みたいなものがあるそうな。）

……本題。
この前から「アルゴリズム・イントロダクション（上）」という情報科学の教科書みたいなものを読んでるのだが、そこで乱択アルゴリズムの話が出ていた。
そこに、"PERMUTE-BY-SORTING"と"RANDOMIZE-IN-PLACE"という二つの配列ランダマイズ手続きが紹介されていた。
そこで、実際どのくらい速度が違うのか、演習がわりにJavaで書いて速度を比べてみた。（勿論教科書なので、演習問題は別にしっかり本に載ってるのだが）

まず、PERMUTE-BY-SORTINGの方だが、これは配列（「Ａ」とする）の各要素にランダムな整数値を付加し、それをキーとして昇順or降順ソートすることでランダムに並べ替えようというものだ。
こんな風に↓

A[0]:1332
A[1]:-233
A[2]:4550
A[3]:980
↓（ソート）
A[1]:-233
A[3]:980
A[0]:1332
A[2]:4550

なるほど。そんな方法が。
実際に書く場合は、「配列に値を付加する」なんてことはできないので、（二つの整数値を保持できるクラスを用意すればできなくもないだろうが、面倒だし遅くなりそうなのでやめておく。）同じサイズの配列を用意して、そこにランダムな整数値を入れてＡと一緒にソ−トする……なんて方法で実装してみた。
（ちなみに、厳密に言うとランダム整数値が偶然ダブった場合は一様ランダム置換かどうかに疑問が残る。というかそれを確かめるのが演習になってたのだが、まだやってない。）

で、ソートアルゴリズムだが、せっかくなので
・マージソート
・クイックソート
の二種類を書いて比べてみた。

まずはマージソート版。



import java.util.*;

class Per_by_Sort{

	public static void MERGE(int P[],int A[],int p,int q,int r){

		

		int L[]=new int[q-p+2];

		int R[]=new int[r-q+1];

		System.arraycopy(P,p,L,0,q-p+1);

		System.arraycopy(P,q+1,R,0,r-q);

		L[q-p+1]=2147483647;

		R[r-q]=2147483647;

		

		int La[]=new int[q-p+2];

		int Ra[]=new int[r-q+1];

		System.arraycopy(A,p,La,0,q-p+1);

		System.arraycopy(A,q+1,Ra,0,r-q);

		La[q-p+1]=2147483647;

		Ra[r-q]=2147483647;

		

		int iL=0,iR=0;

		for(int i=p;i<=r;i++){

			if(L[iL]<R[iR]){

				P[i]=L[iL];

				A[i]=La[iL];

				iL++;

			}else{

				P[i]=R[iR];

				A[i]=Ra[iR];

				iR++;

			}

		}

	}

	

	public static void MERGE_SORT(int P[],int A[],int p,int q){

		if(q>p){

			int j=(int)((q-p)/2)+p;

			MERGE_SORT(P,A,p,j);

			MERGE_SORT(P,A,j+1,q);

			MERGE(P,A,p,j,q);

		}

	}

	

	public static void main(String args[]){
		final int len=3000000;

		int a[]=new int[len];

		int p[]=new int[len];

		Random Generator=new Random();

		for(int i=0;i<len;i++){

			a[i]=i;

		}

		

		//ソートするキーとなるランダムなint値を設定

		for(int i=0;i<len;i++){

			p[i]=Generator.nextInt();

		}

		

		//p[]をキーとしてa[]をソート

		MERGE_SORT(p,a,0,a.length-1);

		

	}

}

マージソートは以前書いてあったのを流用。改造に時間はかからなかった。
要素数3000000のランダム並べ替えにかかった時間は
一回目：3505msec
二回目：3362msec
三回目：3255msec
四回目：3278msec
五回目：3248msec
と、おおむね3.5秒くらいで並べ替えてくれた。

次、クイックソート版。



import java.util.*;

class Per_by_QSort{

	public static int PARTITION(int P[],int A[],int p,int q){

		//pivotをP[q](右端の値)とする。

		int pivot=P[q];

		int i=p-1;

		int temp;

		for(int j=p;j<q;j++){

			//P[j]がpivot以下ならば、iに1加えた後P[i],P[j](またA[i],A[j])を取り替える。

			if(P[j]<=pivot){

				temp=P[++i];

				P[i]=P[j];

				P[j]=temp;

				temp=A[i];

				A[i]=A[j];

				A[j]=temp;

			}

		}

		

		//pivot:P[q]をP[i+1]と入れ替える。

		P[q]=P[++i];

		P[i]=pivot;

		

		//pivotのインデックスを返す。

		return i;

	}

	

	public static void QUICK_SORT(int P[],int A[],int p,int q){

		if(q>p){

			int j=PARTITION(P,A,p,q);

			QUICK_SORT(P,A,p,j-1);

			QUICK_SORT(P,A,j+1,q);

		}

	}

	

	public static void main(String args[])

		final int len=3000000;

		int a[]=new int[len];

		int p[]=new int[len];

		Random Generator=new Random();

		for(int i=0;i<len;i++){

			a[i]=i;

		}

		

		//ソートするキーとなるランダムなint値を設定

		for(int i=0;i<len;i++){

			p[i]=Generator.nextInt();

		}

		

		//p[]をキーとしてa[]をソート

		QUICK_SORT(p,a,0,a.length-1);

	}

}

クイックソートを書くのに割と苦労した。（最終的に件の教科書を見ながら書いた。）
要素数3000000のランダム並べ替えにかかった時間は
一回目：1480msec
二回目：1528msec
三回目：1537msec
四回目：1461msec
五回目：1489msec
と、約1.5秒で置換。やはり要素数が多いだけにマージソートより速い。

次にRANDOMIZE-IN-PLACE。ちなみにこちらの方が早いと紹介されていた。
アルゴリズムはかなり単純で、for文でi=0からi=n（=A[]のサイズ）-1まで繰り返しで、

「iからn-1までの乱数rをとって、
A[i]とA[r]を入れ替える」

これだけ。

一応、このアルゴリズムが一様ランダム置換を生成するということの
証明を書いとく。帰納法でパッと解決する。
あるA[j]が
i番目に置かれる確率をP(i)とすると、
まずP(0)は0〜n-1までの乱数rにjが選ばれる確率なので、1/nである。

帰納法のため、~~漸加式~~漸化式を立てる。（５／１２追記：何でこんな初歩的なミスをorz）
P(i)=(0〜i-1番目に置かれない確率)×(rに選ばれる確率)
$P(i)=\left(1-\sum^{i-1}_{k=0} P(k)\right)\times\frac{1}{n-i}$

ここで、k<iでP(k)=1/nが成り立つとすれば、
$P(i)=\left(1-\frac{i}{n}\right)\times\frac{1}{n-i}$
$P(i)=\left(\frac{n-i}{n}\right)\times\frac{1}{n-i}$
$P(i)=\frac{1}{n}$
よって、帰納法が完成した。

で、Javaで書いたソースがこちら。



import java.util.*;

class Per_by_Replace{

	

	public static void main(String args[]){

		final int len=3000000;

		int a[]=new int[len];

		for(int i=0;i<len;i++){

			a[i]=i;

		}

		

		Random Generator=new Random();

		int temp;

		int nexti;

		for(int i=0;i<len;i++){

			//0からlen-iまでの乱数を生成

			nexti=Generator.nextInt(len-i);

			

			//iからlenまでの乱数にする

			nexti+=i;

			

			//a[i]とa[nexti]とを取り替える

			temp=a[nexti];

			a[nexti]=a[i];

			a[i]=temp;

		}

	}

}

要素数3000000を並べ替えるのに要した時間は
一回目：595msec
二回目：588msec
三回目：573msec
四回目：577msec
五回目：622msec
と、約0.6msecだった。
やはりアルゴリズムの違いは顕著だ。

まあ、今回試したのはこんなとこ。
それにしても最近アルゴリズムの実行時間計測のテーマばっかやってる気がする。始まったばかりのブログがコレじゃあそういうテーマだと思われるよね……

まあ、それも面白そうだけど、もうちょっと広範な話題を書くところにしたいので、次は数学のテーマでなんか書けたらなあと思ってたりします。

では今日はこの辺で（・ω・）ﾉｼ

……それにしても、始まったばかりのブログが６日も更新が滞ってるのはなかなか危険な状態だなあ……