sliding window
-
tcp dahilinde tanimlanmis flow control seysi. pencere olarak dusundugumuz sey diyelim ki 5 paket alsin..
[1][2][3][4][5] seklinde.. bu veriler karsiya yollanir, diyelim ki 1 ve 2 ulasti, pencere hemen kayar [3][4][5][6][7] ve 6-7 gonderilir. onaylar* gelmedikce ilerlemez bu kara tren.
(bkz: windowing) -
-
bu algoritma genellikle "en *** olan alt dizi"yi bulma mantığında kullanılır. buraya "çarpımları en uzun", "toplamları en fazla", "artarak devam eden en uzun dizi" gibi kavramlar gelebilir, birçoğu için bu algoritmayı kullanabilirsiniz.
örneğin leetcode içerisinde aşağıdaki soru bu algoritma ile kolayca çözülebiliyor. sadece mantığını anlamak yeterli.
https://youtu.be/wjigjs6sl7o
ayrıca bu algoritma ile ilgili şu linklere de göz atabilirsiniz, gayet iyi açıklamışlar;
what is sliding window algorithm? examples?: https://stackoverflow.com/q/8269916/447156
an ıntroduction to sliding window algorithms: https://levelup.gitconnected.com/…thms-5533c4fe1cc7
how to solve sliding window problems: https://medium.com/…ing-window-problems-28d67601a66
sliding window algorithm: https://www.baeldung.com/…/sliding-window-algorithm -
özellikle subarray* problemlerinde time complexity'yi* oldukça iyileştiren bu tekniği 2 adet problem ile anlatmaya çalıştım.
https://youtu.be/bnuzqdmazmy
1. problem: sum of all subarrays of size k
size verilen bir dizide "k" boyutlu tüm subarray'lerin toplamını bir liste olarak geriye döndürmeniz isteniyor.
yani {1, 2, 3, 4, 5, 6} dizisi ve k = 3 için sizden {6, 9, 12, 15} döndürmeniz isteniyor. normalde n dizideki eleman sayısını belirtmek üzere brute force yöntemiyle bu soruyu o(n*k)* zamanda çözebiliyoruz, fakat sliding window tekniği ile pencerede* sadece "değişen" elemanları hesaplayarak o(n) zamanda çözülebiliyor.
2. problem: minimum size subarray sum
bu soruda size verilen bir dizi ve k olmak üzere, dizideki toplamı k'dan büyük veya eşit olan en küçük boyutlu subarray'i bulmanız isteniyor.
yani [2,3,1,2,4,3] dizisi ve k = 7 için geriye [4, 3] dizisinin uzunluğu olan 2'yi döndürmek gerekiyor. bu problemin brute force ile o(n^3) ve o(n^2) gibi çözümleri mevcut. fakat sliding window tekniği ile bir defa iterasyon yaparak o(n) zamanda ilgili window'u genişletme ve daraltma yöntemiyle efektif bir şekilde çözüme ulaşabiliyoruz. -
sliding window algoritmasi ile bir pointer ve window buyuklugu icin bir degisken kullanabiliriz. genellikle pencere icindeki tum elemanlar kullanilir (yukaridaki gibi k window buyuklugu icindeki elemanlarin toplami).
two pointers teknigi ile benzerlikleri cok amma velakin two pointers ile problem cozerken bu iki pointer arasindaki tum elemanlar yerine iki pointerdaki degerleri karsilastiririz, ki bu isaretcileri list vb. gibi yerlerde hizli yavas diye varyasyonlarla kullanabiliriz. -
uçaklarda kokpit yan pencereleri. bir ray üzerinde kayarak açıldıkları için bu isim verilmiş. bazı uçaklarda bulunmaz.
ekşi sözlük kullanıcılarıyla mesajlaşmak ve yazdıkları entry'leri
takip etmek için giriş yapmalısın.
hesabın var mı? giriş yap