स्लाइडिंग विंडो एल्गोरिथम के लिए एक गाइड और इसे गो में कैसे लागू करें

संख्याओं और वर्णों के अनुक्रम पर संचालन करना प्रोग्रामिंग का एक महत्वपूर्ण पहलू है। स्लाइडिंग विंडो एल्गोरिदम ऐसा करने के लिए मानक एल्गोरिदम में से एक है।

यह एक सुंदर और बहुमुखी समाधान है जिसने कई डोमेन में अपनी जगह बना ली है। स्ट्रिंग मैनिपुलेशन से लेकर ऐरे ट्रैवर्सल और प्रदर्शन अनुकूलन तक, यह एल्गोरिदम एक भूमिका निभा सकता है।

तो, स्लाइडिंग विंडो एल्गोरिदम कैसे काम करता है, और आप इसे गो में कैसे कार्यान्वित कर सकते हैं?

स्लाइडिंग विंडो एल्गोरिथम को समझना

वहाँ हैं कई शीर्ष एल्गोरिदम जो एक प्रोग्रामर के रूप में जानना उपयोगी है, और स्लाइडिंग विंडो उनमें से एक है। यह एल्गोरिदम डेटा के अनुक्रम पर एक गतिशील विंडो बनाए रखने की एक सरल अवधारणा के इर्द-गिर्द घूमता है, ताकि उस डेटा के सबसेट को कुशलतापूर्वक संसाधित और विश्लेषण किया जा सके।

आप कम्प्यूटेशनल समस्याओं को हल करते समय एल्गोरिदम लागू कर सकते हैं जिसमें डेटा की सारणी, स्ट्रिंग या अनुक्रम शामिल हैं।

स्लाइडिंग विंडो एल्गोरिदम के पीछे मुख्य विचार एक निश्चित या परिवर्तनीय आकार की विंडो को परिभाषित करना और इसे इनपुट डेटा के माध्यम से स्थानांतरित करना है। यह आपको अनावश्यक गणनाओं के बिना इनपुट के विभिन्न उपसमूहों का पता लगाने की सुविधा देता है जो प्रदर्शन में बाधा डाल सकते हैं।

यह कैसे काम करता है इसका एक दृश्य प्रतिनिधित्व यहां दिया गया है:

विंडो की सीमाएँ विशिष्ट समस्या की आवश्यकताओं के अनुसार समायोजित हो सकती हैं।

गो में स्लाइडिंग विंडो एल्गोरिथम लागू करना

स्लाइडिंग विंडो एल्गोरिदम कैसे काम करता है यह जानने के लिए आप एक लोकप्रिय कोडिंग समस्या का उपयोग कर सकते हैं: किसी दी गई लंबाई के साथ उप-सरणी का सबसे बड़ा योग खोजना।

इस नमूना समस्या का उद्देश्य आकार की उप-सरणी खोजना है क जिनके तत्वों का योग सबसे बड़ा मूल्य है। समाधान फ़ंक्शन दो पैरामीटर लेता है: इनपुट सरणी और एक सकारात्मक पूर्णांक प्रतिनिधित्व करता है क.

नमूना सरणी होने दो अंक, जैसा कि नीचे दिया गया कोड दिखाता है:

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

उपरोक्त कोड एल्गोरिदम के लिए आवश्यक चर घोषित करता है और सरणी में पहली विंडो का योग ढूंढता है। इसके बाद यह प्रारंभ होता है मैक्ससम पहली विंडो के योग के साथ.

अगला कदम है खिड़की खिसकाओ के माध्यम से पुनरावृत्त करके अंक सूचकांक से सरणी क अंत तक। विंडो स्लाइडिंग के प्रत्येक चरण में:

1. अद्यतन विंडोसम वर्तमान तत्व को जोड़कर और तत्व को घटाकर विंडोस्टार्ट.
2. अद्यतन मैक्ससम यदि का नया मान विंडोसम उससे भी बड़ा है.

निम्नलिखित कोड स्लाइडिंग विंडो को लागू करता है। इसे इसमें जोड़ें अधिकतमसबरेसम समारोह।

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

जब लूप पूरा हो जाएगा, तो आपके पास सबसे बड़ी राशि होगी मैक्ससम, जिसे आप फ़ंक्शन के परिणाम के रूप में वापस कर सकते हैं:

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] का योग है, जो सबसे बड़ा है।

अब आप इसी तकनीक को समान समस्याओं पर लागू कर सकते हैं, यहां तक ​​कि अन्य भाषाओं में भी, जैसे किसी विंडो के भीतर बार-बार दोहराए जाने वाले तत्वों को संभालना जावा हैश मानचित्र, उदाहरण के लिए।

इष्टतम एल्गोरिदम का परिणाम कुशल अनुप्रयोगों में होता है

जब समस्या-समाधान की बात आती है तो यह एल्गोरिदम कुशल समाधान की शक्ति के प्रमाण के रूप में खड़ा होता है। स्लाइडिंग विंडो प्रदर्शन को अधिकतम करती है और अनावश्यक गणनाओं को समाप्त करती है।

स्लाइडिंग विंडो एल्गोरिथम और गो में इसके कार्यान्वयन की एक ठोस समझ आपको एप्लिकेशन बनाते समय वास्तविक दुनिया के परिदृश्यों से निपटने में सक्षम बनाती है।