分享
为什么问答平台  ›  专栏  ›  技术社区  ›  supert

C++中的加权RNG速度问题 - weighted RNG speed problem in C++

  •  0
  • supert  · 技术社区  · 2 月前

    编辑:为了澄清,问题在于 第二 算法。

    我有一个C++代码,从52张卡片板上采样卡片,效果很好:

    void sample_allcards(int table[5], int holes[], int players) {
        int temp[5 + 2 * players];
        bool try_again;
        int c, n, i;
    
        for (i = 0; i < 5 + 2 * players; i++) {
            try_again = true;
            while (try_again == true) {
                try_again = false;
                c = fast_rand52();
                // reject collisions
                for (n = 0; n < i + 1; n++) {
                    try_again = (temp[n] == c) || try_again;
                }
                temp[i] = c;
            }
        }
        copy_cards(table, temp, 5);
        copy_cards(holes, temp + 5, 2 * players);
    }
    

    我正在实现代码,根据已知的分布(存储为二维表)对孔卡进行采样。我的代码如下:

    void sample_allcards_weighted(double weights[][HOLE_CARDS], int table[5], int holes[], int players) {
        // weights are distribution over hole cards
        int temp[5 + 2 * players];
        int n, i;
    
        // table cards
        for (i = 0; i < 5; i++) {
            bool try_again = true;
            while (try_again == true) {
                try_again = false;
                int c = fast_rand52();
                // reject collisions
                for (n = 0; n < i + 1; n++) {
                    try_again = (temp[n] == c) || try_again;
                }
                temp[i] = c;
            }
        }
    
        for (int player = 0; player < players; player++) {
            // hole cards according to distribution
            i = 5 + 2 * player;
            bool try_again = true;
            while (try_again == true) {
                try_again = false;
                // weighted-sample c1 and c2 at once
                // h is a number < 1325
                int h = weighted_randi(&weights[player][0], HOLE_CARDS);
                // i2h uses h and sets temp[i] to the 2 cards implied by h
                i2h(&temp[i], h);
                // reject collisions
                for (n = 0; n < i; n++) {
                    try_again = (temp[n] == temp[i]) || (temp[n] == temp[i+1]) || try_again;
                }
            }
        }
    
        copy_cards(table, temp, 5);
        copy_cards(holes, temp + 5, 2 * players);
    }
    

    我的问题?加权采样算法的速度慢了10倍。速度对我的应用非常重要。

    有没有办法把我的算法的速度提高到更合理的程度?我在实现过程中是否做了错误的事情?

    谢谢。

    编辑:有人问我关于这个函数的问题,因为它是键,所以我应该发布它。

    inline int weighted_randi(double *w, int num_choices) {
    double r = fast_randd();
    double threshold = 0;
    int n;
    
    for (n = 0; n < num_choices; n++) {
        threshold += *w;
        if (r <= threshold) return n;
        w++;
    }
    // shouldn't get this far
    cerr << n << "\t" << threshold << "\t" << r << endl;
    assert(n < num_choices);
    return -1;
    

    }

    …而i2h()基本上只是一个数组查找。

    6 回复  |  直到 9 年前
        1
  •  1
  •   msw    9 年前

    你的拒绝碰撞变成了 o (n)算法 o (n^2)操作。

    有两种方法可以从牌组中选择牌:随机播放和弹出,或者选择直到牌组的元素唯一为止;您选择的是后者,这需要大量的回溯。

    我没有看代码的细节,只是快速扫描。

        2
  •  1
  •   Necrolis    9 年前

    您可以通过替换所有检查卡是否使用位掩码的循环来获得一些速度,例如对于52张卡的池,我们可以这样防止碰撞:

    DWORD dwMask[2] = {0}; //64 bits
    //...
    int nCard;
    while(true)
    {
        nCard = rand_52();
        if(!(dwMask[nCard >> 5] & 1 << (nCard & 31)))
        {
            dwMask[nCard >> 5] |= 1 << (nCard & 31);
            break;
        }
    }
    //...
    
        3
  •  0
  •   stefaanv    9 年前

    我猜应该是重试循环中的memcpy(1326*sizeof(double))。它似乎没有变化,所以应该每次都复制吗?

        4
  •  0
  •   Mike Dunlavey    1 年前

    与其告诉你问题是什么,不如让我建议你如何找到它。1)在IDE中单步执行,或2) randomly halt it 看看它在做什么。

    也就是说,如果你拒绝大多数样品,那么像你所做的那样,通过拒绝取样可能会花费不合理的长时间。

        5
  •  0
  •   Mark B    9 年前

    循环的内部“再试一次”应该在它设置为“再试一次”时立即停止-在您知道需要再试一次之后再做更多的工作是没有意义的。

    for (n = 0; n < i && !try_again; n++) {
        try_again = (temp[n] == temp[i]) || (temp[n] == temp[i+1]);
    }
    
        6
  •  0
  •   msw    9 年前

    回答关于从加权集中选择的第二个问题也有一个算法替换,它应该不太复杂。这是基于预先计算的原则,不需要重新计算。

    在一个普通的选择中,您有一个整数个箱子,它使选择一个箱子成为 o (1)手术。你的 weighted_randi 函数具有实际长度的容器,因此当前版本中的选择在 o (n)时间。因为你没有说(但确实暗示)重量的矢量 w 是常数,我假设是。

    你对箱子的宽度不感兴趣, 本身 ,您对每次调用时重新计算边缘的位置感兴趣 衡器 使用变量 threshold . 如果 W 是真的,预先计算边缘列表(即 门槛 为了所有 *w 是你的 o (n)只需进行一次的步骤。如果将结果放入(自然)有序的列表中,对所有未来调用进行二进制搜索将生成一个 o (log n)时间复杂性,只需增加 sizeof w / sizeof w[0] .