1
00:00:00,000 --> 00:00:00,030

2
00:00:00,030 --> 00:00:00,460
>> DAVID MALAN: Tudo bem.

3
00:00:00,460 --> 00:00:01,094
Estamos de volta.

4
00:00:01,094 --> 00:00:04,260
Portanto, neste segmento sobre a programação que
Pensei que faria é uma mistura de coisas.

5
00:00:04,260 --> 00:00:06,340
Um, fazer um pouco
de algo prático,

6
00:00:06,340 --> 00:00:08,690
embora com uma forma mais lúdica
environment-- programação

7
00:00:08,690 --> 00:00:11,620
um que é demonstrativo de
exatamente os tipos de idéias

8
00:00:11,620 --> 00:00:14,220
temos vindo a falar,
mas um pouco mais formalmente.

9
00:00:14,220 --> 00:00:18,200
Dois, olhar para alguns dos
as formas mais técnicas

10
00:00:18,200 --> 00:00:21,520
que um programador seria realmente resolver
problemas como o problema procura

11
00:00:21,520 --> 00:00:24,530
que olhou antes e
também uma mais fundamentalmente

12
00:00:24,530 --> 00:00:26,020
problema interessante de classificação.

13
00:00:26,020 --> 00:00:28,840
>> Nós só assumiu desde o ir buscar
que esse livro de telefone foi resolvido,

14
00:00:28,840 --> 00:00:31,980
mas que por si só é realmente uma espécie de
problema difícil com muitas maneiras diferentes

15
00:00:31,980 --> 00:00:32,479
resolvê-lo.

16
00:00:32,479 --> 00:00:34,366
Então, vamos usá-los como
uma classe de problemas

17
00:00:34,366 --> 00:00:36,740
representante das coisas que
pode ser resolvido de um modo geral.

18
00:00:36,740 --> 00:00:38,980
E então vamos falar
sobre com algum detalhe o que

19
00:00:38,980 --> 00:00:42,360
são chamados de dados structures--
formas mais extravagantes como listas ligadas

20
00:00:42,360 --> 00:00:46,290
e tabelas de hash e árvores que
um programador seria realmente

21
00:00:46,290 --> 00:00:48,890
usar e, geralmente, utilizar
em um quadro branco para pintar

22
00:00:48,890 --> 00:00:51,840
uma imagem do que ele ou ela
vislumbra para a implementação

23
00:00:51,840 --> 00:00:52,980
algum pedaço de software.

24
00:00:52,980 --> 00:00:55,130
>> Então vamos fazer o hands-on primeira parte.

25
00:00:55,130 --> 00:01:00,090
Então, basta sujar as mãos com um
ambiente chamada scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Esta é uma ferramenta que usamos
na nossa classe de graduação.

27
00:01:02,636 --> 00:01:04,510
Mesmo que ele é projetado
para as idades de 12 e acima,

28
00:01:04,510 --> 00:01:07,570
podemos usá-lo para o up
parte desse um pouco

29
00:01:07,570 --> 00:01:10,020
já que é um bom, divertido
forma gráfica da aprendizagem

30
00:01:10,020 --> 00:01:12,160
um pouco sobre programação.

31
00:01:12,160 --> 00:01:17,600
Então cabeça para que URL, onde você
deve ver uma página como esta,

32
00:01:17,600 --> 00:01:23,330
e vá em frente e clique
Junte-se a zero no canto superior direito

33
00:01:23,330 --> 00:01:28,300
e escolher um nome de usuário e uma
senha e, finalmente, obter-se

34
00:01:28,300 --> 00:01:29,970
um scratch.mit.edu account--.

35
00:01:29,970 --> 00:01:32,165

36
00:01:32,165 --> 00:01:34,665
Pensei em usar isso como uma
primeira oportunidade para mostrar isso.

37
00:01:34,665 --> 00:01:39,120
A questão foi levantada durante a pausa
sobre o código realmente se parece.

38
00:01:39,120 --> 00:01:41,315
E nós estávamos falando
durante a pausa de cerca de C,

39
00:01:41,315 --> 00:01:45,060
em particular um particular--
menor nível em uma linguagem mais antiga.

40
00:01:45,060 --> 00:01:47,750
E eu apenas fiz uma rápida
Google busca para encontrar o código C

41
00:01:47,750 --> 00:01:51,574
para pesquisa binária, o algoritmo que nós
usado para procurar o livro de telefone mais cedo.

42
00:01:51,574 --> 00:01:54,240
Neste exemplo particular, é claro,
não procurar um livro de telefone.

43
00:01:54,240 --> 00:01:57,840
Ele só procura um monte de
números na memória do computador.

44
00:01:57,840 --> 00:02:01,000
Mas se você gostaria de obter apenas um Visual
sentido do que uma programação real

45
00:02:01,000 --> 00:02:05,370
linguagem parece, parece
um pouco algo como isto.

46
00:02:05,370 --> 00:02:09,759
Portanto, é cerca de 20-plus,
30 ou mais linhas de código,

47
00:02:09,759 --> 00:02:12,640
mas a conversa que
estavam tendo durante as férias

48
00:02:12,640 --> 00:02:16,000
era sobre como isso realmente
se transformou em zeros e uns

49
00:02:16,000 --> 00:02:19,200
e se você não pode simplesmente reverter essa
processar e ir de zeros e uns

50
00:02:19,200 --> 00:02:20,210
voltar ao código.

51
00:02:20,210 --> 00:02:22,620
>> Infelizmente, o processo de
é tão transformadora

52
00:02:22,620 --> 00:02:24,890
que é muito mais fácil dizer do que fazer.

53
00:02:24,890 --> 00:02:29,400
Fui em frente e realmente se transformou
esse programa, Binary Search,

54
00:02:29,400 --> 00:02:32,700
em zeros e uns por meio de um
O programa chamado compilador que eu

55
00:02:32,700 --> 00:02:34,400
acontecer de ter aqui bem no meu Mac.

56
00:02:34,400 --> 00:02:37,850
E se você olhar para a tela
aqui, concentrando-se especificamente

57
00:02:37,850 --> 00:02:43,520
nesses seis colunas do meio somente,
você verá apenas zeros e uns.

58
00:02:43,520 --> 00:02:48,290
E esses são os zeros e uns que
compor exatamente esse programa de pesquisa.

59
00:02:48,290 --> 00:02:53,720
>> E assim cada pedaço de cinco bits,
cada byte de zeros e uns aqui,

60
00:02:53,720 --> 00:02:57,310
representam algumas instruções
tipicamente dentro de um computador.

61
00:02:57,310 --> 00:03:00,730
E, na verdade, se você já ouviu o
slogan de marketing "Intel inside" - que,

62
00:03:00,730 --> 00:03:04,610
é claro, significa apenas que você tem um
CPU Intel ou o cérebro dentro do computador.

63
00:03:04,610 --> 00:03:08,000
E o que significa ser um CPU é
que você tem um conjunto de instruções,

64
00:03:08,000 --> 00:03:08,840
por assim dizer.

65
00:03:08,840 --> 00:03:11,620
>> Cada CPU no mundo, muitos dos
-los feito pela Intel nos dias de hoje,

66
00:03:11,620 --> 00:03:13,690
compreende um finito
número de instruções.

67
00:03:13,690 --> 00:03:18,690
E essas instruções são tão baixo nível
como adicionar esses dois números juntos,

68
00:03:18,690 --> 00:03:22,560
multiplicar esses dois números juntos,
mover este pedaço de dados a partir daqui

69
00:03:22,560 --> 00:03:27,340
para aqui na memória, salvar esta
informações daqui até aqui na memória,

70
00:03:27,340 --> 00:03:32,200
e assim por forth-- muito, muito
baixo nível, detalhes quase eletrônicos.

71
00:03:32,200 --> 00:03:34,780
Mas com os matemático
operações acoplado

72
00:03:34,780 --> 00:03:37,410
com o que discutimos anteriormente,
a representação dos dados

73
00:03:37,410 --> 00:03:40,450
como zeros e uns, pode
você construir tudo

74
00:03:40,450 --> 00:03:44,180
que um computador pode fazer hoje, seja
é textual, gráfica, musical,

75
00:03:44,180 --> 00:03:45,580
ou então.

76
00:03:45,580 --> 00:03:49,450
>> Então isso é muito fácil de obter
perdido nas ervas daninhas de forma rápida.

77
00:03:49,450 --> 00:03:52,150
E há um monte de
desafios sintáticas

78
00:03:52,150 --> 00:03:56,630
em que se tornar o mais simples,
estúpido de erros de digitação nenhum do programa

79
00:03:56,630 --> 00:03:57,860
funcionará qualquer.

80
00:03:57,860 --> 00:04:00,366
E assim, em vez de usar um
linguagem como C, esta manhã,

81
00:04:00,366 --> 00:04:02,240
Eu pensei que seria
mais divertido para realmente fazer

82
00:04:02,240 --> 00:04:04,840
algo mais visual, que
enquanto projetado para crianças

83
00:04:04,840 --> 00:04:08,079
é, na verdade, uma manifestação perfeita
de uma programação real

84
00:04:08,079 --> 00:04:10,370
language-- só acontece de
usar imagens em vez de texto

85
00:04:10,370 --> 00:04:11,710
para representar essas idéias.

86
00:04:11,710 --> 00:04:15,470
>> Então, quando você de fato tem um
conta no scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
clique no botão Criar
no canto superior esquerdo do site.

88
00:04:21,070 --> 00:04:24,620
E você deve ver um ambiente como
o que eu estou prestes a ver em minha tela

89
00:04:24,620 --> 00:04:26,310
Aqui.

90
00:04:26,310 --> 00:04:29,350
E nós vamos gastar um pouco
pouco de tempo a jogar aqui.

91
00:04:29,350 --> 00:04:34,080
Vamos ver se nós não podemos todos resolver alguns
problemas em conjunto da seguinte maneira.

92
00:04:34,080 --> 00:04:39,420
>> Então, o que você verá dentro deste
environment-- e realmente apenas deixar

93
00:04:39,420 --> 00:04:40,050
me uma pausa.

94
00:04:40,050 --> 00:04:42,680
Será que alguém não está aqui?

95
00:04:42,680 --> 00:04:45,070
Não aqui?

96
00:04:45,070 --> 00:04:45,800
ESTÁ BEM.

97
00:04:45,800 --> 00:04:49,030
Então, deixe-me salientar alguns
características desse ambiente.

98
00:04:49,030 --> 00:04:55,024
>> Então, na parte superior esquerda da tela, nós
tem palco do zero, por assim dizer.

99
00:04:55,024 --> 00:04:57,440
Zero não é apenas o nome
desta linguagem de programação;

100
00:04:57,440 --> 00:05:00,356
é também o nome do gato que
você vê por padrão, não em laranja.

101
00:05:00,356 --> 00:05:02,160
Ele está em um estágio, de modo
tanto como eu descrevi

102
00:05:02,160 --> 00:05:05,770
a tartaruga anteriormente como estar em um
rectangular ambiente quadro branco.

103
00:05:05,770 --> 00:05:09,800
mundo deste gato está totalmente confinada
para esse retângulo em cima lá.

104
00:05:09,800 --> 00:05:12,210
>> Enquanto isso, do lado direito
lado aqui, é

105
00:05:12,210 --> 00:05:15,610
apenas uma área de roteiros, um
lousa em branco se você quiser.

106
00:05:15,610 --> 00:05:18,590
Este é o lugar onde nós estamos indo para escrever
nossos programas em apenas um momento.

107
00:05:18,590 --> 00:05:22,935
E os blocos de construção que deve
usado para gravar essa program-- o quebra-cabeça

108
00:05:22,935 --> 00:05:25,310
pedaços, se você will-- são
aqueles aqui no meio,

109
00:05:25,310 --> 00:05:27,500
e eles estão categorizados
pela funcionalidade.

110
00:05:27,500 --> 00:05:31,000
Assim, por exemplo, eu estou indo para ir em frente
e demonstram, pelo menos, um destes.

111
00:05:31,000 --> 00:05:33,690
Eu estou indo para ir em frente e clique
a categoria de controle em cima.

112
00:05:33,690 --> 00:05:35,720
>> Portanto, estas são as categorias em cima.

113
00:05:35,720 --> 00:05:39,410
Vou clique na categoria de Controle.

114
00:05:39,410 --> 00:05:44,020
Em vez disso, eu vou clique nos eventos
categoria, a primeira um em cima.

115
00:05:44,020 --> 00:05:47,790
E se você gostaria de acompanhar, mesmo
como fazer isso, você está muito bem-vindo para.

116
00:05:47,790 --> 00:05:52,180
Eu estou indo para clicar e arrastar esse
primeiro, "quando a bandeira verde clicado."

117
00:05:52,180 --> 00:05:58,410
E então eu vou deixá-la apenas
aproximadamente no topo das minhas folhas em branco.

118
00:05:58,410 --> 00:06:01,450
>> E o que é agradável sobre risco
é que esta parte do enigma, quando

119
00:06:01,450 --> 00:06:04,560
interligado com outro quebra-cabeça
peças, vai fazer literalmente

120
00:06:04,560 --> 00:06:06,460
o que essas peças do puzzle dizer que fazer.

121
00:06:06,460 --> 00:06:09,710
Assim, por exemplo, Scratch é certo
agora no meio de seu mundo.

122
00:06:09,710 --> 00:06:14,660
Eu estou indo para ir em frente e escolher
Agora, vamos dizer, a categoria Movimento,

123
00:06:14,660 --> 00:06:18,000
se você gostaria de fazer o
same-- categoria Motion.

124
00:06:18,000 --> 00:06:20,430
E agora notem eu tenho um todo
monte de peças do puzzle aqui

125
00:06:20,430 --> 00:06:23,370
que, novamente, tipo de fazer o que eles dizem.

126
00:06:23,370 --> 00:06:28,110
E eu estou indo para ir em frente e arrastar e
soltar o bloco movimento bem aqui.

127
00:06:28,110 --> 00:06:31,860
>> E note que, assim que você começa
perto da parte inferior da "bandeira verde

128
00:06:31,860 --> 00:06:34,580
clicado "botão, o aviso prévio
como uma linha branca aparece,

129
00:06:34,580 --> 00:06:36,950
como se fosse quase
magnética, ele quer ir para lá.

130
00:06:36,950 --> 00:06:43,070
Apenas deixe ir, e ele se encaixará
em conjunto e as formas irá corresponder.

131
00:06:43,070 --> 00:06:46,620
E agora você pode, talvez, quase
adivinhar onde estamos indo com isso.

132
00:06:46,620 --> 00:06:51,570
>> Se você olhar para o estágio zero
por aqui e olhar para o topo,

133
00:06:51,570 --> 00:06:55,142
você verá uma luz vermelha, um
pare o sinal, e uma bandeira verde.

134
00:06:55,142 --> 00:06:57,100
E eu estou indo para ir em frente
e assistir os meus screen--

135
00:06:57,100 --> 00:06:58,460
por apenas um momento, se pudesse.

136
00:06:58,460 --> 00:07:01,960
Vou clique no
bandeira verde agora,

137
00:07:01,960 --> 00:07:07,850
e moveu-se o que parece ser 10 passos
ou 10 pixels, 10 pontos, na tela.

138
00:07:07,850 --> 00:07:13,390
>> E assim não excitante,
mas deixe-me propor

139
00:07:13,390 --> 00:07:17,440
sem sequer ensinando isso, basta
usando o próprio seu próprio let intuition--

140
00:07:17,440 --> 00:07:22,560
-me propor que você descobrir como
fazer scratch pé direito para fora do palco.

141
00:07:22,560 --> 00:07:28,700
Tê-lo abrir caminho para o lado direito
a tela, todo o caminho para a direita.

142
00:07:28,700 --> 00:07:32,200
Deixe-me dar-lhe um momento
ou mais para lutar com isso.

143
00:07:32,200 --> 00:07:37,681
Você pode querer dar uma olhada
em outras categorias de blocos.

144
00:07:37,681 --> 00:07:38,180
Tudo certo.

145
00:07:38,180 --> 00:07:41,290
Então, só para recapitular, quando temos
a bandeira verde clicado aqui

146
00:07:41,290 --> 00:07:44,850
e mover 10 passos é a
única instrução, cada vez que eu

147
00:07:44,850 --> 00:07:46,720
clique na bandeira verde, o que está acontecendo?

148
00:07:46,720 --> 00:07:50,070
Bem, isso está executando o meu programa.

149
00:07:50,070 --> 00:07:52,450
Então, eu poderia fazer isso
talvez 10 vezes manualmente,

150
00:07:52,450 --> 00:07:55,130
mas este se sente um pouco
pouco hackish, por assim dizer,

151
00:07:55,130 --> 00:07:57,480
em que eu realmente não estou
resolvendo o problema.

152
00:07:57,480 --> 00:08:00,530
Eu só estou tentando novamente e
de novo e de novo e de novo

153
00:08:00,530 --> 00:08:03,180
até eu meio que acidentalmente
alcançar a directiva

154
00:08:03,180 --> 00:08:05,560
que se propõe atingir mais cedo.

155
00:08:05,560 --> 00:08:08,200
>> Mas nós sabemos de nossa
pseudocódigo anterior de que há

156
00:08:08,200 --> 00:08:11,870
esta noção em programação de looping,
fazendo algo novo e de novo.

157
00:08:11,870 --> 00:08:14,888
E então eu vi que um monte de você
alcançou peça o quebra-cabeça?

158
00:08:14,888 --> 00:08:17,870

159
00:08:17,870 --> 00:08:18,730
Repita até.

160
00:08:18,730 --> 00:08:21,400
Para que pudéssemos fazer algo
como repetir até.

161
00:08:21,400 --> 00:08:23,760
E o que você repetir até que exatamente?

162
00:08:23,760 --> 00:08:27,720

163
00:08:27,720 --> 00:08:28,540
>> ESTÁ BEM.

164
00:08:28,540 --> 00:08:31,974
E deixe-me ir com um que é
um pouco mais simples para apenas um momento.

165
00:08:31,974 --> 00:08:33,140
Deixe-me ir em frente e fazer isso.

166
00:08:33,140 --> 00:08:35,559
Observe que, como você pode ter
descoberto sob controle,

167
00:08:35,559 --> 00:08:38,409
existe este bloco de repetição, que
Não parece que ele é tão grande.

168
00:08:38,409 --> 00:08:41,039
Não há muito espaço no
entre essas duas linhas amarelas.

169
00:08:41,039 --> 00:08:43,539
Mas, como alguns de vocês podem ter
notado, se você arrastar e soltar,

170
00:08:43,539 --> 00:08:45,150
notar como cresce para preencher a forma.

171
00:08:45,150 --> 00:08:46,274
>> E você ainda pode empinar mais.

172
00:08:46,274 --> 00:08:48,670
Ele só vai continuar a crescer, se
você arrastar e pairar sobre ele.

173
00:08:48,670 --> 00:08:51,110
E eu não sei o que é
melhor aqui, então vamos

174
00:08:51,110 --> 00:08:54,760
me, pelo menos, repetir cinco vezes, por
exemplo, e depois voltar para o palco

175
00:08:54,760 --> 00:08:56,720
e clique na bandeira verde.

176
00:08:56,720 --> 00:08:59,110
E agora percebe que não é bem lá.

177
00:08:59,110 --> 00:09:02,400
>> Agora alguns de vocês proposto,
Victoria fez, repita 10 vezes.

178
00:09:02,400 --> 00:09:05,140
E que geralmente faz
levá-lo todo o caminho,

179
00:09:05,140 --> 00:09:10,510
Mas não seria haver uma mais robusta
maneira do que arbitrariamente descobrir

180
00:09:10,510 --> 00:09:12,640
quantos movimentos para fazer?

181
00:09:12,640 --> 00:09:17,680
O que poderia ser um bloco melhor
do que repetir 10 vezes ser?

182
00:09:17,680 --> 00:09:20,380
>> Sim, então porque não fazer algo para sempre?

183
00:09:20,380 --> 00:09:24,390
E agora deixe-me mover esta parte do enigma
lá dentro e livrar-se de um presente.

184
00:09:24,390 --> 00:09:28,300
Agora note, não importa onde Raspadinha
começa, ele vai para a borda.

185
00:09:28,300 --> 00:09:30,700
E felizmente MIT,
que faz scratch, apenas

186
00:09:30,700 --> 00:09:33,190
garante que ele nunca
desaparece completamente.

187
00:09:33,190 --> 00:09:35,360
Você pode sempre agarrar sua cauda.

188
00:09:35,360 --> 00:09:37,680
>> E apenas intuitivamente,
por que ele continua se movendo?

189
00:09:37,680 --> 00:09:38,892
O que está acontecendo aqui?

190
00:09:38,892 --> 00:09:41,440

191
00:09:41,440 --> 00:09:43,824
Ele parece ter parado, mas
em seguida, se eu pegar e arrastar

192
00:09:43,824 --> 00:09:45,240
ele continua querendo ir para lá.

193
00:09:45,240 --> 00:09:46,123
Por que é que?

194
00:09:46,123 --> 00:09:51,610

195
00:09:51,610 --> 00:09:54,360
Verdadeiramente, um computador é, literalmente,
vai fazer o que você diga a ele para fazer.

196
00:09:54,360 --> 00:09:58,380
Então, se você disse isso antes fazer o
coisa seguinte para sempre, mover 10 passos,

197
00:09:58,380 --> 00:10:01,860
ele vai continuar e vai
até que eu bati o sinal vermelho

198
00:10:01,860 --> 00:10:04,620
e parar o programa completamente.

199
00:10:04,620 --> 00:10:06,610
>> Assim, mesmo se você não fez
fazer isso, como eu poderia

200
00:10:06,610 --> 00:10:09,510
fazer mover mais rápido do risco
do outro lado da tela?

201
00:10:09,510 --> 00:10:12,060

202
00:10:12,060 --> 00:10:13,280
Mais passos, certo?

203
00:10:13,280 --> 00:10:15,710
Então, em vez de fazer 10
de cada vez, por quê nós não

204
00:10:15,710 --> 00:10:20,100
vá em frente e mudar isso a--
o que você propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Então agora eu vou clique no verde
bandeira, e, na verdade, ele vai muito rápido.

206
00:10:24,410 --> 00:10:27,180
>> E isso, claro, é apenas
uma manifestação de animação.

207
00:10:27,180 --> 00:10:28,060
O que é animação?

208
00:10:28,060 --> 00:10:33,090
É apenas mostrando-lhe a um ser humano
grupo inteiro de imagens fixas, realmente,

209
00:10:33,090 --> 00:10:34,160
muito, muito rápido.

210
00:10:34,160 --> 00:10:36,500
E por isso, se nós estamos apenas dizendo
-lo a se mover mais passos,

211
00:10:36,500 --> 00:10:39,750
nós apenas estamos tendo o efeito ser
mudança onde ele está na tela

212
00:10:39,750 --> 00:10:42,900
toda a unidade mais rapidamente por de tempo.

213
00:10:42,900 --> 00:10:46,454
>> Agora, o próximo desafio que propus
era tê-lo saltar para fora da borda.

214
00:10:46,454 --> 00:10:49,120
E sem saber o quebra-cabeça
peças exist-- porque é fina

215
00:10:49,120 --> 00:10:53,030
se você não chegar ao
etapa do que challenge--

216
00:10:53,030 --> 00:10:54,280
você quer fazer intuitivamente?

217
00:10:54,280 --> 00:10:58,030
Como poderíamos tê-lo saltar para trás e
diante, entre a esquerda e direita?

218
00:10:58,030 --> 00:11:02,630

219
00:11:02,630 --> 00:11:03,810
>> Sim.

220
00:11:03,810 --> 00:11:05,680
Então, precisamos de algum tipo
da condição, e nós

221
00:11:05,680 --> 00:11:09,710
parecem ter condicionais, por assim
falar, sob a categoria de controle.

222
00:11:09,710 --> 00:11:14,110
Qual destes blocos
nós provavelmente quer?

223
00:11:14,110 --> 00:11:15,200
Sim, talvez "se, então."

224
00:11:15,200 --> 00:11:18,780
Então, observe que, entre os blocos amarelo
temos aqui, não é este "se"

225
00:11:18,780 --> 00:11:23,920
ou este "if, else" bloco que vai
nos permitem tomar uma decisão para fazer isso

226
00:11:23,920 --> 00:11:25,000
ou para fazer isso.

227
00:11:25,000 --> 00:11:27,380
E você ainda pode inserí-las
para fazer várias coisas.

228
00:11:27,380 --> 00:11:34,910
Ou se você não tenha ido ainda aqui,
vá em frente para a categoria Sensing

229
00:11:34,910 --> 00:11:39,612
e- vamos ver se ele está aqui.

230
00:11:39,612 --> 00:11:43,050

231
00:11:43,050 --> 00:11:52,050
>> Então, o bloco pode ser útil aqui
para detectar se ele está fora do palco?

232
00:11:52,050 --> 00:11:56,740
Sim, notar que alguns desses blocos
pode ser parametrizada, por assim dizer.

233
00:11:56,740 --> 00:12:00,706
Eles podem ser tipo de personalização, não
ao contrário do HTML ontem com atributos,

234
00:12:00,706 --> 00:12:03,330
onde esses atributos tipo de
personalizar o comportamento de uma etiqueta.

235
00:12:03,330 --> 00:12:08,880
Da mesma forma aqui, posso agarrar esta comovente
bloco e mudança e fazer a pergunta,

236
00:12:08,880 --> 00:12:11,500
você está tocando o mouse
ponteiro como o cursor

237
00:12:11,500 --> 00:12:13,250
ou você está tocando a borda?

238
00:12:13,250 --> 00:12:15,210
>> Então deixe-me entrar e fazer isso.

239
00:12:15,210 --> 00:12:18,130
Eu estou indo para afastar por um momento.

240
00:12:18,130 --> 00:12:21,320
Deixe-me agarrar esta parte do enigma
aqui, este enigma isso,

241
00:12:21,320 --> 00:12:24,570
e eu vou Desordem
-los por apenas um momento.

242
00:12:24,570 --> 00:12:27,620
Eu estou indo para mover este,
alterar esta a beira tocar,

243
00:12:27,620 --> 00:12:38,590
e eu vou fazer isso de movimento.

244
00:12:38,590 --> 00:12:40,490
Então, aqui estão alguns ingredientes.

245
00:12:40,490 --> 00:12:42,570
Eu acho que eu tenho tudo o que quero.

246
00:12:42,570 --> 00:12:47,710
>> Será que alguém gostaria de propor como eu
pode conectar estes talvez de cima para baixo

247
00:12:47,710 --> 00:12:52,020
a fim de resolver o problema de ter
Zero direita para a esquerda para a direita para mover

248
00:12:52,020 --> 00:12:57,020
esquerda para a direita para a esquerda, cada um
tempo apenas saltar fora da parede?

249
00:12:57,020 --> 00:12:58,050
O que eu quero fazer?

250
00:12:58,050 --> 00:13:01,097
Qual bloco deve me conectar à
"Flag quando verde clicou pela primeira vez"?

251
00:13:01,097 --> 00:13:04,060

252
00:13:04,060 --> 00:13:06,200
>> OK, então vamos começar com o "para sempre".

253
00:13:06,200 --> 00:13:07,170
O que vai dentro em seguida?

254
00:13:07,170 --> 00:13:10,290
Alguém.

255
00:13:10,290 --> 00:13:11,850
OK, mova etapas.

256
00:13:11,850 --> 00:13:12,350
Tudo certo.

257
00:13:12,350 --> 00:13:14,470
Então o que?

258
00:13:14,470 --> 00:13:15,120
Então a se.

259
00:13:15,120 --> 00:13:17,720
E note, mesmo que pareça
imprensados ​​junto com força,

260
00:13:17,720 --> 00:13:19,500
ela só vai crescer para preencher.

261
00:13:19,500 --> 00:13:21,500
Ele vai apenas no salto, onde eu quero.

262
00:13:21,500 --> 00:13:25,920
>> E o que eu pus entre
if e então?

263
00:13:25,920 --> 00:13:27,180
Provavelmente "se tocar borda."

264
00:13:27,180 --> 00:13:31,800
E observem, novamente, é muito grande
para ele, mas ele vai crescer para preencher.

265
00:13:31,800 --> 00:13:35,002
E, em seguida, virar 15 graus?

266
00:13:35,002 --> 00:13:35,710
Quantos graus?

267
00:13:35,710 --> 00:13:38,800

268
00:13:38,800 --> 00:13:41,196
Sim, então 180 girará
me a toda a volta.

269
00:13:41,196 --> 00:13:42,570
Então vamos ver se eu tenho esse direito.

270
00:13:42,570 --> 00:13:43,930
Deixe-me afastar.

271
00:13:43,930 --> 00:13:45,130
>> Deixe-me arrastar zero para cima.

272
00:13:45,130 --> 00:13:50,030
Então, ele é um pouco distorcida
agora, mas isso é bom.

273
00:13:50,030 --> 00:13:52,231
Como posso repor-lo facilmente?

274
00:13:52,231 --> 00:13:59,879

275
00:13:59,879 --> 00:14:01,045
Eu estou indo para enganar um pouco.

276
00:14:01,045 --> 00:14:04,074

277
00:14:04,074 --> 00:14:05,990
Então, eu estou adicionando outro
bloco, só para ficar claro.

278
00:14:05,990 --> 00:14:08,424
Eu quero que ele aponta 90 graus
à direita por padrão,

279
00:14:08,424 --> 00:14:10,840
então eu só vou dizer a ele
para fazer isso por meio de programação.

280
00:14:10,840 --> 00:14:11,632
E aqui vamos nós.

281
00:14:11,632 --> 00:14:14,740

282
00:14:14,740 --> 00:14:15,740
Nós parecemos ter feito isso.

283
00:14:15,740 --> 00:14:19,980
É um pouco estranho, porque
ele está andando de cabeça para baixo.

284
00:14:19,980 --> 00:14:21,250
Vamos chamar esse um bug.

285
00:14:21,250 --> 00:14:22,120
Isso é um erro.

286
00:14:22,120 --> 00:14:27,320
Um bug é um erro em um programa, um
erro lógico que eu, o ser humano, feito.

287
00:14:27,320 --> 00:14:28,985
Por que ele está indo de cabeça para baixo?

288
00:14:28,985 --> 00:14:33,560

289
00:14:33,560 --> 00:14:35,250
Será que MIT estragar ou eu?

290
00:14:35,250 --> 00:14:38,840

291
00:14:38,840 --> 00:14:42,550
>> Sim, quero dizer, não é MIT
falha. Eles me deram uma parte do enigma

292
00:14:42,550 --> 00:14:44,970
que diz que transformar alguns número de graus.

293
00:14:44,970 --> 00:14:47,672
E por sugestão de Victoria,
Eu estou girando 180 graus,

294
00:14:47,672 --> 00:14:48,880
que é a intuição certa.

295
00:14:48,880 --> 00:14:53,700
Mas transformar 180 graus literalmente
significa virar 180 graus,

296
00:14:53,700 --> 00:14:55,860
e isso não é realmente
o que eu quero, aparentemente.

297
00:14:55,860 --> 00:14:58,026
Porque pelo menos ele está em
este mundo bidimensional,

298
00:14:58,026 --> 00:15:00,740
de modo decisivo que realmente está acontecendo
para virar de cabeça para baixo.

299
00:15:00,740 --> 00:15:04,030
>> I provavelmente vai querer usar o bloco
em vez disso, com base no que você vê aqui?

300
00:15:04,030 --> 00:15:11,890

301
00:15:11,890 --> 00:15:14,790
Como podemos corrigir isso?

302
00:15:14,790 --> 00:15:18,380
É, por isso, poderia apontar
no sentido oposto.

303
00:15:18,380 --> 00:15:22,300
E, na verdade, mesmo que seja
não vai ser suficiente,

304
00:15:22,300 --> 00:15:26,410
porque só pode código rígido
a apontar para a esquerda ou para a direita.

305
00:15:26,410 --> 00:15:27,920
>> Você sabe o que poderíamos fazer?

306
00:15:27,920 --> 00:15:30,160
Parece que temos um
bloco de conveniência aqui.

307
00:15:30,160 --> 00:15:32,987
Se eu aumentar o zoom, ver
algo que gostamos aqui?

308
00:15:32,987 --> 00:15:36,120

309
00:15:36,120 --> 00:15:40,020
Portanto, parece que o MIT tem uma
abstração construída aqui.

310
00:15:40,020 --> 00:15:45,440
Este bloco parece ser equivalente
para que outros blocos, plural?

311
00:15:45,440 --> 00:15:49,510
>> Este bloco parece ser equivalente
a todo este trio de blocos

312
00:15:49,510 --> 00:15:50,880
que temos aqui.

313
00:15:50,880 --> 00:15:54,670
Então não é que eu posso simplificar a minha
programa por se livrar de tudo isso

314
00:15:54,670 --> 00:15:58,270
e basta colocar isso aqui.

315
00:15:58,270 --> 00:16:01,620
E agora ele ainda é um pouco
carrinho, e isso é bom para agora.

316
00:16:01,620 --> 00:16:03,370
Vamos deixar que seja.

317
00:16:03,370 --> 00:16:06,000
Mas meu programa é ainda
mais simples, e isso, também,

318
00:16:06,000 --> 00:16:09,060
seria representativa
de um objetivo em programming--

319
00:16:09,060 --> 00:16:13,430
é idealmente fazer o seu código como
simples, tão compacto quanto possível,

320
00:16:13,430 --> 00:16:15,650
enquanto continuam a ser tão
legível possível.

321
00:16:15,650 --> 00:16:20,310
Você não quer fazê-lo de modo sucinto
que é difícil de entender.

322
00:16:20,310 --> 00:16:22,826
>> Mas observe que eu substituído
três blocos com um,

323
00:16:22,826 --> 00:16:24,200
e isso é, sem dúvida, uma coisa boa.

324
00:16:24,200 --> 00:16:27,280
Eu abstraída a noção
de verificar se você está

325
00:16:27,280 --> 00:16:29,120
na borda com apenas um bloco.

326
00:16:29,120 --> 00:16:31,520
Agora podemos nos divertir com isso, na verdade.

327
00:16:31,520 --> 00:16:35,790
Isso não acrescentar muito
valor intelectual, mas valor lúdico.

328
00:16:35,790 --> 00:16:39,730
Eu estou indo para ir em frente
e pegar este som aqui.

329
00:16:39,730 --> 00:16:42,900

330
00:16:42,900 --> 00:16:46,420
Então deixe-me ir em frente, e deixe-me
parar o programa por um momento.

331
00:16:46,420 --> 00:16:52,070
Vou gravar o seguinte,
permitindo o acesso ao meu microfone.

332
00:16:52,070 --> 00:16:53,181
>> Aqui vamos nós.

333
00:16:53,181 --> 00:16:53,680
Ouch.

334
00:16:53,680 --> 00:16:58,710

335
00:16:58,710 --> 00:17:01,140
Vamos tentar isso novamente.

336
00:17:01,140 --> 00:17:02,279
Aqui vamos nós.

337
00:17:02,279 --> 00:17:03,570
OK, eu gravei a coisa errada.

338
00:17:03,570 --> 00:17:04,580
Aqui vamos nós.

339
00:17:04,580 --> 00:17:05,080
Ouch.

340
00:17:05,080 --> 00:17:07,910

341
00:17:07,910 --> 00:17:08,800
Ouch.

342
00:17:08,800 --> 00:17:09,300
Tudo certo.

343
00:17:09,300 --> 00:17:10,791
Agora eu preciso para se livrar dessa.

344
00:17:10,791 --> 00:17:11,290
Tudo certo.

345
00:17:11,290 --> 00:17:13,950
>> Então agora eu tenho um
gravação de apenas "ouch".

346
00:17:13,950 --> 00:17:18,040
Então agora eu estou indo para ir
em frente e chamar isso de "ai".

347
00:17:18,040 --> 00:17:20,270
Eu estou indo para voltar
para meus scripts, e agora

348
00:17:20,270 --> 00:17:25,460
aviso há este bloco que se chama
reproduzir o som "miau" ou reproduzir o som "ai".

349
00:17:25,460 --> 00:17:28,920
Eu estou indo para arrastar isso, e onde
devo colocar isso para efeito cômico?

350
00:17:28,920 --> 00:17:31,740

351
00:17:31,740 --> 00:17:37,860
É, por isso agora é uma espécie de
carrinho, porque agora este block--

352
00:17:37,860 --> 00:17:42,050
observe como esse "se na borda,
salto "é uma espécie de auto-contido.

353
00:17:42,050 --> 00:17:43,704
Então eu preciso consertar isso.

354
00:17:43,704 --> 00:17:44,870
Deixe-me ir em frente e fazer isso.

355
00:17:44,870 --> 00:17:48,630
Deixe-me se livrar dessa e voltar
para a nossa original, mais deliberada

356
00:17:48,630 --> 00:17:49,870
funcionalidade.

357
00:17:49,870 --> 00:18:01,080
Então, "se tocar borda, em seguida," Eu quero
a girar, como Victoria proposto,

358
00:18:01,080 --> 00:18:02,480
180 graus.

359
00:18:02,480 --> 00:18:05,497
E eu quero jogar
o som "ouch" lá?

360
00:18:05,497 --> 00:18:11,800

361
00:18:11,800 --> 00:18:15,580
>> Sim, notar que é fora
esse bloco amarelo.

362
00:18:15,580 --> 00:18:17,680
Então, isso também seria uma
bug, mas tenho notado isso.

363
00:18:17,680 --> 00:18:21,290
Então eu vou arrastá-lo até aqui,
e aviso agora é dentro do "se".

364
00:18:21,290 --> 00:18:24,250
Assim, o "se" é esse tipo
de como blot braço-like

365
00:18:24,250 --> 00:18:26,260
que só vai
fazer o que está dentro dela.

366
00:18:26,260 --> 00:18:30,216
Então agora se eu diminuir o zoom em
o risco de annoying--

367
00:18:30,216 --> 00:18:32,860

368
00:18:32,860 --> 00:18:36,470
>> COMPUTADOR: Ai, ai, ai.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: E
só vai durar para sempre.

370
00:18:39,910 --> 00:18:44,160
Agora é só para acelerar as coisas
aqui, deixe-me ir em frente e abrir-se,

371
00:18:44,160 --> 00:18:50,460
vamos dizer-- deixe-me ir para algum
do meu próprio material de classe.

372
00:18:50,460 --> 00:18:53,000

373
00:18:53,000 --> 00:19:00,220
E deixe-me abrir, vamos dizer, este
um feito por um dos nossos companheiros de ensino

374
00:19:00,220 --> 00:19:01,500
um par de anos atrás.

375
00:19:01,500 --> 00:19:04,732
Então, alguns de vocês podem recordar
este jogo de outros tempos,

376
00:19:04,732 --> 00:19:05,940
e é realmente notável.

377
00:19:05,940 --> 00:19:08,190
Mesmo que nós fizemos o
mais simples de programas de agora,

378
00:19:08,190 --> 00:19:09,980
vamos considerar o que isso
realmente parece.

379
00:19:09,980 --> 00:19:10,650
Deixe-me bateu jogar.

380
00:19:10,650 --> 00:19:14,210

381
00:19:14,210 --> 00:19:18,980
>> Então, neste jogo, temos um
rã, e utilizando a seta keys--

382
00:19:18,980 --> 00:19:23,340
ele toma passos maiores do que eu recorde--
Eu tenho controle sobre esse sapo.

383
00:19:23,340 --> 00:19:29,630
E o objetivo é atravessar a movimentada
estrada sem correr para os carros.

384
00:19:29,630 --> 00:19:34,735
E vamos see-- se eu ir até aqui, eu
tem que esperar por um registro para rolar.

385
00:19:34,735 --> 00:19:38,130

386
00:19:38,130 --> 00:19:39,274
Isto parece um bug.

387
00:19:39,274 --> 00:19:42,240

388
00:19:42,240 --> 00:19:43,495
Este é um tipo de bug.

389
00:19:43,495 --> 00:19:45,980

390
00:19:45,980 --> 00:19:46,480
Tudo certo.

391
00:19:46,480 --> 00:19:51,550
Eu estou neste aqui,
lá, e então você continua

392
00:19:51,550 --> 00:19:54,100
indo até você obter todas
as rãs para os lírios.

393
00:19:54,100 --> 00:19:55,920
Agora, isso pode parecer
tanto mais complexa,

394
00:19:55,920 --> 00:19:57,840
mas vamos tentar quebrar
este para baixo mentalmente

395
00:19:57,840 --> 00:20:00,040
e verbalmente em seus blocos componentes.

396
00:20:00,040 --> 00:20:03,910
Então, há provavelmente um quebra-cabeça
peça que nós não vimos ainda

397
00:20:03,910 --> 00:20:07,440
mas que está respondendo aos comandos das teclas,
a coisas que eu bati no teclado.

398
00:20:07,440 --> 00:20:11,660
>> Então, há provavelmente algum tipo de
bloco que diz, se a chave é igual a acima,

399
00:20:11,660 --> 00:20:15,965
em seguida, fazer algo com Scratch--
talvez movê-lo 10 etapas desta forma.

400
00:20:15,965 --> 00:20:20,240
Se tecla para baixo é pressionado, mover 10 passos
Desta forma, ou para a esquerda, mover 10 passos

401
00:20:20,240 --> 00:20:21,710
Desta forma, 10 passos que.

402
00:20:21,710 --> 00:20:23,644
Virei claramente o gato em um sapo.

403
00:20:23,644 --> 00:20:26,060
Então, isso é apenas onde o
traje, como chamadas de raspadinhas ele-- nós

404
00:20:26,060 --> 00:20:28,440
acabou de importar uma imagem do sapo.

405
00:20:28,440 --> 00:20:29,570
>> Mas o que mais está acontecendo?

406
00:20:29,570 --> 00:20:32,794
Que outras linhas de código,
o que as outras peças do puzzle

407
00:20:32,794 --> 00:20:35,460
fez Blake, o nosso ensino do companheiro,
utilizar neste programa, aparentemente?

408
00:20:35,460 --> 00:20:38,320

409
00:20:38,320 --> 00:20:42,730
O que está fazendo tudo move--
o que de programação construir?

410
00:20:42,730 --> 00:20:44,950
>> Movimento, de modo que o sure--
mover o bloco, com certeza.

411
00:20:44,950 --> 00:20:49,330
E o que é que o bloco movimento
Dentro, mais provável?

412
00:20:49,330 --> 00:20:52,850
Sim, algum tipo de loop, talvez um
sempre bloquear, talvez uma repetição block--

413
00:20:52,850 --> 00:20:54,070
repetir até que o bloco.

414
00:20:54,070 --> 00:20:57,330
E é isso que está a fazer os registros e
os lírios e tudo mais movimento

415
00:20:57,330 --> 00:20:57,990
vai e volta.

416
00:20:57,990 --> 00:21:00,270
É só acontecendo sem parar.

417
00:21:00,270 --> 00:21:03,180
>> Por que alguns dos carros
movendo mais rápido do que os outros?

418
00:21:03,180 --> 00:21:06,607
O que é diferente sobre esses programas?

419
00:21:06,607 --> 00:21:09,690
Sim, provavelmente alguns deles estão a tomar
mais passos de uma só vez e alguns deles

420
00:21:09,690 --> 00:21:10,690
menos etapas de uma só vez.

421
00:21:10,690 --> 00:21:14,670
E o efeito visual
é rápido contra lento.

422
00:21:14,670 --> 00:21:16,030
>> O que você acha que aconteceu?

423
00:21:16,030 --> 00:21:19,700
Quando eu tenho o meu sapo todo o caminho
do outro lado da rua e do rio

424
00:21:19,700 --> 00:21:23,560
na almofada de lírio, algo
digno de nota aconteceu.

425
00:21:23,560 --> 00:21:26,540
O que aconteceu assim que eu fiz isso?

426
00:21:26,540 --> 00:21:27,210
Parou.

427
00:21:27,210 --> 00:21:29,680
Aquele sapo parou, e
Eu tenho uma segunda rã.

428
00:21:29,680 --> 00:21:33,155
Então, o construto deve ser
usado lá, o recurso?

429
00:21:33,155 --> 00:21:36,020

430
00:21:36,020 --> 00:21:38,660
>> É, por isso há algum tipo de
"Se" condicionar-se lá, também.

431
00:21:38,660 --> 00:21:41,909
E acontece out-- não vimos isto--
mas há outros blocos em que há

432
00:21:41,909 --> 00:21:45,300
pode dizer que, se você está tocando
outra coisa na tela,

433
00:21:45,300 --> 00:21:47,720
se você está tocando a almofada de lírio ", então".

434
00:21:47,720 --> 00:21:50,810
E, em seguida, que é quando nós
fazer a segunda rã aparecer.

435
00:21:50,810 --> 00:21:54,969
Assim, mesmo que este jogo é certamente
muito antigo, embora à primeira vista

436
00:21:54,969 --> 00:21:58,010
há tanta coisa acontecendo Blake on-- e
não chicotear isto em dois minutos,

437
00:21:58,010 --> 00:22:00,390
provavelmente levou vários
horas para criar este jogo

438
00:22:00,390 --> 00:22:03,850
com base em sua memória ou vídeos
da versão de passado dele.

439
00:22:03,850 --> 00:22:07,940
Mas todas estas pequenas coisas
indo na tela de forma isolada

440
00:22:07,940 --> 00:22:11,550
resumem-se a estes muito simples
movimentos constructs-- ou declarações

441
00:22:11,550 --> 00:22:15,519
como já discutimos, loops e
condições, e é sobre isso.

442
00:22:15,519 --> 00:22:17,060
Há algumas outras características extravagantes.

443
00:22:17,060 --> 00:22:19,130
Alguns deles são puramente
estética ou acústico,

444
00:22:19,130 --> 00:22:20,964
como os sons Eu só jogou com.

445
00:22:20,964 --> 00:22:23,380
Mas para a maior parte, você
tem nesta língua, risco,

446
00:22:23,380 --> 00:22:25,350
todos da fundamental
blocos de construção que você

447
00:22:25,350 --> 00:22:29,280
têm em C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
e qualquer número de outras línguas.

449
00:22:32,960 --> 00:22:36,720
Qualquer dúvida sobre zero?

450
00:22:36,720 --> 00:22:37,220
Tudo certo.

451
00:22:37,220 --> 00:22:40,303
Portanto, não vamos mergulhar mais fundo para zero,
que você é bem-vindo neste fim de semana,

452
00:22:40,303 --> 00:22:42,860
especialmente se você tem filhos ou
sobrinhos e sobrinhas e tal,

453
00:22:42,860 --> 00:22:44,220
apresentá-los a zero.

454
00:22:44,220 --> 00:22:47,960
É realmente um maravilhosamente lúdica
ambiente, com, como os seus autores,

455
00:22:47,960 --> 00:22:49,120
tetos muito altos.

456
00:22:49,120 --> 00:22:51,670
Mesmo que começou com
muito detalhes de baixo nível,

457
00:22:51,670 --> 00:22:54,890
você pode realmente fazer um pouco
com ele, e este é talvez

458
00:22:54,890 --> 00:22:57,360
uma demonstração de exatamente isso.

459
00:22:57,360 --> 00:23:02,920
>> Mas vamos agora fazer a transição para um pouco mais
problemas sofisticados, se quiserem,

460
00:23:02,920 --> 00:23:05,870
conhecida como "busca" e
"Triagem", de modo mais geral.

461
00:23:05,870 --> 00:23:09,500
Tivemos este livro de telefone earlier-- aqui está
outra apenas para discussion--

462
00:23:09,500 --> 00:23:13,460
que fomos capazes de pesquisa
de forma mais eficiente porque

463
00:23:13,460 --> 00:23:15,270
de um pressuposto significativo.

464
00:23:15,270 --> 00:23:17,655
E só para ficar claro, o que
suposição era eu fazendo

465
00:23:17,655 --> 00:23:19,280
ao pesquisar através deste livro de telefone?

466
00:23:19,280 --> 00:23:23,342

467
00:23:23,342 --> 00:23:25,300
Que Mike Smith estava em
o livro de telefone, embora eu

468
00:23:25,300 --> 00:23:27,410
seria capaz de lidar
o cenário sem ele

469
00:23:27,410 --> 00:23:30,720
lá se eu simplesmente parou prematuramente.

470
00:23:30,720 --> 00:23:31,806
O livro é alfabética.

471
00:23:31,806 --> 00:23:33,930
E isso é muito generoso
suposição, porque isso

472
00:23:33,930 --> 00:23:36,580
significa someone-- Eu sou do tipo
de corte de um canto,

473
00:23:36,580 --> 00:23:40,580
como eu sou mais rápido porque alguém
outros fizeram um monte de trabalho duro para mim.

474
00:23:40,580 --> 00:23:43,120
>> Mas e se o telefone
livro foram não separados?

475
00:23:43,120 --> 00:23:47,050
Talvez Verizon tenho preguiça, só jogou
nomes e números de todos lá dentro

476
00:23:47,050 --> 00:23:50,120
talvez na ordem em que eles
assinou o serviço de telefone.

477
00:23:50,120 --> 00:23:54,570
E quanto tempo leva-me
para encontrar alguém como Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1.000 páginas de telefone book-- quantas
páginas que eu tenho que olhar através?

479
00:23:58,160 --> 00:23:58,905
>> Todos eles.

480
00:23:58,905 --> 00:24:00,030
Você é tipo de fora da sorte.

481
00:24:00,030 --> 00:24:03,420
Você literalmente tem que olhar para todos os
página se o livro de telefone é apenas

482
00:24:03,420 --> 00:24:04,450
ordenados aleatoriamente.

483
00:24:04,450 --> 00:24:06,910
Você pode ter sorte e encontrar Mike
na primeira página, porque ele

484
00:24:06,910 --> 00:24:08,826
foi o primeiro cliente
para solicitar o serviço de telefone.

485
00:24:08,826 --> 00:24:10,760
Mas ele pode ter sido a última também.

486
00:24:10,760 --> 00:24:12,500
>> Então ordem aleatória não é bom.

487
00:24:12,500 --> 00:24:16,750
Então, suponha que temos para ordenar a
livro de telefone ou nos dados gerais tipo

488
00:24:16,750 --> 00:24:18,520
que nos foi dado.

489
00:24:18,520 --> 00:24:19,440
Como podemos fazer isso?

490
00:24:19,440 --> 00:24:21,360
>> Bem, deixe-me tentar
um exemplo simples aqui.

491
00:24:21,360 --> 00:24:24,290
Deixe-me ir em frente e atirar uma
alguns números no quadro.

492
00:24:24,290 --> 00:24:35,480
Suponha que os números que temos são,
digamos, quatro, dois, um e três.

493
00:24:35,480 --> 00:24:38,390
E, Ben, classificar esses números para nós.

494
00:24:38,390 --> 00:24:39,017
>> Tudo bem.

495
00:24:39,017 --> 00:24:39,850
Como você fez isso?

496
00:24:39,850 --> 00:24:42,731

497
00:24:42,731 --> 00:24:43,230
Tudo certo.

498
00:24:43,230 --> 00:24:44,710
Então comece com a menor
valor e o mais alto,

499
00:24:44,710 --> 00:24:46,084
e isso é realmente boa intuição.

500
00:24:46,084 --> 00:24:48,080
E perceber que nós
os seres humanos são realmente muito

501
00:24:48,080 --> 00:24:49,913
bom em resolver problemas
assim, pelo menos,

502
00:24:49,913 --> 00:24:51,810
quando os dados é relativamente pequena.

503
00:24:51,810 --> 00:24:54,860
Assim que você começa a ter centenas
de números, milhares de números,

504
00:24:54,860 --> 00:24:58,440
milhões de números, Ben provavelmente
Não poderia fazê-lo assim tão rápido,

505
00:24:58,440 --> 00:25:00,620
assumindo que havia
lacunas nos números.

506
00:25:00,620 --> 00:25:03,450
Muito fácil de contar até um milhão
Caso contrário, basta demorado.

507
00:25:03,450 --> 00:25:07,150
>> Assim, o algoritmo soa
como Ben usado agora

508
00:25:07,150 --> 00:25:08,930
Foi busca pelo menor número.

509
00:25:08,930 --> 00:25:12,900
Assim, mesmo que nós, humanos, pode levar
em um monte de informações visuais,

510
00:25:12,900 --> 00:25:14,830
um computador é, na verdade
um pouco mais limitada.

511
00:25:14,830 --> 00:25:17,560
O computador só pode
olhar para um byte de cada vez

512
00:25:17,560 --> 00:25:20,770
ou talvez quatro bytes de cada vez--
nos dias de hoje talvez 8 bytes de cada vez--

513
00:25:20,770 --> 00:25:24,450
mas um número muito pequeno
de bytes num determinado momento.

514
00:25:24,450 --> 00:25:28,480
>> Então, uma vez que nós realmente temos
quatro valores separados aqui--

515
00:25:28,480 --> 00:25:32,440
e você pode pensar em Ben como tendo
antolhos se fosse um computador, tais

516
00:25:32,440 --> 00:25:36,450
que ele não pode ver qualquer outra coisa
de um número em uma vez--

517
00:25:36,450 --> 00:25:39,720
por isso, geralmente irá assumir, como em
Inglês, vamos ler da direita para a esquerda.

518
00:25:39,720 --> 00:25:42,870
Assim, o primeiro número Ben provavelmente parecia
em seguida, foi de quatro e muito rapidamente

519
00:25:42,870 --> 00:25:44,770
percebi que é um muito grande
number-- deixe-me continuar a procurar.

520
00:25:44,770 --> 00:25:45,357
>> Há dois.

521
00:25:45,357 --> 00:25:45,940
Espere um minuto.

522
00:25:45,940 --> 00:25:47,070
Dois é menor do que quatro.

523
00:25:47,070 --> 00:25:47,986
Eu vou lembrar.

524
00:25:47,986 --> 00:25:49,070
Dois é agora o menor.

525
00:25:49,070 --> 00:25:50,417
Agora um-- que é ainda melhor.

526
00:25:50,417 --> 00:25:51,250
Isso é ainda menor.

527
00:25:51,250 --> 00:25:54,000
Vou esquecer dois
e lembre-se um agora.

528
00:25:54,000 --> 00:25:56,550
>> E ele poderia parar de olhar?

529
00:25:56,550 --> 00:25:58,360
Bem, ele poderia baseadas
nesta informação,

530
00:25:58,360 --> 00:26:00,477
mas ele seria melhor pesquisa
o resto da lista.

531
00:26:00,477 --> 00:26:02,060
Porque o que se for zero estavam na lista?

532
00:26:02,060 --> 00:26:03,643
E se negativo alguém fosse na lista?

533
00:26:03,643 --> 00:26:07,720
Ele só sabe que a sua resposta
é correto se ele é exaustivamente

534
00:26:07,720 --> 00:26:08,729
verifiquei a lista inteira.

535
00:26:08,729 --> 00:26:10,020
Então olhamos para o resto deste.

536
00:26:10,020 --> 00:26:11,394
Three-- que era um desperdício de tempo.

537
00:26:11,394 --> 00:26:13,540
Demos azar, mas eu estava
Ainda correta de fazê-lo.

538
00:26:13,540 --> 00:26:17,857
E então agora ele presumivelmente
seleccionado o número mais pequeno

539
00:26:17,857 --> 00:26:20,440
e basta colocá-lo no início
da lista, como eu vou fazer aqui.

540
00:26:20,440 --> 00:26:23,480
Agora, o que você fez depois, embora
você não pensar nisso quase

541
00:26:23,480 --> 00:26:25,962
a este ponto?

542
00:26:25,962 --> 00:26:27,670
Repita o processo,
de modo algum tipo de loop.

543
00:26:27,670 --> 00:26:28,920
Há uma ideia familiar.

544
00:26:28,920 --> 00:26:30,860
Então aqui é quatro.

545
00:26:30,860 --> 00:26:32,110
Isso é atualmente o menor.

546
00:26:32,110 --> 00:26:33,220
Isso é um candidato.

547
00:26:33,220 --> 00:26:33,900
Não mais.

548
00:26:33,900 --> 00:26:34,770
Agora que eu vi dois.

549
00:26:34,770 --> 00:26:36,630
Esse é o próximo elemento mais pequeno.

550
00:26:36,630 --> 00:26:40,800
Three-- que não é menor, então,
agora Ben pode arrancar os dois.

551
00:26:40,800 --> 00:26:44,510
>> E agora nós repita o processo, e
de curso de três é puxado para fora em seguida.

552
00:26:44,510 --> 00:26:45,420
Repita o processo.

553
00:26:45,420 --> 00:26:46,990
Quatro é puxado para fora.

554
00:26:46,990 --> 00:26:50,140
E agora estamos fora dos números,
assim que a lista deve ser ordenada.

555
00:26:50,140 --> 00:26:51,960
>> E, de fato, este é um algoritmo formal.

556
00:26:51,960 --> 00:26:56,610
Um cientista da computação seria
chamam isso de "tipo de seleção,"

557
00:26:56,610 --> 00:27:00,880
A idéia é tipo um
listar iteratively-- novamente

558
00:27:00,880 --> 00:27:03,807
e novamente e novamente selecionando
o menor número.

559
00:27:03,807 --> 00:27:06,140
E o que é agradável sobre ele é
isso é tão danado intuitiva.

560
00:27:06,140 --> 00:27:07,470
É tão simples.

561
00:27:07,470 --> 00:27:11,100
E você pode repetir o mesmo
operação novamente e novamente.

562
00:27:11,100 --> 00:27:12,150
É simples.

563
00:27:12,150 --> 00:27:17,170
>> Neste caso, foi rápido, mas
quanto tempo faz exame realmente?

564
00:27:17,170 --> 00:27:19,880
Vamos fazê-lo parecer e
sentir um pouco mais tedioso.

565
00:27:19,880 --> 00:27:24,150
Então, um, dois, três, quatro, cinco, seis,
sete, oito, nove, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- número arbitrário.

567
00:27:26,160 --> 00:27:28,780
Eu só queria mais isso
tempo do que apenas a quatro.

568
00:27:28,780 --> 00:27:30,780
Então, se eu tenho um todo
monte de números agora---lo

569
00:27:30,780 --> 00:27:32,420
não importa mesmo
o que é-- Vamos

570
00:27:32,420 --> 00:27:34,380
pensar sobre o que este
algoritmo é realmente como.

571
00:27:34,380 --> 00:27:35,857
>> Suponha que há números lá.

572
00:27:35,857 --> 00:27:38,190
Mais uma vez, não importa o que
eles são, mas eles são aleatórios.

573
00:27:38,190 --> 00:27:39,679
Estou aplicando o algoritmo de Ben.

574
00:27:39,679 --> 00:27:41,220
Eu preciso selecionar o menor número.

575
00:27:41,220 --> 00:27:41,761
O que eu faço?

576
00:27:41,761 --> 00:27:44,240
E eu vou fisicamente
fazê-lo desta vez para representá-lo.

577
00:27:44,240 --> 00:27:46,099
Olhando, olhando,
olhando, olhando, olhando.

578
00:27:46,099 --> 00:27:48,140
Só na hora que eu chegar a
o fim da lista pode

579
00:27:48,140 --> 00:27:51,230
Eu percebo a menor
número era dois neste momento.

580
00:27:51,230 --> 00:27:52,720
Não está na lista.

581
00:27:52,720 --> 00:27:54,400
Então, eu coloquei dois.

582
00:27:54,400 --> 00:27:55,590
>> O que devo fazer em seguida?

583
00:27:55,590 --> 00:27:58,600
Olhando, olhando, olhando, olhando.

584
00:27:58,600 --> 00:28:02,250
Agora eu encontrei o número sete, porque
há falhas nestes Números de

585
00:28:02,250 --> 00:28:03,300
mas apenas arbitrária.

586
00:28:03,300 --> 00:28:03,800
Tudo certo.

587
00:28:03,800 --> 00:28:06,030
Então agora eu posso colocar para baixo sete.

588
00:28:06,030 --> 00:28:08,860
Olhando olhando, olhando.

589
00:28:08,860 --> 00:28:11,030
>> Agora eu estou supondo,
claro, que não faz Ben

590
00:28:11,030 --> 00:28:14,780
tem RAM extra, extra
memória, porque, obviamente,

591
00:28:14,780 --> 00:28:16,080
Estou olhando para o mesmo número.

592
00:28:16,080 --> 00:28:18,246
Certamente eu poderia ter lembrado
todos esses números,

593
00:28:18,246 --> 00:28:19,930
e isso é absolutamente verdadeiro.

594
00:28:19,930 --> 00:28:22,610
Mas se Ben lembra tudo
dos números que viu,

595
00:28:22,610 --> 00:28:24,430
ele não tem feito realmente
progressos fundamentais

596
00:28:24,430 --> 00:28:26,170
porque ele já tem
a capacidade de pesquisar

597
00:28:26,170 --> 00:28:27,540
através dos números na mesa.

598
00:28:27,540 --> 00:28:29,373
Lembrando todas as
O números não ajudam,

599
00:28:29,373 --> 00:28:32,490
porque ele pode ainda como um computador
só olhar para, já dissemos, um número

600
00:28:32,490 --> 00:28:33,080
de uma vez.

601
00:28:33,080 --> 00:28:35,760
Portanto, não há nenhum tipo de fraude
lá que você pode aproveitar.

602
00:28:35,760 --> 00:28:39,170
>> Então, na realidade, como eu
continuar pesquisando a lista,

603
00:28:39,170 --> 00:28:44,200
Eu literalmente só tem que continuar
frente e para trás através dele, arrancando

604
00:28:44,200 --> 00:28:45,710
a próxima menor número.

605
00:28:45,710 --> 00:28:48,810
E como você pode tipo de inferir
dos meus movimentos parvos,

606
00:28:48,810 --> 00:28:50,860
isso só fica muito
tedioso muito rapidamente,

607
00:28:50,860 --> 00:28:54,850
e eu parecem estar indo para trás e
frente, para trás e para a frente um pouco.

608
00:28:54,850 --> 00:29:03,220
Agora, para ser justo, eu não tenho que ir
bem como, bem, vamos see-- para ser justo,

609
00:29:03,220 --> 00:29:06,310
Eu não tenho que caminhar bastante
como muitos passos de cada vez.

610
00:29:06,310 --> 00:29:09,200
Uma vez que, é claro, como I
selecionar números da lista,

611
00:29:09,200 --> 00:29:11,860
a lista restante está ficando mais curto.

612
00:29:11,860 --> 00:29:14,240
>> E assim vamos pensar sobre
quantos passos eu estou realmente

613
00:29:14,240 --> 00:29:16,010
traipsing através de cada vez.

614
00:29:16,010 --> 00:29:18,950
Na primeira situação
tivemos 16 números,

615
00:29:18,950 --> 00:29:22,210
e assim por maximally-- vamos apenas
fazer isso por um discussion--

616
00:29:22,210 --> 00:29:25,640
Eu tive que olhar através de 16
números para encontrar a menor.

617
00:29:25,640 --> 00:29:28,420
Mas uma vez eu arrancado
o menor número, como

618
00:29:28,420 --> 00:29:30,590
tempo durou a lista restante, é claro?

619
00:29:30,590 --> 00:29:31,420
Apenas 15.

620
00:29:31,420 --> 00:29:34,670
Então, quantos números fez Ben ou eu tenho
olhar através da segunda vez?

621
00:29:34,670 --> 00:29:36,832
15, só para ir e encontrar o menor.

622
00:29:36,832 --> 00:29:39,540
Mas agora, é claro, a lista é,
também, menor do que era antes.

623
00:29:39,540 --> 00:29:42,540
Então, como muitos passos fez I
tem que tomar a próxima vez?

624
00:29:42,540 --> 00:29:49,970
14 e depois 13 e depois 12, além de ponto,
ponto, ponto, até que eu estou à esquerda com apenas um.

625
00:29:49,970 --> 00:29:53,146
Portanto, agora um cientista da computação seria
perguntar, bem, o que faz que todos iguais?

626
00:29:53,146 --> 00:29:55,770
Na verdade, é igual a algum concreto
número que certamente poderíamos

627
00:29:55,770 --> 00:30:00,490
fazer aritmeticamente, mas queremos falar
sobre a eficiência de algoritmos

628
00:30:00,490 --> 00:30:04,940
um pouco mais como uma fórmula,
independente de quanto tempo a lista é.

629
00:30:04,940 --> 00:30:06,240
>> E assim que você sabe o quê?

630
00:30:06,240 --> 00:30:09,860
Este é 16, mas como eu disse antes,
vamos chamar o tamanho do problema

631
00:30:09,860 --> 00:30:10,970
n, onde n é um número.

632
00:30:10,970 --> 00:30:13,220
Talvez seja 16, talvez seja
três, talvez seja um milhão.

633
00:30:13,220 --> 00:30:13,761
Eu não sei.

634
00:30:13,761 --> 00:30:14,390
Eu não me importo.

635
00:30:14,390 --> 00:30:16,520
O que eu realmente quero é
uma fórmula que eu puder

636
00:30:16,520 --> 00:30:19,420
usar para comparar este algoritmo
contra outros algoritmos

637
00:30:19,420 --> 00:30:22,350
que alguém pode reclamar
são melhores ou piores.

638
00:30:22,350 --> 00:30:25,430
>> Assim, ao que parece, e só eu
sei que isto da escola primária,

639
00:30:25,430 --> 00:30:34,790
que isso realmente funciona para o mesmo
coisa que n mais de n mais um sobre dois.

640
00:30:34,790 --> 00:30:40,020
E isso acontece para igualar, de
Naturalmente, n ao quadrado mais n mais de dois.

641
00:30:40,020 --> 00:30:43,250
Então, se eu queria uma fórmula
por quantos passos

642
00:30:43,250 --> 00:30:46,330
estavam envolvidos em olhar para todos
desses números novo e de novo

643
00:30:46,330 --> 00:30:52,681
e de novo e de novo, eu diria
é n ao quadrado mais n mais de dois.

644
00:30:52,681 --> 00:30:53,430
Mas você sabe o que?

645
00:30:53,430 --> 00:30:54,500
Isso só parece confuso.

646
00:30:54,500 --> 00:30:56,470
Eu realmente quero um
sentido geral das coisas.

647
00:30:56,470 --> 00:30:58,810
E você pode se lembrar de
ensino médio que não

648
00:30:58,810 --> 00:31:00,660
é a noção de termo de maior ordem.

649
00:31:00,660 --> 00:31:05,300
Qual destes termos, a n
quadrado, a N, ou a meia,

650
00:31:05,300 --> 00:31:07,550
tem o maior impacto ao longo do tempo?

651
00:31:07,550 --> 00:31:11,920
O maior n recebe, que
destes assuntos mais?

652
00:31:11,920 --> 00:31:15,560
>> Em outras palavras, se eu ligar
em um milhão, n ao quadrado

653
00:31:15,560 --> 00:31:17,900
vai ser mais provável
o fator dominante,

654
00:31:17,900 --> 00:31:21,670
Uma vez que um milhão de vezes
em si é muito maior

655
00:31:21,670 --> 00:31:23,682
do que mais um adicional milhões.

656
00:31:23,682 --> 00:31:24,390
Então você sabe o quê?

657
00:31:24,390 --> 00:31:27,305
Este é um tal danado grande
número se você quadrado de um número.

658
00:31:27,305 --> 00:31:28,430
Isso realmente não importa.

659
00:31:28,430 --> 00:31:30,596
Nós só vamos cruz que
fora e esquecê-la.

660
00:31:30,596 --> 00:31:34,250
E assim um cientista da computação diria
que a eficiência deste algoritmo

661
00:31:34,250 --> 00:31:37,850
é da ordem de n ao quadrado
Quero dizer realmente uma aproximação.

662
00:31:37,850 --> 00:31:40,810
É uma espécie de cerca de n ao quadrado.

663
00:31:40,810 --> 00:31:44,130
Ao longo do tempo, a maior
e maior n recebe, este

664
00:31:44,130 --> 00:31:47,610
é uma boa estimativa para o que o
a eficiência ou a falta de eficiência

665
00:31:47,610 --> 00:31:49,400
deste algoritmo é realmente.

666
00:31:49,400 --> 00:31:52,040
E eu derivar que, é claro,
de realmente fazer a matemática.

667
00:31:52,040 --> 00:31:54,040
Mas agora eu só estou acenando
minhas mãos, porque eu só

668
00:31:54,040 --> 00:31:55,790
quer um sentido geral deste algoritmo.

669
00:31:55,790 --> 00:31:58,850
>> Então, usando a mesma lógica, entretanto,
vamos considerar outro algoritmo

670
00:31:58,850 --> 00:32:01,162
já olhou at-- busca linear.

671
00:32:01,162 --> 00:32:02,870
Quando eu estava procurando
para o telefone book--

672
00:32:02,870 --> 00:32:05,980
não classificando-o, procurando
através do telefone book--

673
00:32:05,980 --> 00:32:09,197
mantivemos dizendo que era
1.000 passos, ou 500 passos.

674
00:32:09,197 --> 00:32:10,280
Mas vamos generalizar isso.

675
00:32:10,280 --> 00:32:12,860
Se há n páginas
o livro de telefone, o que é

676
00:32:12,860 --> 00:32:17,250
o tempo de execução ou o
eficiência da pesquisa linear?

677
00:32:17,250 --> 00:32:19,750
É da ordem de
quantos passos para encontrar

678
00:32:19,750 --> 00:32:24,210
Mike Smith usando a pesquisa linear, o
primeiro algoritmo, ou mesmo o segundo?

679
00:32:24,210 --> 00:32:27,240

680
00:32:27,240 --> 00:32:31,710
>> No pior dos casos, o Mike
é no final do livro.

681
00:32:31,710 --> 00:32:35,590
Então, se o livro de telefone tem 1.000 páginas,
dissemos última vez, no pior caso,

682
00:32:35,590 --> 00:32:38,380
isso pode levar mais ou menos como
muitas páginas para encontrar Mike?

683
00:32:38,380 --> 00:32:38,990
Como 1000.

684
00:32:38,990 --> 00:32:39,830
É um limite superior.

685
00:32:39,830 --> 00:32:41,790
É uma pior situação possível.

686
00:32:41,790 --> 00:32:44,410
Mas, novamente, nós estamos nos movendo para longe
a partir de números como 1.000 agora.

687
00:32:44,410 --> 00:32:45,730
É apenas n.

688
00:32:45,730 --> 00:32:47,470
>> Então, qual é a conclusão lógica?

689
00:32:47,470 --> 00:32:50,210
Encontrar Mike em um telefone
livro que tem n páginas

690
00:32:50,210 --> 00:32:55,280
pode levar, no pior caso,
quantos passos na ordem de n?

691
00:32:55,280 --> 00:32:58,110
E, de fato um computador
cientista diria

692
00:32:58,110 --> 00:33:02,340
que o tempo de execução, ou o
o desempenho ou a eficiência

693
00:33:02,340 --> 00:33:07,470
ou ineficiência, de um algoritmo como
uma pesquisa linear está na ordem de n.

694
00:33:07,470 --> 00:33:10,010
E podemos aplicar o mesmo
lógica de atravessar algo fora

695
00:33:10,010 --> 00:33:13,170
como eu fiz com o segundo
algoritmo que tivemos com o livro de telefone,

696
00:33:13,170 --> 00:33:16,040
onde fomos duas páginas de cada vez.

697
00:33:16,040 --> 00:33:20,120
>> Então 1.000 página do livro de telefone pode
nos levar 500 páginas voltas, mais um

698
00:33:20,120 --> 00:33:21,910
se dobrar um pouco para trás.

699
00:33:21,910 --> 00:33:26,590
Portanto, se um livro de telefone tem n páginas, mas
nós estamos fazendo duas páginas por vez,

700
00:33:26,590 --> 00:33:28,900
que é aproximadamente o que?

701
00:33:28,900 --> 00:33:33,190
N ao longo de dois, de modo que é como n mais de dois.

702
00:33:33,190 --> 00:33:38,490
Mas eu fiz o pedido de um
há pouco que n ao longo dois--

703
00:33:38,490 --> 00:33:41,060
isso é meio o mesmo que apenas n.

704
00:33:41,060 --> 00:33:44,050
É apenas um fator constante,
cientistas da computação diria.

705
00:33:44,050 --> 00:33:45,970
Vamos apenas focar
as variáveis, realmente--

706
00:33:45,970 --> 00:33:47,780
os maiores variáveis ​​na equação.

707
00:33:47,780 --> 00:33:52,530
>> pesquisa de modo linear, seja feito um
página de cada vez ou duas páginas por vez,

708
00:33:52,530 --> 00:33:54,810
é uma espécie de fundamentalmente o mesmo.

709
00:33:54,810 --> 00:33:56,880
Ainda é da ordem de n.

710
00:33:56,880 --> 00:34:01,930
Mas eu reivindicado com a minha foto anterior
que o terceiro algoritmo não foi

711
00:34:01,930 --> 00:34:02,480
linear.

712
00:34:02,480 --> 00:34:03,605
Não era uma linha reta.

713
00:34:03,605 --> 00:34:08,659
Foi que linha curva, e o
fórmula algébrica havia o que?

714
00:34:08,659 --> 00:34:11,812
Log de n-- tão log base dois de n.

715
00:34:11,812 --> 00:34:14,520
E não temos de ir para muito
muitos detalhes sobre logaritmos de hoje,

716
00:34:14,520 --> 00:34:17,394
mas a maioria dos cientistas da computação não iria
mesmo dizer-lhe qual é a base.

717
00:34:17,394 --> 00:34:20,639
Porque é tudo apenas
fatores constantes, por assim dizer,

718
00:34:20,639 --> 00:34:22,659
apenas pequenas diferenças numéricas.

719
00:34:22,659 --> 00:34:31,179
E assim esta seria uma muito comum
caminho para computador particular formais

720
00:34:31,179 --> 00:34:33,949
cientistas uma placa ou
programadores em um quadro branco

721
00:34:33,949 --> 00:34:36,889
na verdade, argumentando que
algoritmo que usariam

722
00:34:36,889 --> 00:34:39,500
ou que a eficiência
de seu algoritmo é.

723
00:34:39,500 --> 00:34:42,960
>> E isso não é necessariamente algo
você discute em qualquer grande detalhe,

724
00:34:42,960 --> 00:34:47,889
mas um bom programador é alguém
que tem uma base sólida, formal.

725
00:34:47,889 --> 00:34:50,120
Ele é capaz de falar com
-lo neste tipo de forma

726
00:34:50,120 --> 00:34:53,350
e realmente fazer
argumentos qualitativos como

727
00:34:53,350 --> 00:34:56,870
a razão pela qual um algoritmo ou
um pedaço de software

728
00:34:56,870 --> 00:35:00,165
é superior, de alguma forma para outra.

729
00:35:00,165 --> 00:35:02,540
Porque você poderia certamente
basta executar o programa de uma pessoa

730
00:35:02,540 --> 00:35:04,980
e contar o número de segundos
é preciso para classificar alguns números,

731
00:35:04,980 --> 00:35:06,710
e você pode executar alguns
O programa de outra pessoa

732
00:35:06,710 --> 00:35:08,418
e contar o número
de segundos que leva.

733
00:35:08,418 --> 00:35:12,840
Mas esta é uma forma mais geral, que
você pode usar para analisar algoritmos,

734
00:35:12,840 --> 00:35:15,520
se quiserem, apenas
de papel ou apenas verbalmente.

735
00:35:15,520 --> 00:35:18,430
Sem mesmo executá-lo, sem
mesmo tentando entradas de amostra,

736
00:35:18,430 --> 00:35:20,180
você pode apenas raciocinar com ele.

737
00:35:20,180 --> 00:35:24,670
E assim, com a contratação de um desenvolvedor ou se
tendo-lhe espécie de discutir com você

738
00:35:24,670 --> 00:35:28,460
porque seu algoritmo, seu segredo
molho para pesquisar bilhões

739
00:35:28,460 --> 00:35:30,580
de páginas da web para o seu
empresa é melhor, estes

740
00:35:30,580 --> 00:35:33,302
são os tipos de argumentos que
deveria idealmente ser capaz de fazer.

741
00:35:33,302 --> 00:35:35,010
Ou, pelo menos, estes são
os tipos de coisas

742
00:35:35,010 --> 00:35:40,211
que viria em discussão, na
menos em uma discussão muito formal.

743
00:35:40,211 --> 00:35:40,710
Tudo certo.

744
00:35:40,710 --> 00:35:44,400
Então Ben propôs algo
chamado de seleção de classificação.

745
00:35:44,400 --> 00:35:48,200
Mas eu vou propor que há
outras maneiras de fazer isso, também.

746
00:35:48,200 --> 00:35:50,400
O que eu não gosto muito
sobre o algoritmo de Ben

747
00:35:50,400 --> 00:35:54,400
é que ele continuou andando, ou
tendo-me andar, e para trás

748
00:35:54,400 --> 00:35:56,930
e de trás e para frente e para trás e para frente.

749
00:35:56,930 --> 00:36:04,130
E se em vez eu fosse fazer
algo como esses números aqui

750
00:36:04,130 --> 00:36:08,200
e eu fosse apenas para lidar com cada
número por sua vez, como eu estou dado?

751
00:36:08,200 --> 00:36:10,780
>> Em outras palavras, é aqui
minha lista de números.

752
00:36:10,780 --> 00:36:12,944
Quatro, um, três, dois.

753
00:36:12,944 --> 00:36:14,360
E eu vou fazer o seguinte.

754
00:36:14,360 --> 00:36:17,230
Eu estou indo para inserir os números
onde eles pertencem, em vez

755
00:36:17,230 --> 00:36:18,980
do que selecionando-os um de cada vez.

756
00:36:18,980 --> 00:36:20,820
Em outras palavras, aqui é o número quatro.

757
00:36:20,820 --> 00:36:22,430
>> Aqui está a minha lista original.

758
00:36:22,430 --> 00:36:25,290
E eu vou manter
essencialmente uma nova lista aqui.

759
00:36:25,290 --> 00:36:26,710
Portanto, esta é a lista de idade.

760
00:36:26,710 --> 00:36:28,560
Esta é a nova lista.

761
00:36:28,560 --> 00:36:30,220
Eu vejo o número quatro em primeiro lugar.

762
00:36:30,220 --> 00:36:34,500
Minha nova lista é inicialmente vazio,
por isso é o caso trivialmente

763
00:36:34,500 --> 00:36:36,410
que quatro está agora a lista variada.

764
00:36:36,410 --> 00:36:39,560
Estou apenas tomando o número que eu sou dado,
e eu estou colocando isso na minha nova lista.

765
00:36:39,560 --> 00:36:41,460
>> É esta nova lista ordenada?

766
00:36:41,460 --> 00:36:41,990
Sim.

767
00:36:41,990 --> 00:36:45,090
É estúpido porque há apenas um
elemento, mas é absolutamente classificadas.

768
00:36:45,090 --> 00:36:46,390
Não há nada fora do lugar.

769
00:36:46,390 --> 00:36:49,290
É mais interessante, este algoritmo,
quando eu passar para a próxima etapa.

770
00:36:49,290 --> 00:36:50,550
>> Agora eu tenho um.

771
00:36:50,550 --> 00:36:55,430
Assim, uma, é claro, pertence ao
início ou no fim desta nova lista?

772
00:36:55,430 --> 00:36:56,360
O início.

773
00:36:56,360 --> 00:36:58,530
Então eu tenho que fazer algum trabalho agora.

774
00:36:58,530 --> 00:37:01,410
Fui tomar alguns
liberdades com o meu marcador

775
00:37:01,410 --> 00:37:03,120
por apenas desenhar coisas
onde eu quero que eles,

776
00:37:03,120 --> 00:37:05,320
mas isso não é realmente
preciso em um computador.

777
00:37:05,320 --> 00:37:08,530
Um computador, como se sabe, tem
RAM, ou memória de acesso aleatório,

778
00:37:08,530 --> 00:37:12,411
e isso é um byte e
outro byte e outro byte.

779
00:37:12,411 --> 00:37:14,910
E se você tem um gigabyte de
RAM, você tem um bilhão de bytes,

780
00:37:14,910 --> 00:37:16,680
mas eles estão fisicamente em um único local.

781
00:37:16,680 --> 00:37:19,540
Você não pode simplesmente mover coisas ao redor
desenhando-a no tabuleiro

782
00:37:19,540 --> 00:37:20,750
onde quiser.

783
00:37:20,750 --> 00:37:24,090
Então, se a minha nova lista tem
quatro locais na memória,

784
00:37:24,090 --> 00:37:27,480
Infelizmente a quatro é
já no lugar errado.

785
00:37:27,480 --> 00:37:30,410
>> Assim, para inserir o número um
Eu não posso simplesmente desenhá-lo aqui.

786
00:37:30,410 --> 00:37:31,901
Este local de memória não existe.

787
00:37:31,901 --> 00:37:35,150
Isso seria fazer batota, e eu tenho sido
batota pictoricamente por alguns minutos

788
00:37:35,150 --> 00:37:35,800
Aqui.

789
00:37:35,800 --> 00:37:40,950
Então, realmente, se eu quiser colocar um aqui,
Eu tenho que copiar temporariamente os quatro

790
00:37:40,950 --> 00:37:43,030
e depois colocar um lá.

791
00:37:43,030 --> 00:37:45,500
>> Isso é bom, isso é correto,
que é tecnicamente possível,

792
00:37:45,500 --> 00:37:48,410
mas percebe que é um trabalho extra.

793
00:37:48,410 --> 00:37:50,460
Eu não basta colocar o número no lugar.

794
00:37:50,460 --> 00:37:53,026
A primeira vez que teve que mover uma
número, em seguida, colocá-lo no lugar,

795
00:37:53,026 --> 00:37:54,650
então eu meio que duplicou a minha quantidade de trabalho.

796
00:37:54,650 --> 00:37:55,660
Portanto, manter isso em mente.

797
00:37:55,660 --> 00:37:57,120
>> Mas agora estou feito com este elemento.

798
00:37:57,120 --> 00:37:59,056
Agora eu quero pegar o número três.

799
00:37:59,056 --> 00:38:00,430
Onde, é claro, ele pertence?

800
00:38:00,430 --> 00:38:01,480
Entre.

801
00:38:01,480 --> 00:38:03,650
Eu não pode enganar mais
e só colocá-lo lá,

802
00:38:03,650 --> 00:38:06,770
porque, novamente, essa memória
é em locais físicos.

803
00:38:06,770 --> 00:38:10,900
Então eu tenho que copiar os quatro
e colocar os três aqui.

804
00:38:10,900 --> 00:38:11,550
Não é um grande negócio.

805
00:38:11,550 --> 00:38:14,610
É apenas uma etapa extra
novamente-- sente muito barato.

806
00:38:14,610 --> 00:38:16,445
>> Mas agora eu passo para os dois.

807
00:38:16,445 --> 00:38:17,820
Os dois, é claro, pertence aqui.

808
00:38:17,820 --> 00:38:20,990
Agora você começa a ver como
o trabalho pode acumular.

809
00:38:20,990 --> 00:38:23,520
Agora o que eu tenho que fazer?

810
00:38:23,520 --> 00:38:28,570
Sim, eu tenho que mover a quatro,
Eu, então, tem que copiar os três,

811
00:38:28,570 --> 00:38:31,200
e agora eu posso inserir os dois.

812
00:38:31,200 --> 00:38:34,460
E a captura com este
algoritmo, curiosamente,

813
00:38:34,460 --> 00:38:41,050
se que suponha que temos uma forma mais extrema
caso em que ele é, digamos oito, sete,

814
00:38:41,050 --> 00:38:45,150
seis, cinco, quatro, três, dois, um.

815
00:38:45,150 --> 00:38:49,450
Isto é, em muitos contextos,
o pior cenário,

816
00:38:49,450 --> 00:38:51,570
porque o danado
é, literalmente, para trás.

817
00:38:51,570 --> 00:38:53,670
>> Realmente não
afeta o algoritmo de Ben,

818
00:38:53,670 --> 00:38:55,940
porque na selecção de Ben
tipo que ele vai continuar

819
00:38:55,940 --> 00:38:58,359
indo e voltando pela lista.

820
00:38:58,359 --> 00:39:01,150
E porque ele estava sempre à procura
através de toda a lista restante,

821
00:39:01,150 --> 00:39:02,858
Não importa
em que os elementos são.

822
00:39:02,858 --> 00:39:05,630
Mas, neste caso, com a minha inserção
approach-- vamos tentar isso.

823
00:39:05,630 --> 00:39:08,616
>> Então, um, dois, três, quatro,
cinco, seis, sete, oito.

824
00:39:08,616 --> 00:39:11,630
Um dois três quatro,
cinco, seis, sete, oito.

825
00:39:11,630 --> 00:39:14,320
Vou tomar a oito,
e onde posso colocá-lo?

826
00:39:14,320 --> 00:39:17,260
Bem, no início da minha lista,
porque esta nova lista é ordenada.

827
00:39:17,260 --> 00:39:18,760
E eu atravessá-la fora.

828
00:39:18,760 --> 00:39:20,551
>> Onde devo colocar o sete?

829
00:39:20,551 --> 00:39:21,050
Danado.

830
00:39:21,050 --> 00:39:23,174
Ele precisa ir lá, então
Eu tenho que fazer alguma cópia.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
E agora a sete vai aqui.

833
00:39:28,480 --> 00:39:29,860
Agora eu passar para o seis.

834
00:39:29,860 --> 00:39:30,980
Agora é ainda mais trabalho.

835
00:39:30,980 --> 00:39:32,570
>> Oito tem que ir aqui.

836
00:39:32,570 --> 00:39:33,920
Sete tem de ir aqui.

837
00:39:33,920 --> 00:39:35,450
Agora, a seis pode ir aqui.

838
00:39:35,450 --> 00:39:37,950
Agora eu agarrar a cinco.

839
00:39:37,950 --> 00:39:40,560
Agora, a oito tem que ir
aqui, sete tem que ir aqui,

840
00:39:40,560 --> 00:39:43,650
seis tem que ir aqui, e
agora os cinco e repita.

841
00:39:43,650 --> 00:39:46,610
E eu estou muito bem
movendo-o constantemente.

842
00:39:46,610 --> 00:39:52,950
>> Assim, no final, este algorithm-- nós vamos
chamá-lo de inserção sort-- realmente

843
00:39:52,950 --> 00:39:55,020
tem um monte de trabalho, também.

844
00:39:55,020 --> 00:39:56,970
É apenas diferente
tipo de trabalho de Ben.

845
00:39:56,970 --> 00:40:00,090
O trabalho de Ben tinha-me ir
e para trás todo o tempo,

846
00:40:00,090 --> 00:40:03,510
selecionar o próximo menor
elemento novamente e novamente.

847
00:40:03,510 --> 00:40:06,660
Por isso, foi este tipo muito visual do trabalho.

848
00:40:06,660 --> 00:40:10,600
>> Este outro algoritmo que ainda é
correct-- ele vai começar o trabalho done--

849
00:40:10,600 --> 00:40:12,800
apenas muda a quantidade de trabalho.

850
00:40:12,800 --> 00:40:15,420
Parece que inicialmente você está
poupança, porque você está apenas

851
00:40:15,420 --> 00:40:19,190
lidar com cada elemento
na frente sem andar todo

852
00:40:19,190 --> 00:40:20,930
o caminho através da lista como Ben era.

853
00:40:20,930 --> 00:40:25,300
Mas o problema é, especialmente nestes
casos louco onde tudo está para trás,

854
00:40:25,300 --> 00:40:27,830
você é apenas um tipo de
adiando o trabalho duro

855
00:40:27,830 --> 00:40:30,360
até que você tem que corrigir seus erros.

856
00:40:30,360 --> 00:40:33,919
>> E por isso, se você pode imaginar este
oito e sete anos e seis e cinco

857
00:40:33,919 --> 00:40:36,710
e depois de quatro e três e dois
movendo seu caminho através da lista,

858
00:40:36,710 --> 00:40:39,060
temos apenas mudou o
tipo de trabalho que estamos fazendo.

859
00:40:39,060 --> 00:40:42,340
Em vez de fazê-lo no
início da minha iteração,

860
00:40:42,340 --> 00:40:45,250
Eu estou fazendo isso apenas na
fim de cada iteração.

861
00:40:45,250 --> 00:40:50,550
Assim, verifica-se que este algoritmo,
também, geralmente chamado de ordenação por inserção,

862
00:40:50,550 --> 00:40:52,190
é também da ordem de n ao quadrado.

863
00:40:52,190 --> 00:40:56,480
É realmente não é melhor,
não é melhor em tudo.

864
00:40:56,480 --> 00:41:00,810
>> No entanto, há uma terceira abordagem
Gostaria de encorajar-nos a considerar,

865
00:41:00,810 --> 00:41:02,970
que é esta.

866
00:41:02,970 --> 00:41:07,850
Então suponho minha lista, por simplicidade
mais uma vez, é de quatro, um, três,

867
00:41:07,850 --> 00:41:11,080
dois-- apenas quatro números.

868
00:41:11,080 --> 00:41:13,300
Ben teve boa intuição,
boa intuição humana

869
00:41:13,300 --> 00:41:16,340
antes, pelo que fixa o conjunto
listar eventually-- tipo de inserção.

870
00:41:16,340 --> 00:41:18,020
I persuadiu-nos junto.

871
00:41:18,020 --> 00:41:22,530
Mas vamos considerar o
maneira mais simples de corrigir esta lista.

872
00:41:22,530 --> 00:41:24,110
>> Esta lista não está ordenada.

873
00:41:24,110 --> 00:41:26,130
Por quê?

874
00:41:26,130 --> 00:41:31,920
Em Inglês, explicar por que
Na verdade não é classificada.

875
00:41:31,920 --> 00:41:33,400
O que significa a não ser ordenados?

876
00:41:33,400 --> 00:41:34,220
>> ESTUDANTE: Não é sequencial.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: Não sequencial.

878
00:41:34,990 --> 00:41:35,822
Me dê um exemplo.

879
00:41:35,822 --> 00:41:37,180
>> ALUNO: Coloque-as em ordem.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Dê-me um exemplo mais específico.

882
00:41:38,790 --> 00:41:39,832
>> ALUNO: ordem crescente.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Ordem não ascendente.

884
00:41:41,206 --> 00:41:42,100
Ser mais preciso.

885
00:41:42,100 --> 00:41:45,190
Eu não sei o que você quer dizer com ascendente.

886
00:41:45,190 --> 00:41:47,150
O que está errado?

887
00:41:47,150 --> 00:41:49,930
>> ALUNO: O menor da
números não está no primeiro espaço.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: menor número de
não no primeiro espaço.

889
00:41:51,140 --> 00:41:52,120
Seja mais específico.

890
00:41:52,120 --> 00:41:55,000
Eu estou começando a pegar.

891
00:41:55,000 --> 00:41:59,470
Nós estamos contando, mas
o que está fora de ordem aqui?

892
00:41:59,470 --> 00:42:00,707
>> ALUNO: seqüência numérica.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: seqüência numérica.

894
00:42:02,040 --> 00:42:04,248
tipo de todos de manutenção
isso aqui-- nível muito elevado.

895
00:42:04,248 --> 00:42:07,450
Apenas literalmente me dizer o que é
errado como uma força de cinco anos de idade.

896
00:42:07,450 --> 00:42:08,310
>> ALUNO: Mais um.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: O que é isso?

898
00:42:08,750 --> 00:42:09,610
>> ALUNO: Mais um.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: O que quer dizer mais um?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Dê-me uma pessoa diferente de cinco anos de idade.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
O que há de errado, mãe?

904
00:42:18,330 --> 00:42:19,940
O que está errado, pai?

905
00:42:19,940 --> 00:42:22,808
O que quer dizer isso não é ordenada?

906
00:42:22,808 --> 00:42:24,370
>> ALUNO: Não é o lugar certo.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Qual é
não no lugar certo?

908
00:42:25,580 --> 00:42:26,174
>> ALUNO: Four.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, bom.

910
00:42:27,090 --> 00:42:29,110
Então, quatro não é onde deveria estar.

911
00:42:29,110 --> 00:42:30,590
Em particular, é esse direito?

912
00:42:30,590 --> 00:42:33,000
Quatro e um, o primeiro
dois números que vejo.

913
00:42:33,000 --> 00:42:34,930
Isto está certo?

914
00:42:34,930 --> 00:42:36,427
Não, eles estão fora de ordem, certo?

915
00:42:36,427 --> 00:42:38,135
Na verdade, acho que agora
sobre um computador, também.

916
00:42:38,135 --> 00:42:40,824
Ele pode apenas olhar para talvez um,
talvez duas coisas ao once--

917
00:42:40,824 --> 00:42:43,240
e, na verdade, apenas uma coisa
de cada vez, mas pode, pelo menos

918
00:42:43,240 --> 00:42:45,790
olhar para uma coisa, então o
próxima coisa bem próximo a ela.

919
00:42:45,790 --> 00:42:47,380
>> Então são estes em ordem?

920
00:42:47,380 --> 00:42:48,032
Claro que não.

921
00:42:48,032 --> 00:42:48,740
Então você sabe o quê?

922
00:42:48,740 --> 00:42:51,020
Por que não tomamos bebê
passos corrigir esse problema

923
00:42:51,020 --> 00:42:53,410
em vez de fazer estes fantasia
algoritmos, como Ben, onde

924
00:42:53,410 --> 00:42:56,440
Ele é uma espécie de corrigi-lo por
looping através da lista

925
00:42:56,440 --> 00:42:59,670
em vez de fazer o que eu fiz, onde
Eu meio que fixa-lo como nós vamos?

926
00:42:59,670 --> 00:43:03,650
Vamos apenas literalmente quebrar a
noção de ordem numérica order--,

927
00:43:03,650 --> 00:43:06,990
chamá-lo de tudo o que você want--
para estas comparações de pares.

928
00:43:06,990 --> 00:43:07,590
>> Quatro e um.

929
00:43:07,590 --> 00:43:09,970
É esta a ordem correta?

930
00:43:09,970 --> 00:43:11,310
Então vamos corrigir isso.

931
00:43:11,310 --> 00:43:14,700
Um e quatro, e em seguida
vamos apenas copiar isso.

932
00:43:14,700 --> 00:43:15,560
Tudo bem, bom.

933
00:43:15,560 --> 00:43:17,022
Fixei um e quatro.

934
00:43:17,022 --> 00:43:18,320
Três e dois?

935
00:43:18,320 --> 00:43:18,820
Não.

936
00:43:18,820 --> 00:43:21,690
Deixe minhas palavras coincidir com os meus dedos.

937
00:43:21,690 --> 00:43:23,695
Quatro e três?

938
00:43:23,695 --> 00:43:27,930
>> Não é em ordem, então eu vou
para fazer um, três, quatro, dois.

939
00:43:27,930 --> 00:43:28,680
Tudo bem.

940
00:43:28,680 --> 00:43:32,310
Agora, quatro e dois?

941
00:43:32,310 --> 00:43:33,370
Precisamos corrigir isso, também.

942
00:43:33,370 --> 00:43:36,700
Então, um, dois, três, quatro.

943
00:43:36,700 --> 00:43:39,820
Então, é classificada?

944
00:43:39,820 --> 00:43:43,170
Não, mas é o mais perto de ordenados?

945
00:43:43,170 --> 00:43:48,930
>> É, porque nós corrigido este
erro, nós corrigido este erro,

946
00:43:48,930 --> 00:43:50,370
e nós corrigido este erro.

947
00:43:50,370 --> 00:43:52,420
Por isso, fixa três erros, sem dúvida.

948
00:43:52,420 --> 00:43:58,100
Ainda realmente não parece ordenada, mas
é objectivamente mais perto de ordenado

949
00:43:58,100 --> 00:44:00,080
porque fixa alguns desses erros.

950
00:44:00,080 --> 00:44:02,047
>> Agora o que eu faço agora?

951
00:44:02,047 --> 00:44:03,630
I tipo de alcançado o fim da lista.

952
00:44:03,630 --> 00:44:05,680
Eu parecia ter fixado
todos os erros, mas não.

953
00:44:05,680 --> 00:44:08,510
Porque neste caso, alguns números
poderia ter borbulhava mais perto

954
00:44:08,510 --> 00:44:10,410
para outros números
ainda estão fora de ordem.

955
00:44:10,410 --> 00:44:12,951
Então, vamos fazê-lo novamente, e eu vou
apenas fazê-lo no lugar neste momento.

956
00:44:12,951 --> 00:44:14,170
Um e três?

957
00:44:14,170 --> 00:44:14,720
Está bem.

958
00:44:14,720 --> 00:44:16,070
Três e dois?

959
00:44:16,070 --> 00:44:17,560
Claro que não, então vamos mudar isso.

960
00:44:17,560 --> 00:44:19,160
Então, dois, três.

961
00:44:19,160 --> 00:44:21,340
Três e quatro?

962
00:44:21,340 --> 00:44:24,370
E agora vamos ser
particularmente pedante aqui.

963
00:44:24,370 --> 00:44:26,350
É classificado?

964
00:44:26,350 --> 00:44:29,280
Você seres humanos sabe que está classificada.

965
00:44:29,280 --> 00:44:30,400
>> Eu deveria tentar novamente.

966
00:44:30,400 --> 00:44:31,900
Então, Olivia está propondo que eu tente novamente.

967
00:44:31,900 --> 00:44:32,530
Por quê?

968
00:44:32,530 --> 00:44:35,810
Porque um computador não tiver
o luxo dos nossos olhos humanos

969
00:44:35,810 --> 00:44:38,080
de apenas olhando traseira-- OK, eu sou feito.

970
00:44:38,080 --> 00:44:41,610
Como o computador determinar
que a lista está agora classificado?

971
00:44:41,610 --> 00:44:44,590
Mecanicamente.

972
00:44:44,590 --> 00:44:47,650
>> Eu deveria passar por
mais uma vez, e apenas se I

973
00:44:47,650 --> 00:44:51,190
não faça / encontrar algum erro pode I
então concluir que o computador, sim,

974
00:44:51,190 --> 00:44:51,980
nós somos bons de ir.

975
00:44:51,980 --> 00:44:54,850
Assim, um e dois, dois e
três, três e quatro.

976
00:44:54,850 --> 00:44:58,030
Agora eu posso definitivamente dizer que este é
classificadas, porque eu não fez alterações.

977
00:44:58,030 --> 00:45:01,940
Agora, seria um erro e apenas
tolo se eu, o computador,

978
00:45:01,940 --> 00:45:05,640
perguntou essas mesmas perguntas novamente
esperando respostas diferentes.

979
00:45:05,640 --> 00:45:07,110
não deveria acontecer.

980
00:45:07,110 --> 00:45:08,600
>> E então agora a lista é ordenada.

981
00:45:08,600 --> 00:45:12,630
Infelizmente, duração de
este algoritmo também é N quadrado.

982
00:45:12,630 --> 00:45:13,130
Por quê?

983
00:45:13,130 --> 00:45:19,520
Porque você tem n números, e na
pior caso você tem que mover n números

984
00:45:19,520 --> 00:45:23,637
n vezes, porque você tem que continuar
de volta para verificar e corrigir potencialmente

985
00:45:23,637 --> 00:45:24,220
esses números.

986
00:45:24,220 --> 00:45:26,280
E nós podemos fazer a mais
análise formal, também.

987
00:45:26,280 --> 00:45:29,530
>> Então, tudo isso é para dizer que tomamos
três abordagens diferentes, uma

988
00:45:29,530 --> 00:45:32,210
deles imediatamente intuitiva
fora do bastão de Ben

989
00:45:32,210 --> 00:45:35,170
à minha inserção sugerido
tipo a este

990
00:45:35,170 --> 00:45:38,540
onde tipo de perder de vista
a floresta para as árvores inicialmente.

991
00:45:38,540 --> 00:45:41,760
Mas, então, se você tomar um passo para trás,
voila, temos fixo a noção de classificação.

992
00:45:41,760 --> 00:45:43,824
Portanto, este é, ouso dizer,
um nível mais baixo talvez

993
00:45:43,824 --> 00:45:45,740
do que alguns dos outros
algoritmos, mas vamos

994
00:45:45,740 --> 00:45:48,550
ver se não podemos visualizar
estes por meio deste.

995
00:45:48,550 --> 00:45:51,450
>> Então, este é um bom
software que alguém

996
00:45:51,450 --> 00:45:56,110
escreveu usando barras coloridas que há de
vai fazer o seguinte para nós.

997
00:45:56,110 --> 00:45:57,736
Cada uma destas barras representa um número.

998
00:45:57,736 --> 00:46:00,026
Taller a barra, maior
o número, menores do bar,

999
00:46:00,026 --> 00:46:00,990
Quanto menor o número.

1000
00:46:00,990 --> 00:46:05,880
Assim, idealmente, queremos uma boa pirâmide
onde começa pequeno e recebe grande,

1001
00:46:05,880 --> 00:46:08,330
e isso significaria que
essas barras são classificadas.

1002
00:46:08,330 --> 00:46:11,200
Então, eu estou indo para ir em frente e escolher,
por exemplo, o algoritmo de Ben

1003
00:46:11,200 --> 00:46:13,990
tipo selecção first--.

1004
00:46:13,990 --> 00:46:16,220
>> E observe o que está fazendo.

1005
00:46:16,220 --> 00:46:18,670
A maneira como eles optou por fazer
visualizar este algoritmo

1006
00:46:18,670 --> 00:46:22,090
é que, assim como eu era
andando através da minha lista,

1007
00:46:22,090 --> 00:46:24,710
este programa está andando
através da sua lista de números,

1008
00:46:24,710 --> 00:46:28,160
destacando em cada rosa
número que ele está olhando.

1009
00:46:28,160 --> 00:46:32,360
E o que está prestes a acontecer agora?

1010
00:46:32,360 --> 00:46:35,154
>> O menor número de que
I ou Ben encontrou de repente

1011
00:46:35,154 --> 00:46:36,820
é movido para o início da lista.

1012
00:46:36,820 --> 00:46:40,037
E notem que eles fizeram evict
o número que estava lá,

1013
00:46:40,037 --> 00:46:41,120
e isso é perfeitamente bem.

1014
00:46:41,120 --> 00:46:42,600
Eu não entrar nesse nível de detalhe.

1015
00:46:42,600 --> 00:46:44,308
Mas é preciso colocar
esse número em algum lugar,

1016
00:46:44,308 --> 00:46:47,775
por isso, apenas mudou-se para o
local aberto que foi criado.

1017
00:46:47,775 --> 00:46:49,900
Então eu vou para acelerar este
-se, porque caso contrário,

1018
00:46:49,900 --> 00:46:51,871
torna-se rapidamente muito tedioso.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animação speed-- lá vamos nós.

1021
00:46:58,600 --> 00:47:01,850
Então, agora mesmo princípio
Eu estava aplicando, mas você

1022
00:47:01,850 --> 00:47:06,540
pode começar a sentir o algoritmo, se você
vai, ou vê-lo um pouco mais claramente.

1023
00:47:06,540 --> 00:47:13,190
E este algoritmo tem o efeito de
seleccionar o próximo elemento mais pequeno,

1024
00:47:13,190 --> 00:47:16,422
então você vai começar a
vê-lo rampa até à esquerda.

1025
00:47:16,422 --> 00:47:19,130
E em cada iteração, como eu
proposto, que faz um pouco menos de trabalho.

1026
00:47:19,130 --> 00:47:21,921
Ele não tem que percorrer todo o caminho
de volta para a extremidade esquerda da lista,

1027
00:47:21,921 --> 00:47:23,900
porque já
conhece aqueles são classificadas.

1028
00:47:23,900 --> 00:47:28,129
Então, que tipo de parece que é
acelerando, mesmo que cada passo é

1029
00:47:28,129 --> 00:47:29,420
tendo a mesma quantidade de tempo.

1030
00:47:29,420 --> 00:47:31,600
Há apenas poucas etapas restantes.

1031
00:47:31,600 --> 00:47:35,240
E agora você pode tipo de sentir a
algoritmo de limpeza do final do mesmo,

1032
00:47:35,240 --> 00:47:37,040
e na verdade agora está classificada.

1033
00:47:37,040 --> 00:47:41,620
>> Então ordenação por inserção é tudo feito.

1034
00:47:41,620 --> 00:47:43,600
Eu necessidade de re-embaralhar a matriz.

1035
00:47:43,600 --> 00:47:45,940
E observe Eu só pode
manter randomização-lo,

1036
00:47:45,940 --> 00:47:50,630
e vamos ter uma aproximação das
a mesma abordagem, ordenação por inserção.

1037
00:47:50,630 --> 00:47:55,050
Deixe-me retardá-lo para aqui.

1038
00:47:55,050 --> 00:47:56,915
Vamos começar que mais.

1039
00:47:56,915 --> 00:47:57,414
Pare.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Vamos pular quatro.

1042
00:48:02,410 --> 00:48:03,200
Aqui vamos nós.

1043
00:48:03,200 --> 00:48:04,190
Randomize eles matriz.

1044
00:48:04,190 --> 00:48:05,555
E aqui nós vai-- tipo de inserção.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Toque.

1047
00:48:12,800 --> 00:48:17,280
Observe que ele está lidando com cada
elemento que encontra imediatamente,

1048
00:48:17,280 --> 00:48:20,282
mas se ele pertence a
o aviso de lugar errado

1049
00:48:20,282 --> 00:48:21,740
todo o trabalho que tem que acontecer.

1050
00:48:21,740 --> 00:48:24,700
Temos que continuar mudando mais
e mais elementos para abrir espaço

1051
00:48:24,700 --> 00:48:27,340
para o que queremos colocar no lugar.

1052
00:48:27,340 --> 00:48:30,740
>> Então, nós estamos focando na
extremidade esquerda da lista única.

1053
00:48:30,740 --> 00:48:34,460
Repare que não temos sequer olhou at-- nós
não têm destacado em qualquer coisa rosa

1054
00:48:34,460 --> 00:48:35,610
para a direita.

1055
00:48:35,610 --> 00:48:38,180
Nós estamos apenas lidando com
os problemas à medida que avançamos,

1056
00:48:38,180 --> 00:48:40,430
mas nós estamos criando um monte de
trabalhar para nós ainda.

1057
00:48:40,430 --> 00:48:44,410
E assim se acelerar este processo
agora a ficar completa,

1058
00:48:44,410 --> 00:48:46,210
ele tem uma sensação diferente para ele, de fato.

1059
00:48:46,210 --> 00:48:50,150
É apenas incidindo sobre o fim esquerdo, mas
fazendo um pouco mais de trabalho como needed--

1060
00:48:50,150 --> 00:48:53,230
tipo de coisas suavização
mais, consertar as coisas,

1061
00:48:53,230 --> 00:48:58,350
mas lidar última instância, com
cada elemento de um de cada vez

1062
00:48:58,350 --> 00:49:07,740
até chegarmos ao as-- bem, nós
todos sabemos como isso vai acabar,

1063
00:49:07,740 --> 00:49:09,700
por isso é um pouco nada assombroso talvez.

1064
00:49:09,700 --> 00:49:12,830
>> Mas a lista na end--
spoiler-- vai ser resolvido.

1065
00:49:12,830 --> 00:49:15,300
Então, vamos olhar para um último.

1066
00:49:15,300 --> 00:49:16,840
Nós não podemos simplesmente ignorar agora.

1067
00:49:16,840 --> 00:49:18,000
Estamos quase lá.

1068
00:49:18,000 --> 00:49:19,980
Duas para ir, um para ir.

1069
00:49:19,980 --> 00:49:22,680
E pronto.

1070
00:49:22,680 --> 00:49:23,450
Excelente.

1071
00:49:23,450 --> 00:49:27,220
>> Então agora vamos fazer uma última,
re-randomização com bubble sort.

1072
00:49:27,220 --> 00:49:31,690
E observe aqui, especialmente se eu retardá-lo
para baixo, isso manter mergulhando completamente.

1073
00:49:31,690 --> 00:49:36,830
Mas note que só faz pairwise
tipo comparisons-- de soluções locais.

1074
00:49:36,830 --> 00:49:39,050
Mas assim que chegarmos a
o fim da lista na cor rosa,

1075
00:49:39,050 --> 00:49:40,690
o que vai ter que acontecer de novo?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Sim, ele vai ter que
começar de novo, porque ele só

1078
00:49:46,830 --> 00:49:49,870
erros de pares fixos.

1079
00:49:49,870 --> 00:49:53,120
E que pode ter revelado ainda outros.

1080
00:49:53,120 --> 00:49:58,950
E então se você acelerar este processo, você vai
ver que, assim como o nome indica,

1081
00:49:58,950 --> 00:50:01,870
o menor elements-- ou melhor,
os elements-- maiores estão começando

1082
00:50:01,870 --> 00:50:03,740
a bolha até o topo, se você quiser.

1083
00:50:03,740 --> 00:50:07,380
E os elementos são menores
começando a bolha para baixo à esquerda.

1084
00:50:07,380 --> 00:50:10,780
E, de fato, esse é o tipo de
o efeito visual bem.

1085
00:50:10,780 --> 00:50:17,150
E assim isso vai acabar terminando
de um modo muito semelhante, também.

1086
00:50:17,150 --> 00:50:19,160
>> Não temos para habitar
em um presente particular.

1087
00:50:19,160 --> 00:50:21,010
Deixe-me abrir isso agora também.

1088
00:50:21,010 --> 00:50:24,040
Há alguns outros algoritmos de ordenação
em todo o mundo, alguns dos quais

1089
00:50:24,040 --> 00:50:25,580
são capturados aqui.

1090
00:50:25,580 --> 00:50:29,960
E, especialmente, para os alunos que não são
necessariamente visual ou matemática,

1091
00:50:29,960 --> 00:50:31,930
como fizemos antes, nós podemos
também fazer isso audially

1092
00:50:31,930 --> 00:50:34,210
se associar um som com isso.

1093
00:50:34,210 --> 00:50:36,990
E só por diversão, aqui está um
alguns algoritmos diferentes,

1094
00:50:36,990 --> 00:50:40,950
e um deles, em especial, você está
vai notar é chamado de "merge sort".

1095
00:50:40,950 --> 00:50:43,250
>> É realmente uma fundamentalmente
melhor algoritmo,

1096
00:50:43,250 --> 00:50:45,860
de tal forma que merge sort, um dos
os que você está prestes a ver,

1097
00:50:45,860 --> 00:50:49,170
não é ordem de n ao quadrado.

1098
00:50:49,170 --> 00:50:57,280
É na ordem log de n vezes de
n, que é realmente menor e, portanto,

1099
00:50:57,280 --> 00:50:58,940
mais rápido do que os outros três.

1100
00:50:58,940 --> 00:51:00,670
E há um par outra
bobas que vamos ver.

1101
00:51:00,670 --> 00:51:01,933
>> Então, vamos lá com algum som.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Esta é a ordenação por inserção, por isso novamente
é apenas lidar com os elementos

1104
00:51:10,490 --> 00:51:13,420
como eles vêm.

1105
00:51:13,420 --> 00:51:17,180
Este é bubble sort, por isso é
considerando-os pares de cada vez.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
E, novamente, os maiores elementos
estão borbulhando até o topo.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Em seguida tipo de seleção.

1110
00:51:41,710 --> 00:51:45,420
Este é o algoritmo de Ben, onde
novamente ele está selecionando de forma iterativa

1111
00:51:45,420 --> 00:51:46,843
o próximo elemento mais pequeno.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
E mais uma vez, agora você pode realmente ouvir que
está acelerando, mas apenas na medida

1114
00:51:53,900 --> 00:51:58,230
como ele está fazendo cada vez menos
trabalhar em cada iteração.

1115
00:51:58,230 --> 00:52:04,170
Este é o mais rápido um, merge sort,
que é classificar grupos de números

1116
00:52:04,170 --> 00:52:05,971
em conjunto e, em seguida, combiná-las.

1117
00:52:05,971 --> 00:52:07,720
Assim look-- esquerda
metade já estão classificados.

1118
00:52:07,720 --> 00:52:14,165
>> Agora ele está classificando a metade direita, e
agora ele vai combiná-los em um só.

1119
00:52:14,165 --> 00:52:19,160
Isso é algo chamado de "Gnome tipo."

1120
00:52:19,160 --> 00:52:23,460
E você pode tipo de ver que
ele vai lá e para cá,

1121
00:52:23,460 --> 00:52:27,950
que fixa o trabalho um pouco aqui e
antes de proceder à nova obra.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
E é isso.

1124
00:52:33,692 --> 00:52:36,400
Há um outro tipo, que é
realmente apenas para fins académicos,

1125
00:52:36,400 --> 00:52:40,980
chamado de "tipo estúpido", que leva
seus dados, classifica-o de forma aleatória,

1126
00:52:40,980 --> 00:52:43,350
e verifica se ele está classificada.

1127
00:52:43,350 --> 00:52:47,880
E se não é, re-ordena-lo
aleatoriamente, verifica se ele está classificado,

1128
00:52:47,880 --> 00:52:49,440
e se não se repete.

1129
00:52:49,440 --> 00:52:52,660
E, em teoria, probabilisticamente
isso vai terminar,

1130
00:52:52,660 --> 00:52:54,140
mas depois de um pouco de tempo.

1131
00:52:54,140 --> 00:52:56,930
Não é o mais
eficiente de algoritmos.

1132
00:52:56,930 --> 00:53:02,550
Assim, qualquer perguntas sobre os
algoritmos particulares ou nada

1133
00:53:02,550 --> 00:53:04,720
relacionados lá, também?

1134
00:53:04,720 --> 00:53:09,430
>> Bem, vamos agora desmembrar o que todos
estas linhas são que eu tenho desenhado

1135
00:53:09,430 --> 00:53:15,090
eo que eu estou supondo que o computador
pode fazer debaixo do capô.

1136
00:53:15,090 --> 00:53:18,650
Eu diria que todos esses números
Eu continuo drawing-- eles precisam para obter

1137
00:53:18,650 --> 00:53:21,330
armazenado em algum lugar na memória.

1138
00:53:21,330 --> 00:53:24,130
Vamos nos livrar desse cara agora, também.

1139
00:53:24,130 --> 00:53:30,110
>> Assim, uma parte da memória numa
Computador-- tão RAM DIMM é

1140
00:53:30,110 --> 00:53:35,480
o que procurou ontem, dual
memória em linha module-- se parece com isso.

1141
00:53:35,480 --> 00:53:39,370
E cada uma dessas pequenas fichas pretas
é algum número de bytes, normalmente.

1142
00:53:39,370 --> 00:53:44,380
E então os pinos de ouro são como o
fios que ligam ao computador,

1143
00:53:44,380 --> 00:53:47,521
ea placa de silício verde é apenas
o que mantém tudo em conjunto.

1144
00:53:47,521 --> 00:53:48,770
Então o que isso realmente significa?

1145
00:53:48,770 --> 00:53:53,180
Se eu tipo de desenhar essa mesma imagem,
vamos supor que a simplicidade

1146
00:53:53,180 --> 00:53:55,280
que este DIMM, dual
Inline Memory Module,

1147
00:53:55,280 --> 00:54:00,530
é um gigabyte de RAM, um gigabyte de
memória, que é o número de bytes no total?

1148
00:54:00,530 --> 00:54:02,100
Um gigabyte é quantos bytes?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Mais que isso.

1151
00:54:06,030 --> 00:54:09,960
1124 é kilo, 1.000.

1152
00:54:09,960 --> 00:54:11,730
Mega é milhões.

1153
00:54:11,730 --> 00:54:14,570
Giga é um bilhão.

1154
00:54:14,570 --> 00:54:15,070
>> Eu estou mentindo?

1155
00:54:15,070 --> 00:54:16,670
podemos até ler o rótulo?

1156
00:54:16,670 --> 00:54:19,920
Isto é, na verdade, 128
gigabytes, por isso é mais.

1157
00:54:19,920 --> 00:54:22,130
Mas vamos fingir que isso
é apenas um gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Então isso significa que há um bilhão
bytes de memória disponíveis para mim

1159
00:54:25,640 --> 00:54:29,770
ou 8 bilhões de bits, mas vamos
para falar em termos de bytes agora,

1160
00:54:29,770 --> 00:54:30,750
avançar.

1161
00:54:30,750 --> 00:54:36,330
>> Então, o que isso significa é que isto é
um byte, este é mais um byte,

1162
00:54:36,330 --> 00:54:38,680
este é mais um byte,
e se nós realmente queríamos

1163
00:54:38,680 --> 00:54:43,280
para ser mais específico, teríamos de
desenhar um bilhão de pequenos quadrados.

1164
00:54:43,280 --> 00:54:44,320
Mas o que isso significa?

1165
00:54:44,320 --> 00:54:46,420
Bem, deixe-me apenas aumentar
em nesta imagem.

1166
00:54:46,420 --> 00:54:50,900
Se eu tenho algo que parece
assim agora, isso é quatro bytes.

1167
00:54:50,900 --> 00:54:53,710
>> E assim eu poderia colocar quatro números aqui.

1168
00:54:53,710 --> 00:54:54,990
Um dois três quatro.

1169
00:54:54,990 --> 00:55:00,170
Ou eu poderia colocar quatro letras ou símbolos.

1170
00:55:00,170 --> 00:55:02,620
"Ei!" poderia ir para a direita lá,
porque cada uma das cartas,

1171
00:55:02,620 --> 00:55:04,370
discutimos anteriormente,
Pode ser representado

1172
00:55:04,370 --> 00:55:06,650
com oito bits ou ASCII ou um byte.

1173
00:55:06,650 --> 00:55:09,370
Portanto, em outras palavras, você pode
colocar 8 mil milhões de coisas dentro

1174
00:55:09,370 --> 00:55:11,137
de um presente da vara da memória.

1175
00:55:11,137 --> 00:55:14,345
Agora o que isso significa para colocar as coisas de volta
a volta para trás na memória como esta?

1176
00:55:14,345 --> 00:55:17,330
Isto é o que um programador
chamaria de um "array".

1177
00:55:17,330 --> 00:55:21,250
Em um programa de computador, você não pensa
sobre o hardware subjacente, per se.

1178
00:55:21,250 --> 00:55:24,427
Você só pensa em si mesmo como tendo
acesso a um total bilhão de bytes,

1179
00:55:24,427 --> 00:55:26,010
e você pode o que quiser com ele.

1180
00:55:26,010 --> 00:55:27,880
Mas por conveniência
normalmente é útil

1181
00:55:27,880 --> 00:55:31,202
para manter o seu direito de memória
ao lado do outro como este.

1182
00:55:31,202 --> 00:55:33,660
Então, se eu aumentar o zoom em isto--
porque certamente não vai

1183
00:55:33,660 --> 00:55:39,310
desenhar um bilhão de pequenos squares--
vamos supor que este quadro representa

1184
00:55:39,310 --> 00:55:40,610
essa vara da memória agora.

1185
00:55:40,610 --> 00:55:43,800
E eu vou apenas chamar a todos quantos o meu
marcador acaba me dando aqui.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Portanto, agora temos uma vara
de memória na placa

1188
00:55:52,300 --> 00:55:56,400
que tem um, dois, três, quatro, cinco,
seis, um, dois, três, quatro, cinco, seis,

1189
00:55:56,400 --> 00:56:01,130
seven-- assim 42 bytes de
memória sobre o total da tela.

1190
00:56:01,130 --> 00:56:01,630
Obrigado.

1191
00:56:01,630 --> 00:56:02,838
Sim, fiz a minha aritmética direita.

1192
00:56:02,838 --> 00:56:05,120
Assim, 42 bytes de memória aqui.

1193
00:56:05,120 --> 00:56:06,660
Então o que isso realmente significa?

1194
00:56:06,660 --> 00:56:09,830
Bem, um programador de computador
seria realmente geral

1195
00:56:09,830 --> 00:56:12,450
acha deste como memória endereçável.

1196
00:56:12,450 --> 00:56:16,630
Em outras palavras, cada uma delas
locais na memória, em hardware,

1197
00:56:16,630 --> 00:56:18,030
tem um endereço exclusivo.

1198
00:56:18,030 --> 00:56:22,020
>> Não é tão complexo como um Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Ao contrário, é apenas um número.

1200
00:56:23,830 --> 00:56:27,930
Este é byte número zero, isto é
um, isto é dois, isto é três,

1201
00:56:27,930 --> 00:56:30,327
e esta é de 41.

1202
00:56:30,327 --> 00:56:30,910
Espere um minuto.

1203
00:56:30,910 --> 00:56:32,510
Eu pensei que eu disse 42 um momento atrás.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Comecei a contar do zero,
de modo que é realmente correto.

1206
00:56:37,772 --> 00:56:40,980
Agora não temos realmente desenhá-la
como uma rede, e se você desenhá-lo como uma grade

1207
00:56:40,980 --> 00:56:43,520
Acho que as coisas realmente
obter um pouco enganador.

1208
00:56:43,520 --> 00:56:46,650
O que um programador faria,
em sua própria mente,

1209
00:56:46,650 --> 00:56:50,310
geralmente pensam desta
memória como é como uma fita,

1210
00:56:50,310 --> 00:56:53,340
como um pedaço de fita adesiva
que só vai sobre e sobre para sempre

1211
00:56:53,340 --> 00:56:54,980
ou até ficar sem memória.

1212
00:56:54,980 --> 00:56:59,200
Assim, uma maneira mais comum para desenhar
e só pensar sobre a memória

1213
00:56:59,200 --> 00:57:03,710
seria a de que esta é zero bytes, um,
dois, três, e, em seguida, ponto, ponto, ponto.

1214
00:57:03,710 --> 00:57:07,650
E você tem 42 desses bytes total, o mesmo
embora fisicamente ele pode realmente

1215
00:57:07,650 --> 00:57:09,480
ser algo mais como este.

1216
00:57:09,480 --> 00:57:12,850
>> Então, se você pensa agora do seu
memória como esta, assim como uma fita,

1217
00:57:12,850 --> 00:57:17,640
isso é o que um programador de novo
chamaria de uma matriz de memória.

1218
00:57:17,640 --> 00:57:20,660
E quando você quer realmente armazenar
algo em memória de um computador,

1219
00:57:20,660 --> 00:57:23,290
você geralmente fazer coisas loja
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Então, nós estamos falando de números.

1221
00:57:25,010 --> 00:57:30,880
E quando eu queria para resolver problemas
como quatro, um, três, dois,

1222
00:57:30,880 --> 00:57:33,820
mesmo que eu estava apenas um desenho
apenas o número quatro, um, três,

1223
00:57:33,820 --> 00:57:39,490
dois no bordo, o computador faria
realmente tem esta configuração na memória.

1224
00:57:39,490 --> 00:57:43,347
>> E o que seria ao lado do
dois na memória do computador?

1225
00:57:43,347 --> 00:57:44,680
Bem, não há nenhuma resposta para isso.

1226
00:57:44,680 --> 00:57:45,770
Nós realmente não sabemos.

1227
00:57:45,770 --> 00:57:48,200
E desde que a
O computador não precisa dele,

1228
00:57:48,200 --> 00:57:51,440
ele não precisa se preocupar que é o próximo
aos números que se preocupa com.

1229
00:57:51,440 --> 00:57:55,130
E quando eu disse anteriormente que um computador
só pode olhar para um endereço de cada vez,

1230
00:57:55,130 --> 00:57:56,170
este é o tipo de porquê.

1231
00:57:56,170 --> 00:57:59,490
>> Não ao contrário de um registro
jogador e uma cabeça de leitura

1232
00:57:59,490 --> 00:58:03,030
apenas ser capaz de olhar para um certo
sulco em um registro da velha escola física

1233
00:58:03,030 --> 00:58:06,500
de cada vez, de modo semelhante
pode um computador graças

1234
00:58:06,500 --> 00:58:09,810
a sua CPU e a sua
conjunto de instruções Intel,

1235
00:58:09,810 --> 00:58:12,480
entre cujos instrução
é lido a partir da memória

1236
00:58:12,480 --> 00:58:15,590
ou salvar em memory-- um
computador só pode olhar

1237
00:58:15,590 --> 00:58:19,210
em um local de cada vez--
por vezes, uma combinação dos mesmos,

1238
00:58:19,210 --> 00:58:21,770
mas realmente apenas um local de cada vez.

1239
00:58:21,770 --> 00:58:24,770
Então, quando estávamos fazendo
estes vários algoritmos,

1240
00:58:24,770 --> 00:58:28,110
Eu não só estou escrevendo em um
vacuum-- quatro, um, três, dois.

1241
00:58:28,110 --> 00:58:30,849
Esses números, na verdade, pertencem
algures na memória física.

1242
00:58:30,849 --> 00:58:32,890
Portanto, há pequenino
transistores ou algum tipo

1243
00:58:32,890 --> 00:58:35,840
da eletrônica debaixo da
hood armazenar esses valores.

1244
00:58:35,840 --> 00:58:40,460
>> E no total, quantos bits são
envolvidos agora, só para ficar claro?

1245
00:58:40,460 --> 00:58:45,580
Portanto, este é quatro bytes, ou
agora é 32 bits total.

1246
00:58:45,580 --> 00:58:49,280
Então, na verdade existem 32 zeros e
aqueles que compõem essas quatro coisas.

1247
00:58:49,280 --> 00:58:52,070
Há ainda mais aqui, mas
mais uma vez, não se preocupam com isso.

1248
00:58:52,070 --> 00:58:55,120
>> Então agora vamos fazer outra
pergunta usando memória,

1249
00:58:55,120 --> 00:58:57,519
pois que no final
do dia está na variância.

1250
00:58:57,519 --> 00:59:00,310
Não importa o que pode fazer com
o computador, no final do dia

1251
00:59:00,310 --> 00:59:02,560
o hardware ainda o é
mesmo debaixo do capô.

1252
00:59:02,560 --> 00:59:04,670
Como eu poderia armazenar uma palavra aqui?

1253
00:59:04,670 --> 00:59:09,710
Bem, uma palavra em um computador, como
"Ei!" seria armazenado como esta.

1254
00:59:09,710 --> 00:59:12,300
E se você queria um mais
Word, você pode simplesmente

1255
00:59:12,300 --> 00:59:19,120
substituir esse e dizer algo
como "Olá" e loja que aqui.

1256
00:59:19,120 --> 00:59:23,930
>> E aqui, também, este contiguidade
é realmente uma vantagem,

1257
00:59:23,930 --> 00:59:26,530
porque um computador pode apenas
lido da direita para a esquerda.

1258
00:59:26,530 --> 00:59:28,680
Mas aqui está uma pergunta.

1259
00:59:28,680 --> 00:59:33,480
No contexto desta palavra,
h-e-l-l-o, ponto de exclamação,

1260
00:59:33,480 --> 00:59:38,740
como pode o computador sabe onde o
palavra começa e onde a palavra termina?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
No contexto de números,
Como o computador

1263
00:59:43,800 --> 00:59:48,396
saber quanto tempo a sequência de
números é ou de onde ele começa?

1264
00:59:48,396 --> 00:59:50,270
Bem, acontece out--
e não vamos entrar muito

1265
00:59:50,270 --> 00:59:54,970
a este nível de detail--
computadores mover coisas ao redor na memória

1266
00:59:54,970 --> 00:59:57,800
literalmente, por meio desses endereços.

1267
00:59:57,800 --> 01:00:02,080
Assim, em um computador, se você estiver
escrever código para guardar coisas

1268
01:00:02,080 --> 01:00:05,800
como palavras, o que você está
fazendo realmente está digitando

1269
01:00:05,800 --> 01:00:11,320
expressões que lembram onde em
memória do computador estas palavras são.

1270
01:00:11,320 --> 01:00:14,370
Então deixe-me fazer uma muito,
exemplo muito simples.

1271
01:00:14,370 --> 01:00:18,260
>> Eu estou indo para ir em frente e
abrir um programa de texto simples,

1272
01:00:18,260 --> 01:00:20,330
e eu estou indo para criar
um arquivo chamado hello.c.

1273
01:00:20,330 --> 01:00:22,849
A maioria desta informação que
Não vou entrar em em grande detalhe,

1274
01:00:22,849 --> 01:00:25,140
mas eu estou indo para escrever um
programa nesse mesmo idioma,

1275
01:00:25,140 --> 01:00:31,140
C. Isto é muito mais intimidante,
Eu diria, do que zero,

1276
01:00:31,140 --> 01:00:32,490
mas é muito semelhante em espírito.

1277
01:00:32,490 --> 01:00:34,364
Na verdade, estes encaracolado
braces-- Você pode tipo de

1278
01:00:34,364 --> 01:00:37,820
pensar o que eu fiz como esta.

1279
01:00:37,820 --> 01:00:39,240
>> Vamos fazer isso, na verdade.

1280
01:00:39,240 --> 01:00:45,100
Quando a bandeira verde clicado,
faça o seguinte.

1281
01:00:45,100 --> 01:00:50,210
Quero imprimir "Olá".

1282
01:00:50,210 --> 01:00:51,500
Portanto, esta é agora pseudocódigo.

1283
01:00:51,500 --> 01:00:53,000
Eu sou o tipo de borrar as linhas.

1284
01:00:53,000 --> 01:00:56,750
Em C, esta língua que eu estou falando
sobre, esta linha de impressão Olá

1285
01:00:56,750 --> 01:01:01,940
torna-se realmente "printf" com
alguns parênteses e um ponto e vírgula.

1286
01:01:01,940 --> 01:01:03,480
>> Mas é exatamente a mesma idéia.

1287
01:01:03,480 --> 01:01:06,730
E isso muito user-friendly
"Quando a bandeira verde clicado" torna-se

1288
01:01:06,730 --> 01:01:10,182
o muito mais arcano "void main int."

1289
01:01:10,182 --> 01:01:12,890
E isso realmente não tem mapeamento,
então eu só vou ignorar isso.

1290
01:01:12,890 --> 01:01:17,210
Mas as chaves são como o
peças do puzzle curvo como este.

1291
01:01:17,210 --> 01:01:18,700
>> Assim, você pode tipo de adivinhar.

1292
01:01:18,700 --> 01:01:22,357
Mesmo se você nunca programou antes,
o que é que este programa provavelmente fazer?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Provavelmente imprime Olá
com um ponto de exclamação.

1295
01:01:28,000 --> 01:01:29,150
>> Então, vamos tentar isso.

1296
01:01:29,150 --> 01:01:30,800
Eu estou indo para salvá-lo.

1297
01:01:30,800 --> 01:01:34,000
E isto é, novamente, uma muito
ambiente da velha escola.

1298
01:01:34,000 --> 01:01:35,420
Eu não posso clicar, não pode arrastar.

1299
01:01:35,420 --> 01:01:36,910
Eu tenho que digitar comandos.

1300
01:01:36,910 --> 01:01:41,320
Então, eu quero executar o meu programa, de modo
Eu poderia fazer isso, como hello.c.

1301
01:01:41,320 --> 01:01:42,292
Esse é o arquivo que eu corri.

1302
01:01:42,292 --> 01:01:43,500
Mas espere, eu estou faltando uma etapa.

1303
01:01:43,500 --> 01:01:46,470
O que dizemos é uma condição necessária
passo para uma linguagem como C?

1304
01:01:46,470 --> 01:01:49,470
Acabei de fonte escrita
código, mas o que eu preciso?

1305
01:01:49,470 --> 01:01:50,670
Sim, eu preciso de um compilador.

1306
01:01:50,670 --> 01:01:57,670
Então, no meu Mac aqui, eu tenho um
programa chamado GCC, o compilador GNU C,

1307
01:01:57,670 --> 01:02:03,990
o que me permite fazer isto-- vez
meu código-fonte em, vamos chamá-lo,

1308
01:02:03,990 --> 01:02:04,930
Código da máquina.

1309
01:02:04,930 --> 01:02:10,180
>> E eu posso ver que,
outra vez, como se segue, estes

1310
01:02:10,180 --> 01:02:14,090
são os zeros e uns EU APENAS
criado a partir de meu código-fonte,

1311
01:02:14,090 --> 01:02:15,730
todos os zeros e uns.

1312
01:02:15,730 --> 01:02:17,770
E se eu quiser executar
meu program-- isso acontece

1313
01:02:17,770 --> 01:02:23,010
a ser chamado a.out para
reasons-- histórico "Olá".

1314
01:02:23,010 --> 01:02:24,070
Posso executá-lo novamente.

1315
01:02:24,070 --> 01:02:25,690
Ola Ola Ola.

1316
01:02:25,690 --> 01:02:27,430
E parece estar funcionando.

1317
01:02:27,430 --> 01:02:31,000
>> Mas isso significa que em algum lugar na minha
memória do computador são as palavras

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l o, ponto de exclamação.

1319
01:02:35,279 --> 01:02:38,070
E verifica-se, como um aparte,
o que um computador faria normalmente

1320
01:02:38,070 --> 01:02:40,550
fazer para que ele saiba onde
as coisas começam e end-- é

1321
01:02:40,550 --> 01:02:42,460
vai colocar um símbolo especial aqui.

1322
01:02:42,460 --> 01:02:46,064
E a convenção é colocar o
número zero no final de uma palavra

1323
01:02:46,064 --> 01:02:48,230
para que você saiba onde
realmente termina, de modo que você

1324
01:02:48,230 --> 01:02:52,750
não manter imprimir mais e mais
caracteres que você realmente pretende.

1325
01:02:52,750 --> 01:02:55,400
>> Mas o takeaway aqui, mesmo
embora este é bastante misterioso,

1326
01:02:55,400 --> 01:02:58,140
é que é, em última análise
relativamente simples.

1327
01:02:58,140 --> 01:03:04,550
Foi-lhe dado uma espécie de fita, um espaço em branco
espaço onde pode escrever cartas.

1328
01:03:04,550 --> 01:03:07,150
Você simplesmente tem que ter um
símbolo especial, como arbitrariamente

1329
01:03:07,150 --> 01:03:10,316
o número zero, para colocar na extremidade da
suas palavras para que o computador sabe,

1330
01:03:10,316 --> 01:03:13,410
oh, eu deveria parar a impressão depois
Eu vejo o ponto de exclamação.

1331
01:03:13,410 --> 01:03:16,090
Porque a próxima coisa lá
é um valor ASCII de zero,

1332
01:03:16,090 --> 01:03:19,125
ou o carácter nulo como
alguém iria chamá-lo.

1333
01:03:19,125 --> 01:03:21,500
Mas há um tipo de um problema
aqui, e vamos voltar

1334
01:03:21,500 --> 01:03:23,320
a números por um momento.

1335
01:03:23,320 --> 01:03:28,720
Suponha que eu faço, na verdade,
têm uma série de números,

1336
01:03:28,720 --> 01:03:30,730
e supor que o
programa que eu estou escrevendo é

1337
01:03:30,730 --> 01:03:34,680
como um livro de notas para um professor
e uma sala de aula professores.

1338
01:03:34,680 --> 01:03:38,720
E este programa permite que ele ou ela
para digitar as notas dos seus alunos

1339
01:03:38,720 --> 01:03:39,960
em questionários.

1340
01:03:39,960 --> 01:03:43,750
E suponha que o aluno recebe
100 em seu primeiro teste, talvez

1341
01:03:43,750 --> 01:03:49,920
como um 80 no próximo, em seguida, um
75, em seguida, um 90 no quarto quiz.

1342
01:03:49,920 --> 01:03:54,150
>> Portanto, neste ponto da história,
a matriz é de tamanho quatro.

1343
01:03:54,150 --> 01:03:58,470
Não há absolutamente mais memória no
computador, mas a matriz, por assim dizer,

1344
01:03:58,470 --> 01:04:00,350
é de tamanho quatro.

1345
01:04:00,350 --> 01:04:06,060
Suponha agora que o professor quer
para atribuir um quinto teste para a classe.

1346
01:04:06,060 --> 01:04:08,510
Bem, uma das coisas que ele
ou ela vai ter que fazer

1347
01:04:08,510 --> 01:04:10,650
é agora armazenar um valor adicional aqui.

1348
01:04:10,650 --> 01:04:15,490
Mas se a matriz o professor tem
criado neste programa é de tamanho para,

1349
01:04:15,490 --> 01:04:22,440
um dos problemas com que é uma matriz
você não pode simplesmente continuar a acrescentar a memória.

1350
01:04:22,440 --> 01:04:26,470
Porque o que se outra parte do
programa tem a palavra "hey" ali?

1351
01:04:26,470 --> 01:04:29,650
>> Em outras palavras, a memória pode ser
usado para qualquer coisa em um programa.

1352
01:04:29,650 --> 01:04:33,250
E se antes eu digitei, hey,
Quero entrada quatro pontuações do questionário,

1353
01:04:33,250 --> 01:04:34,784
eles podem ir aqui e aqui.

1354
01:04:34,784 --> 01:04:37,700
E se de repente você mudar sua mente
mais tarde e dizer que eu quero um quinto teste

1355
01:04:37,700 --> 01:04:40,872
pontuação, você não pode simplesmente
colocá-lo onde quiser,

1356
01:04:40,872 --> 01:04:42,580
porque o que se esta
memória está sendo usada

1357
01:04:42,580 --> 01:04:45,990
para algo else-- algum outro programa
ou alguma outra característica do programa

1358
01:04:45,990 --> 01:04:46,910
que você está correndo?

1359
01:04:46,910 --> 01:04:50,650
Então você tem que pensar com antecedência
como você deseja armazenar seus dados,

1360
01:04:50,650 --> 01:04:54,480
porque agora você pintou
sozinho em um canto digital.

1361
01:04:54,480 --> 01:04:57,280
>> Assim, um professor pode, em vez
dizer quando se escreve um programa

1362
01:04:57,280 --> 01:04:59,360
para armazenar a sua
notas, você sabe o quê?

1363
01:04:59,360 --> 01:05:04,180
Vou solicitar,
ao escrever o meu programa,

1364
01:05:04,180 --> 01:05:12,070
que eu quero zero, um, dois, três,
quatro, cinco, seis, oito graus no total.

1365
01:05:12,070 --> 01:05:15,320
Então, um, dois, três, quatro,
cinco, seis, sete, oito.

1366
01:05:15,320 --> 01:05:18,612
O professor pode apenas sobre-alocar
memória ao escrever o seu programa

1367
01:05:18,612 --> 01:05:19,570
e dizer, você sabe o quê?

1368
01:05:19,570 --> 01:05:22,236
Eu nunca vou atribuir mais
de oito testes em um semestre.

1369
01:05:22,236 --> 01:05:23,130
Isso é uma loucura.

1370
01:05:23,130 --> 01:05:24,470
Eu nunca vou atribuir isso.

1371
01:05:24,470 --> 01:05:28,270
Assim que esta maneira que ele ou ela tem a
flexibilidade para pontuações loja de estudante,

1372
01:05:28,270 --> 01:05:33,010
como 75, 90, e talvez um extra, onde
o aluno tem crédito extra, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Mas se o professor nunca
utiliza estes três espaços,

1374
01:05:36,130 --> 01:05:38,860
há um takeaway intuitiva aqui.

1375
01:05:38,860 --> 01:05:41,410
Ele ou ela é apenas desperdício de espaço.

1376
01:05:41,410 --> 01:05:44,790
Portanto, em outras palavras, não é isso
tradeoff comum na programação

1377
01:05:44,790 --> 01:05:48,241
onde você pode alocar
exatamente tanta memória como você quer,

1378
01:05:48,241 --> 01:05:51,490
a cabeça do que é que você está super
efficient-- você não está sendo um desperdício

1379
01:05:51,490 --> 01:05:54,640
em todos-- mas a desvantagem dos quais
é o que se você mudar sua mente quando

1380
01:05:54,640 --> 01:05:58,780
usando o programa que você deseja armazenar
mais dados do que você inicialmente previsto.

1381
01:05:58,780 --> 01:06:03,030
>> Então, talvez a solução é, então,
escrever seus programas de tal forma

1382
01:06:03,030 --> 01:06:05,605
que eles usam mais memória
do que eles realmente precisam.

1383
01:06:05,605 --> 01:06:07,730
Desta forma, você não vai
a correr para esse problema,

1384
01:06:07,730 --> 01:06:09,730
mas você está sendo um desperdício.

1385
01:06:09,730 --> 01:06:12,960
E o mais memória o programa usa,
como discutimos ontem, a menos

1386
01:06:12,960 --> 01:06:15,410
memória que está disponível
para outros programas,

1387
01:06:15,410 --> 01:06:18,790
quanto mais cedo o seu computador pode retardar
para baixo por causa da memória virtual.

1388
01:06:18,790 --> 01:06:22,670
E assim a solução ideal pode ser o que?

1389
01:06:22,670 --> 01:06:24,610
>> Sub-reparte parece ruim.

1390
01:06:24,610 --> 01:06:27,030
Over-reparte parece ruim.

1391
01:06:27,030 --> 01:06:31,120
Então, o que pode ser uma solução melhor?

1392
01:06:31,120 --> 01:06:32,390
A realocação.

1393
01:06:32,390 --> 01:06:33,590
Seja mais dinâmico.

1394
01:06:33,590 --> 01:06:37,520
Não se force a escolher um
priori, no início, o que você quer.

1395
01:06:37,520 --> 01:06:41,370
E, certamente, não o excesso de alocar,
para que você não ser um desperdício.

1396
01:06:41,370 --> 01:06:45,770
>> E assim, para alcançar esse objetivo,
precisa jogar esta estrutura de dados,

1397
01:06:45,770 --> 01:06:48,100
por assim dizer, longe.

1398
01:06:48,100 --> 01:06:51,080
E então o que um programador
tipicamente utilizará

1399
01:06:51,080 --> 01:06:55,940
é algo que não é uma chamada
matriz, mas uma lista ligada.

1400
01:06:55,940 --> 01:07:00,860
Em outras palavras, ele ou ela vai
começar a pensar em sua memória

1401
01:07:00,860 --> 01:07:05,280
como sendo um tipo de forma que eles
pode tirar da seguinte maneira.

1402
01:07:05,280 --> 01:07:08,520
Se eu quiser armazenar um número na
um program-- por isso é de setembro de

1403
01:07:08,520 --> 01:07:12,600
Eu dei os meus alunos um questionário; eu quero
para armazenar primeiro teste dos alunos,

1404
01:07:12,600 --> 01:07:16,220
e eles tem um 100 sobre ele-- I
vou pedir o meu computador,

1405
01:07:16,220 --> 01:07:19,540
por meio do programa que eu tenho
escrito, por um pedaço de memória.

1406
01:07:19,540 --> 01:07:22,570
E eu estou indo para armazenar o
número 100, e é isso.

1407
01:07:22,570 --> 01:07:24,820
>> Em seguida, algumas semanas mais tarde
quando eu chegar em meu segundo questionário,

1408
01:07:24,820 --> 01:07:27,890
e é hora de digitar
em que 90%, eu vou

1409
01:07:27,890 --> 01:07:32,129
para pedir o computador, hey, computador,
Eu posso ter outro pedaço de memória?

1410
01:07:32,129 --> 01:07:34,170
Vai me dar a este
pedaço vazio de memória.

1411
01:07:34,170 --> 01:07:39,370
Vou colocar o número 90,
mas no meu programa de alguma forma ou outro--

1412
01:07:39,370 --> 01:07:42,100
e nós não vai se preocupar com
a sintaxe para isto-- eu preciso

1413
01:07:42,100 --> 01:07:44,430
de alguma forma encadear essas coisas juntas.

1414
01:07:44,430 --> 01:07:47,430
E eu vou acorrentá-los juntamente com
o que parece ser uma seta aqui.

1415
01:07:47,430 --> 01:07:50,050
>> O terceiro questionário que surge,
Eu vou dizer, hey, computador,

1416
01:07:50,050 --> 01:07:51,680
dar-me outro pedaço de memória.

1417
01:07:51,680 --> 01:07:54,660
E eu vou colocar para baixo
que quer que fosse, como 75,

1418
01:07:54,660 --> 01:07:56,920
e tenho de cadeia presente
juntos agora de alguma forma.

1419
01:07:56,920 --> 01:08:00,290
Quarta questionário vem junto, e talvez
isso é para o final do semestre.

1420
01:08:00,290 --> 01:08:03,140
E por esse ponto o meu programa
pode estar usando memória

1421
01:08:03,140 --> 01:08:05,540
em todo o lugar, em todo fisicamente.

1422
01:08:05,540 --> 01:08:08,170
E assim, apenas por diversão, eu sou
vai tirar essa luz

1423
01:08:08,170 --> 01:08:11,260
quiz-- eu esquecer o que era; Eu
acho que talvez um 80 ou algo--

1424
01:08:11,260 --> 01:08:12,500
caminho até aqui.

1425
01:08:12,500 --> 01:08:15,920
>> Mas isso é bom, porque pictoricamente
Eu estou indo para desenhar esta linha.

1426
01:08:15,920 --> 01:08:19,063
Em outras palavras, na realidade,
no hardware do seu computador,

1427
01:08:19,063 --> 01:08:20,979
a primeira pontuação pode
acabar aqui, porque é

1428
01:08:20,979 --> 01:08:22,529
logo no início do semestre.

1429
01:08:22,529 --> 01:08:25,810
O próximo pode acabar aqui
porque um pouco de tempo já passou

1430
01:08:25,810 --> 01:08:27,210
eo programa continua a funcionar.

1431
01:08:27,210 --> 01:08:30,060
A próxima pontuação, que foi
a 75, pode ser por aqui.

1432
01:08:30,060 --> 01:08:33,420
E a última pontuação pode ser
um 80, que é por aqui.

1433
01:08:33,420 --> 01:08:38,729
>> Então, na realidade, fisicamente, isso pode ser
o que a memória do seu computador parece.

1434
01:08:38,729 --> 01:08:41,569
Mas este não é um mentais útil
paradigma para um programador de computador.

1435
01:08:41,569 --> 01:08:44,649
Por que você deveria se preocupar onde o
Parreira seus dados estão terminando?

1436
01:08:44,649 --> 01:08:46,200
Você só quer armazenar dados.

1437
01:08:46,200 --> 01:08:49,390
>> Este é tipo de como nossa discussão
antes de desenhar o cubo.

1438
01:08:49,390 --> 01:08:52,200
Por que você se importa o que
é o ângulo do cubo

1439
01:08:52,200 --> 01:08:53,740
e como você tem que voltar para desenhá-lo?

1440
01:08:53,740 --> 01:08:54,950
Você só quer um cubo.

1441
01:08:54,950 --> 01:08:57,359
Da mesma forma aqui, você
só quero livro de notas.

1442
01:08:57,359 --> 01:08:59,559
Você só quer pensar
isto como uma lista de números.

1443
01:08:59,559 --> 01:09:01,350
Quem se importa como ela é
implementadas em hardware?

1444
01:09:01,350 --> 01:09:05,180
>> Assim, a abstração agora
É esta foto aqui.

1445
01:09:05,180 --> 01:09:07,580
Esta é uma lista ligada, como
um programador iria chamá-lo,

1446
01:09:07,580 --> 01:09:10,640
na medida em que você tem um
lista, obviamente, de números.

1447
01:09:10,640 --> 01:09:14,990
Mas está ligada pictoricamente
por meio destas setas,

1448
01:09:14,990 --> 01:09:18,510
e todas estas setas é-- debaixo
o capô, se você estiver curioso,

1449
01:09:18,510 --> 01:09:23,210
Recordamos que o nosso hardware físico tem
endereços zero, um, dois, três, quatro.

1450
01:09:23,210 --> 01:09:28,465
Todas estas flechas são é como um mapa
ou instruções, onde se 90 é-- agora

1451
01:09:28,465 --> 01:09:29,090
Eu tenho que contar.

1452
01:09:29,090 --> 01:09:31,750
>> Zero, um, dois, três,
quatro, cinco, seis, sete.

1453
01:09:31,750 --> 01:09:35,640
Parece que o 90 é a
memória do número de endereço de sete.

1454
01:09:35,640 --> 01:09:38,460
Todas estas flechas são é
como um pequeno pedaço de papel

1455
01:09:38,460 --> 01:09:42,439
que está dando instruções para o
programa que diz que siga este mapa

1456
01:09:42,439 --> 01:09:43,880
para chegar ao local de sete.

1457
01:09:43,880 --> 01:09:46,680
E lá você vai encontrar o
segunda pontuação do questionário do estudante.

1458
01:09:46,680 --> 01:09:52,100
Enquanto isso, o 75-- se eu continuar com este,
este é sete, oito, nove, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Esta outra seta representa apenas
um mapa para localização de memória 15.

1461
01:09:59,080 --> 01:10:02,550
Mas, novamente, o programador geralmente faz
não se preocupam com este nível de detalhe.

1462
01:10:02,550 --> 01:10:05,530
E na maioria cada programação
linguagem de hoje, o programador

1463
01:10:05,530 --> 01:10:10,490
nem vai saber onde na memória
esses números realmente são.

1464
01:10:10,490 --> 01:10:14,830
Tudo o que ele ou ela tem que se preocupam com o
que eles são de alguma forma ligada em conjunto

1465
01:10:14,830 --> 01:10:18,390
numa estrutura de dados como este.

1466
01:10:18,390 --> 01:10:21,580
>> Mas acontece que não
ficar muito técnico.

1467
01:10:21,580 --> 01:10:27,430
Mas só porque nós podemos, talvez,
dar ao luxo de ter essa discussão aqui,

1468
01:10:27,430 --> 01:10:33,630
suponha que nós revisitar
esta questão aqui de uma matriz.

1469
01:10:33,630 --> 01:10:35,780
Vamos ver se nós lamentamos indo para lá.

1470
01:10:35,780 --> 01:10:42,950
Esta é de 100, 90, 75, e 80.

1471
01:10:42,950 --> 01:10:44,980
>> Deixe-me fazer brevemente esta reivindicação.

1472
01:10:44,980 --> 01:10:48,980
Esta é uma matriz, e de novo, o
característica marcante de uma matriz

1473
01:10:48,980 --> 01:10:52,400
é que todos os seus dados está de volta ao
de volta para trás em memory-- literalmente

1474
01:10:52,400 --> 01:10:56,830
Um byte ou talvez quatro bytes,
um número fixo de bytes de distância.

1475
01:10:56,830 --> 01:11:00,710
Em uma lista ligada, o que poderíamos chamar
assim, debaixo do capô que

1476
01:11:00,710 --> 01:11:02,000
sabe onde esse material é?

1477
01:11:02,000 --> 01:11:03,630
Ele nem sequer precisam fluir como este.

1478
01:11:03,630 --> 01:11:06,050
Alguns dos dados pode ser
de volta para a esquerda até lá.

1479
01:11:06,050 --> 01:11:07,530
Você nem sequer sabe.

1480
01:11:07,530 --> 01:11:15,430
>> E assim, com uma matriz, você tem um
recurso conhecido como acesso aleatório.

1481
01:11:15,430 --> 01:11:20,570
E o que os meios de acesso aleatório é
que o computador pode saltar instantaneamente

1482
01:11:20,570 --> 01:11:22,730
para qualquer local em uma matriz.

1483
01:11:22,730 --> 01:11:23,580
Por quê?

1484
01:11:23,580 --> 01:11:26,000
Porque o computador sabe
que é a primeira localização

1485
01:11:26,000 --> 01:11:29,540
zero, um, dois e três.

1486
01:11:29,540 --> 01:11:33,890
>> E então se você quiser ir de
este elemento para o elemento seguinte,

1487
01:11:33,890 --> 01:11:36,099
você literalmente, na
A mente de computador, basta adicionar um.

1488
01:11:36,099 --> 01:11:39,140
Se você quer ir para o terceiro elemento,
basta adicionar um-- próximo elemento, apenas

1489
01:11:39,140 --> 01:11:40,290
Adicione um.

1490
01:11:40,290 --> 01:11:42,980
No entanto, nesta versão
da história, suponha

1491
01:11:42,980 --> 01:11:46,080
o computador está visitando
ou em lidar com o número 100.

1492
01:11:46,080 --> 01:11:49,770
Como você chegar ao próximo
grau no livro de notas?

1493
01:11:49,770 --> 01:11:52,560
>> Você tem que tomar sete
etapas, que é arbitrária.

1494
01:11:52,560 --> 01:11:58,120
Para chegar ao próximo, você tem que
levar mais oito passos para chegar a 15.

1495
01:11:58,120 --> 01:12:02,250
Em outras palavras, não é um
lacuna constante entre os números,

1496
01:12:02,250 --> 01:12:04,857
e por isso só leva o
computador mais tempo é o ponto.

1497
01:12:04,857 --> 01:12:06,940
O computador tem de procurar
através da memória, a fim

1498
01:12:06,940 --> 01:12:08,990
para encontrar o que você está procurando.

1499
01:12:08,990 --> 01:12:14,260
>> Assim, enquanto uma matriz tende a ser um
structure-- rápida de dados porque você

1500
01:12:14,260 --> 01:12:17,610
pode literalmente apenas fazer aritmética simples
e chegar onde você quer pela adição de um,

1501
01:12:17,610 --> 01:12:21,300
para instance-- uma lista ligada,
você sacrifica esse recurso.

1502
01:12:21,300 --> 01:12:24,020
Você não pode simplesmente ir de primeira
para a segunda a terceira para a quarta.

1503
01:12:24,020 --> 01:12:25,240
Você tem que seguir o mapa.

1504
01:12:25,240 --> 01:12:28,160
Você tem que tomar mais medidas
para chegar a esses valores, que

1505
01:12:28,160 --> 01:12:30,230
parece ser a adição de um custo.

1506
01:12:30,230 --> 01:12:35,910
Então, nós estamos pagando um preço, mas o que era
o recurso que Dan estava procurando aqui?

1507
01:12:35,910 --> 01:12:38,110
O que faz uma lista ligada
aparentemente, nos permitem fazer,

1508
01:12:38,110 --> 01:12:40,240
qual foi a origem da
esta história em particular?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Exatamente.

1511
01:12:43,830 --> 01:12:46,220
Um tamanho dinâmico para isso.

1512
01:12:46,220 --> 01:12:48,040
Podemos acrescentar a esta lista.

1513
01:12:48,040 --> 01:12:51,430
Podemos até mesmo diminuir a lista, para
que só está usando o máximo de memória

1514
01:12:51,430 --> 01:12:55,560
como nós queremos realmente e assim
estamos nunca over-reparte.

1515
01:12:55,560 --> 01:12:58,470
>> Agora é só para ser realmente nit-exigente,
há um custo escondido.

1516
01:12:58,470 --> 01:13:01,980
Então você não deve me deixar convencer
que este é um compromisso convincente.

1517
01:13:01,980 --> 01:13:04,190
Há um outro custo escondido aqui.

1518
01:13:04,190 --> 01:13:06,550
O benefício, para ser claro,
é que nós começamos dinamismo.

1519
01:13:06,550 --> 01:13:10,359
Se eu quiser um outro elemento, só pode
desenhá-lo e colocar um número lá.

1520
01:13:10,359 --> 01:13:12,150
E então eu posso ligá-la
com uma imagem aqui,

1521
01:13:12,150 --> 01:13:14,970
enquanto aqui, novamente, se eu tenho
pintou-me em um canto,

1522
01:13:14,970 --> 01:13:19,410
se alguma coisa já está usando
a memória aqui, estou fora da sorte.

1523
01:13:19,410 --> 01:13:21,700
Pintei-me para o canto.

1524
01:13:21,700 --> 01:13:24,390
>> Mas o que é o oculto
custar nesta foto?

1525
01:13:24,390 --> 01:13:27,690
Não é apenas a quantidade
de tempo que leva

1526
01:13:27,690 --> 01:13:29,870
para ir daqui até aqui,
que é de sete passos, em seguida

1527
01:13:29,870 --> 01:13:32,820
oito etapas, que é mais do que um.

1528
01:13:32,820 --> 01:13:34,830
O que é um outro custo oculto?

1529
01:13:34,830 --> 01:13:35,440
Não apenas tempo.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Informações adicionais estão
necessário para atingir esse quadro.

1532
01:13:49,940 --> 01:13:53,210
>> Sim, esse mapa, esses pequenos pedaços de
papel, como eu manter descrevendo-os como.

1533
01:13:53,210 --> 01:13:55,650
Estes arrows-- aqueles que não são livres.

1534
01:13:55,650 --> 01:13:57,660
A Computador-- você sabe
o que um computador tem.

1535
01:13:57,660 --> 01:13:58,790
Ele tem zeros e uns.

1536
01:13:58,790 --> 01:14:03,170
Se você deseja representar uma flecha ou um
mapear ou um número, você precisa de alguma memória.

1537
01:14:03,170 --> 01:14:05,950
Então, no outro preço que você
pagar por uma lista ligada,

1538
01:14:05,950 --> 01:14:09,070
a ciência da computação comum
de recursos, é também espaço.

1539
01:14:09,070 --> 01:14:11,710
>> E de fato assim, tão comumente,
Entre as compensações

1540
01:14:11,710 --> 01:14:15,580
na concepção de engenharia de software
sistemas é o tempo e espaço--

1541
01:14:15,580 --> 01:14:18,596
são dois dos seus ingredientes, dois
dos seus ingredientes mais caros.

1542
01:14:18,596 --> 01:14:21,220
Isso está me custando mais tempo
porque eu tenho que siga este mapa,

1543
01:14:21,220 --> 01:14:25,730
mas também está me custando mais espaço
porque eu tenho que manter este mapa ao redor.

1544
01:14:25,730 --> 01:14:28,730
Assim, a esperança, como nós tipo de
discutido sobre ontem e hoje,

1545
01:14:28,730 --> 01:14:31,720
é que os benefícios
irá superam os custos.

1546
01:14:31,720 --> 01:14:33,870
>> Mas não há nenhuma solução óbvia aqui.

1547
01:14:33,870 --> 01:14:35,870
Talvez seja melhor--
a la rápida e suja,

1548
01:14:35,870 --> 01:14:38,660
como Kareem proposta earlier--
para jogar memória ao problema.

1549
01:14:38,660 --> 01:14:42,520
Basta comprar mais memória, pensar menos
duro sobre como resolver o problema,

1550
01:14:42,520 --> 01:14:44,595
e resolvê-lo de uma forma mais fácil.

1551
01:14:44,595 --> 01:14:46,720
E, de fato antes, quando
falamos sobre compensações,

1552
01:14:46,720 --> 01:14:49,190
não havia espaço em
o computador e tempo.

1553
01:14:49,190 --> 01:14:51,810
Era hora desenvolvedor, que
é ainda um outro recurso.

1554
01:14:51,810 --> 01:14:54,829
>> Então, novamente, é este ato de equilíbrio
tentando decidir qual dessas coisas

1555
01:14:54,829 --> 01:14:55,870
você está disposto a gastar?

1556
01:14:55,870 --> 01:14:57,380
Qual é o menos caro?

1557
01:14:57,380 --> 01:15:01,040
Que produz os melhores resultados?

1558
01:15:01,040 --> 01:15:01,540
Sim?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> De fato.

1561
01:15:12,580 --> 01:15:15,970
Neste caso, se você estiver
representando números na maps--

1562
01:15:15,970 --> 01:15:18,820
estes são chamados em muitas línguas
"ponteiros" ou "endereços" -

1563
01:15:18,820 --> 01:15:20,390
que é o dobro do espaço.

1564
01:15:20,390 --> 01:15:24,390
Isso não precisa ser tão ruim quanto o dobro se
agora nós estamos apenas armazenar números.

1565
01:15:24,390 --> 01:15:27,410
Suponha que estavam armazenando
registros de pacientes em um hospital--

1566
01:15:27,410 --> 01:15:30,870
assim nomes de Pierson, números de telefone,
números de segurança social, médico

1567
01:15:30,870 --> 01:15:31,540
história.

1568
01:15:31,540 --> 01:15:34,160
Esta caixa pode ser muito,
muito maior, em cujo caso

1569
01:15:34,160 --> 01:15:38,000
um pouco ponteiro minúsculo, o endereço do
a próxima element-- não é um grande negócio.

1570
01:15:38,000 --> 01:15:40,620
É um tal franja
custo, não importa.

1571
01:15:40,620 --> 01:15:43,210
Mas neste caso, sim, é uma duplicação.

1572
01:15:43,210 --> 01:15:45,290
Boa pergunta.

1573
01:15:45,290 --> 01:15:47,900
>> Vamos falar sobre o tempo que um
pouco mais concretamente.

1574
01:15:47,900 --> 01:15:50,380
Qual é o tempo de execução
de pesquisar esta lista?

1575
01:15:50,380 --> 01:15:53,640
Suponha que eu queria para procurar
através de todas as notas dos alunos,

1576
01:15:53,640 --> 01:15:55,980
e há n graus
nesta estrutura de dados.

1577
01:15:55,980 --> 01:15:58,830
Aqui, também, podemos tomar emprestado
o vocabulário da anterior.

1578
01:15:58,830 --> 01:16:00,890
Esta é uma estrutura de dados linear.

1579
01:16:00,890 --> 01:16:04,570
>> Big O de n é o que é necessário para obter
para o fim da presente estrutura de dados,

1580
01:16:04,570 --> 01:16:08,410
whereas-- e não vimos
este antes-- uma matriz dá-lhe

1581
01:16:08,410 --> 01:16:13,555
o que é chamado de tempo constante, o que significa
um passo ou dois passos ou 10 steps--

1582
01:16:13,555 --> 01:16:14,180
não importa.

1583
01:16:14,180 --> 01:16:15,440
É um número fixo.

1584
01:16:15,440 --> 01:16:17,440
Não tem nada a ver com
o tamanho da matriz.

1585
01:16:17,440 --> 01:16:20,130
E a razão para isso,
mais uma vez, é de acesso aleatório.

1586
01:16:20,130 --> 01:16:23,180
O computador pode apenas imediatamente
saltar para outro local,

1587
01:16:23,180 --> 01:16:27,770
porque eles são todos iguais
distância de tudo o resto.

1588
01:16:27,770 --> 01:16:29,112
Não há nenhum pensamento envolvido.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Tudo certo.

1591
01:16:32,400 --> 01:16:39,230
Então, se eu puder, deixe-me tentar
pintar dois quadros finais.

1592
01:16:39,230 --> 01:16:42,830
Um muito comum conhecida como uma tabela hash.

1593
01:16:42,830 --> 01:16:51,120
Então, para motivar a discussão,
deixe-me pensar sobre como fazer isso.

1594
01:16:51,120 --> 01:16:52,610
>> Assim como sobre isso?

1595
01:16:52,610 --> 01:16:55,160
Suponha-se que o problema
queremos resolver agora

1596
01:16:55,160 --> 01:16:58,360
está a implementar em um dictionary--
por isso um monte de palavras em inglês

1597
01:16:58,360 --> 01:16:59,330
como queiras.

1598
01:16:59,330 --> 01:17:02,724
E o objectivo é o de ser capaz de responder
perguntas do formulário esta é uma palavra?

1599
01:17:02,724 --> 01:17:04,640
Então você quer implementar
um corretor ortográfico, apenas

1600
01:17:04,640 --> 01:17:07,220
como um dicionário física
que você pode olhar as coisas em.

1601
01:17:07,220 --> 01:17:10,490
Suponha que eu fosse fazer isso com uma matriz.

1602
01:17:10,490 --> 01:17:12,590
Eu poderia fazer isso.

1603
01:17:12,590 --> 01:17:20,756
>> E supor que as palavras são de maçã
e banana e melão.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
E eu não posso pensar de frutas
que começam com d, então estamos apenas

1606
01:17:26,465 --> 01:17:27,590
vai ter três frutas.

1607
01:17:27,590 --> 01:17:31,510
Portanto, este é um array, e estamos
armazenar todas estas palavras

1608
01:17:31,510 --> 01:17:34,200
neste dicionário como uma matriz.

1609
01:17:34,200 --> 01:17:39,350
A questão, então, é de que outra forma
você pode armazenar esta informação?

1610
01:17:39,350 --> 01:17:43,160
>> Bem, eu sou o tipo de batota aqui, porque
cada uma dessas letras da palavra

1611
01:17:43,160 --> 01:17:44,490
é realmente um byte individual.

1612
01:17:44,490 --> 01:17:46,740
Então, se eu realmente queria ser
nit-exigente, eu realmente deveria

1613
01:17:46,740 --> 01:17:49,600
ser dividindo este se em muito
pequenos pedaços de memória,

1614
01:17:49,600 --> 01:17:51,289
e poderíamos fazer exatamente isso.

1615
01:17:51,289 --> 01:17:53,580
Mas nós estamos indo funcionar em
o mesmo problema que antes.

1616
01:17:53,580 --> 01:17:56,674
E se, como Merriam Webster ou Oxford
faz cada ano-- que adicionar palavras

1617
01:17:56,674 --> 01:17:59,340
ao dictionary-- nós não
necessariamente quer nos pintar

1618
01:17:59,340 --> 01:18:00,780
em um canto com uma matriz?

1619
01:18:00,780 --> 01:18:05,710
>> Então, ao invés, talvez uma abordagem mais inteligente
é colocar a maçã no seu próprio nó ou caixa,

1620
01:18:05,710 --> 01:18:11,190
como diríamos, banana, e
então aqui temos melão.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
E corda que essas coisas juntas.

1623
01:18:16,790 --> 01:18:19,980
Portanto, esta é a matriz, e
esta é a lista ligada.

1624
01:18:19,980 --> 01:18:23,300
Se você não consegue ver, ele só
diz "matriz", e isso diz "lista."

1625
01:18:23,300 --> 01:18:25,780
>> Portanto, temos a mesma
questões exatas como antes,

1626
01:18:25,780 --> 01:18:28,600
pelo qual agora temos
dinamismo na nossa lista ligada.

1627
01:18:28,600 --> 01:18:31,090
Mas temos um dicionário bastante lento.

1628
01:18:31,090 --> 01:18:32,870
Suponha que eu queira procurar uma palavra.

1629
01:18:32,870 --> 01:18:35,430
Pode me levar grande O de n
passos, porque a palavra pode

1630
01:18:35,430 --> 01:18:37,840
ser todo o caminho no final de
a lista, como melão.

1631
01:18:37,840 --> 01:18:40,600
E verifica-se que
na programação, sort

1632
01:18:40,600 --> 01:18:42,700
do santo graal dos dados
estruturas, é algo

1633
01:18:42,700 --> 01:18:46,620
que lhe dá constante
tempo como uma matriz

1634
01:18:46,620 --> 01:18:50,870
mas que ainda lhe dá dinamismo.

1635
01:18:50,870 --> 01:18:52,940
>> Assim, podemos ter o melhor dos dois mundos?

1636
01:18:52,940 --> 01:18:55,570
E, de fato, há algo
chamada tabela hash

1637
01:18:55,570 --> 01:18:59,320
que permite que você faça exatamente
que, ainda que aproximadamente.

1638
01:18:59,320 --> 01:19:03,140
Uma tabela é um columbófilo
estrutura de dados que nós

1639
01:19:03,140 --> 01:19:06,340
pode pensar em como a
combinação de um array--

1640
01:19:06,340 --> 01:19:12,390
e eu vou desenhá-lo
como isto-- e listas ligadas

1641
01:19:12,390 --> 01:19:17,310
que eu vou desenhar como este aqui.

1642
01:19:17,310 --> 01:19:19,760
>> E a maneira como essa coisa
obras é como se segue.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Se este agora-- de hash mesa--
é minha estrutura de dados de terceira,

1645
01:19:29,540 --> 01:19:32,590
e eu quero armazenar
palavras neste, eu não faço

1646
01:19:32,590 --> 01:19:35,440
quero apenas armazenar todas as
palavras de volta para trás a volta para trás.

1647
01:19:35,440 --> 01:19:37,430
Quero aproveitar algumas
pedaço de informação

1648
01:19:37,430 --> 01:19:40,330
sobre as palavras que lhe permitirão
me obtê-lo onde é mais rápido.

1649
01:19:40,330 --> 01:19:43,666
>> Assim, dada a maçã palavras
e banana e melão,

1650
01:19:43,666 --> 01:19:45,040
Eu deliberadamente escolheu essas palavras.

1651
01:19:45,040 --> 01:19:45,340
Por quê?

1652
01:19:45,340 --> 01:19:47,631
O que é uma espécie de fundamentalmente
diferente sobre os três?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Qual é o óbvio?

1655
01:19:51,484 --> 01:19:52,900
Eles começam com letras diferentes.

1656
01:19:52,900 --> 01:19:53,900
>> Então você sabe o quê?

1657
01:19:53,900 --> 01:19:57,120
Em vez de colocar todas as minhas palavras
o mesmo balde, por assim dizer,

1658
01:19:57,120 --> 01:20:00,390
como em uma lista grande, por que não fazer
Eu, pelo menos, tentar uma otimização

1659
01:20:00,390 --> 01:20:04,180
e fazer minhas listas de 1/26 do tempo.

1660
01:20:04,180 --> 01:20:07,440
A otimização convincente
pode ser por que não fazer

1661
01:20:07,440 --> 01:20:10,650
Eu-- ao inserir uma palavra
para essa estrutura de dados,

1662
01:20:10,650 --> 01:20:14,300
na memória do computador, por isso
Não coloquei todas as palavras "a" aqui,

1663
01:20:14,300 --> 01:20:17,270
tudo 'B' palavras aqui,
e todos os "c" palavras aqui?

1664
01:20:17,270 --> 01:20:24,610
Então isso acaba colocando uma maçã
aqui, banana aqui, melão aqui,

1665
01:20:24,610 --> 01:20:25,730
e assim por diante.

1666
01:20:25,730 --> 01:20:31,700
>> E se eu tiver um adicional
palavra como-- o que é outro?

1667
01:20:31,700 --> 01:20:36,640
Maçã, banana, pêra.

1668
01:20:36,640 --> 01:20:39,370
Qualquer um pensa de uma fruta
que começa com a, b, ou c?

1669
01:20:39,370 --> 01:20:40,570
perfeita Blueberry--.

1670
01:20:40,570 --> 01:20:43,990
Isso vai acabar aqui.

1671
01:20:43,990 --> 01:20:47,530
E assim parece que temos um
marginalmente melhor solução,

1672
01:20:47,530 --> 01:20:50,820
porque agora se eu quiser
para procurar maçã, I

1673
01:20:50,820 --> 01:20:53,200
first-- Eu não apenas mergulho
em minha estrutura de dados.

1674
01:20:53,200 --> 01:20:54,850
Eu não mergulho na memória do meu computador.

1675
01:20:54,850 --> 01:20:56,530
I primeiro olhar para a primeira letra.

1676
01:20:56,530 --> 01:20:58,610
>> E isso é o que um computador
cientista diria.

1677
01:20:58,610 --> 01:21:00,760
Você botar em sua estrutura de dados.

1678
01:21:00,760 --> 01:21:04,100
Você toma sua entrada, o que,
neste caso, é uma palavra como maçã.

1679
01:21:04,100 --> 01:21:07,150
Você analisá-lo, olhando para
a primeira letra neste caso,

1680
01:21:07,150 --> 01:21:08,340
hashing-o assim.

1681
01:21:08,340 --> 01:21:10,950
Hashing é um termo geral em que
você toma algo como entrada

1682
01:21:10,950 --> 01:21:12,116
e você produzir alguma saída.

1683
01:21:12,116 --> 01:21:15,090
E a saída em que
caso é a localização

1684
01:21:15,090 --> 01:21:18,150
você deseja pesquisar, o primeiro
local, segundo local, a terceira.

1685
01:21:18,150 --> 01:21:22,160
Assim, a entrada é de maçã,
a saída é em primeiro lugar.

1686
01:21:22,160 --> 01:21:25,054
A entrada é de banana, o
saída deve ser segundo.

1687
01:21:25,054 --> 01:21:27,220
A entrada é melão,
a saída deve ser o terceiro.

1688
01:21:27,220 --> 01:21:30,320
A entrada é de mirtilo, o
saída deve voltar a ser segundo.

1689
01:21:30,320 --> 01:21:34,010
E é isso que ajuda a tirar
atalhos através de sua memória

1690
01:21:34,010 --> 01:21:39,050
a fim de obter a palavras
ou dados de forma mais eficaz.

1691
01:21:39,050 --> 01:21:43,330
>> Agora, isso reduz nosso tempo potencialmente
por tanto como um de 26,

1692
01:21:43,330 --> 01:21:45,850
porque se você assumir que você
ter tantos "a" palavras como "z"

1693
01:21:45,850 --> 01:21:48,080
palavras como palavras "q", que
não é realmente realistic--

1694
01:21:48,080 --> 01:21:50,830
você vai ter a inclinação do outro lado
certas letras do alphabet--

1695
01:21:50,830 --> 01:21:53,204
mas isso seria um incremental
abordagem que não permite

1696
01:21:53,204 --> 01:21:55,930
-lo a obter a palavras muito mais rapidamente.

1697
01:21:55,930 --> 01:21:59,660
E, na realidade, um sofisticado
programa, os Googles do mundo,

1698
01:21:59,660 --> 01:22:02,180
o Facebooks do mundo--
eles usariam uma tabela hash

1699
01:22:02,180 --> 01:22:03,740
para uma série de finalidades diferentes.

1700
01:22:03,740 --> 01:22:06,590
Mas eles não seria tão ingênuo
basta olhar para a primeira letra

1701
01:22:06,590 --> 01:22:09,700
na maçã ou banana ou
pêra ou melão,

1702
01:22:09,700 --> 01:22:13,420
porque como você pode ver esses
listas ainda podia começar por muito tempo.

1703
01:22:13,420 --> 01:22:17,130
>> E por isso este pode ainda ser tipo
de linear-- tão espécie de lento,

1704
01:22:17,130 --> 01:22:19,980
como com o grande O de n
que discutimos anteriormente.

1705
01:22:19,980 --> 01:22:25,290
Então, o que um verdadeiro tabela hash boa vontade
fazer-- ele terá uma variedade muito maior.

1706
01:22:25,290 --> 01:22:28,574
E vai usar um muito mais
função de hash sofisticado,

1707
01:22:28,574 --> 01:22:30,240
de modo que não basta olhar para o "a".

1708
01:22:30,240 --> 01:22:35,480
Talvez ele olha para "a-p-p-l-e" e
de alguma forma, converte essas cinco letras

1709
01:22:35,480 --> 01:22:38,400
no local onde
maçã deve ser armazenado.

1710
01:22:38,400 --> 01:22:42,660
Estamos apenas ingenuamente usando a letra 'a'
sozinho, porque é agradável e simples.

1711
01:22:42,660 --> 01:22:44,600
>> Mas uma tabela hash, em
Ao final, você pode pensar

1712
01:22:44,600 --> 01:22:47,270
como uma combinação de
uma matriz, cada um dos quais

1713
01:22:47,270 --> 01:22:51,700
tem uma lista vinculada que idealmente
deverá ser tão curto quanto possível.

1714
01:22:51,700 --> 01:22:54,364
E isso não é uma solução óbvia.

1715
01:22:54,364 --> 01:22:57,280
De facto, grande parte da sintonização fina
o que se passa debaixo do capô quando

1716
01:22:57,280 --> 01:22:59,654
implementar esses tipos de
estruturas de dados sofisticados

1717
01:22:59,654 --> 01:23:01,640
é o que é o direito
comprimento da matriz?

1718
01:23:01,640 --> 01:23:03,250
Qual é a função hash certo?

1719
01:23:03,250 --> 01:23:04,830
Como você armazenar coisas na memória?

1720
01:23:04,830 --> 01:23:07,249
>> Mas perceber o quão rapidamente
este tipo de discussão

1721
01:23:07,249 --> 01:23:10,540
escalada, seja tão longe que é uma espécie
de sobre a cabeça neste momento, que

1722
01:23:10,540 --> 01:23:11,360
está bem.

1723
01:23:11,360 --> 01:23:18,820
Mas nós começamos, recall, com verdadeiramente
algo de baixo nível e electrónicos.

1724
01:23:18,820 --> 01:23:20,819
E assim este novo é este
tema da abstração,

1725
01:23:20,819 --> 01:23:23,610
onde uma vez que você começar a tomar para
concedido, OK, eu tenho ele-- há

1726
01:23:23,610 --> 01:23:26,680
memória física, OK, tem, cada
localização física tem um endereço,

1727
01:23:26,680 --> 01:23:29,910
OK, I got it, I pode representar
esses endereços como arrows--

1728
01:23:29,910 --> 01:23:34,650
você pode rapidamente começar a ter
conversas mais sofisticados que

1729
01:23:34,650 --> 01:23:38,360
no final parecem estar nos permitindo
para resolver problemas como pesquisar

1730
01:23:38,360 --> 01:23:41,620
e triagem de forma mais eficaz.

1731
01:23:41,620 --> 01:23:44,190
E com certeza, demasiado--
porque eu acho que isso

1732
01:23:44,190 --> 01:23:48,700
é o mais profundo nós fomos em algum
destes tópicos CS proper-- Nós

1733
01:23:48,700 --> 01:23:51,880
feito em um dia e uma metade neste
apontar o que você pode geralmente fazer mais

1734
01:23:51,880 --> 01:23:55,520
o curso de oito semanas em um semestre.

1735
01:23:55,520 --> 01:23:59,670
>> Quaisquer perguntas sobre estes?

1736
01:23:59,670 --> 01:24:01,100
Não?

1737
01:24:01,100 --> 01:24:01,940
Tudo certo.

1738
01:24:01,940 --> 01:24:05,610
Bem, por que não fazemos uma pausa lá,
iniciar o almoço alguns minutos mais cedo,

1739
01:24:05,610 --> 01:24:07,052
retomar em apenas cerca de uma hora?

1740
01:24:07,052 --> 01:24:08,760
E eu vou durar
um pouco com perguntas.

1741
01:24:08,760 --> 01:24:11,343
Então eu vou ter que ir
levar algumas chamadas, se está tudo OK.

1742
01:24:11,343 --> 01:24:15,000
Vou ligar uma música, entretanto,
mas o almoço deve ser ao virar da esquina.

1743
01:24:15,000 --> 01:24:17,862