0

編集：明確にするために、問題は2番目のアルゴリズムにあります。

52 枚のカード デッキからカードをサンプリングする C++ コードが少しありますが、これは問題なく動作します。

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);
}

既知の分布に従ってホールカードをサンプリングするコードを実装しています (2d テーブルとして保存されます)。このコードは次のようになります。

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() は、基本的に単なる配列ルックアップです。

4

6 に答える 6

1

カードが取得されたかどうかを確認するすべてのループをビット マスクに置き換えることで、速度を上げることができます。たとえば、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;
    }
}
//...
于 2010-05-10T11:33:58.577 に答える
1

あなたのリジェクト衝突は、O (n) アルゴリズムを (私が思うに) O (n^2) 操作に変えています。

デッキからカードを選択するには、シャッフルとポップの 2 つの方法があります。または、セットの要素が一意になるまでセットを選択します。あなたはかなりの量のバックトラックを必要とする後者を行っています。

コードの詳細は見ていません。簡単にスキャンしただけです。

于 2010-05-10T09:27:27.013 に答える
0

加重セットからの選択に関する2番目の質問に答えるには、時間の複雑さが少なくなるアルゴリズムの置き換えもあります。これは、事前に計算されたものを再計算する必要がないという原則に基づいています。

通常の選択では、ビンのピッキングをO（1）操作にする整数個のビンがあります。関数weighted_randiには実際の長さのビンがあるため、現在のバージョンでの選択はO（n）時間で動作します。重みのベクトルが一定であるとは言わない（ただし、暗示する）ので、w一定であると仮定します。

ビンの幅自体weighted_randiには関心がなく、変数を使用するたびに再計算するエッジの位置に関心がありますthreshold。の定数wがtrueの場合、エッジのリスト（つまり、thresholdfor allの値*w）を事前に計算することがO（n）ステップであり、1回だけ実行する必要があります。結果を（自然に）順序付けられたリストに入れると、将来のすべての呼び出しでのバイナリ検索により、必要なスペースがわずかで増加するOsizeof w / sizeof w[0] （log n）時間計算量が得られます。

于 2010-05-10T15:19:37.037 に答える
0

問題が何であるかを説明するのではなく、問題を見つける方法を提案させてください。1) IDE で 1 ステップ実行するか、2)ランダムに停止して動作を確認します。

とはいえ、あなたが行っているように、拒否によるサンプリングは、ほとんどのサンプルを拒否している場合、不当に長い時間がかかる可能性があります.

于 2010-05-10T12:18:42.057 に答える
0

内部の「try_again」for ループは、try_again を true に設定するとすぐに停止する必要があります。再試行する必要があることがわかった後で、さらに作業を行う意味はありません。

for (n = 0; n < i && !try_again; n++) {
    try_again = (temp[n] == temp[i]) || (temp[n] == temp[i+1]);
}
于 2010-05-10T15:14:46.097 に答える
0

私の推測では、再試行ループ内の memcpy(1326*sizeof(double)) です。変わらないようなので、毎回コピーすればいいのでは？

于 2010-05-10T09:38:29.063 に答える