Przewodnik po algorytmie przesuwanego okna i sposobie jego implementacji w Go

Wykonywanie operacji na ciągach liczb i znaków jest kluczowym aspektem programowania. Algorytm przesuwanego okna jest jednym ze standardowych algorytmów służących do tego.

To eleganckie i wszechstronne rozwiązanie, które znalazło zastosowanie w wielu dziedzinach. Od manipulacji ciągami po przechodzenie przez tablice i optymalizację wydajności – algorytm ten może odegrać pewną rolę.

Jak zatem działa algorytm przesuwanego okna i jak można go zaimplementować w Go?

Zrozumienie algorytmu przesuwanego okna

Tam są wiele najlepszych algorytmów które są przydatne dla programisty, a przesuwane okno jest jednym z nich. Algorytm ten opiera się na prostej koncepcji utrzymywania dynamicznego okna na sekwencji danych w celu wydajnego przetwarzania i analizowania podzbiorów tych danych.

Algorytm można zastosować do rozwiązywania problemów obliczeniowych obejmujących tablice, ciągi lub sekwencje danych.

Podstawową ideą algorytmu przesuwającego się okna jest zdefiniowanie okna o stałym lub zmiennym rozmiarze i przesuwanie go poprzez dane wejściowe. Pozwala to eksplorować różne podzbiory danych wejściowych bez zbędnych obliczeń, które mogą zmniejszać wydajność.

Oto wizualna reprezentacja tego, jak to działa:

Granice okna można dostosować do wymagań konkretnego problemu.

Implementacja algorytmu przesuwanego okna w Go

Możesz skorzystać z popularnego problemu z kodowaniem, aby dowiedzieć się, jak działa algorytm przesuwanego okna: znajdowanie największej sumy podtablicy o danej długości.

Celem tego przykładowego problemu jest znalezienie podtablicy rozmiaru k których elementy sumują się do największej wartości. Funkcja rozwiązania przyjmuje dwa parametry: tablicę wejściową i dodatnią liczbę całkowitą reprezentującą k.

Niech przykładowa tablica będzie liczby, jak pokazuje poniższy kod:

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

I niech długość podtablicy będzie wynosić k, o wartości 3:

k := 3

Następnie możesz zadeklarować funkcję, która znajdzie maksymalną sumę podtablic o długości k:

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

Być może myślisz, że okno musi być tablicą przechowującą kopie elementów docelowych. Chociaż jest to opcja, działa ona słabo.

Zamiast tego wystarczy zdefiniować granice okna, aby je śledzić. Na przykład w tym przypadku pierwsze okno będzie miało indeks początkowy równy 0 i indeks końcowy k-1. W trakcie przesuwania okna zaktualizujesz te granice.

Pierwszym krokiem do rozwiązania tego problemu jest uzyskanie sumy pierwszej podtablicy o rozmiarze k. Dodaj następujący kod do swojej funkcji:

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

Powyższy kod deklaruje niezbędne zmienne dla algorytmu i znajduje sumę pierwszego okna w tablicy. Następnie następuje inicjalizacja maxSuma z sumą pierwszego okna.

Następnym krokiem jest przesuń okno iterując po liczby tablica z indeksu k do końca. W każdym kroku przesuwania okna:

1. Aktualizacja oknoSuma dodając bieżący element i odejmując element w oknoStart.
2. Aktualizacja maxSuma jeśli nowa wartość oknoSuma jest od niego większy.

Poniższy kod implementuje przesuwane okno. Dodaj to do maksymalnaPodtablicaSuma funkcjonować.

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

Kiedy pętla się zakończy, otrzymasz największą sumę maxSuma, które możesz zwrócić w wyniku funkcji:

return maxSum

Twoja pełna funkcja powinna wyglądać następująco:

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
}

Można zdefiniować główną funkcję do testowania algorytmu, używając wartości liczby I k z wcześniej:

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

Dane wyjściowe w tym przypadku będą 19, który jest sumą podtablicy [4, 8, 7], która jest największa.

Możesz teraz zastosować tę samą technikę do podobnych problemów, nawet w innych językach, na przykład obsługę powtarzających się elementów w oknie za pomocą a Mapa skrótu Java, Na przykład.

Optymalne algorytmy skutkują wydajnymi aplikacjami

Algorytm ten stanowi świadectwo siły skutecznych rozwiązań w rozwiązywaniu problemów. Przesuwane okno maksymalizuje wydajność i eliminuje niepotrzebne obliczenia.

Solidne zrozumienie algorytmu przesuwającego się okna i jego implementacji w Go pozwala stawić czoła rzeczywistym scenariuszom podczas tworzenia aplikacji.