Een gids voor het schuifraamalgoritme en hoe u dit in Go kunt implementeren

Het uitvoeren van bewerkingen op reeksen cijfers en tekens is een cruciaal aspect van programmeren. Het schuifvensteralgoritme is een van de standaardalgoritmen om dit te doen.

Het is een elegante en veelzijdige oplossing die zijn weg heeft gevonden naar meerdere domeinen. Van stringmanipulatie tot array-traversals en prestatie-optimalisatie, dit algoritme kan een rol spelen.

Hoe werkt het schuifvensteralgoritme en hoe kun je het in Go implementeren?

Het schuifraamalgoritme begrijpen

Er zijn veel topalgoritmen die handig zijn om te weten als programmeur, en het schuifvenster is daar één van. Dit algoritme draait om een ​​eenvoudig concept van het handhaven van een dynamisch venster over een reeks gegevens, om subsets van die gegevens efficiënt te verwerken en analyseren.

U kunt het algoritme toepassen bij het oplossen van rekenproblemen waarbij arrays, tekenreeksen of gegevensreeksen betrokken zijn.

Het kernidee achter het glijdende vensteralgoritme is om een ​​venster met een vaste of variabele grootte te definiëren en dit door de invoergegevens te verplaatsen. Hierdoor kunt u verschillende subsets van de invoer verkennen zonder overbodige berekeningen die de prestaties kunnen belemmeren.

Hier is een visuele weergave van hoe het werkt:

De grenzen van het venster kunnen worden aangepast aan de vereisten van het specifieke probleem.

Implementatie van het schuifvensteralgoritme in Go

U kunt een populair codeerprobleem gebruiken om te leren hoe het algoritme met een schuifvenster werkt: het vinden van de grootste som van een subarray met een bepaalde lengte.

Het doel van dit voorbeeldprobleem is het vinden van de subarray van grootte k waarvan de elementen samen de grootste waarde vormen. De oplossingsfunctie bevat twee parameters: de invoerarray en een positief geheel getal dat vertegenwoordigt k.

Laat de voorbeeldarray dat zijn num, zoals de onderstaande code laat zien:

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

En laat de lengte van de subarray zo zijn k, met een waarde van 3:

k := 3

Vervolgens kunt u een functie declareren om de maximale som van subarrays met lengte k te vinden:

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

Je denkt misschien dat het venster een array moet zijn waarin kopieën van de doelelementen worden opgeslagen. Hoewel dat een optie is, presteert het slecht.

In plaats daarvan hoeft u alleen maar de grenzen van het venster te definiëren om het bij te houden. In dit geval heeft het eerste venster bijvoorbeeld een startindex van 0 en een eindindex van k-1. Terwijl u het venster verschuift, werkt u deze grenzen bij.

De eerste stap om dit probleem op te lossen is het verkrijgen van de som van de eerste subarray van grootte k. Voeg de volgende code toe aan uw functie:

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

De bovenstaande code declareert de noodzakelijke variabelen voor het algoritme en vindt de som van het eerste venster in de array. Vervolgens wordt het geïnitialiseerd maxSom met de som van het eerste venster.

De volgende stap is om schuif het raam door te herhalen via de num array uit index k naar het einde. Bij elke stap van het verschuiven van het venster:

1. Update vensterSom door het huidige element op te tellen en het element af te trekken vensterStart.
2. Update maxSom als de nieuwe waarde van vensterSom is groter dan dat.

De volgende code implementeert het schuifvenster. Voeg het toe aan de maximumSubarraySom functie.

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

Wanneer de lus is voltooid, heb je het grootste bedrag binnen maxSom, die u kunt retourneren als resultaat van de functie:

return maxSum

Uw volledige functie zou er als volgt uit moeten zien:

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
}

U kunt een hoofdfunctie definiëren om het algoritme te testen, met behulp van de waarden van num En k van vroeger:

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

De uitvoer zal in dit geval zijn 19, wat de som is van de subarray [4, 8, 7], die de grootste is.

U kunt nu dezelfde techniek toepassen op soortgelijke problemen, zelfs in andere talen, zoals het omgaan met herhaalde elementen binnen een venster met behulp van a Java-hashkaart, Bijvoorbeeld.

Optimale algoritmen resulteren in efficiënte toepassingen

Dit algoritme is een bewijs van de kracht van efficiënte oplossingen als het gaat om het oplossen van problemen. Het schuifvenster maximaliseert de prestaties en elimineert onnodige berekeningen.

Een goed begrip van het schuifvensteralgoritme en de implementatie ervan in Go stelt u in staat om realistische scenario's aan te pakken bij het bouwen van applicaties.