Sprievodca algoritmom posuvného okna a ako ho implementovať v Go

Vykonávanie operácií so sekvenciami čísel a znakov je kľúčovým aspektom programovania. Algoritmus posuvného okna je jedným zo štandardných algoritmov na to.

Je to elegantné a všestranné riešenie, ktoré si našlo cestu do viacerých oblastí. Od manipulácie s reťazcami po prechody poľa a optimalizáciu výkonu môže tento algoritmus zohrávať určitú úlohu.

Ako teda funguje algoritmus posuvného okna a ako ho môžete implementovať v Go?

Pochopenie algoritmu posuvného okna

Existujú veľa špičkových algoritmov ktoré je užitočné poznať ako programátor a posuvné okno je jedným z nich. Tento algoritmus sa točí okolo jednoduchej koncepcie udržiavania dynamického okna nad sekvenciou údajov na efektívne spracovanie a analýzu podmnožín týchto údajov.

Algoritmus môžete použiť pri riešení výpočtových problémov, ktoré zahŕňajú polia, reťazce alebo sekvencie údajov.

Hlavnou myšlienkou algoritmu posuvného okna je definovať okno s pevnou alebo premenlivou veľkosťou a presúvať ho cez vstupné dáta. To vám umožní preskúmať rôzne podmnožiny vstupu bez nadbytočných výpočtov, ktoré môžu brániť výkonu.

Tu je vizuálna reprezentácia toho, ako to funguje:

Hranice okna sa môžu prispôsobiť požiadavkám konkrétneho problému.

Implementácia algoritmu posuvného okna v Go

Môžete použiť populárny problém s kódovaním, aby ste sa naučili, ako funguje algoritmus posuvného okna: nájdenie najväčšieho súčtu podpola s danou dĺžkou.

Cieľom tohto vzorového problému je nájsť podpole veľkosti k ktorých súčet prvkov má najväčšiu hodnotu. Funkcia riešenia má dva parametre: vstupné pole a kladné celé číslo predstavujúce k.

Pole vzoriek nech je nums, ako ukazuje kód nižšie:

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

A nech je dĺžka podpolia taká k, s hodnotou 3:

k := 3

Potom môžete deklarovať funkciu na nájdenie maximálneho súčtu podpolí s dĺžkou k:

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

Možno si myslíte, že okno musí byť pole, ktoré ukladá kópie cieľových prvkov. Aj keď je to možnosť, funguje zle.

Namiesto toho stačí definovať hranice okna, aby ste ho mohli sledovať. Napríklad v tomto prípade bude mať prvé okno počiatočný index 0 a koncový index k-1. V procese posúvania okna aktualizujete tieto hranice.

Prvým krokom k vyriešeniu tohto problému je získať súčet prvého podpola veľkosti k. Pridajte do svojej funkcie nasledujúci kód:

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

Vyššie uvedený kód deklaruje potrebné premenné pre algoritmus a nájde súčet prvého okna v poli. Potom sa inicializuje maxSum so súčtom prvého okna.

Ďalším krokom je posuňte okno iteráciou cez nums pole z indexu k do konca. V každom kroku posúvania okna:

1. Aktualizovať windowSum pridaním aktuálneho prvku a odčítaním prvku at windowsStart.
2. Aktualizovať maxSum ak je nová hodnota windowSum je väčšia ako to.

Nasledujúci kód implementuje posuvné okno. Pridajte to do maximumSubarraySum funkciu.

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

Po dokončení cyklu budete mať najväčšiu sumu maxSum, ktorý môžete vrátiť ako výsledok funkcie:

return maxSum

Vaša úplná funkcia by mala vyzerať 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 definovať hlavnú funkciu na testovanie algoritmu pomocou hodnôt nums a k zo skoršieho:

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

Výstupom v tomto prípade bude 19, čo je súčet čiastkového poľa [4, 8, 7], ktoré je najväčšie.

Teraz môžete použiť rovnakú techniku ​​na podobné problémy, dokonca aj v iných jazykoch, ako je manipulácia s opakovanými prvkami v okne pomocou a Java hash mapa, napríklad.

Optimálne algoritmy vedú k efektívnym aplikáciám

Tento algoritmus je dôkazom sily efektívnych riešení, pokiaľ ide o riešenie problémov. Posuvné okno maximalizuje výkon a eliminuje zbytočné výpočty.

Dôkladné pochopenie algoritmu posuvného okna a jeho implementácie v Go vás vybaví na riešenie reálnych scenárov pri vytváraní aplikácií.