2

このコードは、A、C、T、Gのみを使用してランダムな16文字の文字列を生成します。次に、このシーケンスがハッシュ（unordered_map）にあるかどうかを確認し、含まれていない場合は、それを挿入してダミーのプレースホルダーを指します。

現在の形式では、ACTGに4 ^ 16の文字列があるにもかかわらず、「foriループ」が20000回の反復を必要とする場合、datact=16384でハングします。

しかし..文字列の長さが8、9、10、11 ..から15、または17、18に変更された場合、正しく20000に繰り返されます。unordered_mapが新しいシーケンスのハッシュを拒否するのはなぜですか。ただし、それらのシーケンスが16の場合のみです。文字は長いですか？

#include <string>
#include <vector>
#include <unordered_map>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>

using namespace std;


int main(int argc, char* argv[])
{
    string funnelstring;

    srand ( time(NULL) );

    const int buffersize=10000;
    int currentsize=buffersize;

    int datact=0;

    vector <unsigned int> ctarr(buffersize);

    vector <char> nuc(4);
    nuc[0]='A';
    nuc[1]='C';
    nuc[2]='T';
    nuc[3]='G';

    unordered_map <string,unsigned int*> location;

    unsigned int sct;
    sct=1;

    for (int i=0;i<20000; i++)
    {
        do
        {
            funnelstring="";
            for (int i=0; i<16; i++)
            {   // generate random 16 nucleotide sequence
                funnelstring+=nuc[(rand() % 4)];
            }
        } while (location.find(funnelstring) != location.end()); //asks whether this key has been assigned

        ctarr[datact]=sct;
        location[funnelstring]=&ctarr[datact]; //assign current key to point to data count
        datact++;
        cout << datact << endl;

        if (datact>=currentsize)
        {
            ctarr.resize(currentsize+buffersize);
            currentsize+=buffersize;
        }
    }

    return 0;
}
4

2 に答える 2

2

@ us2012が言ったように、問題はPRNGと、下位ビットのランダム性の低さです。関連する見積もりは次のとおりです。

In Numerical Recipes in C：The Art of Scientific Computing（William H. Press、Brian P. Flannery、Saul A. Teukolsky、William T. Vetterling; New York：Cambridge University Press、1992（2nd ed。、p。277）） 、次のコメントが作成されます。

「1から10までのランダムな整数を生成する場合は、次のように、常に上位ビットを使用して生成する必要があります。

j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));

それに似たものは決してありません

j = 1 + (rand() % 10);

（下位ビットを使用します）。」

また、他の人が指摘しているように、より優れた、より最新のRNGを使用することもできます。

于 2013-02-06T05:52:38.927 に答える
1

原因は、乱数ジェネレーターである可能性が非常に高いです。つまり、PRNGからの乱数のシーケンスが周期的になりすぎた（mod 4）のが速すぎます（ほとんどの乱数ジェネレーターは実際に疑似乱数を生成するため、PRNGという名前になります）。したがって、do...while提供された乱数で新しいヌクレオチド配列を見つけることができないため、ループが終了することはありません。

私が考えることができる2つの修正：

  • 乱数をmod 4生成する代わりに、それらを生成しmod 4^lengthてビットペアを抽出し、00 -> A, 01 -> G, ...

  • のようなより良いPRNGを使用しますstd::mersenne_twister_engine。

（免責事項：私は乱数の専門家ではありません。ミッションクリティカルなシステム、暗号化要件などについては、このアドバイスに頼らないでください。）

于 2013-02-06T05:38:55.533 に答える