Последнее обновление 24.09.2023 — Василий Иванов
Выполнение операций над последовательностями чисел и символов является важнейшим аспектом программирования. Алгоритм скользящего окна является одним из стандартных алгоритмов для этого.
Это элегантное и универсальное решение, которое нашло применение во многих областях. Этот алгоритм может сыграть свою роль — от манипуляций со строками до обхода массива и оптимизации производительности.
Итак, как же работает алгоритм скользящего окна и как его можно реализовать в Go?
Понимание алгоритма скользящего окна
Существует множество основных алгоритмов, которые полезно знать программисту, и скользящее окно — один из них. Этот алгоритм основан на простой концепции поддержания динамического окна над последовательностью данных для эффективной обработки и анализа подмножеств этих данных.
Алгоритм можно применять при решении вычислительных задач, включающих массивы, строки или последовательности данных.
Основная идея алгоритма скользящего окна состоит в том, чтобы определить окно фиксированного или переменного размера и перемещать его по входным данным. Это позволяет вам исследовать различные подмножества входных данных без избыточных вычислений, которые могут снизить производительность.
Вот визуальное представление того, как это работает:
Границы окна могут корректироваться в соответствии с требованиями конкретной задачи.
Реализация алгоритма скользящего окна в Go
Вы можете использовать популярную задачу кодирования, чтобы узнать, как работает алгоритм скользящего окна: поиск наибольшей суммы подмассива заданной длины.
Цель этой выборочной задачи — найти подмассив размера k, сумма элементов которого дает наибольшее значение. Функция решения принимает два параметра: входной массив и положительное целое число, представляющее k.
Пусть образец массива будет числами, как показано в коде ниже:
nums := []int{1, 5, 4, 8, 7, 1, 9}
И пусть длина подмассива равна k со значением 3:
k := 3
Затем вы можете объявить функцию для поиска максимальной суммы подмассивов длиной k:
func maximumSubarraySum(nums []int, k int) int {
// body
}
Вы можете подумать, что окно должно представлять собой массив, в котором хранятся копии целевых элементов. Хотя это вариант, он работает плохо.
Вместо этого вам просто нужно определить границы окна, чтобы отслеживать его. Например, в этом случае первое окно будет иметь начальный индекс 0 и конечный индекс k-1. В процессе перемещения окна вы обновите эти границы.
Первый шаг к решению этой проблемы — получить сумму первого подмассива размера k. Добавьте следующий код в вашу функцию:
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0
for i := 0; i < k; i++ {
windowSum += nums[i]
}
maxSum = windowSum
Код выше объявляет необходимые переменные для алгоритма и находит сумму первого окна в массиве. Затем он инициализирует maxSum суммой первого окна.
Следующий шаг — сдвинуть окно, перебирая массив nums от индекса k до конца. На каждом этапе перемещения окна:
- Обновите windowSum, добавив текущий элемент и вычитая элемент в windowStart.
- Обновите maxSum, если новое значение windowSum больше его.
Следующий код реализует скользящее окно. Добавьте его в функцию MaximumSubarraySum.
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
Ваша полная функция должна выглядеть так:
func maximumSubarraySum(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
}
Вы можете определить основную функцию для проверки алгоритма, используя значения nums и k, полученные ранее:
func main() {
nums := []int{1, 5, 4, 8, 7, 1, 9}
k := 3
fmt.Println(maximumSubarraySum(nums, k))
}
Результатом в этом случае будет 19, что является суммой подмассива [4, 8, 7]который является самым большим.
Теперь вы можете применять ту же технику к аналогичным проблемам, даже на других языках, например, к обработке повторяющихся элементов в окне с использованием хэш-карты Java.
Оптимальные алгоритмы приводят к эффективным приложениям
Этот алгоритм является свидетельством эффективности эффективных решений, когда дело доходит до решения проблем. Скользящее окно максимизирует производительность и исключает ненужные вычисления.
Глубокое понимание алгоритма скользящего окна и его реализации в Go позволит вам решать реальные сценарии при создании приложений.
