[python] 롤링 또는 슬라이딩 윈도우 반복자?

시퀀스 / 반복자 / 생성기에서 반복 가능한 롤링 창 (일명 슬라이딩 창)이 필요합니다. 기본 파이썬 반복은 창 길이가 1 인 특별한 경우로 간주 될 수 있습니다. 현재 다음 코드를 사용하고 있습니다. 누구 든지이 작업을 수행하는 데 더 Pythonic, 덜 장황하거나 더 효율적인 방법이 있습니까?

def rolling_window(seq, window_size):
    it = iter(seq)
    win = [it.next() for cnt in xrange(window_size)] # First window
    yield win
    for e in it: # Subsequent windows
        win[:-1] = win[1:]
        win[-1] = e
        yield win

if __name__=="__main__":
    for w in rolling_window(xrange(6), 3):
        print w

"""Example output:

   [0, 1, 2]
   [1, 2, 3]
   [2, 3, 4]
   [3, 4, 5]
"""



답변

itertools들어 이전 버전의 Python 문서에는 하나가 있습니다 .

from itertools import islice

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result
    for elem in it:
        result = result[1:] + (elem,)
        yield result

문서에서 하나는 조금 더 간결하고 itertools내가 상상하는 더 큰 효과를 내기 위해 사용 합니다.


답변

이것은 collections.deque본질적으로 FIFO를 가지고 있기 때문에 맞춤형으로 보입니다 (한 쪽 끝에 추가하고 다른 쪽에서 제거). 그러나 a를 사용하더라도 list두 번 썰지 않아야합니다. 대신 pop(0)목록과 append()새 항목에서 가져와야합니다.

다음은 원본을 기준으로 패턴 화 된 최적화 된 deque 기반 구현입니다.

from collections import deque

def window(seq, n=2):
    it = iter(seq)
    win = deque((next(it, None) for _ in xrange(n)), maxlen=n)
    yield win
    append = win.append
    for e in it:
        append(e)
        yield win

필자의 테스트에서 필자의 tee버전은 큰 iterables와 작은 창을 위해 그것을 능가 하지만 내 테스트에서 대부분의 시간 동안 여기에 게시 된 다른 모든 것을 능가합니다. 큰 창문에서는 deque원래 속도로 다시 당깁니다.

의 개별 항목에 대한 액세스 deque는 목록 또는 튜플보다 빠르거나 느릴 수 있습니다. (음수 색인을 사용하면 시작 부분 근처의 항목이 빠르거나 끝 부분의 항목이 빠릅니다.) 나는 sum(w)루프의 본문에 넣습니다 . 이것은 deque의 강도에 영향을 미칩니다 (한 항목에서 다음 항목으로의 반복이 빠르기 때문에이 루프는 다음으로 빠른 방법 인 필문 처의 것보다 20 % 빠릅니다). 개별적으로 조회하고 10 개의 창에 항목을 추가하도록 변경하면 테이블이 바뀌고 tee방법이 20 % 빨라졌습니다. 또한 마지막 5 개의 용어에 음수 인덱스를 사용하여 약간의 속도를 회복 할 수 있었지만 tee여전히 조금 더 빠릅니다. 전반적으로 나는 어느 쪽이든 대부분의 사용에 대해 매우 빠르며 약간 더 많은 성능이 필요하다면 프로파일 링하고 가장 적합한 것을 선택하십시오.


답변

나는 좋아한다 tee():

from itertools import tee, izip

def window(iterable, size):
    iters = tee(iterable, size)
    for i in xrange(1, size):
        for each in iters[i:]:
            next(each, None)
    return izip(*iters)

for each in window(xrange(6), 3):
    print list(each)

제공합니다 :

[0, 1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]


답변

여기에 대한 지원을 추가 일반화의 step, fillvalue매개 변수 :

from collections import deque
from itertools import islice

def sliding_window(iterable, size=2, step=1, fillvalue=None):
    if size < 0 or step < 1:
        raise ValueError
    it = iter(iterable)
    q = deque(islice(it, size), maxlen=size)
    if not q:
        return  # empty iterable or size == 0
    q.extend(fillvalue for _ in range(size - len(q)))  # pad to size
    while True:
        yield iter(q)  # iter() to avoid accidental outside modifications
        try:
            q.append(next(it))
        except StopIteration: # Python 3.5 pep 479 support
            return
        q.extend(next(it, fillvalue) for _ in range(step - 1))

필요한 경우 각 청크를 채우는 반복마다 size롤링 step위치 에서 청크 항목을 생성 fillvalue합니다. 예 size=4, step=3, fillvalue='*':

 [a b c d]e f g h i j k l m n o p q r s t u v w x y z
  a b c[d e f g]h i j k l m n o p q r s t u v w x y z
  a b c d e f[g h i j]k l m n o p q r s t u v w x y z
  a b c d e f g h i[j k l m]n o p q r s t u v w x y z
  a b c d e f g h i j k l[m n o p]q r s t u v w x y z
  a b c d e f g h i j k l m n o[p q r s]t u v w x y z
  a b c d e f g h i j k l m n o p q r[s t u v]w x y z
  a b c d e f g h i j k l m n o p q r s t u[v w x y]z
  a b c d e f g h i j k l m n o p q r s t u v w x[y z * *]

step매개 변수 사용 사례의 예는 python에서 큰 .txt 파일을 효율적으로 처리를 참조하십시오 .


답변

필요한 것을 정확하게 수행하는 라이브러리가 있습니다.

import more_itertools
list(more_itertools.windowed([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15],n=3, step=3))

Out: [(1, 2, 3), (4, 5, 6), (7, 8, 9), (10, 11, 12), (13, 14, 15)]


답변

빠른 기여.

현재 파이썬 문서에는 itertool 예제 (예 : http://docs.python.org/library/itertools.html 의 맨 아래)에 “창”이 없으므로 다음은 그룹화 코드를 기반으로하는 스 니펫입니다. 주어진 예 중 하나입니다.

import itertools as it
def window(iterable, size):
    shiftedStarts = [it.islice(iterable, s, None) for s in xrange(size)]
    return it.izip(*shiftedStarts)

기본적으로, 우리는 시작 지점이 한 지점 앞으로 이동하는 일련의 슬라이스 반복자를 만듭니다. 그런 다음 함께 묶습니다. 이 함수는 생성기를 반환합니다 (직접 생성기 자체는 아님).

위의 appending-element 및 advancing-iterator 버전과 마찬가지로 성능 (즉, 최고)은 목록 크기와 창 크기에 따라 다릅니다. 나는 이것이 2 라이너이기 때문에 이것을 좋아합니다 (1 라이너 일 수는 있지만 명명 개념을 선호합니다).

위의 코드가 잘못되었습니다 . 매개 변수가 iterable에 전달되면 작동합니다. 가 시퀀스이지만 하지 않습니다. iterator 호출 인 경우 islice 호출간에 동일한 iterator가 공유되지만 (티는 아님) 이로 인해 상황이 나빠집니다.

다음은 일부 고정 코드입니다.

import itertools as it
def window(iterable, size):
    itrs = it.tee(iterable, size)
    shiftedStarts = [it.islice(anItr, s, None) for s, anItr in enumerate(itrs)]
    return it.izip(*shiftedStarts)

또한 책에 대한 버전이 하나 더 있습니다. 반복자를 복사 한 다음 여러 번 복사하는 대신이 버전은 시작 위치를 앞으로 이동함에 따라 각 반복기의 쌍별 사본을 만듭니다. 따라서, 반복자 t는 t에서 시작점을 갖는 “완전한”반복자와 반복자 t + 1의 기초를 제공합니다.

import itertools as it
def window4(iterable, size):
    complete_itr, incomplete_itr = it.tee(iterable, 2)
    iters = [complete_itr]
    for i in xrange(1, size):
        incomplete_itr.next()
        complete_itr, incomplete_itr = it.tee(incomplete_itr, 2)
        iters.append(complete_itr)
    return it.izip(*iters)


답변

itertools레시피 를 결합하는 방법을 보여주기 pairwise위해 window레시피를 사용하여 consume레시피 를 가능한 한 직접 레시피로 다시 확장합니다 .

def consume(iterator, n):
    "Advance the iterator n-steps ahead. If n is none, consume entirely."
    # Use functions that consume iterators at C speed.
    if n is None:
        # feed the entire iterator into a zero-length deque
        collections.deque(iterator, maxlen=0)
    else:
        # advance to the empty slice starting at position n
        next(islice(iterator, n, n), None)

def window(iterable, n=2):
    "s -> (s0, ...,s(n-1)), (s1, ...,sn), (s2, ..., s(n+1)), ..."
    iters = tee(iterable, n)
    # Could use enumerate(islice(iters, 1, None), 1) to avoid consume(it, 0), but that's
    # slower for larger window sizes, while saving only small fixed "noop" cost
    for i, it in enumerate(iters):
        consume(it, i)
    return zip(*iters)

window조리법과 동일 pairwise그것은 단지 두 번째에있는 하나의 요소 “소비”대체 tee점진적에 소비하는 증가에 -ed 반복자를 n - 1반복자. consume각 반복자를 래핑하는 대신 사용 하는 것은 각 윈도우 값을 추출하는 프로세스가 아닌 단계 동안 래핑 오버 헤드 islice만 지불하므로 (반복적으로 큰 반복 가능의 경우) 약간 더 빠릅니다 (따라서 항목 수가 아닌isliceconsumeniterable ).

성능면에서 다른 솔루션과 비교할 때 이것은 상당히 좋습니다 (확장 할 때 테스트 한 다른 솔루션보다 낫습니다). ipython %timeit매직을 사용하여 Python 3.5.0, Linux x86-64에서 테스트되었습니다 .

kindall는의 deque솔루션을 사용하여 성능 / 정확성 불통을 islice대신 집 압연 발전기 표현의와 반복 가능한 창보다 짧은 경우는 결과를 산출하지 않도록 결과 길이를 테스트뿐만 아니라 전달 maxlen의를 deque위치 적으로 대신 키워드 별 (작은 입력의 경우 놀라운 차이를 만듭니다) :

>>> %timeit -r5 deque(windowkindall(range(10), 3), 0)
100000 loops, best of 5: 1.87 μs per loop
>>> %timeit -r5 deque(windowkindall(range(1000), 3), 0)
10000 loops, best of 5: 72.6 μs per loop
>>> %timeit -r5 deque(windowkindall(range(1000), 30), 0)
1000 loops, best of 5: 71.6 μs per loop

이전에 수정 된 kindall 솔루션과 동일하지만 각각이 yield win변경된 것으로 yield tuple(win)생성 된 결과를 저장하면 모든 저장된 결과가 실제로 가장 최근 결과를 보지 않고 (이 시나리오에서는 다른 모든 합리적인 솔루션이 안전함) tuple=tuple함수 정의에 추가 의 사용을 이동 tuple으로부터 BLEGB받는 사람 L:

>>> %timeit -r5 deque(windowkindalltupled(range(10), 3), 0)
100000 loops, best of 5: 3.05 μs per loop
>>> %timeit -r5 deque(windowkindalltupled(range(1000), 3), 0)
10000 loops, best of 5: 207 μs per loop
>>> %timeit -r5 deque(windowkindalltupled(range(1000), 30), 0)
1000 loops, best of 5: 348 μs per loop

consume기반 솔루션 :

>>> %timeit -r5 deque(windowconsume(range(10), 3), 0)
100000 loops, best of 5: 3.92 μs per loop
>>> %timeit -r5 deque(windowconsume(range(1000), 3), 0)
10000 loops, best of 5: 42.8 μs per loop
>>> %timeit -r5 deque(windowconsume(range(1000), 30), 0)
1000 loops, best of 5: 232 μs per loop

동일 consume하지만 런타임을 줄이기 위해 함수 호출 및 테스트 를 피하기위한 인라인 else경우 , 특히 설정 오버 헤드가 작업의 중요한 부분 인 작은 입력의 경우 :consumen is None

>>> %timeit -r5 deque(windowinlineconsume(range(10), 3), 0)
100000 loops, best of 5: 3.57 μs per loop
>>> %timeit -r5 deque(windowinlineconsume(range(1000), 3), 0)
10000 loops, best of 5: 40.9 μs per loop
>>> %timeit -r5 deque(windowinlineconsume(range(1000), 30), 0)
1000 loops, best of 5: 211 μs per loop

(측면 노트 : 중첩 된 객체 를 만들기 위해 기본 인수 2를 반복적으로 pairwise사용 하는 변형입니다 . 따라서 주어진 반복자는 한 번만 진행되고 독립적으로 증가하는 횟수는 소비하지 않습니다. MrDrFenner의 대답 은 인라인이 아닌 것과 유사합니다 모든 테스트 에서 인라인보다 느리 므로 간결하게하기 위해 그 결과를 생략했습니다.)teeteeconsumeconsume

보시다시피 , 발신자가 결과를 저장해야 할 가능성에 대해 신경 쓰지 않는다면, 최적화 된 kindall의 솔루션 버전은 “큰 반복 가능한 작은 창 크기 사례” (인라인 된 consume승자 가 아닌 경우)를 제외하고 대부분의 시간에 승리합니다. ); 반복 가능한 크기가 증가함에 따라 빠르게 저하되는 반면 창 크기가 증가함에 따라 전혀 저하되지 않습니다 (반복 가능한 크기가 증가하면 다른 솔루션은 모두 느리게 저하되지만 창 크기는 증가합니다). 튜플 map(tuple, ...)링 기능보다 약간 느리게 실행 되는을 감싸서 “필요한 튜플”케이스에 맞게 조정할 수도 있지만 사소한 (1-5 % 더 길어짐) 실행 속도를 빠르게 유지할 수 있습니다. 동일한 값을 반복적으로 반환하는 것을 허용 할 수있는 경우

반품 저장에 대해 안전이 필요한 경우, 인라인consume 이 아닌 가장 작은 입력 크기 (인라인 consume이 아닌 것이 약간 느리지 만 비슷한 스케일링)에서 승리합니다 . 그만큼deque및 단지 작은 인해 설치 비용이 최소 입력을위한 기반 솔루션 승 tupling 및 이득이 작다; iterable이 길어질수록 심하게 저하됩니다.

기록 것을 kindall의 솔루션의 적응 버전 yieldtuple의 내가 사용했다 :

def windowkindalltupled(iterable, n=2, tuple=tuple):
    it = iter(iterable)
    win = deque(islice(it, n), n)
    if len(win) < n:
        return
    append = win.append
    yield tuple(win)
    for e in it:
        append(e)
        yield tuple(win)

tuple함수 정의 라인에서 캐싱을 제거 하고 tuple각각 에서 사용 yield하면 더 빠르지 만 덜 안전한 버전을 얻을 수 있습니다.