Вы уверены, что ваш математический и алгоритмический подход к проблеме верен?
Я столкнулся с точно такой же проблемой, когда случайный случай с Фишером-Йейтсом будет узким местом в угловых случаях. Но для меня настоящая проблема - алгоритм грубой силы, который не подходит для всех задач. Следующая история объясняет проблему и оптимизации, которые я до сих пор предлагал.
Карты для 4 игроков
Количество возможных сделок: 96 бит номер. Это создает большую нагрузку для генератора случайных чисел, чтобы избежать статических аномалий при выборе игрового плана из сгенерированного примера набора сделок. Я решил использовать 2xmt19937_64, отобранный из / dev / random, из-за длительного периода и интенсивной рекламы в сети, что это хорошо для научного моделирования.
Простой подход - использовать случайную последовательность Фишера-Йейтса для генерации сделок и фильтрации сделок, которые не соответствуют уже собранной информации. Knuth shuffle занимает ~ 1400 циклов ЦП на сделку, в основном потому, что мне нужно сгенерировать 51 случайное число и поменять 51 раз записи в таблице.
Это не имеет значения для обычных случаев, когда мне нужно будет генерировать только 10000-100000 сделок за 7 минут. Но есть крайние случаи, когда фильтры могут выбирать только очень маленькое подмножество рук, требующее генерации огромного количества сделок.
Использование одного номера для нескольких карт
При профилировании с помощью callgrind (valgrind) я заметил, что основным замедлением был генератор случайных чисел в C ++ (после переключения с std ::iform_int_distribution, который был первым узким местом).
Тогда мне пришла в голову мысль, что я могу использовать одно случайное число для нескольких карт. Идея состоит в том, чтобы сначала использовать наименее значимую информацию из числа, а затем удалить эту информацию.
int number = uniform_rng(0, 52*51*50*49);
int card1 = number % 52;
number /= 52;
int cards2 = number % 51;
number /= 51;
......
Конечно, это только незначительная оптимизация, потому что генерация все еще O (N).
Генерация с использованием битовых перестановок
Следующей идеей было именно то решение, которое было задано здесь, но я все равно получил O (N), но с большей стоимостью, чем первоначальный случайный случай. Но давайте посмотрим на решение и почему оно так неудачно.
Я решил использовать идею Сделка все сделки Джон Кристман
void Deal::generate()
{
// 52:26 split, 52!/(26!)**2 = 495,918,532,948,1041
max = 495918532948104LU;
partner = uniform_rng(eng1, max);
// 2x 26:13 splits, (26!)**2/(13!)**2 = 10,400,600**2
max = 10400600LU*10400600LU;
hands = uniform_rng(eng2, max);
// Create 104 bit presentation of deal (2 bits per card)
select_deal(id, partner, hands);
}
Пока что хорошо и довольно красиво, но реализация select_deal - это PITA.
void select_deal(Id &new_id, uint64_t partner, uint64_t hands)
{
unsigned idx;
unsigned e, n, ns = 26;
e = n = 13;
// Figure out partnership who owns which card
for (idx = CARDS_IN_SUIT*NUM_SUITS; idx > 0; ) {
uint64_t cut = ncr(idx - 1, ns);
if (partner >= cut) {
partner -= cut;
// Figure out if N or S holds the card
ns--;
cut = ncr(ns, n) * 10400600LU;
if (hands > cut) {
hands -= cut;
n--;
} else
new_id[idx%NUM_SUITS] |= 1 << (idx/NUM_SUITS);
} else
new_id[idx%NUM_SUITS + NUM_SUITS] |= 1 << (idx/NUM_SUITS);
idx--;
}
unsigned ew = 26;
// Figure out if E or W holds a card
for (idx = CARDS_IN_SUIT*NUM_SUITS; idx-- > 0; ) {
if (new_id[idx%NUM_SUITS + NUM_SUITS] & (1 << (idx/NUM_SUITS))) {
uint64_t cut = ncr(--ew, e);
if (hands >= cut) {
hands -= cut;
e--;
} else
new_id[idx%NUM_SUITS] |= 1 << (idx/NUM_SUITS);
}
}
}
Теперь, когда у меня было решение перестановки O (N), чтобы доказать, что алгоритм работает, я начал искать отображение O (1) от случайного числа к перестановке битов. Жаль, что похоже, что единственным решением было бы использование огромных таблиц подстановки, которые могли бы уничтожить кэш процессора Это не очень хорошая идея для ИИ, который будет использовать очень большое количество кешей для анализатора с двойным манекеном.
Математическое решение
После всей тяжелой работы, чтобы выяснить, как генерировать случайные битовые перестановки, я решил вернуться к математике. Вполне возможно применить фильтры перед раздачей карт. Это требует разделения сделок на управляемое количество многоуровневых наборов и выбора между наборами на основе их относительной вероятности после фильтрации невозможных наборов.
У меня еще нет готового кода для этого, чтобы проверить, сколько циклов я трачу в общем случае, когда фильтр выбирает основную часть сделки. Но я считаю, что этот подход обеспечивает наиболее стабильную производительность генерации, сохраняя стоимость менее 0,1%.