Python/NumPy lần xuất hiện đầu tiên của subarray

Question

Trong Python hoặc NumPy, cách tốt nhất để tìm ra sự xuất hiện đầu tiên của một subarray là gì?

Ví dụ, tôi có

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

cách nhanh nhất là gì (run-time-khôn ngoan) để tìm ra nơi mà b xảy ra trong một? Tôi hiểu cho chuỗi này là cực kỳ dễ dàng, nhưng những gì về cho một danh sách hoặc ndarray numpy?

Cảm ơn rất nhiều!

[CHỈNH SỬA] Tôi thích giải pháp gọn gàng hơn, vì từ kinh nghiệm vectơ vất vả của tôi nhanh hơn nhiều so với việc hiểu danh sách Python. Trong khi đó, mảng lớn là rất lớn, vì vậy tôi không muốn chuyển đổi nó thành một chuỗi; đó sẽ là (quá) dài.

Answer 1

Tôi giả sử bạn đang tìm kiếm một giải pháp cụ thể, cụ thể hơn là hiểu danh sách đơn giản hoặc cho vòng lặp. Một cách tiếp cận có thể là sử dụng kỹ thuật rolling window để tìm kiếm các cửa sổ có kích thước phù hợp. Dưới đây là các chức năng 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) 
... 

Sau đó, bạn có thể làm một cái gì đó giống như

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

Để làm điều này thực sự hữu ích, bạn phải giảm nó dọc theo trục 1 sử dụng all:

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

Sau đó, bạn có thể sử dụng tuy nhiên bạn sẽ sử dụng một mảng boolean. Một cách đơn giản để lấy chỉ mục ra:

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

Để biết danh sách, bạn có thể điều chỉnh một trong các phương thức tương tự này.

Đối rất mảng lớn và subarrays, bạn có thể tiết kiệm bộ nhớ như thế này:

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

Mặt khác, điều này có lẽ sẽ chậm hơn. Làm thế nào chậm hơn nhiều là không rõ ràng mà không cần thử nghiệm; xem câu trả lời của Jamie cho một tùy chọn bảo tồn bộ nhớ khác để kiểm tra các kết quả dương tính giả. Tôi tưởng tượng rằng sự khác biệt tốc độ giữa hai giải pháp này sẽ phụ thuộc rất nhiều vào bản chất của đầu vào.

Answer 2

Một cố gắng, nhưng tôi chắc chắn có pythonic hơn & efficent cách để làm điều đó ...

 
def array_match(a, b): 
    for i in xrange(0, len(a)-len(b)+1): 
     if a[i:i+len(b)] == b: 
      return i 
    return None 

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

print array_match(a,b) 
1 

---

(trả lời đầu tiên Đây không phải là trong phạm vi của câu hỏi, như cdhowie được đề cập)

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

Answer 3

Câu trả lời đầu tiên của tôi, nhưng tôi nghĩ rằng điều này sẽ hoạt động ....

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

Trả về chỉ mục mà mẫu bắt đầu.

Answer 4

bạn có thể gọi phương thức tostring() để chuyển đổi mảng thành chuỗi và sau đó bạn có thể sử dụng tìm kiếm chuỗi nhanh. phương pháp này có thể nhanh hơn khi bạn có nhiều subarray để kiểm tra.

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 

Answer 5

Một cách tiếp cận chập dựa, mà nên được nhiều bộ nhớ hiệu quả hơn so với phương pháp stride_tricks dựa trên:

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] 

Với mảng thực sự lớn nó có thể không thể sử dụng một cách tiếp cận stride_tricks, nhưng điều này vẫn hoạt động:

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 

Answer 6

tôi biết điều này là khá một câu hỏi cũ, nhưng gần đây tôi đã phải giải quyết việc này một cách nhanh chóng và hiệu quả và phương pháp nhanh nhất (đặc biệt đối với ar dài tia) Tôi tìm thấy là, tôi nghĩ rằng tôi để nó ở đây để tham khảo:

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

Bạn phải cẩn thận rằng cả hai mảng và chuỗi có cùng một loại.

Answer 7

Dưới đây là một lựa chọn khá thẳng về phía trước:

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] 

Sau đó, sử dụng một, vectơ b ban đầu chúng tôi nhận được:

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

Answer 8

Tạo một mảng (hoặc chuyển đổi) như thế này

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