взвешенная проблема скорости ГСЧ в C ++

Question

Редактировать: чтобы уточнить, проблема в алгоритме second .

У меня есть немного кода на 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);
}

Я реализую код для выборки закрытых карт в соответствии с известным дистрибутивом (хранится в виде 2-мерной таблицы). Мой код для этого выглядит так:

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 раз медленнее. Скорость очень важна для моего приложения.

Есть ли способ повысить скорость моего алгоритма до чего-то более разумного? Я что-то не так делаю в своей реализации?

Спасибо.

edit: меня спросили об этой функции, которую я должен был опубликовать, так как это ключ

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 () - это просто поиск по массиву.

Answer 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;
    }
}
//...

Answer 2

Ваши отклоненные коллизии превращают алгоритм O (n) в (я думаю) O (n ^ 2) операцию.

Есть два способа выбрать карты из колоды: перемешать и поп, или выбрать наборы, пока элементы набора не станут уникальными; Вы делаете последнее, которое требует значительного количества возврата.

Я не смотрел детали кода, только быстрое сканирование.

Answer 3

Ответ на второй вопрос о выборе из взвешенного набора также имеет алгоритмическую замену, которая должна быть менее сложной по времени. Это основано на принципе того, что предварительно вычислено, нет необходимости пересчитывать.

В обычном выборе у вас есть целое число ячеек, что делает выбор ящика операцией O (1). Ваша функция weighted_randi имеет ячейки реальной длины, поэтому выбор в текущей версии выполняется за O (n) времени. Поскольку вы не говорите (но подразумеваете), что вектор весов w является постоянным, я буду считать, что это так.

Вас не интересует ширина ячеек, per se , вас интересуют местоположения их ребер, которые вы пересчитываете при каждом вызове weighted_randi, используя переменную threshold. Если постоянство w истинно, предварительный расчет списка ребер (то есть значение threshold для всех *w) является вашим O (n) шагом, который должен быть только сделано один раз. Если вы поместите результаты в (естественно) упорядоченный список, бинарный поиск по всем будущим вызовам приведет к сложности времени O (log n) с увеличением необходимого пространства только на sizeof w / sizeof w[0].

Answer 4

Ваш внутренний цикл try_again должен прекратиться, как только для try_again будет установлено значение true - больше нет смысла выполнять больше работы, если вы знаете, что вам нужно повторить попытку.

for (n = 0; n < i && !try_again; n++) {
    try_again = (temp[n] == temp[i]) || (temp[n] == temp[i+1]);
}

Answer 5

Вместо того, чтобы рассказать вам, в чем проблема, позвольте мне предложить, как вы можете ее найти. Либо 1) пошаговое выполнение в IDE, либо 2) случайным образом остановка , чтобы посмотреть, что он делает.

При этом выборка путем отклонения, как вы делаете, может занять неоправданно много времени, если вы отклоняете большинство образцов.

Answer 6

Мое предположение: memcpy (1326 * sizeof (double)) внутри цикла повторения. Кажется, он не меняется, поэтому его нужно копировать каждый раз?