1
00:00:00,000 --> 00:00:05,259

2
00:00:05,259 --> 00:00:08,300
DOUG LLOYD: ასე CS50, ჩვენ დაფარული
ბევრი სხვადასხვა მონაცემთა სტრუქტურები,

3
00:00:08,300 --> 00:00:09,180
არა?

4
00:00:09,180 --> 00:00:11,420
ჩვენ ვნახეთ კოლექტორები, და უკავშირდება
სიები და hash მაგიდები,

5
00:00:11,420 --> 00:00:15,210
და ცდილობს, stacks და რიგები.

6
00:00:15,210 --> 00:00:17,579
ჩვენ ასევე ვისწავლოთ ცოტა
ხეები და heaps,

7
00:00:17,579 --> 00:00:20,120
მაგრამ რეალურად ეს ყველაფერი უბრალოდ დასრულდება
მიმდინარეობს ვარიაციები თემაზე.

8
00:00:20,120 --> 00:00:22,840
მართლაც ეს
სახის ოთხი ძირითადი იდეები

9
00:00:22,840 --> 00:00:25,190
რომ ყველაფერი შეიძლება მოვხარშოთ ქვემოთ.

10
00:00:25,190 --> 00:00:28,150
მასივები, დაკავშირებული სიები,
hash მაგიდები და ლელო.

11
00:00:28,150 --> 00:00:30,720
და როგორც მე ვთქვი,
ვარიაციები, მათ შორის,

12
00:00:30,720 --> 00:00:32,720
მაგრამ ეს არის საკმაოდ
ბევრი ვაპირებ

13
00:00:32,720 --> 00:00:38,140
ყველაფერი ჩვენ ვაპირებთ, რომ გაიგო
შესახებ ამ კლასში თვალსაზრისით C.

14
00:00:38,140 --> 00:00:40,140
>> მაგრამ როგორ გავაკეთოთ ეს ყველა ღონისძიება, არა?

15
00:00:40,140 --> 00:00:44,265
ჩვენ ვისაუბრეთ დადებითი და უარყოფითი მხარეები
თითოეული ცალკე videos მათ,

16
00:00:44,265 --> 00:00:46,390
მაგრამ არსებობს ბევრი ნომრები
მიღების დააგდეს გარშემო.

17
00:00:46,390 --> 00:00:48,723
არსებობს ბევრი საერთო
აზრები მიღების დააგდეს გარშემო.

18
00:00:48,723 --> 00:00:51,950
შევეცადოთ და კონსოლიდაცია
იგი მხოლოდ ერთ ადგილას.

19
00:00:51,950 --> 00:00:55,507
მოდით მოხდეს დადებითი წინააღმდეგ
უარყოფითი, და მიიჩნევს,

20
00:00:55,507 --> 00:00:57,340
რომელიც მონაცემები სტრუქტურა
შეიძლება იყოს უფლება მონაცემები

21
00:00:57,340 --> 00:01:01,440
სტრუქტურა თქვენი კონკრეტული სიტუაცია,
ნებისმიერი სახის მონაცემები, თქვენ შენახვას.

22
00:01:01,440 --> 00:01:06,625
თქვენ არ აუცილებლად ყოველთვის უნდა
გამოიყენოთ სუპერ სწრაფი ჩასმა, წაშლა,

23
00:01:06,625 --> 00:01:10,761
და საძიებელი საქართველოს trie თუ თქვენ ნამდვილად
არ აინტერესებს ჩასმა და წაშლა

24
00:01:10,761 --> 00:01:11,260
ძალიან ბევრი.

25
00:01:11,260 --> 00:01:13,968
თუ თქვენ უბრალოდ სწრაფად შემთხვევითი
ხელმისაწვდომობა, იქნებ მასივი უკეთესია.

26
00:01:13,968 --> 00:01:15,340
მოდით გამოიხადოს რომ.

27
00:01:15,340 --> 00:01:18,530
მოდით ვისაუბროთ თითოეული ოთხი
ძირითადი სახის მონაცემთა სტრუქტურები

28
00:01:18,530 --> 00:01:21,720
რომ ჩვენ ვისაუბრეთ და
უბრალოდ, როდესაც ისინი შეიძლება იყოს კარგი,

29
00:01:21,720 --> 00:01:23,340
და როდესაც ისინი შეიძლება არ იყოს კარგი.

30
00:01:23,340 --> 00:01:24,610
მოდით დავიწყოთ მასივები.

31
00:01:24,610 --> 00:01:27,300
ასე რომ, ჩასმა, რომ სახის ცუდი.

32
00:01:27,300 --> 00:01:31,350
>> Insertion ბოლოს მასივი OK,
თუ ჩვენ ვაშენებთ მასივი, როგორც ჩვენ მივდივართ.

33
00:01:31,350 --> 00:01:33,570
მაგრამ, თუ ჩვენ უნდა ჩაწეროთ
ელემენტების შევიდა შუა,

34
00:01:33,570 --> 00:01:35,550
ვფიქრობ, უკან ჩასმა
დალაგების, იქ არის ბევრი

35
00:01:35,550 --> 00:01:37,510
გადასვლის ჯდება ელემენტს არსებობს.

36
00:01:37,510 --> 00:01:41,170
ასე რომ, თუ ჩვენ ვაპირებთ ჩადეთ
სადმე, მაგრამ ბოლოს მასივი,

37
00:01:41,170 --> 00:01:43,590
ეს, ალბათ, არც ისე დიდი.

38
00:01:43,590 --> 00:01:46,710
>> ანალოგიურად, წაშლა, თუ ჩვენ
წაშლის ბოლოდან მასივი,

39
00:01:46,710 --> 00:01:49,810
ალბათ, ასევე არ არის იმდენად დიდი, თუ
ჩვენ არ გვინდა, რომ დატოვოს ცარიელი ხარვეზები,

40
00:01:49,810 --> 00:01:50,790
რომელიც, როგორც წესი, არა.

41
00:01:50,790 --> 00:01:54,700
ჩვენ გვინდა, რომ ამოიღონ ელემენტს, და
მაშინ ერთგვარი რათა ის snug ერთხელ.

42
00:01:54,700 --> 00:01:57,670
ასე რომ, წაშლის ელემენტების
მასივი, ასევე არც ისე დიდი.

43
00:01:57,670 --> 00:01:58,820
>> ძიება, თუმცა, არის დიდი.

44
00:01:58,820 --> 00:02:00,920
ჩვენ წვდომის,
მუდმივი დრო საძიებელი.

45
00:02:00,920 --> 00:02:03,800
ჩვენ, უბრალოდ, ვამბობთ შვიდი, და ჩვენ წავიდეთ
რომ მასივი გადატანის შვიდი.

46
00:02:03,800 --> 00:02:05,907
ჩვენ ვამბობთ, 20, ერთად წავიდეთ
მასივი გადატანის 20.

47
00:02:05,907 --> 00:02:07,240
ჩვენ არ უნდა iterate მასშტაბით.

48
00:02:07,240 --> 00:02:08,630
ეს არის საკმაოდ კარგი.

49
00:02:08,630 --> 00:02:11,020
>> კოლექტორები ასევე შედარებით ადვილი დასალაგებლად.

50
00:02:11,020 --> 00:02:14,040
ყოველ დროს, ჩვენ ვისაუბრეთ დახარისხება
ალგორითმი, როგორიცაა შერჩევის დალაგების,

51
00:02:14,040 --> 00:02:18,820
Insertion დალაგების, bubble sort, შერწყმა
დალაგების, ჩვენ ყოველთვის გამოიყენება კოლექტორები უნდა გავაკეთოთ,

52
00:02:18,820 --> 00:02:21,860
რადგან მასივები საკმაოდ ადვილი
სახის, შედარებით მონაცემთა სტრუქტურები

53
00:02:21,860 --> 00:02:22,970
ჩვენ ვნახეთ ჯერჯერობით.

54
00:02:22,970 --> 00:02:24,320
>> ისინი ასევე შედარებით მცირე.

55
00:02:24,320 --> 00:02:25,695
იქ არ არის ბევრი დამატებითი ფართი.

56
00:02:25,695 --> 00:02:29,210
თქვენ უბრალოდ გათვალისწინებულია ზუსტად ისევე,
როგორც თქვენ უნდა გამართავს თქვენი მონაცემები,

57
00:02:29,210 --> 00:02:30,320
და ეს საკმაოდ ბევრი იყო.

58
00:02:30,320 --> 00:02:33,180
ასე რომ, ისინი საკმაოდ პატარა
და ეფექტური გზით.

59
00:02:33,180 --> 00:02:36,000
მაგრამ კიდევ ერთი მინუსი, თუმცა,
ის არის, რომ ისინი ფიქსირებული ზომის.

60
00:02:36,000 --> 00:02:38,630
ჩვენ უნდა განაცხადოს რამდენად
დიდი ჩვენ გვინდა ჩვენი მასივი იყოს,

61
00:02:38,630 --> 00:02:39,940
და ჩვენ მხოლოდ ერთი ესროლეს.

62
00:02:39,940 --> 00:02:41,280
ჩვენ ვერ იზრდება და მცირდება იგი.

63
00:02:41,280 --> 00:02:44,582
>> თუ ჩვენ უნდა იზრდება ან მცირდება, მას, ჩვენ
უნდა განაცხადოს სრულიად ახალი მასივი,

64
00:02:44,582 --> 00:02:47,750
დააკოპირეთ ყველა ელემენტები
პირველი მასივი მეორე მასივი.

65
00:02:47,750 --> 00:02:51,410
და თუ ჩვენ ვერ გათვალა, რომ
დროს, ჩვენ უნდა გავაკეთოთ, რომ კიდევ ერთხელ.

66
00:02:51,410 --> 00:02:52,760
არც თუ ისე დიდი.

67
00:02:52,760 --> 00:02:58,750
ასე რომ კოლექტორები არ მოგვცემს მოქნილობა
აქვს ცვლადი ნომრები ელემენტები.

68
00:02:58,750 --> 00:03:01,320
>> ერთად უკავშირდება სია,
ჩასმა საკმაოდ მარტივია.

69
00:03:01,320 --> 00:03:03,290
ჩვენ უბრალოდ დაყენება გადატანა წინ.

70
00:03:03,290 --> 00:03:04,892
წაშლა ასევე საკმაოდ მარტივია.

71
00:03:04,892 --> 00:03:06,100
ჩვენ უნდა მოვძებნოთ ელემენტებს.

72
00:03:06,100 --> 00:03:07,270
ეს მოითხოვს გარკვეულ ძებნას.

73
00:03:07,270 --> 00:03:10,270
>> მაგრამ ერთხელ თქვენ ი ელემენტს
თქვენ ეძებთ, ყველა თქვენ უნდა გავაკეთოთ

74
00:03:10,270 --> 00:03:12,830
არის შეცვლის მაჩვენებელი,
შესაძლოა, ორი თუ თქვენ გაქვთ

75
00:03:12,830 --> 00:03:15,151
დაკავშირებული list-- ორმაგად
დაკავშირებული სიაში, rather--

76
00:03:15,151 --> 00:03:16,650
და მაშინ შეგიძლიათ უბრალოდ გასათავისუფლებლად კვანძი.

77
00:03:16,650 --> 00:03:18,399
თქვენ არ უნდა გადაიტანოს
გარშემო ყველაფერი.

78
00:03:18,399 --> 00:03:22,090
თქვენ უბრალოდ შეცვალოს ორი მითითებას,
ასე რომ, საკმაოდ სწრაფად.

79
00:03:22,090 --> 00:03:23,470
>> ძიება არის ცუდი, თუმცა, არა?

80
00:03:23,470 --> 00:03:26,280
იმისათვის, რომ იპოვოს
ელემენტს უკავშირდება სია,

81
00:03:26,280 --> 00:03:29,154
ან დამოუკიდებლად ან ორმაგად უკავშირდება,
ჩვენ სწორხაზოვან ძიება იგი.

82
00:03:29,154 --> 00:03:32,320
ჩვენ უნდა დავიწყოთ დასაწყისში და
გადაადგილება ბოლოს, ან ბოლოს დაიწყება ნაბიჯი

83
00:03:32,320 --> 00:03:33,860
დასაწყისში.

84
00:03:33,860 --> 00:03:35,474
ჩვენ არ გვაქვს წვდომის აღარ.

85
00:03:35,474 --> 00:03:37,265
ასე რომ, თუ ჩვენ ვაკეთებთ
ბევრი ეძებს, იქნებ

86
00:03:37,265 --> 00:03:39,830
უკავშირდება სიაში არ არის
ისე კარგია ჩვენთვის.

87
00:03:39,830 --> 00:03:43,750
>> ისინი ასევე ნამდვილად
ძნელია დასალაგებლად, არა?

88
00:03:43,750 --> 00:03:45,666
ერთადერთი გზა შეგიძლიათ
ნამდვილად დასალაგებლად უკავშირდება სიაში

89
00:03:45,666 --> 00:03:47,870
დასალაგებლად, როგორც თქვენ აშენდეს.

90
00:03:47,870 --> 00:03:50,497
მაგრამ თუ თქვენ დასალაგებლად, როგორც თქვენ
მშენებლობა იგი, თქვენ აღარ

91
00:03:50,497 --> 00:03:51,830
მიღების სწრაფი ჩანართები მთელი მსოფლიოს მასშტაბით.

92
00:03:51,830 --> 00:03:53,746
თქვენ არა მხოლოდ tacking
რამ გადატანა წინ.

93
00:03:53,746 --> 00:03:55,710
თქვენ უნდა მოვძებნოთ
სწორი ადგილზე დააყენოს,

94
00:03:55,710 --> 00:03:57,820
და შემდეგ თქვენი ჩასმა
ხდება მხოლოდ როგორც ცუდი

95
00:03:57,820 --> 00:03:59,390
როგორც ჩასმა მასივი.

96
00:03:59,390 --> 00:04:03,130
ასე უკავშირდება სიები არ არის
იმდენად დიდი დახარისხება მონაცემები.

97
00:04:03,130 --> 00:04:05,830
>> ისინი ასევე საკმაოდ პატარა, ზომა ბრძენი.

98
00:04:05,830 --> 00:04:08,496
ორმაგად უკავშირდება სიაში ოდნავ
უფრო დიდი, ვიდრე ცალკე უკავშირდება სიები,

99
00:04:08,496 --> 00:04:10,620
რომლებიც ოდნავ დიდი
ვიდრე კოლექტორები, მაგრამ ეს არ არის

100
00:04:10,620 --> 00:04:13,330
დიდი ოდენობით შეეწირა სივრცეში.

101
00:04:13,330 --> 00:04:18,730
ასე რომ, თუ სივრცეში პრემია, მაგრამ
არ არის მართლაც ინტენსიური პრემია,

102
00:04:18,730 --> 00:04:22,180
ეს შეიძლება იყოს სწორი გზა წასვლა.

103
00:04:22,180 --> 00:04:23,330
>> Hash მაგიდები.

104
00:04:23,330 --> 00:04:25,850
ჩანართი hash მაგიდა
საკმაოდ მარტივია.

105
00:04:25,850 --> 00:04:26,980
ეს არის ორი ნაბიჯი პროცესში.

106
00:04:26,980 --> 00:04:30,700
პირველი, ჩვენ უნდა აწარმოებს ჩვენი მონაცემები
ქეშირების ფუნქცია მისაღებად hash კოდი,

107
00:04:30,700 --> 00:04:37,550
და მაშინ ჩვენ ჩადეთ ელემენტს შევიდა
hash მაგიდაზე რომ hash კოდი ადგილმდებარეობა.

108
00:04:37,550 --> 00:04:40,879
>> წაშლა, მსგავსი უკავშირდება სია,
არის ადვილი ერთხელ თქვენ ნახავთ ელემენტს.

109
00:04:40,879 --> 00:04:43,170
თქვენ უნდა იპოვოთ იგი, პირველ რიგში,
მაგრამ მაშინ, როცა წაშლა,

110
00:04:43,170 --> 00:04:45,128
თქვენ უბრალოდ უნდა გაცვალონ
რამდენიმე მითითებას,

111
00:04:45,128 --> 00:04:47,250
თუ თქვენ იყენებთ ცალკე chaining.

112
00:04:47,250 --> 00:04:49,942
თუ თქვენ იყენებთ საცდელი,
ან თუ თქვენ არა

113
00:04:49,942 --> 00:04:51,650
გამოყენებით მიჯაჭვის ყველა
თქვენი hash მაგიდა,

114
00:04:51,650 --> 00:04:53,040
წაშლა არის რეალურად მართლაც ადვილია.

115
00:04:53,040 --> 00:04:57,134
ყველაფერი რაც თქვენ გჭირდებათ რომ გააკეთოთ, არის hash
მონაცემები, და მერე იმ ადგილას.

116
00:04:57,134 --> 00:04:58,925
და ვთქვათ, თქვენ არ
გაქვთ რაიმე collisions,

117
00:04:58,925 --> 00:05:01,650
თქვენ გექნებათ წაშალოთ ძალიან სწრაფად.

118
00:05:01,650 --> 00:05:04,930
>> ახლა, ძიება, სადაც ყველაფერი
კიდევ ცოტა უფრო რთული.

119
00:05:04,930 --> 00:05:06,910
ეს საშუალოდ უკეთესი
ვიდრე დაკავშირებული სიები.

120
00:05:06,910 --> 00:05:09,560
თუ თქვენ იყენებთ chaining,
თქვენ ჯერ კიდევ აქვს უკავშირდება სია,

121
00:05:09,560 --> 00:05:13,170
რაც იმას ნიშნავს, თქვენ გაქვთ
ძიება აზიანებს უკავშირდება სიაში.

122
00:05:13,170 --> 00:05:18,390
იმის გამო, რომ თქვენ მიღების თქვენი უკავშირდება
სიაში და გაყოფის იგი 100-ზე მეტი ან 1000

123
00:05:18,390 --> 00:05:25,380
ან n ელემენტების თქვენი hash მაგიდა, თქვენ
დაკავშირებული სიები ყველა ერთი nth ზომა.

124
00:05:25,380 --> 00:05:27,650
ისინი ყველა არსებითად პატარა.

125
00:05:27,650 --> 00:05:32,080
თქვენ არ n დაკავშირებული სიები ნაცვლად
ერთი უკავშირდება სიაში ზომა n.

126
00:05:32,080 --> 00:05:34,960
>> ასე რომ, ამ რეალურ სამყაროში მუდმივი
ფაქტორი, რომელიც ჩვენ, როგორც წესი,

127
00:05:34,960 --> 00:05:39,730
არ საუბრობენ დრო სირთულის, ის
ამჯამად რეალურად განსხვავებას აქ.

128
00:05:39,730 --> 00:05:43,020
ასე რომ, ძიება კვლავ ხაზოვანი
ძიება თუ თქვენ იყენებთ chaining,

129
00:05:43,020 --> 00:05:46,780
მაგრამ სიგრძეზე სია
თქვენ ეძებს მეშვეობით

130
00:05:46,780 --> 00:05:50,080
ძალიან, ძალიან მოკლე შედარებით.

131
00:05:50,080 --> 00:05:52,995
კიდევ ერთხელ, თუ დახარისხება თქვენი
მიზანი აქ, hash მაგიდა

132
00:05:52,995 --> 00:05:54,370
ალბათ, არ არის სწორი გზა წასვლა.

133
00:05:54,370 --> 00:05:56,830
უბრალოდ გამოიყენოთ მასივი თუ დახარისხება
მართლაც მნიშვნელოვანია თქვენთვის.

134
00:05:56,830 --> 00:05:58,590
>> და მათ შეუძლიათ აწარმოებს გამის ზომა.

135
00:05:58,590 --> 00:06:01,640
ეს ძნელი სათქმელია, თუ არა
hash მაგიდა არის პატარა და დიდი,

136
00:06:01,640 --> 00:06:04,110
იმიტომ, რომ ეს ნამდვილად არის დამოკიდებული
დიდი თქვენი hash მაგიდა.

137
00:06:04,110 --> 00:06:07,340
თუ თქვენ მხოლოდ იქნება შენახვის
ხუთ ელემენტები თქვენი hash მაგიდა,

138
00:06:07,340 --> 00:06:10,620
და თქვენ უნდა hash მაგიდა
10,000 ელემენტების ის,

139
00:06:10,620 --> 00:06:12,614
თქვენ ალბათ კარგვაა ბევრი სივრცეში.

140
00:06:12,614 --> 00:06:15,030
კონტრასტი რომ თქვენ ასევე შეგიძლიათ
აქვს ძალიან კომპაქტური hash მაგიდები,

141
00:06:15,030 --> 00:06:18,720
მაგრამ პატარა თქვენი hash მაგიდა იღებს,
აღარ თითოეული იმ დაკავშირებული სიები

142
00:06:18,720 --> 00:06:19,220
იღებს.

143
00:06:19,220 --> 00:06:22,607
ასე რომ, იქ ნამდვილად არ გზა განსაზღვროს
ზუსტად ზომა hash მაგიდა,

144
00:06:22,607 --> 00:06:24,440
მაგრამ ეს, ალბათ უსაფრთხო
უნდა ითქვას, რომ ეს ზოგადად

145
00:06:24,440 --> 00:06:27,990
იქნება უფრო დიდი, ვიდრე უკავშირდება
სია შენახვის იგივე მონაცემების მიხედვით,

146
00:06:27,990 --> 00:06:30,400
მაგრამ ნაკლებია trie.

147
00:06:30,400 --> 00:06:32,720
>> და ცდილობს მეოთხე
ამ სტრუქტურების

148
00:06:32,720 --> 00:06:34,070
ჩვენ ვლაპარაკობდით.

149
00:06:34,070 --> 00:06:36,450
ჩასმა შევიდა trie არის რთული.

150
00:06:36,450 --> 00:06:38,400
არსებობს ბევრი დინამიური
მეხსიერების გამოყოფის,

151
00:06:38,400 --> 00:06:40,780
განსაკუთრებით დასაწყისში,
როგორც თქვენ დაწყებული აშენება.

152
00:06:40,780 --> 00:06:43,700
მაგრამ ეს არის მუდმივი დრო.

153
00:06:43,700 --> 00:06:47,690
ეს მხოლოდ ადამიანის ელემენტს
აქ რომ ხდის სახიფათო.

154
00:06:47,690 --> 00:06:53,250
ექმნებათ null მაჩვენებელი, malloc
სივრცე, იქ, შესაძლოა malloc ფართი

155
00:06:53,250 --> 00:06:54,490
იქიდან ერთხელ.

156
00:06:54,490 --> 00:06:58,880
დალაგების დაშინების ფაქტორი
პოინტერები დინამიური მეხსიერების გამოყოფის

157
00:06:58,880 --> 00:07:00,130
არის დაბრკოლება გარკვევა.

158
00:07:00,130 --> 00:07:04,550
მაგრამ ერთხელ თქვენ განბაჟებული ის, ჩასმა
რეალურად საქმე საკმაოდ მარტივია,

159
00:07:04,550 --> 00:07:06,810
და რა თქმა უნდა, არის მუდმივი დრო.

160
00:07:06,810 --> 00:07:07,680
>> წაშლა არ არის ადვილი.

161
00:07:07,680 --> 00:07:11,330
ყველა თქვენ უნდა გააკეთოთ ნავიგაცია ქვემოთ
რამდენიმე მითითებას და თავისუფალი კვანძის,

162
00:07:11,330 --> 00:07:12,420
ასე რომ, საკმაოდ კარგი.

163
00:07:12,420 --> 00:07:13,930
ძიება არის ასევე საკმაოდ სწრაფად.

164
00:07:13,930 --> 00:07:16,780
ეს მხოლოდ საფუძველზე
ხანგრძლივობა თქვენი მონაცემები.

165
00:07:16,780 --> 00:07:19,924
ასე რომ, თუ ყველა თქვენი მონაცემები
ხუთ ხასიათის სტრიქონები,

166
00:07:19,924 --> 00:07:22,590
მაგალითად, თქვენ შენახვა ხუთ
ხასიათის სტრიქონები თქვენს trie,

167
00:07:22,590 --> 00:07:25,439
ეს მხოლოდ იღებს ხუთი საფეხურით
იპოვოს ის, რაც თქვენ ეძებთ.

168
00:07:25,439 --> 00:07:28,480
ხუთი არის მუდმივი ფაქტორი, ასე რომ
ერთხელ, ჩასმა, წაშლა და ძიება

169
00:07:28,480 --> 00:07:31,670
აქ არის ყველა, მუდმივი, ეფექტურად.

170
00:07:31,670 --> 00:07:34,880
>> სხვა საქმეა, რომ თქვენი trie არის
რეალურად სახის უკვე დახარისხებული, არა?

171
00:07:34,880 --> 00:07:36,800
ძალით, თუ როგორ ჩვენ
ჩასმის ელემენტები,

172
00:07:36,800 --> 00:07:40,060
აპირებს წერილი წერილი საქართველოს
გასაღები, ან ციფრი მიერ ციფრი გასაღები,

173
00:07:40,060 --> 00:07:45,084
როგორც წესი, თქვენი trie მთავრდება
სახის დალაგებულია როგორც თქვენ აშენება.

174
00:07:45,084 --> 00:07:47,250
ეს ნამდვილად არ აკეთებს
გრძნობა, რომ ვიფიქროთ, დახარისხება

175
00:07:47,250 --> 00:07:49,874
იგივე გზა ჩვენ ვიფიქროთ
ეს მასივები, ან უკავშირდება სიები,

176
00:07:49,874 --> 00:07:51,070
ან hash მაგიდები.

177
00:07:51,070 --> 00:07:54,780
მაგრამ გარკვეული თვალსაზრისით, თქვენი
trie დალაგებულია როგორც თქვენ გადასვლა.

178
00:07:54,780 --> 00:07:58,630
>> მინუსი, რა თქმა უნდა, არის ის, რომ
trie, სწრაფად ხდება დიდი.

179
00:07:58,630 --> 00:08:02,970
ყოველი გადაკვეთაზე წერტილი, თქვენ შეიძლება
ჰქონდეს თუ თქვენი გასაღები შედგება ციფრები,

180
00:08:02,970 --> 00:08:04,880
თქვენ გაქვთ 10 სხვა
ადგილებზე შეგიძლიათ გადასვლა, რომელიც

181
00:08:04,880 --> 00:08:07,490
იმას ნიშნავს, რომ ყველა კვანძის
შეიცავს ინფორმაციას

182
00:08:07,490 --> 00:08:11,440
მონაცემები გსურთ შეინახოთ
რომ კვანძის, პლიუს 10 მითითებას.

183
00:08:11,440 --> 00:08:14,430
რაც, CS50 IDE, არის 80 ბაიტი.

184
00:08:14,430 --> 00:08:17,220
ასე რომ, ეს მინიმუმ 80 ბაიტი
ყველა კვანძის რომ თქვენ შექმნათ,

185
00:08:17,220 --> 00:08:19,240
და ეს არ არის კი დამთვლელი მონაცემები.

186
00:08:19,240 --> 00:08:24,950
და თუ თქვენი კვანძების
წერილების ნაცვლად ციფრები,

187
00:08:24,950 --> 00:08:27,825
ახლა თქვენ გაქვთ 26 მითითებას
ყველა ადგილმდებარეობა.

188
00:08:27,825 --> 00:08:32,007
და 26-ჯერ 8 არის ალბათ 200
ბაიტი, ან რაღაც მსგავსი.

189
00:08:32,007 --> 00:08:33,840
და თქვენ უნდა კაპიტალი
და ამას თქვენ შეგიძლიათ

190
00:08:33,840 --> 00:08:35,381
ვხედავ, სადაც მე ვაპირებ ამ, არა?

191
00:08:35,381 --> 00:08:37,500
შენი კვანძების შეიძლება მიიღოს მართლაც
დიდი, და ასე trie

192
00:08:37,500 --> 00:08:40,470
თავად, საერთო ჯამში, შეიძლება
ნამდვილად დიდი, ძალიან.

193
00:08:40,470 --> 00:08:42,630
ასე რომ, თუ სივრცეში არის მაღალი
პრემია თქვენი სისტემის,

194
00:08:42,630 --> 00:08:45,830
trie, არ შეიძლება იყოს სწორი გზა
წასვლა, მიუხედავად იმისა, რომ მისი სხვა სარგებელი

195
00:08:45,830 --> 00:08:47,780
მოვიდეს პიესა.

196
00:08:47,780 --> 00:08:48,710
მე Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
ეს არის CS50.

198
00:08:50,740 --> 00:08:52,316