复杂的哈希冲突

2021-01-02 08:22:44

Warning: Can only detect less than 5000 characters

这个\(b_i \)精确地按照泊松二项式分布:每个关键字\(j \)在所有\(j \)中都以概率\ {c_j ^ {-1} \)独立地落入存储桶\(i \) \(i \在S_j \ pmod {T} \中)。将此分布标记为\(\ mathrm {PB} _i \)(请注意,其参数是完整索引集\(\ left \ {c_j ^ {-1} \,\ middle | \,j,in M_i \ right \} \),其中\(M_i = \ left \ {j \,\ middle | \,i \ in S_j \ pmod {T} \ right \} \))。

没那么快。您将如何实际计算最后的概率\(\ mathbb {P} \ {\ mathrm {PB} _i = 1 \} \)?您需要完全计算\(M_i \)集合。关于统一概率的公式存在一些曲解,而\(\ prod_ {j \ in M_i}(1-c_j ^ {-1})\)消失的概率并不存在。后者是对集合\(M_j \)的可交换,关联约简(一个乘积)。因此,我们可以以流方式迭代\(m \ in [n] \),每个存储桶仅维护一个值(\(T \)个项),这将是运行产品\(\ prod_ {j \ in M_i,j \ le m}(1-c_j ^ {-1})\)。当处理\(S_m \)时,对于所有\(j \ in S_m \),我们只需要将每个项就地乘以\((1-c_m ^ {-1})\)。

上面的方法非常适合\(\ mathbb {P} \ {\ mathrm {PB} _i = 0 \} \),但是\(\ mathbb {P} \ {\ mathrm {PB} _i = 1 \} \ )?为此,我们需要为每个\(i \ in [T] \)计算\(M_i \),需要\(\ sum_i \ left | M_i \ right | \)内存,该内存可以比\(T \)!

该怎么办?一种方法是依赖对\(\ mathrm {PB} _i \)分布的近似值:Wikipedia链接了Le Cam的定理。根据Chen-Stein绑定,甚至存在更好的近似值。

真的,试一下,如何计算每个存储桶\(i \)中只有恒定内存的表达式\(\ mathbb {P} \ {\ mathrm {PB} _i = 1 \} \)?

我们首先通过查看用户狼SO的SO答案来抢先一步。特别地,它引入了一个称为概率生成函数的概念。非负离散随机变量\(X \)的PGF \(G_X \)为\(G_X(t)= \ mathbb {E} t ^ X \),通过检查所得序列,可以满足\(\ mathbb {P} \ {X = k \} = \ frac {G_X ^ {(k)}(0)} {k!} \),类似于MGF,其中\(G_X ^ {(k) } \)是\(G_X \)的\(k \)阶导数。

由于\(\ mathrm {PB} _i \)是独立的Bernoulli随机变量\(\ left | M_i \ right | \)的总和,因此Bernoulli- \(p \)PGF为\(1-p(1- t)\),

这样,SO答案继续:我们要做的就是将上面的多项式\(G _ {\ mathrm {PB} _i}(t)\)扩展到其系数列表中,然后将其\(k \)的导数扩展为0除以\(k!\)就是第\(k \)项的系数,因为当您采用导数时,\(k!\)项会从下降的多项式幂中抵消!

这非常好用,如果我们要寻找\(\ mathbb {P} \ {\ mathrm {PB} _i = k \} \),肯定会节省大量的计算时间,因为天真的计算需要\(\ binom {n} {k} \)项,现在简化为扩展\(n \)系数,而且\(G _ {\ mathrm {PB} _i}(t)\)是项的乘积,我们可以通过保留单个系数列表并通过以流方式处理\(S_m \)更新其项来计算它。

不幸的是,每次更新都需要\(O(\ left | M_i \ right |)\)时间,而且我们并没有真正满足我们的内存需求。我们特别要解决\(\ mathbb {P} \ {\ mathrm {PB} _i = 1 \} \),这对我们有帮助吗?

话虽如此,这是一个很好的起点。我们需要注意的是

当我们流过\(m \ in [n] \)时,我们看到\(S_m \)并可以想象维持有限的差异\(\ prod_ {j \ in M_i,j \ le m}(1-c_j ^ {- 1}(1-t))\ bigg | _ {t = \ pm h} \)表示每个存储区\(i \)的小\(h \)。通过将简单项\((1-c_j ^ {-1}(1-t))\)乘以\(t \ in \ pm中的一个),可以为新\(j_in S_m \)中的每个有限差更新h \),最后计算商。

不幸的是,舍入误差是残酷的:我们事先不知道\(\ left | M_i \ right | \),并且对于不同的\(i \)它可能有所不同,因此我们有不同的最优\(h \ )每个\(i \),并且错误保证是不同的…

因此,我们可以设置\(h = 10 ^ {-100} \),然后使用1个复数逐项逐项递增地计算复杂乘积\(G _ {\ mathrm {PB} _i}(t + ih)\)内存数量,最后除以\(h \),而不必担心数值精度。这是因为\(G _ {\ mathrm {PB} _i}(t)\)本身是乘积,因此是可交换的,关联的约简。当渐近逼近不成立时,这真的很方便。

另一方面,我们也可以从系数列表的角度来解决这个问题:如果我们只关心\(G _ {\ mathrm {PB}}(t)\)的第一个\(k \)项,那么我们需要仅更新部分系数列表!我们在下面介绍两种方法。

#而不是直接指定S_j,我们将重点放在单个泊松二项式项b_i#上,并查看我们的近似程度。将numpy导入为np n = 1000 base = 2 p = np。 logspace(np。log(1 / n)/ np。log(base),np。log(1/2)/ np。log(base),n)打印(' n =',n )print('概率min {:.1g}中位数{:.1g} max {:.1g}'。format(* np。percentile(p,(0,50,100)))) ps = p。 sum()eb =(p * p)。 sum()/ ps打印(' E [X] = {:.2f} Chen-Stein总变化误差界限{:.2f}'。format(ps,eb))打印(&#39 ;估计P {X = 1}')h = 1e-100 print('复杂步骤',np。imag(np。prod(1-p *(1-1j * h )))/ h)#调用Bernoulli PGF(1- p)+ pt#从系数列表[1,0]开始def reduce_pgf1(ab,p):#(a + bt + O(t ^ 2))(c + dt)= ac +(cb + ad)t + O(t ^ 2)a,b = ab c,d = 1-p,p返回a * c,c * b + a * d从functools import缩小打印('系数列表'减少(reduce_pgf1,p,(1,0))[1])cs = ps * np。 exp(-ps)print(' chen-stein',cs,' ---保证是{:.4f}-{:. 4f}'。format(max( cs-eb,0),min(cs + eb,1)))

n = 1000概率最小值1e-10中间值3e-06最大值0.1E [X] = 4.89 Chen-Stein总变化误差范围0.05为P {X = 1}复杂步骤估计0.03408848559058106系数列表0.03408848559058105chen-stein 0.03680206141293496 ---保证为0.0000-0.0873

还记得我们假设\(\ left | S_j \ pmod {T} \ right | = \ left | S_j \ right | \)吗?这确实是为了简化表示法。相反,我们可以将集合\(S_j \)指定为每个可能散列的任意概率列表(因此,在\ {h_1 \ equiv h_2 \ pmod {T} \的情况下)\(j \)第一个键进入第(\((h_1 \ bmod T)\)个存储桶是\(2 c_j ^ {-1} \));这只会更改\(\ mathrm {PB} _i \)的参数。

然后,为了解决原始问题,我们可以尝试各种\(T \),计算它们的预期冲突,并根据要进行的空间/时间权衡来决定哈希表的大小。

当然,在其他情况下也会出现这种分布(请参阅此机器人技术论文和有关SO的问题),我承认哈希隐喻主要是用来描述泊松二项式的样子的工具。

作为读者的有趣笔记,有一种高效的两次通过流算法来计算统一概率,该算法不同于上述两种方法。不过,它在数值上可能不稳定。

我们在复数和离散随机变量之间建立了有趣的联系。 让我们在下一篇文章中了解我们可以走多远。