使用位掩码查找数据缺口

Question

我遇到了一个问题，就是要在一串数字中找出指定长度的间隙（空缺）。比如说，给定的数字是 [1,2,3,7,8,9,10]，如果我想找长度为 3 的间隙，我会找到 [4,5,6]。如果间隙的长度是 4，那就什么也找不到。当然，实际的数字序列要长得多。我在很多帖子中看到过这个问题，它有各种应用和实现方式。

我想到的一种可能有效且相对快速的方法是用一个位数组来表示整个数字集合，1表示这个数字存在，0表示这个数字缺失。这样，上面的例子就可以表示为 [1,1,1,0,0,0,1,1,1,1]。然后可以运行一个窗口函数，用给定长度的数组与完整集合进行异或运算，直到所有位置的结果都是1。这个方法大概只需要遍历整个序列一次，复杂度大约是 ~O(n)，再加上每次运算的掩码成本。

这是我想到的实现：

def find_gap(array, start=0, length=10):
    """
    array:  assumed to be of length MAX_NUMBER and contain 0 or 1 
            if the value is actually present
    start:  indicates what value to start looking from
    length: what the length the gap should be
    """

    # create the bitmask to check against
    mask = ''.join( [1] * length )

    # convert the input 0/1 mapping to bit string
    # e.g - [1,0,1,0] -> '1010'
    bits =''.join( [ str(val) for val in array ] )

    for i in xrange(start, len(bits) - length):

        # find where the next gap begins
        if bits[i] != '0': continue

        # gap was found, extract segment of size 'length', compare w/ mask
        if (i + length < len(bits)):
            segment = bits[i:i+length]

            # use XOR between binary masks
            result  = bin( int(mask, 2) ^ int(segment, 2) )

            # if mask == result in base 2, gap found
            if result == ("0b%s" % mask): return i

    # if we got here, no gap exists
    return -1

这个方法对于大约10万的数据来说相当快（不到1秒）。如果有更快或更高效的方法来处理更大的数据集，我会很感激大家的建议。谢谢！

Answer 1

如果你想要提高效率，我会建议你按照下面的方式来做（这里的 x 是一个序列号的列表）：

for i in range(1, len(x)):
  if x[i] - x[i - 1] == length + 1:
    print list(range(x[i - 1] + 1, x[i]))

Answer 2

你可以使用异或（XOR）和位移操作，这样大约能在 O(n) 的时间内完成。

不过在实际操作中，建立一个索引（也就是记录所有大于某个最小长度的间隙的哈希列表）可能是更好的方法。

假设你是从一串整数开始（而不是位掩码），那么你可以通过遍历这串数字来建立索引；每当你发现一个大于你设定的阈值的间隙，就把这个间隙的大小添加到你的字典里（如果需要的话，先把它初始化为一个空列表，然后把在序列中的偏移量加进去）。

最后，你就得到了一个包含所有大于你设定阈值的间隙的列表。

这个方法的一个好处是，当你修改基础列表时，你应该能够保持这个索引的更新。所以，最开始建立索引时花费的 O(n*log(n)) 时间，后续查询和更新索引时只需要 O(log(n)) 的成本。

这里有一个非常简单的函数来建立 gap_index()：

def gap_idx(s, thresh=2):
    ret = dict()
    lw = s[0]  # initial low val.
    for z,i in enumerate(s[1:]):
        if i - lw < thresh:
            lw = i
            continue
        key = i - lw
        if key not in ret:
            ret[key] = list()
        ret[key].append(z)
        lw = i
    return ret

为了同时维护数据集和索引，最好是围绕内置的 'bisect' 模块和它的 insort() 函数来构建一个类。

Answer 3

找出相邻数字之间的差异，然后看看有没有差异足够大的。我们通过构建两个列表来找到这些差异——一个是去掉第一个数字后的所有数字，另一个是去掉最后一个数字后的所有数字。然后我们把这两个列表中的数字一一相减。我们可以用 zip 来把这些数字配对起来。

def find_gaps(numbers, gap_size):
    adjacent_differences = [(y - x) for (x, y) in zip(numbers[:-1], numbers[1:])]
    # If adjacent_differences[i] > gap_size, there is a gap of that size between
    # numbers[i] and numbers[i+1]. We return all such indexes in a list - so if
    # the result is [] (empty list), there are no gaps.
    return [i for (i, x) in enumerate(adjacent_differences) if x > gap_size]

(另外，请学习一些Python的常用写法。我们更喜欢直接遍历，而且Python有真正的布尔类型。)