[PYTHON] 파이썬 / NumPy 하위 배열의 첫 번째 항목

파이썬 / NumPy 하위 배열의 첫 번째 항목

파이썬이나 NumPy에서 하위 배열의 첫 번째 항목을 찾는 가장 좋은 방법은 무엇입니까?

예를 들어, 나는 가지고있다.

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

어디에서 b가 발생했는지 알아내는 가장 빠른 방법은 (런타임에) 무엇입니까? 나는 문자열을 매우 이해하기 쉽지만리스트 나 numpy ndarray는 어떨까요?

고마워요!

[편집] 저의 경험으로 인해 numpy 벡터화는 파이썬 목록 이해보다 훨씬 빠르기 때문에 나는 numpy 솔루션을 선호합니다. 한편, 큰 배열은 거대하므로 문자열로 변환하고 싶지 않습니다. 그것은 (너무) 오래있을 것입니다.

해결법

1. ==============================

   1.간단한 목록 이해 또는 for 루프가 아닌 numpy 특정 솔루션을 찾고 있다고 가정합니다. 한 가지 방법은 롤링 윈도우 기법을 사용하여 적절한 크기의 윈도우를 검색하는 것입니다. 다음은 rolling_window 함수입니다.

   간단한 목록 이해 또는 for 루프가 아닌 numpy 특정 솔루션을 찾고 있다고 가정합니다. 한 가지 방법은 롤링 윈도우 기법을 사용하여 적절한 크기의 윈도우를 검색하는 것입니다. 다음은 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)
   ... 
   

   그럼 너는 뭔가를 할 수있다.

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

   이 기능을 유용하게 사용하려면 all을 사용하여 1 축을 따라 줄여야합니다.

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

   그렇다면 당신은 부울 배열을 사용할 수 있습니다. 인덱스를 가져 오는 간단한 방법은 다음과 같습니다.

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

   목록의 경우 비슷한 방법을 사용하기 위해 이러한 롤 창 반복자 중 하나를 적용 할 수 있습니다.

   매우 큰 배열과 하위 배열의 경우 다음과 같이 메모리를 절약 할 수 있습니다.

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

   반면에 이것은 아마도 느려질 것입니다. 테스트하지 않고 얼마나 느린지 명확하지 않습니다. 오탐 (false positive)을 확인해야하는 또 다른 메모리 절약 옵션에 대한 Jamie의 대답을 참조하십시오. 이 두 솔루션의 속도 차이는 입력의 성격에 크게 의존 할 것이라고 생각합니다.

2. ==============================

   2.convolution 기반 접근 방식으로 stride_tricks 기반 접근 방식보다 메모리 효율이 높아야합니다.

   convolution 기반 접근 방식으로 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]
   

   정말 큰 배열을 사용하면 stride_tricks 접근법을 사용할 수 없을 수도 있지만이 방법은 여전히 ​​작동합니다.

   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
   

3. ==============================

   3.내 최초의 대답,하지만이게 효과가 있다고 생각합니다 ....

   내 최초의 대답,하지만이게 효과가 있다고 생각합니다 ....

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

   패턴이 시작되는 인덱스를 리턴합니다.

4. ==============================

   4.tostring () 메서드를 호출하여 배열을 문자열로 변환 한 다음 빠른 문자열 검색을 사용할 수 있습니다. 검사 할 하위 배열이 많은 경우이 방법이 더 빠를 수도 있습니다.

   tostring () 메서드를 호출하여 배열을 문자열로 변환 한 다음 빠른 문자열 검색을 사용할 수 있습니다. 검사 할 하위 배열이 많은 경우이 방법이 더 빠를 수도 있습니다.

   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
   

5. ==============================

   5.또 다른 시도지만, 나는 그것을 할 더 파이썬적이고 & 효율적인 방법이 있다고 확신합니다 ...

   또 다른 시도지만, 나는 그것을 할 더 파이썬적이고 & 효율적인 방법이 있다고 확신합니다 ...

   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
   

   (이 첫 번째 대답은 cdhowie가 언급 한 것처럼 질문의 범위에 포함되지 않았습니다)

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

6. ==============================

   6.나는 이것이 꽤 오래된 질문이라는 것을 알고있다. 그러나 나는 최근에 이것을 빠르고 효율적으로 해결해야만했다. 그리고 내가 찾은 가장 빠른 방법 (특히 긴 배열의 경우)은 내가 여기에 참고로 남겨 두었다.

   나는 이것이 꽤 오래된 질문이라는 것을 알고있다. 그러나 나는 최근에 이것을 빠르고 효율적으로 해결해야만했다. 그리고 내가 찾은 가장 빠른 방법 (특히 긴 배열의 경우)은 내가 여기에 참고로 남겨 두었다.

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

   배열과 시퀀스가 ​​모두 동일한 dtype을 갖도록주의해야합니다.

7. ==============================

   7.다음은 다소 단순한 옵션입니다.

   다음은 다소 단순한 옵션입니다.

   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]
   

   그런 다음 원본 a, b 벡터를 사용하여 다음을 얻습니다.

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

8. ==============================

   8.이처럼 배열을 만들거나 변환하십시오.

   이처럼 배열을 만들거나 변환하십시오.

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

from https://stackoverflow.com/questions/7100242/python-numpy-first-occurrence-of-subarray by cc-by-sa and MIT license