aos*_*ict 8 c random algorithm
我正在尝试编写一个函数,给定一个(x,y)坐标对和程序的随机种子,对于所有这些对的某些预设百分比,它将伪随机地返回true.除了数据类型的限制之外,x或y没有限制,数据类型是32位signed int.
我目前的方法是将x,y和种子的位加在一起,然后将得到的数字与百分比进行比较:
float percentage = 0.005;
...
unsigned int n = (x ^ y) ^ seed;
return (((float) n / UINT_MAX) < percentage);
但是,似乎这种方法对某些x和y值有偏差.例如,如果它为(0,a)返回true,则它也将为(a,0)返回true.
我知道这个实现只是将它们放在一起是天真的.有没有更好的位加扰算法在这里使用,不会有偏见？
编辑:为了澄清,我不是从一组(x,y)坐标开始,也不是我试图得到一组固定大小的坐标,评估为真.该函数应该能够评估任意x,y和种子的真值,其中百分比控制"真"坐标的平均频率.
简单的解决方案是使用良好的哈希算法。您可以对 的值进行范围检查hash(seed || x || y)。
当然，用百分比单独选择点p并不能保证您最终得到的样本大小恰好为p * N。k（这是样本的预期大小，但任何给定的样本都会有点偏差。）如果您想从大量对象中获取精确大小的样本N，可以使用以下简单算法：
一次检查一个样品中的元素，直到k达到 0。
检查元素 时，如果映射到范围的哈希值小于 ，i则将其添加到样本中。如果将元素添加到样本中，则递减。[0, N-i)kk
没有办法让算术绝对完美（因为没有办法将不同的哈希值完美地划分到桶中，除非是 2 的幂），所以总会有微小的偏差。（浮点运算没有帮助；可能的浮点值的数量也是固定的，并且遭受相同的偏差。）2inn
如果您进行 64 位算术，偏差将非常小，但算术会更复杂，除非您的环境提供 128 位乘法。因此，您可能会对 32 位计算感到满意，其中几亿分之一的偏差[注 1] 并不重要。在这里，您可以利用这样一个事实：假设您的散列算法很好（见下文），散列中的任何 32 位都应该与任何其他 32 位一样无偏。因此以下检查应该可以正常工作：
// I need k elements from a remaining universe of n, and I have a 64-bit hash.
// Return true if I should select this element
bool select(uint32_t n, uint32_t k, uint64_t hash) {
return ((hash & (uint32_t)(-1)) * (uint64_t)n) >> 32 < k;
}
// Untested example sampler
// select exactly k elements from U, using a seed value
std::vector<E> sample(const std::vector<E>& U, uint64_t seed, uint32_t k) {
std::vector<E> retval;
uint32_t n = U.size();
for (uint32_t n = U.size(); k && n;) {
E& elt = U[--n];
if (select(n, k, hash_function(seed, elt))) {
retval.push_back(elt);
--k;
}
}
return retval;
}
假设您需要经常这样做，您将需要使用快速哈希算法；由于您实际上并不是在安全的环境中工作，因此您无需担心算法在加密方面是否安全。
许多高速哈希算法在 64 位单元上工作，因此您可以通过构造由 64 位种子和两个 32 位坐标组成的 128 位输入来最大限度地提高速度。然后，您可以展开哈希循环以执行两个块。
我不会冒险猜测最适合您目的的哈希函数。您可能想查看以下一个或多个开源哈希函数：
... 还有很多。