Проверьте, находятся ли два элемента в списке в определенном порядке?

Question

Скажем, у меня есть список v = [1, 2, 3, 4, 3, 1, 2]. Я хочу написать функцию, find_pair, которая проверит, находятся ли два числа в списке и рядом друг с другом. Итак, find_pair(v, 2, 3) должен вернуть True, но find_pair(v, 1, 4) должен вернуть False.

Возможно ли реализовать find_pair без петли?

Answer 1

v = [1,2,3,4,3,1,2] 
any([2,3] == v[i:i+2] for i in xrange(len(v) - 1)) 

Хотя @ PaoloCapriotti-й версия делает трюк, это один быстрее, потому что он прекращает разбор v, как только будет найдено совпадение.

Answer 2

[2, 3] in [v[i:i+2] for i in range(len(v) - 1)] 

Answer 3

В общем, это невозможно без повторения всех значений. В конце концов, список из тысячи элементов может закончиться [.., 2, 3].

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

Answer 4

Это, вероятно, немного кружным путем, чтобы сделать это, но вы можете использовать (с переменной V выше):

' 2, 3' in str(v) 

Answer 5

Вы будете нуждаться в петлю.

В отличие от строк Python, которые поддерживают тест подпоследовательности с использованием в операторе, списки Python не имеют встроенного теста подпоследовательности.

Answer 6

Если запись списка происходит гораздо реже, чем чтение из нее, возможно, вы можете построить дерево префиксов при записи. [1] будет иметь дочерний узел [2], [2] будет иметь [3] и [3] a [4]. С более сложным набором данных дерево было бы более полезным. Он будет иметь глубину 2 в вашем случае и будет проиндексирован на начальном элементе в вашей последовательности поиска.

Вы все равно будете посещать каждый узел, но только один раз для жизни искомой последовательности, если append-only. Когда вы добавляете элемент, вы обновляете дерево, чтобы включить subsequnce, если он отсутствует. Тогда чтение до максимума O (2 * k), где k - количество уникальных элементов. В случае цифр это 20 максимальных значений для проверки, есть ли последовательность в списке.

Преимущество скорости заключается в предварительном вычислении подпоследовательностей длиной-2, содержащихся в списке, и от удаления дубликатов. Он также хорошо масштабируется до более длинных. O (глубина * k) наихудший случай. Еще лучше, если используются hashtables.

Answer 7

v = [1,2,3,4,3,1,2] 

def find(x,y,v): 
     return (x,y) in zip(v,v[1:]) 

print find(2,3,v) 
print find(1,4,v) 

Answer 8

Я знаю, что вы уже счастливы с одним из ответа на этом посту, но вы можете попробовать со следующим

>>> v = [1,2,3,4,3,1,2] 
def InList(v,(i,j)): 
    start=1 
    try: 
     while True: 
      if v[v.index(i,start)+1]==j and v[v.index(j,start)-1]==i: 
       return True 
      start=v.index(i)+1 
    except IndexError: 
     return False 
    except ValueError: 
     return False 


>>> InList(v,(2,3)) 
True 
>>> InList(v,(4,5)) 
False 
>>> InList(v,(1,2)) 
True 
>>> InList(v,(12,2)) 
False 
>>> InList(v,(3,1)) 
True 

Ok Любопытство стало лучше меня, и так хотел, чтобы проверить, как это делает реализация осуществляется с быстрым публикуемыми реализациями

>>> stmt1=""" 
v = [1,2,3,4,3,1,2] 
def InList(v,(i,j)): 
    start=1 
    try: 
     while True: 
      if v[v.index(i,start)+1]==j and v[v.index(j,start)-1]==i: 
       return True 
      start=v.index(i)+1 
    except IndexError: 
     return False 
    except ValueError: 
     return False 
InList(v,(2,3)) 
InList(v,(4,5)) 
InList(v,(1,2)) 
InList(v,(12,2)) 
""" 
>>> stmt2=""" 
v = [1,2,3,4,3,1,2] 
def InList(v,(x,y)): 
    any([x,y] == v[i:i+2] for i in xrange(len(v) - 1)) 
InList(v,(2,3)) 
InList(v,(4,5)) 
InList(v,(1,2)) 
InList(v,(12,2)) 
""" 
>>> t1=timeit.Timer(stmt=stmt1) 
>>> t2=timeit.Timer(stmt=stmt2) 
>>> print "%.2f usec/pass" % (1000000 * t1.timeit(number=100000)/100000) 
13.67 usec/pass 
>>> print "%.2f usec/pass" % (1000000 * t2.timeit(number=100000)/100000) 
20.67 usec/pass 
>>> 

Гоши это быстрое путем

Примечание ** Спасибо, Майкл за это. Я исправил его, и вот мое обновленное решение.

Answer 9

Ответ eumiro выигрывает для элегантности, но если вам нужно что-то еще быстрее, вы можете воспользоваться встроенным способом list.index(), который экономит время на итерации по всему списку.

v = [1,2,3,4,3,1,2] 

def f1(items): 
    return any([2,3] == v[i:i+2] for i in xrange(len(v) - 1)) 

def f2(items): 
    i = 0 
    index = items.index 
    try: 
     while 1: 
      i = index(2, i) + 1 
      if items[i] == 3: 
       return True 
    except IndexError: 
     return False 

from timeit import repeat  
print "f1", min(repeat("f1(v)", "from __main__ import f1, v", number=1000)) 
print "f2", min(repeat("f2(v)", "from __main__ import f2, v", number=1000)) 

Когда я запускаю это, я получаю:

f1 0.00300002098083 
f2 0.0 

Это должно быть еще быстрее, когда матч не так близко к началу списка.

Answer 10

Вы можете использовать Boyer-Moore algorithm для совершенно ненужного ускорения. Общий случай немного сложный, но это просто, если вы просто ищете пару.

def find_pair(seq, a, b): 
    i = 1 
    while i < len(seq): 
     if seq[i] == b and seq[i - 1] == a: return i - 1 
     i += 2 - (seq[i] == a) 

print find_pair([1, 5, 3, 4, 3, 1, 2, 3, 3], 2, 3) 

Answer 11

Возможно, еще проще:

a = range(100) 
exists = (55,56) in zip(a, a[1:])