सूची को उपयोगी क्या बनाता है
सूचियाँ: आपकी पहली डेटा संरचना
एक सूची (कुछ भाषाओं में एक सरणी कहा जाता है) वस्तुओं को एक विशिष्ट क्रम में संग्रहीत करती है। आप कर सकते हैं:
- किसी भी वस्तु तक इसकी स्थिति से पहुंचें: names[0] पहली वस्तु को पकड़ता है। O(1) — तत्काल।
- अंत में वस्तुएं जोड़ें: names.append("Zoe"). O(1) — तत्काल।
- क्रम में हर वस्तु के माध्यम से चलें: for name in names. O(N) — प्रत्येक वस्तु को एक बार देखता है।
सूचियाँ उस क्रम को संरक्षित करती हैं जिस क्रम में आप चीजें डालते हैं। पहली वस्तु पहली रहती है। आखिरी आखिरी रहती है।
# पालतू जानवरों की एक सूची
pets = ["cat", "dog", "cat", "fish", "dog"]
print(pets[0]) # "cat" — O(1) तत्काल
print(pets[3]) # "fish" — O(1) तत्काल
print(len(pets)) # 5 — डुप्लिकेट रखाध्यान दें: "cat" इनपुट में दो बार दिखाई दिया। "dog" दो बार दिखाई दिया। सूचियाँ डुप्लिकेट की अनुमति देती हैं। वे आपको जो देते हैं, उसे उसी क्रम में संग्रहीत करते हैं।
लेकिन सूचियों की एक कमजोरी है। देखें कि क्या होता है जब आप पूछते हैं: क्या "fish" इस सूची में है?
# सदस्यता जांच — क्या "fish" सूची में है?
if "fish" in pets: # ["cat", "dog", "cat", "fish"...] को एक-एक करके स्कैन करता है
print("found!") # इसे खोजने से पहले 4 वस्तुओं की जांच करनी पड़ीकंप्यूटर जांचता है "cat" — नहीं। "dog" — नहीं। "cat" — नहीं। "fish" — हाँ! इसने जवाब खोजने के लिए 4 वस्तुओं को स्कैन किया। 1,000 वस्तुओं के साथ, इसे सभी 1,000 को स्कैन करना पड़ सकता है। वह सदस्यता जांच O(N) की लागत आती है।
स्कैन लागत की भविष्यवाणी करें
आपके पास 500 छात्रों के नाम की एक सूची यादृच्छिक क्रम में है।
आप जांचना चाहते हैं कि "Zara" सूची में दिखाई देता है या नहीं।
students = ["Alex", "Maria", ..., "Zara", ...] # 500 नाम
if "Zara" in students:
print("enrolled")समुच्चय कैसे अलग तरीके से काम करता है
समुच्चय: सदस्यता प्रश्नों के लिए बनाया गया
एक समुच्चय अद्वितीय वस्तुओं को हैशिंग नामक तकनीक का उपयोग करके संग्रहीत करता है। जब आप कोई वस्तु जोड़ते हैं, तो कंप्यूटर एक हैश (एक संख्यात्मक फिंगरप्रिंट) की गणना करता है जो इसे बताता है कि उस वस्तु को कहाँ संग्रहीत करना है।
जब आप सदस्यता की जांच करते हैं, तो कंप्यूटर एक ही हैश की गणना करता है & सीधे सही स्थान पर जाता है। कोई स्कैनिंग नहीं।
# पालतू जानवरों का एक समुच्चय
pets = {"cat", "dog", "cat", "fish", "dog"}
print(pets) # {"cat", "dog", "fish"} — डुप्लिकेट हटा दिया गया
print(len(pets)) # 3 — केवल अद्वितीय वस्तुएंसूचियों से तीन अंतर पर ध्यान दें:
1. कोई डुप्लिकेट नहीं। "cat" इनपुट में दो बार दिखाई दिया लेकिन समुच्चय केवल एक प्रतिलिपि रखता है।
2. कोई गारंटीकृत क्रम नहीं। समुच्चय किसी भी व्यवस्था में वस्तुओं को प्रिंट कर सकता है।
3. कोई सूचकांक एक्सेस नहीं। आप pets[0] नहीं लिख सकते — समुच्चय के कोई स्थान नहीं हैं।
व्यापार-बंद: आप क्रम & डुप्लिकेट खोते हैं। आप O(1) सदस्यता परीक्षण प्राप्त करते हैं — यह जांचना कि क्या कोई वस्तु मौजूद है समुच्चय के 5 वस्तु हों या 5 मिलियन, समान समय लगता है।
# सदस्यता जांच — क्या "fish" समुच्चय में है?
if "fish" in pets: # hash("fish") → bucket में कूदें → पाया गया
print("found!") # बिल्कुल 1 स्थान की जांच की, 4 नहींसमुच्चय बनाम सूची सदस्यता
आपके पास 500 छात्रों के नाम एक समुच्चय में संग्रहीत हैं, एक सूची की जगह।
students = {"Alex", "Maria", ..., "Zara", ...} # 500 नाम
if "Zara" in students:
print("enrolled")साथ-साथ तुलना
ऑपरेशन चीट शीट
एक सूची का उपयोग करें जब आपको आवश्यकता हो:
- वस्तुएं एक विशिष्ट क्रम में (एक प्लेलिस्ट, एक रेसिपी, एक कतार)
- स्थिति द्वारा एक्सेस (items[3])
- डुप्लिकेट संरक्षित ("cat" 3 बार प्रकट होता है = 3 बिल्लियाँ)
एक समुच्चय का उपयोग करें जब आपको आवश्यकता हो:
- तेज सदस्यता जांच ("क्या मैंने पहले यह देखा है?")
- स्वचालित डुप्लिकेट हटाना
- क्रम के बारे में कोई चिंता नहीं
दोनों का उपयोग करें जब आपको आवश्यकता हो क्रम और तेज लुकअप दोनों:
seen = set() # O(1) सदस्यता जांच
result = [] # सम्मिलन क्रम संरक्षित करता है
for item in data:
if item not in seen: # O(1) जांच
seen.add(item) # O(1) जोड़ें
result.append(item) # O(1) अपेंड करें
# कुल: O(N) — एक पास, प्रत्येक चरण O(1)यह "समुच्चय + सूची" पैटर्न आपको सर्वोत्तम देता है: क्रमबद्ध परिणाम तेज डुप्लिकेट पहचान के साथ।
सही संरचना चुनें
तीन समस्याएं। प्रत्येक के लिए, निर्णय लें: सूची, समुच्चय, या दोनों?
1. आपको गीतों की एक प्लेलिस्ट उस क्रम में संग्रहीत करनी है जिस क्रम में उपयोगकर्ता ने उन्हें जोड़ा।
2. आपको जल्दी से जांचनी है कि क्या उपयोगकर्ता नाम पहले से लिया जा चुका है।
3. आपको एक मेलिंग सूची से डुप्लिकेट ईमेल निकालने की आवश्यकता है लेकिन उन्हें उस क्रम में रखें जिस क्रम में वे साइन अप हुए थे।
डुप्लिकेशन हटाने की समस्या
समस्या: डुप्लिकेट हटाएं, क्रम रखें
आपको ईमेल साइन-अप की एक सूची प्राप्त होती है। कुछ लोग दो बार साइन अप हुए थे। आपको हर व्यक्ति को एक ईमेल भेजना है, उस क्रम में जिस क्रम में वे पहली बार साइन अप हुए थे।
प्रयास 1: केवल सूची (धीमा)
signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
unique = []
for email in signups:
if email not in unique: # unique सूची के O(N) स्कैन
unique.append(email)
# काम करता है! लेकिन: O(N) जांच × N वस्तुएं = O(N²)100 साइन-अप के साथ, यह ~5,000 जांच करता है। 10,000 साइन-अप के साथ: ~50,000,000 जांच।
प्रयास 2: समुच्चय + सूची (तेज)
signups = ["alice@a.com", "bob@b.com", "alice@a.com", "carol@c.com"]
seen = set()
unique = []
for email in signups:
if email not in seen: # O(1) हैश लुकअप
seen.add(email) # O(1) समुच्चय में जोड़ें
unique.append(email) # O(1) सूची में अपेंड करें
# O(1) जांच × N वस्तुएं = O(N)एक ही परिणाम। एक ही क्रम। लेकिन: 10,000 साइन-अप अब ~50,000,000 की जगह ~10,000 जांच की आवश्यकता है।
गति में सुधार की गणना करें
केवल-सूची संस्करण O(N²) पर चलता है। समुच्चय+सूची संस्करण O(N) पर चलता है।
आपके पास 10,000 ईमेल साइन-अप को डुप्लिकेट करने के लिए हैं।
सामान्य तत्व खोजना
समस्या: दोनों सूचियों में वस्तुएं खोजें
आपके पास दो कक्षा रोस्टर हैं। आपको दोनों कक्षाओं में नामांकित छात्रों को खोजने की आवश्यकता है।
धीमा दृष्टिकोण: नेस्टेड लूप O(N × M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b = ["Bob", "Diana", "Eve", "Frank"]
both = []
for student in class_a: # N पुनरावृत्तियां
if student in class_b: # हर बार M स्कैन
both.append(student)
# O(N × M) — प्रत्येक छात्र को class_b के सभी के विरुद्ध स्कैन किया गयातेज दृष्टिकोण: एक सूची को समुच्चय में बदलें O(N + M)
class_a = ["Alice", "Bob", "Carol", "Diana"]
class_b_set = set(class_b) # O(M) निर्माण के लिए
both = []
for student in class_a: # N पुनरावृत्तियां
if student in class_b_set: # O(1) हर बार
both.append(student)
# O(N + M) — एक बार समुच्चय बनाएं, N बार O(1) पर जांच करेंया पायथन के अंतर्निर्मित समुच्चय चौराहे का उपयोग करते हुए भी सरल:
both = set(class_a) & set(class_b) # O(N + M)& ऑपरेटर सभी वस्तुओं को खोजता है जो दोनों समुच्चय में दिखाई देती हैं।
गति के लिए फिर से लिखें
एक स्कूल के पास 200 सदस्यों वाले दो क्लब हैं। यह कोड दोनों क्लबों में छात्रों को खोजता है:
chess_club = [...] # 200 नाम
art_club = [...] # 200 नाम
both_clubs = []
for student in chess_club:
if student in art_club:
both_clubs.append(student)निर्णय ढांचा
आपकी डेटा संरचना निर्णय ढांचा
हर बार जब आप वस्तुओं का संग्रह संग्रहीत करने वाले कोड को लिखते हैं, पूछें:
1. क्या मुझे वस्तुओं का क्रम चाहिए? → सूची
2. क्या मुझे तेज सदस्यता जांच चाहिए? → समुच्चय
3. क्या मुझे क्रम और तेज जांच दोनों चाहिए? → एक साथ समुच्चय + सूची
4. क्या मुझे डुप्लिकेट चाहिए? → सूची (समुच्चय डुप्लिकेट छोड़ते हैं)
---
इस पाठ की मुख्य अंतर्दृष्टि: एक ही प्रोग्राम, एक ही समस्या को हल करते हुए, केवल सही डेटा संरचना चुनकर 1,000× से 1,000,000× तेज चल सकता है। कोई चतुर चाल नहीं। कोई जटिल गणित नहीं। बस पूछना: मेरा कोड सबसे अधिक कौन से ऑपरेशन करता है? फिर उस संरचना को चुनें जहां वे ऑपरेशन O(N) की जगह O(1) में होते हैं।
इस पाठ में सूचियों और समुच्चय कवर किए गए थे। अन्य डेटा संरचनाएं मौजूद हैं (शब्दकोश, पेड़, ढेर) जो अन्य समस्याओं को हल करते हैं। निर्णय ढांचा वही रहता है: अपने ऑपरेशन को समझें, फिर उस संरचना को चुनें जो उन्हें सस्ता बनाता है।
---
गहराई में जाना चाहते हैं? हमारा Big O पाठ विकास दरों और स्केलिंग गणना को विस्तार से कवर करता है। देखें Big O: Fast Enough कितना तेज है?। हमा unhamming कोर्स वास्तविक दुनिया की खामी कवर करता है (MOAD-0001) जहां इसी list-to-set सुधार ने उत्पादन सॉफ़्टवेयर में 1,000× गति में सुधार किया। देखें The Missing Chapter: Algorithmic Complexity।
इस कोड को डीबग करें
एक छात्र ने एक किताब में कितने अद्वितीय शब्द दिखाई देते हैं यह गिनने के लिए यह कोड लिखा:
words = book.split() # सभी शब्दों की सूची
unique_count = 0
checked = []
for word in words: # N शब्द
if word not in checked: # checked सूची को स्कैन करता है
checked.append(word)
unique_count += 1
print(unique_count)किताब में 100,000 शब्द हैं।