1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[संगीत खेल]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> डेविड Malan: यह CS50 है.

5
00:00:14,010 --> 00:00:18,090
और यह शुरुआत है और दोनों है
literally-- लगभग अंत की तरह end--

6
00:00:18,090 --> 00:00:18,825
सप्ताह छह की.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> मुझे लगता है मैं एक हिस्सा था
एक मजेदार तथ्य का छोटा सा.

9
00:00:22,640 --> 00:00:25,370
मैं एक से ऊपर खींच लिया है
पिछले सेमेस्टर के डेटा सेट.

10
00:00:25,370 --> 00:00:29,710
आप हम हर पर आप से पूछना है कि याद कर सकते हैं
पी सेट प्रपत्र आप ऑनलाइन देखा है अगर

11
00:00:29,710 --> 00:00:31,580
या आप व्यक्ति में भाग लिया है.

12
00:00:31,580 --> 00:00:33,020
और यहाँ डेटा है.

13
00:00:33,020 --> 00:00:34,710
तो आज बहुत ज्यादा उम्मीद के मुताबिक था.

14
00:00:34,710 --> 00:00:37,126
लेकिन हम थोड़ा खर्च करना चाहता था
समय के लिए आप के साथ फिर भी.

15
00:00:37,126 --> 00:00:40,599
किसी को क्यों इस अनुमान करना चाहेंगे
ग्राफ, ऊपर नीचे, ऊपर, नीचे तो दांतेदार है

16
00:00:40,599 --> 00:00:41,265
इसलिए लगातार?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
क्या चोटियों में से प्रत्येक करना
और troughs का प्रतिनिधित्व करते हैं?

19
00:00:45,130 --> 00:00:46,005
>> दर्शक: [अश्राव्य]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
डेविड Malan: वास्तव में.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
और अधिक Amusingly, भगवान न करे,
हम शुक्रवार को एक व्याख्यान पकड़

24
00:00:55,480 --> 00:00:58,960
सत्र की शुरुआत में,
कि हम हो क्या देखते है.

25
00:00:58,960 --> 00:01:03,430
तो आज, हम एक बिट में हिस्सा लेना
डेटा संरचनाओं के बारे में अधिक.

26
00:01:03,430 --> 00:01:06,660
और अगर आप एक ठोस का अधिक देने के लिए
पांच में समस्याओं के लिए मानसिक मॉडल,

27
00:01:06,660 --> 00:01:07,450
जो अब बाहर है.

28
00:01:07,450 --> 00:01:10,817
गलतियाँ, जिसमें, हम करेंगे
आप एक पाठ फ़ाइल हाथ कुछ 100,000

29
00:01:10,817 --> 00:01:12,650
प्लस अंग्रेजी शब्द, और
आप के लिए जा रहे हैं

30
00:01:12,650 --> 00:01:17,770
चतुराई से उन्हें लोड करने के लिए बाहर निकालने के लिए
स्मृति में, राम में, कुछ डेटा का उपयोग

31
00:01:17,770 --> 00:01:19,330
अपनी पसंद की संरचना.

32
00:01:19,330 --> 00:01:22,470
>> अब ऐसा ही एक आंकड़ा संरचना सकता है
नहीं होना चाहिए शायद हो, लेकिन,

33
00:01:22,470 --> 00:01:25,630
काफी साधारण लिंक सूची,
जो हम पिछली बार की शुरुआत की.

34
00:01:25,630 --> 00:01:29,220
और एक लिंक सूची में कम से कम था
एक सरणी पर एक फायदा.

35
00:01:29,220 --> 00:01:32,096
एक लाभ के लिए क्या संभावनाएं
यकीनन एक लिंक सूची?

36
00:01:32,096 --> 00:01:32,950
>> दर्शक: निवेशन.

37
00:01:32,950 --> 00:01:33,908
>> डेविड Malan: निवेशन.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
आपको लगता है कि क्या मतलब है?

40
00:01:35,196 --> 00:01:37,872
>> दर्शकों: कहीं भी साथ
सूची [अश्राव्य].

41
00:01:37,872 --> 00:01:38,770
>> डेविड Malan: अच्छा.

42
00:01:38,770 --> 00:01:42,090
तो आप एक तत्व जहाँ भी सम्मिलित कर सकते हैं
आप सूची के बीच में चाहते हैं

43
00:01:42,090 --> 00:01:45,490
कुछ भी फेरबदल करने के लिए बिना,
जो हम अपने छँटाई में निष्कर्ष निकाला

44
00:01:45,490 --> 00:01:47,630
चर्चा, नहीं है
जरूरी नहीं कि एक अच्छी बात है,

45
00:01:47,630 --> 00:01:51,200
यह समय लगता है क्योंकि वास्तव में स्थानांतरित करने के लिए
उन मनुष्यों के सब छोड़ दिया है या सही.

46
00:01:51,200 --> 00:01:55,540
और इसलिए एक लिंक की गई सूची के साथ, आप कर सकते हैं
सिर्फ malloc के साथ आवंटित, एक नया नोड,

47
00:01:55,540 --> 00:01:58,385
और तब के एक जोड़े को अद्यतन
pointers-- दो, तीन आपरेशनों max--

48
00:01:58,385 --> 00:02:01,480
और हम किसी स्लॉट के लिए सक्षम हैं
एक सूची में कहीं भी में.

49
00:02:01,480 --> 00:02:03,550
>> और क्या फायदेमंद था
एक लिंक की गई सूची के बारे में?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
हाँ?

52
00:02:05,659 --> 00:02:06,534
>> दर्शक: [अश्राव्य]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
डेविड Malan: बिल्कुल सही.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
बिल्कुल सही.

57
00:02:11,090 --> 00:02:12,070
यह वास्तव में गतिशील है.

58
00:02:12,070 --> 00:02:15,100
और तुम करने से नहीं कर रहे हैं कि,
अग्रिम में, कुछ निश्चित आकार के लिए

59
00:02:15,100 --> 00:02:18,750
स्मृति का हिस्सा, जैसे तुम होगा
एक सरणी के साथ, उल्टा करने के लिए जो की

60
00:02:18,750 --> 00:02:22,455
आप ही पर नोड्स आवंटित कर सकते हैं
मांग इस तरह के रूप में ही ज्यादा जगह का उपयोग

61
00:02:22,455 --> 00:02:23,330
आप वास्तव में जरूरत के रूप में.

62
00:02:23,330 --> 00:02:26,830
एक सरणी के साथ इसके विपरीत करके, आप कर सकते हैं
गलती से बहुत कम आवंटित.

63
00:02:26,830 --> 00:02:28,871
और फिर यह सिर्फ जा रहा है
गर्दन में दर्द होने की

64
00:02:28,871 --> 00:02:32,440
एक नया बड़ा सरणी reallocate करने के लिए, कॉपी
सब कुछ खत्म हो गया, पुराने सरणी मुक्त

65
00:02:32,440 --> 00:02:33,990
और फिर अपने व्यापार के बारे में कदम.

66
00:02:33,990 --> 00:02:37,479
या बुरा, आप जिस तरह का आवंटन हो सकता है
आप वास्तव में जरूरत से ज्यादा मेमोरी,

67
00:02:37,479 --> 00:02:40,520
और तो आप एक बहुत ही लिए जा रहे हैं
इतनी बात करने के लिए, सरणी कम आबादी.

68
00:02:40,520 --> 00:02:44,350
>> तो एक लिंक सूची इन आप देता है
गतिशीलता और लचीलापन के फायदे

69
00:02:44,350 --> 00:02:46,080
सम्मिलन और विलोपन के साथ.

70
00:02:46,080 --> 00:02:48,000
लेकिन निश्चित रूप से भुगतान एक मूल्य होना चाहिए.

71
00:02:48,000 --> 00:02:50,000
विषयों की वास्तव में, एक
प्रश्नोत्तरी शून्य पर पता लगाया

72
00:02:50,000 --> 00:02:52,430
था व्यापार-नापसंद की एक जोड़ी
हम इस प्रकार अब तक देखा है.

73
00:02:52,430 --> 00:02:56,161
तो एक एक भुगतान की कीमत या क्या है
एक लिंक की गई सूची के नकारात्मक पक्ष?

74
00:02:56,161 --> 00:02:56,660
हाँ.

75
00:02:56,660 --> 00:02:57,560
>> दर्शक: कोई रैंडम एक्सेस.

76
00:02:57,560 --> 00:02:58,809
>> डेविड Malan: नहीं रैंडम एक्सेस.

77
00:02:58,809 --> 00:02:59,540
लेकिन कौन परवाह करता है?

78
00:02:59,540 --> 00:03:01,546
रैंडम एक्सेस सम्मोहक आवाज नहीं करता है.

79
00:03:01,546 --> 00:03:02,421
>> दर्शक: [अश्राव्य]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
डेविड Malan: बिल्कुल.

82
00:03:05,740 --> 00:03:07,580
आप करना चाहते हैं
एक निश्चित algorithm--

83
00:03:07,580 --> 00:03:10,170
और मुझे वास्तव में प्रस्ताव
विशेष रूप से बाइनरी खोज, जो

84
00:03:10,170 --> 00:03:12,600
हम काफी bit-- का उपयोग किया है एक है
आप बिना सोचे समझे नहीं है,

85
00:03:12,600 --> 00:03:15,516
आपको लगता है कि सरल गणित नहीं कर सकते
मध्य तत्व की तरह खोजने की

86
00:03:15,516 --> 00:03:16,530
और इसे ठीक करने के लिए कूद.

87
00:03:16,530 --> 00:03:20,239
आप के बजाय पहली बार में शुरू कर दिया है
तत्व और रैखिक बाएं से खोज

88
00:03:20,239 --> 00:03:22,780
सही करने के लिए आप खोजना चाहते हैं
मध्यम या किसी भी अन्य तत्व.

89
00:03:22,780 --> 00:03:24,410
>> दर्शक: यह शायद अधिक स्मृति लेता है.

90
00:03:24,410 --> 00:03:25,040
>> डेविड Malan: अधिक स्मृति ले जाता है.

91
00:03:25,040 --> 00:03:27,464
कहां कि अतिरिक्त है
स्मृति में से आने वाले खर्च?

92
00:03:27,464 --> 00:03:28,339
>> दर्शक: [अश्राव्य]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
डेविड Malan: बिल्कुल.

95
00:03:33,440 --> 00:03:35,679
यहां इस मामले में, हम था
पूर्णांकों के लिए एक लिंक की गई सूची,

96
00:03:35,679 --> 00:03:37,470
और अभी तक हम दोगुना कर रहे हैं
स्मृति की राशि

97
00:03:37,470 --> 00:03:39,680
हम भी ये संकेत भंडारण के द्वारा की जरूरत है.

98
00:03:39,680 --> 00:03:42,090
के रूप में एक बड़ी बात के अब कम
अपने structs बड़ा हो

99
00:03:42,090 --> 00:03:45,320
और तुम नहीं एक संख्या भंडारण कर रहे हैं लेकिन
शायद एक छात्र या कोई अन्य वस्तु.

100
00:03:45,320 --> 00:03:46,880
लेकिन मुद्दा यह निश्चित रूप से बनी हुई है.

101
00:03:46,880 --> 00:03:49,421
और तो आपरेशनों के एक नंबर
लिंक सूचियों पर बुलाया गया

102
00:03:49,421 --> 00:03:50,570
n-- रेखीय की बड़ी हे थे.

103
00:03:50,570 --> 00:03:54,730
प्रविष्टि या खोज जैसे हालात
या मामला एक तत्व में विलोपन

104
00:03:54,730 --> 00:03:57,720
के बहुत अंत में होने का क्या हुआ
इसे हल या नहीं है कि क्या सूची.

105
00:03:57,720 --> 00:04:01,167
>> कभी कभी तुम भाग्यशाली हो और में हो सकता है
इन कार्यों पर इतनी कम सीमा

106
00:04:01,167 --> 00:04:04,250
अगर तुम भी निरंतर समय हो सकता है
हमेशा पहले तत्व को देख,

107
00:04:04,250 --> 00:04:05,070
उदाहरण के लिए.

108
00:04:05,070 --> 00:04:09,360
लेकिन अंत में, हम वादा किया
होली ग्रेल प्राप्त करने के लिए

109
00:04:09,360 --> 00:04:12,630
डेटा संरचनाओं का, या
कुछ सन्निकटन क्या है,

110
00:04:12,630 --> 00:04:14,290
लगातार समय के माध्यम से.

111
00:04:14,290 --> 00:04:17,579
हम तत्वों को खोजने या तत्व जोड़ सकते हैं
या सूची से तत्वों को दूर?

112
00:04:17,579 --> 00:04:19,059
हम बहुत जल्द ही देखेंगे.

113
00:04:19,059 --> 00:04:21,100
और यह कि एक बाहर जाती है
हम कर रहे हैं तंत्र की

114
00:04:21,100 --> 00:04:23,464
आज का उपयोग करने के लिए शुरू करने जा रहा है,
पी में वार्षिक उपयोग, पांच सेट

115
00:04:23,464 --> 00:04:24,630
वास्तव में बहुत परिचित है.

116
00:04:24,630 --> 00:04:27,430
उदाहरण के लिए, यह एक गुच्छा है अगर
परीक्षा पुस्तकों की, जिनमें से प्रत्येक की

117
00:04:27,430 --> 00:04:29,660
एक छात्र का पहला है
इस पर और अंतिम नाम नाम है,

118
00:04:29,660 --> 00:04:31,820
और मैं उन लोगों से लेने
एक परीक्षा के अंत में,

119
00:04:31,820 --> 00:04:33,746
और वे सभी सुंदर हो
एक यादृच्छिक क्रम में ज्यादा,

120
00:04:33,746 --> 00:04:36,370
और हम छँटाई के बारे में जाना चाहता हूँ
इन परीक्षाओं इतना है कि एक बार श्रेणीबद्ध

121
00:04:36,370 --> 00:04:38,661
यह सिर्फ एक बहुत आसान है और
उन्हें तेजी से वापस बाहर हाथ करने के लिए

122
00:04:38,661 --> 00:04:40,030
वर्णानुक्रम में छात्रों के लिए.

123
00:04:40,030 --> 00:04:42,770
अपने सहज ज्ञान क्या होगा
इस तरह की परीक्षा के एक ढेर के लिए?

124
00:04:42,770 --> 00:04:45,019
>> ठीक है, तुम मुझे पसंद कर रहे हैं, तो आप
इस मीटर है कि देख सकते हैं,

125
00:04:45,019 --> 00:04:48,505
इसलिए मुझे लगता है, की तरह में इस डाल करने के लिए जा रहा हूँ
यह मेरी मेज या मेरी मंजिल जहां अगर

126
00:04:48,505 --> 00:04:50,650
मैं चीजों फैल रहा हूँ
out-- या मेरे सरणी really--

127
00:04:50,650 --> 00:04:52,210
मैं वहाँ में सुश्री के सभी डाल सकता है.

128
00:04:52,210 --> 00:04:52,710
ओह.

129
00:04:52,710 --> 00:04:55,020
यहाँ एक ए तो मैं हो सकता है
यहाँ के रूप में डाल दिया.

130
00:04:55,020 --> 00:04:55,520
ओह.

131
00:04:55,520 --> 00:04:57,980
यहाँ मैं जा रहा हूँ एक और ए है
यहाँ पर डाला कि.

132
00:04:57,980 --> 00:05:02,490
यहाँ एक जेड यहाँ एक और एम और इसलिए है
मैं इस तरह की ढेर बनाना शुरू कर सकता है.

133
00:05:02,490 --> 00:05:06,620
और फिर शायद मैं बाद में जाना चाहते हैं
और तरह की बहुत nitpicky-ly क्रमबद्ध

134
00:05:06,620 --> 00:05:07,710
व्यक्तिगत बवासीर.

135
00:05:07,710 --> 00:05:11,300
लेकिन बात मैं देखना होगा है
मैं हाथ हूँ कि इनपुट पर

136
00:05:11,300 --> 00:05:14,016
और मैं कुछ गणना करना होगा
कि इनपुट के आधार पर निर्णय.

137
00:05:14,016 --> 00:05:15,640
यह एक साथ शुरू होता है, वहाँ पर डाल दिया.

138
00:05:15,640 --> 00:05:18,980
यह जेड के साथ शुरू होता है, इस पर डाल
बीच में वहाँ, और सब कुछ.

139
00:05:18,980 --> 00:05:22,730
>> तो यह है कि एक तकनीक है
आम तौर पर hashing-- एच-ए-एस-H-- के रूप में जाना

140
00:05:22,730 --> 00:05:26,550
जो आम तौर पर के रूप में लेने का मतलब
इनपुट और गणना करने के लिए है कि इनपुट का उपयोग

141
00:05:26,550 --> 00:05:30,940
एक मूल्य, आम तौर पर एक संख्या है, और है कि
नंबर एक भंडारण में सूचकांक है

142
00:05:30,940 --> 00:05:32,260
कंटेनर, एक सरणी की तरह.

143
00:05:32,260 --> 00:05:35,490
तो दूसरे शब्दों में, मैं एक हो सकता है
हैश समारोह, मैं अपने दिमाग में कर के रूप में,

144
00:05:35,490 --> 00:05:37,940
मैं किसी के देखते हैं कि
एक साथ शुरू होता है जो नाम,

145
00:05:37,940 --> 00:05:40,190
मुझे लगता है कि नक्शा करने के लिए जा रहा हूँ
मेरे सिर में शून्य करने के लिए.

146
00:05:40,190 --> 00:05:44,160
मैं जेड के साथ किसी को देखते हैं, मैं हूँ
मेरे सिर में से 25 कि नक्शा करने के लिए जा रहा

147
00:05:44,160 --> 00:05:46,220
और फिर उस में डाल
पिछले सबसे ढेर.

148
00:05:46,220 --> 00:05:50,990
>> अब, अगर आप मेरे मस्तिष्क के बारे में नहीं लगता
लेकिन एक सी कार्यक्रम, क्या संख्या सका

149
00:05:50,990 --> 00:05:53,170
आपको लगता है कि एक ही परिणाम प्राप्त करने पर भरोसा करते हैं?

150
00:05:53,170 --> 00:05:55,594
दूसरे शब्दों में, आप अगर
, ASCII वर्ण एक था

151
00:05:55,594 --> 00:05:57,510
आप कैसे तय करते हैं
क्या बाल्टी में डाल दिया?

152
00:05:57,510 --> 00:05:59,801
आप शायद नहीं करना चाहती
बाल्टी 65, में डाल दिया जो

153
00:05:59,801 --> 00:06:01,840
वहाँ पर तरह होगा
कोई अच्छा कारण के लिए.

154
00:06:01,840 --> 00:06:04,320
जहाँ आप एक डाल करना चाहते हैं
इसके ASCII मूल्य के संदर्भ में?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
कहां आप अपने आस्की लिए क्या करना चाहते हैं
मूल्य एक होशियार बाल्टी के साथ आने की

157
00:06:08,920 --> 00:06:09,480
में डाल दिया?

158
00:06:09,480 --> 00:06:10,206
>> दर्शक: माइनस ए

159
00:06:10,206 --> 00:06:10,956
>> डेविड Malan: हाँ.

160
00:06:10,956 --> 00:06:13,190
तो शून्य से एक या ऋण
विशेष रूप से 65 अगर यह

161
00:06:13,190 --> 00:06:18,240
एक राजधानी ए या 98 अगर
यह एक छोटा अक्षर एक है.

162
00:06:18,240 --> 00:06:21,300
और इसलिए है कि बहुत, हमें करने की अनुमति होगी
बस और बहुत हिसाब,

163
00:06:21,300 --> 00:06:23,260
इस तरह से एक बाल्टी में कुछ डाल दिया.

164
00:06:23,260 --> 00:06:26,010
तो यह है कि हम वास्तव में नहीं पता चला है
इस रूप में अच्छी तरह से भी क्विज़ साथ.

165
00:06:26,010 --> 00:06:29,051
>> तो क्या आप परिक्रमा की याद हो सकता है आपके
कवर पर शिक्षण साथी का नाम.

166
00:06:29,051 --> 00:06:32,270
और TF के नाम का आयोजन किया गया
वर्णानुक्रम इन स्तंभों में,

167
00:06:32,270 --> 00:06:34,400
खैर, यह विश्वास है या नहीं,
जब हम में से सभी 80 प्लस

168
00:06:34,400 --> 00:06:37,800
, ग्रेड के लिए रात को एक साथ मिला
हमारे ग्रेडिंग प्रक्रिया में अंतिम चरण

169
00:06:37,800 --> 00:06:41,830
एक बड़ा में क्विज़ हैश है
[अश्राव्य] पर मंजिल की अंतरिक्ष

170
00:06:41,830 --> 00:06:45,110
और हर किसी की क्विज़ बाहर करना
उनके TF के बिल्कुल क्रम में

171
00:06:45,110 --> 00:06:47,700
कवर पर नाम, क्योंकि
तो यह हमारे लिए एक बहुत आसान है

172
00:06:47,700 --> 00:06:51,290
उस का उपयोग रैखिक के माध्यम से खोज करने के लिए
खोज या चालाकी से किसी तरह

173
00:06:51,290 --> 00:06:54,050
एक TF खोजने के लिए अपने या
उसे छात्रों के क्विज़.

174
00:06:54,050 --> 00:06:56,060
>> हैशिंग की तो इस विचार
आप है देखेंगे कि

175
00:06:56,060 --> 00:07:00,520
काफी शक्तिशाली वास्तव में बहुत है
आम और बहुत ही सहज,

176
00:07:00,520 --> 00:07:03,000
ज्यादा शायद विभाजित तरह और
जीतना सप्ताह शून्य में था.

177
00:07:03,000 --> 00:07:05,250
Hackathon करने के लिए मैं तेजी से आगे
कुछ साल पहले.

178
00:07:05,250 --> 00:07:08,040
इस Zamyla और एक जोड़ी की थी
अन्य स्टाफ ग्रीटिंग छात्रों

179
00:07:08,040 --> 00:07:09,030
वे में आया था.

180
00:07:09,030 --> 00:07:12,680
और हम तह की एक पूरी गुच्छा था
नाम टैग के साथ वहां टेबल.

181
00:07:12,680 --> 00:07:15,380
और हम नाम टैग का आयोजन किया था
साथ वहाँ पर के रूप में पसंद

182
00:07:15,380 --> 00:07:16,690
और वहाँ पर Zs.

183
00:07:16,690 --> 00:07:20,350
और तो TFS की एक बहुत बड़ी चतुराई
निर्देश के रूप में यह लिखा था

184
00:07:20,350 --> 00:07:21,030
दिन के लिए.

185
00:07:21,030 --> 00:07:24,480
और सेमेस्टर इस सप्ताह 12 में
सब सही समझ और हर कोई बना

186
00:07:24,480 --> 00:07:25,310
क्या करना है पता था.

187
00:07:25,310 --> 00:07:27,900
लेकिन कभी भी आपने
उसी तरह पंक्तिबद्ध,

188
00:07:27,900 --> 00:07:30,272
आप को लागू कर रहे हैं
एक हैश की इसी धारणा.

189
00:07:30,272 --> 00:07:31,730
तो चलो यह एक छोटा सा औपचारिक रूप देना.

190
00:07:31,730 --> 00:07:32,890
यहाँ एक सरणी है.

191
00:07:32,890 --> 00:07:36,820
यह एक छोटी होने के लिए तैयार है
विस्तृत सिर्फ नेत्रहीन, दर्शाती,

192
00:07:36,820 --> 00:07:38,920
हम तार डाल सकता है
इस तरह से कुछ में.

193
00:07:38,920 --> 00:07:41,970
और इस सरणी है
स्पष्ट रूप से आकार 26 कुल की.

194
00:07:41,970 --> 00:07:43,935
और बात कहा जाता है
तालिका मनमाने ढंग से.

195
00:07:43,935 --> 00:07:48,930
लेकिन यह सिर्फ एक कलाकार के गायन है
एक हैश तालिका क्या हो सकता है की.

196
00:07:48,930 --> 00:07:52,799
>> तो एक हैश तालिका अब जा रहा है
एक उच्च स्तर डेटा संरचना हो.

197
00:07:52,799 --> 00:07:54,840
दिन के अंत में
हम आपको लगता है कि देखने वाले हो

198
00:07:54,840 --> 00:07:58,700
एक हैश तालिका, लागू कर सकते हैं जो
ज्यादा चेक-इन लाइन की तरह है

199
00:07:58,700 --> 00:08:02,059
ज्यादा इस तरह से एक hackathon पर
तालिका परीक्षा पुस्तकों छंटाई के लिए प्रयोग किया जाता है.

200
00:08:02,059 --> 00:08:03,850
लेकिन एक हैश तालिका है
इस उच्च स्तर की तरह

201
00:08:03,850 --> 00:08:08,250
एक सरणी इस्तेमाल कर सकते हैं कि अवधारणा
, हुड इसे लागू करने के लिए नीचे

202
00:08:08,250 --> 00:08:11,890
या यह एक लंबाई सूची का उपयोग करें, या भी कर सकता है
शायद कुछ अन्य डेटा संरचनाओं.

203
00:08:11,890 --> 00:08:15,590
और अब कि theme-- ले रहा है
इन मौलिक सामग्री के कुछ

204
00:08:15,590 --> 00:08:18,310
एक सरणी और इस इमारत की तरह
एक लंबाई सूची का अब ब्लॉक

205
00:08:18,310 --> 00:08:21,740
और हम निर्माण कर सकते हैं और क्या देख
उन के शीर्ष पर, सामग्री की तरह

206
00:08:21,740 --> 00:08:26,550
एक नुस्खा में, अधिक से अधिक बनाने
रोचक और उपयोगी अंतिम परिणाम है.

207
00:08:26,550 --> 00:08:28,680
>> हैश तालिका के साथ तो
हम इसे लागू हो सकता है

208
00:08:28,680 --> 00:08:32,540
स्मृति में pictorially इस तरह, लेकिन
कैसे यह वास्तव में कोडित किया जा सकता है?

209
00:08:32,540 --> 00:08:33,789
वैसे, शायद बस के रूप में यह है.

210
00:08:33,789 --> 00:08:38,270
सभी टोपियां में क्षमता है, बस है
उदाहरण 26 के लिए कुछ constant--,

211
00:08:38,270 --> 00:08:42,030
alphabet-- के 26 अक्षरों के लिए
मैं अपने चर तालिका फोन हो सकता है,

212
00:08:42,030 --> 00:08:45,630
और मैं मैं करने जा रहा हूँ का दावा है कि हो सकता है
वहाँ, या स्ट्रिंग में चार सितारों डाल दिया.

213
00:08:45,630 --> 00:08:49,880
तो यह रूप में आसान है, तो यह आप के रूप में
एक हैश तालिका को लागू करना चाहते हैं.

214
00:08:49,880 --> 00:08:51,490
और फिर भी, यह वास्तव में सिर्फ एक सरणी है.

215
00:08:51,490 --> 00:08:53,198
लेकिन फिर, एक हैश
तालिका क्या हम हूँ अब है

216
00:08:53,198 --> 00:08:57,470
बस बात ये है कि एक सार डेटा प्रकार कॉल
शीर्ष पर एक वैचारिक layering की तरह

217
00:08:57,470 --> 00:09:00,780
अधिक सांसारिक कुछ की
अब एक सरणी की तरह.

218
00:09:00,780 --> 00:09:02,960
>> अब, हम कैसे जाते हो
समस्याओं को सुलझाने के बारे में?

219
00:09:02,960 --> 00:09:06,980
खैर, पहले मैं लक्जरी था
की यहां काफी टेबल अंतरिक्ष होने

220
00:09:06,980 --> 00:09:09,460
मैं डाल सकता है ताकि
क्विज़ कहीं भी मैं चाहता था.

221
00:09:09,460 --> 00:09:10,620
तो जैसा कि आप यहां जा सकते हैं.

222
00:09:10,620 --> 00:09:12,100
ZS यहां जा सकते हैं.

223
00:09:12,100 --> 00:09:13,230
सुश्री यहां जा सकते हैं.

224
00:09:13,230 --> 00:09:14,740
और फिर मैं कुछ अतिरिक्त स्थान था.

225
00:09:14,740 --> 00:09:18,740
लेकिन यह एक धोखा अधिकार का एक सा है
अब इस तालिका क्योंकि, मैं अगर सच

226
00:09:18,740 --> 00:09:22,720
एक सरणी के रूप में इसके बारे में सोचा, बस है
कुछ निश्चित आकार का होने जा रहा.

227
00:09:22,720 --> 00:09:25,380
>> तो तकनीकी तौर पर, मैं खींच अगर
एक और छात्र की प्रश्नोत्तरी अप

228
00:09:25,380 --> 00:09:28,490
और इस व्यक्ति की, ओह, देखना
नाम, भी एक एक के साथ शुरू होता है

229
00:09:28,490 --> 00:09:30,980
मैं एक तरह से वहाँ यह करना चाहते हैं.

230
00:09:30,980 --> 00:09:34,740
लेकिन जैसे ही मैं अगर, वहाँ इसे डाल के रूप में
इस तालिका वास्तव में एक सरणी का प्रतिनिधित्व करता है,

231
00:09:34,740 --> 00:09:37,840
मैं अधिभावी या clobbering होने जा रहा हूँ
जो कोई भी इस छात्र की प्रश्नोत्तरी है.

232
00:09:37,840 --> 00:09:38,340
है ना?

233
00:09:38,340 --> 00:09:41,972
इस एक सरणी है, तो केवल एक ही बात कर सकते हैं
इन कोशिकाओं या तत्वों में से प्रत्येक में जाना.

234
00:09:41,972 --> 00:09:43,680
और इसलिए मैं एक तरह से है
ले सकते हैं और चयन करने के लिए.

235
00:09:43,680 --> 00:09:45,735
>> अब पहले की तरह मैं
धोखा दिया और इस या मैंने किया

236
00:09:45,735 --> 00:09:47,526
बस की तरह खड़ी
एक दूसरे के ऊपर उन्हें.

237
00:09:47,526 --> 00:09:49,170
लेकिन उस कोड में उड़ान भरने के लिए नहीं जा रहा है.

238
00:09:49,170 --> 00:09:52,260
इसलिए मैं जहां डाल सकता है
जिसका नाम दूसरा छात्र

239
00:09:52,260 --> 00:09:54,964
मैं था यह सब अगर एक है
उपलब्ध मेज अंतरिक्ष?

240
00:09:54,964 --> 00:09:57,880
और मैं तीन स्लॉट और यह प्रयोग किया है
बस कुछ ही दूसरों को वहाँ की तरह लग रहा है.

241
00:09:57,880 --> 00:09:58,959
आप क्या कर सकते थे?

242
00:09:58,959 --> 00:09:59,834
दर्शक: [अश्राव्य]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
डेविड Malan: हाँ.

245
00:10:01,315 --> 00:10:02,370
शायद चलो बस इसे सरल रखने दें.

246
00:10:02,370 --> 00:10:02,660
है ना?

247
00:10:02,660 --> 00:10:04,243
मैं यह करना चाहते हैं जहां यह फिट नहीं है.

248
00:10:04,243 --> 00:10:07,450
इसलिए मैं इसे डाल करने के लिए जा रहा हूँ
तकनीकी रूप से एक बी जाना होगा जहां.

249
00:10:07,450 --> 00:10:09,932
अब, ज़ाहिर है, मैं शुरू कर रहा हूँ
एक कोने में अपने आप को पेंट करने के लिए.

250
00:10:09,932 --> 00:10:11,890
मैं एक छात्र को मिलता है
जिसका नाम वास्तव में बी है,

251
00:10:11,890 --> 00:10:14,840
अब बी एक छोटे से ले जाया जा रहा है
आगे, के रूप में, हां, हो सकता है

252
00:10:14,840 --> 00:10:17,530
इस एक बी है, तो अब यह यहां जाना पड़ता है.

253
00:10:17,530 --> 00:10:20,180
>> और इसलिए यह बहुत जल्दी
, समस्याग्रस्त हो सकता है

254
00:10:20,180 --> 00:10:23,850
लेकिन यह एक तकनीक है कि वास्तव में है
रेखीय की जांच के रूप में जाना जाता है,

255
00:10:23,850 --> 00:10:26,650
जिससे आप बस पर विचार आपके
सरणी रेखा के साथ हो लिए.

256
00:10:26,650 --> 00:10:29,680
और तुम बस तरह की जांच या
प्रत्येक उपलब्ध तत्व का निरीक्षण

257
00:10:29,680 --> 00:10:31,360
एक उपलब्ध मौके की तलाश में.

258
00:10:31,360 --> 00:10:34,010
और जैसे ही आप पाते रूप
एक, तुम वहाँ में ड्रॉप.

259
00:10:34,010 --> 00:10:38,390
>> अब, कीमत अब भुगतान किया जा रहा
इस समाधान के लिए क्या है?

260
00:10:38,390 --> 00:10:41,300
हम एक निश्चित आकार सरणी है,
और मैं नाम सम्मिलित करते

261
00:10:41,300 --> 00:10:44,059
इसे में, कम से कम शुरू में, क्या है
प्रविष्टि का समय चल रहा है

262
00:10:44,059 --> 00:10:46,350
छात्रों को 'डालने के लिए
सही बाल्टी में क्विज़?

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
क्या की बड़ी हे?

265
00:10:50,002 --> 00:10:51,147
>> दर्शकों: एन.

266
00:10:51,147 --> 00:10:52,480
डेविड Malan: मैं n की बड़ी हे सुना.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
यह सही नहीं है.

269
00:10:54,300 --> 00:10:56,490
लेकिन हम अलग तंग करेंगे
क्यों सिर्फ एक पल में.

270
00:10:56,490 --> 00:10:57,702
यह और क्या हो सकता है?

271
00:10:57,702 --> 00:10:58,755
>> दर्शक: [अश्राव्य]

272
00:10:58,755 --> 00:11:00,380
डेविड Malan: और मुझे नेत्रहीन करते हैं.

273
00:11:00,380 --> 00:11:04,720
इसलिए इस पत्र एस लगता है

274
00:11:04,720 --> 00:11:05,604
>> दर्शक: यह एक है.

275
00:11:05,604 --> 00:11:06,520
डेविड Malan: यह एक है.

276
00:11:06,520 --> 00:11:06,710
है ना?

277
00:11:06,710 --> 00:11:08,950
यह एक सरणी, जो
हम यादृच्छिक उपयोग कर सकते है इसका मतलब है.

278
00:11:08,950 --> 00:11:11,790
और हम इस बात का लगता है कि अगर
शून्य और इस रूप में 25 के रूप में,

279
00:11:11,790 --> 00:11:13,800
और हम महसूस करते हैं कि,
ओह, यहाँ अपने इनपुट एस है,

280
00:11:13,800 --> 00:11:16,350
मैं निश्चित रूप से परिवर्तित कर सकते हैं
एस, एक ASCII चरित्र,

281
00:11:16,350 --> 00:11:18,540
एक इसी नंबर करने के लिए
शून्य और 25 के बीच

282
00:11:18,540 --> 00:11:20,910
और फिर तुरंत
जहां यह है डाल दिया.

283
00:11:20,910 --> 00:11:26,120
>> लेकिन ज़ाहिर है, जैसे ही मैं करने के लिए मिल के रूप में
नाम है जो दूसरा व्यक्ति एक या बी या सी है

284
00:11:26,120 --> 00:11:29,300
अंत में, मैं का उपयोग किया है अगर
रेखीय, मेरे समाधान के रूप में की जांच

285
00:11:29,300 --> 00:11:31,360
का समय चल रहा है
सबसे खराब स्थिति में प्रविष्टि

286
00:11:31,360 --> 00:11:33,120
वास्तव में क्या में उतरना जा रहा है?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
और मैं यहाँ यह सुना
सही ढंग से जल्दी पर.

289
00:11:36,045 --> 00:11:36,920
दर्शक: [अश्राव्य]

290
00:11:36,920 --> 00:11:41,620
डेविड Malan: तो यह वास्तव में एक बार n है
आप एक पर्याप्त बड़ी डेटा सेट है.

291
00:11:41,620 --> 00:11:44,410
तो, एक ओर, अगर
आपके सरणी काफी बड़ा है

292
00:11:44,410 --> 00:11:48,287
और आप अपने डेटा, काफी विरल है
इस सुंदर निरंतर समय मिलता है.

293
00:11:48,287 --> 00:11:50,620
लेकिन जैसे ही आप शुरू के रूप में
अधिक से अधिक तत्वों हो रही है,

294
00:11:50,620 --> 00:11:53,200
और सिर्फ सांख्यिकीय आपको मिल
पत्र के साथ अधिक लोग

295
00:11:53,200 --> 00:11:56,030
एक के रूप में उनके नाम या पत्र
बी, यह संभवतः सकता है

296
00:11:56,030 --> 00:11:57,900
कुछ अधिक रैखिक में उतरना.

297
00:11:57,900 --> 00:11:59,640
तो काफी सही नहीं.

298
00:11:59,640 --> 00:12:00,690
इसलिए हम बेहतर कर सकते थे?

299
00:12:00,690 --> 00:12:03,210
>> खैर, क्या थी हमारी
समाधान जब हम पहले

300
00:12:03,210 --> 00:12:06,820
अधिक से अधिक गतिशीलता है चाहता हूँ
एक सरणी की तरह कुछ की अनुमति दी?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
दर्शक: [अश्राव्य]

303
00:12:08,960 --> 00:12:10,030
डेविड Malan: हम क्या परिचय दिया?

304
00:12:10,030 --> 00:12:10,530
हाँ.

305
00:12:10,530 --> 00:12:11,430
तो एक लिंक की गई सूची.

306
00:12:11,430 --> 00:12:14,430
ठीक है, चलो एक लिंक देखते हैं क्या
सूची के बजाय हमारे लिए कर सकता है.

307
00:12:14,430 --> 00:12:17,630
खैर, मुझे लगता है कि हम प्रस्ताव
निम्नानुसार तस्वीर खींचना.

308
00:12:17,630 --> 00:12:19,620
अब यह एक अलग है
एक उदाहरण से तस्वीर

309
00:12:19,620 --> 00:12:24,750
एक अलग पाठ से, वास्तव में, कि
वास्तव में आकार 31 की एक सरणी का उपयोग है.

310
00:12:24,750 --> 00:12:28,220
और इस लेखक बस
तार हैश करने का निर्णय लिया

311
00:12:28,220 --> 00:12:32,430
व्यक्ति के नाम के आधार पर नहीं,
लेकिन उनके birthdates के आधार पर.

312
00:12:32,430 --> 00:12:35,680
चाहे माह की, वे लगा
आप एक महीने की पहली तारीख को पैदा कर रहे हैं अगर

313
00:12:35,680 --> 00:12:39,580
या एक माह की 31, लेखक
कि मूल्य पर आधारित हैश जाएगा,

314
00:12:39,580 --> 00:12:44,154
थोड़ा बाहर नामों का प्रसार करने के लिए इतनी के रूप में
सिर्फ 26 स्पॉट अनुमति दे सकते हैं और अधिक से अधिक.

315
00:12:44,154 --> 00:12:47,320
और शायद यह एक छोटे से अधिक समान है
वर्णमाला पत्र के साथ जा रहा से,

316
00:12:47,320 --> 00:12:50,236
क्योंकि निश्चित रूप से वहाँ शायद
नाम के साथ दुनिया में और अधिक लोगों को

317
00:12:50,236 --> 00:12:54,020
निश्चित रूप से एक साथ कि शुरू
वर्णमाला के कुछ अन्य पत्र.

318
00:12:54,020 --> 00:12:56,380
इसलिए हो सकता है कि यह एक छोटी सी है
अधिक वर्दी, यह सोचते हैं

319
00:12:56,380 --> 00:12:58,640
एक समान वितरण
एक महीने भर में बच्चों की.

320
00:12:58,640 --> 00:12:59,990
>> लेकिन जाहिर है, यह अभी भी अपूर्ण है.

321
00:12:59,990 --> 00:13:00,370
है ना?

322
00:13:00,370 --> 00:13:01,370
हम टकराव हो रही है.

323
00:13:01,370 --> 00:13:04,680
इस में अनेक लोग
डेटा संरचना अभी भी कर रहे हैं

324
00:13:04,680 --> 00:13:08,432
कम से कम एक ही जन्मतिथि होने
आप महीने के चाहे कर रहे हैं.

325
00:13:08,432 --> 00:13:09,640
लेकिन लेखक क्या किया है?

326
00:13:09,640 --> 00:13:13,427
हम एक सरणी है की तरह ठीक है, ऐसा लगता है
खड़ी तैयार की बाएं हाथ की ओर,

327
00:13:13,427 --> 00:13:15,010
लेकिन वह सिर्फ एक कलाकार के गायन है.

328
00:13:15,010 --> 00:13:18,009
यह बात नहीं है क्या दिशा आप
एक सरणी आकर्षित, यह अभी भी एक सरणी है.

329
00:13:18,009 --> 00:13:20,225
जाहिरा तौर पर इस की एक सरणी क्या है?

330
00:13:20,225 --> 00:13:21,500
>> दर्शक: लिंक की गई सूची.

331
00:13:21,500 --> 00:13:21,650
>> डेविड Malan: हाँ.

332
00:13:21,650 --> 00:13:23,490
यह एक ऐसा लगता है
लिंक की गई सूची की सरणी.

333
00:13:23,490 --> 00:13:26,490
तो फिर, की तरह इस मुद्दे पर
अब इन डेटा संरचनाओं का उपयोग करने का

334
00:13:26,490 --> 00:13:28,550
अधिक करने के लिए सामग्री के रूप में
दिलचस्प समाधान,

335
00:13:28,550 --> 00:13:30,862
आप पूरी तरह से एक ले जा सकते हैं
मौलिक, एक सरणी की तरह,

336
00:13:30,862 --> 00:13:33,320
और तो और अधिक कुछ लेना
एक लिंक की गई सूची की तरह दिलचस्प

337
00:13:33,320 --> 00:13:36,660
और यहां तक ​​कि एक भी में उनके गठबंधन
अधिक दिलचस्प आंकड़ा संरचना.

338
00:13:36,660 --> 00:13:39,630
और वास्तव में, यह भी होगा
एक हैश तालिका कहा जा,

339
00:13:39,630 --> 00:13:42,610
जिससे सरणी है
वास्तव में हैश तालिका,

340
00:13:42,610 --> 00:13:45,600
लेकिन उस हैश तालिका है
जंजीरों, तो बात है,

341
00:13:45,600 --> 00:13:50,220
कि विकसित कर सकते हैं या पर आधारित हटना
तत्वों की संख्या आप सम्मिलित करना चाहते हैं.

342
00:13:50,220 --> 00:13:52,990
>> अब, तदनुसार, क्या है
अब समय चल रहा है?

343
00:13:52,990 --> 00:13:58,030
मैं किसी को सम्मिलित करना चाहते हैं
31 अक्टूबर जिसका जन्मदिन है,

344
00:13:58,030 --> 00:13:59,040
जहां वह या वह जाता है?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
ठीक है.

347
00:14:01,030 --> 00:14:02,819
यह 31 कहते हैं जहां बहुत नीचे.

348
00:14:02,819 --> 00:14:03,610
और यह एकदम सही है.

349
00:14:03,610 --> 00:14:05,060
कि लगातार समय था.

350
00:14:05,060 --> 00:14:08,760
लेकिन हम किसी और को क्या लगता है अगर
जिसका जन्मदिन है, चलो देखते है,

351
00:14:08,760 --> 00:14:10,950
अक्टूबर, नवंबर, 31 दिसंबर?

352
00:14:10,950 --> 00:14:12,790
जहां वह या वह जाने के लिए जा रहा है?

353
00:14:12,790 --> 00:14:13,290
वही बात.

354
00:14:13,290 --> 00:14:13,970
हालांकि दो कदम.

355
00:14:13,970 --> 00:14:15,303
यही कारण है कि यह हालांकि स्थिर नहीं है?

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
ठीक है.

358
00:14:16,860 --> 00:14:17,840
फिलहाल यह है.

359
00:14:17,840 --> 00:14:20,570
लेकिन सामान्य स्थिति में,
हम जोड़ने और अधिक लोगों को,

360
00:14:20,570 --> 00:14:23,790
संभवतया, हम जा रहे हैं
अधिक से अधिक टकराव को पाने के लिए.

361
00:14:23,790 --> 00:14:26,820
>> अब यह एक छोटी सी है
बेहतर तकनीकी क्योंकि

362
00:14:26,820 --> 00:14:34,580
अब मेरी जंजीरों में हो सकता है
सबसे खराब स्थिति कब तक?

363
00:14:34,580 --> 00:14:38,890
मैं इस अधिक में एन लोग सम्मिलित हैं
परिष्कृत डेटा संरचना, एन लोग,

364
00:14:38,890 --> 00:14:41,080
सबसे खराब स्थिति में यह पता होने जा रहा है.

365
00:14:41,080 --> 00:14:41,815
क्यों?

366
00:14:41,815 --> 00:14:43,332
>> दर्शक: क्योंकि अगर हर कोई
एक ही जन्मदिन है,

367
00:14:43,332 --> 00:14:44,545
वे एक लाइन होने जा रहे हैं.

368
00:14:44,545 --> 00:14:45,420
डेविड Malan: बिल्कुल सही.

369
00:14:45,420 --> 00:14:47,480
यह एक छोटे से काल्पनिक हो सकता है
लेकिन सही मायने में सबसे खराब स्थिति में,

370
00:14:47,480 --> 00:14:50,117
हर कोई एक ही जन्मदिन है,
आपके पास आदानों दिया,

371
00:14:50,117 --> 00:14:51,950
आप एक के लिए जा रहे हैं
बड़े पैमाने पर लंबी श्रृंखला.

372
00:14:51,950 --> 00:14:54,241
और हां, तो आप इसे एक कह सकते हैं
तालिका हैश, लेकिन वास्तव में यह है

373
00:14:54,241 --> 00:14:56,810
साथ ही एक बड़े पैमाने पर लिंक की गई सूची
बर्बाद अंतरिक्ष की एक पूरी बहुत.

374
00:14:56,810 --> 00:15:00,460
लेकिन सामान्य तौर पर, हम मानते हैं कि अगर
कम से कम जन्मदिन uniform-- हैं

375
00:15:00,460 --> 00:15:01,750
और यह शायद नहीं है.

376
00:15:01,750 --> 00:15:02,587
मुझे लगता है कि ऊपर बना रहा हूँ.

377
00:15:02,587 --> 00:15:04,420
लेकिन हम यह मान हैं, के लिए
चर्चा की खातिर

378
00:15:04,420 --> 00:15:07,717
वे तो सिद्धांत रूप में, अगर हैं कि
इस ऊर्ध्वाधर प्रतिनिधित्व है

379
00:15:07,717 --> 00:15:11,050
सरणी की, वैसे तो उम्मीद है कि आप कर रहे हैं
कर रहे हैं, आप जानते हैं कि चेन पाने के लिए जा रहा है,

380
00:15:11,050 --> 00:15:15,880
मोटे तौर पर एक ही लंबाई जहां से प्रत्येक
इन महीने का एक दिन का प्रतिनिधित्व करता है.

381
00:15:15,880 --> 00:15:19,930
>> महीने में 31 दिन अगर वहाँ अब,
कि वास्तव में मेरे समय चल रहा है इसका मतलब

382
00:15:19,930 --> 00:15:25,230
31 से अधिक एन की बड़ी हे, जो
रैखिक से बेहतर लगता है.

383
00:15:25,230 --> 00:15:27,950
लेकिन एक क्या था हमारे
प्रतिबद्धताओं कुछ हफ़्ते

384
00:15:27,950 --> 00:15:31,145
पहले इसे व्यक्त करने के लिए आया था, जब भी
एक एल्गोरिथ्म का समय चल रहा है?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
बस केवल उच्च क्रम अवधि को देखो.

387
00:15:35,190 --> 00:15:35,690
है ना?

388
00:15:35,690 --> 00:15:37,400
31 निश्चित रूप से उपयोगी है.

389
00:15:37,400 --> 00:15:39,610
लेकिन यह अभी भी एन की बड़ी हे है.

390
00:15:39,610 --> 00:15:41,730
लेकिन विषयों में से एक
की समस्या पाँच सेट

391
00:15:41,730 --> 00:15:43,950
करने के लिए किया जा रहा है
बिल्कुल स्वीकार करते हैं कि,

392
00:15:43,950 --> 00:15:47,320
asymptotically, सैद्धांतिक रूप
इस डेटा संरचना

393
00:15:47,320 --> 00:15:50,470
बस की तुलना में कोई बेहतर है
एक बड़े पैमाने पर लिंक की गई सूची.

394
00:15:50,470 --> 00:15:53,550
और वास्तव में, सबसे खराब स्थिति में, इस
हैश तालिका कि में उतरना हो सकता है.

395
00:15:53,550 --> 00:15:57,620
>> लेकिन असली दुनिया में, हमारे साथ मनुष्य
खुद एमएसीएस या पीसी या जो कुछ भी है कि

396
00:15:57,620 --> 00:16:01,240
और असली दुनिया में चल रहे हैं
वास्तविक दुनिया डेटा पर सॉफ्टवेयर,

397
00:16:01,240 --> 00:16:03,260
जो एल्गोरिथ्म आप पसंद करते जा रहे हैं?

398
00:16:03,260 --> 00:16:09,180
अंत कदम या लेता है कि एक
एन 31 चरणों से विभाजित लेता है एक

399
00:16:09,180 --> 00:16:12,900
डेटा के कुछ टुकड़े को खोजने के लिए या
कुछ जानकारी देखने के लिए?

400
00:16:12,900 --> 00:16:16,580
मैं बिल्कुल 31 बनावट मतलब
असली दुनिया में एक फर्क.

401
00:16:16,580 --> 00:16:18,540
यह 31 गुना तेजी है.

402
00:16:18,540 --> 00:16:20,880
और हम मनुष्यों निश्चित रूप से कर रहे हैं
कि सराहना करने के लिए जा रहा है.

403
00:16:20,880 --> 00:16:23,004
>> तो विरोधाभास का एहसास
वहाँ वास्तव बीच

404
00:16:23,004 --> 00:16:25,920
सैद्धांतिक रूप से चीजों के बारे में बात कर रहे
निश्चित रूप से और asymptotically जो

405
00:16:25,920 --> 00:16:28,760
हमने देखा है के रूप में महत्व है,
लेकिन असली दुनिया में,

406
00:16:28,760 --> 00:16:32,930
तुम सिर्फ बनाने के बारे में परवाह है
सामान्य जानकारी के लिए मानव खुश,

407
00:16:32,930 --> 00:16:36,010
आप बहुत अच्छी तरह से स्वीकार करने के लिए चाहते हो सकता है
हाँ, यह रेखीय है, तथ्य यह है कि,

408
00:16:36,010 --> 00:16:38,360
लेकिन यह 31 गुना तेजी से है
से रेखीय हो सकता है.

409
00:16:38,360 --> 00:16:41,610
और बेहतर अभी तक, हम बस के लिए नहीं है
एक जन्मतिथि तरह मनमाने ढंग से कुछ करना,

410
00:16:41,610 --> 00:16:44,030
हम एक छोटे से खर्च कर सकता है
अधिक समय और चतुराई

411
00:16:44,030 --> 00:16:47,140
और हम क्या कर सकते हैं के बारे में सोचना,
दिए गए एक व्यक्ति का नाम और हो सकता है

412
00:16:47,140 --> 00:16:50,130
उनकी जन्मतिथि उन गठबंधन करने के लिए
सामग्री कुछ समझ

413
00:16:50,130 --> 00:16:52,720
कि सही मायने में अधिक है
वर्दी और कम दांतेदार,

414
00:16:52,720 --> 00:16:56,250
इसलिए इस तस्वीर से बात करने के लिए
वर्तमान में यह हो सकता है पता चलता है.

415
00:16:56,250 --> 00:16:57,750
कैसे हम कोड में इस लागू कर सकता है?

416
00:16:57,750 --> 00:17:00,280
खैर, मुझे लगता है कि हम प्रस्ताव
बस हम है कुछ वाक्य रचना उधार

417
00:17:00,280 --> 00:17:01,799
इस प्रकार अब तक एक दो बार इस्तेमाल किया.

418
00:17:01,799 --> 00:17:03,590
और मैं परिभाषित करने के लिए जा रहा हूँ
एक नोड, जो फिर से

419
00:17:03,590 --> 00:17:06,812
सिर्फ कुछ के लिए एक सामान्य शब्द है
कुछ डेटा संरचना के लिए कंटेनर.

420
00:17:06,812 --> 00:17:09,020
मुझे लगता है कि प्रस्ताव करने जा रहा हूँ
एक स्ट्रिंग वहाँ में जा रहा है.

421
00:17:09,020 --> 00:17:11,369
लेकिन हम लेने शुरू करने जा रहे हैं
अब बंद पहियों प्रशिक्षण उन.

422
00:17:11,369 --> 00:17:13,230
>> कोई और अधिक CS50 पुस्तकालय
वास्तव में, यदि आप चाहते हैं कि जब तक

423
00:17:13,230 --> 00:17:15,230
अपने अंतिम के लिए इसका इस्तेमाल करने के लिए
ठीक है, जो परियोजना,

424
00:17:15,230 --> 00:17:18,569
लेकिन अब हम वापस खींचने के लिए जा रहे हैं
पर्दा है और यह सिर्फ एक चार सितारा है कहना.

425
00:17:18,569 --> 00:17:22,069
शब्द तो वहाँ होने जा रहा है
प्रश्न में उस व्यक्ति का नाम.

426
00:17:22,069 --> 00:17:25,079
और अब मैं एक कड़ी है
यहाँ अगले नोड के लिए

427
00:17:25,079 --> 00:17:28,170
इन प्रतिनिधित्व करते हैं तो
नोड्स के प्रत्येक

428
00:17:28,170 --> 00:17:30,950
श्रृंखला में, संभावित,
एक लिंक की गई सूची की.

429
00:17:30,950 --> 00:17:34,090
>> और अब मैं कैसे घोषित कर
हैश तालिका ही?

430
00:17:34,090 --> 00:17:36,660
कैसे मैं इस पूरे ढांचे की घोषणा करते हैं?

431
00:17:36,660 --> 00:17:40,960
खैर, सच में, बहुत मैं एक सूचक की तरह इस्तेमाल किया
एक सूची का सिर्फ पहला तत्व को

432
00:17:40,960 --> 00:17:44,510
इससे पहले, इसी प्रकार मैं सिर्फ कह सकते हैं
मैं सिर्फ संकेत के एक झुंड की जरूरत

433
00:17:44,510 --> 00:17:46,270
इस पूरे हैश तालिका लागू करने के लिए.

434
00:17:46,270 --> 00:17:49,484
मैं एक सरणी के लिए जा रहा हूँ
हैश तालिका के लिए कहा जाता है मेज.

435
00:17:49,484 --> 00:17:50,900
यह आकार क्षमता का होने जा रहा है.

436
00:17:50,900 --> 00:17:52,525
यह बात में फिट कर सकते हैं कि कितने तत्व है.

437
00:17:52,525 --> 00:17:56,180
और इस में उन तत्वों में से प्रत्येक
सरणी एक नोड स्टार होने जा रहा है.

438
00:17:56,180 --> 00:17:56,810
क्यों?

439
00:17:56,810 --> 00:18:00,160
खैर, इस तस्वीर प्रति, मैं क्या कर रहा हूँ
हैश तालिका के रूप में लागू करने

440
00:18:00,160 --> 00:18:04,330
प्रभावी रूप में शुरुआत ही है
हम खड़ी खींचा है कि इस सरणी,

441
00:18:04,330 --> 00:18:06,820
जिसका चौकों की प्रत्येक
एक सूचक का प्रतिनिधित्व करता है.

442
00:18:06,820 --> 00:18:09,170
लोगों कि स्लैश है कि
उन के माध्यम से अभी रिक्त हैं.

443
00:18:09,170 --> 00:18:11,410
और लोगों को लगता है कि
सही करने के लिए जा रहा तीर

444
00:18:11,410 --> 00:18:16,140
वास्तविक नोड्स के लिए वास्तविक संकेत दिए गए हैं,
एक लिंक की गई सूची की शुरुआत इसलिये.

445
00:18:16,140 --> 00:18:19,050
>> यहाँ तो, फिर, हम कैसे हो सकता है
एक हैश तालिका लागू

446
00:18:19,050 --> 00:18:21,580
अलग श्रृंखलन लागू करता है.

447
00:18:21,580 --> 00:18:22,840
अब हम बेहतर कर सकते हैं?

448
00:18:22,840 --> 00:18:25,632
सब ठीक है मैं पिछली बार वादा किया था कि
हम लगातार समय को प्राप्त कर सकता है.

449
00:18:25,632 --> 00:18:27,381
और मैं एक तरह से आप दिया
यहां लगातार समय,

450
00:18:27,381 --> 00:18:29,850
लेकिन तब वास्तव में नहीं कहा
लगातार समय यह अभी भी है क्योंकि

451
00:18:29,850 --> 00:18:31,890
कुल पर निर्भर
तत्वों की संख्या

452
00:18:31,890 --> 00:18:34,500
आप में inputting रहे
डेटा संरचना.

453
00:18:34,500 --> 00:18:35,980
लेकिन हम यह किया है लगता है.

454
00:18:35,980 --> 00:18:39,550
मुझे यहाँ पर स्क्रीन करने के लिए वापस जाओ.

455
00:18:39,550 --> 00:18:44,520
, मुझे भी यहाँ इस परियोजना स्पष्ट करते हैं
स्क्रीन, और मैं इस किया था लगता है.

456
00:18:44,520 --> 00:18:49,300
मैं नाम सम्मिलित करने के लिए चाहता था मान लीजिए
दावेन में मेरे डेटा संरचना में.

457
00:18:49,300 --> 00:18:52,100
>> तो मैं एक स्ट्रिंग सम्मिलित करना चाहते हैं
डेटा संरचना में दावेन.

458
00:18:52,100 --> 00:18:54,370
क्या मैं एक प्रयोग नहीं करते
तालिका हैश, लेकिन मैं प्रयोग

459
00:18:54,370 --> 00:18:56,980
अधिक है कि कुछ पेड़ की तरह
एक परिवार के पेड़, जहां की तरह

460
00:18:56,980 --> 00:18:59,670
आप में से कुछ जड़ है
शीर्ष और फिर नोड्स और पत्तियों

461
00:18:59,670 --> 00:19:01,440
कि नीचे और जावक जाना.

462
00:19:01,440 --> 00:19:04,450
, तो वह मुझे लगता है
दावेन के सम्मिलित करना चाहते हैं

463
00:19:04,450 --> 00:19:06,430
वर्तमान में एक खाली सूची है क्या में.

464
00:19:06,430 --> 00:19:09,780
मैं निम्न करने के लिए जा रहा हूँ: मैं कर रहा हूँ
इस परिवार में एक नोड बनाने के लिए जा रहा

465
00:19:09,780 --> 00:19:15,170
पेड़ की तरह डेटा संरचना लग रहा है कि
एक छोटे से इस तरह, जिनमें से प्रत्येक की

466
00:19:15,170 --> 00:19:19,640
आयतों, हम कहते हैं, किया गया है
इसमें अब 26 तत्वों के लिए.

467
00:19:19,640 --> 00:19:21,650
और कोशिकाओं के प्रत्येक
इस सरणी में जा रहा है

468
00:19:21,650 --> 00:19:23,470
एक वर्णमाला के अक्षर प्रतिनिधित्व करने के लिए.

469
00:19:23,470 --> 00:19:28,190
>> विशेष रूप से, मैं इलाज के लिए जा रहा हूँ
यह एक, फिर बी, तो सी, तो विकास है

470
00:19:28,190 --> 00:19:29,310
यहाँ इस एक.

471
00:19:29,310 --> 00:19:32,940
तो यह प्रभावी ढंग से करने जा रहा है
अक्षर डी का प्रतिनिधित्व

472
00:19:32,940 --> 00:19:36,040
लेकिन दावेन के सभी सम्मिलित करने के लिए
मैं थोड़ा और अधिक करने की ज़रूरत नाम है.

473
00:19:36,040 --> 00:19:37,840
तो मैं पहले तो बात करने के हैश करने के लिए जा रहा हूँ.

474
00:19:37,840 --> 00:19:41,049
मैं पहले अक्षर को देखने के लिए जा रहा हूँ
में दावेन का स्पष्ट रूप से एक विकास है, जो

475
00:19:41,049 --> 00:19:42,840
और मैं आवंटित करने के लिए जा रहा हूँ
लग रहा है कि एक नोड

476
00:19:42,840 --> 00:19:45,570
जैसे बड़े एक बड़ा आयत this--
पूरी वर्णमाला फिट करने के लिए पर्याप्त है.

477
00:19:45,570 --> 00:19:47,140
>> अब विकास किया जाता है.

478
00:19:47,140 --> 00:19:49,720
अब ए डी-ए-वी-ई-एन लक्ष्य है.

479
00:19:49,720 --> 00:19:51,220
तो अब मैं क्या करने जा रहा हूँ क्या है.

480
00:19:51,220 --> 00:19:54,027
जैसे ही मैं डी नोटिस शुरू
वहाँ कोई सूचक नहीं है.

481
00:19:54,027 --> 00:19:56,860
यह क्षण में कचरा मूल्यों है
या मैं अशक्त करने के लिए यह को प्रारंभ हो सकता है.

482
00:19:56,860 --> 00:19:59,630
लेकिन मेरे साथ जा रहा रखने के चलो
एक पेड़ के निर्माण के इस विचार.

483
00:19:59,630 --> 00:20:04,260
मुझे इनमें से एक दूसरे का आवंटन करते हैं
इसमें 26 तत्व है कि नोड्स.

484
00:20:04,260 --> 00:20:05,150
>> और तुम जानते हो क्या?

485
00:20:05,150 --> 00:20:09,130
इस स्मृति में सिर्फ एक नोड है कि
मैं एक संरचना का उपयोग, malloc के साथ बनाया

486
00:20:09,130 --> 00:20:11,240
हम जल्द ही देखेंगे के रूप में,
मैं this-- क्या करने जा रहा हूँ

487
00:20:11,240 --> 00:20:14,450
मैं से एक तीर आकर्षित करने के लिए जा रहा हूँ
नीचे डी प्रतिनिधित्व कि बात

488
00:20:14,450 --> 00:20:15,860
इस नए नोड के लिए.

489
00:20:15,860 --> 00:20:19,240
और, पहले अगले अब
दावेन के नाम पत्र,

490
00:20:19,240 --> 00:20:24,150
V-- डी-ए-V-- मैं आगे जाने के लिए जा रहा हूँ
और इस तरह एक और नोड आकर्षित,

491
00:20:24,150 --> 00:20:30,150
जिससे, यहाँ वी तत्व, जो
हम instance-- वूप्स के लिए आकर्षित करेंगे.

492
00:20:30,150 --> 00:20:31,020
हम वहाँ आकर्षित नहीं होगा.

493
00:20:31,020 --> 00:20:31,936
यह यहां जाने के लिए जा रहा है.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> तो फिर हम करने जा रहे हैं
इस वी हो विचार

496
00:20:35,712 --> 00:20:44,920
और फिर यहाँ नीचे हम सूचकांक करने के लिए जा रहे हैं
नीचे वी से हम ई पर विचार करेंगे कि क्या में

497
00:20:44,920 --> 00:20:50,100
और फिर यहाँ से हम जा रहे हैं
यहां इन नोड्स में से एक है जाना.

498
00:20:50,100 --> 00:20:52,930
और अब हम जवाब देने के लिए एक सवाल है.

499
00:20:52,930 --> 00:20:57,840
मैं संकेत मिलता है कि किसी भी तरह करने की जरूरत है
हम स्ट्रिंग दावेन के अंत में कर रहे हैं.

500
00:20:57,840 --> 00:20:59,490
इसलिए मैं सिर्फ यह शून्य छोड़ सकता है.

501
00:20:59,490 --> 00:21:02,670
>> लेकिन हम दावेन का क्या है अगर
भी पूरा नाम, जो

502
00:21:02,670 --> 00:21:04,280
हम, डेवनपोर्ट ने कहा है, के रूप में है?

503
00:21:04,280 --> 00:21:06,970
तो दावेन क्या है अगर
वास्तव में एक substring,

504
00:21:06,970 --> 00:21:08,960
एक बहुत लंबे समय तक तार का एक उपसर्ग?

505
00:21:08,960 --> 00:21:11,450
हम सिर्फ स्थायी रूप से नहीं कर सकते
कुछ भी नहीं हो रहा है कहना

506
00:21:11,450 --> 00:21:14,410
क्योंकि हम कर सकते थे, वहाँ जाने के लिए
डेवनपोर्ट की तरह एक शब्द डालने कभी नहीं

507
00:21:14,410 --> 00:21:15,840
इस डेटा संरचना में

508
00:21:15,840 --> 00:21:19,560
>> तो हम क्या कर सकता है बजाय है
इन तत्वों में से प्रत्येक का इलाज

509
00:21:19,560 --> 00:21:22,170
के रूप में शायद दो होने
उनमें से अंदर तत्वों.

510
00:21:22,170 --> 00:21:24,810
एक, वास्तव में, एक सूचक है
के रूप में मैं कर रहा हूँ.

511
00:21:24,810 --> 00:21:27,100
इन बक्सों में से प्रत्येक तो
सिर्फ एक सेल नहीं है.

512
00:21:27,100 --> 00:21:29,855
लेकिन क्या अगर शीर्ष
one-- नीचे एक

513
00:21:29,855 --> 00:21:32,230
क्योंकि, अशक्त होने जा रहा
बस अभी तक कोई डेवनपोर्ट है.

514
00:21:32,230 --> 00:21:34,197
क्या अगर ऊपर एक
कुछ विशेष मूल्य है?

515
00:21:34,197 --> 00:21:36,530
और यह एक छोटे होने जा रहा है
यह इस आकार आकर्षित करने के लिए कठिन.

516
00:21:36,530 --> 00:21:38,130
लेकिन यह सिर्फ एक जाँच चिह्न है लगता है.

517
00:21:38,130 --> 00:21:38,920
जाँच करें.

518
00:21:38,920 --> 00:21:44,230
डी-ए-वी-ई-एन एक स्ट्रिंग है
इस डेटा संरचना में.

519
00:21:44,230 --> 00:21:48,350
>> इस बीच, अगर मैं और अधिक स्थान था
यहां, मैं, पी-ओ-आर-टी कर सकता है

520
00:21:48,350 --> 00:21:52,650
और मैं नोड में चेक डाल सकता है
कि बहुत अंत में पत्र टी है.

521
00:21:52,650 --> 00:21:55,460
तो यह एक बड़े पैमाने पर है
जटिल दिखने डेटा संरचना.

522
00:21:55,460 --> 00:21:57,210
और मेरी लिखावट
निश्चित रूप से मदद नहीं करता है.

523
00:21:57,210 --> 00:22:00,043
लेकिन मैं कुछ डालने के लिए चाहता था
वरना, हम क्या करना होगा पर विचार करें.

524
00:22:00,043 --> 00:22:03,370
हम में दाऊद डाल करना चाहता था,
हम एक ही तर्क, डी-ए-वी का पालन करता हूं

525
00:22:03,370 --> 00:22:08,802
लेकिन अब मैं अगले में बात करेंगे
तत्व नहीं ई से, लेकिन मैं से डी के लिए

526
00:22:08,802 --> 00:22:10,760
इसलिए होने जा रहा है
इस पेड़ में अधिक नोड्स.

527
00:22:10,760 --> 00:22:12,325
हम अधिक कॉल malloc के लिए जा रहे हैं.

528
00:22:12,325 --> 00:22:14,700
लेकिन मैं एक बनाने के लिए नहीं करना चाहती
इस तस्वीर की पूरी गंदगी.

529
00:22:14,700 --> 00:22:17,710
तो चलो बजाय एक को देखो
कि पूर्व तैयार की गई है

530
00:22:17,710 --> 00:22:21,810
डॉट नहीं के साथ इस तरह, डॉट,
डॉट्स, लेकिन सिर्फ संक्षिप्त सरणियों.

531
00:22:21,810 --> 00:22:23,950
लेकिन नोड्स के प्रत्येक
यहाँ इस पेड़ में

532
00:22:23,950 --> 00:22:26,700
एक ही thing-- का प्रतिनिधित्व करता है
एक सरणी आकार 26 के रे.

533
00:22:26,700 --> 00:22:28,860
>> या हम होना चाहते हैं
वास्तव में उचित अब, क्या

534
00:22:28,860 --> 00:22:30,790
किसी के नाम के रूप में अगर
एक apostrophe, चलो

535
00:22:30,790 --> 00:22:35,560
प्रत्येक नोड वास्तव में है कि मान
इसमें 27 सूचकांकों में न सिर्फ 26 की तरह.

536
00:22:35,560 --> 00:22:42,020
तो यह अब एक डेटा होने जा रहा है
संरचना एक trie-- टी आर-मैं-ई बुलाया.

537
00:22:42,020 --> 00:22:46,120
माना जाता है कि जो एक Trie,
एक पेड़ के लिए ऐतिहासिक एक चालाक नाम

538
00:22:46,120 --> 00:22:49,040
उस के लिए अनुकूलित है
पुनः प्राप्ति, जो जाहिर है,

539
00:22:49,040 --> 00:22:50,870
यह Trie है तो एक मैं-ई के साथ वर्तनी है.

540
00:22:50,870 --> 00:22:52,710
लेकिन उस Trie का इतिहास है.

541
00:22:52,710 --> 00:22:55,860
>> तो एक Trie इस पेड़ की तरह डेटा है
एक परिवार के पेड़ की तरह संरचना

542
00:22:55,860 --> 00:22:57,510
कि अंततः उस तरह बर्ताव करती है.

543
00:22:57,510 --> 00:23:00,890
और यहाँ एक की सिर्फ एक उदाहरण है
अन्य लोगों के नाम की पूरी गुच्छा.

544
00:23:00,890 --> 00:23:03,540
लेकिन अब सवाल
हाथ में क्या है

545
00:23:03,540 --> 00:23:08,070
हम यकीनन एक अधिक शुरू करने से प्राप्त की
जटिल डेटा संरचना, और एक,

546
00:23:08,070 --> 00:23:09,870
सच कहूँ, कि स्मृति का एक बहुत का उपयोग करता है.

547
00:23:09,870 --> 00:23:11,703
>> , क्योंकि भले ही
फिलहाल, मैं ही हूँ

548
00:23:11,703 --> 00:23:15,050
डी एस सूचक का उपयोग और
एक वी और तों और एनएस, और

549
00:23:15,050 --> 00:23:16,700
मैं स्मृति की बहुत की एक बिल्ली बर्बाद कर रहा हूँ.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
लेकिन मैं एक संसाधन खर्च जहां,
मैं वापस एक और लाभ करते हैं.

552
00:23:22,660 --> 00:23:26,020
, मैं और अधिक स्थान खर्च कर रहा हूँ तो अगर
शायद आशा क्या है?

553
00:23:26,020 --> 00:23:27,407
मैं क्या कम खर्च कर रहा हूँ कि?

554
00:23:27,407 --> 00:23:28,240
दर्शक: कम समय.

555
00:23:28,240 --> 00:23:28,990
डेविड Malan: समय.

556
00:23:28,990 --> 00:23:30,320
अब यही वजह है कि हो सकता है?

557
00:23:30,320 --> 00:23:33,880
खैर, सम्मिलन क्या है
समय, अब बड़ी हे के संदर्भ में,

558
00:23:33,880 --> 00:23:37,660
दावेन की तरह एक नाम का
या डेवनपोर्ट या दाऊद?

559
00:23:37,660 --> 00:23:39,340
खैर, दावेन पांच कदम था.

560
00:23:39,340 --> 00:23:42,350
डेवनपोर्ट नौ कदम होगा,
तो यह कुछ और कदम होगा.

561
00:23:42,350 --> 00:23:44,250
डेविड के रूप में अच्छी तरह से पांच कदम होगा.

562
00:23:44,250 --> 00:23:47,230
तो उन ठोस हैं
संख्या, लेकिन निश्चित रूप से नहीं है

563
00:23:47,230 --> 00:23:49,550
पर एक ऊपरी बाध्य
किसी के नाम की लंबाई.

564
00:23:49,550 --> 00:23:52,240
और वास्तव में, समस्या में
पांच विनिर्देश के सेट,

565
00:23:52,240 --> 00:23:54,050
हम प्रस्ताव करने जा रहे हैं
यह कुछ ऐसा है कि

566
00:23:54,050 --> 00:23:55,470
कि 40-कुछ-अजीब अक्षर है.

567
00:23:55,470 --> 00:23:58,180
>> वास्तविक, कोई नहीं है
एक असीम लंबे नाम,

568
00:23:58,180 --> 00:24:01,542
कहने के लिए है जो कि एक की लंबाई
नाम या एक स्ट्रिंग की लंबाई हम हो सकता है

569
00:24:01,542 --> 00:24:03,750
राज्य के कुछ है
संरचना यकीनन क्या है?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
यह निरंतर है.

572
00:24:06,250 --> 00:24:06,430
है ना?

573
00:24:06,430 --> 00:24:09,310
यह की तरह एक बड़ा स्थिर हो सकता है
40-कुछ है, लेकिन यह स्थिर है.

574
00:24:09,310 --> 00:24:13,752
और यह कितने पर कोई निर्भरता है
अन्य नामों इस डेटा संरचना में हैं.

575
00:24:13,752 --> 00:24:15,460
दूसरे शब्दों में, मैं अगर
अब सम्मिलित करना चाहता था

576
00:24:15,460 --> 00:24:20,540
कोल्टन या गेब्रियल या लूटने या Zamyla या
एलिसन या बेलिंडा या किसी अन्य के नाम

577
00:24:20,540 --> 00:24:23,940
इस डेटा में स्टाफ से
संरचना, समय चल रहा है

578
00:24:23,940 --> 00:24:26,750
के अन्य नामों में डालने
सभी प्रभावित पर होने जा रहा

579
00:24:26,750 --> 00:24:30,220
कितने अन्य तत्वों से कर रहे हैं
पहले से ही डेटा संरचना में?

580
00:24:30,220 --> 00:24:31,040
यह.

581
00:24:31,040 --> 00:24:31,540
है ना?

582
00:24:31,540 --> 00:24:36,150
हम प्रभावी रूप से उपयोग कर रहे हैं क्योंकि
इस बहु परत हैश तालिका.

583
00:24:36,150 --> 00:24:38,280
और का समय चल रहा है
इन कार्यों के किसी भी

584
00:24:38,280 --> 00:24:41,510
की संख्या पर निर्भर नहीं है
डेटा संरचना में हैं कि तत्वों

585
00:24:41,510 --> 00:24:43,090
या कि अंततः जा रहे हैं
डेटा संरचना में होना,

586
00:24:43,090 --> 00:24:44,714
लेकिन क्या विशेष रूप से की लंबाई पर?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> किया जा रहा स्ट्रिंग
डाला पड़ता है जो

589
00:24:49,200 --> 00:24:52,580
इस asymptotically स्थिर
एक के time-- बड़ी हे.

590
00:24:52,580 --> 00:24:54,720
और सच कहूँ तो, बस में
असली दुनिया, इस

591
00:24:54,720 --> 00:24:58,380
दावेन का नाम लेता डालने का मतलब
पांच चरणों, या डेवनपोर्ट नौ तरह

592
00:24:58,380 --> 00:25:00,100
कदम, या डेविड पांच चरणों.

593
00:25:00,100 --> 00:25:03,071
वह सुंदर रफ़ू छोटे चल टाइम्स है.

594
00:25:03,071 --> 00:25:05,320
और, वास्तव में, कि एक बहुत है
अच्छी बात है, विशेष रूप से जब

595
00:25:05,320 --> 00:25:08,126
यह कुल पर निर्भर नहीं है
वहाँ में तत्वों की संख्या.

596
00:25:08,126 --> 00:25:10,500
इसलिए हम यह लागू कैसे हो सकता है
कोड में संरचना की तरह?

597
00:25:10,500 --> 00:25:12,900
यह एक छोटे से अधिक है
जटिल है, लेकिन अभी भी यह बात है

598
00:25:12,900 --> 00:25:15,050
सिर्फ एक आवेदन
बुनियादी इमारत ब्लॉकों.

599
00:25:15,050 --> 00:25:17,830
मैं फिर से परिभाषित करने के लिए जा रहा हूँ
हमें नोड इस प्रकार है:

600
00:25:17,830 --> 00:25:21,100
bool word-- कहा जाता है और इस
कुछ भी कहा जा सकता है.

601
00:25:21,100 --> 00:25:23,970
लेकिन bool का प्रतिनिधित्व करता है
क्या मैं एक जाँच चिह्न के रूप में आकर्षित किया.

602
00:25:23,970 --> 00:25:24,490
हां.

603
00:25:24,490 --> 00:25:26,720
यह एक स्ट्रिंग के अंत है
इस डेटा संरचना में.

604
00:25:26,720 --> 00:25:30,702
>> और जाहिर है, नोड सितारा
बच्चों को वहाँ बात कर रहा है.

605
00:25:30,702 --> 00:25:32,410
और, वास्तव में, सिर्फ पसंद
एक परिवार के पेड़, आप

606
00:25:32,410 --> 00:25:34,370
नोड्स पर विचार करेंगे
कि बंद लटक रहे हैं

607
00:25:34,370 --> 00:25:36,920
कुछ माता पिता के नीचे का
तत्व बच्चों के होने के लिए.

608
00:25:36,920 --> 00:25:40,510
और इसलिए बच्चों के लिए जा रहा है
27 की एक सरणी, 27 से एक हो

609
00:25:40,510 --> 00:25:41,680
बस apostrophe के लिए किया जा रहा है.

610
00:25:41,680 --> 00:25:43,390
हम की तरह करने के लिए जा रहे हैं
विशेष मामला है कि के.

611
00:25:43,390 --> 00:25:45,400
तो अगर आप कुछ कर सकते हैं
apostrophes के साथ नाम.

612
00:25:45,400 --> 00:25:47,399
शायद यह भी हाइफन चाहिए
वहाँ में जाना है, लेकिन तुम हूँ

613
00:25:47,399 --> 00:25:50,330
पी सेट 5 हम केवल ध्यान में देखते हैं
पत्र और apostrophes के बारे में.

614
00:25:50,330 --> 00:25:52,990
>> और फिर कैसे आप का प्रतिनिधित्व करते हैं
डेटा संरचना ही?

615
00:25:52,990 --> 00:25:56,454
कैसे आप रूट का प्रतिनिधित्व करते हैं
इस Trie की, तो बात करने के लिए?

616
00:25:56,454 --> 00:25:59,620
खैर, सिर्फ तुम, एक लिंक की गई सूची के साथ पसंद
पहले तत्व के लिए एक संकेत की जरूरत है.

617
00:25:59,620 --> 00:26:04,270
एक Trie के साथ आप सिर्फ एक की जरूरत
इस Trie के रूट के लिए सूचक.

618
00:26:04,270 --> 00:26:07,290
और वहाँ से आप हैश कर सकते हैं
अपने रास्ते नीचे गहरे और गहरे

619
00:26:07,290 --> 00:26:10,460
संरचना में हर दूसरे नोड के लिए.

620
00:26:10,460 --> 00:26:13,440
तो बस यह कर सकते हैं साथ
हम उस संरचना का प्रतिनिधित्व करते हैं.

621
00:26:13,440 --> 00:26:15,877
>> अब, ओह प्रश्न Meanwhile--.

622
00:26:15,877 --> 00:26:17,220
>> दर्शक: bool शब्द क्या है?

623
00:26:17,220 --> 00:26:20,490
>> डेविड Malan: bool शब्द है
सिर्फ इस सी अवतार

624
00:26:20,490 --> 00:26:22,920
मैं क्या वर्णित की
यहाँ, जब इस बॉक्स में

625
00:26:22,920 --> 00:26:26,000
मैं के प्रत्येक बंटवारे शुरू
दो टुकड़ों में सरणी के तत्वों.

626
00:26:26,000 --> 00:26:27,600
एक अगले नोड के लिए एक संकेत है.

627
00:26:27,600 --> 00:26:30,280
अन्य हो गया है
एक चेक बॉक्स की तरह कुछ

628
00:26:30,280 --> 00:26:33,770
एक वहाँ है, हाँ कहने के लिए
यहाँ समाप्त होती है कि दावेन शब्द,

629
00:26:33,770 --> 00:26:35,610
, हम नहीं चाहते क्योंकि
पल, डेव पर.

630
00:26:35,610 --> 00:26:39,320
>> डेव एक होने जा रहा है हालांकि
वैध शब्द है, वह Trie में नहीं है

631
00:26:39,320 --> 00:26:39,830
अभी तक.

632
00:26:39,830 --> 00:26:40,950
और विकास एक शब्द नहीं है.

633
00:26:40,950 --> 00:26:42,770
और डी एक एक शब्द या एक नाम नहीं है.

634
00:26:42,770 --> 00:26:45,020
चेक मार्क तो
केवल आप एक बार इंगित करता है

635
00:26:45,020 --> 00:26:48,190
इस नोड है हिट
पात्रों के पिछले पथ

636
00:26:48,190 --> 00:26:50,700
आप डाला है कि वास्तव में एक स्ट्रिंग.

637
00:26:50,700 --> 00:26:53,660
ताकि सभी bool है
हमारे लिए वहाँ क्या कर रहा है.

638
00:26:53,660 --> 00:26:55,500
>> कोशिश करता है पर कोई अन्य प्रश्न?

639
00:26:55,500 --> 00:26:56,215
हाँ.

640
00:26:56,215 --> 00:26:58,035
>> दर्शक: ओवरलैप क्या है?

641
00:26:58,035 --> 00:26:59,945
क्या आप एक डेव और एक दावेन है तो क्या होगा?

642
00:26:59,945 --> 00:27:00,820
डेविड Malan: बिल्कुल सही.

643
00:27:00,820 --> 00:27:02,580
क्या आप एक डेव और एक दावेन है तो क्या होगा?

644
00:27:02,580 --> 00:27:06,240
हम डालें तो, अगर, एक उपनाम का कहना है
David-- Dave-- डी-ए-वी-ई के लिए?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
यह वास्तव में सुपर सरल है.

647
00:27:08,700 --> 00:27:10,325
इसलिए हम केवल चार कदम उठाने जा रहे हैं.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
डी-ए-वी-ई. और मैं करने के लिए क्या है
मुझे लगता है कि चौथे नोड मारा एक बार करते हैं?

650
00:27:15,847 --> 00:27:16,680
बस की जांच करने जा रही है.

651
00:27:16,680 --> 00:27:18,000
हम पहले से ही जाने के लिए अच्छे हैं.

652
00:27:18,000 --> 00:27:18,840
डन.

653
00:27:18,840 --> 00:27:19,750
चार चरणों.

654
00:27:19,750 --> 00:27:21,590
Asymptotically लगातार समय.

655
00:27:21,590 --> 00:27:26,300
और अब हम कि दोनों दवे ने संकेत दिया है
और दावेन संरचना में तार कर रहे हैं.

656
00:27:26,300 --> 00:27:27,710
तो कोई समस्या नहीं है.

657
00:27:27,710 --> 00:27:30,200
और कैसे उपस्थिति नोटिस
दावेन का नहीं बना था

658
00:27:30,200 --> 00:27:34,750
किसी भी अधिक समय या उससे कम ले
समय डेव के लिए और इसके विपरीत.

659
00:27:34,750 --> 00:27:36,000
>> तो अब हम और क्या कर सकते हैं?

660
00:27:36,000 --> 00:27:40,680
हम पहले इस रूपक का उपयोग किया है
ट्रे के कुछ का प्रतिनिधित्व.

661
00:27:40,680 --> 00:27:43,380
लेकिन यह पता चला है कि एक
ट्रे के ढेर वास्तव में है

662
00:27:43,380 --> 00:27:47,187
एक और अमूर्त डेटा की प्रदर्शनात्मक
एक उच्च स्तर डेटा संरचना type--

663
00:27:47,187 --> 00:27:49,770
अंत में दिन बस है कि
एक सरणी या एक लिंक की गई सूची की तरह

664
00:27:49,770 --> 00:27:50,970
अधिक सांसारिक या कुछ और.

665
00:27:50,970 --> 00:27:53,270
लेकिन यह एक और अधिक दिलचस्प है
वैचारिक अवधारणा.

666
00:27:53,270 --> 00:27:56,440
इस तरह के एक ढेर,
मैथर में यहां ट्रे,

667
00:27:56,440 --> 00:27:58,750
आम तौर पर कहा जाता है
सिर्फ एक ढेर that--.

668
00:27:58,750 --> 00:28:02,540
>> और डेटा संरचना के इस प्रकार में
आप दो operations-- है

669
00:28:02,540 --> 00:28:05,880
आप एक बुलाया धक्का के लिए है
ढेर करने के लिए कुछ जोड़ने,

670
00:28:05,880 --> 00:28:08,320
एक और ट्रे डाल की तरह
ढेर के शीर्ष पर वापस.

671
00:28:08,320 --> 00:28:11,350
आप जिसका मतलब है और फिर, पॉप
सर्वोच्च ट्रे दूर ले.

672
00:28:11,350 --> 00:28:16,210
लेकिन एक ढेर है कि है के बारे में महत्वपूर्ण क्या है
यह इस जिज्ञासु विशेषता मिल गया है.

673
00:28:16,210 --> 00:28:19,560
डायनिंग हॉल स्टाफ के रूप में कर रहे हैं
अगले भोजन के लिए ट्रे उलटफेर,

674
00:28:19,560 --> 00:28:21,380
क्या होने जा रहा है
कैसे छात्रों के बारे में सच

675
00:28:21,380 --> 00:28:22,856
इस डेटा संरचना के साथ बातचीत?

676
00:28:22,856 --> 00:28:24,480
दर्शक: वे एक बंद पॉप जा रहे हैं.

677
00:28:24,480 --> 00:28:26,550
डेविड Malan: वे करने जा रहे हैं
एक बंद, उम्मीद है कि शीर्ष पॉप.

678
00:28:26,550 --> 00:28:28,910
अन्यथा यह बस की तरह बेवकूफ है
नीचे करने के लिए सभी रास्ते जाने के लिए.

679
00:28:28,910 --> 00:28:29,070
है ना?

680
00:28:29,070 --> 00:28:31,620
डेटा संरचना वास्तव में अनुमति नहीं है
आप कम से कम नीचे ट्रे हड़पने के लिए

681
00:28:31,620 --> 00:28:32,520
आसानी से.

682
00:28:32,520 --> 00:28:35,040
तो इस उत्सुक नहीं है
ढेर करने के लिए संपत्ति

683
00:28:35,040 --> 00:28:39,730
में अंतिम आइटम है कि
पहले एक बाहर होने जा रहा.

684
00:28:39,730 --> 00:28:43,400
और कंप्यूटर वैज्ञानिकों कॉल
यह पहली बार में बाहर पिछले LIFO--.

685
00:28:43,400 --> 00:28:45,540
और यह वास्तव में है
दिलचस्प अनुप्रयोगों.

686
00:28:45,540 --> 00:28:50,090
यह जरूरी कुछ के रूप में के रूप में स्पष्ट नहीं है
दूसरों, लेकिन यह वास्तव में उपयोगी हो सकता है

687
00:28:50,090 --> 00:28:54,040
और यह वास्तव में लागू किया जा सकता है
अलग तरीके के एक जोड़े में.

688
00:28:54,040 --> 00:28:58,550
>> तो एक है, और वास्तव में, चलो
मुझे उस में डुबकी नहीं.

689
00:28:58,550 --> 00:28:59,860
के बजाय यह करते हैं.

690
00:28:59,860 --> 00:29:03,700
के लगभग है कि एक पर देखें
एक ही विचार है, लेकिन यह एक छोटे से न्यायपूर्ण है.

691
00:29:03,700 --> 00:29:04,200
है ना?

692
00:29:04,200 --> 00:29:07,560
आप इन प्रशंसक लड़कों में से एक रहे हैं या
वास्तव में एप्पल के उत्पादों को पसंद करता है कि लड़कियों

693
00:29:07,560 --> 00:29:10,130
और आप 3:00 पर जाग उठा
कुछ की दुकान पर अप लाइन के लिए

694
00:29:10,130 --> 00:29:14,150
बहुत नवीनतम iPhone पाने के लिए, आप
इस तरह पंक्तिबद्ध हो सकता है.

695
00:29:14,150 --> 00:29:15,800
>> अब एक पंक्ति बहुत जानबूझ नाम पर है.

696
00:29:15,800 --> 00:29:18,190
क्योंकि वहाँ यह एक रेखा है
यह करने के लिए कुछ निष्पक्षता.

697
00:29:18,190 --> 00:29:18,690
है ना?

698
00:29:18,690 --> 00:29:21,690
आप है, तो यह एक तरह से चूसा होगा
एप्पल स्टोर पर वहाँ पहले मिला

699
00:29:21,690 --> 00:29:25,700
लेकिन आप को प्रभावी ढंग से नीचा कर रहे हैं
ट्रे तो एप्पल कर्मचारियों क्योंकि

700
00:29:25,700 --> 00:29:28,189
अंतिम व्यक्ति पॉप कौन
वास्तव में लाइन में मिला है.

701
00:29:28,189 --> 00:29:31,230
ढेर और कतार, भले ही तो
कार्यात्मक वे same-- की तरह कर रहे हैं

702
00:29:31,230 --> 00:29:33,105
यह सिर्फ इस संग्रह है
संसाधनों की है कि

703
00:29:33,105 --> 00:29:36,210
वहाँ है shrink-- बढ़ती जा रही है और
यह करने के लिए इस निष्पक्षता पहलू,

704
00:29:36,210 --> 00:29:39,634
असली दुनिया में कम से कम,
जहां आपरेशन आप व्यायाम

705
00:29:39,634 --> 00:29:40,800
मौलिक रूप से अलग हैं.

706
00:29:40,800 --> 00:29:43,360
एक कतार एक stack--
rather-- है कहा जाता है

707
00:29:43,360 --> 00:29:45,320
दो ऑपरेशन: N कतार और डी कतार.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
या आप उन्हें कॉल कर सकते हैं
चीजों के किसी भी संख्या.

710
00:29:48,090 --> 00:29:50,770
लेकिन तुम सिर्फ कब्जा करना चाहते हैं
एक जोड़ने का है कि धारणा

711
00:29:50,770 --> 00:29:53,230
और एक अंत में घटाकर है.

712
00:29:53,230 --> 00:29:58,840
>> अब हुड के नीचे, दोनों ढेर
और एक कतार में कैसे लागू किया जा सकता है?

713
00:29:58,840 --> 00:30:01,390
हम संहिता में नहीं जाएंगे
यह क्योंकि उच्च स्तर

714
00:30:01,390 --> 00:30:03,387
विचार की तरह और अधिक स्पष्ट है.

715
00:30:03,387 --> 00:30:04,470
मेरा मतलब है, मनुष्य क्या करते हो?

716
00:30:04,470 --> 00:30:07,030
मैं एप्पल में पहला व्यक्ति हूँ
स्टोर और इस मोर्चे दरवाजा है,

717
00:30:07,030 --> 00:30:08,130
तुम मैं यहाँ खड़ा करने के लिए जा रहा हूँ, पता है.

718
00:30:08,130 --> 00:30:09,750
और अगले व्यक्ति की
यहां खड़ा करने के लिए जा रहा है.

719
00:30:09,750 --> 00:30:11,500
और अगले व्यक्ति की
यहां खड़ा करने के लिए जा रहा है.

720
00:30:11,500 --> 00:30:13,792
तो क्या डेटा संरचना
अपने आप में एक पंक्ति को उधार देता है?

721
00:30:13,792 --> 00:30:14,542
>> दर्शक: एक कतार.

722
00:30:14,542 --> 00:30:15,667
डेविड Malan: ठीक है, एक कतार.

723
00:30:15,667 --> 00:30:16,390
ज़रूर.

724
00:30:16,390 --> 00:30:16,920
और क्या?

725
00:30:16,920 --> 00:30:17,600
>> दर्शक: एक लिंक सूची.

726
00:30:17,600 --> 00:30:18,990
>> डेविड Malan: किसी लिंक किए गए
आप लागू कर सकता है की सूची.

727
00:30:18,990 --> 00:30:22,500
और एक लिंक सूची तो है क्योंकि अच्छा है
विरोध के रूप में यह लंबे समय तक मनमाने ढंग से विकसित कर सकते हैं

728
00:30:22,500 --> 00:30:24,880
कुछ निश्चित संख्या होने के लिए
दुकान में लोगों की.

729
00:30:24,880 --> 00:30:27,030
लेकिन शायद एक निश्चित संख्या
स्थानों में से वैध है.

730
00:30:27,030 --> 00:30:30,350
वे केवल 20 की तरह है क्योंकि अगर
शायद, पहले दिन iPhones

731
00:30:30,350 --> 00:30:33,930
वे केवल आकार की एक सरणी की जरूरत
20 कि कतार, प्रतिनिधित्व करने के लिए जो

732
00:30:33,930 --> 00:30:37,070
हम बात कर शुरू में एक बार ही अब कहने के लिए है
इन उच्च स्तर की समस्याओं के बारे में,

733
00:30:37,070 --> 00:30:38,890
आप इसे लागू कर सकते हैं
किसी भी तरीके की संख्या में.

734
00:30:38,890 --> 00:30:42,030
और शायद ही जा रहा है
अंतरिक्ष और समय में एक व्यापार बंद होना

735
00:30:42,030 --> 00:30:43,950
या सिर्फ अपने खुद के कोड जटिलता में.

736
00:30:43,950 --> 00:30:45,380
>> एक ढेर के बारे में क्या?

737
00:30:45,380 --> 00:30:48,190
खैर, एक ढेर, हम भी देखा है
बस इन ट्रे हो सकता है.

738
00:30:48,190 --> 00:30:50,007
और आप इस एक सरणी लागू कर सकता है.

739
00:30:50,007 --> 00:30:53,090
लेकिन कुछ बिंदु पर आप एक सरणी का उपयोग करें
क्या ट्रे को होने जा रहा है

740
00:30:53,090 --> 00:30:54,173
आप नीचे डालने की कोशिश कर रहे हैं?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
ठीक है.

743
00:30:55,670 --> 00:30:57,490
आप केवल करने के लिए जा रहे हैं
इसलिए उच्च जाने के लिए सक्षम हो.

744
00:30:57,490 --> 00:31:00,156
और मुझे लगता है वे कर रहे हैं माथर में लगता है
वास्तव में है कि उद्घाटन में recessed.

745
00:31:00,156 --> 00:31:01,950
तो वास्तव में, यह लगभग है
मैथर उपयोग कर रहा है जैसे

746
00:31:01,950 --> 00:31:03,783
निश्चित आकार की एक सरणी,
आप ही कर सकते हैं क्योंकि

747
00:31:03,783 --> 00:31:08,302
में है कि उद्घाटन में इतने सारे ट्रे फिट
लोगों के घुटनों से नीचे नीचे दीवार.

748
00:31:08,302 --> 00:31:10,010
और इसलिए हो सकता है कि
एक सरणी होने के लिए कहा,

749
00:31:10,010 --> 00:31:14,300
लेकिन हम निश्चित रूप से उस लागू कर सकता है
अधिक आम तौर पर एक लिंक की गई सूची के साथ.

750
00:31:14,300 --> 00:31:16,390
>> खैर, क्या एक और आंकड़ा संरचना के बारे में?

751
00:31:16,390 --> 00:31:18,760
मुझे यहाँ दृश्य एक दूसरे को खींच दें.

752
00:31:18,760 --> 00:31:24,710
कैसे यहाँ इस एक के बारे में कुछ ऐसा ही?

753
00:31:24,710 --> 00:31:28,920
क्यों यह नहीं है करने के लिए उपयोगी हो सकता है
एक Trie, के रूप में के रूप में फैंसी कुछ जो

754
00:31:28,920 --> 00:31:32,370
हम, ये बहुत विस्तृत नोड्स पड़ा देखा
जिनमें से प्रत्येक एक सरणी में है?

755
00:31:32,370 --> 00:31:35,740
लेकिन हम कुछ ज्यादा क्या करते हैं
बस, एक पुराने स्कूल परिवार के पेड़ की तरह,

756
00:31:35,740 --> 00:31:38,110
जिसका यहां नोड्स के प्रत्येक
सिर्फ एक संख्या भंडारण है.

757
00:31:38,110 --> 00:31:42,180
इसके बजाय एक नाम या वंश की
बस इस तरह से एक संख्या भंडारण है.

758
00:31:42,180 --> 00:31:45,250
>> खैर, शब्दजाल हम में उपयोग
डेटा संरचनाओं दोनों की कोशिश करता है

759
00:31:45,250 --> 00:31:49,510
और पेड़, एक Trie, फिर, जहां
बस जिसका नोड्स सरणियों हैं एक,

760
00:31:49,510 --> 00:31:51,680
अभी भी है क्या तुम हो सकता है
ग्रेड स्कूल से उपयोग

761
00:31:51,680 --> 00:31:53,860
आप एक परिवार बना जब
tree-- पत्ते और जड़

762
00:31:53,860 --> 00:31:57,250
पेड़ और के बच्चों की
माता-पिता और उसके भाई बहन.

763
00:31:57,250 --> 00:32:03,670
और हम एक पेड़ लागू हो सकता है,
उदाहरण के लिए, बस के रूप में इस रूप में.

764
00:32:03,670 --> 00:32:07,420
एक पेड़ है, यह अगर एक नोड में से एक के रूप में
एक संख्या है कि इन हलकों,

765
00:32:07,420 --> 00:32:09,947
यह है नहीं जा रहा है
एक सूचक है, लेकिन दो.

766
00:32:09,947 --> 00:32:11,780
और जैसे ही आप जोड़ने के रूप में
एक दूसरे सूचक, आप

767
00:32:11,780 --> 00:32:13,905
वास्तव में अब तरह कर सकते हैं
दो आयामी डेटा की

768
00:32:13,905 --> 00:32:14,780
स्मृति में संरचनाओं.

769
00:32:14,780 --> 00:32:16,660
एक दो आयामी बहुत पसंद है
सरणी, आप कर सकते हैं

770
00:32:16,660 --> 00:32:18,904
दो आयामी की तरह है
लिंक सूचियों लेकिन लोगों

771
00:32:18,904 --> 00:32:20,820
कि एक पैटर्न का पालन करें
जहां कोई चक्र नहीं है.

772
00:32:20,820 --> 00:32:24,487
यह एक साथ वास्तव में एक पेड़ है
यहाँ और फिर दादा-दादी तरह से ऊपर

773
00:32:24,487 --> 00:32:27,320
कुछ माता-पिता और बच्चों और
पोते और महान पोते.

774
00:32:27,320 --> 00:32:28,370
और बहुत आगे है.

775
00:32:28,370 --> 00:32:32,390
>> लेकिन, इस बारे में भी सच में स्वच्छ क्या है
सिर्फ कोड की एक बिट के साथ आप तंग करने के लिए,

776
00:32:32,390 --> 00:32:35,370
से याद प्रत्यावर्तन
थोड़ी देर पहले, जिससे

777
00:32:35,370 --> 00:32:38,220
आप खुद कहता है कि एक समारोह में लिखें.

778
00:32:38,220 --> 00:32:41,140
यह एक सुंदर अवसर है
कुछ को लागू करने के लिए

779
00:32:41,140 --> 00:32:42,920
प्रत्यावर्तन की तरह, क्योंकि इस पर विचार करें.

780
00:32:42,920 --> 00:32:43,860
>> यह एक पेड़ है.

781
00:32:43,860 --> 00:32:48,040
और मैं कैसे साथ एक छोटे गुदा गया है
मैं गली में पूर्णांकों डाल दिया.

782
00:32:48,040 --> 00:32:51,020
इतना तो है कि यह एक विशेष है
एक द्विआधारी खोज वृक्ष name--.

783
00:32:51,020 --> 00:32:53,460
अब हम द्विआधारी के बारे में सुना है
आप खोज सकते हैं, लेकिन

784
00:32:53,460 --> 00:32:55,180
इस बात के नाम से पीछे काम?

785
00:32:55,180 --> 00:32:59,280
मैं कैसे की पैटर्न क्या है
इस पेड़ में पूर्णांकों डाला?

786
00:32:59,280 --> 00:33:00,696
यह मनमाना नहीं है.

787
00:33:00,696 --> 00:33:01,570
कुछ पैटर्न है.

788
00:33:01,570 --> 00:33:02,090
हाँ.

789
00:33:02,090 --> 00:33:03,370
>> दर्शक: बाईं तरफ के छोटे वाले.

790
00:33:03,370 --> 00:33:03,690
>> डेविड Malan: हाँ.

791
00:33:03,690 --> 00:33:05,062
छोटे लोगों पर छोड़ दिया है.

792
00:33:05,062 --> 00:33:06,270
बड़े लोगों अधिकार पर हैं.

793
00:33:06,270 --> 00:33:12,940
इस तरह के एक सच बयान है कि एक
माता पिता, अपने बाएं बच्चे से अधिक है

794
00:33:12,940 --> 00:33:14,850
इसकी सही बच्चे से कम है लेकिन है.

795
00:33:14,850 --> 00:33:17,750
और वह अकेला भी एक है
पुनरावर्ती मौखिक परिभाषा

796
00:33:17,750 --> 00:33:20,500
आपको लगता है कि आवेदन कर सकते हैं क्योंकि
हर नोड के लिए एक ही तर्क

797
00:33:20,500 --> 00:33:23,080
और यह केवल पैंदा
बाहर, एक आधार के मामले आप अगर

798
00:33:23,080 --> 00:33:25,740
होगा, जब तुम में से एक को मारा
पत्तियों, तो बात है,

799
00:33:25,740 --> 00:33:28,580
छुट्टी आगे कोई बच्चों की है, जहां.

800
00:33:28,580 --> 00:33:30,614
>> अब आप कैसे संख्या 44 मिल सकता है?

801
00:33:30,614 --> 00:33:32,280
तुम, एचएम रूट पर शुरू और कहेंगे.

802
00:33:32,280 --> 00:33:35,690
55 तो मैं जाना चाहते हो 44 नहीं है
सही है या मुझे छोड़ जाना चाहते हो?

803
00:33:35,690 --> 00:33:37,190
ठीक है, जाहिर है कि आप छोड़ दिया जाना है.

804
00:33:37,190 --> 00:33:40,060
और तो यह सिर्फ फोन की तरह है
द्विआधारी खोज में पुस्तक उदाहरण

805
00:33:40,060 --> 00:33:41,099
अधिक आम तौर पर.

806
00:33:41,099 --> 00:33:43,390
लेकिन हम इसे लागू कर रहे हैं
अब एक छोटे से अधिक गतिशील रूप

807
00:33:43,390 --> 00:33:45,339
एक सरणी अनुमति हो सकती है.

808
00:33:45,339 --> 00:33:48,130
और वास्तव में, तुम देखो करना चाहते हैं
कोड में, पहली नज़र में यकीन.

809
00:33:48,130 --> 00:33:49,671
यह लाइनों की एक पूरी गुच्छा की तरह लग रहा है.

810
00:33:49,671 --> 00:33:51,220
लेकिन यह खूबसूरती से सरल है.

811
00:33:51,220 --> 00:33:54,490
आप एक समारोह को लागू करना चाहते हैं
जिसका उद्देश्य जीवन में बुलाया खोज

812
00:33:54,490 --> 00:33:57,290
एक मूल्य के लिए खोज करने के लिए है
जैसे एन, एक पूर्णांक,

813
00:33:57,290 --> 00:34:01,756
और आप एक एक pointer-- में पारित कर रहे हैं
जड़ों की नोड के लिए एक सूचक,

814
00:34:01,756 --> 00:34:04,380
बल्कि, उस पेड़ का जो से
यदि आप सब कुछ का उपयोग कर सकते हैं

815
00:34:04,380 --> 00:34:08,850
कैसे straightforwardly नोटिस
आप तर्क लागू कर सकते हैं.

816
00:34:08,850 --> 00:34:10,880
पेड़ शून्य है,
जाहिर है यह वहाँ नहीं है.

817
00:34:10,880 --> 00:34:11,880
चलो बस झूठी वापस जाएँ.

818
00:34:11,880 --> 00:34:12,000
है ना?

819
00:34:12,000 --> 00:34:14,040
आप इसे कुछ नहीं हाथ हैं,
वहाँ कुछ भी नहीं है.

820
00:34:14,040 --> 00:34:17,900
>> वरना एन की तुलना में कम है, अगर
अब एन तीर n-- पेड़ तीर,

821
00:34:17,900 --> 00:34:20,670
हम सुपर पेश किया याद
संक्षेप में दूसरे दिन,

822
00:34:20,670 --> 00:34:25,100
और कहा कि अभी डी-संदर्भ का मतलब
सूचक और एन बुलाया क्षेत्र पर दिखेगा.

823
00:34:25,100 --> 00:34:27,690
तो यह वहाँ जाना है और इसका मतलब है
एन बुलाया क्षेत्र पर दिखेगा.

824
00:34:27,690 --> 00:34:33,810
तो पता है, तो आप दी रहे हैं मूल्य, कम है
पेड़ पूर्णांक में मूल्य से,

825
00:34:33,810 --> 00:34:35,449
जहां आप जाना चाहते हैं?

826
00:34:35,449 --> 00:34:36,389
बाएं.

827
00:34:36,389 --> 00:34:37,780
>> तो प्रत्यावर्तन नोटिस.

828
00:34:37,780 --> 00:34:39,860
मैं नहीं सच returning-- रहा हूँ.

829
00:34:39,860 --> 00:34:40,989
झूठी नहीं.

830
00:34:40,989 --> 00:34:45,670
मैं जो कुछ भी जवाब लौट रहा हूँ
अपने आप के लिए एक फोन से है, गुजर

831
00:34:45,670 --> 00:34:50,100
बेमानी है जो फिर से एक एन,
लेकिन अब थोड़ा अलग क्या है?

832
00:34:50,100 --> 00:34:51,989
मैं कैसे छोटे समस्या बना रहा हूँ?

833
00:34:51,989 --> 00:34:54,920
मैं दूसरा रूप में गुजर रहा हूँ
तर्क, पेड़ का नहीं जड़,

834
00:34:54,920 --> 00:34:59,616
लेकिन इस मामले में बाएं बच्चे.

835
00:34:59,616 --> 00:35:00,990
तो मैं छोड़ दिया बच्चे में गुजर रहा हूँ.

836
00:35:00,990 --> 00:35:04,720
>> इस बीच एन से बड़ा है, अगर
मैं वर्तमान में देख रहा हूँ नोड,

837
00:35:04,720 --> 00:35:06,690
मैं दाहिने हाथ की ओर खोज.

838
00:35:06,690 --> 00:35:10,880
वरना, पेड़, अशक्त नहीं है और अगर
तत्व बाईं ओर नहीं है

839
00:35:10,880 --> 00:35:13,240
और यह सही करने के लिए नहीं है
मामले अद्भुत क्या है?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
हम वास्तव में नोड पाया है
सवाल है, और इसलिए हम वापसी सच.

842
00:35:18,440 --> 00:35:21,490
>> तो हम सिर्फ सतह खरोंच है
अब इन डेटा संरचनाओं की कुछ.

843
00:35:21,490 --> 00:35:24,370
समस्या पाँच सेट में तुम हूँ
अभी तक आगे इन का पता लगाने,

844
00:35:24,370 --> 00:35:27,250
और आप अपने डिजाइन दिया जाएगा
इस बारे में जाने के लिए की पसंद है.

845
00:35:27,250 --> 00:35:30,250
मैं को समाप्त करना चाहते हैं
सिर्फ एक 30 दूसरा नमूना है

846
00:35:30,250 --> 00:35:32,080
परे अगले हफ्ते और इंतजार कर रहा है क्या की.

847
00:35:32,080 --> 00:35:35,390
>> हम शुक्र begin-- के रूप में आप कर सकते हैं
धीरे-धीरे हमारे संक्रमण think--

848
00:35:35,390 --> 00:35:38,680
सी और कम की दुनिया से
स्तर कार्यान्वयन के विवरण,

849
00:35:38,680 --> 00:35:42,090
एक दुनिया में जिसमें हम के लिए ले जा सकते हैं
किसी और अंत में है कि दी

850
00:35:42,090 --> 00:35:44,010
इन डेटा लागू किया
हमारे लिए संरचनाओं,

851
00:35:44,010 --> 00:35:47,570
और हम समझने के लिए शुरू करेंगे
असली दुनिया को लागू करने का मतलब

852
00:35:47,570 --> 00:35:50,560
वेब आधारित कार्यक्रम और
वेबसाइटों अधिक आम तौर पर

853
00:35:50,560 --> 00:35:52,910
और भी बहुत सुरक्षा
हम केवल है कि निहितार्थ

854
00:35:52,910 --> 00:35:54,850
की सतह खरोंच करने के लिए शुरू कर दिया.

855
00:35:54,850 --> 00:35:57,320
यहाँ हमें इंतजार कर रहा है क्या है
दिन में आने के लिए.

856
00:35:57,320 --> 00:36:00,480
>> [वीडियो प्लेबैक]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -वह, एक संदेश के साथ आया था
सब अपने ही एक प्रोटोकॉल के साथ.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
वह क्रूर की एक दुनिया के लिए आया था
फायरवॉल, बेपरवाह राउटर,

861
00:36:30,894 --> 00:36:33,368
और खतरों मौत से भी बदतर.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
वह तेजी से है.

864
00:36:36,236 --> 00:36:37,980
वह मजबूत है.

865
00:36:37,980 --> 00:36:42,830
उन्होंने कहा कि टीसीपी / आईपी है, और वह अपना पता मिल गया है.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"नेट के योद्धाओं."

868
00:36:48,074 --> 00:36:49,660
[अंत वीडियो प्लेबैक]

869
00:36:49,660 --> 00:36:50,910
डेविड Malan: अगले हफ्ते आ रहा है.

870
00:36:50,910 --> 00:36:51,880
हम आपको फिर देखेंगे.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[वीडियो प्लेबैक]

873
00:36:56,060 --> 00:36:59,240
-और अब, "गहरे विचार"
दावेन Farnham द्वारा.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David हमेशा शुरू होता है
साथ व्याख्यान "ठीक है."

876
00:37:05,820 --> 00:37:08,750
क्यों नहीं, "यहाँ समाधान है
इस हफ्ते की समस्या सेट करने के लिए "

877
00:37:08,750 --> 00:37:12,180
या "हम एक ए आप सब दे रहे हैं?"

878
00:37:12,180 --> 00:37:13,380
[हंसते हुए]

879
00:37:13,380 --> 00:37:15,530
[अंत वीडियो प्लेबैक]