Saya perlu jendela bergulir (alias jendela geser) iterable atas urutan / iterator / generator. Iterasi Python default dapat dianggap sebagai kasus khusus, dengan panjang jendela 1. Saat ini saya menggunakan kode berikut. Adakah yang punya metode yang lebih Pythonic, kurang verbose, atau lebih efisien untuk melakukan ini?

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

Ada satu dalam versi lama dokumen Python dengan itertoolscontoh :

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

Yang dari dokumen sedikit lebih ringkas dan digunakan itertoolsuntuk efek yang lebih besar saya bayangkan.

Ini tampaknya dibuat khusus untuk collections.dequekarena Anda pada dasarnya memiliki FIFO (tambahkan ke satu ujung, hapus dari yang lain). Namun, bahkan jika Anda menggunakan, listAnda tidak harus mengiris dua kali; sebagai gantinya, Anda mungkin harus hanya pop(0)dari daftar dan append()item baru.

Berikut ini adalah implementasi berbasis deque yang dioptimalkan sesuai dengan aslinya:

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

Dalam tes saya itu dengan mudah mengalahkan segala sesuatu yang diposting di sini sebagian besar waktu, meskipun teeversi pembuat pil mengalahkan itu untuk iterables besar dan jendela kecil. Pada jendela yang lebih besar, dequetarikan maju lagi dalam kecepatan mentah.

Akses ke masing-masing item dalam dequemungkin lebih cepat atau lebih lambat daripada dengan daftar atau tupel. (Item di dekat awal lebih cepat, atau item di dekat akhir jika Anda menggunakan indeks negatif.) Saya menaruh a sum(w)di badan loop saya; ini memainkan kekuatan deque (pergantian dari satu item ke item berikutnya cepat, jadi loop ini berjalan 20% lebih cepat dari metode tercepat berikutnya, pembuat pil). Ketika saya mengubahnya secara individual mencari dan menambahkan item dalam jendela sepuluh, tabel berbalik dan teemetode itu 20% lebih cepat. Saya dapat memulihkan beberapa kecepatan dengan menggunakan indeks negatif untuk lima istilah terakhir di samping, tetapi teemasih sedikit lebih cepat. Secara keseluruhan saya akan memperkirakan bahwa salah satu dari mereka banyak cepat untuk sebagian besar kegunaan dan jika Anda memerlukan sedikit lebih banyak kinerja, profil dan pilih salah satu yang terbaik.

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

memberi:

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

Inilah generalisasi yang menambahkan dukungan untuk step, fillvalueparameter:

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

Ini menghasilkan potongan sizeitem pada stepposisi bergulir waktu per iterasi padding setiap potongan dengan fillvaluejika perlu. Contoh untuk 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 * *]

Untuk contoh use case untuk stepparameter, lihat Memproses file .txt besar dengan python secara efisien .

Ada perpustakaan yang melakukan persis apa yang Anda butuhkan:

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

Kontribusi cepat.

Karena python docs saat ini tidak memiliki "jendela" di contoh itertool (yaitu, di bagian bawah http://docs.python.org/library/itertools.html ), inilah cuplikan berdasarkan kode untuk kerapu yang adalah salah satu contoh yang diberikan:

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

Pada dasarnya, kami membuat serangkaian irisan irisan, masing-masing dengan titik awal satu titik lebih jauh ke depan. Lalu, kita kumpulkan bersama-sama. Catatan, fungsi ini mengembalikan generator (bukan langsung generator itu sendiri).

Sama seperti versi append-element dan advance-iterator di atas, kinerja (yang mana yang terbaik) bervariasi dengan ukuran daftar dan ukuran jendela. Saya suka yang ini karena ini adalah dua-liner (bisa jadi satu-liner, tapi saya lebih suka konsep penamaan).

Ternyata kode di atas salah . Ini berfungsi jika parameter yang diteruskan ke iterable adalah urutan tetapi tidak jika itu adalah iterator. Jika itu adalah iterator, iterator yang sama dibagikan (tetapi tidak tee'd) di antara panggilan islice dan ini merusak segalanya.

Berikut ini beberapa kode tetap:

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)

Juga, satu versi lagi untuk buku. Alih-alih menyalin iterator dan kemudian memajukan salinan berkali-kali, versi ini membuat salinan berpasangan dari masing-masing iterator saat kami memindahkan posisi awal ke depan. Jadi, iterator t memberikan iterator "lengkap" dengan titik awal di t dan juga dasar untuk membuat iterator 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)

Hanya untuk menunjukkan bagaimana Anda dapat menggabungkan itertoolsresep , saya memperluas pairwiseresep secara langsung kembali ke windowresep menggunakan consumeresep:

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)

The windowResep adalah sama seperti untuk pairwise, itu hanya menggantikan elemen tunggal "mengkonsumsi" pada kedua teeiterator -ed dengan semakin meningkatnya mengkonsumsi pada n - 1iterator. Menggunakan consumealih-alih membungkus setiap iterator islicesedikit lebih cepat (untuk iterables cukup besar) karena Anda hanya membayar isliceoverhead pembungkus selama consumefase, tidak selama proses mengekstraksi setiap nilai jendela-ed (jadi itu dibatasi oleh n, bukan jumlah item dalam iterable).

Kinerja-bijaksana, dibandingkan dengan beberapa solusi lain, ini cukup bagus (dan lebih baik daripada solusi lain yang saya uji karena skala). Diuji pada Python 3.5.0, Linux x86-64, menggunakan ipython %timeitsihir.

kindall adalah dequesolusi , tweak untuk kinerja / kebenaran dengan menggunakan islicebukannya ekspresi pembangkit rumah linting dan pengujian panjang yang dihasilkan sehingga tidak menghasilkan hasil yang ketika iterable lebih pendek dari jendela, serta melewati maxlendari dequesecara posisi bukannya menurut kata kunci (membuat perbedaan mengejutkan untuk input yang lebih kecil):

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

Sama seperti solusi kindall yang diadaptasi sebelumnya, tetapi dengan masing-masing yield windiubah untuk yield tuple(win)menyimpan hasil dari generator bekerja tanpa semua hasil yang disimpan benar-benar menjadi pandangan dari hasil terbaru (semua solusi masuk akal lainnya aman dalam skenario ini), dan menambah tuple=tupledefinisi fungsi untuk memindahkan penggunaan tupledari Bdalam LEGBke 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

consumesolusi berbasis-ditunjukkan di atas:

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

Sama seperti consume, tetapi sebaris elsekasus consumeuntuk menghindari pemanggilan fungsi dan n is Nonepengujian untuk mengurangi runtime, khususnya untuk input kecil di mana overhead pengaturan adalah bagian yang berarti dari pekerjaan:

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

(Catatan-samping: Varian pada pairwiseyang menggunakan teeargumen default 2 berulang kali untuk membuat teeobjek bersarang , sehingga setiap iterator yang diberikan hanya maju sekali, tidak dikonsumsi secara mandiri dalam peningkatan jumlah kali, mirip dengan jawaban MrDrFenner mirip dengan non-inline consumedan lebih lambat dari yang diuraikan consumepada semua tes, jadi saya telah menghilangkan hasil tersebut untuk singkatnya).

Seperti yang dapat Anda lihat, jika Anda tidak peduli tentang kemungkinan penelepon perlu menyimpan hasil, versi saya yang dioptimalkan dari solusi kindall memenangkan sebagian besar waktu, kecuali dalam "case iterable besar, case ukuran jendela kecil" (di mana yang disebutkan consumemenang ); itu terdegradasi dengan cepat seiring dengan meningkatnya ukuran iterable, sementara tidak menurunkan sama sekali dengan meningkatnya ukuran window (setiap solusi lain terdegradasi lebih lambat untuk peningkatan ukuran iterable, tetapi juga menurunkan untuk ukuran window meningkat). Ia bahkan dapat diadaptasi untuk case "need tuple" dengan membungkusnya map(tuple, ...), yang bekerja sedikit lebih lambat daripada menempatkan tupling pada fungsi, tetapi ini sepele (membutuhkan 1-5% lebih lama) dan memungkinkan Anda menjaga fleksibilitas berjalan lebih cepat ketika Anda bisa mentolerir berulang kali mengembalikan nilai yang sama.

Jika Anda membutuhkan keamanan terhadap pengembalian yang disimpan, inline consumemenang pada semua tetapi ukuran input terkecil (dengan non-inline consumemenjadi sedikit lebih lambat tetapi scaling sama). Solusi deque& tupling berbasis menang hanya untuk input terkecil, karena biaya setup lebih kecil, dan keuntungannya kecil; itu rusak parah karena iterable semakin lama.

Sebagai catatan, versi disesuaikan dari solusi kindall yang yields tuples saya digunakan adalah:

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)

Jatuhkan caching tuplepada baris definisi fungsi dan gunakan tuplemasing yield- masing untuk mendapatkan versi yang lebih cepat namun kurang aman.

Saya menggunakan kode berikut sebagai jendela geser sederhana yang menggunakan generator untuk secara drastis meningkatkan keterbacaan. Kecepatannya sejauh ini sudah cukup untuk digunakan dalam analisis urutan bioinformatika dalam pengalaman saya.

Saya memasukkannya di sini karena saya belum melihat metode ini digunakan. Sekali lagi, saya tidak membuat klaim tentang kinerja yang dibandingkan.

def slidingWindow(sequence,winSize,step=1):
"""Returns a generator that will iterate through
the defined chunks of input sequence. Input sequence
must be sliceable."""

    # Verify the inputs
    if not ((type(winSize) == type(0)) and (type(step) == type(0))):
        raise Exception("**ERROR** type(winSize) and type(step) must be int.")
    if step > winSize:
        raise Exception("**ERROR** step must not be larger than winSize.")
    if winSize > len(sequence):
        raise Exception("**ERROR** winSize must not be larger than sequence length.")

    # Pre-compute number of chunks to emit
    numOfChunks = ((len(sequence)-winSize)/step)+1

    # Do the work
    for i in range(0,numOfChunks*step,step):
        yield sequence[i:i+winSize]

def GetShiftingWindows(thelist, size):
    return [ thelist[x:x+size] for x in range( len(thelist) - size + 1 ) ]

>> a = [1, 2, 3, 4, 5]
>> GetShiftingWindows(a, 3)
[ [1, 2, 3], [2, 3, 4], [3, 4, 5] ]

versi yang sedikit dimodifikasi dari jendela deque, untuk menjadikannya jendela bergulir yang sebenarnya. Sehingga mulai diisi hanya dengan satu elemen, lalu tumbuh hingga ukuran jendela maksimumnya, dan kemudian menyusut saat tepi kiri mendekati akhir:

from collections import deque
def window(seq, n=2):
    it = iter(seq)
    win = deque((next(it, None) for _ in xrange(1)), maxlen=n)
    yield win
    append = win.append
    for e in it:
        append(e)
        yield win
    for _ in xrange(len(win)-1):
        win.popleft()
        yield win

for wnd in window(range(5), n=3):
    print(list(wnd))

ini memberi

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

def rolling_window(list, degree):
    for i in range(len(list)-degree+1):
        yield [list[i+o] for o in range(degree)]

Dibuat ini untuk fungsi rata-rata bergulir

kenapa tidak

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

Itu didokumentasikan dalam Python doc . Anda dapat dengan mudah memperluasnya ke jendela yang lebih luas.

Beberapa iterator!

def window(seq, size, step=1):
    # initialize iterators
    iters = [iter(seq) for i in range(size)]
    # stagger iterators (without yielding)
    [next(iters[i]) for j in range(size) for i in range(-1, -j-1, -1)]
    while(True):
        yield [next(i) for i in iters]
        # next line does nothing for step = 1 (skips iterations for step > 1)
        [next(i) for i in iters for j in range(step-1)]

next(it)memunculkan StopIterationketika urutan selesai, dan untuk beberapa alasan keren itu di luar saya, pernyataan hasil di sini kecuali itu dan fungsi kembali, mengabaikan nilai sisa yang tidak membentuk jendela penuh.

Pokoknya, ini adalah solusi paling tidak namun yang satu-satunya persyaratan adalah bahwa seqmenerapkan salah satu __iter__atau __getitem__tidak dan tidak bergantung pada itertoolsatau collectionsselain solusi @ dansalmo :)

Mari kita membuatnya malas!

from itertools import islice, tee

def window(iterable, size): 
    iterators = tee(iterable, size) 
    iterators = [islice(iterator, i, None) for i, iterator in enumerate(iterators)]  
    yield from zip(*iterators)

list(window(range(5), 3))
# [(0, 1, 2), (1, 2, 3), (2, 3, 4)]

#Importing the numpy library
import numpy as np
arr = np.arange(6) #Sequence
window_size = 3
np.lib.stride_tricks.as_strided(arr, shape= (len(arr) - window_size +1, window_size), 
strides = arr.strides*2)

"""Example output:

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

"" "

Saya menguji beberapa solusi dan satu yang saya buat dan menemukan yang saya buat menjadi yang tercepat, jadi saya pikir saya akan membagikannya.

import itertools
import sys

def windowed(l, stride):
    return zip(*[itertools.islice(l, i, sys.maxsize) for i in range(stride)])

>>> n, m = 6, 3
>>> k = n - m+1
>>> print ('{}\n'*(k)).format(*[range(i, i+m) for i in xrange(k)])
[0, 1, 2]
[1, 2, 3]
[2, 3, 4]
[3, 4, 5]

Bagaimana menggunakan yang berikut ini:

mylist = [1, 2, 3, 4, 5, 6, 7]

def sliding_window(l, window_size=2):
    if window_size > len(l):
        raise ValueError("Window size must be smaller or equal to the number of elements in the list.")

    t = []
    for i in xrange(0, window_size):
        t.append(l[i:])

    return zip(*t)

print sliding_window(mylist, 3)

Keluaran:

[(1, 2, 3), (2, 3, 4), (3, 4, 5), (4, 5, 6), (5, 6, 7)]

Ini adalah pertanyaan lama tetapi bagi mereka yang masih tertarik ada implementasi yang bagus dari slider jendela menggunakan generator dalam hal ini halaman (oleh Adrian Rosebrock).

Ini adalah implementasi untuk OpenCV namun Anda dapat dengan mudah menggunakannya untuk tujuan lain. Untuk yang bersemangat saya akan menempelkan kode di sini tetapi untuk memahaminya lebih baik saya sarankan mengunjungi halaman asli.

def sliding_window(image, stepSize, windowSize):
    # slide a window across the image
    for y in xrange(0, image.shape[0], stepSize):
        for x in xrange(0, image.shape[1], stepSize):
            # yield the current window
            yield (x, y, image[y:y + windowSize[1], x:x + windowSize[0]])

Tip: Anda dapat memeriksa.shape jendela saat iterasi generator untuk membuang yang tidak memenuhi persyaratan Anda

Bersulang

Jawaban DiPaolo yang dimodifikasi untuk memungkinkan pengisian acak dan ukuran langkah variabel

import itertools
def window(seq, n=2,step=1,fill=None,keep=0):
    "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(itertools.islice(it, n))    
    if len(result) == n:
        yield result
    while True:        
#         for elem in it:        
        elem = tuple( next(it, fill) for _ in range(step))
        result = result[step:] + elem        
        if elem[-1] is fill:
            if keep:
                yield result
            break
        yield result

di sini adalah satu liner. Saya menghitung waktunya dan itu kompatibel dengan kinerja jawaban atas dan semakin progresif dengan seq lebih besar dari 20% lebih lambat dengan len (seq) = 20 dan 7% lebih lambat dengan len (seq) = 10000

zip(*[seq[i:(len(seq) - n - 1 + i)] for i in range(n)])

Mencoba bagian saya, sederhana, satu liner, cara pythonic menggunakan islice. Tapi, mungkin tidak efisien secara optimal.

from itertools import islice
array = range(0, 10)
window_size = 4
map(lambda i: list(islice(array, i, i + window_size)), range(0, len(array) - window_size + 1))
# output = [[0, 1, 2, 3], [1, 2, 3, 4], [2, 3, 4, 5], [3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8], [6, 7, 8, 9]]

Penjelasan: Buat jendela dengan menggunakan islice dari window_size dan ulangi operasi ini menggunakan peta di atas semua larik.

Fungsi yang Dioptimalkan untuk menggeser data jendela dalam pembelajaran yang mendalam

def SlidingWindow(X, window_length, stride):
    indexer = np.arange(window_length)[None, :] + stride*np.arange(int(len(X)/stride)-window_length+4)[:, None]
    return X.take(indexer)