Sliding Window: Hareketli Aralık Tekniği Nasıl Kullanılır?

Sliding window, bir dizideki bitişik elemanlardan oluşan aralığı her adımda baştan hesaplamak yerine, pencereyi kontrollü biçimde kaydırarak önceki sonuçtan yararlanır. Bu teknik özellikle k uzunluğundaki aralıkların toplamı, ortalaması veya belirli koşulları sağlayan en uzun ya da en kısa bitişik aralığı bulma problemlerinde kullanılır.

Pencere sabitse uzunluğu değişmez; değişkense koşula göre genişler veya daralır. Temel kazanım, bir eleman pencereye girdiğinde ya da çıktığında sonucu yalnızca gerekli değişiklik kadar güncelleyerek tekrar eden işlemleri azaltmaktır.

Sliding Window Nedir ve Hangi Dizi Sorularında Kullanılır?

Sliding window, Türkçede “hareketli aralık” olarak düşünülebilir. Bir takvimde art arda k günü inceleyerek en yüksek toplam çalışma süresini bulduğunuzu düşünün. İlk pencere pazartesi-perşembe arasındaysa, sonraki pencereyi hesaplamak için salı-cuma günlerini baştan toplamanız gerekmez. Pazartesiyi çıkarıp cumayı eklemek yeterlidir.

Aynı düşünce sınav puanları, günlük sıcaklık ölçümleri, satış kayıtları veya sensör verileri gibi dizilerde uygulanabilir. Buradaki kritik nokta, pencerenin genellikle bitişik alt dizi üzerinde hareket etmesidir. Yani elemanlar arasından istediğimiz birkaç değeri rastgele seçmeyiz; aralıktaki sıra korunur.

• Sabit pencere: Pencerenin uzunluğu baştan belirlenir. Örneğin her 3 ardışık sıcaklığın toplamını veya ortalamasını bulmak.
• Değişken pencere: Pencerenin uzunluğu bir koşula göre değişir. Örneğin toplamı belirli bir değeri aşmayan en uzun bitişik aralığı aramak.
• Toplam ve ortalama soruları: k uzunluğundaki aralıkta maksimum, minimum veya ortalama değeri bulmak.
• Koşullu aralık soruları: Belirli toplamı, frekansı veya eleman sayısını sağlayan en uzun ya da en kısa pencereyi bulmak.

Ancak her dizi problemi sliding window için uygun değildir. Elemanların bitişik olması gerekmiyorsa, problem sıralama istiyorsa veya pencereye bir eleman ekleyip çıkarmak sonucu yerel olarak güncellemek için yeterli değilse bu teknik doğrudan uygulanamayabilir.

Sabit Pencereyi Naif Çözümden Daha Verimli Hale Getirme

Örnek problemimiz şu olsun: Günlük sıcaklıkları gösteren bir dizide, art arda k günün en yüksek toplamını bulalım. Naif yöntemde her başlangıç noktası için k elemanı yeniden toplarız. Örneğin pencere 0. indexten başlıyorsa 0, 1 ve 2. elemanlar; bir sonraki adımda 1, 2 ve 3. elemanlar tekrar işlenir. Ortak elemanlar defalarca toplandığı için gereksiz iş oluşur.

Sliding window yaklaşımında önce ilk pencerenin toplamı hesaplanır. Pencere bir adım sağa kayınca soldan çıkan değer çıkarılır, sağdan giren değer eklenir. Böylece toplamı sıfırdan kurmak yerine önceki toplamı güncelleriz.

Her kayışta şu dört soruyu sormak, algoritmayı zihinde takip etmeyi kolaylaştırır: Ne çıktı, ne girdi, sonuç nasıl değişti, en iyi değer güncellendi mi?

def max_window_sum(values, k):
    if not values or k <= 0 or k > len(values):
        return None

    current = sum(values[:k])
    best = current

    for right in range(k, len(values)):
        current += values[right] - values[right - k]
        best = max(best, current)

    return best

print(max_window_sum([4, 7, 2, 9, 5, 1], 3))

Beklenen çıktı 18 olur. Döngüde values[right] pencereye giren, values[right - k] ise çıkan elemandır. Naif yöntemde her pencere için k toplama işlemi yapılırken, sabit sliding window yaklaşımında ilk toplamdan sonra her kayış yalnızca çıkarma ve ekleme işlemleriyle gerçekleştirilir.

Boş dizi, geçersiz veya sıfırdan küçük k ve dizi uzunluğunu aşan pencere için işlem yapılamaz; örnekte bu durumlar None ile ele alınmıştır. Negatif değerler de sabit pencere toplamı için sorun değildir. Tek elemanlı bir dizide ise yalnızca k = 1 geçerli bir pencere oluşturur.

Sliding Window Kod Örneği: En Yüksek k Eleman Toplamı

Sabit pencere tekniğinde amaç, her seferinde yeni bir alt dizinin toplamını baştan hesaplamak yerine önce ilk pencereyi kurmak ve pencere kaydıkça yalnızca çıkan ve giren elemanları güncellemektir. Aşağıdaki örnekte puan listesindeki art arda gelen 3 elemanın en yüksek toplamını buluyoruz.

def en_yuksek_pencere_toplami(dizi, k):
    if not dizi or k <= 0 or k > len(dizi):
        return None

    pencere_toplami = sum(dizi[:k])
    maksimum = pencere_toplami

    for sag in range(k, len(dizi)):
        pencere_toplami += dizi[sag] - dizi[sag - k]
        maksimum = max(maksimum, pencere_toplami)

    return maksimum

puanlar = [4, 7, 2, 9, 5]
print(en_yuksek_pencere_toplami(puanlar, 3))

Beklenen çıktı:

18

Algoritmanın işleyişi şu sırayı izler:

1. Geçersiz k kontrolü: Dizi boşsa, k sıfır veya negatifse ya da k dizi uzunluğundan büyükse anlamlı bir pencere kurulamaz. Bu durumda None döndürülür.
2. İlk pencerenin kurulması: sum(dizi[:k]) ifadesi ilk 3 elemanın toplamını hesaplar: 4 + 7 + 2 = 13.
3. Başlangıç maksimumunun atanması: İlk pencere elimizdeki tek sonuç olduğu için başlangıçta maksimum toplam olarak kabul edilir.
4. Çıkarma ve ekleme: Pencere bir adım sağa kayarken soldan çıkan değer toplamdan çıkarılır, sağdan giren değer eklenir. Böylece tüm pencereyi yeniden toplamaya gerek kalmaz.
5. Karşılaştırma: Her yeni pencere toplamı mevcut maksimumla karşılaştırılır ve büyük olan korunur.

Sonuç olarak en yüksek toplam 18 olur. Öğrenci, aynı listeyi iç içe döngülerle yazılmış naif çözümde her üçlü grubu baştan toplayarak da kontrol edebilir; iki yöntemin sonucu mutlaka eşleşmelidir. Algoritma mantığını farklı soru tipleriyle pekiştirmek için algoritma bilgi testi üzerinde benzer düşünme adımları uygulanabilir.

Değişken Pencere Nasıl Kurulur ve Sınır Durumları Nasıl Yönetilir?

Değişken pencerede pencerenin uzunluğu baştan sabitlenmez. Genellikle iki işaretçi kullanılır: sağ sınır yeni elemanları pencereye dahil eder, sol sınır ise belirlenen koşul bozulduğunda elemanları çıkararak pencereyi küçültür.

Örneğin toplamı belirli bir sınırı aşmayan en uzun bitişik aralık aranıyorsa sağ işaretçi ilerledikçe toplam güncellenir. Toplam sınırı aşarsa sol işaretçi ilerletilir ve soldaki değerler toplamdan çıkarılır. Tekrarlamayan karakterlerden oluşan en uzun alt dizi sorularında ise toplam yerine karakter frekanslarını tutan bir sözlük kullanılır. Böylece pencerenin içinde hangi değerlerin kaç kez bulunduğu izlenebilir.

Ancak negatif değerler içeren dizilerde toplam tabanlı değişken pencere daha dikkatli incelenmelidir. Pozitif değerlerde pencereye eleman eklemek toplamı artırma, eleman çıkarmak azaltma eğilimindedir; negatif değerler bu tek yönlü ilerlemeyi bozabilir. Bu nedenle kullanılan koşulun gerçekten sağ işaretçisi ilerlerken ve sol işaretçisi küçültürken güvenilir biçimde yönetilip yönetilemediği ayrıca kontrol edilmelidir. Bu tür sınırları anlamlandırmak, algoritma odaklı canlı yazılım eğitimi çalışırken özellikle önemlidir.

Sabit pencere örneğindeki girişler için beklenen davranışlar şöyledir:

• Boş dizi: Pencere kurulamayacağı için sonuç olarak None veya önceden belirlenmiş uygun bir hata davranışı kullanılmalıdır.
• k sıfır veya negatifse: Geçerli bir pencere uzunluğu olmadığı için işlem durdurulmalıdır.
• k dizi uzunluğunu aşarsa: İstenen pencere diziye sığmadığından sonuç üretilmemelidir.
• k dizi uzunluğuna eşitse: Yalnızca tek pencere vardır; sonuç tüm dizinin toplamıdır.
• Tek elemanlı dizi: k = 1 ise sonuç o tek elemanın kendisidir.
• Negatif elemanlar: Algoritma çalışmaya devam eder; başlangıç maksimumu sıfır değil, ilk pencerenin gerçek toplamı seçilmelidir.

• Girdi ve k değeri doğrulandı mı?
• İlk pencere doğru kuruldu mu?
• Çıkan ve giren indeksler doğru mu?
• Pencere sınırları dizinin dışına taşıyor mu?
• Başlangıç maksimumu ilk pencerenin toplamından mı alındı?

Doğruluk Kontrolü, Karmaşıklık ve Uygun Olmayan Problem Türleri

Bir sliding window çözümünü doğrulamanın en güvenilir yolu, aynı girdiyi önce naif yöntemle, ardından hareketli pencere yöntemiyle çalıştırıp sonuçları karşılaştırmaktır. Sonuçlar eşleşse bile yalnızca son cevaba bakmak yerine, her kayıştan sonra güncel pencere toplamını incelemek ara adımlardaki hataları yakalamayı kolaylaştırır.

Örneğin [2, 1, 5, 1, 3] dizisinde k = 3 için ilk toplam 8’dir. Pencere bir kez kayınca soldan 2 çıkarılır, sağa 1 eklenir ve toplam 7 olur. Bir sonraki kayışta 1 çıkarılıp 3 eklenir; toplam 9’a ulaşır. Naif yöntemin bulduğu değer de 9 olmalıdır. Bu ara toplamlar beklenenden farklıysa sorun genellikle yanlış elemanı çıkarmaktan veya yeni elemanı yanlış eklemekten kaynaklanır.

Naif yöntemde her pencere baştan sona tekrar toplandığı için zaman karmaşıklığı O(n · k) olur. Sabit sliding window yaklaşımında ise ilk pencere bir kez hesaplanır; sonraki pencerelerde yalnızca çıkan ve giren eleman işlenir. Bu nedenle zaman karmaşıklığı O(n) seviyesine iner. Ek bir dizi, sözlük veya frekans tablosu kullanılmıyorsa alan karmaşıklığı O(1)’dir.

Değişken pencerelerde analiz, sol ve sağ sınırların nasıl ilerlediğine bağlıdır. Her iki sınır dizi üzerinde en fazla birer kez ilerliyorsa temel tarama çoğunlukla O(n) olur. Ancak karakter frekansları veya başka yardımcı yapılar kullanılıyorsa bu yapıların işlem ve alan maliyeti ayrıca değerlendirilmelidir. Konu anlatımı ve uygulamalı pratikle ilerlemek isteyenler canlı sınıflı eğitim seçeneğini inceleyebilir.

Sliding window her dizi problemine uygulanmaz. Sıralı olmayan seçimlerde, bitişik olmayan alt kümelerde veya pencere toplamı tek adımda güvenilir biçimde güncellenemediğinde başka bir yöntem gerekir. Negatif sayılar sabit pencere toplamlarında sorun oluşturmaz; ancak “toplam belirli bir değeri geçince solu ilerlet” gibi değişken pencere koşullarında toplamın artıp azalması mantığı bozabilir. Bu nedenle algoritmayı küçük testlerle karşılaştırarak kontrol etmek ve temel bilgileri genel kodlama bilgisi testi ile ölçmek yararlı bir pratiktir.

Sık Sorulan Sorular

Sliding window ile iki işaretçi tekniği arasındaki fark nedir?

İki işaretçi, dizideki iki konumu takip eden daha genel bir tekniktir. Sliding window ise genellikle bu işaretçileri bitişik bir aralığın sol ve sağ sınırı olarak kullanır. Bu nedenle sliding window, iki işaretçi yaklaşımının belirli problem türlerine uyarlanmış bir biçimi olarak düşünülebilir.

Sliding window her zaman O(n) zaman karmaşıklığı sağlar mı?

Hayır. Sabit pencerede her elemanın pencereye girip çıkması sayesinde çoğunlukla O(n) elde edilir. Ancak her adımda pahalı bir sıralama, tekrar hesaplama veya karmaşık veri yapısı işlemi yapılırsa toplam maliyet O(n)’den büyük olabilir.

Negatif sayılar içeren dizilerde sliding window kullanılabilir mi?

Sabit pencere toplamı için kullanılabilir; negatif değerler yöntemi bozmaz. Değişken pencerede ise koşulun yalnızca toplamın monoton biçimde artacağı varsayımına dayanıp dayanmadığı kontrol edilmelidir. Negatif değerler bu varsayımı geçersiz kılabilir.

Sabit pencere ile değişken pencere arasında nasıl seçim yapılır?

Pencere uzunluğu soruda doğrudan k olarak veriliyorsa sabit pencere kullanılır. “Koşulu sağlayan en uzun veya en kısa bitişik aralık” aranıyorsa pencere sınırları koşula göre değiştiği için değişken pencere daha uygundur.

Bir sliding window çözümünün doğru çalıştığını nasıl test edebilirim?

Tek pencere, birden fazla pencere, negatif değerler, k = n, tek elemanlı dizi ve geçersiz girdilerle test yapın. Aynı sonuçları naif yöntemle karşılaştırın; ayrıca her kayıştan sonra güncel toplamı veya pencere sınırlarını yazdırarak ara durumları inceleyin.

Doğru problem seçimi ve küçük testlerle yapılan kontrol, sliding window tekniğini ezberlenen bir kalıp olmaktan çıkarıp güvenilir bir problem çözme aracına dönüştürür.