Python / NumPy primera aparición de subarray

En Python o NumPy, ¿cuál es la mejor manera de descubrir la primera aparición de un subarreglo?

Por ejemplo, tengo

a = [1, 2, 3, 4, 5, 6] b = [2, 3, 4] 

¿Cuál es la forma más rápida (en tiempo de ejecución) para averiguar dónde ocurre b en un? Entiendo que para las cadenas esto es extremadamente fácil, pero ¿qué hay de una lista o una ndarray numpy?

¡Muchas gracias!

[EDITADO] Prefiero la solución numpy, ya que, según mi experiencia, la vectorización numpy es mucho más rápida que la comprensión de la lista de Python. Mientras tanto, la gran variedad es enorme, así que no quiero convertirla en una cadena; eso será (demasiado) largo.

Supongo que está buscando una solución específica para muchos, en lugar de una simple lista de comprensión o bucle. Un enfoque podría ser utilizar la técnica de la ventana móvil para buscar ventanas del tamaño apropiado. Aquí está la función rolling_window:

 >>> def rolling_window(a, size): ... shape = a.shape[:-1] + (a.shape[-1] - size + 1, size) ... strides = a.strides + (a. strides[-1],) ... return numpy.lib.stride_tricks.as_strided(a, shape=shape, strides=strides) ... 

Entonces podrías hacer algo como

 >>> a = numpy.arange(10) >>> numpy.random.shuffle(a) >>> a array([7, 3, 6, 8, 4, 0, 9, 2, 1, 5]) >>> rolling_window(a, 3) == [8, 4, 0] array([[False, False, False], [False, False, False], [False, False, False], [ True, True, True], [False, False, False], [False, False, False], [False, False, False], [False, False, False]], dtype=bool) 

Para que esto sea realmente útil, tendría que reducirlo a lo largo del eje 1 utilizando all :

 >>> numpy.all(rolling_window(a, 3) == [8, 4, 0], axis=1) array([False, False, False, True, False, False, False, False], dtype=bool) 

Entonces podrías usar eso, pero usarías una matriz booleana. Una forma sencilla de sacar el índice:

 >>> bool_indices = numpy.all(rolling_window(a, 3) == [8, 4, 0], axis=1) >>> numpy.mgrid[0:len(bool_indices)][bool_indices] array([3]) 

Para las listas, podría adaptar uno de estos iteradores de ventana rodante para utilizar un enfoque similar.

Para arrays y subarreglos muy grandes, podría ahorrar memoria como esta:

 >>> windows = rolling_window(a, 3) >>> sub = [8, 4, 0] >>> hits = numpy.ones((len(a) - len(sub) + 1,), dtype=bool) >>> for i, x in enumerate(sub): ... hits &= numpy.in1d(windows[:,i], [x]) ... >>> hits array([False, False, False, True, False, False, False, False], dtype=bool) >>> hits.nonzero() (array([3]),) 

Por otro lado, esto probablemente será más lento. Cuánto más lento no está claro sin pruebas; vea la respuesta de Jamie para otra opción de conservación de memoria que tiene que verificar falsos positivos. Me imagino que la diferencia de velocidad entre estas dos soluciones dependerá en gran medida de la naturaleza de la entrada.

Un enfoque basado en convolución, que debería ser más eficiente en memoria que el stride_tricks basado en stride_tricks :

 def find_subsequence(seq, subseq): target = np.dot(subseq, subseq) candidates = np.where(np.correlate(seq, subseq, mode='valid') == target)[0] # some of the candidates entries may be false positives, double check check = candidates[:, np.newaxis] + np.arange(len(subseq)) mask = np.all((np.take(seq, check) == subseq), axis=-1) return candidates[mask] 

Con matrices realmente grandes, puede que no sea posible utilizar un enfoque stride_tricks , pero este todavía funciona:

 haystack = np.random.randint(1000, size=(1e6)) needle = np.random.randint(1000, size=(100,)) # Hide 10 needles in the haystack place = np.random.randint(1e6 - 100 + 1, size=10) for idx in place: haystack[idx:idx+100] = needle In [3]: find_subsequence(haystack, needle) Out[3]: array([253824, 321497, 414169, 456777, 635055, 879149, 884282, 954848, 961100, 973481], dtype=int64) In [4]: np.all(np.sort(place) == find_subsequence(haystack, needle)) Out[4]: True In [5]: %timeit find_subsequence(haystack, needle) 10 loops, best of 3: 79.2 ms per loop 

Mi primera respuesta, pero creo que esto debería funcionar …

 [x for x in xrange(len(a)) if a[x:x+len(b)] == b] 

Devuelve el índice en el que comienza el patrón.

puede llamar al método tostring () para convertir una matriz en una cadena, y luego puede usar la búsqueda rápida de cadenas. este método puede ser más rápido cuando tienes muchos subarray para verificar.

 import numpy as np a = np.array([1,2,3,4,5,6]) b = np.array([2,3,4]) print a.tostring().index(b.tostring())//a.itemsize 

Otro bash, pero estoy seguro de que hay una manera más eficiente y más pythonica de hacer eso …

 def array_match (a, b):
     para i en xrange (0, len (a) -len (b) +1):
         si a [i: i + len (b)] == b:
             volver i
     regresar ninguno
 a = [1, 2, 3, 4, 5, 6]
 b = [2, 3, 4]

 imprimir array_match (a, b)
 1

(Esta primera respuesta no estaba en el scope de la pregunta, como se mencionó en el manual)

 set(a) & set(b) == set(b) 

Sé que esta es una pregunta bastante antigua, pero recientemente tuve que resolver esto de manera rápida y eficiente, y el método más rápido (especialmente para arreglos largos) que encontré fue que pensé que lo dejo aquí como referencia:

 data = np.array([1, 2, 3, 4, 5, 6]) sequence = np.array([3, 4, 5]) data.tostring().index(sequence.tostring())//data.itemize 

Debes tener cuidado de que tanto la matriz como la secuencia tengan el mismo tipo de letra.

Aquí hay una opción bastante sencilla:

 def first_subarray(full_array, sub_array): n = len(full_array) k = len(sub_array) matches = np.argwhere([np.all(full_array[start_ix:start_ix+k] == sub_array) for start_ix in range(0, n-k+1)]) return matches[0] 

Luego, utilizando los vectores a, b originales obtenemos:

 a = [1, 2, 3, 4, 5, 6] b = [2, 3, 4] first_subarray(a, b) Out[44]: array([1], dtype=int64) 

Crear una matriz (o convertir) como esta

 >>> ar = numpy.array([1,2,3,4,5,1,2,8,9,1,2,3,4,6], dtype=str) >>> ar.tostring() '12345128912346' >>> ss.count('123') 2 >>> ss.index('123') 0