Есть ли в numpy метод, который проверяет, содержится ли массив в другом массиве?

Question

Я хочу проверить, является ли массив numpy непрерывной последовательностью в другом массиве.

Например,

a = np.array([1,2,3,4,5,6,7])
b = np.array([3,4,5])
c = np.array([2,3,4,6])

Ожидаемый результат будет:

is_sequence_of(b, a) # should return True
is_sequence_of(c, a) # should return False

Я хочу знать, есть ли какой-нибудь простой метод, который делает это.

Answer 1

Подход № 1

Мы можем использовать один с np.searchsorted -

def isin_seq(a,b):
    # Look for the presence of b in a, while keeping the sequence
    sidx = a.argsort()
    idx = np.searchsorted(a,b,sorter=sidx)
    idx[idx==len(a)] = 0
    ssidx = sidx[idx]
    return (np.diff(ssidx)==1).all() & (a[ssidx]==b).all()

Обратите внимание, что это предполагает, что входные массивы не имеют дубликатов.

Образцы прогонов -

In [42]: isin_seq(a,b) # search for the sequence b in a
Out[42]: True

In [43]: isin_seq(c,b) # search for the sequence b in c
Out[43]: False

Подход № 2

Другой с skimage.util.view_as_windows -

from skimage.util import view_as_windows

def isin_seq_v2(a,b):
    return (view_as_windows(a,len(b))==b).all(1).any()

Подход# 3

Это также можно рассматривать как проблему сопоставления с шаблоном, и поэтому для чисел типа int мы можем использовать встроенную функцию OpenCV для template-matching: cv2.matchTemplate (вдохновлено this post), вот так -

import cv2 
from cv2 import matchTemplate as cv2m

def isin_seq_v3(arr,seq):
    S = cv2m(arr.astype('uint8'),seq.astype('uint8'),cv2.TM_SQDIFF)
    return np.isclose(S,0).any()

Подход № 4

Наши методы могут выиграть с short-circuiting основанныйТаким образом, мы будем использовать один с numba для повышения производительности, вот так -

from numba import njit

@njit
def isin_seq_numba(a,b):
    m = len(a)
    n = len(b)
    for i in range(m-n+1):
        for j in range(n):
            if a[i+j]!=b[j]:
                break                
        if j==n-1:
            return True
    return False