重複しない乱数配列(Java版／O(n)アルゴリズム）：解説

こちらの記事で、重複値なしの乱数配列を計算量 O(n) で生成する java コードを紹介しました。
本稿では、そのアルゴリズムについて解説します。

はじめに

プログラムの処理速度を考えるとき、ともすると利用するコマンドの選択ばかりに目を向けてしまいがちです。

• 配列と ArrayList ではどちらが何割速くなるのか？
• for ループと iterator では速さは変わるのか？？
• 外部メソッド化ではなくインラインコーディングを選択すべきか？ etc、etc...

それも一つの考慮点ではありますが（しかし大した差異は出ません）、より重要なのは適切なアルゴリズムを選択することです。

例えば 1,000,000 件の key+value データの中から目的のものを検索することを考えます。

• プログラミングを始めたばかりの初心者は、ループ処理で全データをサーチするかもしれません。このとき、計算量は O(n) になります。
• データ保持形式を工夫し二分木探索を採用することにより、計算量を O(logn) に減らすことができます。
• さらに、ハッシュテーブルを利用することにより、O(1) つまり定数時間オーダーでの検索が可能となります。

選択するアルゴリズムによって、データ量が増えるにつれ10倍、100倍、ときに1,000倍かそれ以上というオーダーで差異が発生します。¹
問題の解決方法を定式化するスペシャリストたるプログラマとしては、適切なアルゴリズムを選択するための目を培っておきたいものです。（私も弱いんですけどね。トホホ...）

解説

さて、本題です。次の問題について考えます。
　　問題：『11～20 の 10 個の数字から 5 個をランダムに並べた配列を得る』

手順0：変数の準備

予め、結果を格納する配列と、作業用の配列を用意します。作業用の配列には候補の値を順に格納しておきます。

result : [  ][  ][  ][  ][  ]
work   : [11][12][13][14][15][16][17][18][19][20]

手順1：1個目の値の選択

1回目の乱数選択として、0～9 の範囲の乱数を生成します。
つまり、得たい値の範囲 11～20 で乱数を生成するのではなく、work 配列のインデックスの範囲で乱数を生成します。

2 が得られたとしましょう。
work[2] == 13 が選択されたものとして、結果の 1 つ目に保存します。
そして、work[2] == 13 は一度選択されお役御免ですので、work 末尾の work[9] == 20 と入れ替えてうしろへ追いやってしまいます。

result : [13][  ][  ][  ][  ]
work   : [11][12][20][14][15][16][17][18][19][13]

手順2：2個目の値の選択

さて、次に2回目の乱数選択です。
今度は 0～9 ではなく、一つ少ない 0～8 の範囲で乱数を生成します。
というのは、末尾の work[9] == 13 はすでに選択済みであり用無しですから。

5 が得られたとしましょう。
work[5] == 16 が選択されたものとして、結果の 2 つ目に保存します。
そして、work[5] == 16 は一度選択されお役御免ですので、今回の範囲の work 末尾である work[8] == 19 と入れ替えてうしろへ追いやってしまいます。

result : [13][16][  ][  ][  ]
work   : [11][12][20][14][15][19][17][18][16][13]

以上の手順を繰り返すことで、求める配列を得ることができます。
繰り返す回数は、求める配列の長さである 5 回で十分です。

もう一工夫

さて、上記は穏やかな例でしたが、次のような場合はどうでしょうか。
　　問題：『1～1,000,000 の百万個の数字から 3 個をランダムに並べた配列を得る』

result : [ ][ ][ ]
work   : [1][2][3][4][5] .. [999_998][999_999][1_000_000]

これではあまりに無駄が大きすぎます。
work のメモリ領域が無駄であるばかりでなく、work の初期化のために、計算量が result のサイズではなく work のサイズに依存してしまいます。

これを回避するために、『重複しない乱数配列(Java版／O(n)アルゴリズム）』で紹介したコードでは work 配列の代わりに HashMap を利用し、必要になったデータだけを保持するようにしています。

orz

ここまで書いたところで、このアルゴリズムに『Fisher-Yates法』という立派な名前がついていることを知りました。基本的なアルゴリズム、デザインパターンなどはちゃんと知っておかないとダメっすね... orz
分かり易く解説されているWebサイトへのリンク を貼っておきます。

最後に

しっかりとしたアルゴリズムに基づくコードは美しく、読みやすいものです。
アルゴリズムはプログラミング言語の種別を超えた汎用的なものです。
プログラマの基本道具・共通言語として、ポケットにたくさん詰め込んでおきたいものです。

注釈

1. まぁ今のご時世、百万件くらいまでであれば、ベタな O(n) アルゴリズムでも実用上は困らないかもしれません。1000件くらいまでであればベタループが最も速いかもしれません。しかしそれを選ぶとしても、他の様々な可能性（アルゴリズム）を理解したうえで選択したいものです。 ↩