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

2
00:00:05,259 --> 00:00:08,300
Doug LLOYD: Entón, en CS50, nós Cubrimos
un gran número de diferentes estruturas de datos,

3
00:00:08,300 --> 00:00:09,180
non?

4
00:00:09,180 --> 00:00:11,420
Vimos arrays, e ligados
listas e táboas de hash,

5
00:00:11,420 --> 00:00:15,210
e tenta, pilas e colas.

6
00:00:15,210 --> 00:00:17,579
Tamén imos aprender un pouco
sobre árbores e montes,

7
00:00:17,579 --> 00:00:20,120
pero realmente todos estes acabar
sendo variacións sobre un tema.

8
00:00:20,120 --> 00:00:22,840
Hai realmente estes
tipo de catro ideas básicas

9
00:00:22,840 --> 00:00:25,190
que o resto pode ferver para abaixo.

10
00:00:25,190 --> 00:00:28,150
Arrays, listas ligadas,
táboas de hash, e intenta.

11
00:00:28,150 --> 00:00:30,720
E como dixen, hai
son variacións sobre eles,

12
00:00:30,720 --> 00:00:32,720
pero iso é moi
moi indo para resumir

13
00:00:32,720 --> 00:00:38,140
todo o que vai falar
Sobre esta clase en termos de C.

14
00:00:38,140 --> 00:00:40,140
>> Pero como estes todos medida, non?

15
00:00:40,140 --> 00:00:44,265
Nós falamos sobre os pros e contras
de cada un en vídeos separados sobre eles,

16
00:00:44,265 --> 00:00:46,390
pero hai unha morea de números
sendo xogado en torno.

17
00:00:46,390 --> 00:00:48,723
Hai unha morea de xeral
pensamentos ser xogado ao redor.

18
00:00:48,723 --> 00:00:51,950
Imos tentar e consolidar
Lo en só un lugar.

19
00:00:51,950 --> 00:00:55,507
Imos pesar os pros contra
os contra, e considere

20
00:00:55,507 --> 00:00:57,340
cal a estrutura de datos
pode ser a datos dereita

21
00:00:57,340 --> 00:01:01,440
estrutura para a súa situación particular,
calquera tipo de datos que está a garda.

22
00:01:01,440 --> 00:01:06,625
Non necesariamente ten sempre
usar o super rápida inserción, borrado,

23
00:01:06,625 --> 00:01:10,761
e investigación dunha trie se realmente
non se preocupan inserir e eliminar

24
00:01:10,761 --> 00:01:11,260
Demasiado.

25
00:01:11,260 --> 00:01:13,968
Se precisa só rapidamente aleatoria
acceso, quizais unha matriz é mellor.

26
00:01:13,968 --> 00:01:15,340
Entón, imos destilar iso.

27
00:01:15,340 --> 00:01:18,530
Imos falar sobre cada un dos catro
principais tipos de estruturas de datos

28
00:01:18,530 --> 00:01:21,720
que xa falamos sobre, e
basta ver cando pode ser bo,

29
00:01:21,720 --> 00:01:23,340
e cando poden non ser tan bo.

30
00:01:23,340 --> 00:01:24,610
Entón imos comezar coa matrices.

31
00:01:24,610 --> 00:01:27,300
Entón inserción, que é tipo de malo.

32
00:01:27,300 --> 00:01:31,350
>> A inserción no extremo dunha matriz é OK,
se estamos a construír unha matriz como imos nós.

33
00:01:31,350 --> 00:01:33,570
Pero se nós necesitamos introducir
elementos no medio,

34
00:01:33,570 --> 00:01:35,550
creo que volta a inserción
tipo, hai moito

35
00:01:35,550 --> 00:01:37,510
de desprazamento para axustar un elemento en alí.

36
00:01:37,510 --> 00:01:41,170
E por iso, se nós estamos indo a introducir
calquera lugar, pero ao final dunha matriz,

37
00:01:41,170 --> 00:01:43,590
que probablemente non é tan grande.

38
00:01:43,590 --> 00:01:46,710
>> Do mesmo xeito, a exclusión, a non ser que sexamos
exclusión dende o extremo dunha matriz,

39
00:01:46,710 --> 00:01:49,810
é, probablemente, tampouco tan grande se
nós non queremos deixar lagoas baleiras,

40
00:01:49,810 --> 00:01:50,790
que normalmente non.

41
00:01:50,790 --> 00:01:54,700
Queremos eliminar un elemento, e
a continuación, tipo de facelo cómodo de novo.

42
00:01:54,700 --> 00:01:57,670
E así a exclusión de elementos
unha matriz, tampouco tan grande.

43
00:01:57,670 --> 00:01:58,820
>> Lookup, porén, é grande.

44
00:01:58,820 --> 00:02:00,920
Temos de acceso aleatorio,
investigación de tempo constante.

45
00:02:00,920 --> 00:02:03,800
Nós só dicir sete, e nós imos
a matriz deslocalización sete.

46
00:02:03,800 --> 00:02:05,907
Dicimos 20, coa go
matriz deslocalización 20.

47
00:02:05,907 --> 00:02:07,240
Non temos para percorrer transversalmente.

48
00:02:07,240 --> 00:02:08,630
Iso é moi bo.

49
00:02:08,630 --> 00:02:11,020
>> Arrays tamén son relativamente fáciles de clasificar.

50
00:02:11,020 --> 00:02:14,040
Cada vez que falamos dunha selección
algoritmo, como selección de tipo,

51
00:02:14,040 --> 00:02:18,820
tipo de inserción, bubble sort, merge
tipo, sempre utilizado matrices para facelo,

52
00:02:18,820 --> 00:02:21,860
porque as matrices son moi fáciles de
tipo, con respecto ás estruturas de datos

53
00:02:21,860 --> 00:02:22,970
vimos ata agora.

54
00:02:22,970 --> 00:02:24,320
>> Eles tamén son relativamente pequeno.

55
00:02:24,320 --> 00:02:25,695
Non hai unha morea de espazo extra.

56
00:02:25,695 --> 00:02:29,210
Só anular exactamente tanto
como precisa para almacenar os seus datos,

57
00:02:29,210 --> 00:02:30,320
e iso é moi fermoso isto.

58
00:02:30,320 --> 00:02:33,180
Entón son moi pequenos
e eficiente deste xeito.

59
00:02:33,180 --> 00:02:36,000
Pero outra desvantaxe, con todo,
é que son de tamaño fixo.

60
00:02:36,000 --> 00:02:38,630
Debemos declarar exactamente como
gran queremos que a nosa matriz para ser,

61
00:02:38,630 --> 00:02:39,940
e nós só temos unha oportunidade.

62
00:02:39,940 --> 00:02:41,280
Non podemos crecer e reduci-lo.

63
00:02:41,280 --> 00:02:44,582
>> Se necesitamos crecer ou encoller-lo, nós
Debe declarar unha matriz enteiramente novo,

64
00:02:44,582 --> 00:02:47,750
copiar todos os elementos do
primeira matriz para a segunda matriz.

65
00:02:47,750 --> 00:02:51,410
E se calculou mal que
tempo, debemos facelo de novo.

66
00:02:51,410 --> 00:02:52,760
Non é tan boa.

67
00:02:52,760 --> 00:02:58,750
Entón matrices non nos dan a flexibilidade
ter número variable de elementos.

68
00:02:58,750 --> 00:03:01,320
>> Cunha lista ligada,
inserción é moi fácil.

69
00:03:01,320 --> 00:03:03,290
Nós só alinhavar para adiante.

70
00:03:03,290 --> 00:03:04,892
Eliminación tamén é moi doado.

71
00:03:04,892 --> 00:03:06,100
Temos que atopar os elementos.

72
00:03:06,100 --> 00:03:07,270
Que implica algunha investigación.

73
00:03:07,270 --> 00:03:10,270
>> Pero unha vez que teña atopado o elemento
está a buscar, todo o que precisa facer

74
00:03:10,270 --> 00:03:12,830
é cambiar un punteiro,
posiblemente dous, se ten

75
00:03:12,830 --> 00:03:15,151
unha ligada lista-- un dobre
lista ligada, rather--

76
00:03:15,151 --> 00:03:16,650
e entón pode só liberar o no.

77
00:03:16,650 --> 00:03:18,399
Non ten que cambiar
todo ao seu redor.

78
00:03:18,399 --> 00:03:22,090
Acaba de cambiar dous punteiros,
de xeito que é moi rápido.

79
00:03:22,090 --> 00:03:23,470
>> Lookup é malo, non?

80
00:03:23,470 --> 00:03:26,280
Co fin para nós atopar un
elemento nunha lista ligada,

81
00:03:26,280 --> 00:03:29,154
illadamente ou dobremente conectado,
temos a linear busca-lo.

82
00:03:29,154 --> 00:03:32,320
Temos que comezar a principios e
move o fin, ou comezar a finais do movemento

83
00:03:32,320 --> 00:03:33,860
para o inicio.

84
00:03:33,860 --> 00:03:35,474
Non temos acceso aleatorio máis.

85
00:03:35,474 --> 00:03:37,265
Entón, se estamos facendo un
moita investigación, quizais

86
00:03:37,265 --> 00:03:39,830
unha lista ligada non é
tan bo para nós.

87
00:03:39,830 --> 00:03:43,750
>> Eles tamén son realmente
difícil de resolver, non?

88
00:03:43,750 --> 00:03:45,666
O único xeito que poida
realmente clasificar unha lista ligada

89
00:03:45,666 --> 00:03:47,870
é para clasificalos lo como construílo.

90
00:03:47,870 --> 00:03:50,497
Pero se clasificalos lo como
constrúe-lo, non é máis

91
00:03:50,497 --> 00:03:51,830
facendo insercións rápidas anymore.

92
00:03:51,830 --> 00:03:53,746
Non está só alinhavando
as cousas para adiante.

93
00:03:53,746 --> 00:03:55,710
Ten que atopar o
punto axeitado para poñelas,

94
00:03:55,710 --> 00:03:57,820
e, a continuación, a súa inserción
pasa a ser case tan malo

95
00:03:57,820 --> 00:03:59,390
como a inserción nunha matriz.

96
00:03:59,390 --> 00:04:03,130
Entón listas ligadas non son
tan grande para clasificar os datos.

97
00:04:03,130 --> 00:04:05,830
>> Eles tamén son moi pequeno, tamaño-wise.

98
00:04:05,830 --> 00:04:08,496
Dobremente lista ligada lixeiramente
maior que illadamente listas ligadas,

99
00:04:08,496 --> 00:04:10,620
que son lixeiramente maiores
de matrices, pero non é

100
00:04:10,620 --> 00:04:13,330
unha enorme cantidade de espazo desperdiçado.

101
00:04:13,330 --> 00:04:18,730
Polo tanto, se o espazo é un premio, pero
non un premio moi intenso,

102
00:04:18,730 --> 00:04:22,180
este pode ser o camiño certo a continuación.

103
00:04:22,180 --> 00:04:23,330
>> As táboas de hash.

104
00:04:23,330 --> 00:04:25,850
Inserción nunha táboa hash
é moi sinxelo.

105
00:04:25,850 --> 00:04:26,980
É un proceso de dúas etapas.

106
00:04:26,980 --> 00:04:30,700
En primeiro lugar, necesitamos realizar nosas informacións a través
unha función hash para obter un código de hash,

107
00:04:30,700 --> 00:04:37,550
e, despois, introduza o elemento para o
táboa hash naquel lugar do código hash.

108
00:04:37,550 --> 00:04:40,879
>> Eliminación, semellante a lista ligada,
é doado xa que atopa o elemento.

109
00:04:40,879 --> 00:04:43,170
Ten que atopalo primeiro,
pero, a continuación, cando excluílo,

110
00:04:43,170 --> 00:04:45,128
só precisa cambiar
un par de agullas,

111
00:04:45,128 --> 00:04:47,250
se está a usar o fío separado.

112
00:04:47,250 --> 00:04:49,942
Se está usando enquisa,
ou se non está

113
00:04:49,942 --> 00:04:51,650
usando fío en todo
na súa táboa de hash,

114
00:04:51,650 --> 00:04:53,040
eliminación é realmente moi fácil.

115
00:04:53,040 --> 00:04:57,134
Todo o que precisa facer é botar o
datos, e logo ir a ese lugar.

116
00:04:57,134 --> 00:04:58,925
E no caso de que non facer
ten colisións,

117
00:04:58,925 --> 00:05:01,650
vai ser capaz de borrar moi rapidamente.

118
00:05:01,650 --> 00:05:04,930
>> Agora, a investigación é onde as cousas
estar un pouco máis complicado.

119
00:05:04,930 --> 00:05:06,910
Está na mellor media
de listas ligadas.

120
00:05:06,910 --> 00:05:09,560
Se está usando o fío,
aínda ten unha lista ligada,

121
00:05:09,560 --> 00:05:13,170
o que significa que aínda ten a
Busca detrimento unha lista ligada.

122
00:05:13,170 --> 00:05:18,390
Senón porque está tomando o seu ligada
lista e división lo máis de 100 ou 1000

123
00:05:18,390 --> 00:05:25,380
ou n elementos na súa táboa de hash, é
listas ligadas son todos un enésimo o tamaño.

124
00:05:25,380 --> 00:05:27,650
Son todos substancialmente menor.

125
00:05:27,650 --> 00:05:32,080
Vostede listas n ligada ao contrario
dunha lista ligada de tamaño n.

126
00:05:32,080 --> 00:05:34,960
>> E así, este mundo real constante
factor, que xeralmente

127
00:05:34,960 --> 00:05:39,730
non falar da complexidade en tempo,
fai realmente facer a diferenza aquí.

128
00:05:39,730 --> 00:05:43,020
Así investigación aínda é lineal
buscar se está a usar o fío,

129
00:05:43,020 --> 00:05:46,780
pero a lonxitude da lista
Estás a ver a

130
00:05:46,780 --> 00:05:50,080
é moi, moi curto, por comparación.

131
00:05:50,080 --> 00:05:52,995
De novo, a clasificación é a súa
obxectivo aquí, hash de táboa de

132
00:05:52,995 --> 00:05:54,370
probablemente non é o camiño certo a continuación.

133
00:05:54,370 --> 00:05:56,830
Só ten que usar unha matriz clasificar
é realmente importante para ti.

134
00:05:56,830 --> 00:05:58,590
>> E poden realizar a gama de tamaño.

135
00:05:58,590 --> 00:06:01,640
É difícil dicir se unha
táboa hash é pequeno ou grande,

136
00:06:01,640 --> 00:06:04,110
porque realmente depende de
como gran súa táboa hash é.

137
00:06:04,110 --> 00:06:07,340
Se está indo só para estar almacenando
cinco elementos na súa táboa hash,

138
00:06:07,340 --> 00:06:10,620
e ten unha táboa hash
con 10.000 elementos nel,

139
00:06:10,620 --> 00:06:12,614
probablemente está perdendo unha gran cantidade de espazo.

140
00:06:12,614 --> 00:06:15,030
Contraste sendo tamén pode
ten táboas de hash moi compactas,

141
00:06:15,030 --> 00:06:18,720
pero menor súa táboa hash queda,
canto máis cada unha destas listas ligadas

142
00:06:18,720 --> 00:06:19,220
recibe.

143
00:06:19,220 --> 00:06:22,607
E así non hai realmente ningunha maneira de definir
exactamente o tamaño dunha táboa hash,

144
00:06:22,607 --> 00:06:24,440
pero pode ser seguro
dicir que é xeralmente

145
00:06:24,440 --> 00:06:27,990
vai ser maior que un conectado
lista almacenar os mesmos datos,

146
00:06:27,990 --> 00:06:30,400
pero menor que un trie.

147
00:06:30,400 --> 00:06:32,720
>> E intentos son a cuarta
destas estruturas

148
00:06:32,720 --> 00:06:34,070
que temos que chegou a falar.

149
00:06:34,070 --> 00:06:36,450
A inserción nunha trie é complexo.

150
00:06:36,450 --> 00:06:38,400
Hai unha morea de dinámica
distribución de memoria,

151
00:06:38,400 --> 00:06:40,780
especialmente no inicio,
como está empezando a construír.

152
00:06:40,780 --> 00:06:43,700
Pero é tempo constante.

153
00:06:43,700 --> 00:06:47,690
É só o elemento humano
aquí que fai que sexa complicado.

154
00:06:47,690 --> 00:06:53,250
Ter que atopar punteiro nulo, malloc
espazo, ir alí, o espazo posiblemente malloc

155
00:06:53,250 --> 00:06:54,490
a partir de aí de novo.

156
00:06:54,490 --> 00:06:58,880
O tipo de factor de intimidación de
punteiros en distribución dinámica de memoria

157
00:06:58,880 --> 00:07:00,130
é o obstáculo para limpar.

158
00:07:00,130 --> 00:07:04,550
Pero unha vez que limpou-o, inserción
en realidade vén moi sinxelo,

159
00:07:04,550 --> 00:07:06,810
e é sen dúbida tempo constante.

160
00:07:06,810 --> 00:07:07,680
>> A exclusión é doado.

161
00:07:07,680 --> 00:07:11,330
Todo o que precisa facer é navegar abaixo a
par de agullas e libre o no,

162
00:07:11,330 --> 00:07:12,420
de xeito que é moi bo.

163
00:07:12,420 --> 00:07:13,930
Lookup tamén é moi rápido.

164
00:07:13,930 --> 00:07:16,780
É só con base na
lonxitude dos seus datos.

165
00:07:16,780 --> 00:07:19,924
Polo tanto, se os seus datos é
cinco cadeas de caracteres,

166
00:07:19,924 --> 00:07:22,590
por exemplo, está almacenando cinco
cadeas de caracteres no seu trie,

167
00:07:22,590 --> 00:07:25,439
el só ten cinco pasos para
atopar o que está a procurar.

168
00:07:25,439 --> 00:07:28,480
Cinco é só un factor constante, polo que
de novo, inserción, exclusión e investigación

169
00:07:28,480 --> 00:07:31,670
aquí están todos os tempos constante, de forma eficaz.

170
00:07:31,670 --> 00:07:34,880
>> Outra cousa é que o seu trie é
de feito, medio que xa clasificadas, non?

171
00:07:34,880 --> 00:07:36,800
En virtude de como estamos
elementos Inserir,

172
00:07:36,800 --> 00:07:40,060
indo letra por letra do
clave, ou díxito por díxito da chave,

173
00:07:40,060 --> 00:07:45,084
normalmente, o trie acaba sendo
tipo de clasificadas como construílo.

174
00:07:45,084 --> 00:07:47,250
Realmente non fai
sentido pensar en clasificación

175
00:07:47,250 --> 00:07:49,874
do mesmo xeito que pensamos sobre
con matrices ou listas ligadas,

176
00:07:49,874 --> 00:07:51,070
ou táboas de hash.

177
00:07:51,070 --> 00:07:54,780
Pero, en certo sentido, o seu
trie é clasificada como vai.

178
00:07:54,780 --> 00:07:58,630
>> A desvantaxe, claro, é que
un trie rapidamente pasa a ser enorme.

179
00:07:58,630 --> 00:08:02,970
De todos os puntos de intersección, pode
have-- súa chave está composta de díxitos,

180
00:08:02,970 --> 00:08:04,880
ten 10 outros
lugares que pode ir, o que

181
00:08:04,880 --> 00:08:07,490
significa que cada nodo
contén información

182
00:08:07,490 --> 00:08:11,440
sobre os datos que quere gardar
no nodo que, ademais de 10 punteiros.

183
00:08:11,440 --> 00:08:14,430
Que, en CS50 IDE, é de 80 bytes.

184
00:08:14,430 --> 00:08:17,220
Entón, é, polo menos, 80 bytes para
cada nodo que crear,

185
00:08:17,220 --> 00:08:19,240
e iso non o é contando datos.

186
00:08:19,240 --> 00:08:24,950
E se os seus nodos son
letras en vez de díxitos,

187
00:08:24,950 --> 00:08:27,825
agora ten 26 punteiros
de todos os lugares.

188
00:08:27,825 --> 00:08:32,007
E 26 veces 8 pode ser 200
bytes, ou algo parecido.

189
00:08:32,007 --> 00:08:33,840
E ten o capital
e pode lowercase--

190
00:08:33,840 --> 00:08:35,381
ver onde estou indo con iso, non?

191
00:08:35,381 --> 00:08:37,500
Seus nós pode ser moi
gran, e así a trie

192
00:08:37,500 --> 00:08:40,470
Se, en xeral, pode
estar realmente grande, demasiado.

193
00:08:40,470 --> 00:08:42,630
Polo tanto, se o espazo é alta
premio no seu sistema,

194
00:08:42,630 --> 00:08:45,830
un trie pode non ser o camiño certo para
ir, a pesar dos seus outros beneficios

195
00:08:45,830 --> 00:08:47,780
entran en xogo.

196
00:08:47,780 --> 00:08:48,710
Eu son Doug Lloyd.

197
00:08:48,710 --> 00:08:50,740
Este é CS50.

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