Fastest way to generate hash function from k wise independent hash family for small k(<=5)

user_1131274 0
Viewed 1135

I need a hash function h[n]:[t] from k wise independent hash family when k is small (<= 5). Or I need n hash values chosen uniformly randomly from [1-t] such that they are k wise independent. I am trying to implement some randomized algorithms where I needed this. I was generating n random number from range [1-t] using

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

but this seems to be too slow for my application. Since I don't need full randomness but only 4 wise independence I was wondering if I could speed this up. I know I can use polynomial hash family to get k wise independence but is this the best? If yes, is there any fast implementation of this which I can plug in? If no, what are the alternative ways (libraries, possibly in Python)?

I have looked at this thread Obtaining a k-wise independent hash function but I am not sure what the accepted answer means by this: "if you need k different hash, just re-use the same algorithm k times, with k different seeds".

Any suggestions are greatly appreciated. Thanks.

murmurhash hash random python
2 Answers

You can try to use numba's jit with 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)

Output:

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)

Thus, numpy + numba is 1135 times faster than scipy's implementation of randint().

user_99470100
user_2055210
Related