Slankiojo lango algoritmo vadovas ir kaip jį įdiegti „Go“.

Veiksmų atlikimas su skaičių ir simbolių sekomis yra esminis programavimo aspektas. Stumdomo lango algoritmas yra vienas iš standartinių algoritmų, skirtų tai padaryti.

Tai elegantiškas ir universalus sprendimas, atsidūręs keliose srityse. Šis algoritmas gali atlikti svarbų vaidmenį nuo manipuliavimo eilutėmis iki masyvo perėjimo ir našumo optimizavimo.

Taigi, kaip veikia slankiojančio lango algoritmas ir kaip jį įgyvendinti programoje „Go“?

Slankiojo lango algoritmo supratimas

Yra daug geriausių algoritmų kuriuos naudinga žinoti programuotojui, o stumdomas langas yra vienas iš jų. Šis algoritmas sukasi aplink paprastą koncepciją, kaip išlaikyti dinaminį langą per duomenų seką, kad būtų galima efektyviai apdoroti ir analizuoti tų duomenų pogrupius.

Algoritmą galite taikyti spręsdami skaičiavimo problemas, susijusias su masyvais, eilutėmis arba duomenų sekomis.

Pagrindinė slankiojančio lango algoritmo idėja yra apibrėžti fiksuoto arba kintamo dydžio langą ir perkelti jį į įvesties duomenis. Tai leidžia tyrinėti skirtingus įvesties pogrupius be perteklinių skaičiavimų, kurie gali trukdyti našumui.

Čia yra vaizdinis, kaip tai veikia:

Lango ribos gali būti koreguojamos pagal konkrečios problemos reikalavimus.

Stumdomo lango algoritmo įgyvendinimas programoje Go

Norėdami sužinoti, kaip veikia slankiojo lango algoritmas, galite naudoti populiarią kodavimo problemą: rasti didžiausią tam tikro ilgio pomasyvo sumą.

Šios pavyzdinės problemos tikslas yra rasti dydžio pomasyvį k kurių elementų suma sudaro didžiausią vertę. Sprendimo funkcija apima du parametrus: įvesties masyvą ir teigiamą sveikąjį skaičių k.

Tegul pavyzdinis masyvas yra numeriai, kaip rodo toliau pateiktas kodas:

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

Ir tegul submasyvo ilgis yra k, kurios vertė 3:

k := 3

Tada galite paskelbti funkciją, kad surastumėte didžiausią masyvų, kurių ilgis k, sumą:

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

Galbūt galvojate, kad langas turi būti masyvas, kuriame saugomos tikslinių elementų kopijos. Nors tai yra galimybė, ji veikia prastai.

Vietoj to, jums tereikia apibrėžti lango ribas, kad galėtumėte jį stebėti. Pavyzdžiui, šiuo atveju pirmame lange bus pradžios indeksas 0 ir pabaigos indeksas k-1. Slenkdami langą atnaujinsite šias ribas.

Pirmasis žingsnis siekiant išspręsti šią problemą yra gauti pirmojo k dydžio pomasyvo sumą. Pridėkite šį kodą prie savo funkcijos:

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

Aukščiau pateiktas kodas deklaruoja būtinus algoritmo kintamuosius ir suranda pirmojo masyvo lango sumą. Tada jis inicijuojamas maxSum su pirmojo lango suma.

Kitas žingsnis yra pastumkite langą kartodami per numeriai masyvas iš indekso k iki galo. Kiekviename lango slinkimo etape:

1. Atnaujinti langasSuma pridedant dabartinį elementą ir atimant elementą at langas Pradėti.
2. Atnaujinti maxSum jei nauja vertė langasSuma yra didesnis už jį.

Šis kodas įgyvendina stumdomą langą. Pridėkite jį prie maksimaliSubarraySum funkcija.

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

Kai ciklas bus baigtas, turėsite didžiausią sumą maxSum, kurią galite grąžinti kaip funkcijos rezultatą:

return maxSum

Visa jūsų funkcija turėtų atrodyti taip:

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
}

Galite apibrėžti pagrindinę funkciją, kad patikrintumėte algoritmą, naudodami reikšmes numeriai ir k iš anksčiau:

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

Išvestis šiuo atveju bus 19, kuri yra pomasyvo [4, 8, 7] suma, kuri yra didžiausia.

Dabar galite taikyti tą pačią techniką panašioms problemoms, net ir kitomis kalbomis, pvz., tvarkyti pasikartojančius elementus lange naudodami a Java maišos žemėlapis, pavyzdžiui.

Optimalūs algoritmai užtikrina efektyvias programas

Šis algoritmas yra veiksmingų sprendimų galios įrodymas, kai reikia spręsti problemas. Stumdomas langas padidina našumą ir pašalina nereikalingus skaičiavimus.

Tvirtas supratimas apie slankiojančio lango algoritmą ir jo įgyvendinimą programoje „Go“ leidžia spręsti realaus pasaulio scenarijus kuriant programas.