いくつかのランダムアルゴリズム【+整理】

22206 ワード

淘宝検索技術ブログhttp://www.searchtb.com/2010/12/random-algorithm.html

本文の内容

ランダム選択データ

乱数の計算

まとめ

この文章をよく見ると、ちょっと驚きましたが、ランダムな数がこんなに考えなければならないものがあるとは思いませんでした.
日常の仕事では,ランダムアルゴリズムを用いることがしばしば必要である.たとえば、大量のデータに対して、ランダムにいくつかのデータを選択して分析する必要があります.また、あるスコアを得た後、ランダム性を増加させるためには、そのスコアに基づいて、摂動を追加し、その摂動を特定の確率分布に従わせる必要がある.本文は主にこの2つの方面から出発して、いくつかのアルゴリズムを紹介して、みんなの参考に供します.
仮定すると,ランダム関数float frand()を用い,戻り値は(0,1)上に均一に分布した.ほとんどのプログラム言語ライブラリでは、このような関数が提供されています.C/C++のような他の言語では,間接的な方法で得ることができる.次のようになります.

ランダムにデータを選択
集合

があると仮定し、集合Aからm個の要素を0≦m≦nの確率でどのように選択するか.
古典確率式を計算することにより,各要素が選択される確率はm/nであることが分かった.集合A内の要素が本来ランダムであり,各要素が各位置に現れる確率が等しく,A上で1回だけデータを選択する場合,Aの前のm個の要素を直接返すか,k個の要素ごとに1個取るなどの類似の方法がある.しかし,このようなアルゴリズムは限界が大きく,集合Aに対する要求が高いため,以下に2つの他のアルゴリズムを紹介する.
集合A中の要素が各位置にランダム性を持たず、何らかの方法で並べ替えられていると仮定すると、集合A中の各要素

を遍歴し、一定の確率に基づいて

を選択することができる.

をAから選択する必要がある要素の個数、

を要素

およびその右側の要素の個数、すなわち

とすると、要素

を選択する確率は

となる.この証明は省略する.
前の2つの要素

がそれぞれ選択された確率を簡単に計算します.

は

が選択される確率を表し、対応する

は選択されていないとする.
1)第1の要素が選択される確率は

であり、

である.
2)2番目の要素が選択される確率

上記のアルゴリズムをC++で実現した.

template<class T>

bool getRand(const vector<T> vecData, int m, vector<T>& vecRand)

    int32_t nSize = vecData.size();

    if(nSize < m || m < 0)

        return false;

    vecRand.clear();

    vecRand.reserve(m);

    for(int32_t i = 0, isize = nSize; i < isize ; i++){

            float fRand = frand();

            if(fRand <=(float)(m)/nSize){

                vecRand.push_back(vecData[i]);

                m--;

        nSize --;

    return true;

上記アルゴリズムは、m=4、n=10で100万回選択した場合、位置要素ごとに選択される確率を統計する.
位置
かくりつ
1
0.399912
2
0.400493
3
0.401032
4
0.399447
5
0.399596
6
0.39975
7
0.4
8
0.399221
9
0.400353
10
0.400196
また、他にも多くのアルゴリズムがあり、単独では紹介されません.i番目の数の場合、

からランダムに1つの数を取って

と交換する.
場合によっては、大きなデータファイルからランダムにいくつかのデータを選択するなど、Aから要素の数を直接得ることはできません.メモリが不足している場合、私たちのファイルのデータの個数を知るためには、まずファイル全体を遍歴し、次にファイルを遍歴して上記のアルゴリズムを利用してm個の要素をランダムに選択する必要があります.あるいはhadoopのようなreduce法では,データの反復器しか得られない.コレクションを複数回巡回することはできません.要素をメモリに保存するしかありません.これらの場合,データファイルが大きいとアルゴリズムの速度が大きく影響し,reduceマシンの構成にも依存する.
このとき,一度だけ集合を巡回するアルゴリズムを試みることができる.
1)前のm個の要素を集合A’に入れる.
2)i番目の要素(i>m)について、iをm/iの確率でA’のいずれかの要素を等確率でランダムに置き換える.集合が終わるまで
3)A’を返す.
次に,このアルゴリズムでは,各要素が選択される確率がm/nであることを実証する.
1)m＋1個の要素に遍歴すると、その要素がA’に保存される確率はm／(m＋1)であり、前のm個の要素がA’に保存される確率は1−(m／m＋1＊1／m)＝m／m＋1である.
2)i番目の要素を巡回する場合、前のi−1個の要素がA’に保存される確率をm/(i−1)とする.アルゴリズムによれば、i番目の要素がA’に保存される確率はm/iであり、前のi-1の各要素がA’に残る確率はm/(i-1)*(1-(m/i*1/m)=m/iである.
3)まとめにより,各元素がA’に残る確率がm/nとなる.
hadoopのようなreduce関数では,Javaでこのアルゴリズムを実現する.

public void reduce(TextPair key, Iterator value, OutputCollector collector, int m)

    Text[] vecData = new Text[m];

    int nCurrentIndex = 0;

    while(value.hasNext()){

        Text tValue = value.next();

        if(nCurrentIndex < m){

           vecData[nCurrentIndex] = tValue;

        else if(frand() < (float)m / (nCurrentIndex+1)) {

           int nReplaceIndex = (int)(frand() * m);

           vecData[nReplaceIndex] = tValue;

        nCurrentIndex ++;

 //collect data

…….

上記のアルゴリズムを用いて、m=4、n=10で100万回の選択を経た後、各位置が選択される確率を計算する.
位置
かくりつ
1
0.400387
2
0.400161
3
0.399605
4
0.399716
5
0.400012
6
0.39985
7
0.399821
8
0.400871
9
0.400169
10
0.399408

乱数の計算
検索ソートでは、各検索ドキュメントのスコアにランダムな摂動を追加し、その摂動を確率分布に適合させる必要がある場合があります.
確率密度関数