Ръководство за алгортима на плъзгащия се прозорец и как да го внедрите в Go

Извършването на операции върху поредици от числа и знаци е ключов аспект на програмирането. Алгоритъмът за плъзгащ се прозорец е един от стандартните алгоритми за това.

Това е елегантно и универсално решение, което е намерило своето място в множество домейни. От манипулиране на низове до обхождане на масиви и оптимизиране на производителността, този алгоритъм може да играе роля.

И така, как работи алгоритъмът на плъзгащия се прозорец и как можете да го внедрите в Go?

Разбиране на алгоритъма на плъзгащия се прозорец

Има много топ алгоритми които е полезно да знаете като програмист и плъзгащият се прозорец е един от тях. Този алгоритъм се върти около проста концепция за поддържане на динамичен прозорец върху последователност от данни, за ефективна обработка и анализ на подгрупи от тези данни.

Можете да приложите алгоритъма при решаване на изчислителни проблеми, които включват масиви, низове или поредици от данни.

Основната идея зад алгоритъма за плъзгащ се прозорец е да се дефинира прозорец с фиксиран или променлив размер и да се премести през входните данни. Това ви позволява да изследвате различни подмножества на входа без излишни изчисления, които могат да попречат на производителността.

Ето визуално представяне на това как работи:

Границите на прозореца могат да се коригират според изискванията на конкретния проблем.

Внедряване на алгоритъма за плъзгащ се прозорец в Go

Можете да използвате популярен проблем с кодирането, за да научите как работи алгоритъмът на плъзгащия се прозорец: намиране на най-голямата сума от подмасив с дадена дължина.

Целта на този примерен проблем е да се намери подмасивът на размера к чиято сума на елементите е с най-голяма стойност. Функцията за решение приема два параметъра: входния масив и представляващото положително цяло число к.

Нека примерният масив е бройки, както показва кодът по-долу:

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

И нека дължината на подмасива бъде к, със стойност 3:

k := 3

След това можете да декларирате функция за намиране на максималната сума от подмасиви с дължина k:

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

Може би си мислите, че прозорецът трябва да бъде масив, който съхранява копия на целевите елементи. Въпреки че това е опция, тя се представя зле.

Вместо това просто трябва да определите границите на прозореца, за да го следите. Например, в този случай първият прозорец ще има начален индекс от 0 и краен индекс на к-1. В процеса на плъзгане на прозореца ще актуализирате тези граници.

Първата стъпка за решаване на този проблем е да се получи сумата от първия подмасив с размер k. Добавете следния код към вашата функция:

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

Кодът по-горе декларира необходимите променливи за алгоритъма и намира сумата на първия прозорец в масива. След това се инициализира maxSum със сумата на първия прозорец.

Следващата стъпка е да плъзнете прозореца чрез итерация през бройки масив от индекс к до края. Във всяка стъпка на плъзгане на прозореца:

1. Актуализация windowSum чрез добавяне на текущия елемент и изваждане на елемента at windowStart.
2. Актуализация maxSum ако новата стойност на windowSum е по-голямо от него.

Следният код имплементира плъзгащия се прозорец. Добавете го към максимална сума на подмасив функция.

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

Когато цикълът завърши, ще имате най-голямата сума maxSum, който можете да върнете като резултат от функцията:

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], който е най-големият.

Вече можете да приложите същата техника към подобни проблеми, дори и на други езици, като обработка на повтарящи се елементи в прозорец с помощта на Java хеш карта, например.

Оптималните алгоритми водят до ефективни приложения

Този алгоритъм е свидетелство за силата на ефикасните решения, когато става въпрос за решаване на проблеми. Плъзгащият се прозорец увеличава максимално производителността и елиминира ненужните изчисления.

Доброто разбиране на алгоритъма на плъзгащия се прозорец и неговото внедряване в Go ви дава възможност да се справите със сценарии от реалния свят, когато създавате приложения.