कोड को बढ़ते दरों के लिए पढ़ना
कोड रिव्यू के लिए सही होना vs कोड रिव्यू के लिए जटिलता
सही होने के लिए कोड रिव्यू लॉजिक दोष पकड़ते हैं: गलत स्थितियाँ, ऑफ-बाय-वन इंडेक्स, मिसिंग नल चेक। जटिलता जागरूक कोड रिव्यू एक अलग श्रेणी के दोष पकड़ते हैं: कोड जो N = 100 पर सही रूप से काम करता है लेकिन N = 100,000 पर विनाशकारी रूप से बढ़ता है।
इस पाठ का जुड़ाव unhamming कोर्स के गहन विश्लेषण से होता है: [एल्गोरिदमिक जटिलता में लापता अध्याय](/en/un/unhamming_algorithmic_complexity) बिग ओ को प्रोडक्शन दोषों के संदर्भ में रखता है, और [MOAD-0001: सेडिमेंट्री दोष](/en/un/unhamming_moad_sedimentary) पैटर्न को 60+ सॉफ्टवेयर इकोसिस्टمز में मैप करता है।
दो समीक्षा हेकुरिस्टिक्स
Nested loops जटिलता को गुणा करते हैं। दो nested loops N आइटम पर चलते हैं तो O(N²) बनाते हैं। तीन produce O(N³). जब समीक्षा करते हैं: loop nesting गहराई को पहले गिनें।
एक गर्म loop के अंदर sequential container। किसी .contains(), .includes(), .find(), या in list चेक को loop के अंदर किसी भी समय O(N) का खर्च आता है। N iterations पर: O(N²) कुल। यह पैटर्न प्रोडक्शन कोड में दौरान दutzens of ecosystems में पाया जाता है - GHC Haskell कंपाइलर, Python pip, Apache Maven, Rust Cargo, TypeScript, Godot। वही गलती, अलग कोडबेस।
समीक्षा: find_duplicates
जटिलता के लिए कॉम्प्लेक्सिटी के लिए निम्नलिखित पायथन फ़ंक्शन की समीक्षा करें:
def find_duplicates(items):
seen = []
duplicates = []
for item in items:
if item in seen:
duplicates.append(item)
else:
seen.append(item)
return duplicatesMOAD-0001: sedimentary defect
एक ही दोष, साठ वातावरण
एक loop के अंदर if x not in list: list.append(x) पैटर्न सामान्य है - हो चुका है - विभिन्न सॉफ्टवेयर वातावरणों के निर्माण कोड में:
- GHC (हस्कल कंपाइलर): निर्भरता समाधान, O(N²) पर N = 50,000 पैकेज पर, 17 मिनट के निर्माण समय
- Python pip: निर्भरता संघर्ष समाधान
- Apache Maven: classpath दोहराव योजना
- Rust Cargo: सुविधा एकीकरण
- TypeScript कंपाइलर: मॉड्यूल योजना
- Godot / Redot गेम इंजन: नोड ग्राफ यात्रा
इन सभी टीमों ने गलती नहीं की। उन्होंने छोटे N पर सही कोड लिखा। N बढ़ा। कोड कैल्सिफाइड हुआ। पैटर्न को एक नाम है: MOAD-0001, sedimentary defect। sediment: सही और नन-हानिकारक पतली परतों में। समय के साथ, परतें एकत्र होती हैं और कठोर होती हैं।
हल
प्रत्येक मामले में: एकाधिकारी कंटेनर को हैश कंटेनर से बदलें। एक लाइन। सही इनपुट के लिए व्यवहार में कोई परिवर्तन नहीं। वास्तविक-विश्व N पर 100-1000 गुणा तेजी।
हल काम करता है क्योंकि दो संचालन तेज रहना चाहिए:
1. सदस्यता जाँच: इस तत्व को पहले से ही देखा गया है क्या?
2. संगत निर्देशांक: तत्वों को उनके प्रारंभिक दिखाई के क्रम में वापस करें (कभी-कभी आवश्यक होता है, कभी-कभी नहीं)।
एक सेट (1) को O(1) में हैश टेबल में तत्वों को संग्रहीत करता है। यदि (2) भी महत्वपूर्ण है, तो संगत निर्देशांक के लिए एक अलग सूची रखें और सदस्यता जाँच के लिए सेट। दो डेटा संरचनाएँ, प्रत्येक को एक काम करने दें।
पPull अनुरोध का जवाब देना
एक पुल अनुरोध MOAD-0001 को एक परियोजना के ग्राफ यात्रा फ़ंक्शन में ठीक करता है। एक समीक्षक टिप्पणी करता है:
> "Sets don't preserve insertion order — this changes behavior."
साक्षात्कार विश्लेषण पैटर्न
अपेक्षित स्वरूप
अल्गोरिदम की जटिलता विश्लेषण सॉफ्टवेयर इंजीनियरिंग साक्षात्कारों में प्रकट होता है। एक मजबूत उत्तर चार भाग के पैटर्न का अनुसरण करता है:
1. वर्तमान जटिलता का बयान - O(?) समय, O(?) स्थान के लिए।
2. कारण का व्याख्या - संबंधित निर्माण की पहचान करें (गति वाले गोला, लाइनर स्कैन गोले, वापसी वाले विभाजन)।
3. सुधार का प्रस्ताव - परिवर्तन का नाम दें और इसे पेश करने वाले डेटा संरचना या एल्गोरिदम का परिचय दें।
4. नई जटिलता का बयान - सुधार के बाद, समय और स्थान की जटिलता क्या होगी?
उदाहरण:
कोड: [सूची के अंदर गोले में सदस्यता जाँच करने वाली कार्यक्षमता]
वर्तमान: O(N²) — `item in seen_list` की सदस्यता जाँच O(N) है × N गिनतियाँ
सुधार: seen_list को seen_set (हैश सेट) से बदलें
बाद: O(N) — सेट सदस्यता जाँच O(1) हैयह क्षमता साक्षात्कारों के बाहर भी लागू होता है: जटिलता के प्रति जागरूक कोड समीक्षा, आर्किटेक्चर डिज़ाइन, प्रदर्शन डिबगिंग, सुरक्षा ऑडिट। किसी भी प्रणाली के लिए लाभ होता है जो वैरिएबल साइज के इनपुट प्रसंस्करण करता है।
यह पाठ यूनहैमिंग कोर्स के आगे के साथ जुड़ता है, जो इसीexact पैटर्न को 60+ ओपन-सोर्स परियोजनाओं के लिए प्रोडक्शन दोष निर्धारण पर लागू करता है।
साक्षात्कार: analyze has_common_element
इस कार्यक्रम के लिए चार भाग के साक्षात्कार स्वरूप को लागू करें:
def has_common_element(list_a, list_b):
for item in list_a:
for other in list_b:
if item == other:
return True
return False