Verifique si dos artículos están en una lista, en un orden en particular?

Question

Digamos que tengo una lista v = [1, 2, 3, 4, 3, 1, 2]. Quiero escribir una función, find_pair que verificará si dos números están en la lista y adyacentes entre sí. Por lo tanto, find_pair(v, 2, 3) debe devolver True, pero find_pair(v, 1, 4) debe devolver False.

¿Es posible aplicar find_pair sin un bucle?

Answer 1

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

Mientras que la versión de @ PaoloCapriotti hace el truco, éste es más rápido, ya que deja de analizar el v tan pronto como se encuentra una coincidencia.

Answer 2

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

Answer 3

En general, es imposible sin iterar sobre todos los valores. Después de todo, una lista de mil elementos puede terminar en [.., 2, 3].

En casos especiales, hay atajos. ¿Los valores están siempre ordenados y siempre está buscando un valor específico? Si es así, puede, por ejemplo, usa una búsqueda binaria para encontrar el valor y luego compáralo con el siguiente valor. Si los valores están desordenados, no hay atajos. Si está buscando dos valores posteriores, no hay atajos. Para los casos intermedios, puede haber un atajo.

Answer 4

Esto es probablemente un poco de una manera indirecta de hacerlo, pero se puede usar (con su variable v arriba):

' 2, 3' in str(v) 

Answer 5

Vas a necesitar un bucle.

A diferencia de las cadenas de Python que admiten una prueba de subsecuencia mediante el operador en, las listas de Python no tienen una prueba de subsecuencia incorporada.

Answer 6

Si escribir la lista ocurre con mucha menos frecuencia que la lectura de ella, tal vez se podría construir un árbol de prefijos sobre escritura. [1] tendría un nodo secundario [2], [2] tendría un [3] y un [3] un [4]. Con un conjunto de datos más complejo, el árbol sería más útil. Tendría una profundidad de 2 en su caso y se indexaría en el elemento inicial de su secuencia de búsqueda.

todavía serías asisten cada nodo, pero sólo una vez durante la vida de la secuencia buscada, si sólo de adición. A medida que agrega un elemento, debe actualizar el árbol para incluir el subsequnce si no está presente. Entonces las lecturas se reducen a un máximo de O (2 * k) donde k es la cantidad de elementos únicos. En el caso de los dígitos, son 20 lecturas máximas para probar si una secuencia está en la lista.

ventaja La velocidad viene de precomputen la longitud-2 subsecuencias de la lista contiene y de la eliminación de duplicados. También se adapta bien a longitudes más largas. O (profundidad * k) el peor caso. Aún mejor si se emplean 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

Sé que ya está satisfecho con uno de la respuesta de en este post pero, puede intentar con los siguientes

>>> 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 curiosidad lo mejor de mí y así que quería probar cómo lo hace aplicación realiza con la aplicación más rápida publicado

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

Gosh esta es una forma rápida

Nota ** Gracias Michael por señalarlo. Lo he corregido y aquí está mi solución actualizada.

Answer 9

La respuesta de eumiro gana por elegancia, pero si necesita algo aún más rápido, puede aprovechar el método integrado list.index() que ahorra tiempo en la iteración de toda la lista.

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

Cuando ejecuto esto, me sale:

f1 0.00300002098083 
f2 0.0 

Esto debería ser aún más rápido cuando el partido no es tan cerca del principio de la lista.

Answer 10

Puede usar el Boyer-Moore algorithm para una aceleración totalmente innecesaria. El caso general es un poco difícil, pero es sencillo si solo buscas un par.

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

Tal vez aún más simple:

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