Průvodce algoritmem posuvného okna a jak jej implementovat v Go

Provádění operací s posloupnostmi čísel a znaků je zásadním aspektem programování. Algoritmus posuvného okna je jedním ze standardních algoritmů, jak toho dosáhnout.

Je to elegantní a všestranné řešení, které si našlo cestu do mnoha oblastí. Od manipulace s řetězci po procházení polí a optimalizaci výkonu může tento algoritmus hrát roli.

Jak tedy funguje algoritmus posuvného okna a jak jej můžete implementovat v Go?

Pochopení algoritmu posuvného okna

Existují mnoho špičkových algoritmů které je užitečné znát jako programátor a posuvné okno je jedním z nich. Tento algoritmus se točí kolem jednoduchého konceptu udržování dynamického okna nad sekvencí dat pro efektivní zpracování a analýzu podmnožin těchto dat.

Algoritmus můžete použít při řešení výpočetních problémů, které zahrnují pole, řetězce nebo sekvence dat.

Základní myšlenkou algoritmu posuvného okna je definovat okno s pevnou nebo proměnnou velikostí a posouvat jej prostřednictvím vstupních dat. To vám umožní prozkoumat různé podmnožiny vstupu bez nadbytečných výpočtů, které mohou bránit výkonu.

Zde je vizuální znázornění toho, jak to funguje:

Hranice okna se mohou upravit podle požadavků konkrétního problému.

Implementace algoritmu posuvného okna v Go

Chcete-li se naučit, jak funguje algoritmus posuvného okna, můžete použít oblíbený problém s kódováním: nalezení největšího součtu dílčího pole s danou délkou.

Cílem tohoto vzorového problému je najít dílčí pole velikosti k jehož prvky mají největší hodnotu. Funkce řešení má dva parametry: vstupní pole a kladné celé číslo představující k.

Nechte pole vzorků být nums, jak ukazuje kód níže:

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

A nechť je délka dílčího pole k, s hodnotou 3:

k := 3

Poté můžete deklarovat funkci pro nalezení maximálního součtu dílčích polí o délce k:

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

Možná si myslíte, že okno musí být pole, které ukládá kopie cílových prvků. I když je to možnost, funguje špatně.

Místo toho stačí definovat hranice okna, abyste jej mohli sledovat. Například v tomto případě bude mít první okno počáteční index 0 a koncový index k-1. V procesu posouvání okna tyto hranice aktualizujete.

Prvním krokem k vyřešení tohoto problému je získat součet prvního dílčího pole o velikosti k. Přidejte do své funkce následující kód:

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

Výše uvedený kód deklaruje potřebné proměnné pro algoritmus a najde součet prvního okna v poli. Poté se inicializuje maxSum se součtem prvního okna.

Dalším krokem je posuňte okno iterací přes nums pole z indexu k do konce. V každém kroku posuvu okna:

1. Aktualizace windowSum přidáním aktuálního prvku a odečtením prvku at windowsStart.
2. Aktualizace maxSum pokud je nová hodnota windowSum je větší než to.

Následující kód implementuje posuvné okno. Přidejte to do maximumSubarraySum funkce.

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

Když se smyčka dokončí, budete mít největší součet maxSum, kterou můžete vrátit jako výsledek funkce:

return maxSum

Vaše kompletní funkce by měla vypadat takto:

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
}

Můžete definovat hlavní funkci pro testování algoritmu pomocí hodnot nums a k z dřívějška:

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

Výstupem v tomto případě bude 19, což je součet dílčího pole [4, 8, 7], které je největší.

Nyní můžete použít stejnou techniku ​​na podobné problémy, dokonce i v jiných jazycích, jako je manipulace s opakovanými prvky v okně pomocí a Java hash mapa, například.

Optimální algoritmy vedou k efektivním aplikacím

Tento algoritmus je důkazem síly efektivních řešení, pokud jde o řešení problémů. Posuvné okno maximalizuje výkon a eliminuje zbytečné výpočty.

Důkladné porozumění algoritmu posuvného okna a jeho implementace v Go vás vybaví k řešení reálných scénářů při vytváření aplikací.