文章/答案/技术大牛

发布

社区首页 >问答首页 >从k个独立散列族生成散列函数的最快方法(<=5)

问从k个独立散列族生成散列函数的最快方法(<=5)
EN

Stack Overflow用户

提问于 2017-09-27 14:45:51

回答 2查看 1.2K关注 0票数 22

当k很小时，我需要k个独立散列族的散列函数h[n]:[t] (<= 5)。或者，我需要从[1-t]中随机选择n个哈希值，以便它们是K-独立。我正在尝试实现一些我需要的随机算法。我用range [1-t]生成n个随机数

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

但对于我的应用程序来说，这似乎太慢了。由于我不需要完全的随机性，但只有4个明智的独立性，我想知道我是否可以加快这一点。我知道我可以用多项式散列来获得k个独立，但这是最好的吗？如果是，是否有任何快速实现，我可以插入吗？如果不是，有什么可供选择的方法(库，可能在Python中)？

我看过这个线程获取k向独立的散列函数，但我不知道这个被接受的答案意味着什么：“如果您需要k个不同的散列，只需重复使用相同的算法k次，有k个不同的种子”。

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

random

hash

murmurhash

python

回答 2

Stack Overflow用户

发布于 2018-08-16 15:33:26

您可以尝试使用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)

输出：

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比的randint()实现速度快1135倍。

票数 1

Stack Overflow用户

发布于 2021-06-11 15:45:48

求实k向独立散列函数的最快方法是求有限域上的k次多项式。最快的方法可能是使用携带较少的乘法。例如，代码(参见https://github.com/speedyhash/shorthash/blob/master/include/clhash.h#L248 )

一般来说，您应该看到维基百科文章中的技巧部分：hashing#Techniques

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/46450864

复制

相似问题

问从k个独立散列族生成散列函数的最快方法(<=5)
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问从k个独立散列族生成散列函数的最快方法(<=5)EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问从k个独立散列族生成散列函数的最快方法(<=5)
EN