पाठ · #1 / 11

ऐरे (Arrays)

लगातार (contiguous) मेमोरी — एक CPU साइकल में इंडेक्स तक पहुँच

init

at index 3 value

खुद आज़माएँ: किसी इंडेक्स को चमकाने के लिए read दबाइए (हरा = O(1))। फिर किसी शुरुआती इंडेक्स पर insert कीजिए और देखिए कैसे दाईं तरफ़ की कोशिकाएँ नारंगी रंग में लहर बनकर खिसकती हैं — यही O(n) की लागत आँखों के सामने है।

यह क्यों मायने रखता है

कंप्यूटिंग में ऐरे सबसे बुनियादी डेटा स्ट्रक्चर है। बाक़ी हर डेटा स्ट्रक्चर या तो ऐरे पर ही बना होता है, या उसकी सीमाओं से पार पाने के लिए गढ़ा गया होता है। ऐरे को समझना यानी यह समझना कि कंप्यूटर असल में डेटा को रखता और पढ़ता कैसे है।

मूल विचार

एक गलियारे में नंबर लगे लॉकरों की एक क़तार की कल्पना कीजिए। हर लॉकर पर एक नंबर (इंडेक्स) पुता है, और आप सीधे लॉकर #47 तक चल कर जा सकते हैं क्योंकि आपको ठीक-ठीक पता है वह कहाँ है — आपको पहले लॉकर 1 से 46 तक जाँचने की ज़रूरत नहीं।

यही एक ऐरे है। मेमोरी का एक लगातार (contiguous) ब्लॉक, जहाँ हर ख़ाने की एक तय जगह होती है।

जादू यह है: चूँकि तत्व अग़ल-बग़ल रखे होते हैं, किसी भी तत्व तक उसके इंडेक्स से पहुँचना तत्काल होता है — O(1)। कंप्यूटर हिसाब लगाता है: base_address + (index * element_size)।

सीमा यह है: अगर आप बीच में कोई नया तत्व डालना चाहें, तो उसके बाद के सारे तत्वों को खिसकना पड़ता है — O(n)। ठीक वैसे जैसे ठूँस-ठूँस कर भरी अलमारी में एक और किताब घुसाना।

मुख्य बातें

इंडेक्स तक पहुँच O(1) है — यही ऐरे की परिभाषक ताक़त है
मनमानी जगहों पर डालना/हटाना खिसकाव की वजह से O(n) है
मेमोरी लगातार (contiguous) होती है — कैश प्रदर्शन के लिए बढ़िया
आकार आम तौर पर तय होता है; डायनामिक ऐरे आकार बदलने की लागत को amortize कर देते हैं

और गहराई में

ऐरे तब चमकते हैं जब आपको रैंडम एक्सेस चाहिए और बीच में डालना/हटाना कभी-कभार ही पड़ता है। डायनामिक ऐरे (Vec, ArrayList) भर जाने पर क्षमता दुगुनी करके आकार-परिवर्तन सँभालते हैं — इसी से append की amortized लागत फिर भी O(1) बनी रहती है। ऐरे कैश के लिहाज़ से भी अनुकूल होते हैं: क्रमिक तत्वों तक पहुँचना तेज़ है क्योंकि वे एक साथ CPU कैश में लोड हो जाते हैं।

"amortized" O(1) क्यों — दुगुना करने का प्रमाण

एक डायनामिक ऐरे किसी छोटी क्षमता (मान लीजिए 4) से शुरू होता है और हर बार भर जाने पर दुगुना हो जाता है। ज़्यादातर push बस किसी ख़ाली ख़ाने में लिख देते हैं — O(1)। पर हर कुछ देर बाद ऐरे भर जाता है और आपको दुगुने आकार का नया ऐरे बनाकर पुराने n तत्व उसमें कॉपी करने पड़ते हैं — यह O(n) है।

तो क्या push सचमुच O(1) है? बहुत सारे push के औसत में, हाँ। 1 से n तत्वों तक बढ़ने में लगा कुल काम गिनिए:

copies: 1 + 2 + 4 + 8 + … + n/2 + n
     = 2n − 1
     = O(n) total work spread across n inserts
     = O(1) per insert, amortized

यह गुणोत्तर श्रेणी (geometric sum) हर पद को दुगुना करती है, पर पिछले पद घटकर आधे रह जाते हैं। कुल काम n में रैखिक ही बना रहता है। अगर दुगुना करने के बजाय आप आधा-आधा बढ़ाएँ, तो हर आकार-परिवर्तन O(n) हो जाता है और amortization का फ़ायदा नहीं मिलता — कुल काम चढ़कर O(n²) हो जाता है। दुगुना करना ही वह जादुई स्थिरांक है जिससे हिसाब बराबर बैठता है।

यह amortized विश्लेषण का पहला चिर-परिचित स्वाद है — यही पैटर्न हैश-टेबल rehashing, हीप निर्माण, और रिंग-बफ़र क़तारों में भी दिखता है।

कैश लोकैलिटी — दस गुने फ़र्क़ की असली वजह

ऐरे सिर्फ़ O(1) एक्सेस की वजह से तेज़ नहीं होते — वे इसलिए तेज़ हैं क्योंकि आधुनिक CPU क्रमिक मेमोरी को पहले से ही prefetch कर लेते हैं। जब आप arr[i] पढ़ते हैं, तो CPU एक पूरी कैश लाइन (आम तौर पर 64 बाइट — 16 int, या 8 double) L1 कैश में लोड कर देता है। उसके बाद arr[i+1] फिर arr[i+2] पढ़ना मुफ़्त कैश हिट हैं।

वही डेटा अगर एक लिंक्ड लिस्ट में मेमोरी भर बिखरा पड़ा हो, तो ज़्यादातर पॉइंटर dereference पर एक L1 मिस की क़ीमत चुकानी पड़ती है। स्थिरांक देखिए:

L1 हिट: ~1 ns (≈ 4 CPU साइकल)
L2 हिट: ~3 ns
L3 हिट: ~10 ns
मुख्य मेमोरी: ~100 ns

किसी गरम (hot) लूप में, एक ही तत्वों को रखते हुए भी एक ऐरे लिंक्ड लिस्ट से 10–100 गुना तेज़ हो सकता है, जबकि दोनों को घुमाने (iterate) में O(n) ही लगता है। Big-O इसे छुपा देता है। रोबोटिक्स का अनुभवसिद्ध नियम: किसी भी अंदरूनी लूप के लिए स्ट्रक्ट के ऐरे (AoS) या ऐरे के स्ट्रक्ट (SoA) को तरजीह दीजिए; लिंक्ड लिस्ट को सिर्फ़ उस बिरले मौक़े के लिए बचाकर रखिए जब आपको किसी ज़िंदा नोड संदर्भ के साथ O(1) splice चाहिए।

गणितीय ब्यौरा

Time Complexity: Access: O(1); Search (unsorted): O(n); Insert at end: O(1) amortized; Insert at index i: O(n-i)
Address Calculation: address[i] = base + i × sizeof(element)

क्रियान्वयन (Implementation)

Rust में ऐरे

// Fixed-size array
let arr: [i32; 5] = [1, 2, 3, 4, 5];
let third = arr[2]; // O(1) access

// Dynamic array (Vec)
let mut vec = Vec::new();
vec.push(1); // O(1) amortized
vec.insert(0, 0); // O(n) - shifts all elements

मुख्य ऑपरेशन

arr[i] - O(1) रैंडम एक्सेस
vec.push(x) - O(1) amortized append
vec.insert(i, x) - O(n) डालना
vec.remove(i) - O(n) हटाना

अभ्यास

ऐरे पर बने तीन चिर-परिचित सवाल, हर एक अलग तकनीक दिखाता है:

Two Sum — आसान · हैश टेबल के ज़रिए समय बचाने के लिए मेमोरी ख़र्च करना
Maximum Subarray (Kadane's) — मध्यम · एक ही पास में चलती हुई स्थिति रखना
Trapping Rain Water — कठिन · चलते हुए अधिकतम के साथ दो-पॉइंटर स्कैन

→ सभी अभ्यास सवाल देखें

🧱 ऐरे (Arrays)