Водич за алгоритм клизног прозора и како га имплементирати у Го

Извођење операција над низовима бројева и знакова је кључни аспект програмирања. Алгоритам клизног прозора је један од стандардних алгоритама за то.

То је елегантно и свестрано решење које је нашло свој пут у више домена. Од манипулације стринговима до обиласка низа и оптимизације перформанси, овај алгоритам може играти улогу.

Дакле, како функционише алгоритам клизног прозора и како га можете имплементирати у Го?

Разумевање алгоритма клизног прозора

Постоје много врхунских алгоритама које је корисно знати као програмер, а клизни прозор је један од њих. Овај алгоритам се врти око једноставног концепта одржавања динамичког прозора над низом података, за ефикасну обраду и анализу подскупова тих података.

Алгоритам можете применити када решавате рачунарске проблеме који укључују низове, низове или низове података.

Основна идеја која стоји иза алгоритма клизног прозора је да се дефинише прозор фиксне или променљиве величине и да се помера кроз улазне податке. Ово вам омогућава да истражите различите подскупове улаза без сувишних прорачуна који могу ометати перформансе.

Ево визуелног приказа како то функционише:

Границе прозора могу се прилагодити према захтевима специфичног проблема.

Имплементација алгоритма клизног прозора у Го

Можете користити популарни проблем кодирања да научите како алгоритам клизног прозора функционише: проналажење највећег збира подниза са датом дужином.

Циљ овог проблема узорка је да се пронађе подниз величине к чији се елементи сабирају до највеће вредности. Функција решења узима два параметра: улазни низ и позитиван цео број који представља к.

Нека је низ узорака нумс, као што показује код испод:

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

И нека је дужина подниза к, са вредношћу 3:

k := 3

Затим можете декларисати функцију да пронађете максималан збир поднизова дужине к:

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

Можда мислите да прозор мора бити низ који чува копије циљних елемената. Иако је то опција, делује лоше.

Уместо тога, само треба да дефинишете границе прозора да бисте га пратили. На пример, у овом случају, први прозор ће имати почетни индекс 0 и крајњи индекс к-1. У процесу померања прозора, ажурираћете ове границе.

Први корак за решавање овог проблема је добијање суме првог подниза величине к. Додајте следећи код својој функцији:

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

Код изнад декларише потребне променљиве за алгоритам и проналази збир првог прозора у низу. Затим се иницијализује макСум са збиром првог прозора.

Следећи корак је да помери прозор итерацијом кроз нумс низ из индекса к до краја. У сваком кораку померања прозора:

1. ажурирање виндовСум додавањем тренутног елемента и одузимањем елемента у виндовСтарт.
2. ажурирање макСум ако је нова вредност од виндовСум је већи од њега.

Следећи код имплементира клизни прозор. Додајте га у макимумСубарраиСум функција.

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

Када се петља заврши, имаћете највећу суму макСум, који можете вратити као резултат функције:

return maxSum

Ваша комплетна функција би требало да изгледа овако:

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
}

Можете дефинисати главну функцију за тестирање алгоритма, користећи вредности од нумс и к од раније:

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

Излаз у овом случају ће бити 19, што је збир подниза [4, 8, 7], који је највећи.

Сада можете да примените исту технику на сличне проблеме, чак и на другим језицима, као што је руковање поновљеним елементима унутар прозора помоћу Јава хеш мапа, на пример.

Оптимални алгоритми резултирају ефикасним апликацијама

Овај алгоритам је сведочанство о моћи ефикасних решења када је у питању решавање проблема. Клизни прозор максимизира перформансе и елиминише непотребна израчунавања.

Добро разумевање алгоритма клизног прозора и његове имплементације у Го омогућава вам да се ухватите у коштац са сценаријима из стварног света када правите апликације.