解决方案是使用一个好的哈希算法。你可以对hash(seed || x || y)
的值进行范围检查。
当然,使用百分比p
逐个选择点并不能保证最终得到的样本大小恰好为p * N
。(这是样本的期望大小,但任何给定的样本都会稍微偏离。)如果你想从包含N
个对象的集合中精确地获取大小为k
的样本,则可以使用以下简单算法:
无法使算术完美(因为没有办法将2i
个不同的哈希值完美分成n
个桶,除非n
是2的幂),因此总会存在微小偏差。(浮点运算也无济于事;可能的浮点值数量也是固定的,并且受到相同偏差的影响。)
如果使用64位算术,则偏差将非常微小,但除非您的环境提供128位乘法,否则算术将更加复杂。因此,您可以满足于32位计算,其中一千万分之一的偏差[注1]并不重要。在这里,您可以利用您哈希中的任何32位应该与其他任何32位一样不偏的事实(假设您的哈希算法很好,详见下文)。因此,以下检查应该能够正常工作:
bool select(uint32_t n, uint32_t k, uint64_t hash) {
return ((hash & (uint32_t)(-1)) * (uint64_t)n) >> 32 < k;
}
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位输入来最大化速度。然后,您可以展开哈希循环以执行恰好两个块。
我无法猜测最适合您目的的哈希函数。您可能想查看这些开源哈希函数之一或多个:
... 还有很多其他的哈希函数。
注释
- 如果你在大西洋的那一边,就是数十亿。