首页 > 编程珠玑P135页

编程珠玑P135页

中间有段话是这样说的:直观的映射t*bins/maxval可能导致数值溢出,因此,我们采用下述代码所示的更安全的映射:

void insert(t)
    i = t / (1 + maxval/bins)
    bin[i] = rinsert(bin[i], t)

请问:为什么会溢出?(我觉得可能是先乘后除的原因),另外,为什么i = t / (1 + maxval/bins)要加上1呢?


没有看过书, 个人觉的原因如下: t*bins/maxval 会溢出 , 是因为 t * bins , 如果t 和 bins 都为 INT_MAX , 直接乘就溢出了

加1的原因一般有二个吧:

  1. 避免除0
  2. 避免除数太小 , 发生溢出 , 比如 maxval/bins = 1e-10 , 那么 t / ( maxvla / bins) 就等于 t ^ 10 , 然后就溢出了 , 加上1之后 , 结果就在 1 ~ t 之间了 。

加一是当maxval不是bins的倍数的情况下,仍然能将 0..maxval 分布到各个bins中去(虽然不严格均分),相当于每个bin(或bucket)都有了额外的空间。

举个例子: 假设maxval为50, bins为3。若无额外空间的话,只能分别映射 [0..15], [16..31], [32..47],若t in [48..50],就溢出了。

PS 我想书中所说的溢出也有这个意思。


溢出你的想法是对的 坐等加一的答案

【热门文章】
【热门文章】