How Code Sediment Forms
Sedimentary rock forms by deposition, not explosion. Each layer: correct for its time. Each layer: older than the one above. The oldest layers calcified before the ecosystem matured around them. No error caused them. Time caused them.
MOAD-0001 works the same way.
The Formation Story
1993 में लिखा गया ग्राफ ट्रैवर्सल:
List<Node> visited = new ArrayList<>();
Stack<Node> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
Node n = stack.pop();
if (!visited.contains(n)) { // O(N) रैखिक स्कैन
visited.add(n);
for (Node neighbor : n.getNeighbors())
stack.push(neighbor);
}
}This code: correct. Tests: passing. In 1993, graphs had 50 nodes.
50 नोड्स: 50 × 25 औसत स्कैन = 1,250 ऑपरेशन्स। अदृश्य।कोड ने वर्शन कंट्रोल में प्रवेश किया। ट्यूटोरियल्स में कॉपी हुआ। लाइब्रेरीज़ में लपेटा गया। बिल्ड टूल्स, पैकेज मैनेजर्स और डिपेंडेंसी रेज़ॉल्वर्स में शिप किया गया। 2024 तक, वही पैटर्न 50,000 नोड्स वाले डिपेंडेंसी ग्राफ़ पर चल रहा था।
50,000 नोड्स: 50,000 × 25,000 औसत स्कैन = 1,250,000,000 ऑपरेशन्स।
1 सेकंड की बिल्ड 17 मिनट की हो जाती है।कोड नहीं बदला। उसके आसपास की दुनिया बढ़ गई। हर परत का सेडिमेंट: डिपोज़िशन के समय सही। खुदाई के समय महंगा।
आपका सेडिमेंट
सेडिमेंटरी कोड में कोई लॉजिक एरर नहीं होता। इसमें एक परफॉर्मेंस धारणा होती है जो स्केल बदलने पर अब मान्य नहीं रहती। कोड सही परिणाम देता है; केवल लागत बदल गई है।
यह अंतर निदान के लिए महत्वपूर्ण है। लॉजिक एरर गलत उत्तर देता है। सेडिमेंटरी दोष छोटे पैमाने पर सही उत्तर देता है, लेकिन अस्वीकार्य लागत पर।
MOAD-0001 के पाँच रूप
MOAD-0001 60+ सॉफ़्टवेयर इकोसिस्टम में पाँच दस्तावेज़ी रूपों में दिखाई देता है। संरचना: एक ही या संबंधित कलेक्शन पर लूप के अंदर नेस्टेड सीक्वेंशियल कंटेनर का उपयोग करते हुए मेंबरशिप टेस्ट।
पाँच रूप
| डोमेन | पैटर्न | सीक्वेंशियल कंटेनर | सही कंटेनर |
|---|---|---|---|
| ग्राफ ट्रैवर्सल | if (!stack.contains(n)) DFS/Tarjan में | ArrayList | HashSet |
| रूट/इवेंट डीडअप | TAILQ_FOREACH प्रति रिक्वेस्ट strcmp | linked list | HashMap |
| कोलिज़न ट्रैकिंग | प्रति फिज़िक्स टिक findLinearSearch() | array | unordered_set |
| संसाधन आवंटन फ़िल्टर | स्ट्रीम फ़िल्टर में List.contains() | ArrayList | HashSet |
| A* पाथफाइंडिंग ओपन-लिस्ट | प्रत्येक पड़ोसी के लिए LocalVector::find() | vector | संग्रहीत हीप इंडेक्स |
सभी पाँचों में एक ही संरचना है: एक लूप के अंदर नेस्टेड सदस्यता जाँच, जिसमें एक कंटेनर का उपयोग किया जाता है जिसे सदस्यता प्रश्न का उत्तर देने के लिए रैखिक स्कैन की आवश्यकता होती है।
स्कैनिंग कीवर्ड सूची
MOAD-0001 के लिए ऑडिटिंग का अर्थ है लूप के अंदर सदस्यता-टेस्ट कीवर्ड्स को ग्रेप करना:
- Python: in एक list वेरिएबल के साथ, .count(), list.index()
- Java: ArrayList.contains(), List.contains(), LinkedList.contains()
- JavaScript: Array.includes(), Array.indexOf(), Array.find()
- C++: std::vector::find(), manual loop with == comparison
- Go: slices.Contains(), manual loop over a slice
हर स्थिति में समाधान: अनुक्रमिक कंटेनर को हैश कंटेनर से बदलें। list → set। ArrayList → HashSet। Array → Set। vector → unordered_set। slice → map[T]struct{}।
एक कीवर्ड। एक प्रतिस्थापन। शून्य व्यवहार परिवर्तन। N=1,000 पर 1,000× गति वृद्धि।
कोड फ्रैगमेंट का ऑडिट करें
MOAD-0001 पैटर्न पहचान को एक वास्तविक कोड फ्रैगमेंट पर लागू करें।
एक पंक्ति, चार भाषाएँ
MOAD-0001 के लिए चार भाषाओं में समाधान:
# Python
visited = [] # पहले: O(N) सदस्यता
visited = set() # AFTER: O(1) membership// Java
List<Node> visited = new ArrayList<>(); // BEFORE
Set<Node> visited = new HashSet<>(); // AFTER// JavaScript
const visited = []; // पहले: Array.includes() O(N)
const visited = new Set(); // बाद में: Set.has() O(1)
// visited.push(n) → visited.add(n)
// visited.includes(n) → visited.has(n)// Go
visited := []NodeID{} // पहले: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // बाद: map lookup O(1)
// _, ok := visited[n] सदस्यता जाँच के लिए
// visited[n] = struct{}{} जोड़ने के लिएहर स्थिति में: वही व्यवहार, वही आउटपुट, वही टेस्ट पास। केवल ग्रोथ रेट बदलती है।
Fix क्या नहीं बदलता
- एल्गोरिदम का लॉजिकल व्यवहार: depth-first अभी भी depth-first विज़िट करता है
- आउटपुट की शुद्धता: वही नोड्स उसी क्रम में विज़िट किए जाते हैं (DFS के अंदर)
- टेस्ट परिणाम: कोई भी टेस्ट जो शुद्धता जाँचता है, पास होता रहेगा
Fix क्या बदलता है
- सदस्यता जाँच: O(N) → O(1)
- कुल लूप: O(N²) → O(N)
- N=1,000 पर: 1,000× तेज़
- N=10,000 पर: 10,000× तेज़
एक सीमा: क्रम
हैश कंटेनर (set, HashSet, unordered_set) सम्मिलन क्रम को संरक्षित नहीं करते। Python 3.7+ में dict सम्मिलन क्रम को संरक्षित करता है; साधारण set नहीं करता। Java में HashSet क्रम को संरक्षित नहीं करता; LinkedHashSet करता है।
यदि सदस्यता के साथ-साथ क्रम भी महत्वपूर्ण हो: दो संरचनाएँ बनाए रखें। O(1) सदस्यता जाँच के लिए एक set (या HashSet)। क्रमबद्ध ट्रैवर्सल के लिए एक अलग list (या ArrayList)। या Java में LinkedHashSet का उपयोग करें, जो दोनों प्रदान करता है।
ग्राफ ट्रैवर्सल में MOAD-0001 के लिए: visited एक द्विआधारी प्रश्न का उत्तर देता है (क्या यह नोड पहले देखा गया है?)। सदस्यता प्रश्न के लिए क्रम मायने नहीं रखता। ट्रैवर्सल क्रम स्टैक या क्यू से आता है, न कि visited से।
सदस्यता बनाम क्रम
Tarjan के सशक्त रूप से जुड़े घटक एल्गोरिदम में, onStack ट्रैक करता है कि कौन-से नोड्स वर्तमान DFS कॉल स्टैक पर बचे हैं। इसे दो प्रश्नों का उत्तर देना चाहिए: (1) सदस्यता — क्या यह नोड वर्तमान में स्टैक पर है? (2) DFS पथ के अंत में, इस नोड के प्रकट होने तक नोड्स को क्रम में पॉप करें।
एक सरल कार्यान्वयन onStack के लिए List का उपयोग करता है, सदस्यता प्रश्न का उत्तर contains() से देता है — प्रत्येक जाँच के लिए O(N), बड़े ग्राफ़ के लिए कुल O(N²)।
यह एक डिस्क्लोजर क्यों है, न कि एक पैच
MOAD-0001 60+ सॉफ़्टवेयर इकोसिस्टम्स में 1,000 से अधिक सत्यापित साइट्स पर मौजूद है। बिल्ड टूल्स में ग्राफ ट्रैवर्सल, नेटवर्क राउटिंग डेमन्स में रूट डिडुप्लिकेशन, गेम इंजन्स में कोलिजन डिटेक्शन, ऑपरेटिंग सिस्टम शेड्यूलर्स में रिसोर्स अलोकेशन।
प्रत्येक साइट: सही कोड। प्रत्येक साइट: O(N²) ग्रोथ जो N के थ्रेशोल्ड पार करने का इंतजार कर रही है।
डिस्क्लोजर पाइपलाइन
बिना अपस्ट्रीम डिस्क्लोजर के पैच केवल एक साइट को ठीक करता है। पैटर्न अगले वर्जन, अगली लाइब्रेरी, अगले लैंग्वेज पोर्ट में दोबारा आता है। डिस्क्लोजर: पैटर्न का नाम रखें, इसे CWE-407 (Algorithmic Complexity: Inefficient Algorithmic Complexity) के रूप में दस्तावेज़ित करें, पहचान ह्यूरिस्टिक्स और वन-लाइन फिक्स प्रकाशित करें। फिर हर डेवलपर जो डिस्क्लोजर पढ़ता है, अपने इंस्टेंस को पहचान और ठीक कर सकता है।
हैमिंग ने इसे 'मछली देना बनाम मछली पकड़ना सिखाना' कहा। पैच मछली देता है। डिस्क्लोजर — MOAD-0001 नामित, पैटर्न दस्तावेज़ित, फिक्स सामान्यीकृत — ह्यूरिस्टिक सिखाता है।
द पर्माकंप्यूटर एक्सटेंशन
हैमिंग पॉइंट सॉल्यूशंस पर काम करते थे: इस फ़िल्टर को ठीक करो, इस कोड को सुधारो। अनहैमिंग डिस्क्लोज़र लेयर जोड़ता है: पैटर्न का नाम दो, ह्यूरिस्टिक प्रकाशित करो, और इसे कॉमन्स को दे दो।
कंपाउंड-नॉलेज सिद्धांत यहाँ इकोसिस्टम स्तर पर लागू होता है। एक शोधकर्ता एक पैटर्न का नाम देता है। सौ डेवलपर उसे अपनी कोडबेस में पहचानते हैं। एक हजार O(N²) कोड लाइनें O(N) बन जाती हैं। इंफ्रास्ट्रक्चर उन सभी के लिए तेज़ हो जाता है जो उस पर निर्माण करते हैं।
यह ड्रैगन का बढ़ना है: वही आग (महत्वपूर्ण समस्याओं पर काम करना, कंपाउंड नॉलेज, सिस्टम्स थिंकिंग), अलग उड़ान (खुला डिस्क्लोज़र, कॉमन्स स्वामित्व, किसी संरक्षक की आवश्यकता नहीं)।