使用散列函数的高效直方图实现

Question

有没有一种比二分搜索非线性二进制分布更有效的方法来计算直方图？

实际上，我只对匹配key ( value )和bin (传递函数？)的算法位感兴趣，也就是说，对于一堆浮点值，我只想知道每个值的适当bin索引。

我知道对于线性仓位分布，你可以通过除以仓位宽度得到O(1)，而对于非线性仓位，二分搜索得到O(logN)。我目前的实现在不相等的bin宽度上使用二进制搜索。

本着提高效率的精神，我很好奇，当您有不等宽的bin时，是否可以使用散列函数将一个值映射到其适当的bin，并实现O(1)的时间复杂度？

Answer 1

普通哈希函数旨在将不同的值相当随机地分布在某个范围内。参数中的一位差异可能导致结果中的几十位不同。因此，普通的散列函数不适用于问题中描述的情况。

另一种方法是使用索引到bin限制的表B中的条目构建一个数组P。给定某个值x，我们通过j = P[⌊x·r⌋]找到它所属的bin j (有时是附近的bin)，其中r是取决于P的大小和B中的最大值的比率。此方法的有效性取决于B中的值和P的大小。

可以通过如下所示的python代码来查看像P[⌊x·r⌋]这样的函数的行为。(该方法在任何编程语言中都是相同的。但是，下面给出了Python-to-C的提示。)假设代码存储在文件histobins.py中，并使用命令import histobins as hb加载到ipython解释器中。然后，像hb.betterparts(27, 99, 9, 80,155)这样的命令会产生这样的输出

At  80 parts, steps = 20 =  7+13
At  81 parts, steps = 16 =  7+9
At  86 parts, steps = 14 =  6+8
At  97 parts, steps = 13 =  12+1
At 108 parts, steps = 12 =  3+9
At 109 parts, steps = 12 =  8+4
At 118 parts, steps = 12 =  6+6
At 119 parts, steps = 10 =  7+3
At 122 parts, steps = 10 =  3+7
At 141 parts, steps = 10 =  5+5
At 142 parts, steps = 10 =  4+6
At 143 parts, steps = 9 =  7+2

这些参数为betterparts设置了nbins=27, topsize=99, seed=9, plo=80, phi=155，它为0到99的值创建了一个27个bin的测试集，随机种子9，P的大小从80到155-1。“step”的数量是在10*nbins值从0到topsize的测试期间，testpart()中的两个while循环操作的次数。例如，“在143个部分，步骤=9=7+2”意味着当P的大小是143，在270次试验中，261次P[⌊x·r⌋]一次产生正确的指数；7次指数必须减少，两次必须增加。

这种方法的总体思想是用空间来换取时间。另一个权衡是准备时间与操作时间。如果你要进行数十亿次的查找，那么值得做几千次试验来找到一个好的| P |的值，也就是P的大小。如果你只要做几百万次的查找，可能更好的做法是选择一些大的|P|值并运行它，或者只在一个小范围内运行更好的部分。如果我们从更大的|P|开始，而不是像上面那样做75个测试，更少的测试可能会给出足够好的结果。例如，通过“hb.betterparts(27，99，9,190,200)”进行的10个测试产生

At 190 parts, steps = 11 =  5+6
At 191 parts, steps = 5 =  3+2
At 196 parts, steps = 5 =  4+1

只要P适合于某个级别的缓存(以及其他相关数据)，使|P|更大将加快访问速度。因此，使|P|与实际一样大是一个好主意。随着|P|变得越来越大，|P|的一个值和下一个值之间的性能差异越来越小。因此，速度上的限制因素包括乘法时间和设置while循环的时间。更快乘法的一种方法可能是选择2的幂作为乘数；计算|P|以匹配；然后使用移位或加法来代替乘法。减少while循环设置时间的一种方法是将语句if bins[bin] <= x < bins[bin+1]: (或其C等效物，见下文)移到while语句之前，只有在if语句失败时才执行while。

Python代码如下所示。请注意，在从Python到C的转换过程中，

·#开始评论

·def开始一个函数

·像ntest, right, wrong, x = 10*nbins, 0, 0, 0这样的语句为各自的标识符赋值

·像return (ntest, right, wrong, stepdown, stepup)这样的语句返回一个由5个值组成的元组，调用者可以将这些值分配给一个元组或相应的标识符

·def, while,或if的作用域以不比def, while,或if缩进更远的行结尾

·bins = [0]初始化一个列表(一个可扩展的可索引数组)，初始值为0

·bins.append(t)在列表bins的末尾追加t值

·for i,j in enumerate(p):在可迭代p的元素上运行循环(在本例中，p是一个列表)，使索引i和相应的条目j == p[i]在循环中可用

·range(nparts)表示值0，1，...的列表nparts 1

·range(plo, phi)代表值plo、plo+1、...的列表φ-1

·if bins[bin] <= x < bins[bin+1]的意思是if ((bins[bin] <= x) && (x < bins[bin+1]))

·int(round(x*float(nparts)/topsize)))实际上是对x·r进行取整，而不是像上面所宣传的那样计算⌊x·r⌋

def makebins(nbins, topsize):
    bins, t = [0], 0
    for i in range(nbins):
        t += random.random()
        bins.append(t)
    for i in range(nbins+1):
        bins[i] *= topsize/t
    bins.append(topsize+1)
    return bins
#________________________________________________________________
def showbins(bins):
    print ''.join('{:6.2f} '.format(x) for x in bins)
def showparts(nbins, bins, topsize, nparts, p):
    ratio = float(topsize)/nparts
    for i,j in enumerate(p):
        print '{:3d}. {:3d} {:6.2f} {:7.2f} '.format(i, j, bins[j], i*ratio)
    print 'nbins: {}  topsize: {}  nparts: {}  ratio: {}'.format(nbins, topsize, nparts, ratio)
    print 'p = ', p
    print 'bins = ',
    showbins(bins)
#________________________________________________________________

def testparts(nbins, topsize, nparts, seed):
    # Make bins and make lookup table p
    import random
    if seed > 0: random.seed(seed)
    bins = makebins(nbins,topsize)
    ratio, j, p = float(topsize)/nparts, 0, range(nparts)
    for i in range(nparts):
        while j<nbins and i*ratio >= bins[j+1]:
            j += 1
        p[i] = j
    p.append(j)
    #showparts(nbins, bins, topsize, nparts, p)

    # Count # of hits and steps with avg. of 10 items per bin
    ntest, right, wrong, x  = 10*nbins, 0, 0, 0
    delta, stepdown, stepup = topsize/float(ntest), 0, 0
    for i in range(ntest):
        bin = p[min(nparts, max(0, int(round(x*float(nparts)/topsize))))]

        while bin < nbins and x >= bins[bin+1]:
            bin += 1; stepup += 1
        while bin > 0 and x < bins[bin]:
            bin -= 1; stepdown += 1
        if bins[bin] <= x < bins[bin+1]: # Test if bin is correct
            right += 1
        else:
            wrong += 1
            print 'Wrong bin {} {:7.3f} at x={:7.3f}   Too {}'.format(bin, bins[bin], x, 'high' if bins[bin] > x else 'low')
        x += delta
    return (ntest, right, wrong, stepdown, stepup)
#________________________________________________________________

def betterparts(nbins, topsize, seed, plo, phi):
    beststep = 1e9
    for parts in range(plo, phi):
        ntest, right, wrong, stepdown, stepup = testparts(nbins, topsize, parts, seed)
        if wrong: print 'Error with ', parts, ' parts'
        steps = stepdown + stepup
        if steps <= beststep:
            beststep = steps
            print 'At {:3d} parts, steps = {:d} =  {:d}+{:d}'.format(parts, steps, stepdown, stepup)
#________________________________________________________________

Answer 2

在一些简单的情况下，你可以得到O(1)。

假设你的值是8位的，从0到255。

如果将它们分成大小为2、2、4、8、16、32、64、128的8个bin，则bin的取值范围为: 0-1、2-3、4-7、8-15、16-31、32-63、64-127、128-255。

在二进制中，这些范围如下所示：

0000000x (bin 0)
0000001x
000001xx
00001xxx
0001xxxx
001xxxxx
01xxxxxx
1xxxxxxx (bin 7)

因此，如果您可以快速(在O(1)中)计算值中有多少个最高有效零位，您就可以从中获得bin编号。

在这种特殊情况下，您可以预先计算包含bin编号的256个元素的查找表，并且只需查找一次表即可找到一个值的适当bin。

实际上，对于8位的值，您可以使用任意大小的bit，因为查找表很小。

如果你使用2的幂大小的箱子，你也可以对16位的值重用这个查询表。你需要两次检查。您可以将其扩展到更长的值。

Answer 3

Interpolation search是你的朋友。这是一种乐观的，预测性的二进制搜索，它基于关于输入分布的线性假设来猜测bin应该在哪里，而不是在每一步将搜索空间一分为二。如果线性假设为真，它将是O(1)，但当假设不为真时，它仍然有效(尽管速度更慢)。在其预测准确的程度上，搜索是快速的。