Sliding Window

Kayan Pencere

Okunuşu: slayding vindou

Güncellendi 3 Ekim 20262 dk okuma

Kısaca

Sliding window tekniği, dizi ya da string'in ardışık parçalarıyla ilgili problemleri alt dizileri baştan hesaplamadan, pencereyi kaydırıp güncelleyerek çözer.

Sliding window tekniği nedir?

Ardışık herhangi k sayının en büyük toplamını bulma problemini düşünün. Her grubu ayrı ayrı toplamak O(n·k) tutar. Kayan pencere mevcut k sayının toplamını tutar; bir adım ilerlemek için sağdan giren sayıyı ekler, soldan çıkanı çıkarır. Her öğe bir kez eklenip bir kez çıkarıldığı için bütün tarama O(n)'dir.

Pencereler sabit ya da değişken boyutlu olabilir. Değişken bir pencere sağ kenarını hareket ettirerek büyür, bir koşul bozulduğunda da sol kenarını hareket ettirerek küçülür. Klasik örnek, tekrarlayan karakter içermeyen en uzun alt string'dir: harfler benzersiz olduğu sürece pencereyi genişletin, bir tekrar görüldüğünde de sol kenarı önceki kopyanın ötesine taşıyın; içerideki harfleri bir set ya da map ile izleyin.

Aynı fikir mülakat sorularının dışında da karşımıza çıkar: analitikteki hareketli ortalamalar, son bir dakikadaki istekleri sayan hız sınırlayıcılar, onaylanmamış verinin bir penceresini izleyen TCP gibi ağ protokolleri ve olayları zaman pencereleri üzerinden toplayan akış sistemleri.

Sık yapılan bir yanlış, kayan pencerenin her alt dizi sorusunda işe yaradığını düşünmektir. Ardışık öğeler ve pencere büyüyüp küçüldükçe öngörülebilir şekilde değişen bir koşul gerektirir. Öğe atlayabilen alt dizilerle (subsequence) ilgili problemler ya da küçültmenin güvenilir şekilde işe yaramadığı negatif sayılar içeren pencereler genellikle prefix toplamları ya da dinamik programlama gibi başka teknikler gerektirir.

Önemli noktalar

Kayan pencere, ardışık bir aralığı izler ve adım adım günceller.
Her öğe bir kez girip bir kez çıkar; bu yüzden taramalar O(n)'dir.
Sabit pencereler k boyutunu korur; değişken pencereler bir koşula göre büyüyüp küçülür.
Hız sınırlayıcılar, hareketli ortalamalar ve TCP aynı fikri kullanır.
Ardışık öğeler ve öngörülebilir bir koşul gerektirir.

Örnek

Sabit ve değişken pencereler (Python)python

def max_sum_of_k(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]     # one in on the right, one out on the left
        best = max(best, window)
    return best

def longest_unique_substring(s):
    seen, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1             # shrink past the earlier copy
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(max_sum_of_k([2, 1, 5, 1, 3, 2], 3))      # 9
print(longest_unique_substring("abcabcbb"))     # 3 ("abc")

Sık sorulan sorular

Hangi tür problemler kayan pencere kullanır?

Ardışık alt diziler ya da alt string'lerle ilgili problemler: k öğe üzerinde en büyük ya da en küçük toplamlar, bir koşulu sağlayan en uzun ya da en kısa aralık, aralıklardaki farklı öğeleri saymak ve bir string içinde anagramları bulmak.

Kayan pencerenin zaman karmaşıklığı nedir?

Genellikle O(n), çünkü pencerenin boyutu yol boyunca değişse bile her öğe pencereye bir kez girer ve en fazla bir kez çıkar.

Hız sınırlamada kayan pencere nasıl kullanılır?

Kayan pencereli bir hız sınırlayıcı, istekleri sabit takvim dakikalarında değil, son 60 saniye gibi en yakın zaman aralığında sayar; bu da iki dakika arasındaki sınırdaki ani patlamaları önler.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin