Pythonic способ определить, являются ли не нулевые записи списка "непрерывными",

Ответ 1

def contiguous(seq):
    seq = iter(seq)
    all(x is None for x in seq)        # Burn through any Nones at the beginning
    any(x is None for x in seq)        # and the first group
    return all(x is None for x in seq) # everthing else (if any) should be None.

Вот несколько примеров. Вы можете использовать next(seq), чтобы получить следующий элемент из итератора. Я поставлю знак, указывающий на следующий элемент после каждого

example1:

seq = iter([None, 1, 2, 3, None])        #  [None, 1, 2, 3, None]
                                         # next^
all(x is None for x in seq)            
                                         #        next^
any(x is None for x in seq)            
                                         #                    next^ (off the end)
return all(x is None for x in seq)       # all returns True for the empty sequence

example2:

seq = iter([1, 2, None, 3, None, None])  #    [1, 2, None, 3, None, None]
                                         # next^
all(x is None for x in seq)            
                                         #    next^
any(x is None for x in seq)            
                                         #             next^  
return all(x is None for x in seq)       # all returns False when 3 is encountered

Ответ 2

Хорошо 'ol itertools.groupby на помощь:

from itertools import groupby

def contiguous(seq):
    return sum(1 for k,g in groupby(seq, lambda x: x is not None) if k) == 1

дает

>>> contiguous([1,2,3,None,None])
True
>>> contiguous([None, 1,2,3,None])
True
>>> contiguous([None, None, 1,2,3])
True
>>> contiguous([None, 1, None, 2,3])
False
>>> contiguous([None, None, 1, None, 2,3])
False
>>> contiguous([None, 1, None, 2, None, 3])
False
>>> contiguous([1, 2, None, 3, None, None])
False

[править]

Поскольку в комментариях есть некоторые обсуждения, я объясню, почему мне нравится этот подход лучше, чем некоторые другие.

Мы пытаемся выяснить, существует ли одна непрерывная группа объектов, отличных от None, и

sum(1 for k,g in groupby(seq, lambda x: x is not None) if k)

подсчитывает количество смежных объектов, отличных от None, используя функцию в stdlib, которая предназначена для сбора сопредельных групп. Как только мы видим groupby, мы считаем "смежными группами" и наоборот. В этом смысле он самодокументируется. Это в основном определение моей цели.

ИМХО Единственная слабость в том, что она не замыкается, и это может быть исправлено, но, подумав об этом, я все еще предпочитаю это, поскольку он использует примитив, который мне нравится, - "подсчитайте количество смежных не-" Нет групп ", которые я предпочитаю просто" рассказать мне, есть ли у вас более чем одна непрерывная группа, отличная от группы ", как только сможете".

Многие из подходов к реализации последнего зависят от умных наблюдений за проблемой, например "если есть только одна непрерывная группа объектов не-Нет", тогда, если мы сканируем, пока не найдем первый объект не-Нет, а затем сканировать объекты до тех пор, пока мы не найдем первую группу, отличную от None, если она существует, то оставлено ли что-либо, что None дает нам наш ответ ". (Или что-то в этом роде, которое является частью моей проблемы: я должен подумать об этом.) Мне кажется, что я использую" детали реализации" о проблеме для ее решения и фокусируется на свойствах проблемы, которые мы можем использовать для решения это, а не просто указать проблему на Python и позволить Python выполнять эту работу.

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

Как всегда, каждый пробег может варьироваться, конечно, и, вероятно, пропорционально их умению.

Ответ 3

Вы можете использовать что-то вроде itertools.groupby:

from itertools import groupby

def are_continuous(items):
    saw_group = False

    for group, values in groupby(items, lambda i: i is not None):
        if group:
            if saw_group:
                return False
            else:
                saw_group = True

    return True

Это будет повторяться только до тех пор, пока он не увидит группу дважды. Я не уверен, если вы считаете [None, None], так что настройте его на свои нужды.

Ответ 4

Это может быть не лучший способ сделать это, но вы можете найти первую запись, отличную от None, и последнюю запись non-None, а затем проверить срез для None. например:.

def is_continuous(seq):
    try:
        first_none_pos = next(i for i,x in enumerate(seq) if x is not None)
        #need the or None on the next line to handle the case where the last index is `None`.
        last_none_pos = -next(i for i,x in enumerate(reversed(seq)) if x is not None) or None
    except StopIteration: #list entirely of `Nones`
        return False
    return None not in seq[first_none_pos:last_none_pos]

assert is_continuous([1,2,3,None,None]) == True
assert is_continuous([None, 1,2,3,None]) == True
assert is_continuous([None, None, 1,2,3]) == True
assert is_continuous([None, 1, None, 2,3]) == False
assert is_continuous([None, None, 1, None, 2,3]) == False
assert is_continuous([None, 1, None, 2, None, 3]) == False
assert is_continuous([1, 2, None, 3, None, None]) == False

Это будет работать для любого типа последовательности.

Ответ 5

Естественным способом использования элементов последовательности является использование dropwhile:

from itertools import dropwhile
def continuous(seq):
    return all(x is None for x in dropwhile(lambda x: x is not None,
                                            dropwhile(lambda x: x is None, seq)))

Мы можем выразить это без вложенных вызовов функций:

from itertools import dropwhile
def continuous(seq):
    core = dropwhile(lambda x: x is None, seq)
    remainder = dropwhile(lambda x: x is not None, core)
    return all(x is None for x in remainder)

Ответ 6

Один вкладыш:

contiguous = lambda l: ' ' not in ''.join('x '[x is None] for x in l).strip()

Реальная работа выполняется с помощью функции strip. Если в разделенной строке есть пробелы, то они не ведутся/завершаются. Остальная часть функции преобразует список в строку, которая имеет пробел для каждого None.

Ответ 7

Я сделал некоторые профилирования, чтобы сравнить подход @gnibbler с подходом groupby. Подход @gnibber последовательно быстрее, особенно. для более длинных списков. Например, я вижу около 50% прироста производительности для случайных входов с длиной 3-100, с 50% -ной вероятностью содержать одну последовательную последовательность (случайным образом выбранную) и в противном случае со случайными значениями. Тестовый код ниже. Я вкратцевал два метода (случайный выбор, который идет первым), чтобы убедиться, что эффекты кеширования отменены. Исходя из этого, я бы сказал, что, хотя подход groupby более интуитивно понятен, подход @gnibber может быть уместным, если профилирование указывает, что это важная часть общего кода для оптимизации - в этом случае соответствующие комментарии должны использоваться для укажите, что происходит с использованием всех/любых значений итератора потребителя.

from itertools import groupby
import random, time

def contiguous1(seq):
    # gnibber approach
    seq = iter(seq)
    all(x is None for x in seq)        # Burn through any Nones at the beginning
    any(x is None for x in seq)        # and the first group
    return all(x is None for x in seq) # everthing else (if any) should be None.

def contiguous2(seq):
    return sum(1 for k,g in groupby(seq, lambda x: x is not None) if k) == 1

times = {'contiguous1':0,'contiguous2':0}

for i in range(400000):
    n = random.randint(3,100)
    items = [None] * n
    if random.randint(0,1):
        s = random.randint(0,n-1)
        e = random.randint(0,n-s)
        for i in range(s,e):
            items[i] = 3
    else:
        for i in range(n):
            if not random.randint(0,2):
                items[i] = 3
    if random.randint(0,1):
        funcs = [contiguous1, contiguous2]
    else:
        funcs = [contiguous2, contiguous1]
    for func in funcs:
        t0 = time.time()
        func(items)
        times[func.__name__] += (time.time()-t0)

print
for f,t in times.items():
    print '%10.7f %s' % (t, f)

Ответ 8

Здесь представлено решение, основанное на numpy. Получите индексы массива всех ненулевых элементов. Затем сравните каждый индекс с тем, который следует за ним. Если разница больше единицы, между ненулевыми значениями есть нули. Если нет индексов, где следующий индекс больше одного больше, то пробелов нет.

def is_continuous(seq):
    non_null_indices = [i for i, obj in enumerate(seq) if obj is not None]
    for i, index in enumerate(non_null_indices[:-1]):
        if non_null_indices[i+1] - index > 1:
            return False
    return True

Ответ 9

Этот алгоритм выполняет работу с несколькими недостатками (удаляет элементы из списка). Но это решение.

В принципе, если вы удалите все непрерывные None с начала и конца. И если вы нашли в списке None число, то целые числа не находятся в непрерывной форме.

def is_continuous(seq):
    while seq and seq[0] is None: del seq[0]
    while seq and seq[-1] is None: del seq[-1]

    return None not in seq

assert is_continuous([1,2,3,None,None]) == True
assert is_continuous([None, 1,2,3,None]) == True
assert is_continuous([None, None, 1,2,3]) == True
assert is_continuous([None, 1, None, 2,3]) == False
assert is_continuous([None, None, 1, None, 2,3]) == False
assert is_continuous([None, 1, None, 2, None, 3]) == False
assert is_continuous([1, 2, None, 3, None, None]) == False

Тем не менее, еще один пример того, как маленький код может стать злым.

Я хотел бы, чтобы strip() был доступен для list.

Ответ 10

Мой первый подход заключался в использовании переменных для отслеживания...

... это заканчивается очень вложенной и очень трудной последовательностью последовательностей if/else, встроенных в цикл for...

Нет! На самом деле вам нужна только одна переменная. Понимание этой проблемы с точки зрения конечного автомата (FSM) с вашим подходом приведет к довольно приятному решению.

Назовем состояние p. Сначала p равно 0. Затем мы начинаем ходить между состояниями.

Когда все элементы в списке проверяются и все равно не сбой, тогда ответ True.

Одна версия, которая кодирует таблицу переводов в dict

def contiguous(s, _D={(0,0):0, (0,1):1, (1,0):2, (1,1):1, (2,0):2, (2,1):3}):
    p = 0
    for x in s:
        p = _D[p, int(x is not None)]
        if p >= 3: return False
    return True

Другая версия, использующая оператор if:

def contiguous(s):
    p = 0
    for x in s:
        if x is None and p == 1 or x is not None and (p == 0 or p == 2):
            p += 1
        if p >= 3: return False
    return True

Поэтому я хочу сказать, что использование if и for по-прежнему является питоновым.

Обновление

Я нашел другой способ кодирования FSM. Мы можем упаковать таблицу переводов в 12-битное целое число.

def contiguous(s):
    p = 0
    for x in s:
        p = (3684 >> (4*p + 2*(x!=None))) & 3
        if p >= 3: return False
    return True

Здесь 3684, магическое число, можно получить:

    _D[p,a]     3  2  1  2  1  0
         p      2  2  1  1  0  0
         a      1  0  1  0  1  0
bin(3684) = 0b 11 10 01 10 01 00 

Читаемость не так хороша, как другая, но быстрее, поскольку она позволяет избежать поиска в словарях. Вторая версия работает так же быстро, как это, но эту идею кодирования можно обобщить, чтобы решить больше проблем.

Ответ 11

Вот способ использования numpy:

a = np.array([1, 2, 3, np.nan, 4, 5, np.nan, 6, 7])

# This returns indices of nans
# eg. [[3], [6]]
# use .squeeze() to convert to [3, 6]
aa = np.argwhere(a != a).squeeze()

# use a diff on your array , if the nans
# are continuous, the diff will always be 1
# if not, diff will be > 1 , and using any() will return True
any(np.diff(aa) > 1)