Dado una lista que contiene un patrón conocido rodeado por el ruido, hay una manera elegante de obtener todos los elementos que la igualdad en el patrón. Véase más abajo para mi crudo código.

list_with_noise = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
known_pattern = [1,2,3,4]
res = []


for i in list_with_noise:
    for j in known_pattern:
        if i == j:
            res.append(i)
            continue

print res

tendríamos 2, 1, 2, 3, 4, 2, 1, 2, 3, 4, 1, 2, 3, 4, 4, 3

bono: evite anexar yo si el patrón no está presente (es decir, permitir 1,2,3,4 pero no 1,2,3)

ejemplos:

find_sublists_in_list([7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5],[1,2,3,4])

[1,2,3,4],[1,2,3,4],[1,2,3,4]


find_sublists_in_list([7,2,1,2,3,2,1,2,3,6,9,9,1,2,3,4,7,4,3,1,2,6],[1,2,3,4])

[1,2,3],[1,2,3],[1,2,3]

Las listas contienen tuplas con nombre.

  • Fiesta sus ojos en en.wikipedia.org/wiki/String_searching_algorithm
  • Usted tal vez quiera dar algunos ejemplos de entradas y los correspondientes resultados esperados. Su pregunta, en su forma actual no es clara.
  • Es esta una pregunta o un ejercicio de programación?
  • No entiendo la diferencia. Actualmente tengo el código de arriba, pero quiere algo «más agradable»
  • Permítanme aclarar, ¿quieres conseguir esas entradas de list_with_nose que están en known_patterns en el mismo orden?
  • ¿Qué acerca de la superposición de patrones (dicen que usted busca [1, 1] en [1, 1, 1, 1]): ¿qué desea que el código de retorno: 2 o 3 partidos?
  • Otra pregunta: ¿qué tipo de elementos hace de su lista con el ruido de contener? algo rápido y las soluciones simples pueden estar disponibles si los elementos son bastante simples (como en la expresión regular de la solución propuesta por Roman Bodnarchuk).
  • 1] en [1, 1, 1, 1] no importa en este caso. la lista con el ruido no será tan simple. Las listas contienen tuplas con nombre, por desgracia.

InformationsquelleAutor rich tier | 2012-04-11

6 Comentarios

  1. 39

    Sé que esta pregunta es de 5 meses de edad y ya está «aceptado», pero googleando un problema que me trajo a esta pregunta y todas las respuestas parecen tener un par de problemas importantes, además de que soy aburrido y quiere probar mi mano en una respuesta, así que solo voy a recitar lo que he encontrado.

    La primera parte de la pregunta, como yo lo entiendo, es bastante trivial: acabo de volver de la lista original con todos los elementos, no en el «patrón» filtrados. Después de ese pensamiento, el primer código pensé en utilizar la función filter ():

    def subfinder(mylist, pattern):
        return list(filter(lambda x: x in pattern, mylist))

    Yo diría que esta solución es, definitivamente, más breve que la de la solución original, pero no más rápido, o al menos no de forma apreciable, y trato de evitar las expresiones lambda si no hay una muy buena razón para el uso de ellos. De hecho, la mejor solución que se me ocurrió que participan de una simple lista de comprensión:

    def subfinder(mylist, pattern):
        pattern = set(pattern)
        return [x for x in mylist if x in pattern]

    Esta solución es más elegante y mucho más rápido que el original: la comprensión es de unos 120% más rápido que el original, mientras que el casting de la modelo en un conjunto de primeras protuberancias que hasta la friolera de 320% más rápido en mis pruebas.

    Ahora para el bono: voy a saltar a la derecha en ella, mi solución es la siguiente:

    def subfinder(mylist, pattern):
        matches = []
        for i in range(len(mylist)):
            if mylist[i] == pattern[0] and mylist[i:i+len(pattern)] == pattern:
                matches.append(pattern)
        return matches

    Esta es una variación de Steven Rumbalski la «ineficiente liner», que, con la adición de la «milista[i] == patrón[0]» verificación y gracias a python evaluación de cortocircuito, es significativamente más rápido que el original de la declaración y de la itertools versión (y todos los demás que ofrece la solución a medida de lo que puedo decir) y incluso admite la superposición de patrones. Así que hay que ir.

    • bueno! Me gustaría hacer un for i in xrange( len(milista) – len(patern) +1 ) a pesar de que para evitar innecesarias comparaciones: por ejemplo, si len(milista) fue de 1000, y len(patrón)fue de 50, a continuación, cuando i = 951, a continuación, len(milista[i+len(patrón)]) será de 49 años, y len(patrón) sería de 50 y así no hay manera de que puede ser igualado
    • también, la comprensión de listas gustaría que
    • He encontrado que el segundo ejemplo también se encuentran sub-listas que estaban fuera de orden.
    • Creo que me gustaría devolver una lista de índices en milista en donde los partidos se han encontrado. Devolución de las copias del patrón no es útil, ya que sabemos lo que es el patrón. Buena solución, aunque. Gracias!
    • Tenga en cuenta que este es optimizado para el relativamente corto de los patrones de búsqueda. En el fondo, este tipo de algoritmo debe ser optimizado para limitar las visitas a cada nodo en el área de búsqueda. Como aumentar la longitud (y/o de la repetición) de la cadena de búsqueda, aumentará el número de repetición de visitas a los nodos. Por ejemplo, [1,2,1,2,3] in [1,2,1,2,1,2,3] resultará en 21 visitas, mientras que mi superposición solución sólo 13. Donde el recuento de visita comienza a dar peor perf de las optimizaciones de caer en C es una pregunta abierta, aunque.
    • Oh, también, tenga en cuenta que la lista de rebanar niega el corto-circuito beneficio, ya que rebanar se materializa todo el sector, en memoria, de modo de tener un tiempo mínimo de complejidad de aquí de len_of_search * len_of_target. Usted podría utilizar itertools.islice(), pero luego tendrías que cambiar el == por algo que iba a trabajar con un iterador.

  2. 4

    De esta manera se consigue el «bonus» de parte de tu pregunta:

    pattern = [1, 2, 3, 4]
    search_list = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
    cursor = 0
    found = []
    for i in search_list:
        if i == pattern[cursor]:
            cursor += 1
            if cursor == len(pattern):
                found.append(pattern)
                cursor = 0
        else:
            cursor = 0

    Para los no-bono:

    pattern = [1, 2, 3, 4]
    search_list = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
    cursor = 0
    found = []
    for i in search_list:
        if i != pattern[cursor]:
            if cursor > 0:
                found.append(pattern[:cursor])
            cursor = 0
        else:
            cursor += 1

    Por último, este se encarga de superposiciones:

    def find_matches(pattern_list, search_list):
        cursor_list = []
        found = []
        for element in search_list:
            cursors_to_kill = []
            for cursor_index in range(len(cursor_list)):
                if element == pattern_list[cursor_list[cursor_index]]:
                    cursor_list[cursor_index] += 1
                    if cursor_list[cursor_index] == len(pattern_list):
                        found.append(pattern_list)
                        cursors_to_kill.append(cursor_index)
                else:
                    cursors_to_kill.append(cursor_index)
            cursors_to_kill.reverse()
            for cursor_index in cursors_to_kill:
                cursor_list.pop(cursor_index)
            if element == pattern_list[0]:
                cursor_list.append(1)
        return found
    • Tenga en cuenta que esta solución va a devolver 2, no 3 resultados en la superposición condición mencionada por EOL en los comentarios a la pregunta.
    • no, no estamos anexando en tiempo real, sólo estamos anexando una vez que hemos encontrado un partido completo, por lo que debemos anexar el patrón completo.
    • Mi respuesta llega votada abajo (sin comentarios), mientras que la respuesta que en realidad introduce nuevos errores innecesariamente y jankily la conversión de toda la lista para una cadena obtiene 3 upvotes? Es TAN raro a veces…
    • en efecto, pero se llevaron una gran marca de verificación verde junto a él!
    • No downvote, pero el bono solución podría ser más sencillo simplemente el recuento el número de ocurrencias del patrón. Si es necesario, el resultado puede entonces simplemente ser dado como pattern * n_occurrences.
    • En realidad, para que coincida con OP esperado de la lista de la lista de resultados en sus editado pregunta, se deben anexar. Haciendo la lista de multiplicar devolverá el resultado en su publicación inicial de la pregunta, pero me voy con su aclaración.
    • Esto es realmente una solución imperfecta. Por ejemplo, si usted está buscando para [1, 2, 1, 2, 3] en [1, 2, 1, 2, 1, 2, 3], va a perder el partido. Pero para que no se repitan coincida con los patrones, esta solución funciona bien. Si desea controlar la repetición de que coincida con los patrones, la forma más eficiente de hacerlo consiste en pre-procesamiento de la cadena de búsqueda para la repetición de secciones y ser capaz de tener el bucle de la pista de múltiples y concurrentes de la superposición de la coincidencia de las subsecciones.
    • Hola @SilasRay su bono de solución de rock.
    • ¿puedes explicar un poco más lo que usted hizo en su primer programa, por favor?

  3. 1
    list_with_noise = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
    string_withNoise = "".join(str(i) for i in list_with_noise)
    known_pattern = [1,2,3,4]
    string_pattern = "".join(str(i) for i in known_pattern)
    string_withNoise.count(string_pattern)
    • Mismo como la Romana de la solución, pero un poco menos robusto (solo acepta números de un solo dígito valores).
  4. 0

    Dado:

    a_list = [7,2,1,2,3,4,2,1,2,3,4,9,9,1,2,3,4,7,4,3,1,2,3,5]
    pat = [1,2,3,4]

    Aquí es un ineficiente forro:

    res = [pat for i in range(len(a_list)) if a_list[i:i+len(pat)] == pat]

    Aquí es más eficiente itertools versión:

    from itertools import izip_longest, islice
    
    res = []
    i = 0  
    
    while True:
        try:
            i = a_list.index(pat[0], i)
        except ValueError:
            break
        if all(a==b for (a,b) in izip_longest(pat, islice(a_list, i, i+len(pat)))):
            res.append(pat)
            i += len(pat)
        i += 1
    • Por qué no reemplazar all(a==b…) simplemente por pat == a_list[i:i+len(pat)]? Esto también podría hacer su código más robusto, como la lista de a_list puede contener None elementos que rompería el izip_longest() de la prueba (ya que produce None por falta de elementos).
    • La idea detrás del uso de all es evitar la creación de sublistas. El único riesgo con None es si pat contiene None, en cuyo caso el fillvalue parámetro para izip_longest puede ser utilizado. izip no fue utilizado debido a que para evitar la coincidencia parcial patrón al final de la lista.
  5. 0

    Un idiomáticas, que se puede componer la solución al problema.

    Primero, tenemos que pedir prestado itertools receta, consume (que consume y desecha a un determinado número de elementos de un iterador. Luego tomamos el itertools receta para pairwise, y extenderlo a un nwise función utilizando consume:

    import itertools
    
    def nwise(iterable, size=2):
        its = itertools.tee(iterable, size)
        for i, it in enumerate(its):
            consume(it, i)  # Discards i elements from it
        return zip(*its)

    Ahora que tenemos que, la resolución de la bonificación problema es realmente fácil:

    def find_sublists_in_list(biglist, searchlist):
        searchtup = tuple(searchlist)
        return [list(subtup) for subtup in nwise(biglist, len(searchlist)) if subtup == searchtup]
    
        # Or for more obscure but faster one-liner:
        return map(list, filter(tuple(searchlist).__eq__, nwise(biglist, len(searchlist))))

    Del mismo modo, una más breve y más rápida (aunque algo menos bonita) solución para el problema principal reemplaza:

    def subfinder(mylist, pattern):
        pattern = set(pattern)
        return [x for x in mylist if x in pattern]

    con:

    def subfinder(mylist, pattern):
        # Wrap filter call in list() if on Python 3 and you need a list, not a generator
        return filter(set(pattern).__contains__, mylist)

    Este se comporta de la misma manera, sino que evita la necesidad de almacenar temporalmente los set a un nombre, y empuja todo el filtrado de trabajo para C.

  6. 0

    def sublist_in_list(sub, lis):
    return str(sub).la banda de'[]’) en str(lis).la banda de'[]’)

    • Por favor proporcione una explicación para su respuesta.

Dejar respuesta

Please enter your comment!
Please enter your name here