1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[Música tocando]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID MALAN: Este é CS50.

5
00:00:14,010 --> 00:00:18,090
E isto é tanto o início eo
end-- como literally-- quase o final

6
00:00:18,090 --> 00:00:18,825
de seis semanas.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> Eu pensei que eu iria partilhar um
pouco de um fato divertido.

9
00:00:22,640 --> 00:00:25,370
Eu puxei isso a partir de um
dados do semestre passado definido.

10
00:00:25,370 --> 00:00:29,710
Você deve se lembrar que pedimos que em cada
forma conjunto p se você assistiu on-line

11
00:00:29,710 --> 00:00:31,580
ou se você já assistiu em pessoa.

12
00:00:31,580 --> 00:00:33,020
E aqui são os dados.

13
00:00:33,020 --> 00:00:34,710
Então, hoje foi muito previsível.

14
00:00:34,710 --> 00:00:37,126
Mas queríamos passar um pouco
de tempo com você, no entanto.

15
00:00:37,126 --> 00:00:40,599
Alguém gostaria de conjecturar por que isso
gráfico é tão irregular, até para baixo, para cima para baixo,

16
00:00:40,599 --> 00:00:41,265
de forma consistente?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
O que cada um dos picos
e depressões representam?

19
00:00:45,130 --> 00:00:46,005
>> AUDIÊNCIA: [inaudível]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID MALAN: De fato.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
E mais divertidamente, Deus me livre,
temos uma palestra na sexta-feira

24
00:00:55,480 --> 00:00:58,960
no início do semestre,
isso é o que vemos acontecer.

25
00:00:58,960 --> 00:01:03,430
Então, hoje, nós participamos de um pouco
mais sobre estruturas de dados.

26
00:01:03,430 --> 00:01:06,660
E, para dar-lhe mais de um sólido
modelo mental para problemas em cinco,

27
00:01:06,660 --> 00:01:07,450
que agora está fora.

28
00:01:07,450 --> 00:01:10,817
Erros de ortografia, no qual, nós vamos
entregar-lhe um arquivo de texto alguns 100.000

29
00:01:10,817 --> 00:01:12,650
mais palavras em inglês, e
você vai ter

30
00:01:12,650 --> 00:01:17,770
para descobrir como para carregá-los de forma inteligente
em memória, na memória RAM, utilizando-se alguns dados

31
00:01:17,770 --> 00:01:19,330
estrutura de sua escolha.

32
00:01:19,330 --> 00:01:22,470
>> Agora, uma tal estrutura de dados poderia
ser, mas provavelmente não deve ser,

33
00:01:22,470 --> 00:01:25,630
a lista ligada bastante simplista,
que introduzimos última vez.

34
00:01:25,630 --> 00:01:29,220
E uma lista ligada tinham pelo menos
uma vantagem sobre uma matriz.

35
00:01:29,220 --> 00:01:32,096
O que é uma vantagem de
uma lista ligada, sem dúvida?

36
00:01:32,096 --> 00:01:32,950
>> AUDIÊNCIA: Inclusão.

37
00:01:32,950 --> 00:01:33,908
>> DAVID MALAN: Inclusão.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
O que você quer dizer com isso?

40
00:01:35,196 --> 00:01:37,872
>> AUDIÊNCIA: Em qualquer lugar ao longo
lista [inaudível].

41
00:01:37,872 --> 00:01:38,770
>> DAVID MALAN: Good.

42
00:01:38,770 --> 00:01:42,090
Assim, você pode inserir um elemento sempre
você quer no meio da lista

43
00:01:42,090 --> 00:01:45,490
sem ter que embaralhar qualquer coisa,
que concluiu, em nossa classificação

44
00:01:45,490 --> 00:01:47,630
discussões, não é
necessariamente uma coisa boa,

45
00:01:47,630 --> 00:01:51,200
porque leva tempo para realmente se mover
todos os seres humanos para a esquerda ou para a direita.

46
00:01:51,200 --> 00:01:55,540
E assim, com uma lista ligada, você pode
apenas alocar com malloc, um novo nó,

47
00:01:55,540 --> 00:01:58,385
e, em seguida, atualizar um par de
pointers-- dois, três operações max--

48
00:01:58,385 --> 00:02:01,480
e nós somos capazes de encaixar alguém
em qualquer lugar em uma lista.

49
00:02:01,480 --> 00:02:03,550
>> O que mais foi vantajoso
cerca de uma lista ligada?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
Sim?

52
00:02:05,659 --> 00:02:06,534
>> AUDIÊNCIA: [inaudível]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID MALAN: Perfeito.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
Perfeito.

57
00:02:11,090 --> 00:02:12,070
É muito dinâmico.

58
00:02:12,070 --> 00:02:15,100
E que você não está cometendo,
antecipadamente, até certo tamanho fixo

59
00:02:15,100 --> 00:02:18,750
pedaço de memória, como você teria
para com uma matriz, o cabeça de que

60
00:02:18,750 --> 00:02:22,455
é que você pode alocar os nós apenas em
demanda utilizando assim apenas a quantidade de espaço

61
00:02:22,455 --> 00:02:23,330
como você realmente precisa.

62
00:02:23,330 --> 00:02:26,830
Em contraste com um array, você pode
acidentalmente alocar muito pouco.

63
00:02:26,830 --> 00:02:28,871
E depois é só ir
ser uma dor no pescoço

64
00:02:28,871 --> 00:02:32,440
para realocar uma nova matriz maior, copiar
tudo mais, liberar a matriz velha,

65
00:02:32,440 --> 00:02:33,990
e depois passar sobre o seu negócio.

66
00:02:33,990 --> 00:02:37,479
Ou pior, você pode alocar forma
mais memória do que você realmente precisa,

67
00:02:37,479 --> 00:02:40,520
e assim você vai ter uma muito
matriz escassamente povoada, por assim dizer.

68
00:02:40,520 --> 00:02:44,350
>> Assim, uma lista ligada dá-lhe estas
vantagens de dinamismo e flexibilidade

69
00:02:44,350 --> 00:02:46,080
com inserções e deleções.

70
00:02:46,080 --> 00:02:48,000
Mas certamente deve haver um preço a pagar.

71
00:02:48,000 --> 00:02:50,000
De fato, um dos temas
explorada no questionário de zero

72
00:02:50,000 --> 00:02:52,430
era um par de os trade-offs
temos visto até agora.

73
00:02:52,430 --> 00:02:56,161
Então, o que é um preço pago ou a
desvantagem de uma lista ligada?

74
00:02:56,161 --> 00:02:56,660
Sim.

75
00:02:56,660 --> 00:02:57,560
>> AUDIÊNCIA: Sem acesso aleatório.

76
00:02:57,560 --> 00:02:58,809
>> DAVID MALAN: Sem acesso aleatório.

77
00:02:58,809 --> 00:02:59,540
Mas quem se importa?

78
00:02:59,540 --> 00:03:01,546
De acesso aleatório não soa convincente.

79
00:03:01,546 --> 00:03:02,421
>> AUDIÊNCIA: [inaudível]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID MALAN: Exatamente.

82
00:03:05,740 --> 00:03:07,580
Se você quer ter
um certo algorithm--

83
00:03:07,580 --> 00:03:10,170
e deixe-me realmente propor
pesquisa binária, em particular, que

84
00:03:10,170 --> 00:03:12,600
é um que usei muito bit--
se você não tem acesso aleatório,

85
00:03:12,600 --> 00:03:15,516
você não pode fazer isso aritmética simples
de como encontrar o elemento do meio

86
00:03:15,516 --> 00:03:16,530
e pulando direito a ela.

87
00:03:16,530 --> 00:03:20,239
Você não tem que começar na primeira
elemento e linearmente busca de esquerda

88
00:03:20,239 --> 00:03:22,780
para a direita, se você quer encontrar
a média ou de qualquer outro elemento.

89
00:03:22,780 --> 00:03:24,410
>> AUDIÊNCIA: Provavelmente ocupa mais memória.

90
00:03:24,410 --> 00:03:25,040
>> DAVID MALAN: ocupa mais memória.

91
00:03:25,040 --> 00:03:27,464
Onde é que adicional
custar vindo de na memória?

92
00:03:27,464 --> 00:03:28,339
>> AUDIÊNCIA: [inaudível]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID MALAN: Exatamente.

95
00:03:33,440 --> 00:03:35,679
Neste caso aqui, tivemos
uma lista encadeada de números inteiros,

96
00:03:35,679 --> 00:03:37,470
e ainda estamos dobrando
a quantidade de memória

97
00:03:37,470 --> 00:03:39,680
precisamos também por armazenar esses ponteiros.

98
00:03:39,680 --> 00:03:42,090
Agora menos de um grande negócio como
suas estruturas ficam maiores

99
00:03:42,090 --> 00:03:45,320
e você está armazenando não um número, mas
talvez um estudante ou algum outro objeto.

100
00:03:45,320 --> 00:03:46,880
Mas o ponto certamente permanece.

101
00:03:46,880 --> 00:03:49,421
E assim um certo número de operações
em listas ligadas foram chamados

102
00:03:49,421 --> 00:03:50,570
eram grandes O linear de n--.

103
00:03:50,570 --> 00:03:54,730
Coisas como inserção ou busca
ou exclusão no caso de um elemento

104
00:03:54,730 --> 00:03:57,720
Aconteceu no final da
a lista se ele está classificado ou não.

105
00:03:57,720 --> 00:04:01,167
>> Às vezes você pode ter sorte e em
limites tão baixos sobre estas operações

106
00:04:01,167 --> 00:04:04,250
pode também ser de tempo constante, se você estiver
sempre olhando para o primeiro elemento,

107
00:04:04,250 --> 00:04:05,070
por exemplo.

108
00:04:05,070 --> 00:04:09,360
Mas, afinal, que prometeu
para alcançar o Santo Graal

109
00:04:09,360 --> 00:04:12,630
de estruturas de dados, ou
alguns destes aproximação,

110
00:04:12,630 --> 00:04:14,290
por meio de constante de tempo.

111
00:04:14,290 --> 00:04:17,579
Podemos encontrar elementos ou adicionar elementos
ou remover elementos de uma lista?

112
00:04:17,579 --> 00:04:19,059
Veremos em breve.

113
00:04:19,059 --> 00:04:21,100
E verifica-se que um
dos mecanismos que estamos

114
00:04:21,100 --> 00:04:23,464
vai começar a usar hoje,
utilização anual em p definir cinco,

115
00:04:23,464 --> 00:04:24,630
é realmente muito familiar.

116
00:04:24,630 --> 00:04:27,430
Por exemplo, se este é um grupo
livros de exame, cada um dos quais

117
00:04:27,430 --> 00:04:29,660
tem um aluno de primeira
nome e último nome,

118
00:04:29,660 --> 00:04:31,820
e eu buscá-las a partir de
no final de um exame,

119
00:04:31,820 --> 00:04:33,746
e todos eles são bastante
muito em uma ordem aleatória,

120
00:04:33,746 --> 00:04:36,370
e queremos ir sobre a classificação
esses exames, de modo que, uma vez classificado

121
00:04:36,370 --> 00:04:38,661
é apenas muito mais fácil e
mais rápido para entregá-los de volta para fora

122
00:04:38,661 --> 00:04:40,030
para os alunos em ordem alfabética.

123
00:04:40,030 --> 00:04:42,770
O que seus instintos ser
para uma pilha de exames como este?

124
00:04:42,770 --> 00:04:45,019
>> Bem, se você é como eu, você
pode ver que isso é m,

125
00:04:45,019 --> 00:04:48,505
então eu vou espécie de colocar isso em,
se esta é a minha mesa ou o meu andar, onde

126
00:04:48,505 --> 00:04:50,650
Estou espalhando coisas
out-- ou minha matriz realmente--

127
00:04:50,650 --> 00:04:52,210
Eu poderia colocar todo o Ms lá dentro.

128
00:04:52,210 --> 00:04:52,710
Oh.

129
00:04:52,710 --> 00:04:55,020
Aqui está um A. Então eu poderia
Como colocar os aqui.

130
00:04:55,020 --> 00:04:55,520
Oh.

131
00:04:55,520 --> 00:04:57,980
Aqui está outro A. Vou
colocar isso aqui.

132
00:04:57,980 --> 00:05:02,490
Aqui está um Z. Aqui está outro M. E assim
Eu poderia começar a fazer pilhas como esta.

133
00:05:02,490 --> 00:05:06,620
E então talvez eu iria mais tarde
e tipo de muito detalhista-ly tipo

134
00:05:06,620 --> 00:05:07,710
as pilhas individuais.

135
00:05:07,710 --> 00:05:11,300
Mas o ponto é que eu ficaria
na entrada que eu sou destro

136
00:05:11,300 --> 00:05:14,016
e eu gostaria de fazer algum calculado
decisão com base nessa entrada.

137
00:05:14,016 --> 00:05:15,640
Se ele começa com A, colocá-lo lá.

138
00:05:15,640 --> 00:05:18,980
Se ele começa com Z, colocá-lo sobre
lá, e tudo mais.

139
00:05:18,980 --> 00:05:22,730
>> Portanto, esta é uma técnica que é
geralmente conhecido como hashing-- H-A-S-h--

140
00:05:22,730 --> 00:05:26,550
o que geralmente significa tomar como
de entrada e usando que a entrada para calcular

141
00:05:26,550 --> 00:05:30,940
um valor, geralmente, um número, e que
número é o índice para um dispositivo de armazenamento

142
00:05:30,940 --> 00:05:32,260
recipiente, como uma matriz.

143
00:05:32,260 --> 00:05:35,490
Portanto, em outras palavras, eu poderia ter um
função de hash, como eu faço na minha cabeça,

144
00:05:35,490 --> 00:05:37,940
que, se eu vejo alguém é
nome que começa com A,

145
00:05:37,940 --> 00:05:40,190
Eu estou indo para mapear que
a zero na minha cabeça.

146
00:05:40,190 --> 00:05:44,160
E se eu vejo alguém com Z, eu sou
vai mapear que a 25 na minha cabeça

147
00:05:44,160 --> 00:05:46,220
e, em seguida, colocar isso em
o último mais pilha.

148
00:05:46,220 --> 00:05:50,990
>> Agora, se você pensar em não meu cérebro
Mas um programa C, o que os números poderiam

149
00:05:50,990 --> 00:05:53,170
você confiar para atingir esse mesmo resultado?

150
00:05:53,170 --> 00:05:55,594
Em outras palavras, se você
tinha o caráter ASCII A,

151
00:05:55,594 --> 00:05:57,510
como é possível determinar
o balde para colocá-lo?

152
00:05:57,510 --> 00:05:59,801
Você provavelmente não quer
colocá-lo em balde de 65 anos, que

153
00:05:59,801 --> 00:06:01,840
Seria como lá
sem uma boa razão.

154
00:06:01,840 --> 00:06:04,320
Onde você quer colocar um
em termos de seu valor ASCII?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
Onde você quer fazer para o seu ASCII
valor para chegar a um balde de forma mais inteligente

157
00:06:08,920 --> 00:06:09,480
para colocá-lo em?

158
00:06:09,480 --> 00:06:10,206
>> AUDIÊNCIA: Minus A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID MALAN: Yeah.

160
00:06:10,956 --> 00:06:13,190
Assim, menos um ou menos
especificamente 65 se é

161
00:06:13,190 --> 00:06:18,240
um capital A. Ou 98 se
é uma minúscula a.

162
00:06:18,240 --> 00:06:21,300
E assim que nos permitem, muito
de forma simples e muito aritmeticamente,

163
00:06:21,300 --> 00:06:23,260
colocar algo em um balde assim.

164
00:06:23,260 --> 00:06:26,010
Então não é que realmente fazemos
este bem mesmo com os quizzes.

165
00:06:26,010 --> 00:06:29,051
>> Assim, você pode se lembrar você circulou seu
Nome ensino companheiro na capa.

166
00:06:29,051 --> 00:06:32,270
E os nomes do TF foram organizadas
estas colunas em ordem alfabética,

167
00:06:32,270 --> 00:06:34,400
Bem, acredite ou não,
quando todos 80 mais de nós

168
00:06:34,400 --> 00:06:37,800
se reuniram na outra noite para grau,
o último passo no nosso processo de classificação

169
00:06:37,800 --> 00:06:41,830
é para picar os questionários em uma grande
espaço de chão no [inaudível]

170
00:06:41,830 --> 00:06:45,110
e estabelecer quizzes de todos para fora
exatamente na ordem de seus TF de

171
00:06:45,110 --> 00:06:47,700
nomes na capa, pois
então é muito mais fácil para nós

172
00:06:47,700 --> 00:06:51,290
a busca através de que o uso linear
procurar ou algum tipo de inteligência

173
00:06:51,290 --> 00:06:54,050
para um TF para encontrar o seu ou
quizzes dos seus alunos.

174
00:06:54,050 --> 00:06:56,060
>> Então, essa idéia de hashing
que você verá é

175
00:06:56,060 --> 00:07:00,520
bastante poderoso é realmente muito
banal e muito intuitiva,

176
00:07:00,520 --> 00:07:03,000
muito parecido, talvez, e dividir
conquista foi na semana zero.

177
00:07:03,000 --> 00:07:05,250
Eu avanço rápido para a hackathon
um par de anos atrás.

178
00:07:05,250 --> 00:07:08,040
Este foi Zamyla e um par de
outros alunos saudação pessoal

179
00:07:08,040 --> 00:07:09,030
como eles entraram.

180
00:07:09,030 --> 00:07:12,680
E nós tivemos um monte de dobradura
mesas lá com etiquetas de nome.

181
00:07:12,680 --> 00:07:15,380
E nós tínhamos as etiquetas de nome organizado
com como os Como por lá

182
00:07:15,380 --> 00:07:16,690
eo Zs lá.

183
00:07:16,690 --> 00:07:20,350
E assim um dos TFs muito inteligente
escreveu isso como as instruções

184
00:07:20,350 --> 00:07:21,030
para o dia.

185
00:07:21,030 --> 00:07:24,480
E na semana 12 do semestre este
tudo fez sentido perfeito e todos

186
00:07:24,480 --> 00:07:25,310
sabia o que fazer.

187
00:07:25,310 --> 00:07:27,900
Mas sempre que tenho
enfileirados na mesma maneira,

188
00:07:27,900 --> 00:07:30,272
você está implementando o
mesma noção de um hash.

189
00:07:30,272 --> 00:07:31,730
Então, vamos formalizar-lo um pouco.

190
00:07:31,730 --> 00:07:32,890
Aqui é uma matriz.

191
00:07:32,890 --> 00:07:36,820
Ele é desenhado para ser um pouco
grande apenas para descrever, visualmente,

192
00:07:36,820 --> 00:07:38,920
para que possamos colocar cordas
em algo como isto.

193
00:07:38,920 --> 00:07:41,970
E essa matriz é
claramente de tamanho 26 total.

194
00:07:41,970 --> 00:07:43,935
E a coisa é chamado
mesa de forma arbitrária.

195
00:07:43,935 --> 00:07:48,930
Mas esta é apenas capitulação de um artista
do que uma tabela hash pode ser.

196
00:07:48,930 --> 00:07:52,799
>> Assim, uma tabela hash agora vai
ser uma estrutura de dados de nível superior.

197
00:07:52,799 --> 00:07:54,840
No final do dia
estamos prestes a ver que você

198
00:07:54,840 --> 00:07:58,700
pode implementar uma tabela hash, que
é muito parecido com a linha de check-in

199
00:07:58,700 --> 00:08:02,059
a uma hackathon muito parecido com este
tabela usada para classificar os livros de exame.

200
00:08:02,059 --> 00:08:03,850
Mas uma tabela hash é
espécie de presente de alto nível

201
00:08:03,850 --> 00:08:08,250
conceito que poderia usar uma matriz
debaixo do capô para implementá-lo,

202
00:08:08,250 --> 00:08:11,890
ou pode usar uma lista de comprimento, ou mesmo
talvez algumas outras estruturas de dados.

203
00:08:11,890 --> 00:08:15,590
E agora que é a tomada theme--
alguns destes ingredientes fundamentais

204
00:08:15,590 --> 00:08:18,310
como um array e este edifício
bloquear agora de uma lista de comprimento

205
00:08:18,310 --> 00:08:21,740
e ver o que mais podemos construir
em cima de quem, como ingredientes

206
00:08:21,740 --> 00:08:26,550
em uma receita, tornando cada vez mais
resultados finais interessantes e úteis.

207
00:08:26,550 --> 00:08:28,680
>> Assim, com a tabela hash
podemos implementá-lo

208
00:08:28,680 --> 00:08:32,540
na memória pictoricamente como este, mas
como pode ele realmente ser codificado em cima?

209
00:08:32,540 --> 00:08:33,789
Bem, talvez simplesmente como é isso.

210
00:08:33,789 --> 00:08:38,270
Se a capacidade em todas as tampas, é apenas
alguns constant-- por exemplo 26,

211
00:08:38,270 --> 00:08:42,030
para 26 letras do alphabet--
Eu poderia chamar de minha mesa variável,

212
00:08:42,030 --> 00:08:45,630
e eu poderia afirmar que eu vou
colocar estrelas de char lá, ou string.

213
00:08:45,630 --> 00:08:49,880
Por isso, é tão simples como isso se você
deseja implementar uma tabela hash.

214
00:08:49,880 --> 00:08:51,490
E, no entanto, isso é realmente apenas uma matriz.

215
00:08:51,490 --> 00:08:53,198
Mas, novamente, um hash
tabela é agora o que vamos

216
00:08:53,198 --> 00:08:57,470
chamar um tipo abstrato de dados que é apenas
uma espécie de estratificação conceitual no topo

217
00:08:57,470 --> 00:09:00,780
de algo mais mundano
agora como um array.

218
00:09:00,780 --> 00:09:02,960
>> Agora, como é que nós vamos
sobre a resolução de problemas?

219
00:09:02,960 --> 00:09:06,980
Bem, no início eu tive o luxo
de ter espaço suficiente mesa aqui

220
00:09:06,980 --> 00:09:09,460
para que eu pudesse colocar o
quizzes em qualquer lugar que eu queria.

221
00:09:09,460 --> 00:09:10,620
Então, como pode ir aqui.

222
00:09:10,620 --> 00:09:12,100
Zs pode ir aqui.

223
00:09:12,100 --> 00:09:13,230
Ms pode ir aqui.

224
00:09:13,230 --> 00:09:14,740
E então eu tive um pouco de espaço extra.

225
00:09:14,740 --> 00:09:18,740
Mas isso é um pouco de um direito de fraude
agora, porque esta tabela, se eu realmente

226
00:09:18,740 --> 00:09:22,720
pensei nisso como uma matriz, é apenas
vai ser de cerca de tamanho fixo.

227
00:09:22,720 --> 00:09:25,380
>> Então, tecnicamente, se eu puxar
se questionário de outro aluno

228
00:09:25,380 --> 00:09:28,490
e ver, oh, esta pessoa de
nome começa com um A também,

229
00:09:28,490 --> 00:09:30,980
Eu meio que quero colocá-lo lá.

230
00:09:30,980 --> 00:09:34,740
Mas assim que eu colocá-lo lá, se
esta tabela de facto representa uma matriz,

231
00:09:34,740 --> 00:09:37,840
Eu vou estar substituindo ou sobrepor
quem questionário deste aluno é.

232
00:09:37,840 --> 00:09:38,340
Certo?

233
00:09:38,340 --> 00:09:41,972
Se este é um array, só uma coisa pode
ir em cada uma destas células ou elementos.

234
00:09:41,972 --> 00:09:43,680
E então eu meio que tenho
de escolher.

235
00:09:43,680 --> 00:09:45,735
>> Agora antes que eu tipo de
enganado e fez isso ou eu

236
00:09:45,735 --> 00:09:47,526
apenas uma espécie de empilhados
-los por cima da outra.

237
00:09:47,526 --> 00:09:49,170
Mas isso não vai voar no código.

238
00:09:49,170 --> 00:09:52,260
Então, onde eu poderia colocar o
segundo aluno cujo nome

239
00:09:52,260 --> 00:09:54,964
é A, se tudo o que eu tinha é este
disponível espaço de tabela?

240
00:09:54,964 --> 00:09:57,880
E eu usei três slots e que
Parece que há apenas alguns outros.

241
00:09:57,880 --> 00:09:58,959
O que você poderia fazer?

242
00:09:58,959 --> 00:09:59,834
AUDIÊNCIA: [inaudível]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID MALAN: Yeah.

245
00:10:01,315 --> 00:10:02,370
Talvez vamos mantê-lo simples.

246
00:10:02,370 --> 00:10:02,660
Certo?

247
00:10:02,660 --> 00:10:04,243
Ela não se encaixa onde eu quero colocá-lo.

248
00:10:04,243 --> 00:10:07,450
Então, eu vou colocá-lo
tecnicamente, onde um B iria.

249
00:10:07,450 --> 00:10:09,932
Agora, é claro, eu estou começando
a pintar-me em um canto.

250
00:10:09,932 --> 00:10:11,890
Se eu chegar a um estudante
cujo nome é, na verdade, B,

251
00:10:11,890 --> 00:10:14,840
agora B vai ser movido um pouco
para a frente, como pode acontecer, sim,

252
00:10:14,840 --> 00:10:17,530
se este é um B, agora ele tem que ir aqui.

253
00:10:17,530 --> 00:10:20,180
>> E por isso esta muito rapidamente
poderia tornar-se problemático,

254
00:10:20,180 --> 00:10:23,850
mas é uma técnica que, na verdade,
é referido como linear de sondagem,

255
00:10:23,850 --> 00:10:26,650
em que você considerar apenas o seu
matriz de ser ao longo da linha.

256
00:10:26,650 --> 00:10:29,680
E você só tipo de sonda ou
inspecionar cada elemento disponível

257
00:10:29,680 --> 00:10:31,360
à procura de um local disponível.

258
00:10:31,360 --> 00:10:34,010
E assim que você encontrar
um, você largá-lo lá dentro.

259
00:10:34,010 --> 00:10:38,390
>> Agora, o preço a ser pago agora
para esta solução é o quê?

260
00:10:38,390 --> 00:10:41,300
Nós temos uma matriz de tamanho fixo,
e quando eu inserir nomes

261
00:10:41,300 --> 00:10:44,059
para ele, pelo menos inicialmente, o que é
o tempo de execução de inserção

262
00:10:44,059 --> 00:10:46,350
para colocar os alunos
quizzes nos baldes certo?

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
Big O de quê?

265
00:10:50,002 --> 00:10:51,147
>> AUDIÊNCIA: n.

266
00:10:51,147 --> 00:10:52,480
DAVID MALAN: Eu ouvi grande O de n.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
Não é verdade.

269
00:10:54,300 --> 00:10:56,490
Mas nós vamos provocar uma separação
por que em apenas um momento.

270
00:10:56,490 --> 00:10:57,702
O que mais poderia ser?

271
00:10:57,702 --> 00:10:58,755
>> AUDIÊNCIA: [inaudível]

272
00:10:58,755 --> 00:11:00,380
DAVID MALAN: E deixe-me fazê-lo visualmente.

273
00:11:00,380 --> 00:11:04,720
Então, suponhamos que esta é a letra S.

274
00:11:04,720 --> 00:11:05,604
>> AUDIÊNCIA: É uma.

275
00:11:05,604 --> 00:11:06,520
DAVID MALAN: É uma.

276
00:11:06,520 --> 00:11:06,710
Certo?

277
00:11:06,710 --> 00:11:08,950
Esta é uma matriz, que
significa que temos acesso aleatório.

278
00:11:08,950 --> 00:11:11,790
E se pensarmos dessa
como zero e isso como 25,

279
00:11:11,790 --> 00:11:13,800
e percebemos que,
oh, aqui está a minha entrada S,

280
00:11:13,800 --> 00:11:16,350
Eu certamente posso converter
S, um caractere ASCII,

281
00:11:16,350 --> 00:11:18,540
a um número correspondente
entre zero e 25

282
00:11:18,540 --> 00:11:20,910
e, em seguida, imediatamente
colocá-lo onde ele pertence.

283
00:11:20,910 --> 00:11:26,120
>> Mas, claro, assim que eu chegar ao
segunda pessoa cujo nome é A ou B ou C

284
00:11:26,120 --> 00:11:29,300
eventualmente, se eu usei o
linear sondagem como a minha solução,

285
00:11:29,300 --> 00:11:31,360
o tempo de execução
inserção no pior caso

286
00:11:31,360 --> 00:11:33,120
é realmente vai transformar-se em quê?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
E eu ouvi-lo aqui
corretamente desde o início.

289
00:11:36,045 --> 00:11:36,920
AUDIÊNCIA: [inaudível]

290
00:11:36,920 --> 00:11:41,620
DAVID MALAN: Assim é, de facto, uma vez n
você tem uma suficientemente grande conjunto de dados.

291
00:11:41,620 --> 00:11:44,410
Assim, por um lado, se
a matriz é grande o suficiente

292
00:11:44,410 --> 00:11:48,287
e seus dados é escassa o suficiente, você
obter este tempo constante bonito.

293
00:11:48,287 --> 00:11:50,620
Mas assim que você começar a
ficando mais e mais elementos,

294
00:11:50,620 --> 00:11:53,200
e apenas estatisticamente que você começa
mais pessoas com a letra

295
00:11:53,200 --> 00:11:56,030
Uma como o seu nome ou a letra
B, que poderia potencialmente

296
00:11:56,030 --> 00:11:57,900
transformar-se em algo mais linear.

297
00:11:57,900 --> 00:11:59,640
Então, não é absolutamente perfeito.

298
00:11:59,640 --> 00:12:00,690
Então, poderíamos fazer melhor?

299
00:12:00,690 --> 00:12:03,210
>> Bem, o que foi o nosso
solução antes quando nós

300
00:12:03,210 --> 00:12:06,820
quer ter mais dinamismo do que
algo como uma matriz permitido?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
AUDIÊNCIA: [inaudível]

303
00:12:08,960 --> 00:12:10,030
DAVID MALAN: O que nós apresentamos?

304
00:12:10,030 --> 00:12:10,530
Sim.

305
00:12:10,530 --> 00:12:11,430
Assim, uma lista ligada.

306
00:12:11,430 --> 00:12:14,430
Bem, vamos ver o que um ligado
lista pode fazer por nós em seu lugar.

307
00:12:14,430 --> 00:12:17,630
Bem, deixe-me propor que
desenhar a imagem da seguinte forma.

308
00:12:17,630 --> 00:12:19,620
Agora este é um diferente
imagem de um exemplo

309
00:12:19,620 --> 00:12:24,750
a partir de um texto diferente, na verdade, que
é, na verdade, usando uma matriz de tamanho 31.

310
00:12:24,750 --> 00:12:28,220
E este autor simplesmente
decidiu botar cordas

311
00:12:28,220 --> 00:12:32,430
não com base em nomes da pessoa,
mas com base em suas datas de nascimento.

312
00:12:32,430 --> 00:12:35,680
Independentemente do mês, figuraram
se você nasceu no primeiro dia de um mês

313
00:12:35,680 --> 00:12:39,580
ou o dia 31 de um mês, o autor
vai botar com base nesse valor,

314
00:12:39,580 --> 00:12:44,154
de forma a disseminar os nomes um pouco
mais do que apenas 26 pontos pode permitir.

315
00:12:44,154 --> 00:12:47,320
E talvez seja um pouco mais uniforme
do que ir com as letras do alfabeto,

316
00:12:47,320 --> 00:12:50,236
porque é claro que há, provavelmente,
mais pessoas no mundo com nomes

317
00:12:50,236 --> 00:12:54,020
que começar com uma que certamente
algumas outras letras do alfabeto.

318
00:12:54,020 --> 00:12:56,380
Então talvez isso seja um pouco
mais uniforme, assumindo

319
00:12:56,380 --> 00:12:58,640
uma distribuição uniforme
de bebés através de um mês.

320
00:12:58,640 --> 00:12:59,990
>> Mas, claro, isso ainda é imperfeito.

321
00:12:59,990 --> 00:13:00,370
Certo?

322
00:13:00,370 --> 00:13:01,370
Nós estamos tendo colisões.

323
00:13:01,370 --> 00:13:04,680
Várias pessoas nesta
estrutura de dados ainda são

324
00:13:04,680 --> 00:13:08,432
tendo a mesma data de nascimento, pelo menos
você independentemente do mês.

325
00:13:08,432 --> 00:13:09,640
Mas o que o autor fez?

326
00:13:09,640 --> 00:13:13,427
Bem, parece que temos um array
no lado da mão esquerda tirada verticalmente,

327
00:13:13,427 --> 00:13:15,010
mas isso é apenas interpretação de um artista.

328
00:13:15,010 --> 00:13:18,009
Não importa que direção você
desenhar uma matriz, que ainda é um array.

329
00:13:18,009 --> 00:13:20,225
O que é isso uma série de aparentemente?

330
00:13:20,225 --> 00:13:21,500
>> AUDIÊNCIA: lista encadeada.

331
00:13:21,500 --> 00:13:21,650
>> DAVID MALAN: Yeah.

332
00:13:21,650 --> 00:13:23,490
Parece que é uma
matriz de lista ligada.

333
00:13:23,490 --> 00:13:26,490
Então, novamente, a este ponto de tipo
de usar essas estruturas de dados agora

334
00:13:26,490 --> 00:13:28,550
como ingredientes a mais
soluções interessantes,

335
00:13:28,550 --> 00:13:30,862
você pode perfeitamente ter um
fundamentais, como uma matriz,

336
00:13:30,862 --> 00:13:33,320
e em seguida, tomar algo mais
interessante como uma lista ligada

337
00:13:33,320 --> 00:13:36,660
e até mesmo combiná-los em um mesmo
estrutura de dados mais interessante.

338
00:13:36,660 --> 00:13:39,630
E, de fato, isso também seria
ser chamado de uma tabela hash,

339
00:13:39,630 --> 00:13:42,610
pelo que a matriz é
realmente a tabela hash,

340
00:13:42,610 --> 00:13:45,600
mas que tem tabela hash
correntes, por assim dizer,

341
00:13:45,600 --> 00:13:50,220
que pode crescer ou psiquiatra com base no
número de elementos que você deseja inserir.

342
00:13:50,220 --> 00:13:52,990
>> Agora, nesse sentido, o que é
o tempo de execução agora?

343
00:13:52,990 --> 00:13:58,030
Se eu quiser inserir alguém
cujo aniversário é 31 de outubro de

344
00:13:58,030 --> 00:13:59,040
onde é que ele ou ela vai?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
Tudo certo.

347
00:14:01,030 --> 00:14:02,819
Na parte inferior, onde ele diz que 31.

348
00:14:02,819 --> 00:14:03,610
E isso é perfeito.

349
00:14:03,610 --> 00:14:05,060
Esse foi o tempo constante.

350
00:14:05,060 --> 00:14:08,760
Mas o que se encontrar alguém
cujo aniversário é, vamos ver,

351
00:14:08,760 --> 00:14:10,950
Outubro, novembro, 31 de dezembro?

352
00:14:10,950 --> 00:14:12,790
Onde é que ele ou ela vai?

353
00:14:12,790 --> 00:14:13,290
Mesma coisa.

354
00:14:13,290 --> 00:14:13,970
Duas etapas embora.

355
00:14:13,970 --> 00:14:15,303
Isso é constante, embora, não é?

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
Tudo certo.

358
00:14:16,860 --> 00:14:17,840
No momento em que ela é.

359
00:14:17,840 --> 00:14:20,570
Mas, no caso geral,
quanto mais as pessoas que agregam,

360
00:14:20,570 --> 00:14:23,790
probabilisticamente, vamos
para obter mais e mais colisões.

361
00:14:23,790 --> 00:14:26,820
>> Agora isso é um pouco
melhor, porque tecnicamente

362
00:14:26,820 --> 00:14:34,580
Agora minhas correntes poderiam estar em
o pior caso quanto tempo?

363
00:14:34,580 --> 00:14:38,890
Se eu inserir n pessoas para este mais
estrutura de dados sofisticado, n pessoas,

364
00:14:38,890 --> 00:14:41,080
na pior das hipóteses ele vai ser n.

365
00:14:41,080 --> 00:14:41,815
Por quê?

366
00:14:41,815 --> 00:14:43,332
>> AUDIÊNCIA: Porque se todo mundo
tem o mesmo aniversário,

367
00:14:43,332 --> 00:14:44,545
eles estão indo para ser uma linha.

368
00:14:44,545 --> 00:14:45,420
DAVID MALAN: Perfeito.

369
00:14:45,420 --> 00:14:47,480
Ele pode ser um pouco artificial,
mas realmente, no pior caso,

370
00:14:47,480 --> 00:14:50,117
se todo mundo tem o mesmo aniversário,
dadas as entradas que você tem,

371
00:14:50,117 --> 00:14:51,950
você vai ter um
maciçamente cadeia longa.

372
00:14:51,950 --> 00:14:54,241
E assim, você poderia chamá-lo de um
Hash Table, mas realmente é

373
00:14:54,241 --> 00:14:56,810
apenas uma enorme lista ligada
um monte de espaço desperdiçado.

374
00:14:56,810 --> 00:15:00,460
Mas, em geral, se assumirmos que
pelo menos, os aniversários são uniform--

375
00:15:00,460 --> 00:15:01,750
e provavelmente não é.

376
00:15:01,750 --> 00:15:02,587
Eu estou fazendo isso.

377
00:15:02,587 --> 00:15:04,420
Mas se assumirmos, por
a causa da discussão

378
00:15:04,420 --> 00:15:07,717
que eles são, então, em teoria, se
esta é a representação verticais

379
00:15:07,717 --> 00:15:11,050
da matriz, bem, então espero que você está
vai ficar cadeias que são, você sabe,

380
00:15:11,050 --> 00:15:15,880
aproximadamente o mesmo comprimento, onde cada um dos
deles representa um dia do mês.

381
00:15:15,880 --> 00:15:19,930
>> Agora, se há 31 dias no mês,
isso significa que o meu tempo de corrida realmente

382
00:15:19,930 --> 00:15:25,230
é grande O de n mais de 31, que
sente melhor do que linear.

383
00:15:25,230 --> 00:15:27,950
Mas o que era um de nossos
compromissos de algumas semanas

384
00:15:27,950 --> 00:15:31,145
há sempre que se tratava de expressar
o tempo de execução de um algoritmo?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
Basta apenas olhar para o termo de ordem superior.

387
00:15:35,190 --> 00:15:35,690
Certo?

388
00:15:35,690 --> 00:15:37,400
31 é definitivamente útil.

389
00:15:37,400 --> 00:15:39,610
Mas isso ainda é grande O de n.

390
00:15:39,610 --> 00:15:41,730
Mas um dos temas
do conjunto de problemas de cinco

391
00:15:41,730 --> 00:15:43,950
vai ser a
reconhecer que absolutamente,

392
00:15:43,950 --> 00:15:47,320
assintoticamente, teoricamente
esta estrutura de dados

393
00:15:47,320 --> 00:15:50,470
não é melhor do que apenas
uma lista ligada maciça.

394
00:15:50,470 --> 00:15:53,550
E, de fato, no pior dos casos, este
tabela hash pode transformar-se em que.

395
00:15:53,550 --> 00:15:57,620
>> Mas no mundo real, com nós seres humanos
que os próprios Macs ou PCs ou o que quer

396
00:15:57,620 --> 00:16:01,240
e estão em execução no mundo real
software em dados do mundo real,

397
00:16:01,240 --> 00:16:03,260
algoritmo que você vai preferir?

398
00:16:03,260 --> 00:16:09,180
Aquele que toma medidas finais ou à
que leva n dividido por 31 passos

399
00:16:09,180 --> 00:16:12,900
para encontrar alguma peça de dados ou
para procurar alguma informação?

400
00:16:12,900 --> 00:16:16,580
Quero dizer, absolutamente as 31 marcas
uma diferença no mundo real.

401
00:16:16,580 --> 00:16:18,540
É 31 vezes mais rápido.

402
00:16:18,540 --> 00:16:20,880
E nós, seres humanos são, certamente,
vai apreciar isso.

403
00:16:20,880 --> 00:16:23,004
>> Assim, perceber a dicotomia
na verdade existe entre

404
00:16:23,004 --> 00:16:25,920
falando sobre coisas teoricamente
e assintoticamente que definitivamente

405
00:16:25,920 --> 00:16:28,760
tem valor como vimos,
mas no mundo real,

406
00:16:28,760 --> 00:16:32,930
se você se preocupa apenas fazendo o
feliz humano para as entradas gerais,

407
00:16:32,930 --> 00:16:36,010
você pode muito bem querer aceitar
o facto de que, sim, isto é linear,

408
00:16:36,010 --> 00:16:38,360
mas é 31 vezes mais rápido
que pode ser linear.

409
00:16:38,360 --> 00:16:41,610
E melhor ainda, nós não apenas temos que
fazer algo arbitrário como a data de nascimento,

410
00:16:41,610 --> 00:16:44,030
poderíamos passar um pouco
mais tempo e inteligência

411
00:16:44,030 --> 00:16:47,140
e pensar sobre o que poderíamos fazer,
dado o nome de uma pessoa e talvez

412
00:16:47,140 --> 00:16:50,130
sua data de nascimento para combinar os
ingredientes para descobrir algo

413
00:16:50,130 --> 00:16:52,720
que é verdadeiramente mais
uniforme e menos irregular,

414
00:16:52,720 --> 00:16:56,250
por assim dizer do que esta imagem
atualmente sugere que poderia ser.

415
00:16:56,250 --> 00:16:57,750
Como podemos implementar isso no código?

416
00:16:57,750 --> 00:17:00,280
Bem, deixe-me propor que
apenas pedir algum sintaxe temos

417
00:17:00,280 --> 00:17:01,799
utilizado um par de vezes até agora.

418
00:17:01,799 --> 00:17:03,590
E eu estou indo para definir
um nó, que novamente

419
00:17:03,590 --> 00:17:06,812
é um termo genérico para apenas alguns
recipiente para alguma estrutura de dados.

420
00:17:06,812 --> 00:17:09,020
Vou propor que
uma seqüência que vai lá dentro.

421
00:17:09,020 --> 00:17:11,369
Mas vamos começar a tomar
aquelas rodinhas fora agora.

422
00:17:11,369 --> 00:17:13,230
>> Não há mais biblioteca CS50
realmente, a menos que você quiser

423
00:17:13,230 --> 00:17:15,230
usá-lo para o seu final,
projeto, que é bom,

424
00:17:15,230 --> 00:17:18,569
mas agora estamos indo para puxar a
cortina e dizer que é apenas uma estrela de char.

425
00:17:18,569 --> 00:17:22,069
Assim, a palavra não vai ser
o nome da pessoa em questão.

426
00:17:22,069 --> 00:17:25,079
E agora eu tenho um link
aqui para o próximo nó

427
00:17:25,079 --> 00:17:28,170
para que estes representam
cada um dos nós

428
00:17:28,170 --> 00:17:30,950
na cadeia, potencialmente,
de uma lista ligada.

429
00:17:30,950 --> 00:17:34,090
>> E agora como faço para declarar
própria tabela de hash?

430
00:17:34,090 --> 00:17:36,660
Como faço para declarar toda esta estrutura?

431
00:17:36,660 --> 00:17:40,960
Bem, realmente, muito parecido com que eu usei um ponteiro
para apenas o primeiro elemento de uma lista

432
00:17:40,960 --> 00:17:44,510
antes, da mesma forma eu posso apenas dizer
Eu só preciso de um monte de ponteiros

433
00:17:44,510 --> 00:17:46,270
para implementar essa tabela hash todo.

434
00:17:46,270 --> 00:17:49,484
Eu vou ter um array
chamada de tabela para a tabela hash.

435
00:17:49,484 --> 00:17:50,900
Vai ser de capacidade tamanho.

436
00:17:50,900 --> 00:17:52,525
É assim que muitos elementos podem caber nele.

437
00:17:52,525 --> 00:17:56,180
E cada um desses elementos neste
matriz vai ser uma estrela nó.

438
00:17:56,180 --> 00:17:56,810
Por quê?

439
00:17:56,810 --> 00:18:00,160
Bem, por esta imagem, o que eu sou
implementar a tabela de hash como

440
00:18:00,160 --> 00:18:04,330
notadamente no início é apenas
essa matriz que temos desenhado na vertical,

441
00:18:04,330 --> 00:18:06,820
cada um de cujos quadrados
representa um ponteiro.

442
00:18:06,820 --> 00:18:09,170
Que aqueles que têm barras
através deles são apenas nulo.

443
00:18:09,170 --> 00:18:11,410
E os que têm
setas que vão para a direita

444
00:18:11,410 --> 00:18:16,140
são ponteiros reais para nós reais,
ergo o início de uma lista ligada.

445
00:18:16,140 --> 00:18:19,050
>> Então, aqui, então, é como podemos
implementar uma tabela hash que

446
00:18:19,050 --> 00:18:21,580
implementa o encadeamento separado.

447
00:18:21,580 --> 00:18:22,840
Agora podemos fazer melhor?

448
00:18:22,840 --> 00:18:25,632
Tudo bem que prometi da última vez que
poderíamos conseguir tempo constante.

449
00:18:25,632 --> 00:18:27,381
E eu meio que lhe deu
constante de tempo aqui,

450
00:18:27,381 --> 00:18:29,850
mas depois não disse realmente
constante de tempo porque ainda é

451
00:18:29,850 --> 00:18:31,890
dependente do total
número de elementos

452
00:18:31,890 --> 00:18:34,500
você está introduzindo em
a estrutura de dados.

453
00:18:34,500 --> 00:18:35,980
Mas suponha que nós fizemos isso.

454
00:18:35,980 --> 00:18:39,550
Deixe-me voltar para a tela aqui.

455
00:18:39,550 --> 00:18:44,520
Permitam-me também projetar esta aqui em cima, claro
da tela, e suponho que eu fiz isso.

456
00:18:44,520 --> 00:18:49,300
Suponha que eu queria inserir o nome
Daven em em minha estrutura de dados.

457
00:18:49,300 --> 00:18:52,100
>> Então, eu quero inserir uma string
Daven na estrutura de dados.

458
00:18:52,100 --> 00:18:54,370
E se eu não usar um
Hash Table, mas eu uso

459
00:18:54,370 --> 00:18:56,980
algo que é mais do tipo árvore
como uma árvore genealógica, onde

460
00:18:56,980 --> 00:18:59,670
você tem alguma raiz no
nós e folhas superiores e, em seguida,

461
00:18:59,670 --> 00:19:01,440
que ir para baixo e para fora.

462
00:19:01,440 --> 00:19:04,450
Suponhamos, então, que eu
deseja inserir Daven de

463
00:19:04,450 --> 00:19:06,430
em que é atualmente uma lista vazia.

464
00:19:06,430 --> 00:19:09,780
Eu vou fazer o seguinte: Eu sou
vai criar um nó desta família

465
00:19:09,780 --> 00:19:15,170
árvore-como estrutura de dados que parece
um pouco parecido com isso, cada uma das quais

466
00:19:15,170 --> 00:19:19,640
retângulos tem, digamos,
para agora 26 elementos nele.

467
00:19:19,640 --> 00:19:21,650
E cada uma das células
nesta matriz vai

468
00:19:21,650 --> 00:19:23,470
para representar a letra de um alfabeto.

469
00:19:23,470 --> 00:19:28,190
>> Especificamente, eu estou indo para o tratamento
este é A, então B, então C, então D,

470
00:19:28,190 --> 00:19:29,310
este aqui.

471
00:19:29,310 --> 00:19:32,940
Então, isso vai efetivamente
representar a letra D.

472
00:19:32,940 --> 00:19:36,040
Mas para inserir todos Daven de
nome eu preciso fazer um pouco mais.

473
00:19:36,040 --> 00:19:37,840
Então, eu estou indo primeiro para mistura, por assim dizer.

474
00:19:37,840 --> 00:19:41,049
Vou olhar para a primeira letra
em Daven do que é, obviamente, uma D,

475
00:19:41,049 --> 00:19:42,840
e eu estou indo para alocar
um nó que parece

476
00:19:42,840 --> 00:19:45,570
como isto-- um grande retângulo grande
o suficiente para caber todo o alfabeto.

477
00:19:45,570 --> 00:19:47,140
>> Agora D é feito.

478
00:19:47,140 --> 00:19:49,720
Agora A. D-A-V-E-N é o objetivo.

479
00:19:49,720 --> 00:19:51,220
Então agora o que eu vou fazer é esta.

480
00:19:51,220 --> 00:19:54,027
Assim que eu comecei a notificação D
não há nenhum ponteiro lá.

481
00:19:54,027 --> 00:19:56,860
É valores de lixo, no momento,
ou eu poderia inicializar a null.

482
00:19:56,860 --> 00:19:59,630
Mas deixe-me continuar com
esta ideia de construir uma árvore.

483
00:19:59,630 --> 00:20:04,260
Deixe-me alocar mais um desses
nodos que contém 26 elementos nele.

484
00:20:04,260 --> 00:20:05,150
>> E você sabe o quê?

485
00:20:05,150 --> 00:20:09,130
Se este é apenas um nó na memória que
Eu criei com malloc, usando uma struct

486
00:20:09,130 --> 00:20:11,240
como veremos em breve,
Eu vou fazer isso-

487
00:20:11,240 --> 00:20:14,450
Vou desenhar uma seta de
a coisa que representasse D para baixo

488
00:20:14,450 --> 00:20:15,860
para este novo nó.

489
00:20:15,860 --> 00:20:19,240
E agora, pela primeira vez o seguinte
carta em nome de Daven,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- eu vou ir em frente
e desenhar outro nó como este,

491
00:20:24,150 --> 00:20:30,150
pelo que, os elementos de V, que aqui
vamos chamar de gritos instance--.

492
00:20:30,150 --> 00:20:31,020
Não vamos tirar lá.

493
00:20:31,020 --> 00:20:31,936
Vai aqui.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> Então nós vamos
consideram que este é V.

496
00:20:35,712 --> 00:20:44,920
E então aqui vamos índice
para baixo de V para o que vamos considerar E.

497
00:20:44,920 --> 00:20:50,100
E então a partir daqui vamos
vá ter um desses nós aqui.

498
00:20:50,100 --> 00:20:52,930
E agora nós temos uma pergunta para responder.

499
00:20:52,930 --> 00:20:57,840
Eu preciso de alguma forma indicam que
estamos no fim da cadeia Daven.

500
00:20:57,840 --> 00:20:59,490
Então, eu poderia deixá-lo nulo.

501
00:20:59,490 --> 00:21:02,670
>> Mas o que se tem de Daven
nome completo também, que

502
00:21:02,670 --> 00:21:04,280
é, como já dissemos, Davenport?

503
00:21:04,280 --> 00:21:06,970
Então, o que se é Daven
realmente uma substring,

504
00:21:06,970 --> 00:21:08,960
um prefixo de uma seqüência muito mais tempo?

505
00:21:08,960 --> 00:21:11,450
Não podemos simplesmente permanentemente
dizer nada vai

506
00:21:11,450 --> 00:21:14,410
para ir lá, porque podíamos
nunca insira uma palavra como Davenport

507
00:21:14,410 --> 00:21:15,840
para esta estrutura de dados

508
00:21:15,840 --> 00:21:19,560
>> Então, o que nós poderíamos fazer é em vez
tratar cada um desses elementos

509
00:21:19,560 --> 00:21:22,170
Tendo como talvez dois
elementos dentro deles.

510
00:21:22,170 --> 00:21:24,810
Um deles é um ponteiro, de fato,
como eu venho fazendo.

511
00:21:24,810 --> 00:21:27,100
Assim, cada uma destas caixas
não é apenas um celular.

512
00:21:27,100 --> 00:21:29,855
Mas e se o topo
um-- do um fundo

513
00:21:29,855 --> 00:21:32,230
vai ser nulo, porque
não há Davenport ainda.

514
00:21:32,230 --> 00:21:34,197
E se o topo
é algum valor especial?

515
00:21:34,197 --> 00:21:36,530
E isso vai ser um pouco
difícil desenhá-la deste tamanho.

516
00:21:36,530 --> 00:21:38,130
Mas acho que é apenas uma marca de verificação.

517
00:21:38,130 --> 00:21:38,920
Confira.

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N é uma seqüência
nesta estrutura de dados.

519
00:21:44,230 --> 00:21:48,350
>> Enquanto isso, se eu tivesse mais espaço
aqui, eu poderia fazer P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
e eu poderia colocar o check-in o nó
que tem a letra T no final.

521
00:21:52,650 --> 00:21:55,460
Portanto, este é um massivamente
estrutura de dados de aparência complexa.

522
00:21:55,460 --> 00:21:57,210
E a minha letra
certamente não ajuda.

523
00:21:57,210 --> 00:22:00,043
Mas se eu queria inserir algo
outra coisa, considere o que faríamos.

524
00:22:00,043 --> 00:22:03,370
Se quiséssemos colocar David na,
nós seguem a mesma lógica, D-A-V,

525
00:22:03,370 --> 00:22:08,802
mas agora eu apontaria na próxima
elemento não a partir de E, mas a partir de I a D.

526
00:22:08,802 --> 00:22:10,760
Portanto, não vai ser
mais nós nesta árvore.

527
00:22:10,760 --> 00:22:12,325
Nós vamos ter chamada malloc mais.

528
00:22:12,325 --> 00:22:14,700
Mas eu não quero fazer uma
bagunça completa da imagem.

529
00:22:14,700 --> 00:22:17,710
Então, vamos olhar para uma vez
que foi pré-formulados

530
00:22:17,710 --> 00:22:21,810
assim com não ponto, ponto,
pontos, mas apenas matrizes abreviados.

531
00:22:21,810 --> 00:22:23,950
Mas cada um dos nós
nesta árvore-se aqui

532
00:22:23,950 --> 00:22:26,700
representa o mesmo coisa--
uma série de Ray tamanho 26.

533
00:22:26,700 --> 00:22:28,860
>> Ou, se quisermos ser
realmente bom agora, o que

534
00:22:28,860 --> 00:22:30,790
se o nome de alguém como
um apóstrofo, vamos

535
00:22:30,790 --> 00:22:35,560
supor que cada nó tem realmente
como 27 índices em que, não apenas 26.

536
00:22:35,560 --> 00:22:42,020
Então, isso agora vai ser um dos dados
uma estrutura chamada trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
Uma trie, que supostamente é
historicamente um nome inteligente para uma árvore

538
00:22:46,120 --> 00:22:49,040
otimizado para
de recuperação, o que, naturalmente,

539
00:22:49,040 --> 00:22:50,870
é soletrado com um I-E por isso é trie.

540
00:22:50,870 --> 00:22:52,710
Mas essa é a história da trie.

541
00:22:52,710 --> 00:22:55,860
>> Assim, uma trie é esses dados em árvore
estrutura como uma árvore genealógica

542
00:22:55,860 --> 00:22:57,510
que em última análise se comporta assim.

543
00:22:57,510 --> 00:23:00,890
E aqui é apenas mais um exemplo de uma
todo monte de nomes de outras pessoas.

544
00:23:00,890 --> 00:23:03,540
Mas a questão agora
na mão é o que tem

545
00:23:03,540 --> 00:23:08,070
ganhamos através da introdução de um indiscutivelmente mais
estrutura de dados complicado, e um,

546
00:23:08,070 --> 00:23:09,870
francamente, que utiliza uma grande quantidade de memória.

547
00:23:09,870 --> 00:23:11,703
>> Porque mesmo que,
no momento, eu só estou

548
00:23:11,703 --> 00:23:15,050
usando ponteiro D e
A e V e Es e Ns,

549
00:23:15,050 --> 00:23:16,700
Eu estou perdendo um pedaço de muita memória.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
Mas onde eu passar um recurso,
Eu tendo a não ganhar de volta um outro.

552
00:23:22,660 --> 00:23:26,020
Então, se eu estou gastando mais espaço,
o que é, provavelmente, a esperança?

553
00:23:26,020 --> 00:23:27,407
Que eu estou gastando menos com o que?

554
00:23:27,407 --> 00:23:28,240
AUDIÊNCIA: Menos tempo.

555
00:23:28,240 --> 00:23:28,990
DAVID MALAN: Time.

556
00:23:28,990 --> 00:23:30,320
Agora, por que pode ser isso?

557
00:23:30,320 --> 00:23:33,880
Bem, o que é a inserção
tempo, em termos de grande ó agora,

558
00:23:33,880 --> 00:23:37,660
de um nome como Daven
ou Davenport ou David?

559
00:23:37,660 --> 00:23:39,340
Bem, Daven era de cinco etapas.

560
00:23:39,340 --> 00:23:42,350
Davenport seria nove etapas,
por isso seria mais alguns passos.

561
00:23:42,350 --> 00:23:44,250
David seria cinco passos bem.

562
00:23:44,250 --> 00:23:47,230
Portanto, estas são de concreto
números, mas certamente há

563
00:23:47,230 --> 00:23:49,550
um limite superior sobre o
comprimento do nome de alguém.

564
00:23:49,550 --> 00:23:52,240
E, de fato, no problema
conjuntos de cinco especificação,

565
00:23:52,240 --> 00:23:54,050
vamos propor
que é algo

566
00:23:54,050 --> 00:23:55,470
que é de 40 caracteres e tantos.

567
00:23:55,470 --> 00:23:58,180
>> Realisticamente, ninguém tem
um nome infinitamente longo,

568
00:23:58,180 --> 00:24:01,542
o que quer dizer que o comprimento de um
nome ou o comprimento de uma string que pode

569
00:24:01,542 --> 00:24:03,750
ter certeza de que o estado de
estrutura é sem dúvida o que?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
É constante.

572
00:24:06,250 --> 00:24:06,430
Certo?

573
00:24:06,430 --> 00:24:09,310
Pode ser uma grande constante como
40 e poucos anos, mas é constante.

574
00:24:09,310 --> 00:24:13,752
E isso não tem nenhuma dependência de quantos
outros nomes estão nesta estrutura de dados.

575
00:24:13,752 --> 00:24:15,460
Em outras palavras, se I
queria agora inserir

576
00:24:15,460 --> 00:24:20,540
Colton ou Gabriel ou Rob ou Zamyla ou
Alison ou Belinda ou quaisquer outros nomes

577
00:24:20,540 --> 00:24:23,940
da equipe em dados
estrutura, é o tempo de execução

578
00:24:23,940 --> 00:24:26,750
de inserir outros nomes
vai ser em tudo impactaram

579
00:24:26,750 --> 00:24:30,220
pela forma como muitos outros elementos são
na estrutura de dados já?

580
00:24:30,220 --> 00:24:31,040
Não é.

581
00:24:31,040 --> 00:24:31,540
Certo?

582
00:24:31,540 --> 00:24:36,150
Porque nós estamos efetivamente usando
esta tabela hash de multi-camada.

583
00:24:36,150 --> 00:24:38,280
E o tempo de execução de
qualquer destas operações

584
00:24:38,280 --> 00:24:41,510
não é dependente do número de
elementos que se encontram na estrutura de dados

585
00:24:41,510 --> 00:24:43,090
ou que são, eventualmente, indo
estar na estrutura de dados,

586
00:24:43,090 --> 00:24:44,714
mas no comprimento do que especificamente?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> A seqüência de estar
inserido, o que faz

589
00:24:49,200 --> 00:24:52,580
este assintoticamente constante
tempo-- grande O de um.

590
00:24:52,580 --> 00:24:54,720
E, francamente, só em
o mundo real, este

591
00:24:54,720 --> 00:24:58,380
significa inserir o nome de Daven leva
como cinco etapas, ou Davenport nove

592
00:24:58,380 --> 00:25:00,100
etapas, ou David cinco etapas.

593
00:25:00,100 --> 00:25:03,071
Isso é muito danado pequenos tempos de execução.

594
00:25:03,071 --> 00:25:05,320
E, de fato, isso é muito
coisa boa, especialmente quando

595
00:25:05,320 --> 00:25:08,126
não é dependente do total
número de elementos de lá.

596
00:25:08,126 --> 00:25:10,500
Então, como podemos implementar esta
tipo de estrutura em código?

597
00:25:10,500 --> 00:25:12,900
É um pouco mais
complexo, mas ainda é

598
00:25:12,900 --> 00:25:15,050
apenas uma aplicação de
blocos de construção básicos.

599
00:25:15,050 --> 00:25:17,830
Eu estou indo para redefinir
nos nó como se segue:

600
00:25:17,830 --> 00:25:21,100
booleano chamado word-- e esta
poderia ser chamado de qualquer coisa.

601
00:25:21,100 --> 00:25:23,970
Mas o representa boleano
o que eu desenhei como uma marca de verificação.

602
00:25:23,970 --> 00:25:24,490
Sim.

603
00:25:24,490 --> 00:25:26,720
Esta é a extremidade de uma corda
nesta estrutura de dados.

604
00:25:26,720 --> 00:25:30,702
>> E, claro, a estrela nó
não está se referindo a crianças.

605
00:25:30,702 --> 00:25:32,410
E, de fato, assim como
uma árvore de família, você

606
00:25:32,410 --> 00:25:34,370
consideraria os nós
que são pendurado

607
00:25:34,370 --> 00:25:36,920
da parte inferior de alguns dos pais
elemento a ser crianças.

608
00:25:36,920 --> 00:25:40,510
E assim as crianças vai
ser uma matriz de 27, a uma 27th

609
00:25:40,510 --> 00:25:41,680
sendo apenas para apóstrofo.

610
00:25:41,680 --> 00:25:43,390
Nós estamos indo para classificar
de caso especial que.

611
00:25:43,390 --> 00:25:45,400
Então você pode ter certeza
nomes com apóstrofo.

612
00:25:45,400 --> 00:25:47,399
Talvez até hífen deve
vá lá, mas você

613
00:25:47,399 --> 00:25:50,330
ver em conjunto p 5 só cuidado
sobre letras e apóstrofos.

614
00:25:50,330 --> 00:25:52,990
>> E então como é que você representa
a própria estrutura de dados?

615
00:25:52,990 --> 00:25:56,454
Como você representar a raiz
desta trie, por assim dizer?

616
00:25:56,454 --> 00:25:59,620
Bem, assim como com uma lista ligada, você
precisa de um ponteiro para o primeiro elemento.

617
00:25:59,620 --> 00:26:04,270
Com uma trie você só precisa de um
ponteiro para a raiz desta trie.

618
00:26:04,270 --> 00:26:07,290
E a partir daí você pode botar
o seu caminho cada vez mais fundo

619
00:26:07,290 --> 00:26:10,460
para todos os outros nós na estrutura.

620
00:26:10,460 --> 00:26:13,440
Então simplesmente com esta lata
nós representamos que struct.

621
00:26:13,440 --> 00:26:15,877
>> Agora Meanwhile-- Oh, pergunta.

622
00:26:15,877 --> 00:26:17,220
>> AUDIÊNCIA: Qual é palavra bool?

623
00:26:17,220 --> 00:26:20,490
>> DAVID MALAN: palavra Bool é
apenas nesta encarnação C

624
00:26:20,490 --> 00:26:22,920
do que eu descrevi
nessa caixa aqui, quando

625
00:26:22,920 --> 00:26:26,000
Comecei dividindo cada um dos
elementos em duas peças da matriz.

626
00:26:26,000 --> 00:26:27,600
Um deles é um ponteiro para o próximo nó.

627
00:26:27,600 --> 00:26:30,280
A outra tem que ser
algo como uma caixa de seleção

628
00:26:30,280 --> 00:26:33,770
dizer que sim, há uma
Daven palavra que termina aqui,

629
00:26:33,770 --> 00:26:35,610
porque não queremos,
no momento, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Mesmo que Dave vai ser um
palavra legítima, ele não está no trie

631
00:26:39,320 --> 00:26:39,830
Ainda.

632
00:26:39,830 --> 00:26:40,950
E D não é uma palavra.

633
00:26:40,950 --> 00:26:42,770
E D-A não é uma palavra ou um nome.

634
00:26:42,770 --> 00:26:45,020
Assim, a marca de verificação
indica apenas uma vez você

635
00:26:45,020 --> 00:26:48,190
atingir esse nó é o
trajetória anterior de personagens

636
00:26:48,190 --> 00:26:50,700
na verdade, uma seqüência de caracteres que você inseriu.

637
00:26:50,700 --> 00:26:53,660
Então, isso é tudo o bool
não está fazendo por nós.

638
00:26:53,660 --> 00:26:55,500
>> Quaisquer outras perguntas sobre tentativas?

639
00:26:55,500 --> 00:26:56,215
Sim.

640
00:26:56,215 --> 00:26:58,035
>> AUDIÊNCIA: Qual é a sobreposição?

641
00:26:58,035 --> 00:26:59,945
E se você tem um Dave e um Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID MALAN: Perfeito.

643
00:27:00,820 --> 00:27:02,580
E se você tem um Dave e um Daven?

644
00:27:02,580 --> 00:27:06,240
Então, se nós inserimos, digamos, um apelido,
para David-- Dave-- D-A-V-E?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
Esta é realmente super simples.

647
00:27:08,700 --> 00:27:10,325
Então nós só vamos levar quatro etapas.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. E o que eu tenho que
fazer, uma vez que eu bati quarta nó?

650
00:27:15,847 --> 00:27:16,680
Basta ir verificar.

651
00:27:16,680 --> 00:27:18,000
Já está pronto para ir.

652
00:27:18,000 --> 00:27:18,840
Feito.

653
00:27:18,840 --> 00:27:19,750
Quatro passos.

654
00:27:19,750 --> 00:27:21,590
Constante de tempo assintoticamente.

655
00:27:21,590 --> 00:27:26,300
E agora que já indicaram que tanto Dave
e Daven são strings na estrutura.

656
00:27:26,300 --> 00:27:27,710
Então, não é um problema.

657
00:27:27,710 --> 00:27:30,200
E observe como a presença
Daven de não torná-lo

658
00:27:30,200 --> 00:27:34,750
levar mais tempo ou menos
tempo para Dave e vice-versa.

659
00:27:34,750 --> 00:27:36,000
>> Então o que mais nós podemos fazer?

660
00:27:36,000 --> 00:27:40,680
Nós usamos esta metáfora antes
bandejas de representar algo.

661
00:27:40,680 --> 00:27:43,380
Mas verifica-se que a
pilha de tabuleiros é realmente

662
00:27:43,380 --> 00:27:47,187
demonstrativo de outro abstrato de dados
type-- uma estrutura de dados de nível superior

663
00:27:47,187 --> 00:27:49,770
que, no final do dia é apenas
como uma matriz ou uma lista ligada

664
00:27:49,770 --> 00:27:50,970
ou algo mais mundano.

665
00:27:50,970 --> 00:27:53,270
Mas é uma mais interessante
conceito conceitual.

666
00:27:53,270 --> 00:27:56,440
Uma pilha, como estes
Bandejas aqui em Mather,

667
00:27:56,440 --> 00:27:58,750
são geralmente chamados
apenas que-- uma pilha.

668
00:27:58,750 --> 00:28:02,540
>> E, neste tipo de estrutura de dados
você tem duas operations--

669
00:28:02,540 --> 00:28:05,880
você tem um chamado de impulso para
adicionando algo para a pilha,

670
00:28:05,880 --> 00:28:08,320
como colocar outra bandeja
trás sobre o topo da pilha.

671
00:28:08,320 --> 00:28:11,350
E em seguida, pop, o que significa que
tomar o mais alto para fora da bandeja.

672
00:28:11,350 --> 00:28:16,210
Mas o que é importante sobre uma pilha é que
ele tem essa característica curiosa.

673
00:28:16,210 --> 00:28:19,560
Como a equipe de sala de jantar são
rearranjar as bandejas para a próxima refeição,

674
00:28:19,560 --> 00:28:21,380
o que vai ser
verdade sobre como os alunos

675
00:28:21,380 --> 00:28:22,856
interagir com essa estrutura de dados?

676
00:28:22,856 --> 00:28:24,480
AUDIÊNCIA: Eles estão indo estalar um fora.

677
00:28:24,480 --> 00:28:26,550
DAVID MALAN: Eles vão
estalar um fora, espero que o topo.

678
00:28:26,550 --> 00:28:28,910
Caso contrário, é apenas uma espécie de estúpida
para percorrer todo o caminho até o fundo.

679
00:28:28,910 --> 00:28:29,070
Certo?

680
00:28:29,070 --> 00:28:31,620
A estrutura de dados realmente não permite
você pegar a bandeja inferior, pelo menos,

681
00:28:31,620 --> 00:28:32,520
facilmente.

682
00:28:32,520 --> 00:28:35,040
Então há esse curioso
propriedade de uma pilha

683
00:28:35,040 --> 00:28:39,730
que o último item é
vai ser o primeiro a sair.

684
00:28:39,730 --> 00:28:43,400
E os cientistas da computação chamam
este LIFO-- último a entrar, primeiro a sair.

685
00:28:43,400 --> 00:28:45,540
E ele realmente tem
aplicações interessantes.

686
00:28:45,540 --> 00:28:50,090
Não é necessariamente tão óbvio como alguns
outros, mas pode, de fato, ser útil,

687
00:28:50,090 --> 00:28:54,040
e pode, de facto, ser implementado
em um par de maneiras diferentes.

688
00:28:54,040 --> 00:28:58,550
>> Então, um, e na verdade, vamos
me não para mergulhar nisso.

689
00:28:58,550 --> 00:28:59,860
Vamos fazer isso em seu lugar.

690
00:28:59,860 --> 00:29:03,700
Vamos olhar para um que é quase o
mesma idéia, mas é um pouco mais justo.

691
00:29:03,700 --> 00:29:04,200
Certo?

692
00:29:04,200 --> 00:29:07,560
Se você é um desses meninos fãs ou
meninas que realmente gosta de produtos da Apple

693
00:29:07,560 --> 00:29:10,130
e você acordou às 3h00
para alinhar em alguma loja

694
00:29:10,130 --> 00:29:14,150
para obter o mais recente iPhone, você
poderia ter fila como este.

695
00:29:14,150 --> 00:29:15,800
>> Agora a fila é muito deliberadamente nomeado.

696
00:29:15,800 --> 00:29:18,190
É uma linha porque não há
alguma justiça a ele.

697
00:29:18,190 --> 00:29:18,690
Certo?

698
00:29:18,690 --> 00:29:21,690
Seria uma espécie de sugado se você tiver
chegou primeiro na Apple Store

699
00:29:21,690 --> 00:29:25,700
mas você é efetivamente o bottommost
bandeja porque os funcionários da Apple, em seguida,

700
00:29:25,700 --> 00:29:28,189
estalar a última pessoa que
realmente tem na linha.

701
00:29:28,189 --> 00:29:31,230
Então, pilhas e filas, embora
funcionalmente eles são tipo do same--

702
00:29:31,230 --> 00:29:33,105
é só esta coleção
de recursos que é

703
00:29:33,105 --> 00:29:36,210
vai crescer e shrink-- existe
este aspecto justiça a ele,

704
00:29:36,210 --> 00:29:39,634
pelo menos, no mundo real,
onde as operações se exercita

705
00:29:39,634 --> 00:29:40,800
são fundamentalmente diferentes.

706
00:29:40,800 --> 00:29:43,360
Um stack-- uma fila
rather-- é dito ter

707
00:29:43,360 --> 00:29:45,320
duas operações: fila de n e d fila.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
Ou você pode chamá-los
uma série de coisas.

710
00:29:48,090 --> 00:29:50,770
Mas você só quer capturar
a noção de que uma é a adição de

711
00:29:50,770 --> 00:29:53,230
e uma última análise, é subtraindo.

712
00:29:53,230 --> 00:29:58,840
>> Agora sob o capô, tanto a pilha
e uma fila poderia ser implementado como?

713
00:29:58,840 --> 00:30:01,390
Não vamos entrar no código de
porque o nível mais elevado

714
00:30:01,390 --> 00:30:03,387
idéia é uma espécie de mais evidente.

715
00:30:03,387 --> 00:30:04,470
Quero dizer, o que os humanos fazem?

716
00:30:04,470 --> 00:30:07,030
Se eu sou a primeira pessoa no Apple
Armazenar e esta é a porta da frente,

717
00:30:07,030 --> 00:30:08,130
você sabe, eu vou ficar aqui.

718
00:30:08,130 --> 00:30:09,750
E a próxima pessoa
vai ficar aqui.

719
00:30:09,750 --> 00:30:11,500
E a próxima pessoa
vai ficar aqui.

720
00:30:11,500 --> 00:30:13,792
Então, o que estrutura de dados
presta-se a uma fila?

721
00:30:13,792 --> 00:30:14,542
>> AUDIÊNCIA: A fila.

722
00:30:14,542 --> 00:30:15,667
DAVID MALAN: Bem, uma fila.

723
00:30:15,667 --> 00:30:16,390
Claro.

724
00:30:16,390 --> 00:30:16,920
O que mais?

725
00:30:16,920 --> 00:30:17,600
>> AUDIÊNCIA: Uma lista ligada.

726
00:30:17,600 --> 00:30:18,990
>> DAVID MALAN: um ligado
lista que poderia implementar.

727
00:30:18,990 --> 00:30:22,500
E uma lista ligada é bom porque depois
ele pode crescer arbitrariamente longa em oposição

728
00:30:22,500 --> 00:30:24,880
para ter um número fixo
de pessoas na loja.

729
00:30:24,880 --> 00:30:27,030
Mas talvez um número fixo
de lugares é legítimo.

730
00:30:27,030 --> 00:30:30,350
Porque se eles só têm como 20
iPhones no primeiro dia, talvez

731
00:30:30,350 --> 00:30:33,930
eles só precisam de uma matriz de tamanho
20 para representar essa fila, que

732
00:30:33,930 --> 00:30:37,070
é só para dizer agora, uma vez que começar a falar
sobre esses problemas de nível superior,

733
00:30:37,070 --> 00:30:38,890
você pode implementá-lo
em qualquer número de maneiras.

734
00:30:38,890 --> 00:30:42,030
E não há, provavelmente, só vai
ser um trade off no espaço e no tempo

735
00:30:42,030 --> 00:30:43,950
ou apenas em sua própria complexidade do código.

736
00:30:43,950 --> 00:30:45,380
>> Que tal uma pilha?

737
00:30:45,380 --> 00:30:48,190
Bem, uma pilha, temos visto também
poderia ser apenas estas bandejas.

738
00:30:48,190 --> 00:30:50,007
E você poderia implementar esta uma matriz.

739
00:30:50,007 --> 00:30:53,090
Mas em algum momento, se você usar uma matriz,
o que vai acontecer com as bandejas

740
00:30:53,090 --> 00:30:54,173
você está tentando colocar para baixo?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
Tudo certo.

743
00:30:55,670 --> 00:30:57,490
Você só vai
ser capaz de ir tão alto.

744
00:30:57,490 --> 00:31:00,156
E eu acho que eles estão em Mather
na verdade, em que a abertura do recesso.

745
00:31:00,156 --> 00:31:01,950
Então, na verdade, é quase
como Mather está usando

746
00:31:01,950 --> 00:31:03,783
uma matriz de tamanho fixo,
porque só você pode

747
00:31:03,783 --> 00:31:08,302
caber tantas bandejas em que a abertura de
a parede abaixo joelhos das pessoas.

748
00:31:08,302 --> 00:31:10,010
E, de modo que pode ser
Diz-se que uma matriz,

749
00:31:10,010 --> 00:31:14,300
mas nós certamente poderia implementar essa
de modo mais geral, com uma lista ligada.

750
00:31:14,300 --> 00:31:16,390
>> Bem, o que dizer de uma outra estrutura de dados?

751
00:31:16,390 --> 00:31:18,760
Deixe-me puxar para cima um outro visuais aqui.

752
00:31:18,760 --> 00:31:24,710
Algo como que tal essa aqui?

753
00:31:24,710 --> 00:31:28,920
Por que ele pode ser útil para não ter
algo tão extravagante como uma trie, que

754
00:31:28,920 --> 00:31:32,370
vimos que tinha esses nós muito largas,
cada um dos quais está em uma matriz?

755
00:31:32,370 --> 00:31:35,740
Mas o que se fazer algo mais
simplesmente, como uma árvore genealógica da velha escola,

756
00:31:35,740 --> 00:31:38,110
cada um de cujos nós aqui
é apenas armazenar um número.

757
00:31:38,110 --> 00:31:42,180
Em vez de um nome ou um descendente
é apenas armazenar um número como este.

758
00:31:42,180 --> 00:31:45,250
>> Bem, o jargão que usamos em
estruturas de dados é duas tentativas

759
00:31:45,250 --> 00:31:49,510
e árvores, onde uma trie, novamente, é
apenas uma cujos nós são matrizes,

760
00:31:49,510 --> 00:31:51,680
ainda é o que você pode
usar da escola de classe

761
00:31:51,680 --> 00:31:53,860
quando você fez uma família
tree-- folhas e da raiz

762
00:31:53,860 --> 00:31:57,250
da árvore e crianças do
pais e irmãos dos mesmos.

763
00:31:57,250 --> 00:32:03,670
E poderíamos implementar uma árvore,
por exemplo, como simplesmente como este.

764
00:32:03,670 --> 00:32:07,420
Uma árvore, como se um nó, um dos
estes círculos que contém um número,

765
00:32:07,420 --> 00:32:09,947
ele não vai ter
um ponteiro, mas dois.

766
00:32:09,947 --> 00:32:11,780
E assim que você adicionar
um segundo ponteiro, você

767
00:32:11,780 --> 00:32:13,905
agora pode realmente fazer tipo
de dados bi-dimensional

768
00:32:13,905 --> 00:32:14,780
estruturas em memória.

769
00:32:14,780 --> 00:32:16,660
Muito parecido com um bidimensional
array, você pode

770
00:32:16,660 --> 00:32:18,904
ter tipo de bi-dimensional
listas ligadas, mas os

771
00:32:18,904 --> 00:32:20,820
que seguem um padrão
onde não há ciclos.

772
00:32:20,820 --> 00:32:24,487
É verdadeiramente uma árvore com uma
maneira avô aqui e depois para cima

773
00:32:24,487 --> 00:32:27,320
alguns pais e filhos e
netos e bisnetos.

774
00:32:27,320 --> 00:32:28,370
e assim por diante.

775
00:32:28,370 --> 00:32:32,390
>> Mas o que é realmente interessante sobre isso também,
só para provocá-lo com um pouco de código,

776
00:32:32,390 --> 00:32:35,370
recordação de recursão
algum tempo atrás, em que

777
00:32:35,370 --> 00:32:38,220
você escrever uma função que chama a si mesmo.

778
00:32:38,220 --> 00:32:41,140
Esta é uma bela oportunidade
para implementar algo

779
00:32:41,140 --> 00:32:42,920
como recursão, porque considerar isso.

780
00:32:42,920 --> 00:32:43,860
>> Esta é uma árvore.

781
00:32:43,860 --> 00:32:48,040
E eu tenho sido um pouco anal com a forma como
Eu coloquei os números inteiros para a rua.

782
00:32:48,040 --> 00:32:51,020
Tanto é assim que ele tem uma especial
nome-- uma árvore de busca binária.

783
00:32:51,020 --> 00:32:53,460
Agora nós já ouviu falar de binário
procurar, mas você pode

784
00:32:53,460 --> 00:32:55,180
trabalhar para trás a partir do nome desta coisa?

785
00:32:55,180 --> 00:32:59,280
Qual é o padrão de como eu
inseridos os números inteiros para esta árvore?

786
00:32:59,280 --> 00:33:00,696
Não é arbitrária.

787
00:33:00,696 --> 00:33:01,570
Há algum padrão.

788
00:33:01,570 --> 00:33:02,090
Sim.

789
00:33:02,090 --> 00:33:03,370
>> AUDIÊNCIA: Os menores de esquerda.

790
00:33:03,370 --> 00:33:03,690
>> DAVID MALAN: Yeah.

791
00:33:03,690 --> 00:33:05,062
Os menores estão à esquerda.

792
00:33:05,062 --> 00:33:06,270
As maiores são na direita.

793
00:33:06,270 --> 00:33:12,940
De tal forma que uma afirmação verdadeira é uma
pai é maior do que o seu filho esquerdo,

794
00:33:12,940 --> 00:33:14,850
mas menos do que o seu filho direito.

795
00:33:14,850 --> 00:33:17,750
E só isso é mesmo um
definição verbal recursiva

796
00:33:17,750 --> 00:33:20,500
porque você pode aplicar esse
mesma lógica para cada nó

797
00:33:20,500 --> 00:33:23,080
E só bottoms
para fora, um caso base, se você

798
00:33:23,080 --> 00:33:25,740
vontade, quando você bate um dos
as folhas, por assim dizer,

799
00:33:25,740 --> 00:33:28,580
onde uma licença não tem filhos ainda.

800
00:33:28,580 --> 00:33:30,614
>> Agora, como você pode encontrar o número 44?

801
00:33:30,614 --> 00:33:32,280
Você poderia começar na raiz e dizer, hm.

802
00:33:32,280 --> 00:33:35,690
55 não é 44 Então eu quero ir
direito ou eu quero ir para a esquerda?

803
00:33:35,690 --> 00:33:37,190
Bem, obviamente você quer ir esquerdo.

804
00:33:37,190 --> 00:33:40,060
E assim é como o telefone
exemplo livro em busca binária

805
00:33:40,060 --> 00:33:41,099
de modo mais geral.

806
00:33:41,099 --> 00:33:43,390
Mas estamos implementá-lo
agora um pouco mais dinâmica

807
00:33:43,390 --> 00:33:45,339
do que uma matriz pode permitir.

808
00:33:45,339 --> 00:33:48,130
E, na verdade, se você quiser olhar
no código, à primeira vista, com certeza.

809
00:33:48,130 --> 00:33:49,671
Parece que um monte de linhas.

810
00:33:49,671 --> 00:33:51,220
Mas é bem simples.

811
00:33:51,220 --> 00:33:54,490
Se você quiser implementar uma função
chamada pesquisa cujo propósito na vida

812
00:33:54,490 --> 00:33:57,290
é a busca de um valor
como n, um inteiro,

813
00:33:57,290 --> 00:34:01,756
e que você passou em um pointer--
um apontador para o nó das raízes,

814
00:34:01,756 --> 00:34:04,380
ao contrário, de que árvore da qual
você pode acessar tudo o mais,

815
00:34:04,380 --> 00:34:08,850
observe como diretamente
você pode implementar a lógica.

816
00:34:08,850 --> 00:34:10,880
Se árvore é nulo,
obviamente ele não está lá.

817
00:34:10,880 --> 00:34:11,880
Vamos apenas retornar falso.

818
00:34:11,880 --> 00:34:12,000
Certo?

819
00:34:12,000 --> 00:34:14,040
Se você entregá-lo nada,
não há nada lá.

820
00:34:14,040 --> 00:34:17,900
>> Logo, se n é inferior a
árvore seta n-- agora arrow n,

821
00:34:17,900 --> 00:34:20,670
lembrar que introduzimos Super
brevemente no outro dia,

822
00:34:20,670 --> 00:34:25,100
e que apenas significa de-referência a
ponteiro e olhar para o campo chamado n.

823
00:34:25,100 --> 00:34:27,690
Então isso significa ir lá e
olhar para o campo chamado n.

824
00:34:27,690 --> 00:34:33,810
Então, se n, o valor que se recebe, é menos
em que o valor do inteiro árvores,

825
00:34:33,810 --> 00:34:35,449
onde você quer ir?

826
00:34:35,449 --> 00:34:36,389
Para a esquerda.

827
00:34:36,389 --> 00:34:37,780
>> Então, observe a recursividade.

828
00:34:37,780 --> 00:34:39,860
Estou returning-- não é verdade.

829
00:34:39,860 --> 00:34:40,989
Não falsa.

830
00:34:40,989 --> 00:34:45,670
Estou voltando qualquer que seja a resposta
é a partir de uma chamada para mim, passando

831
00:34:45,670 --> 00:34:50,100
um n de novo, o que é redundante,
mas o que é um pouco diferente agora?

832
00:34:50,100 --> 00:34:51,989
Como eu estou fazendo o problema menor?

833
00:34:51,989 --> 00:34:54,920
Eu estou passando como o segundo
argumento, não a raiz da árvore,

834
00:34:54,920 --> 00:34:59,616
mas o filho esquerdo neste caso.

835
00:34:59,616 --> 00:35:00,990
Então, eu estou passando o filho esquerdo.

836
00:35:00,990 --> 00:35:04,720
>> Por outro lado, se n for maior do que
o nó Atualmente estou olhando,

837
00:35:04,720 --> 00:35:06,690
Eu procuro o lado direito.

838
00:35:06,690 --> 00:35:10,880
Outra coisa, se a árvore não é nulo, e
Se o elemento não está à esquerda

839
00:35:10,880 --> 00:35:13,240
e não é para a direita,
o que é maravilhosamente o caso?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Nós realmente encontramos o nó em
pergunta, e assim voltamos verdade.

842
00:35:18,440 --> 00:35:21,490
>> Então, nós apenas arranhamos a superfície
agora algumas dessas estruturas de dados.

843
00:35:21,490 --> 00:35:24,370
No conjunto de problemas de cinco você vai
explorar estes ainda mais longe,

844
00:35:24,370 --> 00:35:27,250
e você será dado o seu projeto
escolha de como ir sobre isso.

845
00:35:27,250 --> 00:35:30,250
O que eu gostaria de concluir sobre
é apenas um segundo teaser 30

846
00:35:30,250 --> 00:35:32,080
do que nos espera na próxima semana e além.

847
00:35:32,080 --> 00:35:35,390
>> Como nós begin-- felizmente você pode
penso-- nossa transição lenta

848
00:35:35,390 --> 00:35:38,680
do mundo da C e menor
detalhes de implementação nível,

849
00:35:38,680 --> 00:35:42,090
para um mundo em que podemos tomar para
certo que alguém tem, finalmente,

850
00:35:42,090 --> 00:35:44,010
implementado estes dados
estruturas para nós,

851
00:35:44,010 --> 00:35:47,570
e vamos começar a entender o
mundo real significa de implementação

852
00:35:47,570 --> 00:35:50,560
programas baseados na web e
sites mais geralmente

853
00:35:50,560 --> 00:35:52,910
e também a própria segurança
implicações que nós só

854
00:35:52,910 --> 00:35:54,850
começaram a arranhar a superfície do.

855
00:35:54,850 --> 00:35:57,320
Aqui está o que nos espera
nos dias que virão.

856
00:35:57,320 --> 00:36:00,480
>> [REPRODUÇÃO DE VÍDEO]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -Ele Veio com uma mensagem,
com um protocolo de todos os seus próprios.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Ele veio para um mundo de cruel
firewalls, roteadores indiferente,

861
00:36:30,894 --> 00:36:33,368
e perigos muito piores do que a morte.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Ele é rápido.

864
00:36:36,236 --> 00:36:37,980
Ele é forte.

865
00:36:37,980 --> 00:36:42,830
Ele é o TCP / IP, e ele tem o seu endereço.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Guerreiros da rede."

868
00:36:48,074 --> 00:36:49,660
[FIM REPRODUÇÃO DE VÍDEO]

869
00:36:49,660 --> 00:36:50,910
DAVID MALAN: Na próxima semana.

870
00:36:50,910 --> 00:36:51,880
Vamos vê-lo em seguida.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[REPRODUÇÃO DE VÍDEO]

873
00:36:56,060 --> 00:36:59,240
-E Agora, "Pensamentos Profundos"
por Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Começa sempre
palestras com: "Tudo bem."

876
00:37:05,820 --> 00:37:08,750
Por que não, "Aqui está a solução
ao conjunto de problemas desta semana "

877
00:37:08,750 --> 00:37:12,180
ou "Estamos dando a todos vocês um A?"

878
00:37:12,180 --> 00:37:13,380
[Risos]

879
00:37:13,380 --> 00:37:15,530
[FIM REPRODUÇÃO DE VÍDEO]