python - 使用位掩码查找数据间隙

Question

我面临着在数字序列中查找给定长度的不连续点(间隙)的问题。因此，例如，给定 [1,2,3,7,8,9,10] 和 length=3 的间隙，我会找到 [4,5,6]。如果差距是 length=4，我将一无所获。当然，真正的序列要长得多。我在很多帖子中看到过这个问题，它有各种应用程序和可能的实现。

我认为可行并且应该相对较快的一种方法是将完整集表示为一个位数组，其中包含 1 表示可用数字，0 表示缺失 - 所以上面的代码看起来像 [1,1,1, 0,0,0,1,1,1,1]。然后可能运行一个窗口函数，它将给定长度的数组与完整集合进行 XOR 掩码，直到所有位置都为 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

这对于 ~100k(< 1 秒)来说相当快。我很感激关于如何使更大的集合更快/更有效的提示。谢谢!

Answer 1

找出相邻数字之间的差异，然后寻找足够大的差异。我们通过构建两个列表来找到差异——除了第一个之外的所有数字，以及除了最后一个之外的所有数字——然后将它们成对相减。我们可以使用 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 习语。我们更喜欢直接迭代，我们有一个真正的 bool 类型。)