tamaño - metodos de listas en python
Probando si una lista contiene otra lista con Python (12)
¿Cómo puedo probar si una lista contiene otra lista (es decir, es una subsecuencia contigua)? Supongamos que hay una función llamada contains:
contains([1,2], [-1, 0, 1, 2]) # Returns [2, 3] (contains returns [start, end])
contains([1,3], [-1, 0, 1, 2]) # Returns False
contains([1, 2], [[1, 2], 3]) # Returns False
contains([[1, 2]], [[1, 2], 3]) # Returns [0, 0]
Editar:
contains([2, 1], [-1, 0, 1, 2]) # Returns False
contains([-1, 1, 2], [-1, 0, 1, 2]) # Returns False
contains([0, 1, 2], [-1, 0, 1, 2]) # Returns [1, 3]
Aquí está mi respuesta. Esta función lo ayudará a averiguar si B es una sub-lista de A. La complejidad del tiempo es O (n).
`def does_A_contain_B(A, B): #remember now A is the larger list
b_size = len(B)
for a_index in range(0, len(A)):
if A[a_index : a_index+b_size]==B:
return True
else:
return False`
Aquí está mi versión:
def contains(small, big):
for i in xrange(len(big)-len(small)+1):
for j in xrange(len(small)):
if big[i+j] != small[j]:
break
else:
return i, i+len(small)
return False
Devuelve una tupla de (inicio, final + 1) ya que creo que es más pitónico, como señala Andrew Jaffe en su comentario. No corta ninguna sublista, por lo que debe ser razonablemente eficiente.
Un punto de interés para los novatos es que usa la cláusula else en la declaración for ; esto no es algo que use muy a menudo, pero puede ser muy valioso en situaciones como esta.
Esto es idéntico a buscar subcadenas en una cadena, por lo que para listas grandes puede ser más eficiente implementar algo así como el algoritmo Boyer-Moore .
Aquí hay un algoritmo sencillo que usa métodos de lista:
#!/usr/bin/env python
def list_find(what, where):
"""Find `what` list in the `where` list.
Return index in `where` where `what` starts
or -1 if no such index.
>>> f = list_find
>>> f([2, 1], [-1, 0, 1, 2])
-1
>>> f([-1, 1, 2], [-1, 0, 1, 2])
-1
>>> f([0, 1, 2], [-1, 0, 1, 2])
1
>>> f([1,2], [-1, 0, 1, 2])
2
>>> f([1,3], [-1, 0, 1, 2])
-1
>>> f([1, 2], [[1, 2], 3])
-1
>>> f([[1, 2]], [[1, 2], 3])
0
"""
if not what: # empty list is always found
return 0
try:
index = 0
while True:
index = where.index(what[0], index)
if where[index:index+len(what)] == what:
return index # found
index += 1 # try next position
except ValueError:
return -1 # not found
def contains(what, where):
"""Return [start, end+1] if found else empty list."""
i = list_find(what, where)
return [i, i + len(what)] if i >= 0 else [] #NOTE: bool([]) == False
if __name__=="__main__":
import doctest; doctest.testmod()
Código más pequeño:
def contains(a,b):
str(a)[1:-1].find(str(b)[1:-1])>=0
Creo que este es rápido ...
def issublist(subList, myList, start=0):
if not subList: return 0
lenList, lensubList = len(myList), len(subList)
try:
while lenList - start >= lensubList:
start = myList.index(subList[0], start)
for i in xrange(lensubList):
if myList[start+i] != subList[i]:
break
else:
return start, start + lensubList - 1
start += 1
return False
except:
return False
Después de la edición de OP:
def contains(small, big):
for i in xrange(1 + len(big) - len(small)):
if small == big[i:i+len(small)]:
return i, i + len(small) - 1
return False
Esto funciona y es bastante rápido ya que realiza la búsqueda lineal utilizando el método list.index() y == operador:
def contains(sub, pri):
M, N = len(pri), len(sub)
i, LAST = 0, M-N+1
while True:
try:
found = pri.index(sub[0], i, LAST) # find first elem in sub
except ValueError:
return False
if pri[found:found+N] == sub:
return [found, found+N-1]
else:
i = found+1
Hay una función all() y any() para hacer esto. Para verificar si list1 contiene TODOS los elementos en list2
result = all(elem in list1 for elem in list2)
Para verificar si list1 contiene CUALQUIER elemento en list2
result = any(elem in list1 for elem in list2)
el resultado de la variable sería booleano (VERDADERO / FALSO).
Puedo sugerir humildemente el algoritmo Rabin-Karp si la big lista es realmente grande. El enlace incluso contiene código casi utilizable en casi-Python.
Si refinamos el problema hablando de las pruebas si una lista contiene otra lista con una secuencia, la respuesta podría ser el siguiente delineador:
def contains(subseq, inseq):
return any(inseq[pos:pos + len(subseq)] == subseq for pos in range(0, len(inseq) - len(subseq) + 1))
Aquí pruebas unitarias que usé para ajustar este one-liner:
Si todos los elementos son únicos, puede usar conjuntos.
>>> items = set([-1, 0, 1, 2])
>>> set([1, 2]).issubset(items)
True
>>> set([1, 3]).issubset(items)
False
Traté de hacer esto lo más eficiente posible.
Utiliza un generador; a los que no están familiarizados con estas bestias se les aconseja que revisen su documentación y la de las expresiones de rendimiento .
Básicamente crea un generador de valores de la subsecuencia que se puede restablecer enviándole un valor verdadero. Si el generador se reinicia, comienza a ceder nuevamente desde el comienzo del sub .
Luego solo compara valores sucesivos de sequence con los rendimientos del generador, reiniciando el generador si no coinciden.
Cuando el generador se queda sin valores, es decir, llega al final del sub sin reiniciarlo, eso significa que hemos encontrado nuestra coincidencia.
Dado que funciona para cualquier secuencia, incluso puede usarla en cadenas, en cuyo caso se comporta de manera similar a str.find , excepto que devuelve False lugar de -1 .
Como nota adicional: creo que el segundo valor de la tupla devuelta debería, de acuerdo con los estándares de Python, normalmente ser uno más alto. es decir, "string"[0:2] == "st" . Pero la especificación dice lo contrario, así es como funciona esto.
Depende de si esto pretende ser una rutina de propósito general o si está implementando algún objetivo específico; en el último caso, podría ser mejor implementar una rutina de propósito general y luego envolverla en una función que modifique el valor de retorno para adaptarlo a la especificación.
def reiterator(sub):
"""Yield elements of a sequence, resetting if sent ``True``."""
it = iter(sub)
while True:
if (yield it.next()):
it = iter(sub)
def find_in_sequence(sub, sequence):
"""Find a subsequence in a sequence.
>>> find_in_sequence([2, 1], [-1, 0, 1, 2])
False
>>> find_in_sequence([-1, 1, 2], [-1, 0, 1, 2])
False
>>> find_in_sequence([0, 1, 2], [-1, 0, 1, 2])
(1, 3)
>>> find_in_sequence("subsequence",
... "This sequence contains a subsequence.")
(25, 35)
>>> find_in_sequence("subsequence", "This one doesn''t.")
False
"""
start = None
sub_items = reiterator(sub)
sub_item = sub_items.next()
for index, item in enumerate(sequence):
if item == sub_item:
if start is None: start = index
else:
start = None
try:
sub_item = sub_items.send(start is None)
except StopIteration:
# If the subsequence is depleted, we win!
return (start, index)
return False