data structures - tutorial - अंदर जाने के लिए सबसे उपयोगी डेटा संरचनाएं क्या हैं?




data structures types (10)

मुझे यह जानने में दिलचस्पी है कि लोग प्रोग्रामिंग में जानने के लिए सबसे उपयोगी डेटा संरचनाओं पर विचार करेंगे। आप हर समय अपने डेटा का उपयोग कैसे कर सकते हैं?

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

प्रत्येक उत्तर केवल एक डेटा संरचना के बारे में होना चाहिए।

ज्ञान और अनुभव के किसी भी मोती के लिए धन्यवाद साझा कर सकते हैं।


डेटा संरचनाओं में से एक मैं सबसे अधिक (वैक्टर से आगे, का उपयोग करता हूं) हैशटेबल है। यदि आप को (1) समय में बड़ी मात्रा में डेटा खोज करने में सक्षम होने की आवश्यकता है, तो इसका मतलब केवल एक ही चुनौती है, इसका मतलब है कि खोज का समय बढ़ने से नहीं बढ़ता क्योंकि संग्रह के आकार बढ़ता है।

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

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

सी # के साथ इसका एक महान कार्यान्वयन Dictionary<keytype, valuetype> और यहां तक ​​कि एक हाइब्रिडएक्टिव है जो कि जब एक हैशटेबल या एक वेक्टर का उपयोग करने का निर्णय करता है किसी भी अच्छी प्रोग्रामिंग पुस्तक का वर्णन है, लेकिन आप विकिपीडिया से अच्छी तरह से सेवा करेंगे: http://en.wikipedia.org/wiki/Hashtable


मुझे नहीं लगता कि एक आंकड़ा है जिसे पता होना चाहिए। प्रत्येक डेटास्ट्रक्चर के पास अपनी संपत्ति है, और एक विशिष्ट समस्या के लिए उपयुक्त है।


मूल सराहना के लिए, आपको कुछ विशिष्ट डेटा प्रकार (सेट, शब्दकोश, आदेश सूची, कतार, स्टैक इत्यादि) के बारे में पता होना चाहिए और प्रत्येक को उनके रिश्तेदार व्यापार-नापसंदों के साथ कार्यान्वित करने के बारे में पता होना चाहिए।

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

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


मैं अपने आप को एसोसिएटिव सरणी का उपयोग करके काफी कुछ ढूँढता हूं, मूलतः सूचकांक के रूप में एक स्ट्रिंग के साथ सरणी।


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


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


मुझे नहीं लगता कि यहाँ एक सामान्य जवाब है। यह कुछ उपयोग के मामले में बाध्य होना चाहिए उदाहरण के लिए, मेरे प्रोग्रामर / प्रबंधक के रूप में 10 से अधिक वर्षों के कैरियर में मैंने कभी द्विआधारी पेड़ का इस्तेमाल नहीं किया है मुझे शक है कि इसका मतलब है कि द्विआधारी पेड़ उपयोगी नहीं हैं, लेकिन कर्नेल और एम्बेडेड दुनिया में लिंक्ड सूची शायद बेहतर फिट बैठती है।
असल में जब मैं कुछ अपवाद छोड़ने के बारे में सोचता हूं तो मैंने केवल साधारण लिंक्ड सूचियों का इस्तेमाल किया था।
और फिर यहां तक ​​कि इसमें एम्बेडेड भी संभवतः न केवल संरचना का इस्तेमाल किया मैं निम्न स्तर के हार्डवेयर प्रोटोकॉल की दुनिया में रह रहा हूं, संभवत: "पहाड़ी ऊपर" और अधिक डेटा संरचना का इस्तेमाल किया ...


लिंक्ड सूचियों के लाभ यह है कि वे नोड्स को जोड़ने / हटाने के लिए बहुत सस्ते हैं। सरणियों के विपरीत [...] उन्हें विस्तार करने पर अधिक मेमोरी की आवश्यकता नहीं होती है।

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

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


ग्राफ एक बहुत शक्तिशाली अनदेखी डेटा संरचना है।

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

मैं एल्गोरिथ्म डिजाइन मैनुअल से रेखांकन के बारे में सीखा, जिसे ब्लॉग पोस्ट में स्टीव येगगे द्वारा सुझाया गया था।


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

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

http://en.wikipedia.org/wiki/Splay_tree





data-structures