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

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으로부터 B의 LEGB받는 사람 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의 솔루션의 적응 버전 yield의 tuple의 내가 사용했다 :

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하면 더 빠르지 만 덜 안전한 버전을 얻을 수 있습니다.

---