确定性比特加扰以过滤坐标

我正在尝试编写一个函数,给定一个(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.(这是样本的预期大小,但任何给定的样本都会稍微偏离.)如果你想要从N个对象的宇宙中获取大小精确为k的样本,可以使用以下简单算法:

>一次检查一个样本中的元素,直到k达到0.
>检查元素i时,如果其映射到范围[0,N-i)的哈希值小于k,则将其添加到样本中.如果将元素添加到样本中,则递减k.

没有办法让算术绝对完美(因为除非n是2的幂,否则无法将2i个不同的散列值完美地划分为n个桶),因此总会存在微小的偏差. (浮点运算没有帮助;可能的浮点值的数量也是固定的,并且受到相同的偏差.)

如果你进行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位输入来最大化速度.然后,您可以展开哈希循环以完成两个块.

为了您的目的,我不会猜测最好的哈希函数.您可能想要查看一个或多个这些开源散列函数:

> Farmhash https://code.google.com/p/farmhash/
> Murmurhash https://code.google.com/p/smhasher/
> xxhash https://code.google.com/p/xxhash/
> siphash https://github.com/majek/csiphash/

… 还有很多.

笔记

>如果你在大西洋那边,那就是几十亿.

相关文章
相关标签/搜索