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
>> DAVID Malan: ეს არის CS50.

5
00:00:14,010 --> 00:00:18,090
და ეს ორივე დაწყების და
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
თქვენ შეიძლება გავიხსენოთ, რომ ჩვენ ვთხოვთ თქვენ ყველა
p კომპლექტი ფორმა, თუ თქვენ უყურებს ონლაინ

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
არავის სურს, რომ conjecture, ამიტომ ეს
გრაფაში ასე jaggy, up down, up down,

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
რა თითოეულ მწვერვალები
და ქვაბულებს წარმოადგენს?

19
00:00:45,130 --> 00:00:46,005
>> აუდიტორია: [INAUDIBLE]

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
რომელიც ახლა out.

28
00:01:07,450 --> 00:01:10,817
Misspellings, სადაც, ჩვენ
გადმოგცეთ ტექსტური ფაილი რამდენიმე 100,000

29
00:01:10,817 --> 00:01:12,650
პლუს ინგლისური სიტყვა და
თქვენ აპირებს აქვს

30
00:01:12,650 --> 00:01:17,770
გაერკვნენ, თუ როგორ ჭკვიანურად მათ ჩატვირთვაზე
მეხსიერება, შევიდა RAM გამოყენებით ზოგიერთი მონაცემები

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
>> აუდიტორია: Insertion.

37
00:01:32,950 --> 00:01:33,908
>> დავით Malan: Insertion.

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
>> აუდიტორია: Anywhere ერთად
სია [INAUDIBLE].

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
გარეშე shuffle არაფერი,
რომელიც დავასკვენით, რომ ჩვენი დახარისხება

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
და შემდეგ განახლება რამდენიმე
პოინტერები ორი, სამი ოპერაციების 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
>> აუდიტორია: [INAUDIBLE]

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

54
00:02:07,538 --> 00:02:08,413
დავით Malan: Perfect.

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
ბლოკი მეხსიერება, როგორც თქვენ ექნება
to მასივი, თავდაყირა, რომელიც

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
გადანაწილების ახალი დიდი მასივი, ასლი
ყველაფერი დასრულდა, უფასო ძველი მასივი,

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
ერთად insertions და წაშლებს.

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
>> DAVID 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
>> აუდიტორია: [INAUDIBLE]

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

81
00:03:04,865 --> 00:03:05,740
DAVID Malan: ზუსტად.

82
00:03:05,740 --> 00:03:07,580
თუ გსურთ აქვს
გარკვეული ალგორითმი

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
და jumping უფლება მას.

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
>> აუდიტორია: [INAUDIBLE]

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

94
00:03:32,566 --> 00:03:33,440
DAVID 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
და ასე მთელი რიგი ოპერაციების
on უკავშირდება სიები დაიბარეს

102
00:03:49,421 --> 00:03:50,570
იყო დიდი O 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
აპირებთ დაიწყოთ გამოყენება დღეს,
წლიური გამოყენება p კომპლექტი ხუთი,

115
00:04:23,464 --> 00:04:24,630
ეს საკმაოდ ნაცნობი.

116
00:04:24,630 --> 00:04:27,430
მაგალითად, თუ ეს არის bunch
საგამოცდო წიგნები, რომელთაგან თითოეული

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
რა თქვენი ინსტინქტები იყოს
დიდი pile გამოცდები ასე?

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-- ან ჩემი array ნამდვილად

127
00:04:50,650 --> 00:04:52,210
მე შეიძლება დააყენოს ყველა ქალბატონი იქ.

128
00:04:52,210 --> 00:04:52,710
Oh.

129
00:04:52,710 --> 00:04:55,020
აი ა ასე მე შეიძლება
ამით, როგორც აქ.

130
00:04:55,020 --> 00:04:55,520
Oh.

131
00:04:55,520 --> 00:04:57,980
აქ არის კიდევ ერთი A. მე ვაპირებ
იმისათვის, რომ მეტი აქ.

132
00:04:57,980 --> 00:05:02,490
აი ზ აქ არის კიდევ ერთი M. და ასე
მე შეიძლება დაიწყოს მიღების piles მოსწონს ეს.

133
00:05:02,490 --> 00:05:06,620
და მაშინ იქნებ მე მინდა წასვლა მოგვიანებით
და ასეთი ძალიან nitpicky-ly სახის

134
00:05:06,620 --> 00:05:07,710
ინდივიდუალური piles.

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
თუ იგი იწყება Z, ამას მეტი
იქ, და ყველაფერი შორის.

139
00:05:18,980 --> 00:05:22,730
>> ასე რომ, ეს არის ტექნიკა, რომელიც არის
საყოველთაოდ ცნობილია, როგორც hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
რაც ზოგადად იმას ნიშნავს, რომ, როგორც
შემავალი და გამოყენებით, რომ input გამოთვლაც

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
და თუ მე ვერ ვხედავ ვინმე Z, მე
ვაპირებთ რუკაზე რომ 25 ჩემი უფროსი

147
00:05:44,160 --> 00:05:46,220
და შემდეგ დააყენა, რომ შევიდა
ბოლო ყველაზე pile.

148
00:05:46,220 --> 00:05:50,990
>> ახლა, თუ ფიქრობთ, რომ არა ჩემი ტვინის
მაგრამ C პროგრამის, რა ციფრები იქნებოდა

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
როგორ განსაზღვრა
რა bucket დააყენოს ის?

152
00:05:57,510 --> 00:05:59,801
ალბათ, არ მინდა
დააყენოს ის bucket 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
სად გსურთ, რომ მისი ASCII
არც ამუშავება სასურველი სტუმარი გახდებით bucket

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
>> DAVID 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
და ისე, რომ საშუალებას გვაძლევს, ძალიან
უბრალოდ და ძალიან arithmetically,

163
00:06:21,300 --> 00:06:23,260
რომ რაღაც შევიდა bucket, როგორიცაა, რომ.

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 პლუს us

168
00:06:34,400 --> 00:06:37,800
მივიღე ერთად სხვა ღამის კლასის,
ბოლო ნაბიჯი ჩვენი შეფასების პროცესი

169
00:06:37,800 --> 00:06:41,830
არის hash ტესტებში შევიდა დიდი
ფართი სართულზე [INAUDIBLE]

170
00:06:41,830 --> 00:06:45,110
და ქმნის ყველას ტესტები out
ზუსტად, რათა მათი TF ს

171
00:06:45,110 --> 00:06:47,700
სახელები საფარი, რადგან
მაშინ ეს ბევრი ადვილია ჩვენთვის

172
00:06:47,700 --> 00:06:51,290
ძებნის რომ იყენებთ ხაზოვანი
ძიება ან რაიმე სახის cleverness

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
და ჩვენ გვქონდა მთელი bunch of დასაკეცი
მაგიდები სახელი tags.

181
00:07:12,680 --> 00:07:15,380
და ჩვენ სახელი tags ორგანიზებული
ერთად მოსწონს როგორც იქ

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
თქვენ განხორციელების
იგივე ცნება hash.

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
რომ ჩვენ შეიძლება დააყენოს strings
რაღაც ამ.

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
მაგრამ ეს მხოლოდ მხატვრის rendition
რა hash მაგიდაზე შეიძლება იყოს.

196
00:07:48,930 --> 00:07:52,799
>> ასე hash მაგიდაზე ახლა აპირებს
უფრო მაღალი დონე მონაცემთა სტრუქტურას.

197
00:07:52,799 --> 00:07:54,840
ბოლოს დღეს
ჩვენ შესახებ, რომ თქვენ

198
00:07:54,840 --> 00:07:58,700
შეგიძლიათ განახორციელოს hash მაგიდა, რომელიც
ძალიან ჰგავს გამშვები ონლაინ

199
00:07:58,700 --> 00:08:02,059
ერთი hackathon მოსწონს ეს
ცხრილის გამოყენება დახარისხება გამოცდა წიგნები.

200
00:08:02,059 --> 00:08:03,850
მაგრამ hash მაგიდა
დალაგების ამ მაღალი დონის

201
00:08:03,850 --> 00:08:08,250
კონცეფცია, რომელიც შეიძლება გამოიყენოთ მასივი
ქვევმოთ hood განახორციელოს ეს,

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
>> ასე hash მაგიდა
შეიძლება განახორციელოს ეს

208
00:08:28,680 --> 00:08:32,540
მეხსიერების ხატოვნად, მაგრამ,
როგორ შეიძლება, რომ რეალურად მიეცეს up?

209
00:08:32,540 --> 00:08:33,789
ასევე, შესაძლოა, უბრალოდ ეს.

210
00:08:33,789 --> 00:08:38,270
თუ მოცულობით ყველა caps, მხოლოდ
ზოგიერთი constant-- მაგალითად 26

211
00:08:38,270 --> 00:08:42,030
26 ასო alphabet--
მე შეიძლება მოვუწოდებთ ჩემი ცვლადი მაგიდა,

212
00:08:42,030 --> 00:08:45,630
და მე შეიძლება ითქვას, რომ მე ვაპირებ
ბოლო char ვარსკვლავი არსებობს, ან string.

213
00:08:45,630 --> 00:08:49,880
ასე რომ, ეს მარტივია, როგორც ეს თუ
განახორციელოს hash მაგიდასთან.

214
00:08:49,880 --> 00:08:51,490
და კიდევ, ეს მართლაც მხოლოდ მასივი.

215
00:08:51,490 --> 00:08:53,198
მაგრამ კიდევ ერთხელ, hash
მაგიდა არის ის, რაც ჩვენ

216
00:08:53,198 --> 00:08:57,470
დარეკეთ აბსტრაქტული მონაცემები ტიპის, რომ მხოლოდ
ერთგვარი კონცეპტუალური layering თავზე

217
00:08:57,470 --> 00:09:00,780
რაღაც უფრო mundane
ახლა მინდა მასივი.

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
Ms შეიძლება აქ.

224
00:09:13,230 --> 00:09:14,740
და მაშინ მქონდა ზედმეტი სივრცეში.

225
00:09:14,740 --> 00:09:18,740
მაგრამ ეს არის ცოტა cheat უფლება
ახლა, რადგან ამ მაგიდასთან, თუ ნამდვილად

226
00:09:18,740 --> 00:09:22,720
მიაჩნდა, რომ ეს მასივი, მხოლოდ
იქნება გარკვეული ფიქსირებული ზომა.

227
00:09:22,720 --> 00:09:25,380
>> ასე რომ ტექნიკურად, თუ მე დახევის
up მეორე სტუდენტი ვიქტორინა

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
უბრალოდ სახის stacked
მათ ზემოთ ერთმანეთს.

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
აუდიტორია: [INAUDIBLE]

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

244
00:10:00,565 --> 00:10:01,315
DAVID 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
ამიტომ, მე ვაპირებ, რომ დააყენოს ის
ტექნიკურად, სადაც B წავიდოდა.

249
00:10:07,450 --> 00:10:09,932
ახლა, რა თქმა უნდა, მე დაწყებული
ხატავს თავს კუთხეში.

250
00:10:09,932 --> 00:10:11,890
თუ მე სტუდენტი
რომლის სახელიც არის რეალურად B,

251
00:10:11,890 --> 00:10:14,840
ახლა B იქნება გადავიდა პატარა
წინ, როგორც შეიძლება მოხდეს, yep,

252
00:10:14,840 --> 00:10:17,530
თუ ეს არის B, ახლა იგი უნდა წავიდეს აქ.

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
დიდი O რა?

265
00:10:50,002 --> 00:10:51,147
>> აუდიტორია: n.

266
00:10:51,147 --> 00:10:52,480
დავით Malan: მე მოვისმინე დიდი O of 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
>> აუდიტორია: [INAUDIBLE]

272
00:10:58,755 --> 00:11:00,380
დავით Malan: ნება მომეცით ამის გაკეთება ვიზუალურად.

273
00:11:00,380 --> 00:11:04,720
ამიტომ ვარაუდობენ, რომ ეს არის წერილი S.

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
და გვესმის, რომ,
რა, აქ ჩემი შეყვანის S,

280
00:11:13,800 --> 00:11:16,350
მე რა თქმა უნდა გარდაქმნას
S, 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
>> მაგრამ რა თქმა უნდა, როგორც კი მივიღებ
მეორე პირი, რომელიც არის სახელი ან B ან C

284
00:11:26,120 --> 00:11:29,300
საბოლოოდ, თუ მე გამოიყენება
ხაზოვანი probing როგორც ჩემი გადაწყვეტა,

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
აუდიტორია: [INAUDIBLE]

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
როგორც მათი სახელი და წერილი
B, შეიძლება პოტენციურად

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
აუდიტორია: [INAUDIBLE]

303
00:12:08,960 --> 00:12:10,030
DAVID 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
და ამ ავტორის უბრალოდ
გადაწყვიტა hash strings

311
00:12:28,220 --> 00:12:32,430
არ ეფუძნება ადამიანის სახელები,
მაგრამ საფუძველზე მათი birthdates.

312
00:12:32,430 --> 00:12:35,680
მიუხედავად იმისა, თვის, მათ figured
თუ თქვენ დაიბადა პირველ თვეში

313
00:12:35,680 --> 00:12:39,580
ან 31 თვეში, ავტორი
იქნება hash საფუძველზე, რომ ღირებულება,

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
მაგრამ ეს მხოლოდ მხატვრის rendition.

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
>> DAVID 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
და მართლაც, ეს ძალიან გვინდა
შეიძლება მოუწოდა hash მაგიდა,

339
00:13:39,630 --> 00:13:42,610
რომლის დროსაც მასივი
ნამდვილად hash მაგიდა,

340
00:13:42,610 --> 00:13:45,600
მაგრამ, რომ hash მაგიდა აქვს
ქსელები, ასე ვთქვათ,

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
probabilistically, ჩვენ ვაპირებთ
უფრო და უფრო მეტი შეჯახება.

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
თუ მე ჩადეთ n ადამიანი ამ უფრო
დახვეწილი მონაცემები სტრუქტურა, N ხალხს,

364
00:14:38,890 --> 00:14:41,080
უარეს შემთხვევაში ეს იქნება n.

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: Perfect.

369
00:14:45,420 --> 00:14:47,480
ეს შეიძლება იყოს პატარა contrived,
მაგრამ ნამდვილად, უარეს შემთხვევაში,

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
ასე რომ, თქვენ შეიძლება ეძახით
hash მაგიდასთან, მაგრამ რეალურად ეს

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
არის დიდი O of n ზე 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
მაგრამ ეს ჯერ კიდევ დიდი O of n.

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
და მართლაც, უარეს შემთხვევაში, ამ
hash table შესაძლოა გადაეცემა შევიდა, რომ.

395
00:15:53,550 --> 00:15:57,620
>> მაგრამ რეალურ სამყაროში, ადამიანები
რომ საკუთარი Macs და კომპიუტერით ან რასაც

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
რომელიც იღებს ბოლოს ნაბიჯები ან
რომელიც იღებს n იყოფა 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
ჩვენ შეგვიძლია დახარჯოს ცოტა
მეტი დრო და cleverness

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
რომ მართლაც უფრო
ერთიანი და ნაკლებად jaggy,

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
მაგრამ ჩვენ ვაპირებთ უნდა დაიწყოს აღების
იმ სასწავლო თვლები off ახლა.

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
მაგრამ ახლა ჩვენ ვაპირებთ, რომ უკან დახევის
ფარდა და აცხადებენ, რომ მხოლოდ char ვარსკვლავი.

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
>> და ახლა როგორ შემიძლია განვაცხადო,
hash მაგიდაზე თავად?

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
ადრე, ისევე შემიძლია მხოლოდ ვთქვა,
მე უბრალოდ უნდა bunch of პოინტერები

433
00:17:44,510 --> 00:17:46,270
განახორციელოს ეს მთელი hash მაგიდასთან.

434
00:17:46,270 --> 00:17:49,484
მე ვაპირებ მასივი
მოუწოდა მაგიდა hash მაგიდასთან.

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
და თითოეული იმ ელემენტებს ამ
array იქნება კვანძის ვარსკვლავი.

438
00:17:56,180 --> 00:17:56,810
რატომ?

439
00:17:56,810 --> 00:18:00,160
ასევე, შეეხება ამ სურათს, რაც მე
განხორციელების hash მაგიდაზე

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
რომ პირობა, რომ აქვს slashes
მეშვეობით მათგან მხოლოდ null.

443
00:18:09,170 --> 00:18:11,410
და პირობა, რომ აქვს
ისრებით აპირებს უფლება

444
00:18:11,410 --> 00:18:16,140
აქტუალური მითითებას ფაქტობრივი კვანძების,
ergo დაწყების უკავშირდება სიაში.

445
00:18:16,140 --> 00:18:19,050
>> ასე რომ, მაშინ, როგორ შეიძლება
განახორციელოს hash მაგიდაზე რომ

446
00:18:19,050 --> 00:18:21,580
ახორციელებს ცალკე chaining.

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
თქვენ შესაყვანი შევიდა
მონაცემთა სტრუქტურას.

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
დავუშვათ, მინდოდა ჩადეთ სახელი
Daven in ჩემს მონაცემები სტრუქტურა.

457
00:18:49,300 --> 00:18:52,100
>> ასე რომ, მინდა ჩადეთ სიმებიანი
Daven შევიდა მონაცემები სტრუქტურა.

458
00:18:52,100 --> 00:18:54,370
რა მოხდება, თუ არ იყენებენ
hash მაგიდასთან, მაგრამ მე

459
00:18:54,370 --> 00:18:56,980
რომ რაღაც უფრო მეტი ხე მსგავსი
მოსწონს ოჯახის ხე, სადაც

460
00:18:56,980 --> 00:18:59,670
თქვენ გაქვთ გარკვეული root ზე
ზევით და შემდეგ კვანძების და ფოთლები

461
00:18:59,670 --> 00:19:01,440
რომ წავიდეთ ქვევით და გარე.

462
00:19:01,440 --> 00:19:04,450
დავუშვათ, მაშინ, რომ მე
გსურთ ჩადეთ Daven მიერ

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
>> კერძოდ, მე ვაპირებ მკურნალობა
ეს არის A, მაშინ B, მაშინ C, მაშინ D,

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
მაგრამ ჩადეთ ყველა Daven მიერ
ასახელებს, მე უნდა გავაკეთოთ ცოტა მეტი.

473
00:19:36,040 --> 00:19:37,840
ასე რომ, მე პირველი აპირებს hash, ასე ვთქვათ.

474
00:19:37,840 --> 00:19:41,049
მე ვაპირებ შევხედოთ პირველი წერილი
in Daven ის რაც აშკარად D,

475
00:19:41,049 --> 00:19:42,840
და მე ვაპირებ გამოუყოფს
კვანძში, რომელიც გამოიყურება

476
00:19:42,840 --> 00:19:45,570
მსგავსი რამ დიდი მართკუთხედი დიდი
საკმარისი, რათა შეწყობოდა მთელი ანბანი.

477
00:19:45,570 --> 00:19:47,140
>> ახლა D კეთდება.

478
00:19:47,140 --> 00:19:49,720
ახლა A. D-A-V-E-N არის მიზანი.

479
00:19:49,720 --> 00:19:51,220
ასე რომ, ახლა, რაც მე ვაპირებ, რომ ეს.

480
00:19:51,220 --> 00:19:54,027
როგორც კი დავიწყე D ცნობა
არ არსებობს კურსორი იქ.

481
00:19:54,027 --> 00:19:56,860
ეს ნაგვის ღირებულებების მომენტში,
ან მე შეიძლება ინიციალიზაცია მას null.

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 გამოყენებით struct

486
00:20:09,130 --> 00:20:11,240
როგორც ჩვენ მალე ვნახავთ,
მე ვაპირებ ამის გაკეთება

487
00:20:11,240 --> 00:20:14,450
მე ვაპირებ მიაპყროს arrow საწყისი
ის, რომ წარმოდგენილი D ქვემოთ

488
00:20:14,450 --> 00:20:15,860
ამ ახალი კვანძში.

489
00:20:15,860 --> 00:20:19,240
და ახლა, პირველი შემდეგი
წერილი Daven სახელი,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- მე ვაპირებ წავიდეთ წინ
და გავამახვილო კიდევ ერთი კვანძის, როგორც ეს,

491
00:20:24,150 --> 00:20:30,150
რომლის დროსაც, V ელემენტები აქ,
ჩვენ მიაპყროს instance-- whoops.

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
>> მაშინ ჩვენ ვაპირებთ
მიგვაჩნია, რომ ეს V.

496
00:20:35,712 --> 00:20:44,920
და შემდეგ ქვევით აქ ჩვენ ვაპირებთ ინდექსი
ქვემოთ V შევიდა, რაც ჩვენ განვიხილავთ E.

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
მე უნდა როგორმე მიუთითებს, რომ
ჩვენ ბოლოს სიმებიანი Daven.

500
00:20:57,840 --> 00:20:59,490
ასე რომ მე ვერ დატოვოს null.

501
00:20:59,490 --> 00:21:02,670
>> მაგრამ რა, თუ ჩვენ გვაქვს Daven მიერ
სრული სახელი, რომელნი

502
00:21:02,670 --> 00:21:04,280
ეს არის, როგორც ჩვენ განაცხადა, Davenport?

503
00:21:04,280 --> 00:21:06,970
მერე რა, რომ Daven არის
რეალურად 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
იქ, იმიტომ, რომ ჩვენ შეგვიძლია
არ ჩაწეროთ სიტყვა, როგორიცაა Davenport

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
იქნება null, რადგან
არ არსებობს Davenport უბრალოდ არ არის.

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
D-A-V-E-N ტექსტი
ამ მონაცემების სტრუქტურას.

519
00:21:44,230 --> 00:21:48,350
>> იმავდროულად, თუ მქონდა მეტი სივრცე
აქ, მე ვერ გავაკეთებ P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
და მე ვერ დააყენა გამშვები კვანძის
რომ აქვს წერილი T at ბოლომდე.

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
თუ გვინდოდა დავით,
ჩვენ გვინდა დაიცვას იგივე ლოგიკით, D-A-V,

525
00:22:03,370 --> 00:22:08,802
მაგრამ ახლა მინდა აღვნიშნო შემდეგი
ელემენტი არ E, მაგრამ მე დ

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
ისევე როგორც ეს არ dot, dot,
წერტილი, მაგრამ მხოლოდ შემოკლებით მასივები.

531
00:22:21,810 --> 00:22:23,950
მაგრამ თითოეული კვანძების
ამ ხეს აქ

532
00:22:23,950 --> 00:22:26,700
წარმოადგენს იგივე რამ
მასივი Ray ზომა 26.

533
00:22:26,700 --> 00:22:28,860
>> თუ ჩვენ გვინდა, რომ იყოს
ნამდვილად სწორი ახლა, რა

534
00:22:28,860 --> 00:22:30,790
თუ ვინმეს სახელი
აპოსტროფი, მოდით

535
00:22:30,790 --> 00:22:35,560
ვივარაუდოთ, რომ თითოეული კვანძის რეალურად აქვს
როგორც 27 ინდექსები, არა მხოლოდ 26.

536
00:22:35,560 --> 00:22:42,020
ასე რომ, ეს ახლა იქნება მონაცემები
სტრუქტურა მოუწოდა trie-- T-R-I-E.

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
ჩაწერეთ რომელზეც I-E, ასე რომ 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
და აქ არის კიდევ ერთი მაგალითი
მთელი bunch სხვა ხალხის სახელები.

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
გამოყენებით D's მაჩვენებელი და
და V და Es და Ns,

549
00:23:15,050 --> 00:23:16,700
მე გაყვანაა heck of მეხსიერების დიდ ნაწილს.

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: Time.

556
00:23:28,990 --> 00:23:30,320
რატომ შეიძლება რომ იყოს?

557
00:23:30,320 --> 00:23:33,880
ისე, რა არის ჩასმა
დრო, თვალსაზრისით დიდი O ახლა,

558
00:23:33,880 --> 00:23:37,660
სახელის როგორიცაა Daven
ან Davenport ან დავითი?

559
00:23:37,660 --> 00:23:39,340
ასევე, Daven იყო ხუთი საფეხურით.

560
00:23:39,340 --> 00:23:42,350
Davenport იქნება ცხრა ნაბიჯები,
ასე რომ, ეს იქნება კიდევ რამდენიმე ნაბიჯი.

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 ან
Alison ან Belinda ან სხვა სახელები

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
იმიტომ, რომ ჩვენ ეფექტურად გამოყენების
ეს მრავალ ფენას hash მაგიდასთან.

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-- დიდი O ერთი.

590
00:24:52,580 --> 00:24:54,720
და გულწრფელად, უბრალოდ
რეალურ ცხოვრებაში, ეს

591
00:24:54,720 --> 00:24:58,380
ნიშნავს ჩასმა Daven სახელი იღებს
ისევე როგორც ხუთი ნაბიჯები, ან Davenport ცხრა

592
00:24:58,380 --> 00:25:00,100
ნაბიჯები, ან დავით ხუთი საფეხურით.

593
00:25:00,100 --> 00:25:03,071
ეს არის საკმაოდ darn პატარა გაშვებული ჯერ.

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
მივიჩნევთ, რომ კვანძების
რომ ჰკიდია off

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
მხოლოდ იმიტომ, რომ ამისთვის აპოსტროფი.

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
ხედავთ p კომპლექტი 5 ჩვენ მხოლოდ აინტერესებს
შესახებ წერილები და ხაზს.

614
00:25:50,330 --> 00:25:52,990
>> და შემდეგ, როგორ ფიქრობთ წარმოადგენს
მონაცემთა სტრუქტურას თავად?

615
00:25:52,990 --> 00:25:56,454
როგორ ფიქრობთ, წარმოადგენს root
ამ trie, ასე ვთქვათ?

616
00:25:56,454 --> 00:25:59,620
კარგად, ისევე, როგორც დაკავშირებული სიაში, თქვენ
უნდა მომცეთ პირველ ელემენტს.

617
00:25:59,620 --> 00:26:04,270
ერთად trie თქვენ უბრალოდ უნდა ერთი
მომცეთ root ამ trie.

618
00:26:04,270 --> 00:26:07,290
და იქიდან შეგიძლიათ hash
თქვენი გზა ქვემოთ უფრო და უფრო ღრმა

619
00:26:07,290 --> 00:26:10,460
ყველა სხვა კვანძის სტრუქტურა.

620
00:26:10,460 --> 00:26:13,440
ასე რომ, უბრალოდ ეს შეიძლება
ჩვენ წარმოვადგენთ, რომ struct.

621
00:26:13,440 --> 00:26:15,877
>> ახლა Meanwhile-- Oh, კითხვა.

622
00:26:15,877 --> 00:26:17,220
>> აუდიტორია: რა არის bool სიტყვა?

623
00:26:17,220 --> 00:26:20,490
>> დავით Malan: რედაქტირება სიტყვა
მხოლოდ ამ C განსახიერება

624
00:26:20,490 --> 00:26:22,920
რა მე აღწერილი
ამ ყუთს, როდესაც

625
00:26:22,920 --> 00:26:26,000
დავიწყე გაყოფა თითოეული
array ელემენტები ორ ნაწილად.

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
ვთქვა, დიახ, არსებობს
სიტყვა Daven, რომ აქ მთავრდება,

629
00:26:33,770 --> 00:26:35,610
იმიტომ, რომ ჩვენ არ გვინდა,
ამ ეტაპზე, Dave.

630
00:26:35,610 --> 00:26:39,320
>> მიუხედავად იმისა, რომ Dave იქნება
ლეგიტიმური სიტყვა, ის არ trie

631
00:26:39,320 --> 00:26:39,830
ამჟამად.

632
00:26:39,830 --> 00:26:40,950
და D არ არის სიტყვა.

633
00:26:40,950 --> 00:26:42,770
და D-არ არის, სიტყვა ან სახელი.

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
რა მოხდება, თუ თქვენ გაქვთ Dave და Daven?

642
00:26:59,945 --> 00:27:00,820
დავით Malan: Perfect.

643
00:27:00,820 --> 00:27:02,580
რა მოხდება, თუ თქვენ გაქვთ Dave და Daven?

644
00:27:02,580 --> 00:27:06,240
ასე რომ, თუ ჩვენ ჩადეთ, ამბობენ, მეტსახელად
for David-- Dave-- D-A-V-E?

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
D-A-V-E. და რა მაქვს
გავაკეთოთ ერთხელ მოხვდა, რომ მეოთხე კვანძის?

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
და ახლა ჩვენ მითითებულია, რომ ორივე Dave
და Daven სიმები სტრუქტურა.

656
00:27:26,300 --> 00:27:27,710
ასე არ არის პრობლემა.

657
00:27:27,710 --> 00:27:30,200
და შეამჩნია, როგორ თანდასწრებით
საქართველოს Daven არ ხდის

658
00:27:30,200 --> 00:27:34,750
მიიღოს ნებისმიერი მეტი დრო და ნაკლები
დრო Dave და პირიქით.

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
მაგრამ აღმოჩნდება, რომ
Stack of ქაღალდის რეალურად

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
ან რაიმე უფრო mundane.

665
00:27:50,970 --> 00:27:53,270
მაგრამ ეს უფრო საინტერესო
კონცეპტუალური კონცეფცია.

666
00:27:53,270 --> 00:27:56,440
დასტის, მოსწონს ეს
ქაღალდის აქ Mather,

667
00:27:56,440 --> 00:27:58,750
როგორც წესი, ეწოდება
უბრალოდ that-- Stack.

668
00:27:58,750 --> 00:28:02,540
>> და ამ ტიპის მონაცემები სტრუქტურა
თქვენ გაქვთ ორი ოპერაციები

669
00:28:02,540 --> 00:28:05,880
თქვენ გაქვთ ერთი მოუწოდა დააყენებს
და დასძინა, რაღაც დასტის,

670
00:28:05,880 --> 00:28:08,320
აყენებს სხვა tray
უკან ზევით Stack.

671
00:28:08,320 --> 00:28:11,350
და მაშინ პოპ, რაც იმას ნიშნავს,
მიიღოს უმაღლეს tray off.

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
აუდიტორია: ისინი აპირებენ პოპ ერთი off.

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
რომ ბოლო პუნქტის არის
იქნება პირველი out.

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
თუ თქვენ ერთი ამ გულშემატკივართა ბიჭები ან
გოგონებს, რომ ნამდვილად უყვარს Apple პროდუქცია

693
00:29:07,560 --> 00:29:10,130
და თქვენ გამოიღვიძა up at 3:00 AM
გამოდიან რაღაც მაღაზიაში

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
ეს იქნებოდა ერთგვარი sucked, თუ თქვენ
იქ პირველად Apple Store

699
00:29:21,690 --> 00:29:25,700
მაგრამ თქვენ ეფექტურად bottommost
უჯრა, რადგან Apple თანამშრომლები შემდეგ

700
00:29:25,700 --> 00:29:28,189
პოპ უკანასკნელი ადამიანი, რომელიც
რეალურად მივიღე ხაზი.

701
00:29:28,189 --> 00:29:31,230
ასე stacks და რიგები, მიუხედავად იმისა,
ფუნქციურად ისინი სახის იგივე

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
>> ახლა ქვევმოთ hood, როგორც დასტის
და რიგიდან შეიძლება განხორციელდეს, თუ როგორ?

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
თუ მე პირველი პირი Apple
შესანახად და ეს არის შესასვლელი კარი,

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
ასე რომ, რა მონაცემები სტრუქტურა
lends თავს მდგომ?

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
და იქ, ალბათ, უბრალოდ აპირებს
კომერციული off სივრცე და დრო

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
და მე ვფიქრობ, Mather ისინი
რეალურად recessed წელს გახსნა.

745
00:31:00,156 --> 00:31:01,950
ამიტომ მართლაც, თითქმის
როგორიცაა Mather გამოყენებით

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
ნება მომეცით დახევის up ერთი სხვა ვიზუალური აქ.

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
>> ასევე, jargon ვიყენებთ
მონაცემთა სტრუქტურები, როგორც ლელო

759
00:31:45,250 --> 00:31:49,510
და ხეები, სადაც trie, კიდევ ერთხელ,
მხოლოდ ერთი, რომლის კვანძების მასივები,

760
00:31:49,510 --> 00:31:51,680
ჯერ კიდევ, თუ რა შეიძლება
გამოიყენოთ grade სკოლა

761
00:31:51,680 --> 00:31:53,860
როდესაც თქვენ გააკეთა ოჯახის
ხე ფოთლები და root

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
ეს მართლაც ხე ერთი
grandparent გზა აქ და შემდეგ

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
>> მაგრამ რა მართლაც გარღვევა ამ ძალიან,
მხოლოდ tease თქვენ ცოტა კოდი,

776
00:32:32,390 --> 00:32:35,370
გავიხსენოთ უკან საწყისი
awhile უკან, რომლის დროსაც

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
და მე ცოტა anal, თუ როგორ
მე ზუსტად რიცხვებით ქუჩაში.

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
>> DAVID 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
და ეს მხოლოდ bottoms
გარეთ, ბაზის შემთხვევაში, თუ

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
თქვენ, რომ იწყება root და აცხადებენ, რომ hm.

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
როგორც ჩანს, მთელი bunch of ხაზები.

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
მოძიება მნიშვნელობა
მოსწონს N, რიცხვი,

813
00:33:57,290 --> 00:34:01,756
და თქვენ გავიდა ერთი მაჩვენებელი
მომცეთ კვანძის ფესვები,

814
00:34:01,756 --> 00:34:04,380
უფრო სწორად, რომ ხე, საიდანაც
თქვენ შეგიძლიათ თქვათ ყველაფერი,

815
00:34:04,380 --> 00:34:08,850
შეამჩნევთ, თუ როგორ პირდაპირ
შეგიძლიათ განახორციელოს ლოგიკა.

816
00:34:08,850 --> 00:34:10,880
თუ ხე null,
ცხადია, რომ ეს არ არსებობს.

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 ნაკლებია, ვიდრე
ხე arrow N-- ახლა arrow n,

821
00:34:17,900 --> 00:34:20,670
გავიხსენოთ, რომ ჩვენ გააცნო super
მოკლედ მეორე დღეს,

822
00:34:20,670 --> 00:34:25,100
და ეს მხოლოდ იმას ნიშნავს de-მინიშნება
მაჩვენებელი და შევხედოთ საველე მოუწოდა n.

823
00:34:25,100 --> 00:34:27,690
ეს იმას ნიშნავს, იქ და
შევხედოთ საველე მოუწოდა n.

824
00:34:27,690 --> 00:34:33,810
ასე რომ, თუ n ღირებულება თქვენ მოცემული, ნაკლებად
მეტი ღირებულების ხეები რიცხვი,

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
n ისევ, რომელიც არის ზედმეტი,
მაგრამ რა არის ოდნავ განსხვავებული?

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
>> ამასობაში, თუ n მეტია, ვიდრე
კვანძის მე გაკეთებული ეძებს,

837
00:35:04,720 --> 00:35:06,690
მე ძებნის მარჯვენა მხარეს.

838
00:35:06,690 --> 00:35:10,880
სხვაგან, თუ ხე არ არის null, და
თუ ელემენტი არ არის, რომ მარცხენა

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
>> ასე რომ, ჩვენ უბრალოდ scratched ზედაპირზე
ახლა ზოგიერთი ამ მონაცემების სტრუქტურები.

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 მეორე teaser

846
00:35:30,250 --> 00:35:32,080
რა ელის მომავალ კვირას და მის ფარგლებს გარეთ.

847
00:35:32,080 --> 00:35:35,390
>> როგორც ჩვენ begin-- საბედნიეროდ თქვენ შეიძლება
აზრით, ჩვენს გადასვლას ნელა

848
00:35:35,390 --> 00:35:38,680
მსოფლიო C და ქვედა
დონეზე განხორციელების დეტალები,

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
ის მოვიდა სამყაროში სასტიკი
ეკრანები, uncaring მარშრუტიზატორები,

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
ის TCP / IP, და ის მიიღო თქვენს მისამართზე.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Warriors წმინდა."

868
00:36:48,074 --> 00:36:49,660
[END ვიდეო აღწარმოების]

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
და ახლა, "Deep Thoughts"
მიერ Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
დავით ყოველთვის იწყება
ლექციები, "ყველა უფლება".

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
[LAUGHING]

879
00:37:13,380 --> 00:37:15,530
[END ვიდეო აღწარმოების]