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

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

Вы можете использовать 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().

Примерно то же, что и 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

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

Они обеспечивают один проход по вашему списку ввода.

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

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)]

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

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