Руководство по алгоритму скользящего окна и его реализации на 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

Код выше объявляет необходимые переменные для алгоритма и находит сумму первого окна в массиве. Затем он инициализирует максимальная сумма с суммой первого окна.

Следующий шаг – сдвинуть окно путем итерации по цифры массив из индекса к к концу. На каждом этапе перемещения окна:

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], который является самым большим.

Теперь вы можете применять ту же технику для решения аналогичных задач даже на других языках, например, для обработки повторяющихся элементов в окне с помощью Хэш-карта Java, например.

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

Этот алгоритм является свидетельством эффективности эффективных решений, когда дело доходит до решения проблем. Скользящее окно максимизирует производительность и исключает ненужные вычисления.

Глубокое понимание алгоритма скользящего окна и его реализации в Go позволит вам решать реальные сценарии при создании приложений.