2

此代码仅使用 A、C、T、G 生成一个随机的 16 个字符的字符串。然后它检查这个序列是否在散列（unordered_map）中，如果没有，则插入它并指向一个虚拟占位符。

在其当前形式中，当“for i 循环”需要 20000 次迭代时，它会挂在 datact=16384 处，尽管 ACTG 有 4^16 个字符串。

但是.. 如果字符串长度更改为 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，以及低位随机性差。这是一个相关的报价：

在 C 中的数值食谱：科学计算的艺术（William H. Press、Brian P. Flannery、Saul A. Teukolsky、William T. Vetterling；纽约：剑桥大学出版社，1992 年（第 2 版，第 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循环永远不会退出，因为它无法使用提供的随机数找到新的核苷酸序列。

我能想到的两个修复：

  • 不是生成随机数mod 4，而是生成它们mod 4^length并提取位对，00 -> A, 01 -> G, ...

  • 使用更好的 PRNG，例如std::mersenne_twister_engine.

（免责声明：我不是随机数方面的专家。对于关键任务系统、加密要求等，请不要依赖此建议。）

于 2013-02-06T05:38:55.533 回答