Python/NumPy Pierwsze wystąpienie podwielokrotności

Question

W języku Python lub NumPy, jaki jest najlepszy sposób na sprawdzenie pierwszego wystąpienia podwielokrotności?

Na przykład, mam

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

Jaki jest najszybszy sposób (run-time-wise), aby dowiedzieć się, gdzie występuje bw? Rozumiem, że dla ciągów jest to bardzo łatwe, ale co z listą lub numpy ndarray?

Wielkie dzięki!

[EDYTOR] Preferuję rozwiązanie numpy, ponieważ z mojego doświadczenia wynika, że ​​wektoryzacja numpy jest znacznie szybsza niż zrozumienie listy Pythona. Tymczasem duży zestaw jest ogromny, więc nie chcę go konwertować na ciąg; to będzie (zbyt) długo.

Answer 1

Zakładam, że szukasz rozwiązania specyficznego dla numpy, a nie prostego rozumienia list lub pętli. Jednym ze sposobów może być użycie techniki rolling window do wyszukania okien o odpowiednim rozmiarze. Oto funkcja 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) 
... 

Następnie można zrobić coś takiego

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

Aby to naprawdę przydatne, trzeba by zmniejszyć go wzdłuż osi 1, stosując all:

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

Następnie możesz użyć tego, ale użyjesz tablicy boolowskiej. Prosty sposób, aby uzyskać indeks out:

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

Na listach można przystosować jedną z tych rolling window iteratory używać podobnego podejścia.

Dla bardzo duże tablice i subarrays, można zaoszczędzić pamięć tak:

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

Z drugiej strony, to prawdopodobnie będzie wolniejszy. Ile wolniej nie jest jasne bez testowania; odpowiedź na Jamie dla innej opcji oszczędzania pamięci, która musi sprawdzić fałszywe alarmy. Wyobrażam sobie, że różnica prędkości pomiędzy tymi dwoma rozwiązaniami będzie zależeć w dużym stopniu od natury danych wejściowych.

Answer 2

Innym spróbować, ale jestem pewien, że jest bardziej pythonic & skuteczny sposób to zrobić ...

 
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 

---

(ta pierwsza odpowiedź nie była w zakresie kwestii, jak cdhowie mentionned)

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

Answer 3

mój pierwszy kiedykolwiek odpowiedzieć, ale myślę, że to powinno działać ....

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

Powoduje zwrócenie indeksu, od którego rozpoczyna się wzorzec.

Answer 4

można wywołać metodę tostring(), aby przekonwertować tablicę na łańcuch, a następnie można użyć szybkiego wyszukiwania ciągów. ta metoda może być szybsza, gdy masz wiele podbarwaczy do sprawdzenia.

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

podejściem splot oparte że powinno być więcej pamięci efektywne niż podejście do stride_tricks oparta:

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] 

z naprawdę dużymi tablicami może nie być możliwe wykorzystanie podejścia stride_tricks, ale ten nadal działa:

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

wiem, że to dość stare pytanie, ale niedawno rozwiązać ten problem w szybki i efektywny sposób i najszybszym sposobem (szczególnie w przypadku długich AR Promienie) znalazłem, myślałem zostawić go tutaj dla odniesienia:

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

Trzeba być ostrożnym, że zarówno macierz i mają taką samą sekwencję dtype.

Answer 7

Oto opcja raczej prosta:

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] 

Następnie przy użyciu oryginalnych A, B wektory otrzymujemy:

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

Answer 8

utworzyć tablicę (lub konwersji), jak to

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