「解きながら学ぶJava入門編」のアルゴリズムについて

はじめまして。
新人プログラマーで、現在、柴田望洋氏の「解きながら学ぶJava 入門編」を四苦八苦しながら解き進めています。
今回は上記書籍に載っている、とあるアルゴリズムについてご質問させていただきたく思います。

問題6-13(191ページ~192ページ）「配列の要素の並びをシャッフルする(ランダムな順となるようにかき混ぜる)プログラム」を作成する問題についてです。
回答には以下のような答えが載っておりますが

Java
1	public static void main(String[] args) {
2		Random rand  = new Random();
3		Scanner stdIn = new Scanner(System.in);
4
5		System.out.print("要素数：");
6		int n = stdIn.nextInt();
7		int[] a = new int[n];
8
9		for(int i =0; i < n; i++){
10			System.out.print("a[ "+ i + "] = ");
11			a[i] = stdIn.nextInt();
12		}
13
14//////////////////シャッフルの処理///////////////////
15		for(int i = 0; i < 2 * n; i++) {
16			int idx1 = rand.nextInt(n);
17			int idx2 = rand.nextInt(n);
18			int t = a[idx1];
19			a[idx1] = a[idx2];
20			a[idx2] = t;
21		}
22//////////////////////////////////////////////////////
23
24		System.out.println("要素をかき混ぜました。");
25		for(int i =0; i < n; i++){
26			System.out.println("a[ "+ i + "] = " + a[i]);
27		}
28
29	}

一方で、次頁にはシャッフルの処理部分で「もっと効率のよいアルゴリズムも考案されてます」とあり、以下のコードが紹介されています。

Java
1//////////////////シャッフルの処理///////////////////
2		for(int i = n - 1; i > 0; i--){
3			int j = rand.nextInt(i + 1);
4			if(i != j) {
5				int t = a[i];
6				a[i] = a[j];
7				a[j] = t;
8			}
9		}
10//////////////////////////////////////////////////////
11

このコードについて疑問点が２つあります。

①なぜrand.nextInt(i + 1);の箇所でループ毎に生成する乱数の数を減らしていくのか？
②for(int i = n - 1; i > 0; i--)と配列の後ろ→前にかけて探索していくのはなぜか？
for(int i = 1; i < n; i++)として前→後ろの順で探索して言っていけない理由は？

どなたかご教示いただけたら幸いです。よろしくお願いします。

行動規範の内容に同意します

回答4件

ベストアンサー

「箱のなかにn個のボールがあり，順番に取り出して並べる」とイメージするといいかもしれません．
n=10として，1~10の番号が書かれたボールが入っているとします．

[1 2 3 4 5 6 7 8 9 10]

この中からランダムに1つ取り出します．仮に「3」を取ったとしましょう．
これを箱から出すのですが，それを配列の中で分離します．
そのために，配列の最後と選ばれた要素を入れ替えます．すると

[1 2 10 4 5 6 7 8 9 | 3]

この|の左側が箱の中，右側が箱の外で並べられているとお考えください．
この状態で次のボールを出します．箱の中身は1個取り出したので残り9個(|の左側)です．
これが

①なぜrand.nextInt(i + 1);の箇所でループ毎に生成する乱数の数を減らしていくのか？

の答えです．取り出すたびに箱の中のボールは減っていくので，その分取り出す範囲を狭めなければなりません．
次に「6」が選ばれたとしたら，この場合はすでに出した「3」の前に置きます．つまり

[1 2 10 4 5 9 7 8 | 6 3]

こうなります．これを最後まで繰り返しているのが「効率のよいアルゴリズム」として提示されているコードです．
これを踏まえれば，

②for(int i = n - 1; i > 0; i--)と配列の後ろ→前にかけて探索していくのはなぜか？
for(int i = 1; i < n; i++)として前→後ろの順で探索して言っていけない理由は？

これは，「この場合は」後ろから探索しているだけで，同じ要領で前から探索する方法でも可能です．
ただし，出したボールを置く位置は配列の最初の方から順番になり，乱数の下限がループ毎に上がっていくことに注意しなければいけません．

投稿2015/09/13 15:42

編集2015/09/13 15:57

swordone

総合スコア20651

nakanohitobot

2015/09/14 15:27

ご回答有り難うございます。非常にイメージし易いです！ここまでわかりやすく解説していただけるとは質問して良かったと感じております。しかし、理解力不足で申し訳ありませんが一点だけ疑問があります。＞取り出すたびに箱の中のボールは減っていくので，その分取り出す範囲を狭めなければなりません．とありますが、実際には取り出したボールは減らず、すでに指定した位置を再度指定しても問題はありませんよね？例えば [1 2 10 4 5 9 7 8 | 6 3] でi = 8の時に、|の右側にある６,３の要素番号8,9が指定されてもシャッフルできてしまいます。わざわざ、減らすして考えるのはなぜなのでしょうか？

swordone

2015/09/14 15:55 編集

要素の並び順の確率を一様にするためです．今10個のボールを使っていますが，この方法で行くと例えば「1」が最初に取り出される=配列の最後に並ぶ確率は1/10です．「1」が2番目に取り出され，最後から2番目に並ぶ確率は，最初に選ばれない9/10と2回目に選ばれる1/9を掛けて1/10になります．以降，「1」がどの位置に来るのも等確率になるのです．当然他の数字もどこに並ぶかは等確率になります．すでに取り出したボールも入れ替え対象にしてしまうと，この確率の均等さが失われてしまいます．簡単に言うと，公平に選ばれたはずの10番目の要素が，あとから入れ替わったのでは(しかもその時の10番目が選ばれるチャンスもなければ)不公平ですよね？

swordone

2015/09/15 00:22

ちょっと上の説明ではわかりにくかったので，改めて説明します．「シャッフルする」と言うとややこしくなりますが，やりたいのは「無作為な方法での順不同への並び替え」です．このアルゴリズムでやってるのは，無作為に箱から取り出した順番に後ろから並べていることなのです．箱の中から取り出して|の右側に並べたボールは「すでに位置が確定した要素」なのです．箱の中から取り出したいのに，箱の外にあるボールまでもう一回出そうとするのはおかしいですよね？順列のパターンを書き出す時に使う樹形図を思い浮かべてください．1番目に取り出した要素の次に並ぶ可能性のあるのは，まだ選ばれていない要素ですよね？10個だと多すぎるので，4つの数字の並び順の樹形図を書いてみてください．

nakanohitobot

2015/09/16 00:10

わざわざ丁寧なご回答ありがとうございます。数学の問題ですね。よくわかりました。まだコーディングで一杯一杯でして、アルゴリズムまで考えることは難しいですが、徐々に慣れていきたいと思います。回答いただいた皆さんをベストアンサーにしたいのですが、お一人しか選べないということで、swordoneさんを選ばせていただきます。今回は本当にありがとうございました。

行動規範の内容に同意します

①は当然です。カードの山から一枚ずつ抜いて新しい山に置いていくような動きですから、処理が進むにつれて元の山は小さくなり、つまり乱数の範囲も小さくしていくことになります。

②は、どちらでもかまいませんが、私も後ろから前へ走査するように書くと思います。その方が文字数も少なくシンプルに書けますので。

投稿2015/09/13 15:39

yuba

総合スコア5568

nakanohitobot

2015/09/14 14:34

ご回答有り難うございます。 ①に関して、「カードの山」とはわかりやすい例えですね。コードを読んだ時に、こういったイメージが浮かんでくるようになりたいです。 ②に関しては他の方もおっしゃっていますが、どちらでも良いようなので安心しました。ただ、シンプルか？というと初心者の私としてはよくある前→後ろ探索のほうがシンプルに感じてしまいます＾＾；

yuba

2015/09/16 03:30

②で後ろ→前がシンプルである理由についてです。山が小さくなっていくので、乱数範囲は 0～51、0~50、0～49、…という風に縮めていきますよね。そういう乱数がjとして取れているので、元の山にはa[j]という風にアクセスできると楽なわけです。配列aが「元の山」「新しい山」を兼ねていますので、前半が「元の山」ということにすればa[i]でアクセスすれば前半部分である元の山に当たります。すると、シャッフルが進むにつれて後半部分が大きくなる、つまり「仕切り」が後ろ→前に動いてくるわけです。この「仕切り」こそがiですね。

nakanohitobot

2015/09/20 02:19

返信遅くなってすいません。乱数の値を、そのまま要素番号に利用できるからなんですね。ありがとうございました。

行動規範の内容に同意します

シャッフルについての参考情報を紹介します。

世界最速の配列シャッフルアルゴリズム、Fisher-Yatesアルゴリズム http://pandanoir.seesaa.net/article/341955064.html

teratail でも過去に数回、シャッフルについての質問がでています。

ゲームにおいて、ランダムに手を配る手法の妥当性 https://teratail.com/questions/11484
重複しない乱数 https://teratail.com/questions/7924
java hit&blow https://teratail.com/questions/6892
Javaで配列をランダムに表示させたい https://teratail.com/questions/434

投稿2015/09/13 21:55

katoy

総合スコア22324

nakanohitobot

2015/09/14 14:36

ご回答有り難うございます。単なるシャッフルといっても色々あるのですね。時間があるときにじっくり読ませていただきたいと考えております。

行動規範の内容に同意します

先に結論です．
①乱数の数を減らす必要はありません．
②前から順に行ってもかまいません．

＜簡単な実装の問題点＞
そもそも，簡単なシャッフルの例では十分にシャッフルできるとは言えない実装です．
シャッフルの試行回数が少ないと，一度も乱数によって選択されない要素が存在する可能性も高く，
そのような要素は移動することがありません．
そこで2 * n回要素を交換してランダムな位置に移動されない要素が存在する確率を低くしています．
しかしこの方法で試行回数を増やしても，
元の位置からランダムな位置に移動されない要素が存在する確率を０にすることはできません．
そのためシャッフル後の配置は一様に分布するとはいえなくなります．

＜高速な実装の意味＞
そこで，iを使って順にすべての要素をランダムな位置j（同じ位置に戻る場合もあり）に移動します．
逆に元の位置からランダムな位置に移動しない要素がなければ良いため，
rand.nextInt(i + 1)でもrand.nextInt(n)でもいいはずです．

＜ハードウェアによる速度向上＞
CPUなどの細かい知識の話になりますが，キャッシュのヒット率などの理由から，
rand.nextInt(i + 1)の方が若干プログラムが高速になる可能性があります．（微々たるものですが）
またif文でiとjが同じ時は入れ替えないというプログラムになっていますが，
実行環境やコンパイラによってはif文で判定をしないほうが高速になる場合もあります．
C言語でintで100000000個の配列で試したところ数%ほどifがない方が速かったです．
環境：Mac OS X Yosemite/Darwin，Intel core i7 2.8GHz，gcc 4.2.1（最適化なし）
（C言語で試したのは単純に，私がC言語を一番好きだからです）
「どうせほとんど一致しないし，一致しても挙動に問題はない，ならば毎回行うifの時間をなくそう」
という寸法です．