1

对于我的 minhashing 算法的实现，我需要对整数进行许多随机排列，这将通过使用随机散列函数（尽可能多）来模拟。目前我使用以下形式的哈希函数：

h(x) = (a*x + b) % c

其中a和b是随机生成的数字，c是大于b最大值的素数。无论如何，代码运行得太慢了，不可能在合理的运行时间内使用超过 15 个这样的哈希函数。任何人都可以推荐其他在 Python 中对整数使用随机散列函数的方法吗？在其他帖子中，我遇到了使用按位混洗和XOR操作的建议，但我并不完全理解应该如何实现这样的东西（我对 Python 比较陌生）。

4

1 回答 1

0

借用我对类似问题的回答，并快速查看 Python 文档以尝试猜测有效的语法......

您发布的代码是可以的，但它可能会以比最佳精度更长的精度计算，并且它涉及一个也使事情变慢的除法。

为了使其更快，您可以将其固定c为 2 的幂，并且可以使用二进制&(and) 而不是模数，这样可以：

h(x) = (a * x + b) & ((1 << 32) - 1)

这与以下内容相同：

h(x) = (a * x + b) & (4294967296 - 1)

这与以下内容相同：

h(x) = (a * x + b) % 4294967296

并且您必须确保它a是一个奇数（这就是使它与cwhenc是 2 的幂次共质所需的全部内容）。此示例将输出范围限制为 32 位整数。您可以根据需要更改它。我不知道 Python 的限制是什么。

如果您想要更多的参数化，或者您发现结果不够“随机”（它会很快通过统计测试，但这通常没关系），那么您可以添加更多操作；但是您不能添加更多这些操作，因为加法和乘法链总是会简化为一对加法和乘法，因此额外的操作不会解决任何问题。

你可以做的是使用位移和异或来打破线性；像这样：

def h(x):
  x = x ^ (x >> 16)
  x = (a * x + b) & ((1 << 32) - 1)
  x = x ^ (x >> 16)
  x = (c * x + d) & ((1 << 32) - 1)
  x = x ^ (x >> 16)
  return x

如果你愿意，你可以试验它的变化。如果您将bandd设置为零并将中间更改为16，13那么您将获得MurmurHash3a终结器构造，只要您选择好并且c（遗憾的是它们不能只是随机的），它对于大多数用途来说已经足够接近理想了。

于 2016-10-18T20:21:59.840 回答