बाइनरी खोज और मर्ज सॉर्ट के लगभग सभी कार्यान्वयन में त्रुटि है

यह जोशुआ बलोच के 2006 के एक्स्ट्रा का एक अनुवाद है , अतिरिक्त - इसके बारे में सभी पढ़ें: लगभग सभी बाइनरी सर्च और मर्जर्ट्स ब्रोकन लेख हैं ।

मुझे कार्नेगी मेलन यूनिवर्सिटी में जॉन बेंटले का पहला व्याख्यान याद आया, जिसमें उन्होंने हमसे पूछा, हौसले से पके हुए स्नातक छात्रों को बाइनरी सर्च फंक्शन लिखने के लिए कहा। उन्होंने इसका एक समाधान निकाला और इसे बोर्ड पर उतारा, और निश्चित रूप से, यह एक गलती के रूप में निकला, जैसा कि हमारे कई अन्य प्रयासों में था। यह घटना मेरे लिए उनकी पुस्तक "पर्ल ऑफ़ प्रोग्रामिंग" का स्पष्ट प्रदर्शन था। नैतिक सावधानी से कार्यक्रम में आक्रमणकारियों की व्यवस्था करना है।

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

तो गलती क्या है? यहाँ जावा में मानक द्विआधारी खोज है, उनमें से एक जिसे मैंने java.util.Arrays लिए लिखा था।

 public static int binarySearch(int[] a, int key) { int low = 0; int high = a.length - 1; while (low <= high) { int mid = (low + high) / 2; int midVal = a[mid]; if (midVal < key) low = mid + 1 else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found. } 

छठी पंक्ति में त्रुटि:

  int mid = (low + high) / 2; 

द पीयर्स ऑफ प्रोग्रामिंग में, बेंटले ने एक समान पंक्ति की कीमत पर लिखा है कि वह "इन संख्याओं के औसत के बराबर है, जो निकटतम छोटे पूर्णांक तक गोल है।" पहली नज़र में, सब कुछ ठीक है, लेकिन पर्याप्त रूप से बड़े low और high (अर्थात्, यदि उनकी राशि 2 ³¹ -1 से अधिक है) तो एक त्रुटि होती है। उनका योग ऋणात्मक संख्या बन जाता है, और mid भी ऋणात्मक हो जाता है। सी में, यह अप्रत्याशित परिणामों के साथ सरणी के बाहर मेमोरी एक्सेस का कारण होगा, जबकि जावा एक ArrayIndexOutOfBoundsException फेंकता है।

यह त्रुटि केवल बहुत बड़ी सरणियों पर दिखाई देती है, 2 ³⁰ से अधिक (एक अरब के आदेश के) तत्व। 80 के दशक में, जब पुस्तक में दिन का प्रकाश देखा जाता था, तो यह असंभव होता था, लेकिन अब Google पर (और वास्तव में किसी भी परियोजना में) यह एक सामान्य बात है। बेंटले "प्रोग्रामिंग के मोती" में लिखते हैं: "हालांकि बाइनरी खोज का पहला संस्करण 1946 में प्रकाशित हुआ था, सही कोड जो n के सभी मूल्यों को संसाधित करता है, केवल 1962 में दिखाई दिया।" वास्तव में, अब तक का सही कोड शायद ही सबसे लोकप्रिय भाषा कार्यान्वयन में भी सामने आया है।

तो आप इस कोड को कैसे लिखते हैं? छठी पंक्ति को इस प्रकार लिखा जा सकता है:

  int mid = low + ((high - low) / 2); 

हालांकि, शायद, यह विकल्प तेज और सरल है:

  int mid = (low + high) >>> 1; 

C / C ++ में कोई >>> ऑपरेटर नहीं है, लेकिन आप इसे इस तरह लिख सकते हैं:

  mid = ((unsigned int)low + (unsigned int)high)) >> 1; 

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

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

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

17 फरवरी, 2008 को फ़िनिश रिसर्च सेंटर के मुख्य अभियंता नोकिया एंटोनी ट्रूक्स (एंटोनी ट्रूक्स) ने अपडेट किया कि सी और सी ++ के लिए प्रस्तावित फिक्स सही संचालन की गारंटी नहीं देता है, क्योंकि इन भाषाओं के मानकों के अलावा अंकगणितीय अतिप्रवाह इसके अलावा एक अपरिभाषित परिणाम देता है। अब जब हमने इस दोष को ठीक कर लिया है, तो हमें यकीन है कि कार्यक्रम सही ढंग से काम कर रहा है। ;)

संदर्भ:

• " प्रोग्रामिंग के मोती " - मैं इसकी अत्यधिक अनुशंसा करता हूं, इसे खरीदना सुनिश्चित करें! (एक अनुवादक से: एक रूसी अनुवाद पुस्तक से उद्धृत)
  
• JDK बगट्रैकर में त्रुटि संदेश
  
• सल्वाटोर रग्गीरी द्वारा 2003 का एक अधिक सामान्य लेख, लेकिन शायद कम दिलचस्प समस्या: मनमाने ढंग से हस्ताक्षर के दो पूर्णांक के मध्य का पता लगाना। लेख प्रदर्शन के मुद्दों को संबोधित नहीं करता है, और प्रस्तावित समाधान आंतरिक मर्ज सॉर्ट चक्र के लिए पर्याप्त तेज़ नहीं है।