Даже если RAND_MAX больше dictionary.size(), использование оператора % для выбора индекса приводит к неравномерному распределению.Модуль заставит ранние слова выбираться чаще, чем более поздние (если RAND_MAX + 1 не является целым кратным dictionary.size()).
Рассмотрим простой пример: предположим, что в вашем словаре 10 слов, иRAND_MAX равно 14. Когда rand() возвращает значение от 0 до 9, соответствующее слово выбирается напрямую.Но когда rand() это 10-14, тогда будет выбрано одно из первых пяти слов.Таким образом, первые пять слов имеют в два раза больше шансов быть выбранными, чем последние пять слов.
Лучший способ отобразить [0 .. RAND_MAX] в [0 .. dictionary.size()) - использовать деление:
assert(RAND_MAX + 1 >= dictionary.size());
randNumb = rand() * dictionary.size() / (RAND_MAX + 1);
Но вы должны быть осторожны с целочисленным переполнением.Если RAND_MAX * dictionary.size() больше, чем вы можете представить в целом числе, вам нужно будет использовать больший тип данных.Некоторые системы имеют такую функцию, как MulDiv именно для этой цели.Если у вас нет что-то вроде MulDiv, вы можете преобразовать его в тип с плавающей запятой и затем усечь результат обратно в целое число:
double temp = static_cast<double>(rand()) * dictionary.size() / (RAND_MAX + 1);
randNumb = static_cast<int>(temp);
Это все еще несовершенныйраспределением, но «горячие» слова теперь будут равномерно распределяться по словарю, а не сгущаться в начале.
Чем ближе RAND_MAX + 1 к целому кратному dictionary.size(), тем лучше для васбыть.И если вы не можете быть уверены, что он близок к целочисленному кратному, тогда вы хотите, чтобы RAND_MAX был как можно больше по отношению к dictionary.size().
, так как вы не имеете большого контроля над RAND_MAXВы могли бы рассмотреть возможность настройки dictionary.size().Например, если вам нужны только шестибуквенные слова, то почему бы не убрать все остальные из словаря?
std::vector<std::string> six_letter_words;
std::copy_if(dictionary.begin(), dictionary.end(),
std::back_inserter(six_letter_words),
[](const std::string &word){ return word.size() == 6; });
С уменьшенным набором мы можем использовать более общий алгоритм для выбора слов:
typedef std::vector<std::string> WordList;
// Returns true with the given probability, which should be 0.0 to 1.0.
bool Probably(double probability) {
return (static_cast<double>(std::rand()) / RAND_MAX) < probability;
}
// Selects n words from the dictionary using a normal distribution and
// copies them to target.
template <typename OutputIt>
OutputIt Select(int n, const WordList &dictionary, OutputIt target) {
double count = static_cast<double>(n);
for (std::size_t i = 0; count > 0.0 && i < dictionary.size(); ++i) {
if (Probably(count / (dictionary.size() - i))) {
*target++ = dictionary[i];
count -= 1.0;
}
}
return target;
}
Идея состоит в том, чтобы пройтись по каждому слову в словаре и выбрать его с вероятностью числа слов, которое нужно выбрать, деленного на количество слов, из которых осталось выбрать.Это хорошо работает, даже если RAND_MAX относительно мало.В целом, однако, это гораздо больше вычислений, чем попытка случайного выбора индексов.Также обратите внимание, что этот метод никогда не выберет одно и то же слово более одного раза, в отличие от метода отображения индекса.
Вы вызываете Select следующим образом:
// Select six words from six_letter_words using a normal distribution.
WordList selected;
Select(6, six_letter_words, std::back_inserter(selected));
Также обратите внимание, что большинство реализацийrand() довольно просты и могут не дать хорошего нормального распределения для начала.