即使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()
大多數實現是相當簡單的,不得提供一個良好的正態分佈開始。
請注意,使用模數來限制隨機數的間隔會產生偏差。 – 2012-03-04 13:27:08