Bu akıllı algoritma programlarınızı hızlandırabilir ve dizilerle çalışmanıza ilham verebilir.

Sayı ve karakter dizileri üzerinde işlemler gerçekleştirmek programlamanın çok önemli bir yönüdür. Kayan pencere algoritması bunu yapmak için kullanılan standart algoritmalardan biridir.

Birden fazla alanda kendine yer bulmuş zarif ve çok yönlü bir çözümdür. Dizi manipülasyonundan dizi geçişlerine ve performans optimizasyonuna kadar bu algoritma önemli bir rol oynayabilir.

Peki kayan pencere algoritması nasıl çalışır ve bunu Go'da nasıl uygulayabilirsiniz?

Kayan Pencere Algoritmasını Anlamak

Var birçok üst düzey algoritma Bir programcı olarak bunları bilmek faydalıdır ve kayan pencere de bunlardan biridir. Bu algoritma, söz konusu verilerin alt kümelerini verimli bir şekilde işlemek ve analiz etmek için bir veri dizisi üzerinde dinamik bir pencerenin korunmasına ilişkin basit bir konsept etrafında döner.

Dizileri, dizileri veya veri dizilerini içeren hesaplama problemlerini çözerken algoritmayı uygulayabilirsiniz.

instagram viewer

Kayan pencere algoritmasının arkasındaki temel fikir, sabit veya değişken boyutta bir pencere tanımlamak ve onu giriş verileri boyunca taşımaktır. Bu, performansı engelleyebilecek gereksiz hesaplamalar olmadan girdinin farklı alt kümelerini keşfetmenize olanak tanır.

İşte nasıl çalıştığının görsel bir temsili:

Pencerenin sınırları belirli problemin gereksinimlerine göre ayarlanabilir.

Go'da Kayan Pencere Algoritmasının Uygulanması

Kayan pencere algoritmasının nasıl çalıştığını öğrenmek için popüler bir kodlama problemini kullanabilirsiniz: belirli bir uzunluğa sahip bir alt dizinin en büyük toplamını bulma.

Bu örnek problemin amacı boyutun alt dizisini bulmaktır. k unsurları toplamı en büyük değere sahip olan. Çözüm işlevi iki parametre alır: giriş dizisi ve temsil eden pozitif bir tamsayı k.

Örnek dizi olsun sayılar, aşağıdaki kodun gösterdiği gibi:

nums := []int{1, 5, 4, 8, 7, 1, 9}

Ve alt dizi uzunluğunun şöyle olmasına izin verin: k3 değeriyle:

k := 3

Daha sonra k uzunluğundaki alt dizilerin maksimum toplamını bulmak için bir işlev bildirebilirsiniz:

funcmaximumSubarraySum(nums []int, k int)int {
// body
}

Pencerenin, hedef öğelerin kopyalarını saklayan bir dizi olması gerektiğini düşünüyor olabilirsiniz. Bu bir seçenek olsa da, kötü performans gösteriyor.

Bunun yerine, takip edebilmek için pencerenin sınırlarını tanımlamanız yeterlidir. Örneğin, bu durumda, ilk pencerenin başlangıç ​​indeksi şu şekilde olacaktır: 0 ve bir bitiş indeksi k-1. Pencereyi kaydırma sürecinde bu sınırları güncelleyeceksiniz.

Bu problemi çözmenin ilk adımı, k büyüklüğündeki ilk alt dizinin toplamını elde etmektir. Fonksiyonunuza aşağıdaki kodu ekleyin:

var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0
for i := 0; i < k; i++ {
 windowSum += nums[i]
}
maxSum = windowSum

Yukarıdaki kod, algoritma için gerekli değişkenleri bildirir ve dizideki ilk pencerenin toplamını bulur. Daha sonra başlatılır maksimumToplam ilk pencerenin toplamı ile.

Bir sonraki adım ise pencereyi kaydır yineleyerek sayılar dizinden dizi k sonuna kadar. Pencereyi kaydırmanın her adımında:

  1. Güncelleme pencereToplam geçerli öğeyi ekleyerek ve öğeyi çıkararak pencereBaşlat.
  2. Güncelleme maksimumToplam yeni değeri ise pencereToplam ondan daha büyüktür.

Aşağıdaki kod kayan pencereyi uygular. Onu ekle maksimumAltdiziToplamı işlev.

for windowEnd = k; windowEnd < len(nums); windowEnd++ {
 windowSum = windowSum + nums[windowEnd] - nums[windowStart]
if windowSum > maxSum {
 maxSum = windowSum
 }
// slide window forward
 windowStart++
}

Döngü tamamlandığında en büyük toplamı elde edersiniz maksimumToplamişlevin sonucu olarak döndürebileceğiniz:

return maxSum

Tam işleviniz şöyle görünmelidir:

funcmaximumSubarraySum(nums []int, k int)int {
var windowStart, windowEnd, maxSum, windowSum int
 windowStart = 0
for i := 0; i < k; i++ {
 windowSum += nums[i]
 }


 maxSum = windowSum


for windowEnd = k; windowEnd < len(nums); windowEnd++ {
 windowSum = windowSum + nums[windowEnd] - nums[windowStart]


if windowSum > maxSum {
 maxSum = windowSum
 }


// slide window forward
 windowStart++ 
 }
return maxSum
}

Algoritmayı test etmek için değerlerini kullanarak bir ana işlev tanımlayabilirsiniz. sayılar Ve k erkenden:

funcmain() {
 nums := []int{1, 5, 4, 8, 7, 1, 9}
 k := 3
 fmt.Println(maximumSubarraySum(nums, k))
}

Bu durumda çıktı şu şekilde olacaktır: 19, en büyüğü olan alt dizinin [4, 8, 7] toplamıdır.

Artık aynı tekniği, başka dillerde bile benzer problemlere uygulayabilirsiniz; örneğin bir pencerede tekrarlanan öğelerin işlenmesi gibi. Java karma haritası, Örneğin.

Optimal Algoritmalar Verimli Uygulamalarla Sonuçlanır

Bu algoritma, sorun çözme söz konusu olduğunda etkili çözümlerin gücünün bir kanıtıdır. Kayan pencere performansı en üst düzeye çıkarır ve gereksiz hesaplamaları ortadan kaldırır.

Kayan pencere algoritmasının ve Go'daki uygulamasının sağlam bir şekilde anlaşılması, uygulamalar oluştururken gerçek dünya senaryolarıyla başa çıkmanızı sağlar.