Rustで効率的なFisher–Yatesシャッフルを実装してみよう

Rustで有名アルゴリズムを実装して、Rustについての理解を深めることが目的の連載です。今回扱うのは、配列のシャッフルについてです。最初に何も考えずに実装してみて、次に効率的に配列の要素をシャッフルするFisher–Yatesシャッフルを実装してみましょう。

• Fisher–Yatesシャッフルを実装してみよう

コンピューターにとって適当にシャッフルは難しい

コンピューターは、人間よりも計算も速く正確に動いてくれるものですが、意外なことが苦手だったりします。そんな苦手なことの一つが「適当にシャッフルする」という作業です。

そもそも計算によって乱数を生成するのは簡単なことではありません。それで、さまざまな乱数生成アルゴリズムが提案されています。また、現在時刻やマウスの移動など、さまざまな物理現象を利用して、乱数生成を行う手法もあります。「適当さ」をコンピューターで再現するのは難しいものなのです。

Rustのrandクレートにはshuffleメソッドが用意されている

とは言え、Rustや一般的なプログラミング言語には、シャッフルを実現する機能が用意されています。Rustには標準で乱数ライブラリが備わっていないのですが、プロジェクトを作成するついでに、乱数ライブラリの「rand」クレートをインストールすることで、乱数やシャッフルを行うことができます。

randクレートには、shuffleメソッドが用意されていて、配列やVec型のシャッフルを手軽に実現できます。今日のお題である独自のシャッフル関数を実装する前に、標準的な方法も確認しておきましょう。

ターミナル(WindowsならPowerShell、macOSならターミナル.app)を起動して下記のコマンドを実行して、プロジェクトを生成しましょう。

# プロジェクトのフォルダを作成
mkdir rand_shuffle_sample
cd rand_shuffle_sample
# プロジェクトを初期化してrandクレートを追加
cargo init
cargo add rand

そして、src/main.rsに次のようなプログラムを記述しましょう。

use rand::seq::SliceRandom;
use rand::thread_rng;

fn main() {
    // Vec型の変数を作成して数値を格納 --- (*1)
    let mut numbers = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
    println!("before : {:?}", numbers);
    // シャッフル --- (*2)
    let mut rng = thread_rng(); // 乱数生成器を初期化
    numbers.shuffle(&mut rng); // シャッフル
    // シャッフル後の結果を表示  --- (*3)
    println!("after  : {:?}", numbers);
}

まずはプログラムを実行してみましょう。ターミナルで「cargo run」コマンドを実行すると、0から9までの値を格納したVec型の変数numbersをシャッフルして表示します。

• randクレートでシャッフルしたところ

プログラム自体は難しいものではありません。randクレートのSliceRandomトレイトを取り込むことで、shuffleメソッドが使えるようになります。(＊1)でRustの動的にデータを追加できるVec型の変数numbersを初期化します。そして、(＊2)でnumbersをシャッフルして、(＊3)でシャッフル後の結果を表示します。

このプログラムが面白いのが、Vec型には、shuffleというメソッドは用意されていないという点にあります。Rustでは、型に直接メソッドを追加するのではなく、トレイトを介して型を拡張することが可能なのです。

今回の場合で言えば、SliceRandomトレイトにshuffleメソッドが定義されており、プログラムの冒頭で「use rand::seq::SliceRandom」と宣言することにより、Vec型にshuffleメソッドが追加されたかのように振る舞わせることができます。

興味があれば、randクレートの該当するソースコードを直接見てみると良いでしょう。randクレートを読むのはとても勉強になります。

適当にシャッフルを実装してみよう

それでは、ここから、自作の関数を作ってみましょう。randクレートを使うことなく、自分でシャッフルを行う関数を実装するのです。

それで、何も頭を使わずシャッフルを実装しようと思ったら、次のような手順が思いつくのではないでしょうか。

- (1) 配列の要素数をNとしたとき、N未満の乱数をaとbを生成する
- (2) 配列[a]と配列[b]を交換する
- (3) 上記を何度も繰り返すことでシャッフルが行われる

とても原始的な方法です。この手順でシャッフル関数を作ってみましょう。コマンドラインで以下を実行してプロジェクトを作成しましょう。今度は、cargoコマンドで初期化だけを行います。

mkdir my_shuffle1
cd my_shuffle1
cargo init

なお、本連載の3回目でXorshiftを利用した乱数生成について紹介していますので、そこで作成したxorshift関数も利用してみましょう。

src/main.rsに次のようなプログラムを記述しましょう。

fn main() {
    let mut seed = 123456789; // 適当な乱数シードを指定
    // 5回シャッフル結果を表示 --- (*1)
    for i in 0..5 {
        let mut list = vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        shuffle(&mut seed, &mut list);
        println!("{}回目: {:?}", i+1, list);
    }
}

// 簡単なシャッフル関数(不完全) --- (*2)
fn shuffle(seed: &mut u64, list: &mut[usize]) {
    for _ in 0..list.len() {
        // 乱数aとbを得て、a番目とb番目の要素を入れ替える --- (*3)
        let a = random(seed) as usize % list.len();
        let b = random(seed) as usize % list.len();
        list.swap(a, b);
    }
}

// xorshiftを利用して乱数を生成する --- (*4)
fn random(seed: &mut u64) -> u64 {
    *seed ^= *seed << 13;
    *seed ^= *seed >> 7;
    *seed ^= *seed << 17;
    *seed
}

プログラムを実行してみましょう。ターミナルで「cargo run」を実行しましょう。すると下記のように表示されます。見た感じ、うまくいっています。

• 実行してみたところ

プログラムの(＊1)では5回シャッフルして結果を表示します。(＊2)ではシャッフル関数shuffleを定義します。(＊3)では、乱数aとbを得て、その位置の要素を入れ替えます。(＊4)では、Xorshiftアルゴリズムで乱数を生成します。

(＊2)の部分では、要素数の回数だけ繰り返すようにしています。繰り返し回数を増やせば、当然、ランダムにシャッフルされるのですが、同じ要素を二度選択してしまう可能性もあります。

今回は、うまくいきましたが、無意味に二度同じ要素を選んで入れ替えてしまう可能性もあるため、よくよく考えると効率が悪い方法であることも分かるでしょう。この点で、次に紹介する「Fisher–Yatesシャッフル」は、より効率的に要素をシャッフルできます。

なお、main関数の冒頭で乱数のシードを123456789と固定にしていますので、シャッフル結果が毎回同じ結果になります。毎回異なる結果にしたい場合には、この部分を、以下のように修正してください。

let mut seed = 123456789; // 適当な乱数シードを指定
// 現在時刻(UNIXエポック秒)を足す
seed += std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs(); 

この後で紹介するプログラムでも、seedが固定となっているため、必要に応じて、現在時刻などの適当なシード値を加えてください。

Fisher–Yatesシャッフルについて

「Fisher–Yatesシャッフル」は、1938年にフィッシャーとイェーツの著作にて発表されたアルゴリズムです。もともと、コンピューターを使うのではなく、紙とペンと乱数表を使うことを想定したものでした。彼らが考案したアルゴリズムを使うと、効率的にシャッフルできるため、コンピューターでも広くこの方法が利用されるようになりました。既に紹介したrandクレートでもこのアルゴリズムが採用されています。

「Fisher–Yatesシャッフル」では、次の手順でシャッフルを行います。

- (1) 要素Nを持つ配列で、変数iを(N-1)から1まで減らしながら以下を実行
- (2) 0以上i以下の乱数をlに代入
- (3) 配列[k]と配列[i]の値を交換

この手法を図にすると次のようになるでしょう。変数iは後ろから順に1ずつ減らしていきます。その際、変数kをランダムに選びます。そして、配列[k]と配列[i]の値を交換します。

• Fisher–Yatesシャッフルの仕組み