从k向独立散列族生成小k（<=5）散列函数的最快方法

Question

当k很小（<= 5）时，我需要一个散列函数h[n]:[t]，来自k-wise独立散列家族。或者我需要从[1-t]中随机选择n个散列值，使它们是k wise independent。我正在尝试在我需要的地方实现一些随机算法。我用的是从[1-t]范围生成n个随机数

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

但这对我的申请来说太慢了。因为我不需要完全的随机性，只有4个明智的独立性，我想知道我是否可以加快这个速度。我知道我可以用多项式散列族来获得k-wise独立性，但这是最好的吗？如果是，有没有什么我可以插入的快速实现？如果没有，有什么替代方法（库，可能是Python）？在

我看过这篇文章Obtaining a k-wise independent hash function，但我不确定接受的答案是什么意思： “如果需要k个不同的散列，只需重复使用相同的算法k次，使用k个不同的种子”。在

如有任何建议，我们将不胜感激。谢谢。在

Answer 1

您可以尝试使用numba的jit和numpy的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)

输出：

^{pr2}$

因此，numpy+numba比scipy的randint()实现快1135倍。在