راهنمای الگوریتم پنجره کشویی و نحوه پیاده سازی آن در Go

این الگوریتم هوشمندانه می تواند برنامه های شما را سرعت بخشد و کار شما را با آرایه ها الهام بخشد.

انجام عملیات بر روی دنباله ای از اعداد و کاراکترها یکی از جنبه های مهم برنامه نویسی است. الگوریتم پنجره کشویی یکی از الگوریتم های استاندارد برای انجام این کار است.

این یک راه حل زیبا و همه کاره است که راه خود را در چندین دامنه پیدا کرده است. از دستکاری رشته تا پیمایش آرایه و بهینه سازی عملکرد، این الگوریتم می تواند نقش مهمی را ایفا کند.

بنابراین، الگوریتم پنجره کشویی چگونه کار می کند و چگونه می توانید آن را در 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 را با مجموع اولین پنجره مقداردهی اولیه می کند.

مرحله بعدی این است که پنجره را با تکرار در آرایه اعداد از نمایه k تا انتها بکشید. در هر مرحله از کشیدن پنجره:

1. با افزودن عنصر فعلی و کم کردن عنصر در windowStart، windowSum را به روز کنید.
2. اگر مقدار جدید windowSum از آن بیشتر است، maxSum را به روز کنید.

کد زیر پنجره کشویی را پیاده سازی می کند. آن را به تابع 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] است که بزرگترین است.

اکنون می‌توانید همین تکنیک را برای مشکلات مشابه، حتی در زبان‌های دیگر، مانند مدیریت عناصر مکرر در یک پنجره با استفاده از نقشه هش جاوا، اعمال کنید.

الگوریتم های بهینه منجر به برنامه های کارآمد می شوند

این الگوریتم به عنوان شاهدی بر قدرت راه حل های کارآمد در هنگام حل مسئله است. پنجره کشویی عملکرد را به حداکثر می رساند و محاسبات غیر ضروری را حذف می کند.

درک کامل از الگوریتم پنجره کشویی و پیاده سازی آن در Go شما را برای مقابله با سناریوهای دنیای واقعی هنگام ساخت برنامه ها مجهز می کند.

منبع مقاله