22

当h[n]:[t]k 很小时<= 5（或者我需要从其中均匀随机选择 n 个哈希值[1-t]，以便它们是k 明智独立的。我正在尝试在需要的地方实现一些随机算法。[1-t]我正在使用从范围内生成 n 个随机数

scipy.stats.randint(0,self._t).rvs(self._n)

但这对我的应用程序来说似乎太慢了。因为我不需要完全随机性，但只需要 4 次独立，我想知道我是否可以加快速度。我知道我可以使用多项式哈希族来获得 k 明智的独立性，但这是最好的吗？如果是，是否有任何我可以插入的快速实现？如果不是，还有哪些替代方法（库，可能在 Python 中）？

我看过这个线程获取一个 k 方向独立散列函数，但我不确定接受的答案是什么意思：“如果你需要 k 个不同的散列，只需重复使用相同的算法 k 次，使用 k 个不同的种子” .

非常感谢任何建议。谢谢。

4

2 回答 2

1

您可以尝试将 numba'sjit与 numpy's一起使用random.randint()：

import scipy.stats
import numpy as np
from numba import jit

def randint_scipy(n):
    return scipy.stats.randint(0, 10000).rvs(n)

def randint_numpy(n):
    return np.random.randint(0, 10000, n)

@jit
def randint_numpy_jit(n):
    return np.random.randint(0, 10000, n)

%timeit randint_scipy(5)
%timeit randint_numpy(5)
%timeit randint_numpy_jit(5)

输出：

1.09 ms ± 10.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
4.63 µs ± 149 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
960 ns ± 50.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

因此，numpy + numba比 scipy 的randint().

于 2018-08-16T15:33:26.030 回答
0

获得真正的 k 向独立散列函数的最快方法是在有限域上评估 k 次多项式。最快的方法可能是使用少进位乘法。例如，代码见https://github.com/speedyhash/shorthash/blob/master/include/clhash.h#L248

一般来说，您应该看到 Wikipedia 文章中的“技术”部分：https ://en.wikipedia.org/wiki/K-independent_hashing#Techniques

于 2021-06-11T15:45:48.377 回答