先頭へ戻る

ランダムシャッフル 解答ページ | Programming Place Plus アルゴリズムとデータ構造編【その他のアルゴリズム】 第2章

Programming Place Plus トップページ -- アルゴリズムとデータ構造編

先頭へ戻る

問題①

問題① 良くない方法と、Fisher-Yates shuffle とを使って、実際に結果の偏りがどの程度出るかを確認するプログラムを作成してください。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

typedef void (*shuffle_func)(int*, size_t);

enum {
    ARRAY_SIZE = 3,
};
static const int INIT_ARRAY_DATA[ARRAY_SIZE] = {0, 1, 2};
static const int ARRAY_PATTURN[][ARRAY_SIZE] = {
    {0, 1, 2},
    {0, 2, 1},
    {1, 0, 2},
    {1, 2, 0},
    {2, 0, 1},
    {2, 1, 0},
};

static void test_run(shuffle_func func);
static void random_shuffle(int* array, size_t size);
static void random_shuffle_ex(int* array, size_t size);
static int search_patturn(const int* array, size_t size);

int main(void)
{
    srand( (unsigned int)time(NULL) );

    test_run( random_shuffle );
    test_run( random_shuffle_ex );

    return 0;
}

/*
    指定したシャッフル関数でテスト実行開始
*/
void test_run(shuffle_func func)
{
    static const int RUN_COUNT = 10000;  // 実行回数

    int array[ARRAY_SIZE];
    int patturn_count[SIZE_OF_ARRAY(ARRAY_PATTURN)] = {0};
    int patturn_index;

    for( int i = 0; i < RUN_COUNT; ++i){
        memcpy( array, INIT_ARRAY_DATA, sizeof(INIT_ARRAY_DATA) );
        func( array, SIZE_OF_ARRAY(array) );
        patturn_index = search_patturn( array, SIZE_OF_ARRAY(array) );
        patturn_count[patturn_index]++;
    }

    for( size_t i = 0; i < SIZE_OF_ARRAY(patturn_count); ++i){
        printf("%zu: %d  (%.1f%%)\n",
            i,
            patturn_count[i],
            (double)patturn_count[i] * 100.0 / RUN_COUNT
        );
    }
    printf("\n\n");
}

/*
    配列の要素をランダムシャッフルする
*/
void random_shuffle(int* array, size_t size)
{
    for( size_t i = 0; i < size; ++i ){
        size_t a = rand() % size;
        size_t b = rand() % size;
        SWAP( int, array[a], array[b] );
    }
}

/*
    配列の要素をランダムシャッフルする
*/
void random_shuffle_ex(int* array, size_t size)
{
    for( size_t i = size; i > 1; --i ){
        size_t a = i - 1;
        size_t b = rand() % i;
        SWAP( int, array[a], array[b] );
    }
}

/*
    並び順のパターンを探す
*/
int search_patturn(const int* array, size_t size)
{
    for( size_t i = 0; i < SIZE_OF_ARRAY(ARRAY_PATTURN); ++i ){
        if(memcmp(array, ARRAY_PATTURN[i], sizeof(int)*ARRAY_SIZE) == 0){
            return (int)i;
        }
    }

    assert(!"該当するパターンが見つからない");
    return -1;
}

このプログラムを何度か実行すると、次のような結果を得られました。

0: 1798  (18.0%)
1: 1761  (17.6%)
2: 1810  (18.1%)
3: 1472  (14.7%)
4: 1436  (14.4%)
5: 1723  (17.2%)


0: 1683  (16.8%)
1: 1656  (16.6%)
2: 1656  (16.6%)
3: 1706  (17.1%)
4: 1643  (16.4%)
5: 1656  (16.6%)
0: 1846  (18.5%)
1: 1792  (17.9%)
2: 1721  (17.2%)
3: 1455  (14.6%)
4: 1490  (14.9%)
5: 1696  (17.0%)


0: 1618  (16.2%)
1: 1621  (16.2%)
2: 1701  (17.0%)
3: 1679  (16.8%)
4: 1680  (16.8%)
5: 1701  (17.0%)
0: 1898  (19.0%)
1: 1712  (17.1%)
2: 1739  (17.4%)
3: 1503  (15.0%)
4: 1422  (14.2%)
5: 1726  (17.3%)


0: 1645  (16.4%)
1: 1691  (16.9%)
2: 1738  (17.4%)
3: 1697  (17.0%)
4: 1566  (15.7%)
5: 1663  (16.6%)

それぞれ、最初の 6個が、良くない方法でのランダムシャッフルの結果で、後ろの 6個が Fisher-Yates shuffle での結果です。それぞれ、計10万回のランダムシャッフルを行い、その結果のパターン(全部で6パターン)のどれになったかを出力しています。( )内には、全体の何パーセントの割合で、そのパターンが登場しているかを出力してあります。

良くない方法では、14.2% ~ 19.0% の範囲に収まっています。一方、Fisher-Yates shuffle では、15.7% ~ 17.4% の範囲にあります。この結果を見る限り、Fisher-Yates shuffle の方が狭い範囲に収まっているので、偏りが少ないようです。

本編での解説の理屈どおりなら、Fisher-Yates shuffle はもっと優秀な結果を示すはずですが、rand関数によって生成される疑似乱数の質が悪いため、選び出される位置に偏りが生まれてしまい、多少悪い結果になっていますが、良くない方法の方と条件は同じですから、やはり Fisher-Yates shuffle の方が優秀であると言えるでしょう。


参考リンク


------------------------------------------------------------------------

更新履歴

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2012/5/19 新規作成。



第2章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー