دليل لخوارزمية النافذة المنزلقة وكيفية تنفيذها في Go

يعد تنفيذ العمليات على تسلسل الأرقام والحروف جانبًا مهمًا في البرمجة. تعد خوارزمية النافذة المنزلقة إحدى الخوارزميات القياسية للقيام بذلك.

إنه حل أنيق ومتعدد الاستخدامات وجد طريقه إلى مجالات متعددة. من معالجة السلسلة إلى اجتياز المصفوفة وتحسين الأداء، يمكن لهذه الخوارزمية أن تلعب دورًا.

إذًا، كيف تعمل خوارزمية النافذة المنزلقة، وكيف يمكنك تنفيذها في Go؟

فهم خوارزمية النافذة المنزلقة

هناك العديد من الخوارزميات العليا والتي من المفيد أن تعرفها كمبرمج، والنافذة المنزلقة هي إحداها. تدور هذه الخوارزمية حول مفهوم بسيط يتمثل في الحفاظ على نافذة ديناميكية على سلسلة من البيانات، لمعالجة وتحليل مجموعات فرعية من تلك البيانات بكفاءة.

يمكنك تطبيق الخوارزمية عند حل المشكلات الحسابية التي تتضمن صفائف أو سلاسل أو تسلسلات من البيانات.

الفكرة الأساسية وراء خوارزمية النافذة المنزلقة هي تحديد نافذة ذات حجم ثابت أو متغير وتحريكها عبر بيانات الإدخال. يتيح لك هذا استكشاف مجموعات فرعية مختلفة من المدخلات دون الحاجة إلى حسابات زائدة يمكن أن تعيق الأداء.

فيما يلي تمثيل مرئي لكيفية عمله:

قد يتم ضبط حدود النافذة وفقًا لمتطلبات المشكلة المحددة.

تنفيذ خوارزمية النافذة المنزلقة في Go

يمكنك استخدام مسألة ترميز شائعة لمعرفة كيفية عمل خوارزمية النافذة المنزلقة: العثور على أكبر مجموع لمصفوفة فرعية بطول معين.

الهدف من هذه المشكلة النموذجية هو العثور على المصفوفة الفرعية للحجم ك التي مجموع عناصرها لأكبر قيمة. تأخذ وظيفة الحل معلمتين: صفيف الإدخال وعدد صحيح موجب يمثل ك.

دع مجموعة العينة تكون أرقام، كما يوضح الكود أدناه:

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

واسمحوا أن يكون طول الصفيف الفرعي ك، بقيمة 3:

k := 3

يمكنك بعد ذلك إعلان دالة للعثور على الحد الأقصى لمجموع المصفوفات الفرعية بطول k:

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

ربما تعتقد أن النافذة يجب أن تكون عبارة عن مصفوفة تقوم بتخزين نسخ من العناصر المستهدفة. ورغم أن هذا خيار، إلا أن أداءه ضعيف.

بدلاً من ذلك، كل ما عليك فعله هو تحديد حدود النافذة لتتبعها. على سبيل المثال، في هذه الحالة، سيكون للنافذة الأولى فهرس بداية 0 ومؤشر نهاية ك-1. أثناء عملية تحريك النافذة، ستقوم بتحديث هذه الحدود.

الخطوة الأولى لحل هذه المشكلة هي الحصول على مجموع المصفوفة الفرعية الأولى بالحجم k. أضف الكود التالي إلى وظيفتك:

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

يعلن الكود أعلاه عن المتغيرات الضرورية للخوارزمية ويجد مجموع النافذة الأولى في المصفوفة. ثم يتم التهيئة maxSum مع مجموع النافذة الأولى.

الخطوة التالية هي حرك النافذة عن طريق التكرار من خلال أرقام مصفوفة من الفهرس ك إلى النهاية. في كل خطوة من خطوات تحريك النافذة:

1. تحديث windowSum وذلك بإضافة العنصر الحالي وطرح العنصر في windowStart.
2. تحديث maxSum إذا كانت القيمة الجديدة ل windowSum أعظم منه.

ينفذ التعليمة البرمجية التالية النافذة المنزلقة. إضافته إلى maxSubarraySum وظيفة.

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

يجب أن تبدو وظيفتك الكاملة كما يلي:

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
}

يمكنك تحديد وظيفة رئيسية لاختبار الخوارزمية باستخدام قيم أرقام و ك في وقت سابق من:

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

سيكون الإخراج في هذه الحالة 19، وهو مجموع المصفوفة الفرعية [4، 8، 7]، وهي الأكبر.

يمكنك الآن تطبيق نفس الأسلوب على مشكلات مماثلة، حتى في اللغات الأخرى، مثل التعامل مع العناصر المتكررة داخل النافذة باستخدام ملف خريطة تجزئة جافا، على سبيل المثال.

الخوارزميات المثالية تؤدي إلى تطبيقات فعالة

تقف هذه الخوارزمية بمثابة شهادة على قوة الحلول الفعالة عندما يتعلق الأمر بحل المشكلات. تعمل النافذة المنزلقة على زيادة الأداء إلى الحد الأقصى وتزيل الحسابات غير الضرورية.

إن الفهم القوي لخوارزمية النافذة المنزلقة وتنفيذها في Go يجهزك للتعامل مع سيناريوهات العالم الحقيقي عند إنشاء التطبيقات.