डौग लॉयड: तो CS50 में, हम को कवर किया है विभिन्न डेटा संरचनाओं की एक बहुत कुछ है,
है ना?
हम सरणियों देखा है, और जुड़ा हुआ है सूचियों, और हैश टेबल,
और कोशिश करता है, के ढेर और कतारों।
हम भी एक छोटे से सीखना होगा पेड़ और ढेर के बारे में,
लेकिन वास्तव में इन सब सिर्फ अंत एक विषय में बदलाव किया जा रहा है।
वास्तव में कर रहे हैं इन चार बुनियादी विचारों की तरह
और है कि सब कुछ करने के लिए नीचे उबाल कर सकते हैं।
सारणियों, लिंक सूचियों, हैश तालिका, और कोशिश करता है।
और जैसे मैं ने कहा, उन पर बदलाव कर रहे हैं,
लेकिन यह बहुत है बहुत संक्षेप में प्रस्तुत करने जा रहा
सब कुछ हम बात करने जा रहे हैं सी के संदर्भ में इस वर्ग में के बारे में
>> लेकिन कैसे इन सही, सब उपाय करते हैं?
हम पेशेवरों और विपक्ष के बारे में बात की है उन पर अलग वीडियो में प्रत्येक की,
लेकिन संख्या की एक बहुत कुछ है चारों ओर फेंक दिया हो रही है।
सामान्य का एक बहुत कुछ है विचारों के आसपास फेंक दिया हो रही है।
की कोशिश और मजबूत करते हैं यह सिर्फ एक जगह में।
के खिलाफ पेशेवरों तौलना चलो विपक्ष और विचार
जो डेटा संरचना सही डेटा हो सकता है
अपनी विशेष स्थिति के लिए संरचना, डेटा की तरह जो कुछ भी आप भंडारण कर रहे हैं।
तुम जरूरी हमेशा की जरूरत नहीं है सुपर फास्ट प्रविष्टि, हटाने का उपयोग
एक Trie की और देखने अगर आप वास्तव में डालने और हटाने के बारे में परवाह नहीं है
बहुत ज्यादा।
आप बस जल्दी से यादृच्छिक की जरूरत है उपयोग, शायद एक सरणी बेहतर है।
तो चलो कि गढ़ने करते हैं।
के चार में से प्रत्येक के बारे में बात करते हैं डेटा संरचनाओं के प्रमुख प्रकार
हम के बारे में बात की थी, और है कि वे अच्छा हो सकता है, जब सिर्फ देखते हैं,
और जब वे इतना अच्छा नहीं हो सकता है।
तो चलो सरणियों के साथ शुरू करते हैं।
प्रविष्टि तो, उस तरह का बुरा है।
>> एक सरणी के अंत में निवेशन, ठीक है हम जाने के रूप में हम एक सरणी का निर्माण कर रहे हैं।
लेकिन हम डालने की जरूरत है, तो बीच में तत्वों,
प्रविष्टि के लिए वापस लगता है तरह, एक बहुत कुछ है
वहाँ में एक तत्व फिट करने के लिए स्थानांतरण।
और हम डालने के लिए जा रहे हैं यदि हां कहीं भी, लेकिन एक सरणी के अंत में,
कि शायद इतना बड़ा नहीं है।
>> इसी तरह, विलोपन, जब तक कि हम कर रहे हैं एक सरणी के अंत से हटाने,
शायद यह भी है, तो इतना बड़ा नहीं है हम खाली अंतराल छोड़ नहीं करना चाहते हैं,
जो आमतौर पर हम नहीं।
हम एक तत्व को दूर करने के लिए चाहते हैं, और तो एक तरह से इसे फिर से चुस्त बनाने के।
और हां से तत्वों को हटाने एक सरणी भी इतना बड़ा नहीं।
>> देखने का है, हालांकि, महान है।
हम यादृच्छिक उपयोग किया है, लगातार समय देखने।
हम सिर्फ सात कहते हैं, और हम चले सरणी स्थानांतरण से सात।
हम करने के लिए जाने के साथ, 20 का कहना है सरणी स्थानांतरण 20।
हम भर में पुनरावृति करने की जरूरत नहीं है।
वो काफ़ी अच्छा है।
>> सारणियों भी सुलझाने के लिए अपेक्षाकृत आसान कर रहे हैं।
हम एक छँटाई के बारे में बात की थी, हर समय इस तरह के चयन प्रकार के रूप में एल्गोरिथ्म,
प्रविष्टि प्रकार, बुलबुला तरह, विलय तरह, हम हमेशा यह करना सरणियों इस्तेमाल किया,
सरणियों के लिए बहुत आसान कर रहे हैं क्योंकि डाटा संरचनाओं के सापेक्ष तरह,
हम अब तक देखा है।
>> उन्होंने यह भी अपेक्षाकृत छोटे हैं।
अतिरिक्त अंतरिक्ष के एक बहुत कुछ नहीं है।
तुम बस बिल्कुल के रूप में ज्यादा अलग सेट आप अपने डेटा रखने के लिए जरूरत के रूप में,
और बस यही सब है।
तो वे बहुत छोटे हैं और उस रास्ते में कुशल है।
लेकिन एक और नकारात्मक पहलू है, हालांकि, वे आकार में तय कर रहे हैं कि है।
हम वास्तव में कैसे की घोषणा की है बड़े हम, हमारे सरणी होना चाहते हैं
और हम केवल इसे एक शॉट मिलता है।
हम आगे बढ़ने और यह हटना नहीं कर सकते हैं।
>> हम इसे विकसित या हटना करने के लिए जरूरत है, हम एक पूरी तरह से नए सरणी की घोषणा करने की जरूरत है,
के तत्वों के सभी कॉपी दूसरी सरणी में पहली सरणी।
और हम उस आकलन गलत है, तो समय, हम फिर से ऐसा करने की जरूरत है।
इतना महान नहीं।
तो सरणियों हमें लचीलापन देना नहीं है तत्वों के चर संख्या है।
>> एक लिंक सूची के साथ, प्रविष्टि बहुत आसान है।
हम बस सामने पर हमले।
विलोपन भी बहुत आसान है।
हम तत्वों को खोजने के लिए है।
यही कारण है कि कुछ खोज शामिल है।
>> लेकिन अगर आप तत्व पाया है एक बार आप क्या करने की जरूरत है, सभी के लिए देख रहे हैं
एक सूचक परिवर्तन है, संभवतः दो अगर आपके पास
एक एक दोगुना list-- से जुड़े लिंक सूची, rather--
और फिर आप बस नोड मुक्त कर सकते हैं।
आप बदलाव की जरूरत नहीं है चारों ओर सब कुछ।
तुम बस, दो संकेत बदलने तो यह है कि बहुत जल्दी है।
>> देखने का अधिकार है, हालांकि बुरा है?
हमें एक को खोजने के लिए आदेश में एक लिंक सूची में तत्व,
चाहे वह अकेले या दोगुना, लिंक्ड हम यह खोज रैखिक के लिए है।
हम शुरुआत में शुरू कर दिया है और अंत ले जाते हैं, या अंत चाल पर शुरू
शुरुआत तक।
हम अब और रैंडम एक्सेस नहीं है।
हम एक कर रहे हैं तो खोज के बहुत कुछ है, हो सकता है
एक लिंक सूची नहीं है हमारे लिए इतना काफी अच्छा है।
>> वे वास्तव में भी कर रहे हैं सॉर्ट करने के लिए मुश्किल है, है ना?
एक ही तरीका है आप कर सकते हैं वास्तव में एक लिंक की गई सूची को सॉर्ट
आप यह निर्माण के रूप में इसे सुलझाने के लिए है।
लेकिन अगर आप आप के रूप में इसे तरह यदि यह निर्माण, आप नहीं रह रहे हैं
अब जल्दी सम्मिलन बना रही है।
तुम बस टैकिंग नहीं कर रहे हैं सामने पर बातें।
आप खोजने के लिए है सही जगह डाल दिया है,
और फिर अपनी प्रविष्टि बस के बारे में के रूप में बुरा हो जाता है
एक सरणी में डालने के रूप में।
तो लिंक सूचियों नहीं हैं डेटा छँटाई के लिए बहुत अच्छा है।
>> उन्होंने यह भी बहुत छोटा है, आकार के लिहाज से कर रहे हैं।
दोगुना से थोड़ा सूची से जुड़े अकेले लिंक सूचियों से बड़ा,
जो थोड़ा बड़ा कर रहे हैं सरणियों की तुलना में, लेकिन यह नहीं है
बर्बाद अंतरिक्ष की एक बड़ी राशि।
तो अगर अंतरिक्ष एक प्रीमियम पर है, लेकिन नहीं वास्तव में एक तीव्र प्रीमियम,
यह जाने का सही तरीके से हो सकता है।
>> हैश टेबल।
एक हैश तालिका में निवेशन काफी स्पष्ट है।
यह एक दो कदम प्रक्रिया है।
पहले हम के माध्यम से हमारे डेटा चलाने की जरूरत है एक हैश समारोह में एक हैश कोड प्राप्त करने के लिए,
और फिर हम में तत्व सम्मिलित कि हैश कोड स्थान पर हैश तालिका।
>> लिंक सूची के समान विलोपन, आप तत्व मिल एक बार में आसान है।
आप पहली बार इसे खोजने के लिए है लेकिन फिर आप इसे हटाते हैं,
आप बस का आदान-प्रदान करने की जरूरत है संकेत की एक जोड़ी,
यदि आप अलग श्रृंखलन का उपयोग कर रहे हैं।
आप की जांच कर उपयोग कर रहे हैं, या अगर तुम नहीं हो
का उपयोग करने पर सभी श्रृंखलन अपने हैश तालिका में,
विलोपन वास्तव में बहुत आसान है।
आप सब करने की ज़रूरत हैश है डेटा, और फिर उस स्थान पर जाना है।
और यह सोचते हैं आप नहीं करते , किसी भी collisions है
आप बहुत जल्दी नष्ट करने में सक्षम हो जाएगा।
>> अब, देखने जहां चीजें है एक छोटे से अधिक जटिल हो।
यह बेहतर औसत पर है लिंक सूचियों से।
आप श्रृंखलन उपयोग कर रहे हैं, आप अभी भी एक लिंक सूची है,
जो तुम अब भी है, जिसका मतलब खोज एक लिंक सूची हानि।
आप ले जा रहे हैं बल्कि इसलिए कि अपने लिंक सूची और 100 या 1,000 से अधिक तेज
या एन अपने हैश तालिका में तत्वों, आप कर रहे हैं लिंक सूचियों आकार वें सब एक हैं।
वे सब काफी छोटे हैं।
आप n के बजाय सूचियों से जुड़ा हुआ है आकार n में से एक लिंक सूची की।
>> और इसलिए इस वास्तविक दुनिया स्थिरांक आम तौर पर हम जो कारक,
समय जटिलता के बारे में बात नहीं है, यह वास्तव में यहाँ एक फर्क पड़ता है।
तो देखने में अभी भी रैखिक है आप श्रृंखलन उपयोग कर रहे हैं, खोज
लेकिन सूची की लंबाई आप के माध्यम से खोज कर रहे हैं
तुलना से बहुत, बहुत ही कम है।
फिर, छँटाई अपनी है, तो यहाँ लक्ष्य, हैश तालिका
शायद सही तरीके से जाने के लिए नहीं।
छँटाई तो बस एक सरणी का उपयोग आप के लिए वास्तव में महत्वपूर्ण है।
>> और वे आकार की सरगम ​​चला सकते हैं।
यह एक है कि क्या कहना मुश्किल है हैश तालिका, छोटा या बड़ा है
यह सच पर निर्भर करता है क्योंकि कैसे बड़े अपने हैश तालिका है।
आप केवल भंडारण हो जा रहे हैं अपने हैश तालिका में पांच तत्वों,
और आप एक हैश तालिका है उस में 10,000 तत्वों के साथ,
आप शायद अंतरिक्ष के एक बहुत कुछ बर्बाद कर रहे हैं।
इसके विपरीत भी आप कर सकते हैं किया जा रहा है बहुत कॉम्पैक्ट हैश टेबल है
लेकिन छोटे अपने हैश तालिका, हो जाता है उन लिंक सूचियों में से प्रत्येक के लंबे समय तक
हो जाता है।
और तो वास्तव में परिभाषित करने के लिए कोई रास्ता नहीं है क्या वास्तव में एक हैश तालिका के आकार,
लेकिन यह शायद सुरक्षित यह आम तौर पर कहने के लिए
एक लिंक्ड से भी बड़ा होने जा रहा एक ही डेटा भंडारण सूची,
एक Trie से लेकिन छोटे।
>> और कोशिश करता है चौथे कर रहे हैं इन संरचनाओं की
कि हम के बारे में बात कर रहा है।
एक Trie में डालने जटिल है।
गतिशील का एक बहुत कुछ है स्मृति आवंटन,
विशेष रूप से शुरुआत में, आप का निर्माण करने के लिए शुरू कर रहे हैं के रूप में।
लेकिन यह निरंतर समय है।
यह केवल मानवीय तत्व है यहां यह मुश्किल है कि बनाता है।
शून्य सूचक का सामना करने के बाद, malloc अंतरिक्ष, संभवतः malloc जगह नहीं जाना
वहां से फिर से।
की धमकी कारक की तरह गतिशील स्मृति आवंटन में संकेत
स्पष्ट करने बाधा है।
लेकिन आप इसे मंजूरी दे दी है, एक बार प्रविष्टि वास्तव में, काफी सरल आता है
और यह निश्चित रूप से लगातार समय है।
>> विलोपन के लिए आसान है।
आप सब करने की ज़रूरत नीचे नेविगेट है एक संकेत और मुक्त नोड की जोड़ी है,
इसलिए कि बहुत अच्छा है।
देखने का भी बहुत तेज है।
यह केवल पर आधारित है अपने डेटा की लंबाई।
अपने डेटा के सभी है तो अगर पाँच चरित्र तार,
उदाहरण के लिए, यदि आप पाँच भंडारण कर रहे हैं अपने Trie में चरित्र तार,
यह केवल करने के लिए पांच कदम उठा लेता है आप के लिए क्या देख रहे हैं।
पांच तो, सिर्फ एक निरंतर कारक है फिर, प्रविष्टि, हटाने, और देखने
यहां प्रभावी ढंग से, सभी समय लगातार कर रहे हैं।
>> एक और बात अपने Trie है वास्तव में एक तरह से पहले से ही सही, हल?
हम कर रहे हैं कि कैसे के पुण्य से डालने तत्वों,
के पत्र द्वारा पत्र लिए जा रहा द्वारा कुंजी के अंकों द्वारा कुंजी, या अंकों,
आम तौर पर, अपने Trie समाप्त होता जा रहा आप इसे बनाने के रूप में एक तरह से सुलझा लिया।
यह वास्तव में आता नहीं है भावना छँटाई के बारे में सोचने के लिए
उसी तरह से हम के बारे में सोचने यह सरणियों, या लिंक सूचियों के साथ
या हैश टेबल।
लेकिन कुछ समझ में, अपने तुम जाओ के रूप Trie हल है।
>> नकारात्मक पक्ष यह है, ज़ाहिर है, वह यह है कि एक Trie तेजी से बड़ा हो जाता है।
हर जंक्शन बिंदु से, आप कर सकते हैं अपने प्रमुख अंक के होते हैं, तो have--,
आप अन्य 10 है जगहों पर आप जा सकते हैं, जो
हर नोड का मतलब है कि जानकारी शामिल
डेटा के बारे में आप संग्रहीत करना चाहते हैं उस नोड, प्लस 10 संकेत पर।
कौन सा है, CS50 आईडीई पर, 80 बाइट्स है।
तो इसके लिए कम से कम 80 बाइट्स है आप बना सकते हैं कि हर नोड,
और कहा कि यहां तक ​​कि डेटा की गिनती नहीं है।
और अपने नोड्स रहे हैं, तो बजाय अंक के पत्र,
अब आप 26 संकेत है हर स्थान से।
और 26 से 8 बार शायद 200 है बाइट्स, या ऐसा कुछ।
और अगर आप पूंजी है और आप कर सकते हैं lowercase--
मैं इस के साथ जा रहा हूँ, जहां सही, देखते हैं?
अपने नोड्स वास्तव में प्राप्त कर सकते हैं बड़ा है, और इसलिए Trie
ही है, कुल मिलाकर, यह कर सकते हैं भी, सच में बड़े हो जाओ।
अंतरिक्ष में एक उच्च पर है तो अगर आपके सिस्टम पर प्रीमियम,
एक Trie को सही तरीके से नहीं हो सकता है यहां तक ​​कि इसकी अन्य लाभों हालांकि, जाना
आओ, खेल में शामिल हो।
मैं डौग लॉयड हूँ।
इस CS50 है।