即使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