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

2
00:00:05,259 --> 00:00:08,300
Даг LLOYD: Значи во CS50, ние сме опфатени
голем број на различни структури на податоци,

3
00:00:08,300 --> 00:00:09,180
нели?

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

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

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
>> Хаш маси.

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 или 1000

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

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

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
но помала од 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
Морале да се судрите со нулти покажувач, Примерок
простор, оди таму, можеби Примерок простор

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
или хаш маси.

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
Од секоја крстосница момент, може да
have-- ако вашиот клуч се состои од бројки,

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 ИРО, е 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
И имаш капитал
а вие може lowercase--

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
Јас сум Даг Лојд.

197
00:08:48,710 --> 00:08:50,740
Ова е CS50.

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