Opas liukuikkuna-algoritmiin ja sen käyttöönottoon Go-tilassa

Toimintojen suorittaminen numero- ja merkkijonoille on ohjelmoinnin keskeinen osa. Liukuikkuna-algoritmi on yksi vakioalgoritmeista sen tekemiseen.

Se on tyylikäs ja monipuolinen ratkaisu, joka on löytänyt tiensä useille toimialueille. Tämä algoritmi voi olla osansa merkkijonojen käsittelystä taulukon läpikäymiseen ja suorituskyvyn optimointiin.

Joten miten liukuva ikkuna-algoritmi toimii ja kuinka voit toteuttaa sen Gossa?

Liukuvan ikkunan algoritmin ymmärtäminen

On monia huippualgoritmeja jotka on hyödyllistä tietää ohjelmoijana, ja liukuva ikkuna on yksi niistä. Tämä algoritmi pyörii yksinkertaisen konseptin ympärillä ylläpitää dynaamista ikkunaa datasarjan yli, jotta datan osajoukkoja voidaan käsitellä ja analysoida tehokkaasti.

Voit käyttää algoritmia, kun ratkaiset laskennallisia ongelmia, jotka sisältävät taulukoita, merkkijonoja tai tietosarjoja.

Liukuikkuna-algoritmin ydinajatuksena on määrittää kiinteän tai muuttuvan kokoinen ikkuna ja siirtää sitä syötetietojen läpi. Tämän avulla voit tutkia syötteen eri osajoukkoja ilman ylimääräisiä laskelmia, jotka voivat haitata suorituskykyä.

Tässä on visuaalinen esitys siitä, miten se toimii:

Ikkunan rajat voivat mukautua tietyn ongelman vaatimusten mukaan.

Liukuvan ikkunan algoritmin käyttöönotto Gossa

Voit käyttää suosittua koodaustehtävää oppiaksesi kuinka liukuikkuna-algoritmi toimii: löytää tietynpituisen alitaulukon suurin summa.

Tämän näytetehtävän tavoitteena on löytää koon alitaulukko k jonka elementtien summa on suurin. Ratkaisufunktio ottaa kaksi parametria: syötetaulukon ja edustavan positiivisen kokonaisluvun k.

Olkoon näytetaulukko numerot, kuten alla oleva koodi osoittaa:

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

Ja olkoon alitaulukon pituus k, jonka arvo on 3:

k := 3

Voit sitten ilmoittaa funktion löytääksesi k-pituisten alitaulukoiden enimmäissumman:

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

Saatat ajatella, että ikkunan on oltava taulukko, joka tallentaa kopiot kohdeelementeistä. Vaikka se on vaihtoehto, se toimii huonosti.

Sen sijaan sinun on vain määritettävä ikkunan rajat, jotta voit seurata sitä. Esimerkiksi tässä tapauksessa ensimmäisen ikkunan aloitusindeksi on 0 ja loppuindeksi k-1. Päivität nämä rajat ikkunaa liu'uttaessasi.

Ensimmäinen askel tämän ongelman ratkaisemiseksi on saada ensimmäisen k-koon alitaulukon summa. Lisää seuraava koodi funktioosi:

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

Yllä oleva koodi ilmoittaa algoritmille tarvittavat muuttujat ja löytää taulukon ensimmäisen ikkunan summan. Sitten se alustuu maxSum ensimmäisen ikkunan summalla.

Seuraava askel on liu'uta ikkunaa iteroimalla numerot taulukko indeksistä k loppuun. Jokaisessa ikkunan liukuvaiheessa:

1. Päivittää windowsSum lisäämällä nykyinen elementti ja vähentämällä alkio at windowStart.
2. Päivittää maxSum jos uusi arvo windowsSum on sitä suurempi.

Seuraava koodi toteuttaa liukuvan ikkunan. Lisää se kohtaan maksimiSubarraySum toiminto.

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

Kun silmukka on valmis, saat suurimman summan maxSum, jonka voit palauttaa funktion tuloksena:

return maxSum

Koko toimintosi pitäisi näyttää tältä:

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
}

Voit määrittää pääfunktion algoritmin testaamiseksi käyttämällä arvoja numerot ja k aikaisemmasta:

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

Tulos tässä tapauksessa on 19, joka on alitaulukon [4, 8, 7] summa, joka on suurin.

Voit nyt soveltaa samaa tekniikkaa samanlaisiin ongelmiin, jopa muilla kielillä, kuten käsitellä toistuvia elementtejä ikkunassa käyttämällä a Java hash kartta, esimerkiksi.

Optimaaliset algoritmit johtavat tehokkaisiin sovelluksiin

Tämä algoritmi on osoitus tehokkaiden ratkaisujen voimasta ongelmanratkaisussa. Liukuva ikkuna maksimoi suorituskyvyn ja poistaa tarpeettomat laskennat.

Vankka ymmärrys liukuikkuna-algoritmista ja sen toteutuksesta Gossa auttaa sinua selviytymään tosielämän skenaarioista sovelluksia rakennettaessa.