1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN Schmid: Ás veces, cando a construción dun
programa, pode querer usar un

3
00:00:10,890 --> 00:00:13,190
estrutura de datos coñecida como un dicionario.

4
00:00:13,190 --> 00:00:17,960
Un dicionario claves mapas, que son
xeralmente cordas, cos valores, Ints,

5
00:00:17,960 --> 00:00:21,900
caracteres, un punteiro para un obxecto,
o que queiramos.

6
00:00:21,900 --> 00:00:26,510
É como dicionarios comúns
Que mapa palabras través de axustes.

7
00:00:26,510 --> 00:00:29,440
>> Dicionarios nos ofrecer o
capacidade de almacenar información

8
00:00:29,440 --> 00:00:32,750
asociado a algo
e procura-lo máis tarde.

9
00:00:32,750 --> 00:00:36,620
Entón, como é que imos realmente implementar un
dicionario, por exemplo, en código C que pudermos

10
00:00:36,620 --> 00:00:38,460
usar en un dos nosos programas?

11
00:00:38,460 --> 00:00:41,790
Así, hai unha serie de formas que
poderiamos aplicar un dicionario.

12
00:00:41,790 --> 00:00:45,930
>> Por unha banda, poderíamos utilizar unha matriz que
dinámica re-size ou poderiamos usar un

13
00:00:45,930 --> 00:00:49,150
lista ligada, táboa hash
ou unha árbore binaria.

14
00:00:49,150 --> 00:00:52,250
Pero o que quere que nós escoller, hai que
ser consciente da eficiencia e da

15
00:00:52,250 --> 00:00:54,300
desempeño da implementación.

16
00:00:54,300 --> 00:00:57,930
Debemos pensar sobre o algoritmo usado
para introducir e buscar os elementos en

17
00:00:57,930 --> 00:00:59,120
a estrutura de datos.

18
00:00:59,120 --> 00:01:03,060
>> Por agora, imos supor que nós
quere usar cadeas como claves.

19
00:01:03,060 --> 00:01:07,290
Imos falar sobre unha posibilidade,
unha estrutura de datos chamada de trie.

20
00:01:07,290 --> 00:01:11,210
Entón aquí está unha representación visual
dun trie.

21
00:01:11,210 --> 00:01:14,590
>> Como a imaxe suxire, un trie
é unha estrutura de datos en árbore con

22
00:01:14,590 --> 00:01:16,050
nós conectados.

23
00:01:16,050 --> 00:01:19,420
Vemos que hai claramente unha raíz
nó con algúns enlaces que se estende ata

24
00:01:19,420 --> 00:01:20,500
outros nós.

25
00:01:20,500 --> 00:01:23,040
Pero o que é que cada nodo consiste?

26
00:01:23,040 --> 00:01:26,700
Se asumimos que estamos almacenar claves
con só caracteres alfabéticos, e

27
00:01:26,700 --> 00:01:30,150
que non se preocupan a capitalización,
aquí está unha definición dun nó que

28
00:01:30,150 --> 00:01:31,100
será suficiente.

29
00:01:31,100 --> 00:01:34,130
>> Un obxecto cuxo tipo é struct
nó ten dúas pezas

30
00:01:34,130 --> 00:01:35,740
chamada de datos e nenos.

31
00:01:35,740 --> 00:01:39,200
Nós deixamos a parte de datos como un comentario
para ser substituído por un compoñente

32
00:01:39,200 --> 00:01:43,190
declaración cando nodo struct é
incorporados nun programa C.

33
00:01:43,190 --> 00:01:47,040
A parte de datos dun nodo pode ser un
Valor booleano para indicar se

34
00:01:47,040 --> 00:01:51,160
non representa o no a conclusión
dunha chave de dicionario ou pode ser unha

35
00:01:51,160 --> 00:01:54,240
cadea que representa a definición
dunha palabra no dicionario.

36
00:01:54,240 --> 00:01:58,870
>> Imos usar un rostro sorridente para indicar
cando os datos están presentes nun nodo.

37
00:01:58,870 --> 00:02:02,310
Hai 26 elementos na nosa
variedade nenos, un índice

38
00:02:02,310 --> 00:02:03,690
por carácter alfabético.

39
00:02:03,690 --> 00:02:06,570
Imos ver o significado
deste breve.

40
00:02:06,570 --> 00:02:10,759
>> Imos mirar máis de preto do nodo raíz
no noso diagrama, que non ten datos

41
00:02:10,759 --> 00:02:14,740
asociada con el, tal como indica a
ausencia do rostro sorridente no

42
00:02:14,740 --> 00:02:16,110
porción de datos.

43
00:02:16,110 --> 00:02:19,910
As frechas que se estenden a partir das partes de
os fillos de matriz representan non nodo

44
00:02:19,910 --> 00:02:21,640
punteiros para outros nós.

45
00:02:21,640 --> 00:02:25,500
Por exemplo, a frecha que se estende desde o
o segundo elemento de nenos

46
00:02:25,500 --> 00:02:28,400
representa a letra B
nunha chave de dicionario.

47
00:02:28,400 --> 00:02:31,920
E no diagrama maior
que rótulo-la cun B.

48
00:02:31,920 --> 00:02:35,810
>> Teña en conta que, no diagrama de máis, cando
deseñar un punteiro a outro no, el

49
00:02:35,810 --> 00:02:39,100
Non importa onde a punta da frecha
cumpre que outro nodo.

50
00:02:39,100 --> 00:02:43,850
O noso dicionario mostra contén trie
dúas palabras, que e zoom.

51
00:02:43,850 --> 00:02:47,040
Imos examinar un exemplo de
mirando cara arriba de datos para unha chave.

52
00:02:47,040 --> 00:02:50,800
>> Supoña que quería buscar o
valor correspondente ao baño de clave.

53
00:02:50,800 --> 00:02:53,610
Imos comezar a nosa mirada cara arriba
no nodo raíz.

54
00:02:53,610 --> 00:02:57,870
Entón nós imos ter a primeira letra do noso
clave, B, e atopar o correspondente

55
00:02:57,870 --> 00:03:00,020
detectar, na nosa disposición fillos.

56
00:03:00,020 --> 00:03:04,490
Teña en conta que hai exactamente 26 puntos
na matriz, un para cada letra

57
00:03:04,490 --> 00:03:05,330
o alfabeto.

58
00:03:05,330 --> 00:03:08,800
E nós imos ter os puntos representan o
letras do alfabeto en orde.

59
00:03:08,800 --> 00:03:13,960
>> Nós imos ollar para a segunda índice, logo
índice de un, para B. En xeral, se

60
00:03:13,960 --> 00:03:17,990
Ten algún character C nós
podería determinar o punto correspondente

61
00:03:17,990 --> 00:03:21,520
na matriz nenos a usar
un cálculo así.

62
00:03:21,520 --> 00:03:25,140
Poderiamos usar un nenos maiores
array se queriamos ofrecer ollar-se de

63
00:03:25,140 --> 00:03:28,380
teclas con unha ampla gama de caracteres,
, Como o todo

64
00:03:28,380 --> 00:03:29,880
Conxunto de caracteres ASCII.

65
00:03:29,880 --> 00:03:32,630
>> Neste caso, o punteiro
na nosa gama nenos en

66
00:03:32,630 --> 00:03:34,320
índice non é nulo.

67
00:03:34,320 --> 00:03:36,600
Entón, imos continuar a buscar
o baño de clave.

68
00:03:36,600 --> 00:03:40,130
Se algunha vez atopou un punteiro nulo
no lugar axeitado nos nenos

69
00:03:40,130 --> 00:03:43,230
array mentres atravesamos os nós,
entón nós imos ter que dicir que nós

70
00:03:43,230 --> 00:03:45,630
non podería atopar calquera cousa a esta chave.

71
00:03:45,630 --> 00:03:49,370
>> Agora, imos dar a segunda letra
nosa clave, A, e continuar seguindo

72
00:03:49,370 --> 00:03:52,400
punteiros, deste xeito ata que nós
chegar ao final da nosa clave.

73
00:03:52,400 --> 00:03:56,530
Se chegar ao final da clave sen
bater nos becos sen saída, os punteiros nulos,

74
00:03:56,530 --> 00:03:59,730
como é o caso aquí, entón nós só
Ten que comprobar unha cousa.

75
00:03:59,730 --> 00:04:02,110
É esta chave realmente
no dicionario?

76
00:04:02,110 --> 00:04:07,660
>> Se é así, hai que atopar un valor, ben a
icona do Smiley cara na nosa diagrama onde

77
00:04:07,660 --> 00:04:08,750
a palabra remata.

78
00:04:08,750 --> 00:04:12,270
Se hai algo máis almacenado con
os datos, entón podemos devolve-lo.

79
00:04:12,270 --> 00:04:16,500
Por exemplo, o xardín zoolóxico de chave non está no
dicionario, aínda que puidésemos ter

80
00:04:16,500 --> 00:04:19,810
acadar o fin desta chave sen nunca
bater un punteiro nulo, mentres nós

81
00:04:19,810 --> 00:04:21,089
percorrer a trie.

82
00:04:21,089 --> 00:04:25,436
>> Se tente ollar para o baño de clave, o
segundo para índice de matriz do último nodo,

83
00:04:25,436 --> 00:04:28,750
correspondente á letra H, que
realizaron un punteiro nulo.

84
00:04:28,750 --> 00:04:31,120
Entón baño non está no dicionario.

85
00:04:31,120 --> 00:04:34,800
E así un trie é único en que as claves
nunca son explicitamente almacenada en

86
00:04:34,800 --> 00:04:36,650
a estrutura de datos.

87
00:04:36,650 --> 00:04:38,810
Entón, como imos introducir algo
nunha trie?

88
00:04:38,810 --> 00:04:41,780
>> Imos introducir a clave
zoolóxico na nosa trie.

89
00:04:41,780 --> 00:04:46,120
Lembre que un rostro sorridente nun nodo
podería corresponder en código para un simple

90
00:04:46,120 --> 00:04:50,170
Valor booleano para indicar que zoo
está no dicionario ou podería

91
00:04:50,170 --> 00:04:53,710
corresponden a máis información que nós
quere asociar co zoolóxico clave,

92
00:04:53,710 --> 00:04:56,860
como a definición do
palabra ou outra cousa.

93
00:04:56,860 --> 00:05:00,350
De certa forma, o proceso para introducir
algo nun trie é semellante ao

94
00:05:00,350 --> 00:05:02,060
buscando algo nunha trie.

95
00:05:02,060 --> 00:05:05,720
>> Imos comezar co nó raíz de novo,
seguintes punteiros correspondentes a

96
00:05:05,720 --> 00:05:07,990
as letras da nosa clave.

97
00:05:07,990 --> 00:05:11,310
Por sorte, fomos capaces de seguir punteiros
todo o camiño ata chegar

98
00:05:11,310 --> 00:05:12,770
o extremo da chave.

99
00:05:12,770 --> 00:05:16,480
Desde zoolóxico é un prefixo da palabra
zoom, que é membro da

100
00:05:16,480 --> 00:05:19,440
dicionario, non
reservar os novos nós.

101
00:05:19,440 --> 00:05:23,140
>> Podemos modificar o nó para indicar que
o camiño de caracteres que conducen a

102
00:05:23,140 --> 00:05:25,360
Representa unha clave no noso dicionario.

103
00:05:25,360 --> 00:05:28,630
Agora imos tratar de introducir o
BAÑO clave na trie.

104
00:05:28,630 --> 00:05:32,260
Imos comezar o nodo raíz
e siga os punteiros novo.

105
00:05:32,260 --> 00:05:35,620
Pero nesta situación, se loita un morto
acabar antes somos capaces de chegar ao

106
00:05:35,620 --> 00:05:36,940
extremo da chave.

107
00:05:36,940 --> 00:05:40,980
Agora, imos ter que reservar algún novo
nós terá que asignar un novo

108
00:05:40,980 --> 00:05:43,660
nó a cada resto
carta de nosa clave.

109
00:05:43,660 --> 00:05:46,740
>> Neste caso, só necesitamos
para reservar un novo nodo.

110
00:05:46,740 --> 00:05:50,590
Entón nós imos ter que facer o índice H
referencia a este novo nodo.

111
00:05:50,590 --> 00:05:54,070
Unha vez máis, podemos modificar o no
indicar que o camiño de caracteres

112
00:05:54,070 --> 00:05:57,120
levando a que representa un
clave no noso dicionario.

113
00:05:57,120 --> 00:06:00,730
Imos razoar sobre o asintótica
complexidade dos nosos procedementos para estes

114
00:06:00,730 --> 00:06:02,110
dúas operacións.

115
00:06:02,110 --> 00:06:06,420
>> Notamos que en ambos os casos, o número
de pasos do noso algoritmo tomou foi

116
00:06:06,420 --> 00:06:09,470
proporcional ao número de
letras da palabra clave.

117
00:06:09,470 --> 00:06:10,220
Iso mesmo.

118
00:06:10,220 --> 00:06:13,470
Cando se quere buscar unha palabra nun
trie só precisa para percorrer

119
00:06:13,470 --> 00:06:17,100
as letras unha a unha ata que quere
acadar o fin da palabra ou

120
00:06:17,100 --> 00:06:19,060
acadar unha rúa sen saída no trie.

121
00:06:19,060 --> 00:06:22,470
>> E cando quere inserir unha chave
par de valores nunha trie mediante o

122
00:06:22,470 --> 00:06:26,250
procedemento discutir, o peor caso
terá que asignar un novo nodo

123
00:06:26,250 --> 00:06:27,550
para cada letra.

124
00:06:27,550 --> 00:06:31,290
E imos supor que a distribución
é unha operación de tempo constante.

125
00:06:31,290 --> 00:06:35,850
Así, se asumirmos que a lonxitude da clave é
delimitada por unha constante fixa, tanto

126
00:06:35,850 --> 00:06:39,400
inserción e mirar para arriba son constantes
operacións de tempo para unha trie.

127
00:06:39,400 --> 00:06:42,930
>> Se non facemos esta suposición de que
a lonxitude da clave é delimitada por un fixo

128
00:06:42,930 --> 00:06:46,650
constante, logo inserción e mirar para arriba,
no peor dos casos, son lineais no

129
00:06:46,650 --> 00:06:48,240
lonxitude da clave.

130
00:06:48,240 --> 00:06:51,800
Nótese que o número de elementos gardados
no trie non afecta a mirada cara arriba

131
00:06:51,800 --> 00:06:52,820
ou o tempo de inserción.

132
00:06:52,820 --> 00:06:55,360
É só impactado pola
lonxitude da clave.

133
00:06:55,360 --> 00:06:59,300
>> En contraste, a adición de entradas para, por exemplo,
unha táboa hash tende a facer

134
00:06:59,300 --> 00:07:01,250
futuro mirar para arriba máis lento.

135
00:07:01,250 --> 00:07:04,520
Aínda que isto poida parecer atractivo a primeira vista,
temos que ter presente que un

136
00:07:04,520 --> 00:07:08,740
complexidade asintótica favorable non
significa que, na práctica os datos

137
00:07:08,740 --> 00:07:11,410
estrutura é necesariamente
irrepreensível.

138
00:07:11,410 --> 00:07:15,860
Debemos considerar tamén que para almacenar un
palabra nunha trie que necesitamos, no peor

139
00:07:15,860 --> 00:07:19,700
caso, un número de nós proporcional
ao longo da propia palabra.

140
00:07:19,700 --> 00:07:21,880
>> Tries tenden a usar unha morea de espazo.

141
00:07:21,880 --> 00:07:25,620
Isto está en contraste cunha táboa hash,
en que só precisa dun novo nodo a

142
00:07:25,620 --> 00:07:27,940
gardar algunhas par de valores clave.

143
00:07:27,940 --> 00:07:31,370
Agora, de novo, en teoría, o espazo grande
consumo non parece ser un gran

144
00:07:31,370 --> 00:07:34,620
tratar, sobre todo tendo en conta que a moderna
ordenadores teñen gigabytes e

145
00:07:34,620 --> 00:07:36,180
gigabytes de memoria.

146
00:07:36,180 --> 00:07:39,200
Pero resulta que aínda temos
preocuparse co uso de memoria e

147
00:07:39,200 --> 00:07:42,540
organización en prol da
rendemento, xa que os computadores modernos

148
00:07:42,540 --> 00:07:46,960
ter mecanismos vixente baixo o
portada para acelerar o acceso á memoria.

149
00:07:46,960 --> 00:07:51,180
>> Pero estes mecanismos funcionan mellor cando
accesos á memoria están feitos en compacto

150
00:07:51,180 --> 00:07:52,810
rexións ou zonas.

151
00:07:52,810 --> 00:07:55,910
E os nós de un trie pode residir
en calquera lugar que heap.

152
00:07:55,910 --> 00:07:58,390
Pero estes son os trade-offs
que debemos considerar.

153
00:07:58,390 --> 00:08:01,440
>> Lembre que, ao elixir un data
estrutura para unha determinada tarefa, nós

154
00:08:01,440 --> 00:08:04,420
que pensar en que tipo de
operacións a estrutura de datos ten

155
00:08:04,420 --> 00:08:07,140
soporte e en canto ao rendemento
de cada un destes

156
00:08:07,140 --> 00:08:09,080
asuntos operacións para nós.

157
00:08:09,080 --> 00:08:11,300
Estas operacións poden ata
van máis alá de simples

158
00:08:11,300 --> 00:08:13,430
Mire cara arriba e inserción básico.

159
00:08:13,430 --> 00:08:17,010
Supoña que quería implantar unha especie
de función de auto-completar, moi

160
00:08:17,010 --> 00:08:18,890
como buscador Google fai.

161
00:08:18,890 --> 00:08:22,210
É dicir, voltar todas as claves e
valores que potencialmente

162
00:08:22,210 --> 00:08:24,130
ter un determinado prefixo.

163
00:08:24,130 --> 00:08:27,050
>> Unha trie é exclusivamente útil
para esta operación.

164
00:08:27,050 --> 00:08:29,890
É sinxelo para percorrer
o trie para cada personaxe de

165
00:08:29,890 --> 00:08:30,950
prefixo.

166
00:08:30,950 --> 00:08:33,559
Así como un ollar para a operación,
poderiamos seguir punteiros

167
00:08:33,559 --> 00:08:35,400
carácter por carácter.

168
00:08:35,400 --> 00:08:38,659
A continuación, cando chegar ao final do
prefixo, poderiamos percorrer a

169
00:08:38,659 --> 00:08:42,049
parte restante da estrutura de datos
sempre que calquera das teclas aló

170
00:08:42,049 --> 00:08:43,980
Neste punto temos o prefixo.

171
00:08:43,980 --> 00:08:47,670
>> É tamén fácil de obter este anuncio
en orde alfabética desde o

172
00:08:47,670 --> 00:08:50,970
elementos da matriz nenos
ordenar por orde alfabética.

173
00:08:50,970 --> 00:08:54,420
Polo tanto, esperamos que vai considerar
doazón intenta un intento.

174
00:08:54,420 --> 00:08:56,085
Eu son Kevin Schmid, e este é CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ah, iso é o comezo
do descenso.

177
00:09:00,790 --> 00:09:01,350
Sinto moito.

178
00:09:01,350 --> 00:09:01,870
Sentímolo.

179
00:09:01,870 --> 00:09:02,480
Sentímolo.

180
00:09:02,480 --> 00:09:03,130
Sentímolo.

181
00:09:03,130 --> 00:09:03,950
>> Folga de catro.

182
00:09:03,950 --> 00:09:04,360
Eu estou fóra.

183
00:09:04,360 --> 00:09:05,280
Sentímolo.

184
00:09:05,280 --> 00:09:06,500
Sentímolo.

185
00:09:06,500 --> 00:09:07,490
Sentímolo.

186
00:09:07,490 --> 00:09:12,352
Desculpem-me por facer a persoa que
ten para editar este tolear.

187
00:09:12,352 --> 00:09:13,280
>> Sentímolo.

188
00:09:13,280 --> 00:09:13,880
Sentímolo.

189
00:09:13,880 --> 00:09:15,080
Sentímolo.

190
00:09:15,080 --> 00:09:15,680
Sentímolo.

191
00:09:15,680 --> 00:09:16,280
>> COLUMNA 1: Ben feito.

192
00:09:16,280 --> 00:09:17,530
Iso foi moi ben feito.

193
00:09:17,530 --> 00:09:18,430