Нахождение пробелов в данных с помощью битовой маскировки

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 сек).Буду признателен за советы, как сделать это быстрее / эффективнее для больших наборов.Спасибо!</p>

Answer 1

Вы можете использовать XOR и shift, и он выполняется примерно за 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 2

Найдите различия между соседними числами, а затем найдите достаточно большую разницу.Мы находим различия, создавая два списка - все числа, кроме первого, и все числа, кроме последнего - и вычитая их попарно.Мы можем использовать 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. Мы предпочитаем прямую итерацию, и у нас есть настоящий логический тип.)

Answer 3

Они обеспечивают один шаг вашего списка ввода.

Список значений разрывов для заданной длины:

from itertools import tee, izip
def gapsofsize(iterable, length):
    a, b = tee(iterable)
    next(b, None)
    return ( p for x, y in izip(a, b) if y-x == length+1 for p in xrange(x+1,y) )

print list(gapsofsize([1,2,5,8,9], 2))

[3, 4, 6, 7]

Все значения разрывов:

def gaps(iterable):
    a, b = tee(iterable)
    next(b, None)
    return ( p for x, y in izip(a, b) if y-x > 1 for p in xrange(x+1,y) )

print list(gaps([1,2,4,5,8,9,14]))

[3, 6, 7, 10, 11, 12, 13]

Список разрывов в виде векторов:

def gapsizes(iterable):
    a, b = tee(iterable)
    next(b, None)
    return ( (x+1, y-x-1) for x, y in izip(a, b) if y-x > 1 )

print list(gapsizes([1,2,4,5,8,9,14]))

[(3, 1), (6, 2), (10, 4)]

Обратите внимание, что они являются генераторами и занимают очень мало памяти.Я хотел бы знать, как они работают в вашем тестовом наборе данных.

Answer 4

Практически то, что сделал AIX ... но получил только пробелы желаемой длины:

def findGaps(mylist, gap_length, start_idx=0):
    gap_starts = []
    for idx in range(start_idx, len(mylist) - 1):
        if mylist[idx+1] - mylist[idx] == gap_length + 1:
            gap_starts.append(mylist[idx] + 1)

    return gap_starts

РЕДАКТИРОВАТЬ: скорректированы с учетом пожеланий ОП.

Answer 5

Если вам нужна эффективность, я бы сделал что-то вроде следующего (где 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]))