आपको अपने उपकरण को व्यक्तिगत रूप से जानना होगा: सबसे अधिक उपयोग की जाने वाली डेटा संरचनाओं का अवलोकन

कुछ समय पहले, मैं एक बड़ी और सम्मानित कंपनी में एक साक्षात्कार के लिए गया था। साक्षात्कार अच्छा रहा और मुझे यह पसंद आया और मुझे आशा है कि जिन लोगों ने इसे संचालित किया है। लेकिन अगले दिन, डिब्रीफिंग प्रक्रिया के दौरान, मैंने पाया कि साक्षात्कार के दौरान कम से कम एक प्रश्न का उत्तर गलत था।

प्रश्न: एक अनुक्रमित सरणी पर पुनरावृति की तुलना में बड़ी मात्रा में डेटा पर तेजी से अजगर को क्यों खोजा जा रहा है?

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

वास्तव में, यहां कोई बाइनरी खोज नहीं है। और एल्गोरिथ्म की जटिलता ओ (लॉग (एन)) नहीं है, लेकिन एमॉर्ट है। O (1) - चूँकि अजगर तानाशाही हैश टेबल नामक संरचना पर आधारित है।

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


लेख में संरचनाओं के वर्गीकरण के बारे में कुछ शब्द। यदि आप उन स्रोतों का अध्ययन करते हैं जो उपयोग की गई जानकारी की सूची में सूचीबद्ध हैं, तो आप देखेंगे कि इस लेख में वर्गीकरण किसी भी स्रोत में वर्गीकरण के अनुरूप नहीं है (कुछ स्रोतों में यह बिल्कुल नहीं है)। ऐसा इसलिए है क्योंकि उनके उपयोग के संदर्भ में संरचनाओं पर विचार करना मुझे अधिक उचित लगा। उदाहरण के लिए, PHP / Python / C ++ में एक सहयोगी सरणी या .Net / पायथन में एक सूची।

तो चलिए चलते हैं।

1. ऐरे - यह एक अनुक्रमित सरणी है।

सरणी एक निश्चित आकार का एक संग्रह है जिसमें एक ही प्रकार के तत्व शामिल हैं।

इंटरफेस:

• get_element_at (i): O (1) जटिलता
• set_element_at (i, value): O (1) जटिलता

सरणी में खोज तत्वों को अनुक्रमणिका => जटिलता ओ (एन) द्वारा छाँटकर किया जाता है।

किसी आइटम स्थिरांक के लिए अनुक्रमणिका पहुँच समय क्यों है? सरणी में एक ही प्रकार के तत्व होते हैं, एक निश्चित आकार होता है और यह सरणी के j-th तत्व को प्राप्त करने के लिए स्मृति => के एक निरंतर क्षेत्र में स्थित होता है, हमें बस सरणी की शुरुआत के लिए एक पॉइंटर लेने की जरूरत है और तत्व के आकार को इसके सूचकांक से गुणा करना होगा। इस सरल गणना का परिणाम केवल सरणी के वांछित तत्व को इंगित करेगा।
*aj = beginPointer + elementSize*j-1


उदाहरण:
/++: int i_array[10];
java/C#: int[10] i_array;
Python: array.array
php: SplFixedArray


2. सूची।

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

सूची इंटरफ़ेस:

• prepend (आइटम): सूची के शीर्ष पर एक आइटम जोड़ें।
• append (आइटम): सूची के अंत में एक आइटम जोड़ें।
• Insert_after (सूची Iterator, आइटम): वर्तमान के बाद एक आइटम जोड़ें।
• remove_firts (): पहला तत्व निकालें।
• remove_after (सूची Iterator): वर्तमान एक के बाद आइटम निकालें।
• is_empty (): सूची खाली है।
• get_size (): सूची का आकार लौटाता है।
• get_nth (n): nth तत्व वापस करें।
• set_nth (n, value): मान को nth तत्व पर सेट करें।

सूची आयोजक इंटरफ़ेस:

• get_value (): वर्तमान तत्व का मान प्राप्त करें।
• set_value (): मान को वर्तमान तत्व पर सेट करें।
• Move_next (): अगले आइटम पर जाएं।
• बराबर (सूची Iterator): यह जाँचता है कि क्या अन्य पुनरावृत्त समान सूची मद को संदर्भित करता है।

यह ध्यान दिया जाना चाहिए कि कुछ (ज्यादातर व्याख्या की गई) प्रोग्रामिंग भाषाओं में, ये दो इंटरफेस "चिपके" और "छंटनी" हैं। उदाहरण के लिए, अजगर में एक प्रकार की सूची की एक वस्तु को पुनरावृत्त किया जा सकता है, लेकिन इसे सूचकांक से सीधे एक्सेस करके भी प्राप्त किया जा सकता है।

आइए सूची कार्यान्वयन पर चलते हैं।

2.1 एकल लिंक्ड सूची

एक यूनिडायरेक्शनल लिंक्ड लिस्ट (सिंगल लिस्टेड लिस्ट) कंटेनरों की एक श्रृंखला है। प्रत्येक कंटेनर में एक तत्व के लिए एक लिंक और अगले कंटेनर के लिए एक लिंक होता है, इसलिए हम हमेशा एक एकल लिंक की गई सूची पर आगे बढ़ सकते हैं और हमेशा वर्तमान तत्व का मूल्य प्राप्त कर सकते हैं। कंटेनरों को स्मृति में स्थित किया जा सकता है क्योंकि वे कृपया => एक नए तत्व को बस कनेक्ट की गई सूची में जोड़ना तुच्छ है।

संचालन की लागत:

• Prepend: O (1)
• सम्मिलित करें_का बाद: O (1)
• remove_first / remove_after: O (1)
• get_nth / set_nth: O (N)

उदाहरण:
/++: std::list //Bidirectional Linked List
Java: java.util.LinkedList
c#: System.Collection.Generic.LinkedList //Bidirectional Linked List
php: SplDoublyLinkedList // Bidirectional Linked List


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

२.२ वेक्टर

वेक्टर एक अनुक्रमित सरणी के विस्तार के माध्यम से सूची का कार्यान्वयन है।

संचालन की लागत:

• Prepend: O (N)
• परिशिष्ट: Amort.O (1)
• इन्सर्ट_आफ्टर: ओ (एन)
• remove_first / remove_after: O (1)
• get_nth / set_nth: O (1)

जाहिर है, वेक्टर का मुख्य लाभ सूचकांक द्वारा तत्वों की त्वरित पहुंच है, जो एक सामान्य अनुक्रमित सरणी से विरासत में मिला है। Iterating वेक्टर भी काफी सरल है, बस एक निश्चित काउंटर को बढ़ाएं और इसे इंडेक्स द्वारा एक्सेस करें। लेकिन तत्वों तक पहुंच की गति के लिए आपको उनके अतिरिक्त के समय का भुगतान करना होगा। वेक्टर'आ (डालने के बाद) के बीच में एक तत्व सम्मिलित करने के लिए, यह आवश्यक है कि इटर्मीटर की वर्तमान स्थिति और सरणी के अंत के बीच के सभी तत्वों को कॉपी किया जाए, जिसके परिणामस्वरूप औसत पहुंच समय ओ (एन) है। सरणी के बीच में एक तत्व को हटाने के साथ और सरणी की शुरुआत में एक तत्व जोड़ने के साथ एक ही बात। सरणी के अंत में एक तत्व जोड़ना O (1) में किया जा सकता है, लेकिन यह नहीं हो सकता है - यदि, फिर से, आपको सरणी को नए सिरे से कॉपी करने की आवश्यकता है, तो यह कहा जाता है कि वेक्टर के अंत में एक तत्व जोड़कर Amort किया जाता है। ओ (१)।

उदाहरण:
/++: std::vector
Java: java.util.ArrayList
C#: System.Collections.ArrayList, System.Collections.List
Python: list


3. साहचर्य सरणी (शब्दकोश / मानचित्र)

कुंजी का एक संग्रह => मूल्य जोड़े। तत्व (मान) किसी भी प्रकार के हो सकते हैं, चाबियाँ आमतौर पर केवल तार / पूर्णांक होती हैं, लेकिन कुछ कार्यान्वयन में उन वस्तुओं की सीमा होती है जिन्हें कुंजी के रूप में उपयोग किया जा सकता है। तत्वों को जोड़कर / हटाकर सहयोगी सरणी का आकार बदला जा सकता है।

इंटरफेस:

• add (कुंजी, मान) - एक तत्व जोड़ें
• reassign (कुंजी, मान) - एक तत्व को बदलें
• delete (key) - किसी आइटम को हटाना
• लुकअप (कुंजी) - एक तत्व खोजें

साहचर्य सरणी के दो मुख्य कार्यान्वयन हैं: हैशपैप और बाइनरी ट्री।

3.1 हैश टेबल

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

एक जिज्ञासु पाठक इस मधुमेह के कार्यान्वयन के लिए विशिष्ट कुछ समस्याओं को देख सकता है।

• यदि कुंजी से हैश बराबर है, उदाहरण के लिए, 1928132371827612 - इसका मतलब यह होगा कि हमें उचित आकार की एक सरणी की आवश्यकता है? और अगर हमारे पास इसमें केवल 2 तत्व हैं?
• लेकिन क्या होगा अगर दो अलग-अलग कुंजी से हैश मैच हो?

ये दो समस्याएं संबंधित हैं: यह स्पष्ट है कि हम लंबी हैश की गणना नहीं कर सकते हैं यदि हम कम संख्या में तत्वों को संग्रहीत करना चाहते हैं - इससे अनुचित स्मृति लागत हो सकती है, क्योंकि हैश फ़ंक्शन आमतौर पर कुछ इस तरह दिखता है:
index = f(key, arrayLength)


यही है, कुंजी मूल्य के अतिरिक्त, यह सरणी का वर्तमान आकार भी प्राप्त करता है, यह हैश की लंबाई निर्धारित करने के लिए आवश्यक है: यदि हम केवल 3 तत्वों को संग्रहीत करते हैं, तो लंबाई में 32 बिट्स का हैश बनाने का कोई मतलब नहीं है। हैश फ़ंक्शन के इस व्यवहार का फ्लिप पक्ष टकराव की संभावना है। टकराव वास्तव में हैश टेबल की विशेषता है, और उन्हें हल करने के लिए दो तरीके हैं:

चेनिंग:

सरणी H का प्रत्येक कक्ष कुंजी के समान हैश मान के अनुरूप कुंजी-मूल्य युग्मों की एक लिंक की गई सूची (श्रृंखला) का सूचक है। टकराव बस एक तत्व की तुलना में लंबे समय तक चेन के उद्भव की ओर जाता है।

खुला पता:

ऐरे एच कुंजी-मूल्य जोड़े को स्वयं संग्रहीत करता है। तत्व सम्मिलन एल्गोरिदम सरणी एच की कोशिकाओं को किसी क्रम में तब तक जांचता है जब तक कि पहला मुफ्त सेल नहीं मिल जाता है, जिसमें नया तत्व लिखा जाता है। इस आदेश की गणना मक्खी पर की जाती है, जो चेन के साथ हैश टेबल में आवश्यक पॉइंटर्स के लिए मेमोरी को बचाता है।


संचालन की लागत:

• जोड़ें: Amort.O (1) / O (N)
• reasign: Amort.O (1) / O (N)
• हटाएं: Amort.O (1) / O (N)
• लुकअप: Amort.O (1) / O (N)

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

उदाहरण:
c++: QHash boost::unordered_map/boost::unordered_set (by NickLion )
java: java.util.HashMap<K,V>
c#: System.Collections.Hashtable, System.Collections.Dictionary<K, V>
python: dict
php: array()


3.2 बाइनरी ट्री

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

परिभाषा: बाइनरी ट्री - एक पेड़ जैसी डेटा संरचना जिसमें प्रत्येक नोड में दो से अधिक वंशज (बच्चे) नहीं होते हैं। एक नियम के रूप में, पहले को मूल नोड कहा जाता है, और बच्चों को बाएं और दाएं वारिस कहा जाता है। यदि नोड का कोई वंशज नहीं है, तो इसे पत्ती नोड कहा जाता है।

उदाहरण के लिए, चलो एक द्विआधारी खोज पेड़ लेते हैं: प्रत्येक नोड एक कंटेनर होता है जिसमें तीन तत्व होते हैं: डेटा - वास्तव में संलग्न डेटा (डेटा में तत्व और कुंजी मूल्य दोनों शामिल हैं), बाएं - बाएं अंतर्निहित नोड और दाएं का लिंक - दाएं अंतर्निहित नोड से लिंक। इस स्थिति में, निम्नलिखित नियम पूरा हो गया है: कुंजी [बाएं [X]] <कुंजी [X] [कुंजी [दाईं ओर [X]] - यानी, मूल नोड की डेटा कुंजियाँ बाएं बेटे की डेटा कुंजियों से बड़ी होती हैं और दाईं ओर की डेटा कुंजियों से कम ढीली होती हैं। एक तत्व की खोज करते समय, हम पेड़ के चारों ओर जाते हैं, हर बार वर्तमान नोड की कुंजी के साथ हमारी कुंजी के मूल्य की तुलना करते हैं, और, तुलना के परिणामों के आधार पर, यह निर्धारित करते हुए कि हमें किस रास्ते पर जाना चाहिए। यह गणना करना आसान है कि इस तरह की खोज की जटिलता ओ (लॉगएन) है। एक नया नोड जोड़ते समय, हम एक समान प्रक्रिया करते हैं जब तक कि हम यह नहीं पाते हैं कि नया तत्व कहाँ है। सच है, यह ध्यान दिया जाना चाहिए कि ऐसे पेड़ों को अभी भी संतुलित करने की आवश्यकता है - लेकिन हम पहले से ही इसे छोड़ देंगे। एक जिज्ञासु पाठक स्रोतों की सूची का अध्ययन करके आवश्यक जानकारी प्राप्त करेगा।

संचालन की लागत:

• जोड़ें: Amort.O (lgN)
• reasign: Amort.O (lgN)
• हटाएं: Amort.O (lgN)
• लुकअप: Amort.O (lgN)

उदाहरण:
c++: std::map, std::set
java: java.util.TreeMap<K,V>, java.util.Map<K,V> -
c#: :( SortedDictionary(by NickLion )
python: -
php: -


4. सेट।

तत्वों का अपरिवर्तनीय सेट। सेट को एक बार परिभाषित किया गया है - निर्माण पर, और बाद में तत्वों को केवल पढ़ने के लिए उपयोग प्रदान करता है। एक सेट का विस्तार नहीं किया जा सकता है, जैसे कि उसमें से तत्वों को निकालना या सेट के एक तत्व को बदलना असंभव है। इस संग्रह को लागू करने के लिए आधार के रूप में, एक हैश टेबल आमतौर पर उपयोग किया जाता है, जिसका विवरण ऊपर दिया गया है।

एक सेट केवल एक गणितीय सेट के अमूर्तन का कार्यान्वयन है, अर्थात्। अद्वितीय विशिष्ट तत्वों का एक सेट। ( एटीपी दानली )
उदाहरण:
c++: std::set
java: java.util.Set
C#: System.Collections.HashSet
python: set/frozenset


डेटा संरचनाओं की तुलनात्मक विशेषताएं:


विभिन्न प्रोग्रामिंग भाषाओं में डेटा संरचनाएं:

संदर्भ:

डेटा संरचनाएं (एन)
डेटा संरचनाएं (rus)
बाइनरी सर्च ट्री (एन)
बाइनरी सर्च ट्री (rus)

इसके अलावा, लेखक ने PHP के स्रोत कोड को देखा और एसटीएल पर डॉक पढ़ा।

Upd। हाँ, अजगर के पास एक नियमित अनुक्रमित सरणी (array.array) है। धन्यवाद जादूगर। जैसा कि संशोधित किया गया है, प्रकार आवश्यक रूप से संख्यात्मक नहीं है, प्रकार निर्दिष्ट किया जा सकता है।

Upd। पाठ में बहुत सारे सुधार किए गए हैं। idemura , zibada , tzlom , SiGMan , freeOne , Slaffko , korvindest , Laplace , संपादकों के संपादन के लिए धन्यवाद!

Upd।
जिबदा टिप्पणियों से:
हां, सिर्फ मानचित्र पुनरावृत्ति के विवरण की कमी के कारण, यह आमतौर पर लेख से स्पष्ट नहीं है कि क्यों, ऐसा प्रतीत होता है, जब राख होते हैं तो पेड़ों की आवश्यकता होती है। (O (logN) बनाम O (1))।

उन्हें तब जरूरत होती है, कि आप मानचित्र (या सेट) तत्वों को सूचीबद्ध करना चाहते हैं:
- किसी भी गैर-गारंटीकृत क्रम में (हैशपॉप, कुछ स्क्रिप्टिंग भाषाओं में अंतर्निहित हैश);
- जोड़ने के क्रम में (LinkedHashMap, कुछ अन्य स्क्रिप्टिंग भाषाओं में अंतर्निहित हैश);
- कुंजियों के आरोही क्रम में + दी गई सीमा में केवल कुंजियों को पुनरावृत्त करने की क्षमता।

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