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

2
00:00:00,030 --> 00:00:00,460
>> DAVID MALAN: Va bene.

3
00:00:00,460 --> 00:00:01,094
Siamo tornati.

4
00:00:01,094 --> 00:00:04,260
Quindi, in questo segmento sulla programmazione quello
Ho pensato di fare è un mix di cose.

5
00:00:04,260 --> 00:00:06,340
Uno, fare un po '
di qualcosa di hands-on,

6
00:00:06,340 --> 00:00:08,690
anche se con un più giocoso
environment-- programmazione

7
00:00:08,690 --> 00:00:11,620
uno che è dimostrativo
esattamente il tipo di idee

8
00:00:11,620 --> 00:00:14,220
abbiamo parlato,
ma un po 'più formale.

9
00:00:14,220 --> 00:00:18,200
Due, un'occhiata ad alcune delle
modi più tecnici

10
00:00:18,200 --> 00:00:21,520
che un programmatore potrebbe effettivamente risolvere
problemi come il problema ricerca

11
00:00:21,520 --> 00:00:24,530
che abbiamo guardato prima e
anche una più fondamentalmente

12
00:00:24,530 --> 00:00:26,020
interessante problema di ordinare.

13
00:00:26,020 --> 00:00:28,840
>> Abbiamo appena assunto da ottenere andare
che tale rubrica è stato risolto,

14
00:00:28,840 --> 00:00:31,980
ma che da sola è in realtà una specie di
problema difficile con molti modi diversi

15
00:00:31,980 --> 00:00:32,479
per risolverlo.

16
00:00:32,479 --> 00:00:34,366
Così useremo questi come
una classe di problemi

17
00:00:34,366 --> 00:00:36,740
rappresentante di cose che
potrebbe essere risolto in generale.

18
00:00:36,740 --> 00:00:38,980
E poi parleremo
circa in dettaglio cosa

19
00:00:38,980 --> 00:00:42,360
sono chiamati dati structures--
modi fantasiosi come le liste collegate

20
00:00:42,360 --> 00:00:46,290
e tabelle hash e alberi che
un programmatore sarebbe in realtà

21
00:00:46,290 --> 00:00:48,890
utilizzare e generalmente usare
su una lavagna per dipingere

22
00:00:48,890 --> 00:00:51,840
una foto di quello che lui o lei
prevede per l'attuazione

23
00:00:51,840 --> 00:00:52,980
qualche pezzo di software.

24
00:00:52,980 --> 00:00:55,130
>> Allora, facciamo gli hands-on parte prima.

25
00:00:55,130 --> 00:01:00,090
Quindi, solo mettere le mani sporche con una
ambiente chiamato scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Questo è uno strumento che usiamo
nella nostra classe di laurea.

27
00:01:02,636 --> 00:01:04,510
Anche se è stato progettato
per le età 12 anni in su,

28
00:01:04,510 --> 00:01:07,570
lo usiamo per il up
parte di quel piuttosto un po '

29
00:01:07,570 --> 00:01:10,020
dal momento che è una bella, divertente
modo grafico di apprendimento

30
00:01:10,020 --> 00:01:12,160
un po 'qualcosa sulla programmazione.

31
00:01:12,160 --> 00:01:17,600
Quindi testa a questo URL, dove si
dovrebbe vedere una pagina abbastanza come questo,

32
00:01:17,600 --> 00:01:23,330
e andare avanti e fare clic
Partecipa Scratch in alto a destra

33
00:01:23,330 --> 00:01:28,300
e scegliere un nome utente e una
la password e, infine, farti

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

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

36
00:01:32,165 --> 00:01:34,665
Ho pensato di usare questo come
possibilità prima di mostrare questo.

37
00:01:34,665 --> 00:01:39,120
Una domanda si avvicinò durante la pausa
su quale codice si presenta come.

38
00:01:39,120 --> 00:01:41,315
E parlavamo
durante la pausa su C,

39
00:01:41,315 --> 00:01:45,060
in particolare una particular--
livello più basso in un linguaggio più vecchio.

40
00:01:45,060 --> 00:01:47,750
E ho appena fatto un rapido
Google cerca di trovare il codice C

41
00:01:47,750 --> 00:01:51,574
per la ricerca binaria, l'algoritmo che
utilizzato per la ricerca che rubrica in precedenza.

42
00:01:51,574 --> 00:01:54,240
Questo esempio particolare, naturalmente,
non cercare una rubrica telefonica.

43
00:01:54,240 --> 00:01:57,840
E 'appena cerca un insieme di
numeri nella memoria del computer.

44
00:01:57,840 --> 00:02:01,000
Ma se si desidera solo ottenere una visuale
senso di ciò che una programmazione vera e propria

45
00:02:01,000 --> 00:02:05,370
il linguaggio sembra, sembra
un po 'di qualcosa come questo.

46
00:02:05,370 --> 00:02:09,759
Quindi si tratta di 20-plus,
Circa 30 righe di codice,

47
00:02:09,759 --> 00:02:12,640
ma la conversazione che abbiamo
stavano avendo più di pausa

48
00:02:12,640 --> 00:02:16,000
era circa come questo in realtà
viene trasformato in zero e uno

49
00:02:16,000 --> 00:02:19,200
e se non si può semplicemente tornare che
elaborare e passare da zeri e quelli

50
00:02:19,200 --> 00:02:20,210
tornare al codice.

51
00:02:20,210 --> 00:02:22,620
>> Purtroppo, il processo
è così trasformativa

52
00:02:22,620 --> 00:02:24,890
che è molto più facile a dirsi che a farsi.

53
00:02:24,890 --> 00:02:29,400
Sono andato avanti e realtà si
quel programma, Binary Search,

54
00:02:29,400 --> 00:02:32,700
in zero e uno, sotto forma di
programma chiamato al compilatore che ho

55
00:02:32,700 --> 00:02:34,400
capita di avere qui a destra sul mio Mac.

56
00:02:34,400 --> 00:02:37,850
E se si guarda lo schermo
qui, concentrandosi in particolare

57
00:02:37,850 --> 00:02:43,520
nelle centrali sei colonne soltanto,
vedrete solo zero e uno.

58
00:02:43,520 --> 00:02:48,290
E questi sono gli zeri e quelli che
comporre esattamente questo programma di ricerca.

59
00:02:48,290 --> 00:02:53,720
>> E così ogni pezzo di cinque bit,
ogni byte di zero e uno qui,

60
00:02:53,720 --> 00:02:57,310
rappresentare una certa istruzione
tipicamente all'interno di un computer.

61
00:02:57,310 --> 00:03:00,730
E infatti, se hai sentito il
commercializzazione slogan "Intel inside" - che,

62
00:03:00,730 --> 00:03:04,610
Naturalmente, solo significa avere un
CPU Intel o il cervello all'interno del computer.

63
00:03:04,610 --> 00:03:08,000
E che cosa significa essere una CPU è
che si dispone di un set di istruzioni,

64
00:03:08,000 --> 00:03:08,840
per così dire.

65
00:03:08,840 --> 00:03:11,620
>> Ogni CPU nel mondo, molti
li ha fatti da Intel in questi giorni,

66
00:03:11,620 --> 00:03:13,690
comprende un finita
numero di istruzioni.

67
00:03:13,690 --> 00:03:18,690
E tali istruzioni sono così basso livello
come aggiungere questi due numeri insieme,

68
00:03:18,690 --> 00:03:22,560
moltiplicare questi due numeri insieme,
spostare questo pezzo di dati da qui

69
00:03:22,560 --> 00:03:27,340
di qui nella memoria, salvare questo
informazioni da qui a qui in memoria,

70
00:03:27,340 --> 00:03:32,200
e così forth-- quindi molto, molto
di basso livello, i dettagli quasi elettroniche.

71
00:03:32,200 --> 00:03:34,780
Ma con quelle matematica
operazioni accoppiato

72
00:03:34,780 --> 00:03:37,410
con quello che abbiamo discusso in precedenza,
la rappresentazione dei dati

73
00:03:37,410 --> 00:03:40,450
come zero e uno, in grado di
si costruisce tutto

74
00:03:40,450 --> 00:03:44,180
che un computer può fare oggi, se
è testuale, grafico, musicale,

75
00:03:44,180 --> 00:03:45,580
o altrimenti.

76
00:03:45,580 --> 00:03:49,450
>> Quindi questo è molto facile da ottenere
ha perso le erbacce di fretta.

77
00:03:49,450 --> 00:03:52,150
E ci sono un sacco di
sfide sintattiche

78
00:03:52,150 --> 00:03:56,630
per cui se si effettua il più semplice,
più stupida di errori di battitura nessuno del programma

79
00:03:56,630 --> 00:03:57,860
funzionerà sorta.

80
00:03:57,860 --> 00:04:00,366
E così invece di utilizzare un
linguaggio come C questa mattina,

81
00:04:00,366 --> 00:04:02,240
Ho pensato che sarebbe stato
più divertente da fare in realtà

82
00:04:02,240 --> 00:04:04,840
qualcosa più visivo, che
mentre progettato per i bambini

83
00:04:04,840 --> 00:04:08,079
è in realtà una manifestazione perfetta
di programmazione vera

84
00:04:08,079 --> 00:04:10,370
Language, guarda caso
utilizzare le immagini al posto del testo

85
00:04:10,370 --> 00:04:11,710
per rappresentare quelle idee.

86
00:04:11,710 --> 00:04:15,470
>> Quindi, una volta che hai davvero un
account su scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
fare clic sul pulsante Crea
in alto a sinistra del sito.

88
00:04:21,070 --> 00:04:24,620
E si dovrebbe vedere un ambiente come
quello che sto per vedere sul mio schermo

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

90
00:04:26,310 --> 00:04:29,350
E passeremo solo un po '
po 'di tempo a giocare qui.

91
00:04:29,350 --> 00:04:34,080
Vediamo se non possiamo tutti risolvere alcuni
problemi insieme nel modo seguente.

92
00:04:34,080 --> 00:04:39,420
>> Quindi, quello che vedrete in questo
environment-- e in realtà solo lasciare

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

94
00:04:40,050 --> 00:04:42,680
C'è qualcuno che non qui?

95
00:04:42,680 --> 00:04:45,070
Non qui?

96
00:04:45,070 --> 00:04:45,800
OK.

97
00:04:45,800 --> 00:04:49,030
Quindi, vorrei sottolineare un paio di
caratteristiche di questo ambiente.

98
00:04:49,030 --> 00:04:55,024
>> Così in alto a sinistra dello schermo, abbiamo
hanno fase di Scratch, per così dire.

99
00:04:55,024 --> 00:04:57,440
Scratch non è solo il nome
di questo linguaggio di programmazione;

100
00:04:57,440 --> 00:05:00,356
è anche il nome del gatto che
vedete di default lì in arancione.

101
00:05:00,356 --> 00:05:02,160
È su un palco, così
proprio come ho descritto

102
00:05:02,160 --> 00:05:05,770
la tartaruga in precedenza come essere in un
rettangolare ambiente bordo bianco.

103
00:05:05,770 --> 00:05:09,800
Il mondo di questo gatto è limitato interamente
a quel rettangolo sulla parte superiore là.

104
00:05:09,800 --> 00:05:12,210
>> Nel frattempo, sulla destra
lato qui, è

105
00:05:12,210 --> 00:05:15,610
solo una zona di script, un
tabula rasa, se vuoi.

106
00:05:15,610 --> 00:05:18,590
Questo è dove stiamo andando a scrivere
I nostri programmi in un attimo.

107
00:05:18,590 --> 00:05:22,935
E i mattoni che saremo
utilizzare per scrivere le program-- il puzzle

108
00:05:22,935 --> 00:05:25,310
pezzi, se siete will--
quelli proprio qui in mezzo,

109
00:05:25,310 --> 00:05:27,500
e sono categorizzati
per funzionalità.

110
00:05:27,500 --> 00:05:31,000
Così, per esempio, ho intenzione di andare avanti
e dimostrare almeno uno di questi.

111
00:05:31,000 --> 00:05:33,690
Ho intenzione di andare avanti e fare clic
la categoria di controllo sulla parte superiore.

112
00:05:33,690 --> 00:05:35,720
>> Quindi queste sono le categorie sulla parte superiore.

113
00:05:35,720 --> 00:05:39,410
Ho intenzione di fare clic sulla categoria di controllo.

114
00:05:39,410 --> 00:05:44,020
Piuttosto, ho intenzione di fare clic sui Events
categoria, il primo uno fino all'inizio.

115
00:05:44,020 --> 00:05:47,790
E se si desidera seguire anche
come facciamo questo, sei abbastanza benvenuto a.

116
00:05:47,790 --> 00:05:52,180
Ho intenzione di fare clic e trascinare questo
primo, "quando la bandiera verde cliccato."

117
00:05:52,180 --> 00:05:58,410
E poi ho intenzione di rilasciarlo solo
grosso modo nella parte superiore del mio tabula rasa.

118
00:05:58,410 --> 00:06:01,450
>> E ciò che è bello di Scratch
è che questo pezzo di puzzle, in cui

119
00:06:01,450 --> 00:06:04,560
asservito Puzzle
pezzi, sta per fare letteralmente

120
00:06:04,560 --> 00:06:06,460
ciò che questi pezzi del puzzle dicono di fare.

121
00:06:06,460 --> 00:06:09,710
Così, per esempio, Scratch è giusto
Ora nel mezzo del suo mondo.

122
00:06:09,710 --> 00:06:14,660
Ho intenzione di andare avanti e scegliere
ora, diciamo, la categoria di movimento,

123
00:06:14,660 --> 00:06:18,000
se si desidera fare il
stesso-- categoria Motion.

124
00:06:18,000 --> 00:06:20,430
E ora ho notato un intero
mucchio di pezzi del puzzle qui

125
00:06:20,430 --> 00:06:23,370
che, ancora una volta, tipo di fare quello che dicono.

126
00:06:23,370 --> 00:06:28,110
E ho intenzione di andare avanti e trascinare e
far cadere il blocco mossa giusta qui.

127
00:06:28,110 --> 00:06:31,860
>> E notare che, non appena si ottiene
vicino al fondo della "bandiera verde

128
00:06:31,860 --> 00:06:34,580
cliccato "button, avviso
come appare una linea bianca,

129
00:06:34,580 --> 00:06:36,950
come se fosse quasi
magnetico, si vuole andare lì.

130
00:06:36,950 --> 00:06:43,070
Basta lasciarsi andare, e si aggancerà
insieme e le forme corrisponderanno.

131
00:06:43,070 --> 00:06:46,620
E ora si può forse quasi
indovinare dove stiamo andando con questo.

132
00:06:46,620 --> 00:06:51,570
>> Se si guarda alla fase Scratch
qui e guardare al di sopra di esso,

133
00:06:51,570 --> 00:06:55,142
si vedrà una luce rossa, un
Segnale di stop, e una bandiera verde.

134
00:06:55,142 --> 00:06:57,100
E ho intenzione di andare avanti
e guardare i miei screen--

135
00:06:57,100 --> 00:06:58,460
solo per un momento, se si potesse.

136
00:06:58,460 --> 00:07:01,960
Ho intenzione di fare clic sul
bandiera verde in questo momento,

137
00:07:01,960 --> 00:07:07,850
e si è trasferito quello che sembra essere 10 passi
o 10 pixel, 10 punti, sullo schermo.

138
00:07:07,850 --> 00:07:13,390
>> E quindi non così eccitante,
ma mi permetta di proporre

139
00:07:13,390 --> 00:07:17,440
senza nemmeno insegnare questo, basta
utilizzando il proprio il proprio let intuition--

140
00:07:17,440 --> 00:07:22,560
mi propongo a capire come
rendere Scratch passeggiata proprio dal palco.

141
00:07:22,560 --> 00:07:28,700
Hanno lo far posto sul lato destro della
schermo, fino a destra.

142
00:07:28,700 --> 00:07:32,200
Lasciate che vi dia un attimo
o giù di lì a lottare con quella.

143
00:07:32,200 --> 00:07:37,681
Si potrebbe voler dare un'occhiata
in altre categorie di blocchi.

144
00:07:37,681 --> 00:07:38,180
Tutto ok.

145
00:07:38,180 --> 00:07:41,290
Quindi, solo per ricapitolare, quando abbiamo
la bandiera verde cliccato qui

146
00:07:41,290 --> 00:07:44,850
e spostare 10 passi è la
unica istruzione, ogni volta che

147
00:07:44,850 --> 00:07:46,720
cliccare la bandiera verde, cosa sta succedendo?

148
00:07:46,720 --> 00:07:50,070
Beh, questo è il mio programma in esecuzione.

149
00:07:50,070 --> 00:07:52,450
Così ho potuto fare questo
forse 10 volte manualmente,

150
00:07:52,450 --> 00:07:55,130
ma questo si sente un po '
po 'hacker, per così dire,

151
00:07:55,130 --> 00:07:57,480
per cui io non sono davvero
risolvere il problema.

152
00:07:57,480 --> 00:08:00,530
Sto solo cercando di nuovo e
Ancora e ancora e ancora

153
00:08:00,530 --> 00:08:03,180
fino a quando ho sorta di accidentalmente
conseguire la direttiva

154
00:08:03,180 --> 00:08:05,560
che ho deciso di raggiungere in precedenza.

155
00:08:05,560 --> 00:08:08,200
>> Ma sappiamo dalla nostra
pseudocodice in precedenza che non c'è

156
00:08:08,200 --> 00:08:11,870
questo concetto nella programmazione di looping,
fare qualcosa di nuovo e di nuovo.

157
00:08:11,870 --> 00:08:14,888
E così ho visto che un po 'di te
raggiunto per pezzo ciò puzzle?

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

159
00:08:17,870 --> 00:08:18,730
Ripetere l'operazione fino a quando.

160
00:08:18,730 --> 00:08:21,400
Così abbiamo potuto fare qualcosa
come ripetere fino a quando.

161
00:08:21,400 --> 00:08:23,760
E che cosa si ripete fino a quando esattamente?

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

163
00:08:27,720 --> 00:08:28,540
>> OK.

164
00:08:28,540 --> 00:08:31,974
E mi permetta di andare con uno che è
un po 'più semplice solo per un momento.

165
00:08:31,974 --> 00:08:33,140
Mi permetta di andare avanti e fare questo.

166
00:08:33,140 --> 00:08:35,559
Si noti che, come si può avere
scoperto sotto controllo,

167
00:08:35,559 --> 00:08:38,409
c'è questo blocco di ripetizione, che
non sembra che sia così grande.

168
00:08:38,409 --> 00:08:41,039
Non c'è molto spazio nel
tra queste due linee gialle.

169
00:08:41,039 --> 00:08:43,539
Ma, come alcuni di voi potrebbero avere
notato, se si trascina e goccia,

170
00:08:43,539 --> 00:08:45,150
notare come cresce per riempire la forma.

171
00:08:45,150 --> 00:08:46,274
>> E si può anche riempire di più.

172
00:08:46,274 --> 00:08:48,670
Sarà solo continuare a crescere se
si trascina e si posiziona il mouse sopra di esso.

173
00:08:48,670 --> 00:08:51,110
E io non so che cosa è
meglio qui, in modo da lasciare

174
00:08:51,110 --> 00:08:54,760
me almeno ripetere cinque volte, per
esempio, e poi tornare alla fase

175
00:08:54,760 --> 00:08:56,720
e cliccare la bandiera verde.

176
00:08:56,720 --> 00:08:59,110
E ora notate che non è del tutto lì.

177
00:08:59,110 --> 00:09:02,400
>> Ora alcuni di voi proposti, come
Victoria ha appena fatto, ripetere 10 volte.

178
00:09:02,400 --> 00:09:05,140
E che fa in genere
lui ottenere tutta la strada,

179
00:09:05,140 --> 00:09:10,510
ma non sarebbe esserci una più robusta
modo di arbitrariamente capire

180
00:09:10,510 --> 00:09:12,640
il numero di mosse per fare?

181
00:09:12,640 --> 00:09:17,680
Quale potrebbe essere un blocco di meglio
che ripetere 10 volte essere?

182
00:09:17,680 --> 00:09:20,380
>> Sì, così perché non fare qualcosa per sempre?

183
00:09:20,380 --> 00:09:24,390
E ora mi permetta di spostare questo pezzo di puzzle
all'interno vi e sbarazzarsi di questo.

184
00:09:24,390 --> 00:09:28,300
Ora notate, non importa dove Scratch
inizia, va a bordo.

185
00:09:28,300 --> 00:09:30,700
E per fortuna MIT,
che fa Scratch, basta

186
00:09:30,700 --> 00:09:33,190
si assicura che non ha mai
scompare completamente.

187
00:09:33,190 --> 00:09:35,360
È sempre possibile afferrare la coda.

188
00:09:35,360 --> 00:09:37,680
>> E proprio in modo intuitivo,
perché egli continuare a muoversi?

189
00:09:37,680 --> 00:09:38,892
Che cosa sta succedendo qui?

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

191
00:09:41,440 --> 00:09:43,824
Egli sembra essersi fermato, ma
poi se prendo in mano e trascinare

192
00:09:43,824 --> 00:09:45,240
lui continua a voler andare laggiù.

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

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

195
00:09:51,610 --> 00:09:54,360
In verità, un computer è letteralmente
andando a fare quello che gli si dice di fare.

196
00:09:54,360 --> 00:09:58,380
Quindi, se hai detto in precedenza fare il
cosa seguente per sempre, spostare 10 passi,

197
00:09:58,380 --> 00:10:01,860
sta andando a andare avanti e andare
fino a quando mi ha colpito il segnale di stop rosso

198
00:10:01,860 --> 00:10:04,620
e arrestare il programma del tutto.

199
00:10:04,620 --> 00:10:06,610
>> Quindi, anche se non si è
fare questo, come potrei

200
00:10:06,610 --> 00:10:09,510
rendere Scratch si muovono più velocemente
attraverso lo schermo?

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

202
00:10:12,060 --> 00:10:13,280
Ulteriori passi, giusto?

203
00:10:13,280 --> 00:10:15,710
Così, invece di fare 10
in un momento, perché non

204
00:10:15,710 --> 00:10:20,100
andare avanti e cambiare a--
cosa vorresti propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Così ora ho intenzione di fare clic sul verde
bandiera, e anzi, se ne va veramente veloce.

206
00:10:24,410 --> 00:10:27,180
>> E questo, naturalmente, è solo
una manifestazione di animazione.

207
00:10:27,180 --> 00:10:28,060
Che cosa è l'animazione?

208
00:10:28,060 --> 00:10:33,090
E 'solo che vi mostra l'un essere umano
intero gruppo di immagini fisse in realtà,

209
00:10:33,090 --> 00:10:34,160
molto, molto veloce.

210
00:10:34,160 --> 00:10:36,500
E così, se stiamo solo dicendo
di muoversi più passaggi,

211
00:10:36,500 --> 00:10:39,750
stiamo solo avendo l'effetto sia di
il cambiamento dove si trova sullo schermo

212
00:10:39,750 --> 00:10:42,900
tanto più rapidamente per unità di tempo.

213
00:10:42,900 --> 00:10:46,454
>> Ora la prossima sfida che ho proposto
era quello di avere lui rimbalzare fuori dal bordo.

214
00:10:46,454 --> 00:10:49,120
E senza sapere che cosa di puzzle
pezzi exist-- perché va bene

215
00:10:49,120 --> 00:10:53,030
se non si arriva alla
fase del challenge-- cosa

216
00:10:53,030 --> 00:10:54,280
cosa vuoi fare in modo intuitivo?

217
00:10:54,280 --> 00:10:58,030
Come avremmo lo rimbalzare e
via, tra la sinistra e la destra?

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

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

220
00:11:03,810 --> 00:11:05,680
Quindi abbiamo bisogno di un qualche tipo
di condizioni, e

221
00:11:05,680 --> 00:11:09,710
sembrano avere condizionali, per così
parlare, sotto la categoria di controllo.

222
00:11:09,710 --> 00:11:14,110
Quale di questi blocchi
Non probabilmente vogliamo?

223
00:11:14,110 --> 00:11:15,200
Sì, forse "se, allora."

224
00:11:15,200 --> 00:11:18,780
Quindi notare che tra i blocchi gialli
abbiamo qui, c'è questo "se"

225
00:11:18,780 --> 00:11:23,920
o questo "se, altrimenti" blocco che sarà
ci permettono di prendere una decisione di fare questo

226
00:11:23,920 --> 00:11:25,000
o per farlo.

227
00:11:25,000 --> 00:11:27,380
E si può anche nidificarli
di fare più cose.

228
00:11:27,380 --> 00:11:34,910
Oppure, se non sei ancora andato qui,
andare avanti alla categoria Sensing

229
00:11:34,910 --> 00:11:39,612
e- vediamo se è qui.

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

231
00:11:43,050 --> 00:11:52,050
>> Allora, cosa blocco potrebbe essere utile qui
per rilevare se è dal palco?

232
00:11:52,050 --> 00:11:56,740
Sì, notare che alcuni di questi blocchi
possono essere parametrizzate, per così dire.

233
00:11:56,740 --> 00:12:00,706
Essi possono essere una sorta di personalizzati, non
a differenza di HTML ieri con gli attributi,

234
00:12:00,706 --> 00:12:03,330
dove questi attributi tipo di
personalizzare il comportamento di un tag.

235
00:12:03,330 --> 00:12:08,880
Allo stesso modo qui, posso afferrare questa toccante
blocco e il cambiamento e porre la domanda,

236
00:12:08,880 --> 00:12:11,500
stai toccando il mouse
puntatore come il cursore

237
00:12:11,500 --> 00:12:13,250
o stai toccando il bordo?

238
00:12:13,250 --> 00:12:15,210
>> Quindi, mi permetta di andare e fare questo.

239
00:12:15,210 --> 00:12:18,130
Ho intenzione di diminuire per un istante.

240
00:12:18,130 --> 00:12:21,320
Mi permetta di afferrare questo pezzo di puzzle
qui, questo pezzo di puzzle questo,

241
00:12:21,320 --> 00:12:24,570
e ho intenzione di jumble
li solo per un momento.

242
00:12:24,570 --> 00:12:27,620
Ho intenzione di spostare questo,
cambiare questo a bordo toccante,

243
00:12:27,620 --> 00:12:38,590
e ho intenzione di fare questo movimento.

244
00:12:38,590 --> 00:12:40,490
Quindi, ecco alcuni ingredienti.

245
00:12:40,490 --> 00:12:42,570
Credo di aver avuto tutto quello che voglio.

246
00:12:42,570 --> 00:12:47,710
>> Qualcuno vuole proporre come mi
può collegare questi forse dall'alto verso il basso

247
00:12:47,710 --> 00:12:52,020
al fine di risolvere il problema di avere
Scratch mossa da destra a sinistra a destra per

248
00:12:52,020 --> 00:12:57,020
da sinistra a destra a sinistra, ciascun
tempo solo rimbalzare il muro?

249
00:12:57,020 --> 00:12:58,050
Cosa voglio fare?

250
00:12:58,050 --> 00:13:01,097
Quale blocco dovrei connettersi al
"Flag quando verde cliccato prima"?

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

252
00:13:04,060 --> 00:13:06,200
>> Ok, cominciamo con il "per sempre".

253
00:13:06,200 --> 00:13:07,170
Ciò che va dentro dopo?

254
00:13:07,170 --> 00:13:10,290
Qualcun altro.

255
00:13:10,290 --> 00:13:11,850
OK, spostare passi.

256
00:13:11,850 --> 00:13:12,350
Tutto ok.

257
00:13:12,350 --> 00:13:14,470
Allora che cosa?

258
00:13:14,470 --> 00:13:15,120
Allora il caso.

259
00:13:15,120 --> 00:13:17,720
E si noti, anche se sembra
intramezzato insieme ermeticamente,

260
00:13:17,720 --> 00:13:19,500
sarà solo crescere fino a riempire.

261
00:13:19,500 --> 00:13:21,500
Sarà solo saltare in cui lo voglio.

262
00:13:21,500 --> 00:13:25,920
>> E che cosa ho messo tra
il caso e l'allora?

263
00:13:25,920 --> 00:13:27,180
Probabilmente "se toccando bordo."

264
00:13:27,180 --> 00:13:31,800
E notate, ancora una volta, è troppo grande
per questo, ma che crescerà da riempire.

265
00:13:31,800 --> 00:13:35,002
E poi girare di 15 gradi?

266
00:13:35,002 --> 00:13:35,710
Quanti gradi?

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

268
00:13:38,800 --> 00:13:41,196
Sì, così 180 girerà
mi tutto intorno.

269
00:13:41,196 --> 00:13:42,570
Così vediamo se ho ottenuto questo diritto.

270
00:13:42,570 --> 00:13:43,930
Mi permetta di diminuire.

271
00:13:43,930 --> 00:13:45,130
>> Mi permetta di trascinare Scratch up.

272
00:13:45,130 --> 00:13:50,030
Quindi è un po 'distorta
ora, ma va bene.

273
00:13:50,030 --> 00:13:52,231
Come l'ho ripristinare facilmente?

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

275
00:13:59,879 --> 00:14:01,045
Ho intenzione di barare un po '.

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

277
00:14:04,074 --> 00:14:05,990
Così sto aggiungendo un altro
blocco, tanto per essere chiari.

278
00:14:05,990 --> 00:14:08,424
Voglio che al punto 90 gradi
a destra per impostazione predefinita,

279
00:14:08,424 --> 00:14:10,840
quindi sto solo andando a dirglielo
per fare questo livello di programmazione.

280
00:14:10,840 --> 00:14:11,632
E qui andiamo.

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

282
00:14:14,740 --> 00:14:15,740
Sembra che abbiamo fatto.

283
00:14:15,740 --> 00:14:19,980
E 'un po' strano, perché
sta camminando a testa in giù.

284
00:14:19,980 --> 00:14:21,250
Chiamiamolo un bug.

285
00:14:21,250 --> 00:14:22,120
Questo è un errore.

286
00:14:22,120 --> 00:14:27,320
Un bug è un errore in un programma, un
errore logico che io, l'umano, fatto.

287
00:14:27,320 --> 00:14:28,985
Perché sta andando a testa in giù?

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

289
00:14:33,560 --> 00:14:35,250
Ha MIT vite o fatto io?

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

291
00:14:38,840 --> 00:14:42,550
>> Sì, voglio dire, non è il MIT di
colpa. Mi hanno dato un pezzo di puzzle

292
00:14:42,550 --> 00:14:44,970
che dice girare qualche numero di gradi.

293
00:14:44,970 --> 00:14:47,672
E su suggerimento di Victoria,
Sto girando di 180 gradi,

294
00:14:47,672 --> 00:14:48,880
che è l'intuizione giusta.

295
00:14:48,880 --> 00:14:53,700
Ma girando di 180 gradi letteralmente
mezzi rotazione di 180 gradi,

296
00:14:53,700 --> 00:14:55,860
e che non è proprio
quello che voglio, a quanto pare.

297
00:14:55,860 --> 00:14:58,026
Perché almeno lui è in
questo mondo bidimensionale,

298
00:14:58,026 --> 00:15:00,740
quindi svolta sta realmente accadendo
di capovolgere lo testa in giù.

299
00:15:00,740 --> 00:15:04,030
>> Probabilmente voglio usare quello blocco
invece, in base a ciò che si vede qui?

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

301
00:15:11,890 --> 00:15:14,790
Come possiamo risolvere questo problema?

302
00:15:14,790 --> 00:15:18,380
Sì, così abbiamo potuto puntare
nella direzione opposta.

303
00:15:18,380 --> 00:15:22,300
E in realtà, anche questo è
Non sarà sufficiente,

304
00:15:22,300 --> 00:15:26,410
perché possiamo solo codificare
di puntamento di sinistra o di destra.

305
00:15:26,410 --> 00:15:27,920
>> Sai cosa potremmo fare?

306
00:15:27,920 --> 00:15:30,160
Sembra che abbiamo un
blocco convenienza qui.

307
00:15:30,160 --> 00:15:32,987
Se io zoom avanti, vedi
qualcosa che ci piace qui?

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

309
00:15:36,120 --> 00:15:40,020
Così sembra che il MIT ha una
astrazione costruito qui.

310
00:15:40,020 --> 00:15:45,440
Questo blocco sembra essere equivalente
in cui altri blocchi, plurale?

311
00:15:45,440 --> 00:15:49,510
>> Questo blocco sembra essere equivalente
a tutto questo trio di blocchi

312
00:15:49,510 --> 00:15:50,880
che abbiamo qui.

313
00:15:50,880 --> 00:15:54,670
Così si scopre che posso semplificare la mia
Programma per sbarazzarsi di tutto questo

314
00:15:54,670 --> 00:15:58,270
e appena messo questo qui.

315
00:15:58,270 --> 00:16:01,620
E ora è ancora un po '
buggy, e va bene per ora.

316
00:16:01,620 --> 00:16:03,370
Lasceremo che si tratti.

317
00:16:03,370 --> 00:16:06,000
Ma il mio programma è anche
semplice, e anche questo,

318
00:16:06,000 --> 00:16:09,060
sarebbe rappresentativo
di un obiettivo in programming--

319
00:16:09,060 --> 00:16:13,430
è quello di rendere idealmente il codice come
semplice, più compatto possibile,

320
00:16:13,430 --> 00:16:15,650
pur essendo come
leggibili possibile.

321
00:16:15,650 --> 00:16:20,310
Non si vuole fare in modo succinto
che è difficile da capire.

322
00:16:20,310 --> 00:16:22,826
>> Ma accorgo Ho sostituito
tre blocchi con uno,

323
00:16:22,826 --> 00:16:24,200
e questo è senza dubbio una buona cosa.

324
00:16:24,200 --> 00:16:27,280
Ho astratte via la nozione
di verificare se si è

325
00:16:27,280 --> 00:16:29,120
sul bordo con un solo isolato.

326
00:16:29,120 --> 00:16:31,520
Ora siamo in grado di divertirsi con questo, in effetti.

327
00:16:31,520 --> 00:16:35,790
Questo non aggiunge tanto
valore intellettuale, ma il valore ludico.

328
00:16:35,790 --> 00:16:39,730
Ho intenzione di andare avanti
e afferrare questo suono qui.

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

330
00:16:42,900 --> 00:16:46,420
Quindi, mi permetta di andare avanti, e mi lascio
arrestare il programma per un momento.

331
00:16:46,420 --> 00:16:52,070
Ho intenzione di registrare il seguito,
permettendo l'accesso al mio microfono.

332
00:16:52,070 --> 00:16:53,181
>> Eccoci qui.

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

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

335
00:16:58,710 --> 00:17:01,140
Proviamo di nuovo.

336
00:17:01,140 --> 00:17:02,279
Eccoci qui.

337
00:17:02,279 --> 00:17:03,570
OK, ho registrato la cosa sbagliata.

338
00:17:03,570 --> 00:17:04,580
Eccoci qui.

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

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

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

342
00:17:08,800 --> 00:17:09,300
Tutto ok.

343
00:17:09,300 --> 00:17:10,791
Ora ho bisogno di sbarazzarsi di quella.

344
00:17:10,791 --> 00:17:11,290
Tutto ok.

345
00:17:11,290 --> 00:17:13,950
>> Così ora ho un
la registrazione di soli "ahi".

346
00:17:13,950 --> 00:17:18,040
Così ora ho intenzione di andare
avanti e chiamare questo "ahi".

347
00:17:18,040 --> 00:17:20,270
Ho intenzione di tornare indietro
ai miei script, e ora

348
00:17:20,270 --> 00:17:25,460
avviso c'è questo blocco che si chiama
riprodurre l'audio "meow" o riprodurre il suono "ahi".

349
00:17:25,460 --> 00:17:28,920
Ho intenzione di trascinare questo, e dove
dovrei mettere questo per effetto comico?

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

351
00:17:31,740 --> 00:17:37,860
Sì, così ora è una specie di
buggy, perché ora questo block--

352
00:17:37,860 --> 00:17:42,050
notare come questo "se sul bordo,
rimbalzo "è una specie di self-contained.

353
00:17:42,050 --> 00:17:43,704
Quindi ho bisogno di risolvere questo problema.

354
00:17:43,704 --> 00:17:44,870
Mi permetta di andare avanti e fare questo.

355
00:17:44,870 --> 00:17:48,630
Mi permetta di liberarsi di questo e torno
al nostro originale, più deliberata

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

357
00:17:49,870 --> 00:18:01,080
Quindi, "se toccando bordo, poi" Voglio
a girare, come Victoria proposto,

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

359
00:18:02,480 --> 00:18:05,497
E voglio giocare
il suono "ahi" lì?

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

361
00:18:11,800 --> 00:18:15,580
>> Sì, si noti che è al di fuori
quel blocco giallo.

362
00:18:15,580 --> 00:18:17,680
Quindi anche questo sarebbe un
bug, ma ho notato.

363
00:18:17,680 --> 00:18:21,290
Quindi ho intenzione di trascinarla fino qui,
e l'avviso ora è all'interno del "se".

364
00:18:21,290 --> 00:18:24,250
Quindi, il "se" è questo tipo
di come macchia braccio-like

365
00:18:24,250 --> 00:18:26,260
che è solo andare a
fare ciò che è all'interno di esso.

366
00:18:26,260 --> 00:18:30,216
Così ora se io diminuire a
il rischio di annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Ahi, ahi, ahi.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: E
sarà solo andare avanti per sempre.

370
00:18:39,910 --> 00:18:44,160
Ora basta per accelerare le cose
qui, mi permetta di andare avanti e di aprire,

371
00:18:44,160 --> 00:18:50,460
cerchiamo di say-- mi permetta di andare in qualche
della mia roba dalla classe.

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

373
00:18:53,000 --> 00:19:00,220
E mi permetta di aprire, diciamo, questo
quella fatta da uno dei nostri compagni di insegnamento

374
00:19:00,220 --> 00:19:01,500
un paio d'anni fa.

375
00:19:01,500 --> 00:19:04,732
Così alcuni di voi potrebbe ricordare
questo gioco da altri tempi,

376
00:19:04,732 --> 00:19:05,940
e in realtà è notevole.

377
00:19:05,940 --> 00:19:08,190
Anche se abbiamo fatto la
più semplice dei programmi in questo momento,

378
00:19:08,190 --> 00:19:09,980
prendiamo in considerazione ciò che questo
si presenta come.

379
00:19:09,980 --> 00:19:10,650
Mi ha colpito il gioco.

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

381
00:19:14,210 --> 00:19:18,980
>> Quindi, in questo gioco, abbiamo un
rana, e utilizzando la freccia keys--

382
00:19:18,980 --> 00:19:23,340
prende grandi passi di me remember--
Ho il controllo su questa rana.

383
00:19:23,340 --> 00:19:29,630
E l'obiettivo è quello di ottenere attraverso il occupato
strada senza incorrere in auto.

384
00:19:29,630 --> 00:19:34,735
E cerchiamo di see-- se vado qui, mi
aspettare per un registro a scorrimento da.

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

386
00:19:38,130 --> 00:19:39,274
Questo si sente come un insetto.

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

388
00:19:42,240 --> 00:19:43,495
Questa è una specie di insetto.

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

390
00:19:45,980 --> 00:19:46,480
Tutto ok.

391
00:19:46,480 --> 00:19:51,550
Sono su questo qui,
lì, e poi si mantiene

392
00:19:51,550 --> 00:19:54,100
andare fino ad arrivare tutti
le rane alle ninfee.

393
00:19:54,100 --> 00:19:55,920
Ora questo potrebbe sembrare
tanto più complessa,

394
00:19:55,920 --> 00:19:57,840
ma proviamo a rompere
questo in giù mentalmente

395
00:19:57,840 --> 00:20:00,040
e verbalmente nei suoi blocchi che lo compongono.

396
00:20:00,040 --> 00:20:03,910
Quindi c'è probabilmente un puzzle
pezzo che non abbiamo ancora visto

397
00:20:03,910 --> 00:20:07,440
ma questo è rispondere alle combinazioni di tasti,
a cose mi ha colpito sulla tastiera.

398
00:20:07,440 --> 00:20:11,660
>> Quindi c'è probabilmente un qualche tipo di
blocco che dice, se la chiave è uguale up,

399
00:20:11,660 --> 00:20:15,965
poi fare qualcosa con Scratch--
forse spostarlo 10 passi in questo modo.

400
00:20:15,965 --> 00:20:20,240
Se si preme il tasto premuto, spostare 10 passi
in questo modo, o il tasto sinistro, spostare 10 passi

401
00:20:20,240 --> 00:20:21,710
in questo modo, 10 passi che.

402
00:20:21,710 --> 00:20:23,644
Ho chiaramente trasformato il gatto in una rana.

403
00:20:23,644 --> 00:20:26,060
Ecco, questo è proprio dove il
costume, come le chiamate Scratch it-- noi

404
00:20:26,060 --> 00:20:28,440
appena importato una foto della rana.

405
00:20:28,440 --> 00:20:29,570
>> Ma che altro sta accadendo?

406
00:20:29,570 --> 00:20:32,794
Quali altre linee di codice,
ciò che gli altri pezzi del puzzle

407
00:20:32,794 --> 00:20:35,460
ha fatto Blake, il nostro insegnamento collega,
usare in questo programma, a quanto pare?

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

409
00:20:38,320 --> 00:20:42,730
Cosa sta facendo tutto move--
Che tipo di programmazione costruire?

410
00:20:42,730 --> 00:20:44,950
>> Movimento, in modo che il sure--
muoversi blocco, di sicuro.

411
00:20:44,950 --> 00:20:49,330
E che cosa è quel blocco mossa
interno, più probabile?

412
00:20:49,330 --> 00:20:52,850
Sì, una specie di loop, forse un
sempre bloccare, forse una ripetizione block--

413
00:20:52,850 --> 00:20:54,070
ripetere fino a blocco.

414
00:20:54,070 --> 00:20:57,330
Ed è quello che sta facendo i tronchi e
le ninfee e tutto il resto mossa

415
00:20:57,330 --> 00:20:57,990
avanti e indietro.

416
00:20:57,990 --> 00:21:00,270
E 'solo accadendo all'infinito.

417
00:21:00,270 --> 00:21:03,180
>> Perché alcune delle vetture
muoversi più velocemente rispetto agli altri?

418
00:21:03,180 --> 00:21:06,607
Qual è la differenza quei programmi?

419
00:21:06,607 --> 00:21:09,690
Sì, probabilmente alcuni di loro stanno prendendo
più passi contemporaneamente e alcuni di essi

420
00:21:09,690 --> 00:21:10,690
minor numero di passaggi in una sola volta.

421
00:21:10,690 --> 00:21:14,670
E l'effetto visivo
è veloce contro lento.

422
00:21:14,670 --> 00:21:16,030
>> Cosa ne pensi successo?

423
00:21:16,030 --> 00:21:19,700
Quando ho ottenuto il mio rana tutta la strada
dall'altra parte della strada e il fiume

424
00:21:19,700 --> 00:21:23,560
sulla ninfea, qualcosa
degno di nota è accaduto.

425
00:21:23,560 --> 00:21:26,540
Che cosa è successo, non appena l'ho fatto?

426
00:21:26,540 --> 00:21:27,210
Si fermò.

427
00:21:27,210 --> 00:21:29,680
Quella rana fermato, e
Ho avuto un secondo rana.

428
00:21:29,680 --> 00:21:33,155
Allora, cosa costrutto deve essere
ci utilizzato, quale funzione?

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

430
00:21:36,020 --> 00:21:38,660
>> Sì, così c'è qualche tipo di
"Se" condizione lassù, anche.

431
00:21:38,660 --> 00:21:41,909
E si scopre fuori-- non abbiamo visto questo--
ma ci sono altri blocchi in là che

432
00:21:41,909 --> 00:21:45,300
può dire, se toccando
un'altra cosa sullo schermo,

433
00:21:45,300 --> 00:21:47,720
se si sta toccando il pad giglio ", quindi."

434
00:21:47,720 --> 00:21:50,810
E poi in quel momento che abbiamo
far apparire la seconda rana.

435
00:21:50,810 --> 00:21:54,969
Così, anche se questo gioco è certamente
molto datato, anche se a prima vista

436
00:21:54,969 --> 00:21:58,010
c'è così tanto andare on-- e Blake
non montare questo in due minuti,

437
00:21:58,010 --> 00:22:00,390
probabilmente ha preso lui diversi
ore per creare questo gioco

438
00:22:00,390 --> 00:22:03,850
basato sulla sua memoria o video
della versione di ieri di esso.

439
00:22:03,850 --> 00:22:07,940
Ma tutte queste piccole cose
andare sullo schermo in isolamento

440
00:22:07,940 --> 00:22:11,550
riducono a questi molto semplice
movimenti constructs-- o dichiarazioni

441
00:22:11,550 --> 00:22:15,519
come abbiamo discusso, loop e
le condizioni, e che su di esso.

442
00:22:15,519 --> 00:22:17,060
Ci sono alcune altre caratteristiche amatore.

443
00:22:17,060 --> 00:22:19,130
Alcuni di loro sono puramente
estetica o acustico,

444
00:22:19,130 --> 00:22:20,964
come i suoni Ho appena giocato con.

445
00:22:20,964 --> 00:22:23,380
Ma per la maggior parte, si
avere in questa lingua, Scratch,

446
00:22:23,380 --> 00:22:25,350
tutto della fondamentale
blocchi che si

447
00:22:25,350 --> 00:22:29,280
avere in C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
e qualsiasi numero di altre lingue.

449
00:22:32,960 --> 00:22:36,720
Tutte le domande circa zero?

450
00:22:36,720 --> 00:22:37,220
Tutto ok.

451
00:22:37,220 --> 00:22:40,303
Quindi non ci immergersi in profondità a Scratch,
se sei il benvenuto in questo fine settimana,

452
00:22:40,303 --> 00:22:42,860
soprattutto se avete bambini o
nipoti e così via,

453
00:22:42,860 --> 00:22:44,220
per far loro conoscere Scratch.

454
00:22:44,220 --> 00:22:47,960
In realtà è una meravigliosamente giocoso
ambiente, come dicono i suoi autori,

455
00:22:47,960 --> 00:22:49,120
soffitti molto alti.

456
00:22:49,120 --> 00:22:51,670
Anche se abbiamo iniziato con
molto dettagli di basso livello,

457
00:22:51,670 --> 00:22:54,890
si può davvero fare un bel po '
con esso, e questo è forse

458
00:22:54,890 --> 00:22:57,360
una dimostrazione di esattamente questo.

459
00:22:57,360 --> 00:23:02,920
>> Ma veniamo ora alla transizione un po '
problemi sofisticati, se si vuole,

460
00:23:02,920 --> 00:23:05,870
conosciuto come "ricerca" e
"Smistamento", più in generale.

461
00:23:05,870 --> 00:23:09,500
Abbiamo avuto questa rubrica earlier-- ecco
un altro solo per discussion--

462
00:23:09,500 --> 00:23:13,460
che siamo stati in grado di cercare
in modo più efficiente perché

463
00:23:13,460 --> 00:23:15,270
di un'assunzione significativa.

464
00:23:15,270 --> 00:23:17,655
E tanto per essere chiari, cosa
ipotesi era che fare

465
00:23:17,655 --> 00:23:19,280
durante la ricerca attraverso questa rubrica?

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

467
00:23:23,342 --> 00:23:25,300
Che Mike Smith era in
la rubrica telefonica, anche se

468
00:23:25,300 --> 00:23:27,410
sarebbe in grado di gestire
lo scenario senza di lui

469
00:23:27,410 --> 00:23:30,720
lì se ho appena fermato prematuramente.

470
00:23:30,720 --> 00:23:31,806
Il libro è alfabetico.

471
00:23:31,806 --> 00:23:33,930
E questo è un molto generoso
ipotesi, perché

472
00:23:33,930 --> 00:23:36,580
significa someone-- Sono un po '
di tagliare un angolo,

473
00:23:36,580 --> 00:23:40,580
come io sono più veloce perché qualcuno
altro ha fatto un sacco di duro lavoro per me.

474
00:23:40,580 --> 00:23:43,120
>> Ma cosa succede se il telefono
libro sono stati non ordinato?

475
00:23:43,120 --> 00:23:47,050
Forse Verizon ha pigri, appena buttato
i nomi ei numeri di tutti in là

476
00:23:47,050 --> 00:23:50,120
forse nell'ordine in cui
firmato per il servizio telefonico.

477
00:23:50,120 --> 00:23:54,570
E quanto tempo ci vuole me
di trovare qualcuno come Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1.000 Pagina telefono book-- quanti
pagine devo guardare attraverso?

479
00:23:58,160 --> 00:23:58,905
>> Tutti loro.

480
00:23:58,905 --> 00:24:00,030
Sei una sorta di fuori di fortuna.

481
00:24:00,030 --> 00:24:03,420
È letteralmente deve guardare ad ogni
pagina se la rubrica è solo

482
00:24:03,420 --> 00:24:04,450
ordinati in modo casuale.

483
00:24:04,450 --> 00:24:06,910
Si potrebbe ottenere fortunati e trovare Mike
sulla prima pagina, perché

484
00:24:06,910 --> 00:24:08,826
è stato il primo cliente
di ordinare il servizio telefonico.

485
00:24:08,826 --> 00:24:10,760
Ma avrebbe potuto essere l'ultimo, anche.

486
00:24:10,760 --> 00:24:12,500
>> Quindi ordine casuale non è buona.

487
00:24:12,500 --> 00:24:16,750
Quindi supponiamo di avere per ordinare la
rubrica o nei dati generali sorta

488
00:24:16,750 --> 00:24:18,520
che ci è stata data.

489
00:24:18,520 --> 00:24:19,440
Come possiamo farlo?

490
00:24:19,440 --> 00:24:21,360
>> Beh, vorrei solo provare
un semplice esempio qui.

491
00:24:21,360 --> 00:24:24,290
Lasciami andare avanti e lanciare una
alcuni numeri sul tabellone.

492
00:24:24,290 --> 00:24:35,480
Supponiamo che i numeri che abbiamo sono,
diciamo, quattro, due, uno, e tre.

493
00:24:35,480 --> 00:24:38,390
E, Ben, ordinare questi numeri per noi.

494
00:24:38,390 --> 00:24:39,017
>> Ok bene.

495
00:24:39,017 --> 00:24:39,850
Come hai fatto?

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

497
00:24:42,731 --> 00:24:43,230
Tutto ok.

498
00:24:43,230 --> 00:24:44,710
Così inizia con il più piccolo
il valore e la più alta,

499
00:24:44,710 --> 00:24:46,084
E questo è davvero un buon intuito.

500
00:24:46,084 --> 00:24:48,080
E rendersi conto che noi
gli esseri umani sono in realtà piuttosto

501
00:24:48,080 --> 00:24:49,913
bravo a risolvere i problemi
così, almeno

502
00:24:49,913 --> 00:24:51,810
quando i dati è relativamente piccolo.

503
00:24:51,810 --> 00:24:54,860
Non appena si inizia ad avere centinaia
di numeri, migliaia di numeri,

504
00:24:54,860 --> 00:24:58,440
milioni di numeri, Ben probabilmente
non poteva fare abbastanza così veloce,

505
00:24:58,440 --> 00:25:00,620
supponendo che c'erano
lacune nei numeri.

506
00:25:00,620 --> 00:25:03,450
Abbastanza facile a contare fino a un milione
tuttavia, solo tempo.

507
00:25:03,450 --> 00:25:07,150
>> Così l'algoritmo suona
come Ben utilizzato solo ora

508
00:25:07,150 --> 00:25:08,930
era ricerca del numero più piccolo.

509
00:25:08,930 --> 00:25:12,900
Così, anche se noi umani possiamo prendere
in molte informazioni visivamente,

510
00:25:12,900 --> 00:25:14,830
un computer è in realtà
un po 'più limitata.

511
00:25:14,830 --> 00:25:17,560
Il computer può solo
guardare un byte alla volta

512
00:25:17,560 --> 00:25:20,770
o forse quattro byte alla tempo--
in questi giorni forse 8 byte alla tempo--

513
00:25:20,770 --> 00:25:24,450
ma un numero molto piccolo
di byte in un determinato momento.

514
00:25:24,450 --> 00:25:28,480
>> Quindi, dato che abbiamo davvero
quattro valori separati qui--

515
00:25:28,480 --> 00:25:32,440
e si può pensare di Ben come avere
paraocchi se fosse un computer, quali

516
00:25:32,440 --> 00:25:36,450
che non riesce a vedere niente altro
di un numero alla tempo--

517
00:25:36,450 --> 00:25:39,720
così abbiamo generalmente assumeremo, come in
Inglese, faremo leggere da destra a sinistra.

518
00:25:39,720 --> 00:25:42,870
Quindi, il primo numero di Ben probabilmente guardato
a quattro anni e quindi molto rapidamente

519
00:25:42,870 --> 00:25:44,770
sono resi conto che è una bella grande
number-- mi permetta di continuare a cercare.

520
00:25:44,770 --> 00:25:45,357
>> Ce ne sono due.

521
00:25:45,357 --> 00:25:45,940
Apetta un minuto.

522
00:25:45,940 --> 00:25:47,070
Due è inferiore a quattro.

523
00:25:47,070 --> 00:25:47,986
Ho intenzione di ricordare.

524
00:25:47,986 --> 00:25:49,070
Due è ora il più piccolo.

525
00:25:49,070 --> 00:25:50,417
Ora tra-- che è ancora meglio.

526
00:25:50,417 --> 00:25:51,250
Questo è ancora più piccolo.

527
00:25:51,250 --> 00:25:54,000
Ho intenzione di dimenticare due
e solo ricordare uno ora.

528
00:25:54,000 --> 00:25:56,550
>> E poteva smettere di guardare?

529
00:25:56,550 --> 00:25:58,360
Beh, poteva basato
su queste informazioni,

530
00:25:58,360 --> 00:26:00,477
ma avrebbe fatto meglio a ricerca
il resto della lista.

531
00:26:00,477 --> 00:26:02,060
Perché quello che se lo zero erano nella lista?

532
00:26:02,060 --> 00:26:03,643
Che cosa succede se uno fosse negativo nella lista?

533
00:26:03,643 --> 00:26:07,720
Sa solo che la sua risposta
è corretto se è esaurientemente

534
00:26:07,720 --> 00:26:08,729
controllato l'intera lista.

535
00:26:08,729 --> 00:26:10,020
Quindi guardiamo il resto di questo.

536
00:26:10,020 --> 00:26:11,394
Sulle tre ruote che era una perdita di tempo.

537
00:26:11,394 --> 00:26:13,540
Got sfortunato, ma ero
ancora corretta per farlo.

538
00:26:13,540 --> 00:26:17,857
E così ora lui presumibilmente
selezionato il numero più piccolo

539
00:26:17,857 --> 00:26:20,440
e appena messo all'inizio
della lista, come farò qui.

540
00:26:20,440 --> 00:26:23,480
Ora che cosa hai fatto dopo, anche se
non hai pensato a questo proposito quasi

541
00:26:23,480 --> 00:26:25,962
in questa misura?

542
00:26:25,962 --> 00:26:27,670
Ripetere il processo,
così una sorta di loop.

543
00:26:27,670 --> 00:26:28,920
C'è un'idea familiare.

544
00:26:28,920 --> 00:26:30,860
Così qui è quattro.

545
00:26:30,860 --> 00:26:32,110
Questo è attualmente il più piccolo.

546
00:26:32,110 --> 00:26:33,220
Questo è un candidato.

547
00:26:33,220 --> 00:26:33,900
Non più.

548
00:26:33,900 --> 00:26:34,770
Ora che ho visto due.

549
00:26:34,770 --> 00:26:36,630
Questo è l'elemento immediatamente inferiore.

550
00:26:36,630 --> 00:26:40,800
Sulle tre ruote che non è più piccolo, in modo da
ora Ben può strappare i due.

551
00:26:40,800 --> 00:26:44,510
>> Ed ora si ripete il processo e
naturalmente tre viene tirato fuori il prossimo.

552
00:26:44,510 --> 00:26:45,420
Ripetere il processo.

553
00:26:45,420 --> 00:26:46,990
Quattro viene tirato fuori.

554
00:26:46,990 --> 00:26:50,140
E ora siamo fuori di numeri,
così la lista deve essere ordinato.

555
00:26:50,140 --> 00:26:51,960
>> Ed in effetti, questo è un algoritmo convenzionale.

556
00:26:51,960 --> 00:26:56,610
Uno scienziato computer sarebbe
chiamare questa "selezione tipo,"

557
00:26:56,610 --> 00:27:00,880
l'idea è sorta una
elencare iteratively-- di nuovo

558
00:27:00,880 --> 00:27:03,807
e ancora e ancora selezionando
il numero più piccolo.

559
00:27:03,807 --> 00:27:06,140
E che cosa è bella è
è proprio così maledettamente intuitivo.

560
00:27:06,140 --> 00:27:07,470
E 'così semplice.

561
00:27:07,470 --> 00:27:11,100
E si può ripetere lo stesso
operazione più e più volte.

562
00:27:11,100 --> 00:27:12,150
È semplice.

563
00:27:12,150 --> 00:27:17,170
>> In questo caso è stato veloce, ma
Quanto tempo è effettivamente prendere?

564
00:27:17,170 --> 00:27:19,880
Facciamo sembrare e
sentire un po 'più noioso.

565
00:27:19,880 --> 00:27:24,150
Quindi uno, due, tre, quattro, cinque sei,
sette, otto, nove, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- numero arbitrario.

567
00:27:26,160 --> 00:27:28,780
Volevo solo più questo
tempo che solo il quattro.

568
00:27:28,780 --> 00:27:30,780
Quindi, se ho un intero
po 'di numeri now-- esso

569
00:27:30,780 --> 00:27:32,420
Non importa nemmeno
quello che are-- di lasciare

570
00:27:32,420 --> 00:27:34,380
pensare a ciò che questo
algoritmo è veramente.

571
00:27:34,380 --> 00:27:35,857
>> Supponiamo che ci siano i numeri là.

572
00:27:35,857 --> 00:27:38,190
Anche in questo caso, non importa cosa
essi sono, ma sono casuali.

573
00:27:38,190 --> 00:27:39,679
Mi candido algoritmo di Ben.

574
00:27:39,679 --> 00:27:41,220
Ho bisogno di selezionare il numero più piccolo.

575
00:27:41,220 --> 00:27:41,761
Cosa faccio?

576
00:27:41,761 --> 00:27:44,240
E ho intenzione di fisicamente
farlo in questo momento di agire fuori.

577
00:27:44,240 --> 00:27:46,099
Guardando, guardando,
guardando, guardando, guardando.

578
00:27:46,099 --> 00:27:48,140
Solo il tempo arrivare a
la fine della lista può

579
00:27:48,140 --> 00:27:51,230
Mi rendo conto che il più piccolo
numero era di due questa volta.

580
00:27:51,230 --> 00:27:52,720
Uno non è nella lista.

581
00:27:52,720 --> 00:27:54,400
Così ho messo giù due.

582
00:27:54,400 --> 00:27:55,590
>> Cosa faccio adesso?

583
00:27:55,590 --> 00:27:58,600
Guardando, guardando, guardando, guardando.

584
00:27:58,600 --> 00:28:02,250
Ora ho trovato il numero sette, perché
ci sono lacune in questi numbers--

585
00:28:02,250 --> 00:28:03,300
ma semplicemente arbitrario.

586
00:28:03,300 --> 00:28:03,800
Tutto ok.

587
00:28:03,800 --> 00:28:06,030
Così ora posso mettere giù sette.

588
00:28:06,030 --> 00:28:08,860
Guardando guardando, guardando.

589
00:28:08,860 --> 00:28:11,030
>> Ora sto assumendo, di
Naturalmente, che Ben non

590
00:28:11,030 --> 00:28:14,780
avere RAM in più, in più
memoria, perché, ovviamente,

591
00:28:14,780 --> 00:28:16,080
Sto guardando lo stesso numero.

592
00:28:16,080 --> 00:28:18,246
Sicuramente avrei potuto ricordato
tutti questi numeri,

593
00:28:18,246 --> 00:28:19,930
e questo è assolutamente vero.

594
00:28:19,930 --> 00:28:22,610
Ma se Ben si ricorda tutto
dei numeri che ha visto,

595
00:28:22,610 --> 00:28:24,430
egli non ha fatto davvero
il progresso fondamentale

596
00:28:24,430 --> 00:28:26,170
perché ha già
la capacità di ricerca

597
00:28:26,170 --> 00:28:27,540
i numeri sul tabellone.

598
00:28:27,540 --> 00:28:29,373
Ricordando tutte le
numeri non aiuta,

599
00:28:29,373 --> 00:28:32,490
perché egli può ancora come un computer
solo guardare, abbiamo detto, un numero

600
00:28:32,490 --> 00:28:33,080
Al tempo.

601
00:28:33,080 --> 00:28:35,760
Quindi non c'è nessun tipo di frode
lì che è possibile sfruttare.

602
00:28:35,760 --> 00:28:39,170
>> Quindi, in realtà, come ho
continuare a cercare la lista,

603
00:28:39,170 --> 00:28:44,200
Ho letteralmente devo solo andare avanti
avanti e indietro attraverso di essa, la spiumatura fuori

604
00:28:44,200 --> 00:28:45,710
il prossimo numero più piccolo.

605
00:28:45,710 --> 00:28:48,810
E come si può tipo di inferire
dai miei movimenti stupidi,

606
00:28:48,810 --> 00:28:50,860
questo appena diventa molto
noioso molto rapidamente,

607
00:28:50,860 --> 00:28:54,850
e mi sembra di andare indietro e
indietro, avanti e indietro un bel po '.

608
00:28:54,850 --> 00:29:03,220
Ora, per essere onesti, non ho andare
altrettanto, bene, cerchiamo di see-- ad essere onesti,

609
00:29:03,220 --> 00:29:06,310
Non devo camminare molto
il maggior numero di passaggi ogni volta.

610
00:29:06,310 --> 00:29:09,200
Poiché, ovviamente, come ho
selezionare i numeri dalla lista,

611
00:29:09,200 --> 00:29:11,860
la lista restante è sempre più breve.

612
00:29:11,860 --> 00:29:14,240
>> E così pensiamo
quanti passi sono in realtà

613
00:29:14,240 --> 00:29:16,010
scarpinare attraverso ogni volta.

614
00:29:16,010 --> 00:29:18,950
Nella prima situazione
abbiamo avuto 16 numeri,

615
00:29:18,950 --> 00:29:22,210
e così maximally-- facciamo solo
fare questo per un discussion--

616
00:29:22,210 --> 00:29:25,640
Ho dovuto guardare attraverso 16
i numeri per trovare il più piccolo.

617
00:29:25,640 --> 00:29:28,420
Ma una volta che ho strappato
il numero più piccolo, come

618
00:29:28,420 --> 00:29:30,590
lungo era la lista restante, naturalmente?

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

620
00:29:31,420 --> 00:29:34,670
Così come molti numeri DID Ben o ho
a guardare attraverso la seconda volta?

621
00:29:34,670 --> 00:29:36,832
15, solo per andare a trovare il più piccolo.

622
00:29:36,832 --> 00:29:39,540
Ma ora, naturalmente, l'elenco è,
Anche, più piccolo di quanto non fosse prima.

623
00:29:39,540 --> 00:29:42,540
Così come molti passi ho fatto
prendere la prossima volta?

624
00:29:42,540 --> 00:29:49,970
14 e poi 13 e poi 12, più punti,
dot, dot, fino a quando io sono rimasto con una sola.

625
00:29:49,970 --> 00:29:53,146
Così ora un informatico sarebbe
chiedere, beh, che cosa tutti uguali?

626
00:29:53,146 --> 00:29:55,770
In realtà è uguale a un po 'di cemento
numero che potremmo certamente

627
00:29:55,770 --> 00:30:00,490
facciamo aritmeticamente, ma vogliamo parlare
sull'efficienza degli algoritmi

628
00:30:00,490 --> 00:30:04,940
un po 'più formulaically,
indipendentemente dal tempo la lista è.

629
00:30:04,940 --> 00:30:06,240
>> E così sai cosa?

630
00:30:06,240 --> 00:30:09,860
Questo è 16, ma, come ho detto prima,
facciamo solo chiamare la dimensione del problema

631
00:30:09,860 --> 00:30:10,970
n, dove n è un numero.

632
00:30:10,970 --> 00:30:13,220
Forse è il 16, forse è
tre, forse si tratta di un milione.

633
00:30:13,220 --> 00:30:13,761
Non lo so.

634
00:30:13,761 --> 00:30:14,390
Non mi interessa.

635
00:30:14,390 --> 00:30:16,520
Quello che voglio davvero è
una formula che posso

636
00:30:16,520 --> 00:30:19,420
utilizzare per confrontare questo algoritmo
contro altri algoritmi

637
00:30:19,420 --> 00:30:22,350
che qualcuno potrebbe affermare
sono meglio o peggio.

638
00:30:22,350 --> 00:30:25,430
>> Così si scopre, e solo io
conoscere questo dalla scuola elementare,

639
00:30:25,430 --> 00:30:34,790
che questo effettivamente funziona allo stesso
cosa come N su n più uno più di due.

640
00:30:34,790 --> 00:30:40,020
E questo accade per uguagliare, di
Naturalmente, n al quadrato più n più di due.

641
00:30:40,020 --> 00:30:43,250
Quindi, se volevo una formula
per quanti passi

642
00:30:43,250 --> 00:30:46,330
sono stati coinvolti in guardando tutti
di questi numeri ancora e ancora

643
00:30:46,330 --> 00:30:52,681
e ancora e ancora, direi
è n al quadrato più n più di due.

644
00:30:52,681 --> 00:30:53,430
Ma sai una cosa?

645
00:30:53,430 --> 00:30:54,500
Questo sembra proprio disordinato.

646
00:30:54,500 --> 00:30:56,470
Ho solo voglia di un
il senso generale delle cose.

647
00:30:56,470 --> 00:30:58,810
E si potrebbe ricordare da
liceo che non ci

648
00:30:58,810 --> 00:31:00,660
è il concetto di massima termine di ordine.

649
00:31:00,660 --> 00:31:05,300
Quale di questi termini, la n
quadrato, n, o la metà,

650
00:31:05,300 --> 00:31:07,550
ha il maggiore impatto nel corso del tempo?

651
00:31:07,550 --> 00:31:11,920
Più grande è n ottiene, che
della maggior parte tali questioni?

652
00:31:11,920 --> 00:31:15,560
>> In altre parole, se collego
su un milione, n quadrato

653
00:31:15,560 --> 00:31:17,900
sta per essere più probabile
il fattore dominante,

654
00:31:17,900 --> 00:31:21,670
perché un milione di volte
è di per sé molto più grande

655
00:31:21,670 --> 00:31:23,682
di più un ulteriore milione.

656
00:31:23,682 --> 00:31:24,390
Allora sai cosa?

657
00:31:24,390 --> 00:31:27,305
Questo è un grande maledettamente
numero se si piazza un numero.

658
00:31:27,305 --> 00:31:28,430
Questo non ha molta importanza.

659
00:31:28,430 --> 00:31:30,596
Stiamo solo andando croce che
fuori e non pensarci più.

660
00:31:30,596 --> 00:31:34,250
E così un informatico direbbe
che l'efficienza di questo algoritmo

661
00:31:34,250 --> 00:31:37,850
è dell'ordine di n squared--
Voglio dire veramente una approssimazione.

662
00:31:37,850 --> 00:31:40,810
E 'una sorta di circa n al quadrato.

663
00:31:40,810 --> 00:31:44,130
Nel corso del tempo, il più grande
e più grande n ottiene, questo

664
00:31:44,130 --> 00:31:47,610
è una buona stima per quello che la
efficienza o mancanza di efficienza

665
00:31:47,610 --> 00:31:49,400
di questo algoritmo è in realtà.

666
00:31:49,400 --> 00:31:52,040
E derivo che, naturalmente,
dalla realtà facendo due conti.

667
00:31:52,040 --> 00:31:54,040
Ma ora sto solo agitando
le mie mani, perché ho appena

668
00:31:54,040 --> 00:31:55,790
vuole un senso generale di questo algoritmo.

669
00:31:55,790 --> 00:31:58,850
>> Quindi, utilizzando la stessa logica, nel frattempo,
prendiamo in considerazione un altro algoritmo

670
00:31:58,850 --> 00:32:01,162
abbiamo già guardato at-- ricerca lineare.

671
00:32:01,162 --> 00:32:02,870
Quando ero alla ricerca
per il telefono book--

672
00:32:02,870 --> 00:32:05,980
Non smistamento, ricerca
attraverso il telefono book--

673
00:32:05,980 --> 00:32:09,197
abbiamo mantenuto dicendo che era
1.000 passi, o 500 passi.

674
00:32:09,197 --> 00:32:10,280
Ma cerchiamo di generalizzare questo.

675
00:32:10,280 --> 00:32:12,860
Se c'è n pagine
l'elenco telefonico, che cosa è

676
00:32:12,860 --> 00:32:17,250
il tempo di esecuzione o
efficienza della ricerca lineare?

677
00:32:17,250 --> 00:32:19,750
È nell'ordine di
quanti passi per trovare

678
00:32:19,750 --> 00:32:24,210
Mike Smith utilizzando ricerca lineare, la
primo algoritmo, o anche la seconda?

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

680
00:32:27,240 --> 00:32:31,710
>> Nel caso peggiore, Mike
è alla fine del libro.

681
00:32:31,710 --> 00:32:35,590
Quindi, se il libro telefono è dotato di 1.000 pagine,
abbiamo detto l'ultima volta, nel caso peggiore,

682
00:32:35,590 --> 00:32:38,380
potrebbe richiedere più o meno come
molte pagine per trovare Mike?

683
00:32:38,380 --> 00:32:38,990
Come 1.000.

684
00:32:38,990 --> 00:32:39,830
Si tratta di un limite superiore.

685
00:32:39,830 --> 00:32:41,790
E 'una situazione peggiore possibile.

686
00:32:41,790 --> 00:32:44,410
Ma ancora una volta, ci stiamo allontanando
da numeri come 1.000 ora.

687
00:32:44,410 --> 00:32:45,730
E 'solo n.

688
00:32:45,730 --> 00:32:47,470
>> Quindi qual è la conclusione logica?

689
00:32:47,470 --> 00:32:50,210
Trovare Mike in un telefono
libro che ha pagine n

690
00:32:50,210 --> 00:32:55,280
potrebbe prendere, nel caso peggiore,
quanti passi dell'ordine di n?

691
00:32:55,280 --> 00:32:58,110
E in effetti un computer
scienziato direbbe

692
00:32:58,110 --> 00:33:02,340
che il tempo di esecuzione, o
le prestazioni o l'efficienza

693
00:33:02,340 --> 00:33:07,470
o inefficienza, di un algoritmo simile
una ricerca lineare è dell'ordine di n.

694
00:33:07,470 --> 00:33:10,010
E siamo in grado di applicare la stessa
la logica di attraversare qualcosa

695
00:33:10,010 --> 00:33:13,170
come ho appena fatto al secondo
algoritmo che abbiamo avuto con la rubrica telefonica,

696
00:33:13,170 --> 00:33:16,040
dove siamo andati due pagine alla volta.

697
00:33:16,040 --> 00:33:20,120
>> Così 1.000 Pagina rubrica telefonica potrebbe
portarci 500 Page turno, più uno

698
00:33:20,120 --> 00:33:21,910
se raddoppiamo un po 'indietro.

699
00:33:21,910 --> 00:33:26,590
Quindi, se un libro telefono è dotato di n pagine, ma
stiamo facendo due pagine alla volta,

700
00:33:26,590 --> 00:33:28,900
questo è più o meno quello che?

701
00:33:28,900 --> 00:33:33,190
N più di due, in modo che è come n più di due.

702
00:33:33,190 --> 00:33:38,490
Ma ho fatto la richiesta di un
momento fa che n sopra two--

703
00:33:38,490 --> 00:33:41,060
questo è il tipo dello stesso come proprio n.

704
00:33:41,060 --> 00:33:44,050
E 'solo un fattore costante,
gli informatici direbbero.

705
00:33:44,050 --> 00:33:45,970
Concentriamoci solo sul
le variabili, really--

706
00:33:45,970 --> 00:33:47,780
maggiori variabili nell'equazione.

707
00:33:47,780 --> 00:33:52,530
>> ricerca in modo lineare, sia fatta una
pagina alla volta o due pagine alla volta,

708
00:33:52,530 --> 00:33:54,810
è una sorta di fondamentalmente lo stesso.

709
00:33:54,810 --> 00:33:56,880
È ancora dell'ordine di n.

710
00:33:56,880 --> 00:34:01,930
Ma ho sostenuto con la mia immagine precedente
che il terzo algoritmo non era

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

712
00:34:02,480 --> 00:34:03,605
Non era una linea retta.

713
00:34:03,605 --> 00:34:08,659
Era quella linea curva, e la
formula algebrica c'era quello che?

714
00:34:08,659 --> 00:34:11,812
Log di n-- così logaritmo in base due di n.

715
00:34:11,812 --> 00:34:14,520
E noi non dobbiamo andare in troppo
più dettagli su logaritmi oggi,

716
00:34:14,520 --> 00:34:17,394
ma la maggior parte degli scienziati informatici no
anche dirvi ciò che la base è.

717
00:34:17,394 --> 00:34:20,639
Perché è tutto solo
fattori costanti, per così dire,

718
00:34:20,639 --> 00:34:22,659
solo lievi differenze numeriche.

719
00:34:22,659 --> 00:34:31,179
E quindi questo sarebbe molto comune
modo per il calcolatore particolarmente formale

720
00:34:31,179 --> 00:34:33,949
gli scienziati ad una scheda o
programmatori di un bordo bianco

721
00:34:33,949 --> 00:34:36,889
in realtà sostenendo che
algoritmo userebbero

722
00:34:36,889 --> 00:34:39,500
o che l'efficienza
del loro algoritmo è.

723
00:34:39,500 --> 00:34:42,960
>> E questo non è necessariamente qualcosa
si discute in qualsiasi grande dettaglio,

724
00:34:42,960 --> 00:34:47,889
ma un buon programmatore è qualcuno
che ha un solido, sfondo formale.

725
00:34:47,889 --> 00:34:50,120
E 'in grado di parlare di
in questo tipo di strada

726
00:34:50,120 --> 00:34:53,350
e effettivamente fare
argomenti qualitativi come

727
00:34:53,350 --> 00:34:56,870
il motivo per cui un algoritmo o
un pezzo di software

728
00:34:56,870 --> 00:35:00,165
è superiore in un modo all'altro.

729
00:35:00,165 --> 00:35:02,540
Perché si potrebbe certamente
basta eseguire il programma di una persona

730
00:35:02,540 --> 00:35:04,980
e contare il numero di secondi
che serve per ordinare alcuni numeri,

731
00:35:04,980 --> 00:35:06,710
e si può eseguire alcuni
Il programma di altra persona

732
00:35:06,710 --> 00:35:08,418
e contare il numero
di secondi necessari.

733
00:35:08,418 --> 00:35:12,840
Ma questo è un modo più generale che
è possibile utilizzare per analizzare gli algoritmi,

734
00:35:12,840 --> 00:35:15,520
se si vuole, basta su
carta o solo verbalmente.

735
00:35:15,520 --> 00:35:18,430
Senza nemmeno in esecuzione, senza
anche cercando ingressi di esempio,

736
00:35:18,430 --> 00:35:20,180
si può solo ragionare attraverso di essa.

737
00:35:20,180 --> 00:35:24,670
E così con l'assunzione di uno sviluppatore o se
avere lui o lei sorta di discutere a voi

738
00:35:24,670 --> 00:35:28,460
perché il loro algoritmo, il loro segreto
salsa per la ricerca miliardi

739
00:35:28,460 --> 00:35:30,580
di pagine web per la tua
azienda è meglio, questi

740
00:35:30,580 --> 00:35:33,302
sono i tipi di argomenti che
dovrebbe idealmente in grado di fare.

741
00:35:33,302 --> 00:35:35,010
O almeno queste sono
il tipo di cose

742
00:35:35,010 --> 00:35:40,211
che sarebbe venuto in discussione, a
almeno in una discussione molto formale.

743
00:35:40,211 --> 00:35:40,710
Tutto ok.

744
00:35:40,710 --> 00:35:44,400
Così Ben proposto qualcosa
chiamato selection sort.

745
00:35:44,400 --> 00:35:48,200
Ma ho intenzione di proporre che non c'è
altri modi per farlo, troppo.

746
00:35:48,200 --> 00:35:50,400
Quello che non mi piace molto
su algoritmo di Ben

747
00:35:50,400 --> 00:35:54,400
è che egli continuò a camminare, o
avermi camminare, avanti e indietro

748
00:35:54,400 --> 00:35:56,930
e avanti e indietro e avanti e indietro.

749
00:35:56,930 --> 00:36:04,130
E se invece dovessi fare
qualcosa di simile a questi numeri qui

750
00:36:04,130 --> 00:36:08,200
ed io eravamo a che fare solo con ogni
il numero, a sua volta, come sto dato che?

751
00:36:08,200 --> 00:36:10,780
>> In altre parole, ecco
la mia lista di numeri.

752
00:36:10,780 --> 00:36:12,944
Quattro, uno, tre, due.

753
00:36:12,944 --> 00:36:14,360
E ho intenzione di fare quanto segue.

754
00:36:14,360 --> 00:36:17,230
Ho intenzione di inserire i numeri
a cui appartengono piuttosto

755
00:36:17,230 --> 00:36:18,980
che selezionando uno alla volta.

756
00:36:18,980 --> 00:36:20,820
In altre parole, qui è il numero quattro.

757
00:36:20,820 --> 00:36:22,430
>> Ecco la mia lista originale.

758
00:36:22,430 --> 00:36:25,290
E ho intenzione di mantenere
in sostanza un nuovo elenco qui.

759
00:36:25,290 --> 00:36:26,710
Quindi questa è la vecchia lista.

760
00:36:26,710 --> 00:36:28,560
Questa è la nuova lista.

761
00:36:28,560 --> 00:36:30,220
Vedo il numero quattro prima.

762
00:36:30,220 --> 00:36:34,500
La mia nuova lista è inizialmente vuota,
quindi è banalmente caso

763
00:36:34,500 --> 00:36:36,410
che quattro è ora lista assortiti.

764
00:36:36,410 --> 00:36:39,560
Sto solo prendendo il numero che sto dato,
e sto mettendo nella mia nuova lista.

765
00:36:39,560 --> 00:36:41,460
>> E 'questa nuova lista ordinata?

766
00:36:41,460 --> 00:36:41,990
Sì.

767
00:36:41,990 --> 00:36:45,090
È stupido, perché c'è solo una
elemento, ma è assolutamente allineati.

768
00:36:45,090 --> 00:36:46,390
Non c'è nulla fuori posto.

769
00:36:46,390 --> 00:36:49,290
È più interessante, questo algoritmo,
quando mi muovo alla fase successiva.

770
00:36:49,290 --> 00:36:50,550
>> Ora ne ho uno.

771
00:36:50,550 --> 00:36:55,430
Quindi, naturalmente, appartiene alla
inizio o la fine di questa nuova lista?

772
00:36:55,430 --> 00:36:56,360
L'inizio.

773
00:36:56,360 --> 00:36:58,530
Quindi devo fare qualche lavoro ora.

774
00:36:58,530 --> 00:37:01,410
Ho preso un po '
libertà con il mio marcatore

775
00:37:01,410 --> 00:37:03,120
semplicemente disegnando cose
dove li voglio,

776
00:37:03,120 --> 00:37:05,320
ma questo non è proprio
accurata in un computer.

777
00:37:05,320 --> 00:37:08,530
Un computer, come sappiamo, ha
RAM o Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
e questo è un byte e
un altro byte e un altro byte.

779
00:37:12,411 --> 00:37:14,910
E se si dispone di un gigabyte di
RAM, si dispone di un miliardo di byte,

780
00:37:14,910 --> 00:37:16,680
ma sono fisicamente in un unico luogo.

781
00:37:16,680 --> 00:37:19,540
Non si può semplicemente spostare roba in giro
disegnando sulla lavagna

782
00:37:19,540 --> 00:37:20,750
dove vuoi.

783
00:37:20,750 --> 00:37:24,090
Quindi, se la mia nuova lista ha
quattro posizioni di memoria,

784
00:37:24,090 --> 00:37:27,480
purtroppo il quattro è
già nel posto sbagliato.

785
00:37:27,480 --> 00:37:30,410
>> Quindi, per inserire il numero uno
Non posso solo disegnare qui.

786
00:37:30,410 --> 00:37:31,901
Questa posizione di memoria non esiste.

787
00:37:31,901 --> 00:37:35,150
Sarebbe barare, e mi sono stati
barare pittoricamente per pochi minuti

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

789
00:37:35,800 --> 00:37:40,950
Quindi, in realtà, se voglio mettere uno qui,
Devo copiare temporaneamente il quattro

790
00:37:40,950 --> 00:37:43,030
e poi mettere quello lì.

791
00:37:43,030 --> 00:37:45,500
>> Va bene, questo è corretto,
che è tecnicamente possibile,

792
00:37:45,500 --> 00:37:48,410
ma si rendono conto che è un lavoro extra.

793
00:37:48,410 --> 00:37:50,460
Non ho appena messo il numero di posto.

794
00:37:50,460 --> 00:37:53,026
Ho dovuto spostare un
numero, quindi metterlo in atto,

795
00:37:53,026 --> 00:37:54,650
così ho tipo di raddoppiato il mio carico di lavoro.

796
00:37:54,650 --> 00:37:55,660
Modo da tenere a mente.

797
00:37:55,660 --> 00:37:57,120
>> Ma ora sto fatto con questo elemento.

798
00:37:57,120 --> 00:37:59,056
Ora voglio afferrare il numero tre.

799
00:37:59,056 --> 00:38:00,430
Dove, naturalmente, appartiene?

800
00:38:00,430 --> 00:38:01,480
Nel mezzo.

801
00:38:01,480 --> 00:38:03,650
Non posso imbrogliare più
e appena messo lì,

802
00:38:03,650 --> 00:38:06,770
perché, di nuovo, questa memoria
è in luoghi fisici.

803
00:38:06,770 --> 00:38:10,900
Quindi devo copiare i quattro
e mettere i tre qui.

804
00:38:10,900 --> 00:38:11,550
Non un grande affare.

805
00:38:11,550 --> 00:38:14,610
E 'solo un passo in più
again-- si sente molto poco costoso.

806
00:38:14,610 --> 00:38:16,445
>> Ma ora passo a due.

807
00:38:16,445 --> 00:38:17,820
I due, ovviamente, appartiene qui.

808
00:38:17,820 --> 00:38:20,990
Ora si inizia a vedere come
il lavoro può accumularsi.

809
00:38:20,990 --> 00:38:23,520
Ora cosa devo fare?

810
00:38:23,520 --> 00:38:28,570
Sì, devo spostare il quattro,
Poi ho dovuto copiare i tre,

811
00:38:28,570 --> 00:38:31,200
e ora posso inserire i due.

812
00:38:31,200 --> 00:38:34,460
E il fermo con questo
algoritmo, abbastanza interessante,

813
00:38:34,460 --> 00:38:41,050
è che supponiamo di avere un più estremo
caso in cui è diciamo otto, sette,

814
00:38:41,050 --> 00:38:45,150
sei, cinque, quattro, tre, due, uno.

815
00:38:45,150 --> 00:38:49,450
Questo è, in molti contesti,
la peggiore delle ipotesi,

816
00:38:49,450 --> 00:38:51,570
perché l'aggeggio
è letteralmente all'indietro.

817
00:38:51,570 --> 00:38:53,670
>> E 'davvero non
influenzare l'algoritmo di Ben,

818
00:38:53,670 --> 00:38:55,940
perché nella scelta di Ben
Ordina ha intenzione di mantenere

819
00:38:55,940 --> 00:38:58,359
andando avanti e indietro attraverso la lista.

820
00:38:58,359 --> 00:39:01,150
E perché era sempre alla ricerca
tutta la lista restante,

821
00:39:01,150 --> 00:39:02,858
non importa
dove gli elementi sono.

822
00:39:02,858 --> 00:39:05,630
Ma in questo caso con il mio inserimento
approach-- proviamo questo.

823
00:39:05,630 --> 00:39:08,616
>> Quindi uno, due, tre, quattro,
cinque, sei, sette, otto.

824
00:39:08,616 --> 00:39:11,630
Uno due tre quattro,
cinque, sei, sette, otto.

825
00:39:11,630 --> 00:39:14,320
Vado a prendere otto,
e dove lo metto?

826
00:39:14,320 --> 00:39:17,260
Beh, all'inizio della mia lista,
perché questo nuovo elenco è ordinato.

827
00:39:17,260 --> 00:39:18,760
E varco fuori.

828
00:39:18,760 --> 00:39:20,551
>> Dove metto il sette?

829
00:39:20,551 --> 00:39:21,050
Accidenti.

830
00:39:21,050 --> 00:39:23,174
Si deve andare lì, così
Devo fare un po 'la copia.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
E ora i sette va qui.

833
00:39:28,480 --> 00:39:29,860
Ora mi muovo al sei.

834
00:39:29,860 --> 00:39:30,980
Ora è ancora più lavoro.

835
00:39:30,980 --> 00:39:32,570
>> Otto deve andare qui.

836
00:39:32,570 --> 00:39:33,920
Sette deve andare qui.

837
00:39:33,920 --> 00:39:35,450
Ora i sei può andare qui.

838
00:39:35,450 --> 00:39:37,950
Ora prendo il cinque.

839
00:39:37,950 --> 00:39:40,560
Ora gli otto deve andare
qui, sette deve andare qui,

840
00:39:40,560 --> 00:39:43,650
sei deve andare qui, e
Ora i cinque e ripetere.

841
00:39:43,650 --> 00:39:46,610
E sono praticamente
spostandola continuamente.

842
00:39:46,610 --> 00:39:52,950
>> Così, alla fine, questo algorithm-- faremo
chiamare inserimento sort-- realtà

843
00:39:52,950 --> 00:39:55,020
ha un sacco di lavoro, anche.

844
00:39:55,020 --> 00:39:56,970
E 'solo diverso
tipo di lavoro di Ben.

845
00:39:56,970 --> 00:40:00,090
Il lavoro di Ben mi ha fatto andare
avanti e indietro tutto il tempo,

846
00:40:00,090 --> 00:40:03,510
la selezione del prossimo più piccolo
elemento nuovo e di nuovo.

847
00:40:03,510 --> 00:40:06,660
Così è stato questo tipo molto visivo di lavoro.

848
00:40:06,660 --> 00:40:10,600
>> Questo altro algoritmo, che è ancora
correct-- si otterrà il lavoro done--

849
00:40:10,600 --> 00:40:12,800
cambia solo la quantità di lavoro.

850
00:40:12,800 --> 00:40:15,420
Sembra che inizialmente sei
risparmio, perché sei solo

851
00:40:15,420 --> 00:40:19,190
trattare ogni elemento
in attacco senza camminare tutto

852
00:40:19,190 --> 00:40:20,930
il percorso attraverso la lista come Ben era.

853
00:40:20,930 --> 00:40:25,300
Ma il problema è, soprattutto in questi
casi folli in cui è tutto al contrario,

854
00:40:25,300 --> 00:40:27,830
sei solo tipo di
rimandando il duro lavoro

855
00:40:27,830 --> 00:40:30,360
fino ad avere per correggere i tuoi errori.

856
00:40:30,360 --> 00:40:33,919
>> E quindi se si può immaginare questo
otto e sette e sei e cinque

857
00:40:33,919 --> 00:40:36,710
e poi quattro e tre e due
spostando la loro strada attraverso la lista,

858
00:40:36,710 --> 00:40:39,060
abbiamo appena cambiato il
tipo di lavoro che stiamo facendo.

859
00:40:39,060 --> 00:40:42,340
Invece di farlo al
All'inizio del mio iterazione,

860
00:40:42,340 --> 00:40:45,250
Sto solo facendo al
fine di ogni iterazione.

861
00:40:45,250 --> 00:40:50,550
Così si scopre che questo algoritmo,
Anche, generalmente chiamato insertion sort,

862
00:40:50,550 --> 00:40:52,190
è anche dell'ordine di n quadrato.

863
00:40:52,190 --> 00:40:56,480
In realtà non è migliore,
migliore affatto.

864
00:40:56,480 --> 00:41:00,810
>> Tuttavia, c'è un terzo approccio
Mi noi vorremmo suggerire considerare,

865
00:41:00,810 --> 00:41:02,970
che è questo.

866
00:41:02,970 --> 00:41:07,850
Quindi supponiamo che la mia lista, per semplicità
ancora una volta, è di quattro, uno, tre,

867
00:41:07,850 --> 00:41:11,080
two-- soli quattro numeri.

868
00:41:11,080 --> 00:41:13,300
Ben aveva buona intuizione,
buona intuizione umana

869
00:41:13,300 --> 00:41:16,340
prima, con la quale abbiamo fissato l'intera
elencare eventually-- insertion sort.

870
00:41:16,340 --> 00:41:18,020
Contattaci persuasi lungo.

871
00:41:18,020 --> 00:41:22,530
Ma prendiamo in considerazione il
modo più semplice per risolvere questa lista.

872
00:41:22,530 --> 00:41:24,110
>> Questo elenco non è ordinato.

873
00:41:24,110 --> 00:41:26,130
Perché?

874
00:41:26,130 --> 00:41:31,920
In inglese, spiegare perché
In realtà non è ordinato.

875
00:41:31,920 --> 00:41:33,400
Che cosa significa non essere ordinati?

876
00:41:33,400 --> 00:41:34,220
>> STUDENTE: Non è sequenziale.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: non sequenziale.

878
00:41:34,990 --> 00:41:35,822
Fammi un esempio.

879
00:41:35,822 --> 00:41:37,180
>> STUDENTE: Metterli in ordine.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Dammi un esempio più specifico.

882
00:41:38,790 --> 00:41:39,832
>> STUDENTE: ordine crescente.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Non ordine crescente.

884
00:41:41,206 --> 00:41:42,100
Essere più precisi.

885
00:41:42,100 --> 00:41:45,190
Non so cosa si intende per ascendente.

886
00:41:45,190 --> 00:41:47,150
Cosa c'è di sbagliato?

887
00:41:47,150 --> 00:41:49,930
>> STUDENTE: Il più piccolo del
numeri non è nel primo spazio.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: minor numero di
non nel primo spazio.

889
00:41:51,140 --> 00:41:52,120
Sii più preciso.

890
00:41:52,120 --> 00:41:55,000
Sto iniziando a prendere piede.

891
00:41:55,000 --> 00:41:59,470
Contiamo, ma
ciò che è fuori ordine qui?

892
00:41:59,470 --> 00:42:00,707
>> STUDENTE: sequenza numerica.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: sequenza numerica.

894
00:42:02,040 --> 00:42:04,248
tipo di ognuno di conservazione
è qui-- altissimo livello.

895
00:42:04,248 --> 00:42:07,450
Basta letteralmente dimmi cosa c'è
male come una forza di cinque anni.

896
00:42:07,450 --> 00:42:08,310
>> STUDENTE: più uno.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Che cos'è?

898
00:42:08,750 --> 00:42:09,610
>> STUDENTE: più uno.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Cosa vuoi dire più uno?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Dammi un altro di cinque anni.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Cosa c'è che non va, mamma?

904
00:42:18,330 --> 00:42:19,940
Cosa c'è che non va, papà?

905
00:42:19,940 --> 00:42:22,808
Cosa vuol dire questo non è ordinato?

906
00:42:22,808 --> 00:42:24,370
>> STUDENTE: Non è il posto giusto.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Cosa c'è
Non nel posto giusto?

908
00:42:25,580 --> 00:42:26,174
>> STUDENTE: Quattro.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, bene.

910
00:42:27,090 --> 00:42:29,110
Quindi quattro non è dove dovrebbe essere.

911
00:42:29,110 --> 00:42:30,590
In particolare, è questo diritto?

912
00:42:30,590 --> 00:42:33,000
Quattro e uno, il primo
due numeri che vedo.

913
00:42:33,000 --> 00:42:34,930
È giusto?

914
00:42:34,930 --> 00:42:36,427
No, sono in ordine, giusto?

915
00:42:36,427 --> 00:42:38,135
In effetti, pensare ora
A proposito di un computer, anche.

916
00:42:38,135 --> 00:42:40,824
Si può solo guardare forse uno,
forse due cose a once--

917
00:42:40,824 --> 00:42:43,240
e in realtà solo una cosa
alla volta, ma può almeno

918
00:42:43,240 --> 00:42:45,790
guardare una cosa poi la
prossima cosa proprio accanto ad esso.

919
00:42:45,790 --> 00:42:47,380
>> Quindi, sono questi in ordine?

920
00:42:47,380 --> 00:42:48,032
Ovviamente no.

921
00:42:48,032 --> 00:42:48,740
Allora sai cosa?

922
00:42:48,740 --> 00:42:51,020
Perché non prendere il bambino
passaggi risoluzione di questo problema

923
00:42:51,020 --> 00:42:53,410
invece di fare questi fantasia
algoritmi come Ben, dove

924
00:42:53,410 --> 00:42:56,440
E 'una specie di risolverlo da
scorrendo la lista

925
00:42:56,440 --> 00:42:59,670
invece di fare quello che ho fatto, dove
Ho solo tipo di riparato come andiamo?

926
00:42:59,670 --> 00:43:03,650
Diciamo solo letteralmente abbattere il
nozione di ordine numerico order--,

927
00:43:03,650 --> 00:43:06,990
chiamare quello che want--
in questi confronti a coppie.

928
00:43:06,990 --> 00:43:07,590
>> Quattro e uno.

929
00:43:07,590 --> 00:43:09,970
E 'questo l'ordine corretto?

930
00:43:09,970 --> 00:43:11,310
Quindi cerchiamo di sistemare le cose.

931
00:43:11,310 --> 00:43:14,700
Uno e quattro, e poi
ci limiteremo a Ricevuto.

932
00:43:14,700 --> 00:43:15,560
Va bene, bene.

933
00:43:15,560 --> 00:43:17,022
Ho sistemato uno e quattro.

934
00:43:17,022 --> 00:43:18,320
Tre e due?

935
00:43:18,320 --> 00:43:18,820
No.

936
00:43:18,820 --> 00:43:21,690
Lasciate che le mie parole corrispondono le dita.

937
00:43:21,690 --> 00:43:23,695
Quattro e tre?

938
00:43:23,695 --> 00:43:27,930
>> Non è in ordine, così ho intenzione
fare uno, tre, quattro, due.

939
00:43:27,930 --> 00:43:28,680
Ok bene.

940
00:43:28,680 --> 00:43:32,310
Ora quattro e due?

941
00:43:32,310 --> 00:43:33,370
Abbiamo bisogno di risolvere questo problema, anche.

942
00:43:33,370 --> 00:43:36,700
Quindi uno, tre, due, quattro.

943
00:43:36,700 --> 00:43:39,820
Quindi è risolto?

944
00:43:39,820 --> 00:43:43,170
No, ma è più vicino al filtrate?

945
00:43:43,170 --> 00:43:48,930
>> E ', perché abbiamo fissato questo
errore, abbiamo fissato questo errore,

946
00:43:48,930 --> 00:43:50,370
e abbiamo fissato questo errore.

947
00:43:50,370 --> 00:43:52,420
Così abbiamo fissato tre errori senza dubbio.

948
00:43:52,420 --> 00:43:58,100
Ancora in realtà non guardare ordinato, ma
è oggettivamente più vicino alla ordinato

949
00:43:58,100 --> 00:44:00,080
perché abbiamo fissato alcuni di questi errori.

950
00:44:00,080 --> 00:44:02,047
>> Ora cosa faccio adesso?

951
00:44:02,047 --> 00:44:03,630
I tipi di raggiunto la fine della lista.

952
00:44:03,630 --> 00:44:05,680
Mi sembrava di aver risolto
tutti gli errori, ma no.

953
00:44:05,680 --> 00:44:08,510
Poiché in questo caso, alcuni numeri
potrebbe aver bollito su più vicino

954
00:44:08,510 --> 00:44:10,410
ad altri numeri che
sono ancora fuori uso.

955
00:44:10,410 --> 00:44:12,951
Quindi cerchiamo di farlo di nuovo, e io
basta farlo al suo posto questa volta.

956
00:44:12,951 --> 00:44:14,170
Uno e tre?

957
00:44:14,170 --> 00:44:14,720
Va bene.

958
00:44:14,720 --> 00:44:16,070
Tre e due?

959
00:44:16,070 --> 00:44:17,560
Naturalmente no, quindi cerchiamo di cambiare la situazione.

960
00:44:17,560 --> 00:44:19,160
Così due, tre.

961
00:44:19,160 --> 00:44:21,340
Tre e quattro?

962
00:44:21,340 --> 00:44:24,370
Ed ora facciamo solo essere
particolarmente pedante qui.

963
00:44:24,370 --> 00:44:26,350
E 'allineati?

964
00:44:26,350 --> 00:44:29,280
È l'uomo sai che è ordinato.

965
00:44:29,280 --> 00:44:30,400
>> Dovrei provare di nuovo.

966
00:44:30,400 --> 00:44:31,900
Così Olivia propone provo di nuovo.

967
00:44:31,900 --> 00:44:32,530
Perché?

968
00:44:32,530 --> 00:44:35,810
Poiché un computer non dispone
il lusso dei nostri occhi umani

969
00:44:35,810 --> 00:44:38,080
di un semplice sguardo back-- OK, ho finito.

970
00:44:38,080 --> 00:44:41,610
Come fa il computer a determinare
che l'elenco è ora ordinato?

971
00:44:41,610 --> 00:44:44,590
Meccanicamente.

972
00:44:44,590 --> 00:44:47,650
>> Dovrei passare attraverso
ancora una volta, e solo se

973
00:44:47,650 --> 00:44:51,190
Non fare / trovare eventuali errori posso
poi concludere come il computer, sì,

974
00:44:51,190 --> 00:44:51,980
siamo a posto.

975
00:44:51,980 --> 00:44:54,850
Così uno e due, due e
tre, tre e quattro.

976
00:44:54,850 --> 00:44:58,030
Ora posso definitivamente dire che questo è
ordinato, perché ho fatto alcuna modifica.

977
00:44:58,030 --> 00:45:01,940
Ora sarebbe un errore e basta
sciocca se io, il computer,

978
00:45:01,940 --> 00:45:05,640
ha chiesto ancora una volta quelle stesse domande
in attesa di risposte diverse.

979
00:45:05,640 --> 00:45:07,110
Non dovrebbe accadere.

980
00:45:07,110 --> 00:45:08,600
>> E così ora la lista è ordinata.

981
00:45:08,600 --> 00:45:12,630
Purtroppo, il tempo di esecuzione
questo algoritmo è anche N al quadrato.

982
00:45:12,630 --> 00:45:13,130
Perché?

983
00:45:13,130 --> 00:45:19,520
Perché hai n numeri, e nel
peggiore dei casi si deve spostare n numeri

984
00:45:19,520 --> 00:45:23,637
N volte perché si deve andare avanti
indietro per controllare e potenzialmente risolvere

985
00:45:23,637 --> 00:45:24,220
questi numeri.

986
00:45:24,220 --> 00:45:26,280
E possiamo fare di più
analisi formale, troppo.

987
00:45:26,280 --> 00:45:29,530
>> Quindi questo è tutto dire che abbiamo preso
tre diversi approcci, uno

988
00:45:29,530 --> 00:45:32,210
di loro immediatamente intuitivo
fuori del blocco di Ben

989
00:45:32,210 --> 00:45:35,170
al mio inserimento suggerito
sorta a questo

990
00:45:35,170 --> 00:45:38,540
dove tipo di perdere di vista
la foresta per gli alberi inizialmente.

991
00:45:38,540 --> 00:45:41,760
Ma poi se si prende un passo indietro,
voilà, abbiamo fissato la nozione di ordinamento.

992
00:45:41,760 --> 00:45:43,824
Quindi questo è, oserei dire,
un livello inferiore forse

993
00:45:43,824 --> 00:45:45,740
di alcune di quelle altre
algoritmi, ma cerchiamo di

994
00:45:45,740 --> 00:45:48,550
vedere se non possiamo visualizzare
questi attraverso questo.

995
00:45:48,550 --> 00:45:51,450
>> Quindi, questo è un bel
un software che qualcuno

996
00:45:51,450 --> 00:45:56,110
ha scritto utilizzando barre colorate che di
intenzione di fare quanto segue per noi.

997
00:45:56,110 --> 00:45:57,736
Ciascuna di queste barre rappresenta un numero.

998
00:45:57,736 --> 00:46:00,026
Taller il bar, il più grande
il numero, più piccolo è il bar,

999
00:46:00,026 --> 00:46:00,990
minore è il numero.

1000
00:46:00,990 --> 00:46:05,880
Quindi idealmente vogliamo un bel piramide
dove inizia piccolo e diventa grande,

1001
00:46:05,880 --> 00:46:08,330
e ciò significherebbe che
queste barre vengono ordinati.

1002
00:46:08,330 --> 00:46:11,200
Quindi ho intenzione di andare avanti e scegliere,
per esempio, l'algoritmo di Ben

1003
00:46:11,200 --> 00:46:13,990
first-- selection sort.

1004
00:46:13,990 --> 00:46:16,220
>> E notare quello che sta facendo.

1005
00:46:16,220 --> 00:46:18,670
Il modo in cui hanno scelto di
visualizzare questo algoritmo

1006
00:46:18,670 --> 00:46:22,090
è che, proprio come me
passeggiando per la mia lista,

1007
00:46:22,090 --> 00:46:24,710
questo programma è a piedi
attraverso il suo elenco di numeri,

1008
00:46:24,710 --> 00:46:28,160
evidenziando in rosa ogni
numero che si sta guardando.

1009
00:46:28,160 --> 00:46:32,360
E quello che sta per accadere in questo momento?

1010
00:46:32,360 --> 00:46:35,154
>> Il più piccolo numero che
I o Ben trovato improvvisamente

1011
00:46:35,154 --> 00:46:36,820
viene spostato all'inizio della lista.

1012
00:46:36,820 --> 00:46:40,037
E notare che hanno fatto sfrattare
il numero che era lì,

1013
00:46:40,037 --> 00:46:41,120
e che è perfettamente bene.

1014
00:46:41,120 --> 00:46:42,600
Non ho fatto in quel livello di dettaglio.

1015
00:46:42,600 --> 00:46:44,308
Ma abbiamo bisogno di mettere
quel numero da qualche parte,

1016
00:46:44,308 --> 00:46:47,775
così abbiamo appena spostato al
luogo aperto che è stato creato.

1017
00:46:47,775 --> 00:46:49,900
Quindi ho intenzione di accelerare questo
up, perché altrimenti

1018
00:46:49,900 --> 00:46:51,871
diventa molto noioso rapidamente.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animazione speed-- ci andiamo.

1021
00:46:58,600 --> 00:47:01,850
Così ora lo stesso principio
Io ero l'applicazione, ma si

1022
00:47:01,850 --> 00:47:06,540
può iniziare a sentire l'algoritmo, se si
volontà, o di vederlo un po 'più chiaramente.

1023
00:47:06,540 --> 00:47:13,190
E questo algoritmo ha l'effetto di
selezionando l'elemento più piccolo successivo,

1024
00:47:13,190 --> 00:47:16,422
così si sta andando a cominciare a
vederlo rampa sulla sinistra.

1025
00:47:16,422 --> 00:47:19,130
E su ogni iterazione, come ho
proposto, fa un po 'meno lavoro.

1026
00:47:19,130 --> 00:47:21,921
Essa non deve andare fino in fondo
indietro verso l'estremità sinistra della lista,

1027
00:47:21,921 --> 00:47:23,900
perché già
sa chi sono allineati.

1028
00:47:23,900 --> 00:47:28,129
Quindi che tipo di sente come se fosse
accelerando, anche se ogni passo è

1029
00:47:28,129 --> 00:47:29,420
prendendo la stessa quantità di tempo.

1030
00:47:29,420 --> 00:47:31,600
C'è solo un minor numero di passaggi rimanenti.

1031
00:47:31,600 --> 00:47:35,240
E ora è possibile tipo di sentire il
algoritmo di ripulire la fine di esso,

1032
00:47:35,240 --> 00:47:37,040
e in effetti ora è risolto.

1033
00:47:37,040 --> 00:47:41,620
>> Così insertion sort è tutto fatto.

1034
00:47:41,620 --> 00:47:43,600
Ho bisogno di ri-casuale la matrice.

1035
00:47:43,600 --> 00:47:45,940
E notare che posso solo
mantenere randomizzazione esso,

1036
00:47:45,940 --> 00:47:50,630
e otterremo un ravvicinamento delle
lo stesso approccio, insertion sort.

1037
00:47:50,630 --> 00:47:55,050
Mi permetta di rallentarlo a qui.

1038
00:47:55,050 --> 00:47:56,915
Cominciamo che oltre.

1039
00:47:56,915 --> 00:47:57,414
Stop.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Saltiamo quattro.

1042
00:48:02,410 --> 00:48:03,200
Ecco quà.

1043
00:48:03,200 --> 00:48:04,190
Randomize essi array.

1044
00:48:04,190 --> 00:48:05,555
E qui si go-- insertion sort.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Giocare.

1047
00:48:12,800 --> 00:48:17,280
Si noti che si tratta di trattare con ogni
elemento che incontra subito,

1048
00:48:17,280 --> 00:48:20,282
ma se appartiene
il posto avviso sbagliato

1049
00:48:20,282 --> 00:48:21,740
tutto il lavoro che deve accadere.

1050
00:48:21,740 --> 00:48:24,700
Dobbiamo continuare a spostare più
e più elementi per fare spazio

1051
00:48:24,700 --> 00:48:27,340
per quello che vogliamo mettere in atto.

1052
00:48:27,340 --> 00:48:30,740
>> Quindi ci stiamo concentrando sulla
estremità sinistra solo l'elenco.

1053
00:48:30,740 --> 00:48:34,460
Si noti che non abbiamo nemmeno guardato at-- noi
non hanno evidenziato in rosa nulla

1054
00:48:34,460 --> 00:48:35,610
a destra.

1055
00:48:35,610 --> 00:48:38,180
Stiamo solo che fare con
i problemi man mano che procediamo,

1056
00:48:38,180 --> 00:48:40,430
ma stiamo creando un sacco di
lavorare per noi stessi ancora.

1057
00:48:40,430 --> 00:48:44,410
E così, se noi accelerare l'operazione
ora di andare a compimento,

1058
00:48:44,410 --> 00:48:46,210
ha una sensazione diversa ad esso davvero.

1059
00:48:46,210 --> 00:48:50,150
E 'solo concentrandosi sulla estremità sinistra ma
facendo un po 'di lavoro come needed--

1060
00:48:50,150 --> 00:48:53,230
tipo di cose smoothing
sopra, aggiustare le cose,

1061
00:48:53,230 --> 00:48:58,350
ma si tratta in ultima analisi, con
ciascun elemento alla volta

1062
00:48:58,350 --> 00:49:07,740
fino ad arrivare a il-- bene, abbiamo
tutti sappiamo come andrà a finire,

1063
00:49:07,740 --> 00:49:09,700
quindi è un po 'deludente, forse.

1064
00:49:09,700 --> 00:49:12,830
>> Ma l'elenco nella end--
spoiler-- sta per essere ordinato.

1065
00:49:12,830 --> 00:49:15,300
Quindi diamo un'occhiata a un ultimo uno.

1066
00:49:15,300 --> 00:49:16,840
Non possiamo ignorare ora.

1067
00:49:16,840 --> 00:49:18,000
Ci siamo quasi.

1068
00:49:18,000 --> 00:49:19,980
Due per andare, uno per andare.

1069
00:49:19,980 --> 00:49:22,680
E voilà.

1070
00:49:22,680 --> 00:49:23,450
Eccellente.

1071
00:49:23,450 --> 00:49:27,220
>> Così ora facciamo un ultimo uno,
ri-randomizzazione con bubble sort.

1072
00:49:27,220 --> 00:49:31,690
E notate qui, soprattutto se lento
giù, questo non tenere in picchiata attraverso.

1073
00:49:31,690 --> 00:49:36,830
Ma notate rende solo a coppie
sorta comparisons-- di soluzioni locali.

1074
00:49:36,830 --> 00:49:39,050
Ma non appena si arriva a
la fine della lista in rosa,

1075
00:49:39,050 --> 00:49:40,690
quello che sta andando ad avere per accadere di nuovo?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Sì, sta andando ad avere per
ricominciare, perché solo

1078
00:49:46,830 --> 00:49:49,870
errori a coppie fisse.

1079
00:49:49,870 --> 00:49:53,120
E che potrebbe aver rivelato altri ancora.

1080
00:49:53,120 --> 00:49:58,950
E così se accelerare questo, ti
vedere che, proprio come dice il nome,

1081
00:49:58,950 --> 00:50:01,870
minore elements-- o meglio,
i più grandi stanno cominciando elements--

1082
00:50:01,870 --> 00:50:03,740
a bollire fino alla cima, se si vuole.

1083
00:50:03,740 --> 00:50:07,380
E gli elementi più piccoli sono
iniziando a bolla verso sinistra.

1084
00:50:07,380 --> 00:50:10,780
E in effetti, questo è il tipo di
l'effetto visivo pure.

1085
00:50:10,780 --> 00:50:17,150
E così questo finirà per finire
in un modo molto simile, anche.

1086
00:50:17,150 --> 00:50:19,160
>> Non abbiamo soffermarsi
su questo particolare.

1087
00:50:19,160 --> 00:50:21,010
Mi permetta di aprire questo ora, anche.

1088
00:50:21,010 --> 00:50:24,040
Ci sono un paio di altri algoritmi di ordinamento
nel mondo, alcuni dei quali

1089
00:50:24,040 --> 00:50:25,580
vengono catturati qui.

1090
00:50:25,580 --> 00:50:29,960
E soprattutto per gli studenti che non sono
necessariamente visiva o matematica,

1091
00:50:29,960 --> 00:50:31,930
come abbiamo fatto prima, possiamo
anche fare questo audially

1092
00:50:31,930 --> 00:50:34,210
se associamo un suono con questo.

1093
00:50:34,210 --> 00:50:36,990
E solo per divertimento, ecco un
pochi diversi algoritmi,

1094
00:50:36,990 --> 00:50:40,950
e uno di loro, in particolare, si è
andando a notare che viene chiamato "merge sort."

1095
00:50:40,950 --> 00:50:43,250
>> In realtà è un fondamentalmente
meglio algoritmo,

1096
00:50:43,250 --> 00:50:45,860
in modo tale che merge sort, uno dei
quelli che state per vedere,

1097
00:50:45,860 --> 00:50:49,170
Non è dell'ordine di n al quadrato.

1098
00:50:49,170 --> 00:50:57,280
E 'nell'ordine di n volte log di
n, che è in realtà più piccole e quindi

1099
00:50:57,280 --> 00:50:58,940
più velocemente di quelle altre tre.

1100
00:50:58,940 --> 00:51:00,670
E ci sono un paio altro
quelle stupide che vedremo.

1101
00:51:00,670 --> 00:51:01,933
>> Quindi qui si va con qualche suono.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Questo è insertion sort, in modo nuovo
è solo trattare con gli elementi

1104
00:51:10,490 --> 00:51:13,420
come vengono.

1105
00:51:13,420 --> 00:51:17,180
Si tratta di bubble sort, quindi è
considerandoli paia alla volta.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
E ancora, i più grandi elementi
sono gorgogliare fino alla cima.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Next up selection sort.

1110
00:51:41,710 --> 00:51:45,420
Questo è l'algoritmo di Ben, dove
ancora una volta sta selezionando in modo iterativo

1111
00:51:45,420 --> 00:51:46,843
l'elemento immediatamente inferiore.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
E ancora, ora si può veramente sentire che
sta accelerando, ma solo nella misura

1114
00:51:53,900 --> 00:51:58,230
come si sta facendo sempre meno
lavorare su ogni iterazione.

1115
00:51:58,230 --> 00:52:04,170
Questo è il più veloce uno, merge sort,
che è l'ordinamento grappoli di numeri

1116
00:52:04,170 --> 00:52:05,971
insieme e poi li unisce.

1117
00:52:05,971 --> 00:52:07,720
Così look-- sinistra
la metà è già ordinato.

1118
00:52:07,720 --> 00:52:14,165
>> Ora è l'ordinamento la metà destra, e
ora sta andando a combinarle in una sola.

1119
00:52:14,165 --> 00:52:19,160
Questo è qualcosa che si chiama "Gnome sorta."

1120
00:52:19,160 --> 00:52:23,460
E si può vedere che tipo di
sta andando avanti e indietro,

1121
00:52:23,460 --> 00:52:27,950
fissare il lavoro un po 'qui e
lì prima di procedere a un nuovo lavoro.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
E questo è tutto.

1124
00:52:33,692 --> 00:52:36,400
C'è un altro tipo, che è
in realtà solo per scopi accademici,

1125
00:52:36,400 --> 00:52:40,980
chiamato "stupido tipo", che prende
i dati, lo ordina in modo casuale,

1126
00:52:40,980 --> 00:52:43,350
e quindi controlla se è ordinato.

1127
00:52:43,350 --> 00:52:47,880
E se non lo è, si ri-ordina esso
casualmente, controlla se è ordinato,

1128
00:52:47,880 --> 00:52:49,440
e se non si ripete.

1129
00:52:49,440 --> 00:52:52,660
E in teoria, probabilisticamente
questo completerà,

1130
00:52:52,660 --> 00:52:54,140
ma dopo un po 'di tempo.

1131
00:52:54,140 --> 00:52:56,930
Non è il più
efficiente di algoritmi.

1132
00:52:56,930 --> 00:53:02,550
Quindi tutte le domande su quelli
particolari algoritmi o niente

1133
00:53:02,550 --> 00:53:04,720
ci correlate, troppo?

1134
00:53:04,720 --> 00:53:09,430
>> Bene, ora prendere in giro a parte quello che tutti
queste linee sono che ho disegnando

1135
00:53:09,430 --> 00:53:15,090
e quello che sto assumendo il computer
può fare sotto la cappa.

1136
00:53:15,090 --> 00:53:18,650
Direi che tutti questi numeri
Continuo drawing-- hanno bisogno di ottenere

1137
00:53:18,650 --> 00:53:21,330
memorizzati da qualche parte nella memoria.

1138
00:53:21,330 --> 00:53:24,130
Ci sbarazzarsi di questo ragazzo ora, anche.

1139
00:53:24,130 --> 00:53:30,110
>> Così un pezzo di memoria in un
computer-- così RAM DIMM è

1140
00:53:30,110 --> 00:53:35,480
quello che abbiamo cercato di ieri, doppio
di memoria in linea module-- assomiglia a questo.

1141
00:53:35,480 --> 00:53:39,370
E ciascuno di questi piccoli chip neri
è un numero di byte, tipicamente.

1142
00:53:39,370 --> 00:53:44,380
E poi le spille d'oro sono come il
fili che collegano al computer,

1143
00:53:44,380 --> 00:53:47,521
e la scheda di silicio verde è solo
ciò che tiene tutto insieme.

1144
00:53:47,521 --> 00:53:48,770
Così che cosa questo significa veramente?

1145
00:53:48,770 --> 00:53:53,180
Se I tipi di disegnare questo stessa immagine,
supponiamo per semplicità

1146
00:53:53,180 --> 00:53:55,280
che questo DIMM, doppio
Inline Memory Module,

1147
00:53:55,280 --> 00:54:00,530
è un gigabyte di RAM, un gigabyte di
la memoria, che è il numero di byte totale?

1148
00:54:00,530 --> 00:54:02,100
Un gigabyte è quanti byte?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Più di quello.

1151
00:54:06,030 --> 00:54:09,960
1.124 è chilo, 1.000.

1152
00:54:09,960 --> 00:54:11,730
Mega è milioni.

1153
00:54:11,730 --> 00:54:14,570
Giga è un miliardo.

1154
00:54:14,570 --> 00:54:15,070
>> Sto mentendo?

1155
00:54:15,070 --> 00:54:16,670
Possiamo anche leggere l'etichetta?

1156
00:54:16,670 --> 00:54:19,920
Questo è in realtà 128
gigabyte, quindi è più.

1157
00:54:19,920 --> 00:54:22,130
Ma fingiamo che
è solo un gigabyte.

1158
00:54:22,130 --> 00:54:25,640
In modo che significa che c'è un miliardo
byte di memoria disponibile per me

1159
00:54:25,640 --> 00:54:29,770
o 8 miliardi di bit, ma stiamo andando
a parlare in termini di byte ora,

1160
00:54:29,770 --> 00:54:30,750
andando avanti.

1161
00:54:30,750 --> 00:54:36,330
>> Quindi, che cosa significa questo è
un byte, questo è un altro byte,

1162
00:54:36,330 --> 00:54:38,680
questo è un altro byte,
e se volevamo

1163
00:54:38,680 --> 00:54:43,280
per essere precisi dovremmo
disegnare un miliardo di piccoli quadrati.

1164
00:54:43,280 --> 00:54:44,320
Ma che cosa significa?

1165
00:54:44,320 --> 00:54:46,420
Beh, vorrei solo lo zoom
in su questa immagine.

1166
00:54:46,420 --> 00:54:50,900
Se ho qualcosa che sembra
come adesso, che è quattro byte.

1167
00:54:50,900 --> 00:54:53,710
>> E così ho potuto mettere quattro numeri qui.

1168
00:54:53,710 --> 00:54:54,990
Uno due tre quattro.

1169
00:54:54,990 --> 00:55:00,170
Oppure potrei mettere quattro lettere o simboli.

1170
00:55:00,170 --> 00:55:02,620
"Hey!" potrebbe andare proprio lì,
perché ciascuna delle lettere,

1171
00:55:02,620 --> 00:55:04,370
abbiamo discusso in precedenza,
potrebbe essere rappresentata

1172
00:55:04,370 --> 00:55:06,650
con otto bit o ASCII o un byte.

1173
00:55:06,650 --> 00:55:09,370
Quindi, in altre parole, è possibile
mettere 8 miliardi di cose dentro

1174
00:55:09,370 --> 00:55:11,137
di questo uno stick di memoria.

1175
00:55:11,137 --> 00:55:14,345
Ora che cosa significa per rimettere le cose
di back to back in memoria come questo?

1176
00:55:14,345 --> 00:55:17,330
Questo è ciò che un programmatore
chiamerebbe un "allineamento".

1177
00:55:17,330 --> 00:55:21,250
In un programma per computer, non pensi
circa l'hardware sottostante, di per sé.

1178
00:55:21,250 --> 00:55:24,427
Basta pensare a te stesso come avere
accesso a un totale miliardo di byte,

1179
00:55:24,427 --> 00:55:26,010
e si può tutto quello che vuoi con esso.

1180
00:55:26,010 --> 00:55:27,880
Ma per convenienza
è generalmente utile

1181
00:55:27,880 --> 00:55:31,202
per mantenere la giusta memoria
accanto all'altra come questo.

1182
00:55:31,202 --> 00:55:33,660
Quindi, se ingrandire una questo--
perché non stiamo certamente andando

1183
00:55:33,660 --> 00:55:39,310
disegnare un miliardo di piccoli squares--
supponiamo che questa scheda rappresenta

1184
00:55:39,310 --> 00:55:40,610
quel bastone della memoria ora.

1185
00:55:40,610 --> 00:55:43,800
E io solo disegnare come molti come il mio
marcatore finisce per dare me qui.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Così ora abbiamo un bastone
di memoria sulla scheda

1188
00:55:52,300 --> 00:55:56,400
che ha ottenuto uno, due, tre, quattro, cinque,
sei, uno, due, tre, quattro, cinque, sei,

1189
00:55:56,400 --> 00:56:01,130
seven-- così 42 byte di
Memoria sullo schermo totale.

1190
00:56:01,130 --> 00:56:01,630
Grazie.

1191
00:56:01,630 --> 00:56:02,838
Sì, ha fatto la mia aritmetica destra.

1192
00:56:02,838 --> 00:56:05,120
Così 42 byte di memoria qui.

1193
00:56:05,120 --> 00:56:06,660
Che cosa significa questo in realtà significa?

1194
00:56:06,660 --> 00:56:09,830
Ebbene, un programmatore di computer
sarebbe in realtà in genere

1195
00:56:09,830 --> 00:56:12,450
pensare a questa memoria come indirizzabile.

1196
00:56:12,450 --> 00:56:16,630
In altre parole, ognuno di questi
posizioni in memoria, in hardware,

1197
00:56:16,630 --> 00:56:18,030
ha un indirizzo univoco.

1198
00:56:18,030 --> 00:56:22,020
>> Non è così complesso come un Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Invece, è solo un numero.

1200
00:56:23,830 --> 00:56:27,930
Questo è il numero di byte pari a zero, questo è
uno, questo è due, questo è tre,

1201
00:56:27,930 --> 00:56:30,327
e questo è 41.

1202
00:56:30,327 --> 00:56:30,910
Apetta un minuto.

1203
00:56:30,910 --> 00:56:32,510
Pensavo di aver detto 42 un momento fa.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Ho iniziato a contare da zero,
in modo che in realtà è corretta.

1206
00:56:37,772 --> 00:56:40,980
Ora non dobbiamo disegnare realtà
come una griglia, e se si disegna come una griglia

1207
00:56:40,980 --> 00:56:43,520
Penso che le cose in realtà
ottenere un po 'fuorviante.

1208
00:56:43,520 --> 00:56:46,650
Quello che un programmatore sarebbe,
nella sua mente,

1209
00:56:46,650 --> 00:56:50,310
generalmente pensare a questo
la memoria, come è proprio come un nastro,

1210
00:56:50,310 --> 00:56:53,340
come un pezzo di nastro adesivo
che va solo avanti e avanti per sempre

1211
00:56:53,340 --> 00:56:54,980
o fino a quando si esaurisce la memoria.

1212
00:56:54,980 --> 00:56:59,200
Quindi un modo più comune per disegnare
e basta pensare a memoria

1213
00:56:59,200 --> 00:57:03,710
sarebbe che questo byte zero, uno,
due, tre, e poi dot, puntini, puntini.

1214
00:57:03,710 --> 00:57:07,650
E hai 42 tali byte totale, anche
se fisicamente si potrebbe effettivamente

1215
00:57:07,650 --> 00:57:09,480
essere qualcosa di più simile a questo.

1216
00:57:09,480 --> 00:57:12,850
>> Quindi, se ora pensate al vostro
memoria, come tale, come un nastro,

1217
00:57:12,850 --> 00:57:17,640
questo è ciò che un programmatore nuovo
chiamerebbe un array di memoria.

1218
00:57:17,640 --> 00:57:20,660
E quando si desidera memorizzare in realtà
qualcosa nella memoria di un computer,

1219
00:57:20,660 --> 00:57:23,290
generalmente conservare le cose
back-to-back to back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Così abbiamo parlato di numeri.

1221
00:57:25,010 --> 00:57:30,880
E quando ho voluto risolvere i problemi
come quattro, uno, tre, due,

1222
00:57:30,880 --> 00:57:33,820
anche se ero appena disegnavo
solo i numeri quattro, uno, tre,

1223
00:57:33,820 --> 00:57:39,490
due sulla scheda, il computer sarebbe
davvero questa configurazione nella memoria.

1224
00:57:39,490 --> 00:57:43,347
>> E quale sarebbe vicino alla
due nella memoria del computer?

1225
00:57:43,347 --> 00:57:44,680
Beh, non c'è risposta.

1226
00:57:44,680 --> 00:57:45,770
Noi non lo sappiamo.

1227
00:57:45,770 --> 00:57:48,200
E finché la
di computer non ne ha bisogno,

1228
00:57:48,200 --> 00:57:51,440
non deve prendersi cura ciò che è prossimo
ai numeri lo fa a cuore.

1229
00:57:51,440 --> 00:57:55,130
E quando ho detto prima che un computer
può solo guardare un indirizzo alla volta,

1230
00:57:55,130 --> 00:57:56,170
questo è una specie di perché.

1231
00:57:56,170 --> 00:57:59,490
>> Non diversamente da un record
giocatore e una testa di lettura

1232
00:57:59,490 --> 00:58:03,030
solo essere in grado di guardare un certo
scanalatura in un record vecchia scuola fisico

1233
00:58:03,030 --> 00:58:06,500
alla volta, analogamente
può un computer grazie

1234
00:58:06,500 --> 00:58:09,810
alla sua CPU e la sua
set di istruzioni Intel,

1235
00:58:09,810 --> 00:58:12,480
tra cui l'istruzione
viene letto dalla memoria

1236
00:58:12,480 --> 00:58:15,590
o salvare un memory--
computer può solo guardare

1237
00:58:15,590 --> 00:58:19,210
in un unico posto per tempo--
talvolta una loro combinazione,

1238
00:58:19,210 --> 00:58:21,770
ma in realtà solo una posizione alla volta.

1239
00:58:21,770 --> 00:58:24,770
Così, quando stavamo facendo
questi vari algoritmi,

1240
00:58:24,770 --> 00:58:28,110
Non sto scrivendo in un
vacuum-- quattro, uno, tre, due.

1241
00:58:28,110 --> 00:58:30,849
Quei numeri in realtà appartengono
qualche parte fisica nella memoria.

1242
00:58:30,849 --> 00:58:32,890
Quindi ci sono piccolo piccolo
transistor o qualche tipo

1243
00:58:32,890 --> 00:58:35,840
dell'elettronica sotto la
Cappuccio memorizzazione di questi valori.

1244
00:58:35,840 --> 00:58:40,460
>> E in totale, la quantità di bit
coinvolto in questo momento, tanto per essere chiari?

1245
00:58:40,460 --> 00:58:45,580
Quindi questo è di quattro byte, o
ora è 32 bit totale.

1246
00:58:45,580 --> 00:58:49,280
Quindi, ci sono in realtà 32 zeri e
quelli che compongono queste quattro cose.

1247
00:58:49,280 --> 00:58:52,070
C'è ancora di più qui, ma
ancora una volta non ci interessa di questo.

1248
00:58:52,070 --> 00:58:55,120
>> Così ora cerchiamo di chiedere a un altro
domanda utilizzando la memoria,

1249
00:58:55,120 --> 00:58:57,519
perché alla fine
della giornata è in varianza.

1250
00:58:57,519 --> 00:59:00,310
Non importa ciò che potremmo fare con
il computer, alla fine della giornata

1251
00:59:00,310 --> 00:59:02,560
l'hardware è ancora la
stesso sotto la cappa.

1252
00:59:02,560 --> 00:59:04,670
Come faccio a conservare una parola qui?

1253
00:59:04,670 --> 00:59:09,710
Ebbene, una parola in un computer come
"Hey!" sarebbe stato conservato proprio come questo.

1254
00:59:09,710 --> 00:59:12,300
E se si voleva una più lunga
parola, si può semplicemente

1255
00:59:12,300 --> 00:59:19,120
sovrascrivere questo e dire qualcosa
come "ciao" e negozio che qui.

1256
00:59:19,120 --> 00:59:23,930
>> Ed ecco, anche, questa contiguità
in realtà è un vantaggio,

1257
00:59:23,930 --> 00:59:26,530
perché un computer può solo
leggere da destra a sinistra.

1258
00:59:26,530 --> 00:59:28,680
Ma ecco una domanda.

1259
00:59:28,680 --> 00:59:33,480
Nel contesto di questa parola,
h-e-l-l-o, punto esclamativo,

1260
00:59:33,480 --> 00:59:38,740
come potrebbe il computer sa dove il
parola comincia e dove finisce la parola?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
Nel contesto dei numeri,
come fa il computer

1263
00:59:43,800 --> 00:59:48,396
sapere per quanto tempo la sequenza di
numeri è o dove si inizia?

1264
00:59:48,396 --> 00:59:50,270
Bene, si scopre fuori--
e non andremo troppo

1265
00:59:50,270 --> 00:59:54,970
in questo livello di detail--
computer si muovono roba in giro in memoria

1266
00:59:54,970 --> 00:59:57,800
letteralmente per mezzo di questi indirizzi.

1267
00:59:57,800 --> 01:00:02,080
Quindi, in un computer, se siete
la scrittura di codice per memorizzare le cose

1268
01:00:02,080 --> 01:00:05,800
come le parole, quello che stai
realmente facendo sta scrivendo

1269
01:00:05,800 --> 01:00:11,320
espressioni che ricordano dove nel
memoria del computer queste parole sono.

1270
01:00:11,320 --> 01:00:14,370
Quindi, mi permetta di fare molto,
esempio molto semplice.

1271
01:00:14,370 --> 01:00:18,260
>> Ho intenzione di andare avanti e
aprire un semplice programma di testo,

1272
01:00:18,260 --> 01:00:20,330
e ho intenzione di creare
un file chiamato hello.c.

1273
01:00:20,330 --> 01:00:22,849
La maggior parte di queste informazioni che
Non andrà in in grande dettaglio,

1274
01:00:22,849 --> 01:00:25,140
ma ho intenzione di scrivere un
programma nella stessa lingua,

1275
01:00:25,140 --> 01:00:31,140
C. Questo è molto più intimidatorio,
Direi, di Scratch,

1276
01:00:31,140 --> 01:00:32,490
ma è molto simile nello spirito.

1277
01:00:32,490 --> 01:00:34,364
In realtà, questi ricci
braces-- è possibile tipo di

1278
01:00:34,364 --> 01:00:37,820
pensare a quello che ho appena fatto come questo.

1279
01:00:37,820 --> 01:00:39,240
>> Facciamo così, in realtà.

1280
01:00:39,240 --> 01:00:45,100
Quando bandiera verde cliccato,
Fare quanto segue.

1281
01:00:45,100 --> 01:00:50,210
Voglio stampare "ciao".

1282
01:00:50,210 --> 01:00:51,500
Quindi questo è ora pseudocodice.

1283
01:00:51,500 --> 01:00:53,000
Sono un po 'confondendo i confini.

1284
01:00:53,000 --> 01:00:56,750
In C, questa lingua sto parlando
A proposito, questa linea di stampa ciao

1285
01:00:56,750 --> 01:01:01,940
in realtà diventa "printf" con
alcune parentesi e un punto e virgola.

1286
01:01:01,940 --> 01:01:03,480
>> Ma è esattamente la stessa idea.

1287
01:01:03,480 --> 01:01:06,730
E questo molto user-friendly
"Quando bandiera verde cliccato" diventa

1288
01:01:06,730 --> 01:01:10,182
il più arcano "void main int."

1289
01:01:10,182 --> 01:01:12,890
E questo non ha davvero alcuna mappatura,
quindi sto solo andando a ignorare.

1290
01:01:12,890 --> 01:01:17,210
Ma le parentesi graffe sono come il
pezzi del puzzle curvi come questo.

1291
01:01:17,210 --> 01:01:18,700
>> Così si può tipo di indovinare.

1292
01:01:18,700 --> 01:01:22,357
Anche se non hai mai programmato prima,
che cosa fa questo programma probabilmente fare?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Probabilmente stampa ciao
con un punto esclamativo.

1295
01:01:28,000 --> 01:01:29,150
>> Quindi proviamo questo.

1296
01:01:29,150 --> 01:01:30,800
Io vado a salvarlo.

1297
01:01:30,800 --> 01:01:34,000
E questo è, ancora, un
ambiente vecchia scuola.

1298
01:01:34,000 --> 01:01:35,420
Non posso fare clic, non riesco a trascinare.

1299
01:01:35,420 --> 01:01:36,910
Devo digitare i comandi.

1300
01:01:36,910 --> 01:01:41,320
Quindi voglio correre il mio programma, in modo da
Potrei fare questo, come hello.c.

1301
01:01:41,320 --> 01:01:42,292
Questo è il file mi sono imbattuto.

1302
01:01:42,292 --> 01:01:43,500
Ma aspetta, mi manca un passo.

1303
01:01:43,500 --> 01:01:46,470
Cosa abbiamo detto è una condizione necessaria
passo per un linguaggio come il C?

1304
01:01:46,470 --> 01:01:49,470
Ho appena scritto fonte
codice, ma che cosa ho bisogno?

1305
01:01:49,470 --> 01:01:50,670
Sì, ho bisogno di un compilatore.

1306
01:01:50,670 --> 01:01:57,670
Quindi sul mio Mac qui, ho un
programma chiamato GCC, GNU C compiler,

1307
01:01:57,670 --> 01:02:03,990
che mi permette di fare questo-- turno
il mio codice sorgente in, che chiameremo,

1308
01:02:03,990 --> 01:02:04,930
codice macchina.

1309
01:02:04,930 --> 01:02:10,180
>> E posso vedere che,
di nuovo, come segue, questi

1310
01:02:10,180 --> 01:02:14,090
sono gli zeri e quelli che ho appena
creato dal mio codice sorgente,

1311
01:02:14,090 --> 01:02:15,730
tutti gli zeri e uno.

1312
01:02:15,730 --> 01:02:17,770
E se voglio correre
il mio program-- succede

1313
01:02:17,770 --> 01:02:23,010
di essere chiamato a.out per
reasons-- storica "ciao".

1314
01:02:23,010 --> 01:02:24,070
Posso correre di nuovo.

1315
01:02:24,070 --> 01:02:25,690
Ciao ciao ciao.

1316
01:02:25,690 --> 01:02:27,430
E sembra funzionare.

1317
01:02:27,430 --> 01:02:31,000
>> Ma questo significa che da qualche parte nel mio
la memoria del computer sono le parole

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, punto esclamativo.

1319
01:02:35,279 --> 01:02:38,070
E si scopre, tanto per fare un a parte,
ciò che un computer normale procedura

1320
01:02:38,070 --> 01:02:40,550
farlo in modo che sappia dove
le cose iniziano e end-- è

1321
01:02:40,550 --> 01:02:42,460
andando a mettere un simbolo speciale qui.

1322
01:02:42,460 --> 01:02:46,064
E la convenzione è quello di mettere il
numero zero alla fine di una parola

1323
01:02:46,064 --> 01:02:48,230
in modo da sapere dove si
in realtà finisce, in modo da

1324
01:02:48,230 --> 01:02:52,750
non tenere la stampa fuori sempre di più
caratteri di quello che effettivamente intenzione.

1325
01:02:52,750 --> 01:02:55,400
>> Ma l'asporto qui, anche
anche se questo è abbastanza arcano,

1326
01:02:55,400 --> 01:02:58,140
è che è in ultima analisi,
relativamente semplice.

1327
01:02:58,140 --> 01:03:04,550
È stata data una sorta di un nastro, un vuoto
spazio su cui è possibile scrivere lettere.

1328
01:03:04,550 --> 01:03:07,150
È sufficiente avere un
simbolo speciale, come arbitrariamente

1329
01:03:07,150 --> 01:03:10,316
il numero zero, per mettere a fine
le tue parole in modo che il computer sa,

1330
01:03:10,316 --> 01:03:13,410
Oh, avrei dovuto interrompere la stampa dopo
Vedo il punto esclamativo.

1331
01:03:13,410 --> 01:03:16,090
Dato che la prossima cosa c'è
è un valore ASCII pari a zero,

1332
01:03:16,090 --> 01:03:19,125
o il carattere null come
qualcuno lo chiamerebbe.

1333
01:03:19,125 --> 01:03:21,500
Ma c'è una specie di problema
qui, e cerchiamo di revert indietro

1334
01:03:21,500 --> 01:03:23,320
di numeri per un attimo.

1335
01:03:23,320 --> 01:03:28,720
Supponiamo che io faccio, infatti,
hanno una serie di numeri,

1336
01:03:28,720 --> 01:03:30,730
e supponiamo che il
programma che sto scrivendo è

1337
01:03:30,730 --> 01:03:34,680
come un libro di grado per un insegnante
e un'aula insegnanti.

1338
01:03:34,680 --> 01:03:38,720
E questo programma permette di lui o lei
digitare i punteggi dei loro studenti

1339
01:03:38,720 --> 01:03:39,960
il quiz.

1340
01:03:39,960 --> 01:03:43,750
E supponiamo che lo studente ottiene
100 sul loro primo quiz, forse

1341
01:03:43,750 --> 01:03:49,920
come un 80 sul successivo, poi un
75, poi a 90 sul quarto quiz.

1342
01:03:49,920 --> 01:03:54,150
>> Quindi, a questo punto della storia,
la matrice è di dimensioni quattro.

1343
01:03:54,150 --> 01:03:58,470
Non c'è assolutamente più memoria nel
computer, ma la matrice, per così dire,

1344
01:03:58,470 --> 01:04:00,350
è di dimensioni quattro.

1345
01:04:00,350 --> 01:04:06,060
Supponiamo ora che l'insegnante vuole
assegnare un quinto quiz alla classe.

1346
01:04:06,060 --> 01:04:08,510
Ebbene, una delle cose che ha
o lei sta per avere a che fare

1347
01:04:08,510 --> 01:04:10,650
è ora memorizzare un valore aggiunto qui.

1348
01:04:10,650 --> 01:04:15,490
Ma se l'array l'insegnante ha
creata in questo programma è di dimensioni per,

1349
01:04:15,490 --> 01:04:22,440
Uno dei problemi con una serie è che
non si può solo continuare ad aggiungere alla memoria.

1350
01:04:22,440 --> 01:04:26,470
Perché quello che se un'altra parte del
il programma ha la parola "hey" proprio lì?

1351
01:04:26,470 --> 01:04:29,650
>> In altre parole, la memoria può essere
utilizzato per nulla in un programma.

1352
01:04:29,650 --> 01:04:33,250
E se in anticipo ho digitato in, hey,
Voglio ingresso quattro punteggi quiz,

1353
01:04:33,250 --> 01:04:34,784
si potrebbe andare qui e qui.

1354
01:04:34,784 --> 01:04:37,700
E se si cambia improvvisamente idea
più tardi e dire che voglio un quinto quiz

1355
01:04:37,700 --> 01:04:40,872
punteggio, non si può solo
metterlo dove vuoi,

1356
01:04:40,872 --> 01:04:42,580
perché ciò che se questo
memoria utilizzata

1357
01:04:42,580 --> 01:04:45,990
per qualcosa else-- qualche altro programma
o qualche altra caratteristica del programma

1358
01:04:45,990 --> 01:04:46,910
che si sta eseguendo?

1359
01:04:46,910 --> 01:04:50,650
Quindi devi pensare in anticipo
come si desidera memorizzare i dati,

1360
01:04:50,650 --> 01:04:54,480
perché ora hai dipinto
se stessi in un angolo digitale.

1361
01:04:54,480 --> 01:04:57,280
>> Così un insegnante potrebbe invece
dire quando si scrive un programma

1362
01:04:57,280 --> 01:04:59,360
memorizzare sua
gradi, sai cosa?

1363
01:04:59,360 --> 01:05:04,180
Ho intenzione di chiedere,
quando si scrive il mio programma,

1364
01:05:04,180 --> 01:05:12,070
che voglio zero, uno, due, tre,
quattro, cinque, sei, otto gradi totali.

1365
01:05:12,070 --> 01:05:15,320
Quindi uno, due, tre, quattro,
cinque, sei, sette, otto.

1366
01:05:15,320 --> 01:05:18,612
L'insegnante può semplicemente over-allocare
la memoria quando si scrive il suo programma

1367
01:05:18,612 --> 01:05:19,570
e dire, sai una cosa?

1368
01:05:19,570 --> 01:05:22,236
Non sono mai intenzione di assegnare più
di otto quiz in un semestre.

1369
01:05:22,236 --> 01:05:23,130
Questo è solo pazzo.

1370
01:05:23,130 --> 01:05:24,470
Non potrò mai destinare tale.

1371
01:05:24,470 --> 01:05:28,270
In modo che in questo modo lui o lei ha la
flessibilità per i punteggi degli studenti negozio,

1372
01:05:28,270 --> 01:05:33,010
come 75, 90, e forse uno in più in cui
lo studente ha ottenuto il credito extra, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Ma se l'insegnante non
utilizza questi tre spazi,

1374
01:05:36,130 --> 01:05:38,860
c'è un takeaway intuitivo qui.

1375
01:05:38,860 --> 01:05:41,410
Lui o lei è solo spreco di spazio.

1376
01:05:41,410 --> 01:05:44,790
In altre parole, c'è questa
compromesso comune in programmazione

1377
01:05:44,790 --> 01:05:48,241
dove è possibile allocare
esattamente la quantità di memoria che si desidera,

1378
01:05:48,241 --> 01:05:51,490
il rialzo dei quali è che sei Super
efficient-- tu non sia uno spreco

1379
01:05:51,490 --> 01:05:54,640
a tutto-- ma il lato negativo di cui
è cosa succede se si cambia idea quando

1380
01:05:54,640 --> 01:05:58,780
utilizzando il programma che si desidera memorizzare
più dati di quanto originariamente destinati.

1381
01:05:58,780 --> 01:06:03,030
>> Così forse la soluzione è, quindi,
scrivere i programmi in modo tale

1382
01:06:03,030 --> 01:06:05,605
che usano più memoria
quanto ne abbiano bisogno.

1383
01:06:05,605 --> 01:06:07,730
In questo modo non si sta andando
di incorrere in questo problema,

1384
01:06:07,730 --> 01:06:09,730
ma sei stato uno spreco.

1385
01:06:09,730 --> 01:06:12,960
E la più memoria il programma utilizza,
come abbiamo discusso ieri, meno

1386
01:06:12,960 --> 01:06:15,410
la memoria che è disponibile
per altri programmi,

1387
01:06:15,410 --> 01:06:18,790
Quanto prima il computer potrebbe rallentare
a causa di memoria virtuale.

1388
01:06:18,790 --> 01:06:22,670
E così la soluzione ideale potrebbe essere quello che?

1389
01:06:22,670 --> 01:06:24,610
>> Under, che ripartisce sembra male.

1390
01:06:24,610 --> 01:06:27,030
Over-ripartisce sembra male.

1391
01:06:27,030 --> 01:06:31,120
Quindi, quale potrebbe essere una soluzione migliore?

1392
01:06:31,120 --> 01:06:32,390
Riallocazione.

1393
01:06:32,390 --> 01:06:33,590
Essere più dinamica.

1394
01:06:33,590 --> 01:06:37,520
Non sforzatevi di scegliere un
priori, all'inizio, ciò che si vuole.

1395
01:06:37,520 --> 01:06:41,370
E certamente non più di-allocare,
per non essere uno spreco.

1396
01:06:41,370 --> 01:06:45,770
>> E così, per raggiungere questo obiettivo, abbiamo
bisogno di gettare questa struttura dati,

1397
01:06:45,770 --> 01:06:48,100
per così dire, di distanza.

1398
01:06:48,100 --> 01:06:51,080
E così quello che un programmatore
si utilizzano in genere

1399
01:06:51,080 --> 01:06:55,940
è qualcosa che non una chiamata
serie, ma una lista collegata.

1400
01:06:55,940 --> 01:07:00,860
In altre parole, lui o lei
iniziare a pensare a loro memoria

1401
01:07:00,860 --> 01:07:05,280
come tipo di una forma che
può disegnare nel modo seguente.

1402
01:07:05,280 --> 01:07:08,520
Se voglio memorizzare un numero in
un program-- quindi è settembre

1403
01:07:08,520 --> 01:07:12,600
Ho dato ai miei studenti un quiz; voglio
per memorizzare primo quiz degli studenti,

1404
01:07:12,600 --> 01:07:16,220
e hanno ottenuto un 100 sul it-- I
Sto andando a chiedere il mio computer,

1405
01:07:16,220 --> 01:07:19,540
a titolo del programma ho
scritta, per un pezzo di memoria.

1406
01:07:19,540 --> 01:07:22,570
E ho intenzione di archiviare il
numero 100 in essa, e il gioco è fatto.

1407
01:07:22,570 --> 01:07:24,820
>> Poi un paio di settimane più tardi
quando ottengo il mio secondo quiz,

1408
01:07:24,820 --> 01:07:27,890
ed è il momento di digitare
in quel 90%, sto andando

1409
01:07:27,890 --> 01:07:32,129
per chiedere al computer, hey, computer,
posso avere un altro pezzo di memoria?

1410
01:07:32,129 --> 01:07:34,170
Sta andando a darmi questo
vuoto pezzo di memoria.

1411
01:07:34,170 --> 01:07:39,370
Ho intenzione di mettere il numero 90,
ma nel mio programma in qualche modo o other--

1412
01:07:39,370 --> 01:07:42,100
e non ci preoccupare
La sintassi per questo-- ho bisogno

1413
01:07:42,100 --> 01:07:44,430
in qualche modo concatenare queste cose insieme.

1414
01:07:44,430 --> 01:07:47,430
E io li farò concatenare con
quella che appare come una freccia qui.

1415
01:07:47,430 --> 01:07:50,050
>> Il terzo quiz che viene in su,
Sto per dire, hey, computer,

1416
01:07:50,050 --> 01:07:51,680
dammi un altro pezzo di memoria.

1417
01:07:51,680 --> 01:07:54,660
E ho intenzione di mettere giù
qualunque cosa fosse, come 75,

1418
01:07:54,660 --> 01:07:56,920
e devo catena di questo
insieme ora in qualche modo.

1419
01:07:56,920 --> 01:08:00,290
Quarto quiz arriva, e forse
che è verso la fine del semestre.

1420
01:08:00,290 --> 01:08:03,140
E a quel punto il mio programma
potrebbe essere utilizzando la memoria

1421
01:08:03,140 --> 01:08:05,540
dappertutto, tutto fisicamente.

1422
01:08:05,540 --> 01:08:08,170
E così solo per calci, io sono
andando a disegnare questa via

1423
01:08:08,170 --> 01:08:11,260
quiz-- ho dimenticato quello che era; io
che forse un 80 o something--

1424
01:08:11,260 --> 01:08:12,500
fin qui.

1425
01:08:12,500 --> 01:08:15,920
>> Ma va bene, perché pittoricamente
Sto andando a disegnare questa linea.

1426
01:08:15,920 --> 01:08:19,063
In altre parole, in realtà,
in hardware del computer,

1427
01:08:19,063 --> 01:08:20,979
il primo punteggio potrebbe
finiscono qui perché è

1428
01:08:20,979 --> 01:08:22,529
proprio all'inizio del semestre.

1429
01:08:22,529 --> 01:08:25,810
Il prossimo potrebbe finire qui
perché un po 'di tempo è passato

1430
01:08:25,810 --> 01:08:27,210
e il programma continua a funzionare.

1431
01:08:27,210 --> 01:08:30,060
Il punteggio successivo, che era
un 75, potrebbe essere qui.

1432
01:08:30,060 --> 01:08:33,420
E l'ultimo punteggio potrebbe essere
un 80, che è qui.

1433
01:08:33,420 --> 01:08:38,729
>> Quindi, in realtà, fisicamente, questo potrebbe essere
ciò che la memoria del computer assomiglia.

1434
01:08:38,729 --> 01:08:41,569
Ma questo non è un utile mentale
paradigma per un programmatore di computer.

1435
01:08:41,569 --> 01:08:44,649
Perché si deve preoccuparsi in cui il
diamine i dati è di finire?

1436
01:08:44,649 --> 01:08:46,200
Volete solo per memorizzare i dati.

1437
01:08:46,200 --> 01:08:49,390
>> Questo è un po 'come la nostra discussione
precedente del disegno del cubo.

1438
01:08:49,390 --> 01:08:52,200
Perché ti interessa cosa
l'angolo è del cubo

1439
01:08:52,200 --> 01:08:53,740
e come si deve girare a disegnarlo?

1440
01:08:53,740 --> 01:08:54,950
Volete solo un cubo.

1441
01:08:54,950 --> 01:08:57,359
Allo stesso modo qui,
solo voglia di libro di grado.

1442
01:08:57,359 --> 01:08:59,559
Hai voglia di pensare
questo come un elenco di numeri.

1443
01:08:59,559 --> 01:09:01,350
Chi se ne frega come è
implementato in hardware?

1444
01:09:01,350 --> 01:09:05,180
>> Così l'astrazione ora
è questa immagine qui.

1445
01:09:05,180 --> 01:09:07,580
Questa è una lista collegata, come
un programmatore potrebbe chiamare,

1446
01:09:07,580 --> 01:09:10,640
nella misura in cui si dispone di un
lista, ovviamente, di numeri.

1447
01:09:10,640 --> 01:09:14,990
Ma è collegata pittoricamente
per mezzo di queste frecce,

1448
01:09:14,990 --> 01:09:18,510
e tutte queste frecce are-- sotto
il cofano, se siete curiosi,

1449
01:09:18,510 --> 01:09:23,210
ricordare che il nostro hardware fisico ha
indirizzi zero, uno, due, tre, quattro.

1450
01:09:23,210 --> 01:09:28,465
Tutte queste frecce sono è come una mappa
o direzioni, dove se 90 è-- ora

1451
01:09:28,465 --> 01:09:29,090
Ho avuto modo di contare.

1452
01:09:29,090 --> 01:09:31,750
>> Zero, uno, due, tre,
quattro, cinque, sei, sette.

1453
01:09:31,750 --> 01:09:35,640
Sembra che il 90 è a
memoria del numero di indirizzo sette.

1454
01:09:35,640 --> 01:09:38,460
Tutte queste frecce sono è
come un piccolo pezzo di carta

1455
01:09:38,460 --> 01:09:42,439
che sta dando indicazioni per il
programma che dice che seguono questa mappa

1456
01:09:42,439 --> 01:09:43,880
per arrivare alla posizione di sette.

1457
01:09:43,880 --> 01:09:46,680
E ci si trova il
secondo punteggio quiz dello studente.

1458
01:09:46,680 --> 01:09:52,100
Nel frattempo, il 75-- se continuo questo,
questo è sette, otto, 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
>> Quest'altra freccia rappresenta solo
una mappa di locazione di memoria 15.

1461
01:09:59,080 --> 01:10:02,550
Ma ancora una volta, il programmatore fa generalmente
non si preoccupano di questo livello di dettaglio.

1462
01:10:02,550 --> 01:10:05,530
E in più ogni programmazione
il linguaggio di oggi, il programmatore

1463
01:10:05,530 --> 01:10:10,490
Non si sa nemmeno dove in memoria
questi numeri sono in realtà.

1464
01:10:10,490 --> 01:10:14,830
Tutto lui o lei deve preoccuparsi è
che sono in qualche modo collegati insieme

1465
01:10:14,830 --> 01:10:18,390
in una struttura di dati come questo.

1466
01:10:18,390 --> 01:10:21,580
>> Ma si scopre non
per ottenere troppo tecnico.

1467
01:10:21,580 --> 01:10:27,430
Ma proprio perché possiamo forse
permettersi di avere questa discussione qui,

1468
01:10:27,430 --> 01:10:33,630
supponiamo di rivisitare
questo problema qui di un array.

1469
01:10:33,630 --> 01:10:35,780
Vediamo se ci dispiace andare qui.

1470
01:10:35,780 --> 01:10:42,950
Questo è 100, 90, 75, e 80.

1471
01:10:42,950 --> 01:10:44,980
>> Permettetemi brevemente fare questa affermazione.

1472
01:10:44,980 --> 01:10:48,980
Questo è un array, e di nuovo, la
Caratteristica saliente di un array

1473
01:10:48,980 --> 01:10:52,400
è che tutti i dati è tornato a
back to back in memory-- letteralmente

1474
01:10:52,400 --> 01:10:56,830
Un byte o forse quattro byte,
un numero fisso di byte di distanza.

1475
01:10:56,830 --> 01:11:00,710
In una lista collegata, che potremmo disegnare
in questo modo, sotto il cofano che

1476
01:11:00,710 --> 01:11:02,000
sa dove che roba è?

1477
01:11:02,000 --> 01:11:03,630
Non ha nemmeno bisogno di scorrere come questo.

1478
01:11:03,630 --> 01:11:06,050
Alcuni dei dati potrebbe essere
verso sinistra lassù.

1479
01:11:06,050 --> 01:11:07,530
Non si sa nemmeno.

1480
01:11:07,530 --> 01:11:15,430
>> E così con una matrice, si dispone di un
funzionalità nota come accesso casuale.

1481
01:11:15,430 --> 01:11:20,570
E quali mezzi ad accesso casuale è
che il computer può saltare immediatamente

1482
01:11:20,570 --> 01:11:22,730
in qualsiasi posizione in un array.

1483
01:11:22,730 --> 01:11:23,580
Perché?

1484
01:11:23,580 --> 01:11:26,000
Poiché il computer sa
che la prima posizione è

1485
01:11:26,000 --> 01:11:29,540
zero, uno, due e tre.

1486
01:11:29,540 --> 01:11:33,890
>> E così, se si vuole andare da
questo elemento per l'elemento successivo,

1487
01:11:33,890 --> 01:11:36,099
letteralmente, in
la mente del computer, è sufficiente aggiungere uno.

1488
01:11:36,099 --> 01:11:39,140
Se si vuole andare al terzo elemento,
basta aggiungere tra-- elemento successivo, basta

1489
01:11:39,140 --> 01:11:40,290
Aggiungi uno.

1490
01:11:40,290 --> 01:11:42,980
Tuttavia, in questa versione
della storia, supponiamo

1491
01:11:42,980 --> 01:11:46,080
il computer è attualmente alla ricerca
in o trattare con il numero 100.

1492
01:11:46,080 --> 01:11:49,770
Come si arriva a quello successivo
grade nel libro di grado?

1493
01:11:49,770 --> 01:11:52,560
>> Bisogna prendere sette
passi, che è arbitraria.

1494
01:11:52,560 --> 01:11:58,120
Per arrivare a quello successivo, è necessario
prendere un altro otto passi per arrivare a 15.

1495
01:11:58,120 --> 01:12:02,250
In altre parole, non è un
costante divario tra i numeri,

1496
01:12:02,250 --> 01:12:04,857
e così ci vuole solo la
computer più tempo è il punto.

1497
01:12:04,857 --> 01:12:06,940
Il computer deve cercare
attraverso la memoria al fine

1498
01:12:06,940 --> 01:12:08,990
per trovare quello che stai cercando.

1499
01:12:08,990 --> 01:12:14,260
>> Quindi considerando un array tende ad essere un
dati veloce structure-- perché

1500
01:12:14,260 --> 01:12:17,610
può letteralmente fare semplice aritmetica
e arrivare dove si vuole con l'aggiunta di uno,

1501
01:12:17,610 --> 01:12:21,300
per instance-- una lista collegata,
sacrificate quella caratteristica.

1502
01:12:21,300 --> 01:12:24,020
Non si può solo andare dalla prima
al secondo al terzo al quarto posto.

1503
01:12:24,020 --> 01:12:25,240
Bisogna seguire la mappa.

1504
01:12:25,240 --> 01:12:28,160
Devi prendere più passi
per arrivare a quei valori, che

1505
01:12:28,160 --> 01:12:30,230
sembrerebbe essere aggiunta un costo.

1506
01:12:30,230 --> 01:12:35,910
Quindi stiamo pagando un prezzo, ma quello che era
la caratteristica che Dan stava cercando qui?

1507
01:12:35,910 --> 01:12:38,110
Che cosa fa un elenco collegato
a quanto pare ci permettono di fare,

1508
01:12:38,110 --> 01:12:40,240
che era l'origine
questa particolare storia?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Di preciso.

1511
01:12:43,830 --> 01:12:46,220
Una dimensione dinamica ad esso.

1512
01:12:46,220 --> 01:12:48,040
Possiamo aggiungere a questa lista.

1513
01:12:48,040 --> 01:12:51,430
Possiamo anche ridurre la lista, in modo
che stiamo utilizzando solo la quantità di memoria

1514
01:12:51,430 --> 01:12:55,560
come vogliamo davvero e così
siamo mai troppo, che ripartisce.

1515
01:12:55,560 --> 01:12:58,470
>> Ora basta per essere veramente pignoli esigente,
c'è un costo nascosto.

1516
01:12:58,470 --> 01:13:01,980
Quindi non si dovrebbe lasciarmi convincere
che questo è un compromesso convincente.

1517
01:13:01,980 --> 01:13:04,190
C'è un altro costo nascosto qui.

1518
01:13:04,190 --> 01:13:06,550
Il vantaggio, per essere chiari,
è che otteniamo dinamismo.

1519
01:13:06,550 --> 01:13:10,359
Se voglio un altro elemento, posso solo
disegnare e mettere un numero in là.

1520
01:13:10,359 --> 01:13:12,150
E allora posso collegarlo
con una foto qui,

1521
01:13:12,150 --> 01:13:14,970
che è qui, ancora una volta, se ho
Mi dipinto in un angolo,

1522
01:13:14,970 --> 01:13:19,410
se qualcosa sta già usando
la memoria qui, io sono fuori di fortuna.

1523
01:13:19,410 --> 01:13:21,700
Io stesso ho dipinto in un angolo.

1524
01:13:21,700 --> 01:13:24,390
>> Ma qual è il nascosto
costare in questa foto?

1525
01:13:24,390 --> 01:13:27,690
Non è solo la quantità
di tempo che ci vuole

1526
01:13:27,690 --> 01:13:29,870
andare da qui a qui,
che è sette passi, poi

1527
01:13:29,870 --> 01:13:32,820
otto fasi, che è più di uno.

1528
01:13:32,820 --> 01:13:34,830
Che cosa è un altro costo nascosto?

1529
01:13:34,830 --> 01:13:35,440
Non appena il tempo.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Ulteriori informazioni sono
necessario per raggiungere questa immagine.

1532
01:13:49,940 --> 01:13:53,210
>> Sì, quella mappa, quei piccoli frammenti di
carta, come continuo a descriverli come.

1533
01:13:53,210 --> 01:13:55,650
Questi arrows-- coloro che non sono liberi.

1534
01:13:55,650 --> 01:13:57,660
Un computer-- sai
ciò che un computer ha.

1535
01:13:57,660 --> 01:13:58,790
Ha zero e uno.

1536
01:13:58,790 --> 01:14:03,170
Se si vuole rappresentare una freccia o un
mappa o un numero, è necessario qualche ricordo.

1537
01:14:03,170 --> 01:14:05,950
Così l'altro prezzo che
pagare per una lista collegata,

1538
01:14:05,950 --> 01:14:09,070
una scienza informatico comune
risorsa, è anche spazio.

1539
01:14:09,070 --> 01:14:11,710
>> E infatti così, così comunemente,
Tra i compromessi

1540
01:14:11,710 --> 01:14:15,580
nella progettazione di ingegneria del software
sistemi è il tempo e space--

1541
01:14:15,580 --> 01:14:18,596
sono due dei vostri ingredienti, due
dei tuoi ingredienti più costosi.

1542
01:14:18,596 --> 01:14:21,220
Questo mi sta costando più tempo
perché devo seguire questa mappa,

1543
01:14:21,220 --> 01:14:25,730
ma è anche mi è costato più spazio
perché devo mantenere questa mappa intorno.

1544
01:14:25,730 --> 01:14:28,730
Così la speranza, come abbiamo tipo di
discusso nel corso ieri e oggi,

1545
01:14:28,730 --> 01:14:31,720
è che i benefici
saranno superiori ai costi.

1546
01:14:31,720 --> 01:14:33,870
>> Ma non c'è soluzione ovvia qui.

1547
01:14:33,870 --> 01:14:35,870
Forse è better--
a la rapido e sporco,

1548
01:14:35,870 --> 01:14:38,660
come Kareem proposto earlier--
gettare memoria al problema.

1549
01:14:38,660 --> 01:14:42,520
Basta acquistare più memoria, pensare di meno
difficile di risolvere il problema,

1550
01:14:42,520 --> 01:14:44,595
e risolvere in un modo più semplice.

1551
01:14:44,595 --> 01:14:46,720
E infatti in precedenza, quando
abbiamo parlato di compromessi,

1552
01:14:46,720 --> 01:14:49,190
non was spazio in
il computer e il tempo.

1553
01:14:49,190 --> 01:14:51,810
Era giunto il momento di sviluppo, che
è ancora un'altra risorsa.

1554
01:14:51,810 --> 01:14:54,829
>> Quindi, di nuovo, è questo equilibrio
cercando di decidere quale di queste cose

1555
01:14:54,829 --> 01:14:55,870
siete disposti a spendere?

1556
01:14:55,870 --> 01:14:57,380
Quale è il meno costoso?

1557
01:14:57,380 --> 01:15:01,040
Che produce i risultati migliori?

1558
01:15:01,040 --> 01:15:01,540
Sì?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Infatti.

1561
01:15:12,580 --> 01:15:15,970
In questo caso, se siete
che rappresenta numeri nella maps--

1562
01:15:15,970 --> 01:15:18,820
questi sono chiamati in molte lingue
"puntatori" o "indirizzi" -

1563
01:15:18,820 --> 01:15:20,390
è il doppio dello spazio.

1564
01:15:20,390 --> 01:15:24,390
Che non devono essere così male come doppio se
in questo momento stiamo solo la memorizzazione dei numeri.

1565
01:15:24,390 --> 01:15:27,410
Supponiamo che siamo stati memorizzati presso
i dati dei pazienti in un hospital--

1566
01:15:27,410 --> 01:15:30,870
così i nomi di Pierson, numeri di telefono,
numeri di previdenza sociale, medico

1567
01:15:30,870 --> 01:15:31,540
storia.

1568
01:15:31,540 --> 01:15:34,160
Questa casella potrebbe essere molto,
molto più grande, nel qual caso

1569
01:15:34,160 --> 01:15:38,000
un minuscolo puntatore, l'indirizzo
la prossima element-- non è un grosso problema.

1570
01:15:38,000 --> 01:15:40,620
E 'un tale frangia
costo non importa.

1571
01:15:40,620 --> 01:15:43,210
Ma in questo caso, sì, è un raddoppio.

1572
01:15:43,210 --> 01:15:45,290
Buona domanda.

1573
01:15:45,290 --> 01:15:47,900
>> Parliamo di un tempo
poco più concretamente.

1574
01:15:47,900 --> 01:15:50,380
Qual è il tempo di esecuzione
di cercare questa lista?

1575
01:15:50,380 --> 01:15:53,640
Supponiamo che io volevo cercare
attraverso tutti i gradi degli studenti,

1576
01:15:53,640 --> 01:15:55,980
e c'è n gradi
in questa struttura dati.

1577
01:15:55,980 --> 01:15:58,830
Anche qui, si può prendere in prestito
il vocabolario della precedente.

1578
01:15:58,830 --> 01:16:00,890
Questa è una struttura dati lineare.

1579
01:16:00,890 --> 01:16:04,570
>> Big O di n è ciò che è necessario per ottenere
alla fine di questa struttura di dati,

1580
01:16:04,570 --> 01:16:08,410
whereas-- e non abbiamo visto
questo before-- una matrice ti dà

1581
01:16:08,410 --> 01:16:13,555
ciò che si chiama costante di tempo, il che significa
un passo o due gradini o 10 steps--

1582
01:16:13,555 --> 01:16:14,180
non importa.

1583
01:16:14,180 --> 01:16:15,440
Si tratta di un numero fisso.

1584
01:16:15,440 --> 01:16:17,440
Non ha nulla a che fare con
la dimensione della matrice.

1585
01:16:17,440 --> 01:16:20,130
E la ragione di ciò,
di nuovo, è ad accesso casuale.

1586
01:16:20,130 --> 01:16:23,180
Il computer può solo immediatamente
passare a un'altra posizione,

1587
01:16:23,180 --> 01:16:27,770
perché sono tutti uguali
distanza da tutto il resto.

1588
01:16:27,770 --> 01:16:29,112
Non c'è pensiero coinvolti.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Tutto ok.

1591
01:16:32,400 --> 01:16:39,230
Quindi, se posso, vorrei provare a
dipingere due immagini finali.

1592
01:16:39,230 --> 01:16:42,830
Un uno molto comune noto come una tabella hash.

1593
01:16:42,830 --> 01:16:51,120
Quindi, per motivare questa discussione,
fammi pensare su come fare questo.

1594
01:16:51,120 --> 01:16:52,610
>> Così come su questo?

1595
01:16:52,610 --> 01:16:55,160
Supponiamo che il problema
noi vogliamo risolvere ora

1596
01:16:55,160 --> 01:16:58,360
sta attuando in un dictionary--
così un sacco di parole inglesi

1597
01:16:58,360 --> 01:16:59,330
o qualsiasi altra cosa.

1598
01:16:59,330 --> 01:17:02,724
E l'obiettivo è quello di essere in grado di rispondere
domande del modulo è presente una parola?

1599
01:17:02,724 --> 01:17:04,640
Così si desidera implementare
un correttore ortografico, basta

1600
01:17:04,640 --> 01:17:07,220
come un dizionario fisico
che si può guardare le cose in.

1601
01:17:07,220 --> 01:17:10,490
Supponiamo che io dovessi fare questo con un array.

1602
01:17:10,490 --> 01:17:12,590
Ho potuto fare questo.

1603
01:17:12,590 --> 01:17:20,756
>> E supponiamo che le parole sono mela
e banana e melone.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
E non riesco a pensare di frutta
che iniziano con d, quindi siamo solo

1606
01:17:26,465 --> 01:17:27,590
andando ad avere tre frutti.

1607
01:17:27,590 --> 01:17:31,510
Quindi questo è un array, e siamo
memorizzare tutte queste parole

1608
01:17:31,510 --> 01:17:34,200
in questo dizionario come un array.

1609
01:17:34,200 --> 01:17:39,350
La domanda, allora, è come gli altri
potrebbe memorizzare queste informazioni?

1610
01:17:39,350 --> 01:17:43,160
>> Beh, sto tipo di barare qui, perché
ciascuna di queste lettere nella parola

1611
01:17:43,160 --> 01:17:44,490
è davvero un byte individuale.

1612
01:17:44,490 --> 01:17:46,740
Quindi, se ho davvero voluto essere
nit-schizzinosi, dovrei davvero

1613
01:17:46,740 --> 01:17:49,600
essere dividere questo in su in tanto
piccoli blocchi di memoria,

1614
01:17:49,600 --> 01:17:51,289
e abbiamo potuto fare esattamente questo.

1615
01:17:51,289 --> 01:17:53,580
Ma stiamo andando a correre in
lo stesso problema di prima.

1616
01:17:53,580 --> 01:17:56,674
E se, come Merriam Webster o Oxford
fa ogni anno di successo aggiungono parole

1617
01:17:56,674 --> 01:17:59,340
al dictionary-- non lo facciamo
necessariamente voler dipingere noi stessi

1618
01:17:59,340 --> 01:18:00,780
in un angolo con una serie?

1619
01:18:00,780 --> 01:18:05,710
>> Così, invece, forse un approccio più intelligente
è quello di mettere Apple nel proprio nodo o scatola,

1620
01:18:05,710 --> 01:18:11,190
come diremmo, banana, e
allora qui abbiamo melone.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
E noi stringa di queste cose insieme.

1623
01:18:16,790 --> 01:18:19,980
Quindi questa è la matrice, e
questa è la lista collegata.

1624
01:18:19,980 --> 01:18:23,300
Se non riesco a vedere, è solo
dice "matrice", e questo dice "lista".

1625
01:18:23,300 --> 01:18:25,780
>> Così abbiamo la stessa
questioni precise come prima,

1626
01:18:25,780 --> 01:18:28,600
per cui ora abbiamo
dinamismo nella nostra lista collegata.

1627
01:18:28,600 --> 01:18:31,090
Ma abbiamo un dizionario piuttosto lento.

1628
01:18:31,090 --> 01:18:32,870
Supponiamo che io voglio cercare una parola.

1629
01:18:32,870 --> 01:18:35,430
Mi potrebbe prendere grande O di n
passi, perché la parola potrebbe

1630
01:18:35,430 --> 01:18:37,840
essere fino a fine
la lista, come melone.

1631
01:18:37,840 --> 01:18:40,600
E si scopre che
in programmazione, una specie

1632
01:18:40,600 --> 01:18:42,700
del Santo Graal dei dati
strutture, è qualcosa

1633
01:18:42,700 --> 01:18:46,620
che ti dà costante
il tempo come un array

1634
01:18:46,620 --> 01:18:50,870
ma che ti dà ancora dinamismo.

1635
01:18:50,870 --> 01:18:52,940
>> Così possiamo avere il meglio dei due mondi?

1636
01:18:52,940 --> 01:18:55,570
E in effetti, c'è qualcosa
chiamato la tabella di hash

1637
01:18:55,570 --> 01:18:59,320
che permette di fare esattamente
che, seppur approssimativamente.

1638
01:18:59,320 --> 01:19:03,140
Una tabella hash è un amatore
struttura di dati che

1639
01:19:03,140 --> 01:19:06,340
può pensare come il
combinazione di un array--

1640
01:19:06,340 --> 01:19:12,390
e ho intenzione di disegnarlo
come questo-- e liste collegate

1641
01:19:12,390 --> 01:19:17,310
che io traggo come questo qui.

1642
01:19:17,310 --> 01:19:19,760
>> E il modo in cui questa cosa
opere è il seguente.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Se questo now-- hash table--
è la mia struttura terzo dei dati,

1645
01:19:29,540 --> 01:19:32,590
e voglio archiviare
parole in questo, non lo faccio

1646
01:19:32,590 --> 01:19:35,440
desidera memorizzare solo tutte le
parole back to back to back to back.

1647
01:19:35,440 --> 01:19:37,430
Voglio sfruttare qualche
un'informazione

1648
01:19:37,430 --> 01:19:40,330
circa le parole che vi permetterà
Mi capito dove è più veloce.

1649
01:19:40,330 --> 01:19:43,666
>> Quindi, dato il parole mela
e banana e melone,

1650
01:19:43,666 --> 01:19:45,040
Ho deliberatamente scelto quelle parole.

1651
01:19:45,040 --> 01:19:45,340
Perché?

1652
01:19:45,340 --> 01:19:47,631
Che sorta di fondamentalmente
differente circa il tre?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Qual è l'ovvio?

1655
01:19:51,484 --> 01:19:52,900
Iniziano con lettere diverse.

1656
01:19:52,900 --> 01:19:53,900
>> Allora sai cosa?

1657
01:19:53,900 --> 01:19:57,120
Invece di mettere tutte le mie parole nella
lo stesso bucket, per così dire,

1658
01:19:57,120 --> 01:20:00,390
come in una lunga lista, perché non fare
Io, almeno, provo una ottimizzazione

1659
01:20:00,390 --> 01:20:04,180
e fare le mie liste 1/26 più a lungo.

1660
01:20:04,180 --> 01:20:07,440
Una ottimizzazione convincente
potrebbe essere perché non fare

1661
01:20:07,440 --> 01:20:10,650
I-- quando si inserisce una parola
in questa struttura dati,

1662
01:20:10,650 --> 01:20:14,300
nella memoria del computer, perché
Non ho messo tutti «A», le parole qui,

1663
01:20:14,300 --> 01:20:17,270
tutto 'B' parole qui,
e tutti i 'c' parole qui?

1664
01:20:17,270 --> 01:20:24,610
Quindi questo finisce per mettere una mela
qui, banana qui, melone qui,

1665
01:20:24,610 --> 01:20:25,730
e così via.

1666
01:20:25,730 --> 01:20:31,700
>> E se ho un ulteriore
parola like-- cosa è un altro?

1667
01:20:31,700 --> 01:20:36,640
Mela, banana, pera.

1668
01:20:36,640 --> 01:20:39,370
Chiunque pensa di un frutto
che inizia con a, b, o c?

1669
01:20:39,370 --> 01:20:40,570
perfetto Blueberry--.

1670
01:20:40,570 --> 01:20:43,990
Che sta per finire qui.

1671
01:20:43,990 --> 01:20:47,530
E così ci sembra di avere un
marginalmente migliore soluzione,

1672
01:20:47,530 --> 01:20:50,820
perché ora se voglio
per la ricerca di Apple, io

1673
01:20:50,820 --> 01:20:53,200
first-- non lo faccio solo dive
nella mia struttura dati.

1674
01:20:53,200 --> 01:20:54,850
Non mi tuffo nella memoria del mio computer.

1675
01:20:54,850 --> 01:20:56,530
Io prima guardo la prima lettera.

1676
01:20:56,530 --> 01:20:58,610
>> E questo è ciò che un computer
scienziato direbbe.

1677
01:20:58,610 --> 01:21:00,760
È hash nella vostra struttura dati.

1678
01:21:00,760 --> 01:21:04,100
Si prende l'input, che a sua
questo caso è una parola come Apple.

1679
01:21:04,100 --> 01:21:07,150
Si analizza, guardando
la prima lettera in questo caso,

1680
01:21:07,150 --> 01:21:08,340
hashing in tal modo.

1681
01:21:08,340 --> 01:21:10,950
Hashing è un termine generale per cui
si prende qualcosa come input

1682
01:21:10,950 --> 01:21:12,116
e si produce un output.

1683
01:21:12,116 --> 01:21:15,090
E l'uscita dal fatto che
caso è la posizione

1684
01:21:15,090 --> 01:21:18,150
si desidera cercare, la prima
posizione, secondo posizione, terzo.

1685
01:21:18,150 --> 01:21:22,160
Quindi l'ingresso è mela,
l'uscita è prima.

1686
01:21:22,160 --> 01:21:25,054
L'ingresso è di banana, il
uscita dovrebbe essere secondo.

1687
01:21:25,054 --> 01:21:27,220
L'ingresso è melone,
l'uscita dovrebbe essere terzo.

1688
01:21:27,220 --> 01:21:30,320
L'ingresso è di mirtillo, il
uscita dovrebbe essere di nuovo secondo.

1689
01:21:30,320 --> 01:21:34,010
Ed è quello che ti aiuta a prendere
scorciatoie attraverso la memoria

1690
01:21:34,010 --> 01:21:39,050
per arrivare a parole
o dati in modo più efficace.

1691
01:21:39,050 --> 01:21:43,330
>> Ora, questo riduce il nostro tempo potenzialmente
da tanto quanto uno su 26,

1692
01:21:43,330 --> 01:21:45,850
perché se si assume che si
avere il maggior numero di "a" parole come "z"

1693
01:21:45,850 --> 01:21:48,080
parole come parole "Q", che
non è realmente realistic--

1694
01:21:48,080 --> 01:21:50,830
si sta andando ad avere skew tra
alcune lettere del alphabet--

1695
01:21:50,830 --> 01:21:53,204
ma questo sarebbe un incrementale
approccio che non consentono

1696
01:21:53,204 --> 01:21:55,930
di arrivare a parole molto più rapidamente.

1697
01:21:55,930 --> 01:21:59,660
E in realtà, un sofisticato
programma, il Googles del mondo,

1698
01:21:59,660 --> 01:22:02,180
la Facebooks del world--
avrebbero usato una tabella hash

1699
01:22:02,180 --> 01:22:03,740
per molti scopi differenti.

1700
01:22:03,740 --> 01:22:06,590
Ma non sarebbe così ingenuo da
di guardare solo alla prima lettera

1701
01:22:06,590 --> 01:22:09,700
in mela o banana o
pera o melone,

1702
01:22:09,700 --> 01:22:13,420
perché, come si può vedere questi
liste potrebbero ancora arrivare a lungo.

1703
01:22:13,420 --> 01:22:17,130
>> E così questo potrebbe ancora essere una sorta
di linear-- così una sorta di lento,

1704
01:22:17,130 --> 01:22:19,980
come con il grande O di n
che abbiamo discusso in precedenza.

1705
01:22:19,980 --> 01:22:25,290
Quindi, ciò che una vera e propria buona volontà tabella hash
fare-- avrà una matrice molto più grande.

1706
01:22:25,290 --> 01:22:28,574
E userà una molto più
sofisticata funzione di hashing,

1707
01:22:28,574 --> 01:22:30,240
in modo che non si limita a guardare la "a".

1708
01:22:30,240 --> 01:22:35,480
Forse guarda "a-p-p-l-e" e
converte in qualche modo quelle cinque lettere

1709
01:22:35,480 --> 01:22:38,400
nella posizione in cui
Apple dovrebbe essere conservato.

1710
01:22:38,400 --> 01:22:42,660
Stiamo solo ingenuamente con la lettera 'a'
da solo, perché è bello e semplice.

1711
01:22:42,660 --> 01:22:44,600
>> Ma una tabella hash, in
Alla fine, si può pensare

1712
01:22:44,600 --> 01:22:47,270
come una combinazione di
una matrice, ciascuna delle quali

1713
01:22:47,270 --> 01:22:51,700
ha una lista collegata che idealmente
deve essere il più breve possibile.

1714
01:22:51,700 --> 01:22:54,364
E questa non è una soluzione ovvia.

1715
01:22:54,364 --> 01:22:57,280
In realtà, gran parte della messa a punto
che va avanti sotto il cofano quando

1716
01:22:57,280 --> 01:22:59,654
l'attuazione di tali tipi di
sofisticate strutture di dati

1717
01:22:59,654 --> 01:23:01,640
è ciò che è il diritto
lunghezza della matrice?

1718
01:23:01,640 --> 01:23:03,250
Qual è la funzione hash giusto?

1719
01:23:03,250 --> 01:23:04,830
Come si fa a memorizzare le cose in memoria?

1720
01:23:04,830 --> 01:23:07,249
>> Ma rendersi conto di quanto rapidamente
questo tipo di discussione

1721
01:23:07,249 --> 01:23:10,540
escalation, sia così lontano che è una specie
oltre la testa a questo punto, che

1722
01:23:10,540 --> 01:23:11,360
è ok.

1723
01:23:11,360 --> 01:23:18,820
Ma abbiamo iniziato, il richiamo, con veramente
qualcosa di basso livello ed elettroniche.

1724
01:23:18,820 --> 01:23:20,819
E così questo è ancora una volta questo
tema di astrazione,

1725
01:23:20,819 --> 01:23:23,610
dove una volta si inizia a prendere per
concesso, OK, ho it-- c'è

1726
01:23:23,610 --> 01:23:26,680
memoria fisica, OK, capito, ogni
ubicazione fisica ha un indirizzo,

1727
01:23:26,680 --> 01:23:29,910
OK, ho capito, posso rappresentare
quegli indirizzi come arrows--

1728
01:23:29,910 --> 01:23:34,650
si può iniziare molto rapidamente ad avere
conversazioni più sofisticati che

1729
01:23:34,650 --> 01:23:38,360
alla fine sembrano essere permettendoci
per risolvere i problemi come la ricerca

1730
01:23:38,360 --> 01:23:41,620
e classificare in modo più efficace.

1731
01:23:41,620 --> 01:23:44,190
E stare tranquilli, too--
perché credo che questo

1732
01:23:44,190 --> 01:23:48,700
è il più profondo siamo andati in qualche
di questi argomenti CS proper-- Abbiamo

1733
01:23:48,700 --> 01:23:51,880
fatto in un giorno e mezzo in questo
puntare quello che si potrebbe fare di solito sopra

1734
01:23:51,880 --> 01:23:55,520
corso di otto settimane in un semestre.

1735
01:23:55,520 --> 01:23:59,670
>> Tutte le domande su questi?

1736
01:23:59,670 --> 01:24:01,100
No?

1737
01:24:01,100 --> 01:24:01,940
Tutto ok.

1738
01:24:01,940 --> 01:24:05,610
Beh, perché non ci fermiamo lì,
iniziare a pranzo un paio di minuti di anticipo,

1739
01:24:05,610 --> 01:24:07,052
riprendere in quasi un'ora?

1740
01:24:07,052 --> 01:24:08,760
E io indugiare per
un po 'di domande.

1741
01:24:08,760 --> 01:24:11,343
Poi ho intenzione di andare
prendere un paio di chiamate, se va bene.

1742
01:24:11,343 --> 01:24:15,000
Io accendo po 'di musica, nel frattempo,
ma il pranzo dovrebbe essere dietro l'angolo.

1743
01:24:15,000 --> 01:24:17,862