Ez az okos algoritmus felgyorsíthatja programjait, és tömbök segítségével inspirálhatja munkáját.
A szám- és karaktersorozatokon végzett műveletek végrehajtása a programozás döntő része. A csúszóablak algoritmus az egyik szabványos algoritmus erre.
Ez egy elegáns és sokoldalú megoldás, amely több területen is megtalálta az utat. A karakterlánc-manipulációtól a tömbbejárásig és a teljesítményoptimalizálásig ez az algoritmus szerepet játszhat.
Tehát hogyan működik a csúszó ablak algoritmusa, és hogyan lehet megvalósítani a Go-ban?
A csúszóablak algoritmus megértése
Vannak sok top algoritmus amelyeket programozóként hasznos tudni, és ezek közé tartozik a csúszóablak. Ez az algoritmus egy egyszerű koncepció körül forog: dinamikus ablakot kell fenntartani egy adatsoron, hogy hatékonyan feldolgozzák és elemzik az adatok részhalmazait.
Az algoritmus akkor alkalmazható, ha olyan számítási problémákat old meg, amelyek tömböket, karakterláncokat vagy adatsorozatokat foglalnak magukban.
A csúszóablak-algoritmus mögött meghúzódó alapötlet egy rögzített vagy változó méretű ablak meghatározása, és annak mozgatása a bemeneti adatokon. Ez lehetővé teszi a bemenet különböző részhalmazainak felfedezését a teljesítményt akadályozó redundáns számítások nélkül.
Itt van egy vizuális ábrázolás a működéséről:
Az ablak határai az adott probléma követelményei szerint módosíthatók.
A csúszóablak algoritmus megvalósítása a Go-ban
Egy népszerű kódolási feladat segítségével megtudhatja, hogyan működik a csúszóablak algoritmus: egy adott hosszúságú résztömb legnagyobb összegének megtalálása.
Ennek a mintafeladatnak a célja a méret altömbjének megtalálása k amelynek elemei a legnagyobb értéket adják. A megoldási függvény két paramétert vesz fel: a bemeneti tömböt és egy pozitív egész számot k.
Legyen a mintatömb számok, ahogy az alábbi kód is mutatja:
nums := []int{1, 5, 4, 8, 7, 1, 9}
És legyen az altömb hossza k, 3-as értékkel:
k := 3
Ezután deklarálhat egy függvényt, hogy megtalálja a k hosszúságú altömbök maximális összegét:
funcmaximumSubarraySum(nums []int, k int)int {
// body
}
Lehet, hogy azt gondolja, hogy az ablaknak egy tömbnek kell lennie, amely a célelemek másolatait tárolja. Bár ez egy lehetőség, rosszul működik.
Ehelyett csak meg kell határoznia az ablak határait, hogy nyomon kövesse azt. Például ebben az esetben az első ablak kezdő indexe: 0 és egy végindex k-1. Az ablak elcsúsztatásakor frissíteni fogja ezeket a határokat.
A probléma megoldásának első lépése az, hogy megkapjuk az első k méretű résztömb összegét. Adja hozzá a következő kódot a függvényéhez:
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0for i := 0; i < k; i++ {
windowSum += nums[i]
}
maxSum = windowSum
A fenti kód deklarálja az algoritmushoz szükséges változókat, és megkeresi a tömb első ablakának összegét. Ezután inicializálódik maxSum az első ablak összegével.
A következő lépés az csúsztassa az ablakot iterálásával a számok tömb indexből k a végéig. Az ablak elcsúsztatásának minden lépésében:
- Frissítés windowsSum az aktuális elem hozzáadásával és az at elem kivonásával windowStart.
- Frissítés maxSum ha az új értéke windowsSum nagyobb annál.
A következő kód megvalósítja a csúszó ablakot. Add hozzá a maximumSubarraySum funkció.
for windowEnd = k; windowEnd < len(nums); windowEnd++ {
windowSum = windowSum + nums[windowEnd] - nums[windowStart]if windowSum > maxSum {
maxSum = windowSum
}
// slide window forward
windowStart++
}
Amikor a ciklus befejeződik, akkor a legnagyobb összeget kapja maxSum, amelyet a függvény eredményeként adhat vissza:
return maxSum
A teljes függvénynek így kell kinéznie:
funcmaximumSubarraySum(nums []int, k int)int {
var windowStart, windowEnd, maxSum, windowSum int
windowStart = 0for 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
}
Megadhat egy fő függvényt az algoritmus teszteléséhez, az értékek használatával számok és k korábbiról:
funcmain() {
nums := []int{1, 5, 4, 8, 7, 1, 9}
k := 3
fmt.Println(maximumSubarraySum(nums, k))
}
A kimenet ebben az esetben az lesz 19, amely a legnagyobb résztömb [4, 8, 7] összege.
Most már alkalmazhatja ugyanazt a technikát hasonló problémákra, akár más nyelveken is, például az ablakon belüli ismétlődő elemek kezelése a segítségével Java hash térkép, például.
Az optimális algoritmusok hatékony alkalmazásokat eredményeznek
Ez az algoritmus a hatékony megoldások erejének bizonyítéka a problémamegoldás terén. A csúszóablak maximalizálja a teljesítményt és kiküszöböli a szükségtelen számításokat.
A tolóablak algoritmus alapos ismerete és megvalósítása a Go-ban felkészíti Önt arra, hogy valós forgatókönyveket hozzon létre alkalmazások készítése során.
