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

2
00:00:05,259 --> 00:00:08,300
Даг Ллоид: Дакле, у ЦС50 смо покривени
много различитих структура података,

3
00:00:08,300 --> 00:00:09,180
jel tako?

4
00:00:09,180 --> 00:00:11,420
Видели смо низова, и повезан
листе, и хасх табеле,

5
00:00:11,420 --> 00:00:15,210
и покушава, гомила и редови.

6
00:00:15,210 --> 00:00:17,579
Такође ћемо научити нешто
о дрвећу и гомиле,

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
Арраис, повезане листе,
хасх табеле, и покушава.

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
Све ћемо да причамо
абоут у овој класи у смислу Ц.

14
00:00:38,140 --> 00:00:40,140
>> Али како то све мере, зар не?

15
00:00:40,140 --> 00:00:44,265
Разговарали смо о предностима и недостацима
сваког у одвојеним видео на њима,

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
и ИП адресу од Трие ако заиста
не маре за уметање и брисање

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
>> Постављање на крају низа је у реду,
ако градимо низ како идемо.

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
Желимо да уклоните елемент, и
онда некако би се поново фино.

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
Ми не морамо да преко поновити.

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
уметање врста, балон врста, спајање
врста, увек се користи низове да то уради,

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
то повезано лист-- представљају двоструко
линкед лист, ратхер--

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
Не само да тацкинг
ствари на фронту.

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
>> Хасх таблес.

104
00:04:23,330 --> 00:04:25,850
Убацивање у хеш табели
је прилично једноставан.

105
00:04:25,850 --> 00:04:26,980
То је процес у два корака.

106
00:04:26,980 --> 00:04:30,700
Прво морамо да водимо податке преко
хасх функција да бисте добили хеш код,

107
00:04:30,700 --> 00:04:37,550
и онда убаците елемент у
хеш табеле на тој хеш код локацији.

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
ако користите посебан цхаининг.

112
00:04:47,250 --> 00:04:49,942
Ако користите прескок,
или, ако ниси

113
00:04:49,942 --> 00:04:51,650
користећи цхаининг уопште
у вашем хасх табели,

114
00:04:51,650 --> 00:04:53,040
Брисање је заправо веома лако.

115
00:04:53,040 --> 00:04:57,134
Све што треба да урадите је да емитују
података, а затим пређите на тој локацији.

116
00:04:57,134 --> 00:04:58,925
И под претпоставком да не
имате судара,

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
Ако користите уланцавање,
и даље имате повезану листу,

121
00:05:09,560 --> 00:05:13,170
што значи да још увек имају
Претрага штету повезану листу.

122
00:05:13,170 --> 00:05:18,390
Али пошто узимаш свој повезан
листа и то цијепање преко 100 или 1.000

123
00:05:18,390 --> 00:05:25,380
или н елемената у вашем хасх табели, ти си
повезане листе су сви једно сис величине.

124
00:05:25,380 --> 00:05:27,650
Сви су знатно мањи.

125
00:05:27,650 --> 00:05:32,080
Ви сте повезани листе уместо н
једне повезане листе величине н.

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
Дакле ИП адресу и даље линеарна
тражење ако користите уланцавање,

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
Опет, ако је ваш сортирање
циљ овде, хасх сто је

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
Тешко је рећи да ли је
Дисперзија сто је мали или велики,

136
00:06:01,640 --> 00:06:04,110
јер то стварно зависи
колика ти хасх сто је.

137
00:06:04,110 --> 00:06:07,340
Ако само идете да се складиштење
пет елемената у вашем хасх табели,

138
00:06:07,340 --> 00:06:10,620
и имате хасх табелу
са 10.000 елементе у њој,

139
00:06:10,620 --> 00:06:12,614
вероватно губимо пуно простора.

140
00:06:12,614 --> 00:06:15,030
Цонтраст вам такође може да буде
имају веома компактне хасх табеле,

141
00:06:15,030 --> 00:06:18,720
али је мањи ваш хеш табеле добија,
дуже сваки од тих повезаних листи

142
00:06:18,720 --> 00:06:19,220
добија.

143
00:06:19,220 --> 00:06:22,607
И тако заиста не постоји начин да се дефинише
управо величине хеш табели,

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
али мање од Трие.

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
Убацивање у Трие је сложен.

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
Имајући у сусрет Нулл Поинтер, маллоц
простор, иди тамо, вероватно маллоц простор

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
На пример, ви чување пет
низови карактера у вашем Трие,

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
>> Друга ствар је да је ваш трие је
некако већ поредани, зар не?

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
обично, ваш трие завршила се као
врста поредани као што сте га градити.

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
или хасх табеле.

177
00:07:51,070 --> 00:07:54,780
Али, у неком смислу, твој
трие се разврстава као ти.

178
00:07:54,780 --> 00:07:58,630
>> Лоша страна је, наравно, да
Трие брзо постаје огроман.

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
Који, на ЦС50 ИДЕ, је 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
Ваши чворови могу се стварно
велика, и тако Трие

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
трие можда није прави начин да се
го, иако њени друге бенефиције

195
00:08:45,830 --> 00:08:47,780
ступају на сцену.

196
00:08:47,780 --> 00:08:48,710
Ја сам Доуг Лојд.

197
00:08:48,710 --> 00:08:50,740
Ово је ЦС50.

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