Sliding window tetap

Soal penghitungan pada subarray berukuran tetap, jumlah maksimum maupun rata-rata bergeser, adalah keluarga soal yang paling wajar diselesaikan dengan pola sliding window. Jendela berukuran $k$ digeser satu indeks pada setiap langkah, dan nilainya dimutakhirkan dari jendela sebelumnya alih-alih dihitung ulang dari nol. Setelah topik ini, perhitungan yang tampaknya menuntut $O(n \cdot k)$ operasi selesai dalam $O(n)$, templat umumnya sudah terbentuk, dan jebakan urutan pemutakhiran jendela sudah dikenali sebelum menimpa.

Jendela yang bergeser, bukan dihitung ulang#

Cara paling langsung menghitung jumlah setiap jendela adalah menjumlahkan ulang $k$ elemen untuk setiap posisi awal. Ada $n - k + 1$ jendela pada data berpanjang $n$, sehingga total operasinya $(n - k + 1) \cdot k$, yang bertumbuh sebagai $O(n \cdot k)$. Pada data ribuan elemen dengan $k$ ratusan, jumlah operasinya menyentuh ratusan ribu, padahal sebagian besar penjumlahan itu menghitung elemen yang sama berulang kali.

Pola sliding window menyingkirkan pengulangan itu dengan memandang jendela sebagai satu kesatuan yang bergeser. Elemen di ujung kiri keluar, elemen baru di kanan masuk, dan sisanya tetap menjadi anggota jendela yang sama. Diagram berikut menangkap satu pergeseran pada jendela berukuran empat.

Keluar-masuk yang hanya menyentuh dua elemen itulah seluruh kunci polanya. Jumlah jendela baru tidak dihitung dari nol, melainkan jumlah lama ditambah nilai masuk dikurangi nilai keluar, satu penambahan dan satu pengurangan per pergeseran. Penghematan itu tidak bergantung pada isi data, karena biaya satu pergeseran selalu dua operasi, berapa pun nilai yang keluar dan masuk.

Satu masuk, satu keluar#

Berkas berikut membandingkan kedua cara pada data yang sama, sepuluh elemen dengan $k = 4$, lengkap dengan penghitung operasi penjumlahan. Pendekatan bersarang menjumlahkan ulang setiap jendela, sedangkan pendekatan jendela membangun jendela pertama sekali lalu memutakhirkannya.

# Jumlah maksimum subarray berukuran k: cara bersarang versus jendela tetap.
# Penghitung operasi membandingkan kerja keduanya pada masukan yang sama.

def jumlah_maks_bersarang(data, k):
    operasi = 0
    terbaik = None
    for mulai in range(len(data) - k + 1):
        jumlah = 0
        for i in range(mulai, mulai + k):
            jumlah += data[i]
            operasi += 1
        if terbaik is None or jumlah > terbaik:
            terbaik = jumlah
    return terbaik, operasi

def jumlah_maks_jendela(data, k):
    operasi = 0
    jumlah = sum(data[:k])   # membangun jendela pertama
    operasi += k
    terbaik = jumlah
    for i in range(k, len(data)):
        jumlah += data[i] - data[i - k]   # satu masuk, satu keluar
        operasi += 2
        if jumlah > terbaik:
            terbaik = jumlah
    return terbaik, operasi

data = [4, 2, 9, 1, 8, 5, 7, 3, 6, 2]
k = 4
hasil_a, ops_a = jumlah_maks_bersarang(data, k)
hasil_b, ops_b = jumlah_maks_jendela(data, k)
print("data :", data)
print("k    :", k)
print("bersarang: jumlah maksimum", hasil_a, "dengan", ops_a, "operasi penjumlahan")
print("jendela  : jumlah maksimum", hasil_b, "dengan", ops_b, "operasi penjumlahan")

data : [4, 2, 9, 1, 8, 5, 7, 3, 6, 2]
k    : 4
bersarang: jumlah maksimum 23 dengan 28 operasi penjumlahan
jendela  : jumlah maksimum 23 dengan 16 operasi penjumlahan

Kedua pendekatan sepakat pada jumlah maksimum 23, tetapi biayanya 28 lawan 16 operasi. Angka 28 berasal dari tujuh jendela kali empat elemen, sedangkan 16 berasal dari empat penjumlahan pembentuk jendela pertama ditambah dua operasi untuk masing-masing enam pergeseran. Penghitung di atas sengaja tidak memasukkan perbandingan pemutakhiran jawaban, dan perbandingan itu berjumlah sama, tujuh kali untuk keduanya, sehingga kesimpulan perbandingannya tidak tergeser. Keunggulan pendekatan jendela juga tidak menuntut syarat apa pun pada data, karena perhitungannya hanya menjumlah dan mengurangi tanpa memandang urutan maupun tanda nilai. Pada masukan yang jauh lebih besar, selisih $(n - k + 1) \cdot k$ lawan $n$ tumbuh dari sedikit menjadi puluhan kali lipat, dan penghitung sederhana inilah yang membuat klaim $O(n \cdot k)$ lawan $O(n)$ berhenti menjadi teori.

Rata-rata bergeser pada catatan suhu#

Aturan satu masuk satu keluar berlaku sama untuk rata-rata, yang perhitungannya hanya berbeda satu pembagian di ujung. Catatan suhu harian berikut memuat sepuluh nilai dengan jendela tiga hari, sehingga keluarannya delapan rata-rata yang masing-masing menyertai satu posisi jendela.

# Rata-rata bergeser dengan jendela tetap pada catatan suhu harian.

def rata_rata_jendela(data, k):
    jumlah = sum(data[:k])          # membangun jendela pertama
    hasil = [jumlah / k]
    for i in range(k, len(data)):
        jumlah += data[i] - data[i - k]   # satu masuk, satu keluar
        hasil.append(jumlah / k)
    return hasil

suhu = [21, 23, 25, 24, 22, 20, 26, 28, 27, 25]
k = 3
hasil = rata_rata_jendela(suhu, k)
print("suhu :", suhu)
print("k    :", k)
for urut, nilai in enumerate(hasil, start=1):
    print(f"jendela {urut}: rata-rata {nilai:.2f}")

suhu : [21, 23, 25, 24, 22, 20, 26, 28, 27, 25]
k    : 3
jendela 1: rata-rata 23.00
jendela 2: rata-rata 24.00
jendela 3: rata-rata 23.67
jendela 4: rata-rata 22.00
jendela 5: rata-rata 22.67
jendela 6: rata-rata 24.67
jendela 7: rata-rata 27.00
jendela 8: rata-rata 26.67

Delapan hasil untuk sepuluh data mengikuti aturan $n - k + 1$, bukan sepuluh, karena jendela tiga hari tidak muat melewati posisi terakhirnya. Angka pada keluaran mudah diperiksa ulang: jendela pertama memuat 21, 23, dan 25 yang rata-ratanya 23,00, sedangkan jendela ketujuh memuat 26, 28, dan 27 dengan rata-rata 27,00 sebagai nilai tertingginya. Bentuk keluaran seperti ini persis yang dibutuhkan laporan bergeser, misalnya catatan suhu tiga hari terakhir yang diperbarui setiap hari. Struktur yang dipelihara hanyalah satu bilangan jumlah, sehingga memori tambahannya konstan tidak peduli berapa panjang catatannya.

Templat umum jendela tetap#

Bentuk semua demo di atas dapat dirangkum menjadi templat tiga langkah: bangun jendela pertama, geser dengan satu masuk dan satu keluar, lalu mutakhirkan jawaban setelah setiap pergeseran tuntas. Templat berikut adalah kerangkanya dalam bahasa Python.

# tidak-dijalankan
jumlah = sum(data[:k])                # bangun jendela pertama
terbaik = jumlah                      # jawaban awal dari jendela pertama
for i in range(k, len(data)):
    jumlah += data[i] - data[i - k]   # geser: satu masuk, satu keluar
    terbaik = max(terbaik, jumlah)    # mutakhirkan jawaban

Dua baris pertama menangani jendela pembuka, sedangkan badan perulangan hanya mengurus pergeseran beserta pemutakhiran jawaban. Variabel terbaik disesuaikan dengan soalnya, rata-rata untuk laporan bergeser, jumlah itu sendiri untuk soal maksimum, atau indeks posisi ketika lokasinya diminta. Yang tidak boleh berubah adalah urutannya, pergeseran tuntas terlebih dahulu, baru jawaban dicatat. Setelah setiap iterasi, variabel jumlah dijamin persis sama dengan jumlah $k$ elemen terakhir yang diperiksa, dan invarian inilah yang membuat jawaban tidak perlu diverifikasi ulang dari nol.

Sebelum templat dijalankan, dua syarat layak diperiksa: $k$ harus positif dan tidak boleh melebihi panjang data, karena sum(data[:k]) tetap menghasilkan angka meskipun jendelanya tidak pernah utuh. Selama kedua syarat itu terpenuhi, akses data[i - k] pada setiap pergeseran selalu sah, karena elemen keluar pasti sudah berada di dalam jendela pembuka. Templat ini juga menjelaskan mengapa polanya cepat ditulis ulang dari nol. Tidak ada struktur data tambahan yang dipelihara, hanya satu penambahan dan satu pengurangan per langkah, sehingga versinya untuk bahasa lain hampir identik.

Kesalahan umum#

Kesalahan yang paling sering pada jendela tetap bukan soal rumus, melainkan urutan pemutakhiran. Pencatatan hasil yang dilakukan di antara penambahan elemen masuk dan pengurangan elemen keluar membiarkan jendela memuat $k + 1$ nilai pada saat hasil direkam. Berkas berikut menjalankan kedua urutan pada data yang sama agar akibatnya terlihat.

# Dua urutan pemutakhiran jendela tetap: satu benar, satu menggeser
# jendela hanya separuh langkah pada saat hasil dicatat.

def rata_rata_setengah_langkah(data, k):
    # keliru: hasil dicatat setelah penambahan tetapi sebelum pengurangan
    jumlah = sum(data[:k])
    hasil = []
    for i in range(k, len(data)):
        jumlah += data[i]
        hasil.append(jumlah / k)     # jendela sedang memuat k + 1 nilai
        jumlah -= data[i - k]
    return hasil

def rata_rata_utuh(data, k):
    # benar: satu pergeseran tuntas (masuk dan keluar) sebelum dicatat
    jumlah = sum(data[:k])
    hasil = [jumlah / k]
    for i in range(k, len(data)):
        jumlah += data[i]
        jumlah -= data[i - k]
        hasil.append(jumlah / k)
    return hasil

data = [5, 10, 15, 20, 25, 30]
k = 3
a = rata_rata_setengah_langkah(data, k)
b = rata_rata_utuh(data, k)
print("setengah langkah:", [f"{v:.2f}" for v in a])
print("utuh            :", [f"{v:.2f}" for v in b])

setengah langkah: ['16.67', '23.33', '30.00']
utuh            : ['10.00', '15.00', '20.00', '25.00']

Versi utuh menghasilkan empat rata-rata yang benar, yaitu 10, 15, 20, dan 25, sedangkan versi setengah langkah menghasilkan tiga nilai yang semuanya terlalu besar. Nilai 16,67 pada catatan pertama adalah jumlah empat elemen 5, 10, 15, dan 20 yang dibagi tiga, bukan jendela yang sah. Kesalahan semacam ini mudah lolos karena kodenya hanya tertukar dua baris.

1. Menghitung ulang jumlah jendela di dalam perulangan. Menulis sum(data[i-k+1:i+1]) pada setiap langkah mengembalikan biaya $O(n \cdot k)$ meskipun bentuknya tetap disebut jendela. Pergeseran wajib berupa satu penambahan dan satu pengurangan.
2. Mengabaikan kasus data lebih pendek dari $k$. Pada data lima elemen dengan $k = 8$, sum(data[:k]) diam-diam menjumlahkan yang tersedia saja dan jawabannya menyesatkan. Periksa panjang data sebelum membangun jendela.
3. Mengira jumlah hasil sebanyak $n$. Jendela berukuran $k$ hanya menghasilkan $n - k + 1$ jawaban, dan perulangan yang menuntut $n$ hasil pasti mengakses indeks di luar batas.
4. Membalik tanda elemen keluar. Penjumlahan yang lupa dikurangi, atau tandanya tertukar, membuat angka jendela membengkak perlahan dan jawaban maksimumnya mengarah ke ujung data tanpa dasar.

Ringkasan#

• Jendela tetap memutakhirkan jumlah dengan satu penambahan dan satu pengurangan per pergeseran, menurunkan biaya dari $(n - k + 1) \cdot k$ menjadi $O(n)$.
• Demo sepuluh elemen dengan $k = 4$ mencatat 28 operasi bersarang lawan 16 operasi jendela pada jawaban maksimum yang sama, yaitu 23.
• Rata-rata bergeser mengikuti templat yang sama dan menghasilkan $n - k + 1$ nilai, delapan untuk sepuluh suhu dengan $k = 3$.
• Pencatatan jawaban wajib menunggu pergeseran tuntas, karena jendela yang direkam di antara keduanya memuat $k + 1$ elemen.

Referensi#

• Built-in Types — Python Software Foundation — dokumentasi pemotongan urutan (slicing) yang dipakai untuk membangun jendela pertama.
• NeetCode Roadmap — NeetCode — peta latihan dengan kategori sliding window yang memuat keluarga soal jendela tetap.