确定性位混淆过滤坐标。

Question

我正在尝试编写一个函数，给定一个(x,y)坐标对和程序的随机种子，将以伪随机的方式为某些预设百分比的所有这样的坐标对返回true。 x或y没有任何限制，除了数据类型的限制，它是一个32位有符号整数。

我的当前方法是将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)坐标开始，也不是要获取一个评估为true的固定大小的坐标集。该函数应该能够针对任意的x、y和种子(seed)计算出真值，百分比控制“真”坐标的平均频率。

- aosdict

---

确认一下 - 你正在寻找一个确定性算法，它可以在给定一些种子的情况下选择固定百分比的点并返回它们，但是具有良好的分布特性？ - templatetypedef

不完全是这样。它不需要提前评估点并返回一组点。它只需要能够决定一个坐标点的真值，并且可以重复地这样做。这就是我所说的确定性 - 对于给定的相同（x，y，seed），它必须始终返回相同的真值。 - aosdict

Answer 1

解决方案是使用一个好的哈希算法。你可以对hash(seed || x || y)的值进行范围检查。

当然，使用百分比p逐个选择点并不能保证最终得到的样本大小恰好为p * N。（这是样本的期望大小，但任何给定的样本都会稍微偏离。）如果你想从包含N个对象的集合中精确地获取大小为k的样本，则可以使用以下简单算法：

• 逐个检查样本中的元素，直到k达到0。

• 当检查元素 i 时，如果其哈希值映射到范围[0，N-i)内小于k，则将其添加到样本中。如果将该元素添加到样本中，则将k减1。

无法使算术完美（因为没有办法将2i个不同的哈希值完美分成n个桶，除非n是2的幂），因此总会存在微小偏差。（浮点运算也无济于事；可能的浮点值数量也是固定的，并且受到相同偏差的影响。）

如果使用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/ ：Farmhash 是一个快速哈希函数，适用于 64 位数据。它被设计为在哈希表中最大限度地提高性能。
• Murmurhash https://code.google.com/p/smhasher/ ：Murmurhash 是一个非加密哈希函数，用于将任意长度的输入数据映射到较短的固定长度的哈希值。
• xxhash https://code.google.com/p/xxhash/ ：xxhash 是一种极快的哈希算法，可用于散列消息、键或数据。
• siphash https://github.com/majek/csiphash/ ：Siphash 是一种快速、安全且强密码保护的哈希函数，适用于散列密钥和其他小块数据。

... 还有很多其他的哈希函数。

---

注释

1. 如果你在大西洋的那一边，就是数十亿。

- rici

---

一旦您拥有哈希值，那么如何将其转换为固定大小的随机点样本呢？ - templatetypedef

我认为这里的问题在于样本空间是所有32位整数对...这太大了，实际上无法在内存中保存。您需要一个隐式公式来查看这些点是否在样本中。 - templatetypedef

@templatetypedef：我对问题的理解不是这样的。也许我错了。但是，似乎OP有一个实际的x,y点集，应该从中取样。如果您只想从整个宇宙中获取随机点集，可以使用一个良好的PRNG种子值，并以成对方式提取32位整数。 - rici

@templatetypedef：否则，你怎么理解“百分比”呢？即使你有像谷歌一样的基础设施，要求所有2^64个可能的x，y对的0.5％也是不合理的。 - rici

Answer 2

我更喜欢通过组合线性同余生成器来输入种子、x和y。

这通常比哈希快得多，它是专门为此目的设计的：在特定范围内输出均匀的伪随机数。

使用Wichmann-Hill推荐的系数（也用于一些Microsoft Excel版本中），我们可以做到：

si = 171 * s % 30269;
xi = 172 * x % 30307;
yi = 170 * y % 30323;

r_combined = fmod(si/30269. + xi/30307. + yi/30323., 1.);

return r_combined < percentage;

s 是第一次调用时的种子，而每次后续调用则使用前一个 si。(感谢 rici 的评论提供了这个信息)

- Imran

---

除非在每次调用该函数时更改种子，否则它将对选择点(x, y)的概率产生非常严重的偏差。我认为您可能想使用PRNG序列而不是固定的种子值。 - rici

因此，这需要至少三个乘法和六个除法，假设您可以优化fmod（x，1.0）以避免除法。我相信我指出的几个哈希函数如果针对一个对齐的128位输入进行专门优化，可以击败它。 - rici

这很有趣。我需要阅读更多关于一些简单哈希函数的内容。我会假设它们没有通过所有随机性测试，因为LCG被认为是最快的方法，但我一定要再调查一下。 - Imran

然而，由于这种方法使用了LCG，即使它在某个x-y-seed元组上评估为true，例如，它在使用相同值进行后续调用时可能不一定评估为true。如果（370，12，58000）第一次返回true，则第二次可能不会返回true，因为si已更改。如果我对此有误，请纠正我。 - aosdict

你是正确的。如果你想要在相同的x、y和种子下每次得到相同的结果，那么就不要更新种子，只需使用相同的种子即可。 - Imran