1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Va bene, quindi questo è
CS50 Questa è la fine della settimana di cinque.

3
00:00:15,860 --> 00:00:19,220
E ricordare che l'ultima volta che abbiamo
iniziato a guardare i dati più elaborato

4
00:00:19,220 --> 00:00:22,310
strutture che hanno cominciato a risolvere
problemi, che hanno cominciato a introdurre

5
00:00:22,310 --> 00:00:25,640
nuovi problemi, ma la chiave di questo
era il tipo di filettatura che

6
00:00:25,640 --> 00:00:27,940
iniziato a fare da nodo a nodo.

7
00:00:27,940 --> 00:00:30,085
Quindi questo, naturalmente, è
una lista concatenata.

8
00:00:30,085 --> 00:00:31,960
E per concatenata,
Voglio dire, c'è solo un

9
00:00:31,960 --> 00:00:33,380
filo tra tali nodi.

10
00:00:33,380 --> 00:00:35,890
Si scopre che si può fare amatore
cose come le liste doppiamente collegate

11
00:00:35,890 --> 00:00:38,470
per cui si dispone di una freccia
in entrambe le direzioni, che

12
00:00:38,470 --> 00:00:40,320
può aiutare con alcune efficienze.

13
00:00:40,320 --> 00:00:42,000
Ma questo risolto il problema?

14
00:00:42,000 --> 00:00:43,500
Che cosa ha fatto questo problema risolto?

15
00:00:43,500 --> 00:00:46,620
Perché abbiamo a cuore il Lunedi?

16
00:00:46,620 --> 00:00:49,820
Perché, in teoria, abbiamo a cuore il Lunedi?

17
00:00:49,820 --> 00:00:50,630
Che cosa fa?

18
00:00:50,630 --> 00:00:51,950
>> PUBBLICO: Possiamo ridimensionare dinamicamente.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, in modo che possiamo
ridimensionare dinamicamente.

20
00:00:53,740 --> 00:00:54,710
Complimenti entrambi.

21
00:00:54,710 --> 00:00:57,560
Così si può ridimensionare in modo dinamico questo
struttura di dati, mentre una matrice,

22
00:00:57,560 --> 00:01:00,760
richiamo, è necessario conoscere un
priori come si desidera molto spazio

23
00:01:00,760 --> 00:01:03,870
e se avete bisogno di un po 'più
spazio, sei un po 'fuori di fortuna.

24
00:01:03,870 --> 00:01:05,560
È necessario creare un array completamente nuovo.

25
00:01:05,560 --> 00:01:07,893
Dovete spostare tutti i vostri
dati da uno all'altro,

26
00:01:07,893 --> 00:01:10,600
infine liberare il vecchio matrice
se è possibile, e quindi procedere.

27
00:01:10,600 --> 00:01:13,891
Quali appena si sente molto costoso e molto
inefficiente, e anzi può essere.

28
00:01:13,891 --> 00:01:14,890
Ma questo non è tutto buono.

29
00:01:14,890 --> 00:01:18,180
Paghiamo un prezzo, quello che era uno
dei prezzi più evidenti noi

30
00:01:18,180 --> 00:01:20,550
pagare usando una lista concatenata?

31
00:01:20,550 --> 00:01:22,825
>> PUBBLICO: Dobbiamo usare
doppio spazio per ognuno.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Sì, quindi abbiamo bisogno
almeno il doppio dello spazio.

33
00:01:25,200 --> 00:01:27,700
In realtà, mi sono reso conto di questa immagine
anche un po 'fuorviante,

34
00:01:27,700 --> 00:01:32,200
perché il CS50 IDE in un sacco di moderno
computer, un puntatore o un indirizzo

35
00:01:32,200 --> 00:01:33,700
Non è infatti quattro byte.

36
00:01:33,700 --> 00:01:36,090
E 'molto spesso questi
giorni otto byte, che

37
00:01:36,090 --> 00:01:38,530
mezzi fondo più
rettangoli lì in realtà

38
00:01:38,530 --> 00:01:40,900
sono un po 'il doppio
grande come quello che ho disegnato,

39
00:01:40,900 --> 00:01:44,409
il che significa che si sta utilizzando tre volte
tanto spazio quanto potremmo avere altrimenti.

40
00:01:44,409 --> 00:01:46,700
Ora, allo stesso tempo, siamo
ancora parlando byte, giusto?

41
00:01:46,700 --> 00:01:49,140
Non stiamo parlando necessariamente
megabyte o gigabyte,

42
00:01:49,140 --> 00:01:51,000
a meno che questi dati strutture diventano grandi.

43
00:01:51,000 --> 00:01:54,510
>> E così oggi cominciamo a considerare
come potremmo esplorare i dati

44
00:01:54,510 --> 00:01:57,310
in modo più efficiente se in
Infatti i dati diventa più grande.

45
00:01:57,310 --> 00:02:00,360
Ma proviamo a canonicalizzare
le operazioni primi

46
00:02:00,360 --> 00:02:02,460
che si può fare su questi
tipi di strutture di dati.

47
00:02:02,460 --> 00:02:04,790
Quindi qualcosa come un collegato
Lista supporta generalmente

48
00:02:04,790 --> 00:02:07,514
operazioni come eliminare,
inserire, e la ricerca.

49
00:02:07,514 --> 00:02:08,639
E che cosa voglio dire con questo?

50
00:02:08,639 --> 00:02:11,222
Questo significa solo che di solito,
se la gente sta usando lista collegata,

51
00:02:11,222 --> 00:02:14,287
essi o qualcun altro ha messo in atto
funzioni come cancellare, inserire,

52
00:02:14,287 --> 00:02:16,120
e di ricerca, in modo da poter
effettivamente fare qualcosa

53
00:02:16,120 --> 00:02:18,030
utile con la struttura di dati.

54
00:02:18,030 --> 00:02:20,760
Quindi, diamo un rapido sguardo
a come potremmo implementare

55
00:02:20,760 --> 00:02:24,530
del codice per una lista collegata come segue.

56
00:02:24,530 --> 00:02:27,885
>> Quindi questo è solo un po 'di codice C,
nemmeno un programma completo

57
00:02:27,885 --> 00:02:29,260
che ho davvero frustato rapidamente.

58
00:02:29,260 --> 00:02:32,300
Non è in linea nella distribuzione
codice, perché non effettivamente eseguito.

59
00:02:32,300 --> 00:02:33,790
Ma accorgo ho appena
con un commento, ha detto,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, c'è qualcosa
là, puntini puntini, qualcosa lì.

61
00:02:36,130 --> 00:02:38,410
E facciamo solo guardare
ciò che le parti sono succose.

62
00:02:38,410 --> 00:02:40,790
Così sulla linea tre,
ricordare che questo è ora

63
00:02:40,790 --> 00:02:45,960
Abbiamo proposto che dichiara un nodo scorso
tempo, uno di quegli oggetti rettangolari.

64
00:02:45,960 --> 00:02:48,790
Ha un int che chiameremo N,
ma potremmo chiamarla nulla,

65
00:02:48,790 --> 00:02:51,920
e poi una stella nodo struct chiamata successiva.

66
00:02:51,920 --> 00:02:55,520
E tanto per essere chiari, che secondo
Linea, sulla linea sei, che cosa è?

67
00:02:55,520 --> 00:02:57,930
Che cosa sta facendo per noi?

68
00:02:57,930 --> 00:03:01,044
Perché certamente sembra più
criptico rispetto ai nostri soliti variabili.

69
00:03:01,044 --> 00:03:02,740
>> PUBBLICO: Fa muovere più di un.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: E 'la fa muovere più di un.

71
00:03:04,650 --> 00:03:08,580
E per essere più precisi,
si memorizza l'indirizzo

72
00:03:08,580 --> 00:03:11,582
del nodo che è destinata ad essere
semanticamente accanto ad esso, giusto?

73
00:03:11,582 --> 00:03:13,540
Quindi non sta andando a
spostare necessariamente nulla.

74
00:03:13,540 --> 00:03:15,290
E 'solo andando a
memorizzare un valore, che è

75
00:03:15,290 --> 00:03:17,170
andando ad essere l'indirizzo
di altri nodi,

76
00:03:17,170 --> 00:03:20,810
ed è per questo che abbiamo detto struct
nodo stella, la stella che indica

77
00:03:20,810 --> 00:03:22,370
un puntatore o un indirizzo.

78
00:03:22,370 --> 00:03:26,390
OK, ora se si assume che abbiamo
questo N a nostra disposizione, e facciamo

79
00:03:26,390 --> 00:03:29,490
assumere che qualcun altro ha
inserito un sacco di numeri interi

80
00:03:29,490 --> 00:03:30,400
in una lista collegata.

81
00:03:30,400 --> 00:03:35,640
E quella lista collegata è
puntata da un certo punto

82
00:03:35,640 --> 00:03:39,040
una chiamata lista variabile che è
passato qui come parametro,

83
00:03:39,040 --> 00:03:43,120
Come posso fare per linea
14 di attuazione ricerca?

84
00:03:43,120 --> 00:03:45,990
In altre parole, se io sono l'attuazione
funzione la cui scopo nella vita

85
00:03:45,990 --> 00:03:48,889
è quello di prendere un int e poi il
inizio di una lista collegata,

86
00:03:48,889 --> 00:03:50,430
che è un puntatore alla lista collegata.

87
00:03:50,430 --> 00:03:52,992
Come prima, che credo David
era il nostro volontario il Lunedi,

88
00:03:52,992 --> 00:03:54,700
lui stava indicando
l'intera lista collegata,

89
00:03:54,700 --> 00:03:57,820
è come se stiamo passando
David in quanto il nostro argomento qui.

90
00:03:57,820 --> 00:03:59,990
Come possiamo fare per l'attraversamento di questa lista?

91
00:03:59,990 --> 00:04:04,640
Beh, si scopre che anche se
puntatori sono relativamente nuovo ora a noi,

92
00:04:04,640 --> 00:04:07,010
possiamo fare questo relativamente
semplicemente.

93
00:04:07,010 --> 00:04:09,500
>> Ho intenzione di andare avanti e
dichiarare una variabile temporanea che

94
00:04:09,500 --> 00:04:12,364
per convenzione sta solo andando
per essere chiamato puntatore, o PTR,

95
00:04:12,364 --> 00:04:14,030
ma si potrebbe chiamare tutto quello che vuoi.

96
00:04:14,030 --> 00:04:16,470
E ho intenzione di inizializzare
per l'inizio della lista.

97
00:04:16,470 --> 00:04:20,050
Così si può sorta di pensare a questo
come me l'insegnante, l'altro giorno,

98
00:04:20,050 --> 00:04:23,580
tipo di punta a qualcuno
tra i nostri umani come volontari.

99
00:04:23,580 --> 00:04:26,470
Quindi sono una variabile temporanea che è
solo indicando la stessa cosa

100
00:04:26,470 --> 00:04:31,390
che il nostro casualmente chiamato
volontario Davide stava anche facendo notare.

101
00:04:31,390 --> 00:04:35,440
Ora, mentre puntatore è
non nullo, perché il richiamo

102
00:04:35,440 --> 00:04:40,350
che nulla è un valore speciale sentinel
la delimita la fine della lista,

103
00:04:40,350 --> 00:04:44,280
Così, mentre io non sto indicando la
terra come la nostra ultima volontario

104
00:04:44,280 --> 00:04:47,190
era, andiamo avanti
e procedere come segue.

105
00:04:47,190 --> 00:04:51,820
Se pointer-- e ora io voglio tipo di
a fare quello che abbiamo fatto con lo studente

106
00:04:51,820 --> 00:04:57,410
structure-- se il puntatore punto accanto
equals-- piuttosto, se il puntatore puntino N è uguale

107
00:04:57,410 --> 00:05:02,290
uguaglia la variabile N, la
argomentazione che è stata passata in,

108
00:05:02,290 --> 00:05:05,370
poi voglio andare avanti
e dire ritorno vero.

109
00:05:05,370 --> 00:05:11,020
Ho trovato il numero N all'interno di
uno dei nodi della mia lista collegata.

110
00:05:11,020 --> 00:05:13,500
Ma il punto non è più
lavora in questo contesto,

111
00:05:13,500 --> 00:05:17,260
perché puntatore, PTR, è
infatti un puntatore, un indirizzo,

112
00:05:17,260 --> 00:05:20,632
abbiamo effettivamente possibile meravigliosamente
infine utilizzare un pezzo di sintassi

113
00:05:20,632 --> 00:05:22,590
quel tipo di marche
senso intuitivo e realtà

114
00:05:22,590 --> 00:05:27,870
utilizzare una freccia qui, il che significa che vanno dal
che indirizzo all'intero lì.

115
00:05:27,870 --> 00:05:30,160
Quindi è molto simile a
spirito l'operatore punto,

116
00:05:30,160 --> 00:05:33,860
ma perché puntatore non è un puntatore
e non un struct vera e propria,

117
00:05:33,860 --> 00:05:35,380
usiamo la freccia.

118
00:05:35,380 --> 00:05:40,620
>> Quindi, se il nodo corrente che, la
variabile temporanea, sto indicando

119
00:05:40,620 --> 00:05:43,060
non è N, che cosa voglio fare?

120
00:05:43,060 --> 00:05:45,910
Bene, con i miei volontari umani
che abbiamo avuto qui l'altro giorno,

121
00:05:45,910 --> 00:05:49,710
se il mio primo essere umano non è quello che ho
vuole, e forse il secondo umano non è

122
00:05:49,710 --> 00:05:52,660
quello che voglio, e il terzo, mi
bisogno di continuare a muoversi fisicamente.

123
00:05:52,660 --> 00:05:54,690
Come come faccio a passo attraverso una lista?

124
00:05:54,690 --> 00:05:57,470
Quando abbiamo avuto un array,
appena fatto come me plus plus.

125
00:05:57,470 --> 00:06:03,660
Ma in questo caso, è sufficiente
fare puntatore, ottiene, puntatore, il prossimo.

126
00:06:03,660 --> 00:06:07,580
In altre parole, il campo successivo
è come tutte le mani di sinistra

127
00:06:07,580 --> 00:06:10,880
che i nostri volontari il Lunedi
stavano usando per puntare a qualche altro nodo.

128
00:06:10,880 --> 00:06:12,890
Quelli erano i loro vicini di.

129
00:06:12,890 --> 00:06:17,060
>> Quindi, se voglio fare un passo in questa lista,
Non posso fare io plus plus più,

130
00:06:17,060 --> 00:06:20,120
Io invece devo dire
Io, puntatore, sta andando

131
00:06:20,120 --> 00:06:24,650
per uguagliare qualunque sia il campo successivo è,
Il campo successivo è il campo successivo è,

132
00:06:24,650 --> 00:06:28,350
seguendo tutte quelle mani sinistra
che abbiamo avuto sul palco di puntamento

133
00:06:28,350 --> 00:06:30,000
per alcuni valori successivi.

134
00:06:30,000 --> 00:06:32,590
E se avrò finito
che tutta iterazione,

135
00:06:32,590 --> 00:06:39,330
e, infine, mi ha colpito nulla non avendo
N trovato ancora, appena ritorno falso.

136
00:06:39,330 --> 00:06:44,100
Così ancora una volta, tutto quello che stiamo facendo qui,
come per l'immagine di un momento fa,

137
00:06:44,100 --> 00:06:47,840
è a partire dalla punta verso la
inizio della lista, presumibilmente.

138
00:06:47,840 --> 00:06:50,970
E poi posso controllare, è il valore
Sto cercando pari a nove?

139
00:06:50,970 --> 00:06:52,650
Se è così, torno vero e ho finito.

140
00:06:52,650 --> 00:06:56,450
Se no, aggiorno la mia mano,
Puntatore AKA, per puntare

141
00:06:56,450 --> 00:06:59,540
presso la sede del prossimo freccia e
quindi la posizione successiva della freccia,

142
00:06:59,540 --> 00:07:00,480
e la successiva.

143
00:07:00,480 --> 00:07:03,770
Sto semplicemente camminando attraverso questo array.

144
00:07:03,770 --> 00:07:06,010
>> Così ancora una volta, chi se ne frega?

145
00:07:06,010 --> 00:07:07,861
Come quello che è questo un ingrediente per?

146
00:07:07,861 --> 00:07:10,360
Beh, ricordiamo che abbiamo introdotto
il concetto di una pila, che

147
00:07:10,360 --> 00:07:15,400
è un tipo di dato astratto, in quanto si tratta di
non è una cosa C, non è una cosa CS50,

148
00:07:15,400 --> 00:07:19,430
è un'idea astratta, questa idea di
accatastamento cose uno sopra l'altro

149
00:07:19,430 --> 00:07:21,820
che può essere implementato in
mazzi di modi diversi.

150
00:07:21,820 --> 00:07:25,600
E un modo abbiamo proposto è stato con
un array, o con una lista collegata.

151
00:07:25,600 --> 00:07:29,570
E si scopre che canonicamente, un
pila supporta almeno due operazioni.

152
00:07:29,570 --> 00:07:32,320
E le parole d'ordine sono spinta, a
spingere qualcosa nello stack,

153
00:07:32,320 --> 00:07:34,770
come un nuovo vassoio nel
sala da pranzo, o pop,

154
00:07:34,770 --> 00:07:39,000
il che significa per rimuovere il più alto
vassoio dalla pila in sala

155
00:07:39,000 --> 00:07:41,500
sala, e poi magari un po '
altre operazioni pure.

156
00:07:41,500 --> 00:07:45,770
Così come potremmo definire la struttura
che ora stiamo chiamando una pila?

157
00:07:45,770 --> 00:07:50,020
>> Bene, abbiamo tutti i requisiti
sintassi a nostra disposizione in C. Io dico,

158
00:07:50,020 --> 00:07:53,830
darmi una definizione di tipo
una struttura all'interno di una pila,

159
00:07:53,830 --> 00:07:58,030
Io vado a dire è un array, di un
tutta una serie di numeri e quindi le dimensioni.

160
00:07:58,030 --> 00:08:00,930
Quindi, in altre parole, se voglio
per implementare questo in codice,

161
00:08:00,930 --> 00:08:03,830
lasciatemi andare e solo tipo di
disegnare ciò che questo sta dicendo.

162
00:08:03,830 --> 00:08:06,317
Quindi questo sta dicendo, mi dia una
struttura che ha ottenuto un array,

163
00:08:06,317 --> 00:08:09,400
e io non so che cosa è la capacità,
è apparentemente una costante che ho

164
00:08:09,400 --> 00:08:10,858
definito altrove, e va bene.

165
00:08:10,858 --> 00:08:15,260
Ma supponiamo che sia solo uno,
due, tre, quattro, cinque.

166
00:08:15,260 --> 00:08:16,700
Così capacità è di 5.

167
00:08:16,700 --> 00:08:21,730
Questo elemento interno del mio
struttura sarà chiamato numeri.

168
00:08:21,730 --> 00:08:24,020
E poi ho bisogno di uno
altra variabile a quanto pare

169
00:08:24,020 --> 00:08:27,814
chiamato dimensione che inizialmente ho intenzione
di stipulare viene inizializzato a zero.

170
00:08:27,814 --> 00:08:29,730
Se non c'è niente in
lo stack, la dimensione è pari a zero,

171
00:08:29,730 --> 00:08:31,420
e suoi valori spazzatura nei numeri.

172
00:08:31,420 --> 00:08:33,450
Non ho idea di che cosa è in là ancora.

173
00:08:33,450 --> 00:08:36,059
>> Quindi, se voglio spingere
qualcosa nello stack,

174
00:08:36,059 --> 00:08:40,780
supponiamo che io chiamo la funzione Push, e
Dico spingere 50, come il numero 50,

175
00:08:40,780 --> 00:08:44,090
dove proporrebbe
Vorrei attirare in questo array?

176
00:08:44,090 --> 00:08:47,124
Ci sono cinque diverse risposte possibili.

177
00:08:47,124 --> 00:08:48,790
Dove si vuole spingere il numero 50?

178
00:08:48,790 --> 00:08:51,899
Se l'obiettivo qui, di nuovo, chiamare il
funzione push, passare a un argomento

179
00:08:51,899 --> 00:08:52,940
di 50, dove lo metto?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Cinque possible-- probabilità del 20%
di indovinare correttamente.

182
00:08:59,052 --> 00:08:59,896
Sì?

183
00:08:59,896 --> 00:09:00,740
>> PUBBLICO: Estrema destra.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Estrema destra.

185
00:09:01,990 --> 00:09:08,359
Vi è ora una probabilità del 25%
di indovinare correttamente.

186
00:09:08,359 --> 00:09:09,650
In modo che sarebbe realmente bene.

187
00:09:09,650 --> 00:09:12,770
Per convenzione, lo dirò con una matrice,
avremmo generalmente iniziare a sinistra,

188
00:09:12,770 --> 00:09:14,519
ma potremmo certamente
iniziare a destra.

189
00:09:14,519 --> 00:09:17,478
Così lo spoiler qui sarebbe Sono
probabilmente andando a disegnare sulla sinistra,

190
00:09:17,478 --> 00:09:20,060
proprio come in una matrice normale dove
Comincio andare a sinistra a destra.

191
00:09:20,060 --> 00:09:21,780
Ma se si può capovolgere
l'aritmetica, bene.

192
00:09:21,780 --> 00:09:23,060
Non è solo convenzionale.

193
00:09:23,060 --> 00:09:24,880
Ok, ho bisogno di fare un
altro cambiamento però.

194
00:09:24,880 --> 00:09:27,710
Ora che ho spinto qualcosa
nello stack, e adesso?

195
00:09:27,710 --> 00:09:29,400
>> Va bene, devo incrementare la dimensione.

196
00:09:29,400 --> 00:09:32,600
Così mi permetta di andare avanti e basta
aggiornare questo, che era pari a zero.

197
00:09:32,600 --> 00:09:35,950
E invece ora, sto andando
a mettere in valore uno.

198
00:09:35,950 --> 00:09:39,460
E ora supponiamo che io spingo un altro
numero sullo stack, come 51.

199
00:09:39,460 --> 00:09:42,680
Beh, devo fare un altro
cambiamento, che è fino alla dimensione due.

200
00:09:42,680 --> 00:09:46,100
E poi immagino io spingere un altro
numero sullo stack come 61,

201
00:09:46,100 --> 00:09:52,530
ora ho bisogno di aggiornare il formato un altro
tempo, e ottenere il valore 3 come dimensione.

202
00:09:52,530 --> 00:09:54,690
E ora supponiamo che io chiamo pop.

203
00:09:54,690 --> 00:09:57,250
Ora pop, per convenzione,
non prende un argomento.

204
00:09:57,250 --> 00:10:00,430
Con uno stack, tutta
punto della metafora cassetto

205
00:10:00,430 --> 00:10:03,450
è che non si dispone di discrezionalità
per andare a prendere quel vassoio, tutto quello che puoi fare

206
00:10:03,450 --> 00:10:06,330
è pop quella superiore da
pila, solo perché.

207
00:10:06,330 --> 00:10:08,010
Questo è ciò che questa struttura dati fa.

208
00:10:08,010 --> 00:10:12,250
>> Quindi, che la logica, se io
dire pop, che cosa viene fuori?

209
00:10:12,250 --> 00:10:13,080
Così 61.

210
00:10:13,080 --> 00:10:15,402
Allora, qual è veramente il computer
intenzione di fare in memoria?

211
00:10:15,402 --> 00:10:16,610
Che cosa significa il mio codice ha a che fare?

212
00:10:16,610 --> 00:10:20,330
Cosa vorresti proporre
cambiamo sullo schermo?

213
00:10:20,330 --> 00:10:23,410
Che cosa dovrebbe cambiare?

214
00:10:23,410 --> 00:10:24,960
Scusate?

215
00:10:24,960 --> 00:10:26,334
Così ci liberiamo di 61.

216
00:10:26,334 --> 00:10:27,500
Così posso sicuramente farlo.

217
00:10:27,500 --> 00:10:28,640
E posso liberarmi di 61.

218
00:10:28,640 --> 00:10:30,980
E poi cosa altro
cambiamento deve accadere?

219
00:10:30,980 --> 00:10:33,160
Dimensioni ha probabilmente tornare a due.

220
00:10:33,160 --> 00:10:34,210
E così va bene.

221
00:10:34,210 --> 00:10:36,690
Ma aspettate un minuto, formato
un momento fa aveva tre anni.

222
00:10:36,690 --> 00:10:38,240
Diciamo solo fare un controllo di integrità rapido.

223
00:10:38,240 --> 00:10:41,810
Come Non sapevamo che ci
voleva sbarazzarsi di 61?

224
00:10:41,810 --> 00:10:42,760
Perché stiamo popping.

225
00:10:42,760 --> 00:10:46,450
E così ho questo secondo dimensioni proprietà.

226
00:10:46,450 --> 00:10:48,470
>> Aspetta un attimo, io sono
ripensando a seconda settimana

227
00:10:48,470 --> 00:10:51,660
quando abbiamo iniziato a parlare
array, dove questa era la posizione a zero,

228
00:10:51,660 --> 00:10:55,920
questa era la posizione uno, questo era la posizione
due, questa è la posizione di tre, quattro,

229
00:10:55,920 --> 00:10:58,460
sembra che il
rapporto tra dimensione

230
00:10:58,460 --> 00:11:02,780
e l'elemento che voglio rimuovere
dalla matrice sembra essere proprio quello?

231
00:11:02,780 --> 00:11:05,120
Dimensione meno uno.

232
00:11:05,120 --> 00:11:07,786
E così che è come gli esseri umani
sappiamo 61 viene prima.

233
00:11:07,786 --> 00:11:09,160
Come sta il computer sta per sapere?

234
00:11:09,160 --> 00:11:11,701
Quando il codice, dove probabilmente
vuole fare una taglia meno,

235
00:11:11,701 --> 00:11:14,950
così tre meno uno è di due, e che
significa che vogliamo sbarazzarci di 61.

236
00:11:14,950 --> 00:11:18,000
E allora possiamo davvero aggiornare
le dimensioni in modo che le dimensioni ora

237
00:11:18,000 --> 00:11:20,300
va da tre a due.

238
00:11:20,300 --> 00:11:24,520
E proprio per essere pedante, io vado
a proporre che ho finito, giusto?

239
00:11:24,520 --> 00:11:27,660
Avete proposto intuitivamente
correttamente dovrei liberarmi di 61.

240
00:11:27,660 --> 00:11:30,700
Ma io non ho genere di
sorta di deciso di eliminare 61?

241
00:11:30,700 --> 00:11:33,790
Ho effettivamente dimenticato
che in realtà è lì.

242
00:11:33,790 --> 00:11:37,680
E ripensare a PSET4, se avete letto
l'articolo sulla medicina legale, il PDF

243
00:11:37,680 --> 00:11:40,780
che abbiamo avuto ragazzi leggere, oppure
leggerà questa settimana per PSET4.

244
00:11:40,780 --> 00:11:44,300
Ricordiamo che si tratta in realtà di germano
l'idea di computer forensics.

245
00:11:44,300 --> 00:11:47,820
Quello che un computer non è generalmente
dimentica proprio dove qualcosa è,

246
00:11:47,820 --> 00:11:51,300
ma non va e come
cercare di graffiare fuori o di esclusione

247
00:11:51,300 --> 00:11:54,560
quei bit con zero e uno
o qualche altro modello casuale

248
00:11:54,560 --> 00:11:56,690
a meno che non te lo fanno deliberatamente.

249
00:11:56,690 --> 00:11:58,930
Quindi la vostra intuizione era
a destra, cerchiamo di sbarazzarsi di 61.

250
00:11:58,930 --> 00:12:00,650
Ma in realtà, non dobbiamo dare fastidio.

251
00:12:00,650 --> 00:12:04,040
Abbiamo solo bisogno di dimenticare che
è lì, cambiando la nostra dimensione.

252
00:12:04,040 --> 00:12:05,662
>> Ora c'è un problema con questo stack.

253
00:12:05,662 --> 00:12:07,620
Se continuo a spingere le cose
nello stack, che cosa è

254
00:12:07,620 --> 00:12:11,167
ovviamente succederà
nel giro di poco tempo momenti?

255
00:12:11,167 --> 00:12:12,500
Stiamo andando a corto di spazio.

256
00:12:12,500 --> 00:12:13,580
E che cosa facciamo?

257
00:12:13,580 --> 00:12:14,680
Stiamo tipo di fottuti.

258
00:12:14,680 --> 00:12:19,000
Questa implementazione non consente
noi ridimensionare la matrice, perché usando

259
00:12:19,000 --> 00:12:21,240
questa sintassi, se
ripensare a seconda settimana,

260
00:12:21,240 --> 00:12:23,520
una volta che hai dichiarato
la dimensione di una matrice,

261
00:12:23,520 --> 00:12:26,780
non abbiamo ancora visto un meccanismo dove
è possibile modificare la dimensione della matrice.

262
00:12:26,780 --> 00:12:29,020
E infatti C non ha questa caratteristica.

263
00:12:29,020 --> 00:12:32,524
Se dici darmi cinque
Nths, li chiamano numeri,

264
00:12:32,524 --> 00:12:33,940
è tutto quello che hai intenzione di farlo.

265
00:12:33,940 --> 00:12:38,790
Così facciamo ora a partire da Lunedi, abbiamo
la capacità di esprimere una soluzione

266
00:12:38,790 --> 00:12:42,480
però, abbiamo solo bisogno di modificare
la definizione di una pila

267
00:12:42,480 --> 00:12:46,840
di non essere certo di matrice hard-coded,
ma solo per memorizzare un indirizzo.

268
00:12:46,840 --> 00:12:47,890
>> Ora, perché è questo?

269
00:12:47,890 --> 00:12:51,690
Ora non ci resta che stare bene con
il fatto che quando il mio programma viene eseguito,

270
00:12:51,690 --> 00:12:53,730
Sto presumibilmente intenzione di
chiedere l'umano,

271
00:12:53,730 --> 00:12:55,110
quanti numeri vuoi salvare?

272
00:12:55,110 --> 00:12:56,776
Quindi l'ingresso deve venire da qualche parte.

273
00:12:56,776 --> 00:12:59,140
Ma una volta che so che
numero, quindi posso solo

274
00:12:59,140 --> 00:13:02,470
utilizzare ciò che funziona per dare
me un pezzo di memoria?

275
00:13:02,470 --> 00:13:03,580
Posso usare malloc.

276
00:13:03,580 --> 00:13:06,710
E posso dire qualsiasi numero di
byte Voglio tornare per questi Nths.

277
00:13:06,710 --> 00:13:10,910
E tutto quello che ho per memorizzare i numeri
variabile qui dentro questo struct

278
00:13:10,910 --> 00:13:13,480
dovrebbe essere quello?

279
00:13:13,480 --> 00:13:18,440
Ciò che in realtà va nel
numeri in questo scenario?

280
00:13:18,440 --> 00:13:21,300
Sì, un puntatore al primo
Byte di quel pezzo della memoria,

281
00:13:21,300 --> 00:13:24,940
o più specificamente, l'indirizzo
del primo di tali bytes.

282
00:13:24,940 --> 00:13:27,300
Non importa se si tratta di un
byte o un miliardo di byte,

283
00:13:27,300 --> 00:13:28,890
Ho solo bisogno di preoccuparsi prima.

284
00:13:28,890 --> 00:13:31,530
Perché ciò che le garanzie malloc e
le mie garanzie del sistema operativo,

285
00:13:31,530 --> 00:13:34,170
è che il pezzo di memoria I
ottenere, che sta per essere contigui.

286
00:13:34,170 --> 00:13:35,378
Non ci sara essere lacune.

287
00:13:35,378 --> 00:13:38,576
Quindi, se ho chiesto 50
byte o 1.000 byte,

288
00:13:38,576 --> 00:13:40,450
sono tutti andando essere
back to back to back.

289
00:13:40,450 --> 00:13:44,500
E fino a quando mi ricordo di quanto è grande, come
tanto che ho chiesto, tutto quello che ho bisogno di sapere

290
00:13:44,500 --> 00:13:46,230
è il primo indirizzo.

291
00:13:46,230 --> 00:13:48,660
>> Così ora abbiamo la capacità di codice.

292
00:13:48,660 --> 00:13:51,280
Anche se, sta andando a prendere noi
più tempo per scrivere questo in su,

293
00:13:51,280 --> 00:13:55,900
ora abbiamo potuto riallocare che la memoria da
solo la memorizzazione di un indirizzo diverso lì

294
00:13:55,900 --> 00:13:59,060
se vogliamo una più grande o addirittura
un pezzo inferiore di memoria.

295
00:13:59,060 --> 00:14:00,170
Così qui per un fuori commercio.

296
00:14:00,170 --> 00:14:01,360
Ora abbiamo dinamismo.

297
00:14:01,360 --> 00:14:03,350
Noi abbiamo ancora
contiguità sto sostenendo.

298
00:14:03,350 --> 00:14:05,881
Perché malloc ci darà
un blocco contiguo di memoria.

299
00:14:05,881 --> 00:14:08,630
Ma questo sta per essere un dolore
il collo per noi, il programmatore,

300
00:14:08,630 --> 00:14:09,770
al codice realmente in su.

301
00:14:09,770 --> 00:14:10,730
E 'solo più lavoro.

302
00:14:10,730 --> 00:14:13,930
Abbiamo bisogno di codice simile a quello che ero
sbattere fuori solo un momento fa.

303
00:14:13,930 --> 00:14:16,120
Molto fattibile, ma aggiunge complessità.

304
00:14:16,120 --> 00:14:19,520
E così il tempo di sviluppo, programmatori
il tempo è ancora un altro risorsa

305
00:14:19,520 --> 00:14:22,520
che potremmo aver bisogno di spendere
un po 'di tempo per ottenere nuove funzionalità.

306
00:14:22,520 --> 00:14:24,020
E poi, naturalmente, c'è una coda.

307
00:14:24,020 --> 00:14:26,227
Non andremo in questo
uno in più dettagliato.

308
00:14:26,227 --> 00:14:27,560
Ma è molto simile nello spirito.

309
00:14:27,560 --> 00:14:31,220
Ho potuto implementare una coda, e
le sue operazioni corrispondenti,

310
00:14:31,220 --> 00:14:35,660
enqueue o dequeue, come aggiungere o rimuovere,
è solo un modo più fantasioso di dirlo,

311
00:14:35,660 --> 00:14:38,100
enqueue o dequeue, come segue.

312
00:14:38,100 --> 00:14:41,170
Posso solo darmi una struct
ha di nuovo allineamento di un numero,

313
00:14:41,170 --> 00:14:44,000
ha di nuovo una dimensione,
Ma perché ora serve

314
00:14:44,000 --> 00:14:46,940
per tenere traccia della parte anteriore di una coda?

315
00:14:46,940 --> 00:14:50,630
Non avevo bisogno di sapere
la parte anteriore del mio stack.

316
00:14:50,630 --> 00:14:53,570
Ebbene, se ancora per un
queue-- facciamo solo difficile

317
00:14:53,570 --> 00:14:57,870
codice come avere come cinque
interi qui potenzialmente.

318
00:14:57,870 --> 00:15:00,940
Quindi questo è zero, uno, due, tre, quattro.

319
00:15:00,940 --> 00:15:03,430
Questo sta per essere
chiamato di nuovo i numeri.

320
00:15:03,430 --> 00:15:06,940
E questo sarà chiamato dimensioni.

321
00:15:06,940 --> 00:15:10,056
>> Perché non è sufficiente
di avere solo le dimensioni?

322
00:15:10,056 --> 00:15:11,680
Bene, spingere gli stessi numeri.

323
00:15:11,680 --> 00:15:14,220
Così ho pushed-- io accodato, o spinto.

324
00:15:14,220 --> 00:15:20,150
Ora ti enqueue 50, e poi
51, e poi 61, e puntini puntini.

325
00:15:20,150 --> 00:15:21,070
Ecco, questo è enqueue.

326
00:15:21,070 --> 00:15:23,176
I accodato 50, poi 51, poi 61.

327
00:15:23,176 --> 00:15:25,050
E che sembra identico
ad una pila finora,

328
00:15:25,050 --> 00:15:27,190
tranne che ho bisogno di fare un cambiamento.

329
00:15:27,190 --> 00:15:33,680
Ho bisogno di aggiornare queste dimensioni, così vado
da zero a uno a due per tre ora.

330
00:15:33,680 --> 00:15:35,760
Come faccio a DEQUEUE?

331
00:15:35,760 --> 00:15:36,890
Che cosa succede con dequeue?

332
00:15:36,890 --> 00:15:41,950
Chi dovrebbe venire fuori questa lista prima
se è la linea presso l'Apple Store?

333
00:15:41,950 --> 00:15:42,780
Quindi 50.

334
00:15:42,780 --> 00:15:44,700
Quindi è una specie di complicato questo momento.

335
00:15:44,700 --> 00:15:47,880
Considerando che l'ultima volta che era super
facile da fare solo un formato meno,

336
00:15:47,880 --> 00:15:51,440
Ho arrivare alla fine del mio allineamento efficacemente
dove i numeri sono, rimuove 61.

337
00:15:51,440 --> 00:15:52,920
Ma io non voglio rimuovere 61.

338
00:15:52,920 --> 00:15:55,030
Voglio prendere 50, che
era lì a 05:00

339
00:15:55,030 --> 00:15:56,790
in fila per il
nuovo iPhone o roba del genere.

340
00:15:56,790 --> 00:16:01,200
E così, per sbarazzarsi di 50, I
non si può solo fare questo, giusto?

341
00:16:01,200 --> 00:16:02,547
Posso barrare 50.

342
00:16:02,547 --> 00:16:04,380
Ma abbiamo appena detto noi
non c'è bisogno di essere così anale

343
00:16:04,380 --> 00:16:06,330
da graffiare fuori o nascondere i dati.

344
00:16:06,330 --> 00:16:08,090
Possiamo solo dimenticare dove si trova.

345
00:16:08,090 --> 00:16:12,330
>> Ma se cambio la mia taglia subito per
due, è questo sufficienti informazioni

346
00:16:12,330 --> 00:16:15,711
di sapere cosa sta succedendo nella mia coda?

347
00:16:15,711 --> 00:16:16,680
Non proprio.

348
00:16:16,680 --> 00:16:19,830
Come la mia taglia è di due, ma
dove fa la coda cominciare,

349
00:16:19,830 --> 00:16:22,980
soprattutto se ho ancora
questi stessi numeri in memoria.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Così ho bisogno di ricordare
ora dove il fronte è.

352
00:16:27,090 --> 00:16:29,630
E così come ho proposto su
lì, avremo appena chiamato

353
00:16:29,630 --> 00:16:33,729
Fronte all'ennesima potenza, la cui iniziale
valore deve essere stato quello che?

354
00:16:33,729 --> 00:16:35,270
Zero, solo l'inizio della lista.

355
00:16:35,270 --> 00:16:40,876
Ma ora oltre a decremento
le dimensioni, si incrementa il proprio fronte.

356
00:16:40,876 --> 00:16:42,000
Ora qui è un altro problema.

357
00:16:42,000 --> 00:16:43,030
Così una volta Continuo ad andarci.

358
00:16:43,030 --> 00:16:47,520
Supponiamo che questo è il numero di
come 121, 124, e poi, dannazione,

359
00:16:47,520 --> 00:16:48,610
Sono fuori di spazio.

360
00:16:48,610 --> 00:16:50,390
Ma aspettate un minuto, non lo sono.

361
00:16:50,390 --> 00:16:55,630
Quindi, a questo punto della storia,
supponiamo che la dimensione è uno, due,

362
00:16:55,630 --> 00:17:00,370
tre, quattro, così supporre che il
dimensione è quattro, la parte anteriore è uno,

363
00:17:00,370 --> 00:17:01,621
così 51 è nella parte anteriore.

364
00:17:01,621 --> 00:17:04,329
Voglio mettere un altro numero qui,
ma, dannazione, sono fuori di spazio.

365
00:17:04,329 --> 00:17:06,710
Ma io non sono davvero, giusto?

366
00:17:06,710 --> 00:17:11,192
Dove ho potuto mettere un po '
valore aggiunto, come la 171?

367
00:17:11,192 --> 00:17:13,400
Sì, ho potuto solo tipo di
tornare laggiù, giusto?

368
00:17:13,400 --> 00:17:18,161
E poi attraversare la 50, o
basta sovrascrivere con 171.

369
00:17:18,161 --> 00:17:20,410
E se vi state chiedendo perché
i nostri numeri si sono così casuale,

370
00:17:20,410 --> 00:17:24,150
questi sono comunemente prese di computer
corsi di scienza a Harvard dopo CS50.

371
00:17:24,150 --> 00:17:27,510
Ma quella era una buona ottimizzazione,
perché ora non sto sprecando spazio.

372
00:17:27,510 --> 00:17:30,750
Devo ancora ricordare
quanto è grande questa cosa è totale.

373
00:17:30,750 --> 00:17:31,500
Sono le cinque totale.

374
00:17:31,500 --> 00:17:33,375
Perché non voglio
iniziare a sovrascrivere 51.

375
00:17:33,375 --> 00:17:36,260
Così ora sono ancora fuori di spazio,
così lo stesso problema di prima.

376
00:17:36,260 --> 00:17:39,140
Ma si può vedere come la società
nel codice, probabilmente

377
00:17:39,140 --> 00:17:41,910
dovuto scrivere un po 'di più
complessità per realizzare questo obiettivo.

378
00:17:41,910 --> 00:17:44,510
E in effetti, che cosa operatore
in C probabilmente lascia

379
00:17:44,510 --> 00:17:48,110
si magicamente fare questo la circolarità?

380
00:17:48,110 --> 00:17:50,160
Sì, l'operatore modulo,
il segno di percentuale.

381
00:17:50,160 --> 00:17:53,160
Allora, qual è genere di freddo su una coda,
anche se manteniamo gli array di disegno

382
00:17:53,160 --> 00:17:56,520
come queste linee rette, come, se si
tipo di pensare a questo come curva

383
00:17:56,520 --> 00:18:00,341
intorno come un cerchio, poi basta
intuitivamente che tipo di lavori mentalmente

384
00:18:00,341 --> 00:18:01,590
Penso che un po 'più pulito.

385
00:18:01,590 --> 00:18:05,190
Si sarebbe ancora necessario implementare
che modello mentale nel codice.

386
00:18:05,190 --> 00:18:07,550
Quindi non è così difficile,
in ultima analisi, di attuare,

387
00:18:07,550 --> 00:18:12,430
ma abbiamo ancora perde la size-- piuttosto, il
capacità di ridimensionare, se non facciamo questo.

388
00:18:12,430 --> 00:18:15,310
>> Dobbiamo eliminare l'array, abbiamo
sostituirlo con un unico puntatore,

389
00:18:15,310 --> 00:18:20,010
e poi da qualche parte nel mio codice ho
una chiamata quale funzione per creare effettivamente

390
00:18:20,010 --> 00:18:23,720
la matrice numeri chiamati?

391
00:18:23,720 --> 00:18:26,190
Malloc, o qualche simile
la funzione, esattamente.

392
00:18:26,190 --> 00:18:30,481
Tutte le domande di pile o code.

393
00:18:30,481 --> 00:18:30,980
Sì?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Bella domanda.

396
00:18:34,240 --> 00:18:35,830
Cosa modulo usereste qui.

397
00:18:35,830 --> 00:18:38,520
Quindi in generale, quando si utilizza
mod, si farebbe

398
00:18:38,520 --> 00:18:40,620
con la dimensione della
intera struttura dati.

399
00:18:40,620 --> 00:18:44,120
Così qualcosa come cinque o la capacità, se
è costante, probabilmente è coinvolto.

400
00:18:44,120 --> 00:18:47,100
Ma solo facendo modulo cinque
probabilmente non è sufficiente,

401
00:18:47,100 --> 00:18:51,380
perché abbiamo bisogno di sapere fare noi
avvolgere intorno qui o qui o qui.

402
00:18:51,380 --> 00:18:54,160
Quindi, probabilmente sei anche
andando a voler coinvolgere

403
00:18:54,160 --> 00:18:57,220
la dimensione della cosa, o
la variabile anteriore pure.

404
00:18:57,220 --> 00:19:00,140
Quindi è proprio questo relativamente
semplice espressione aritmetica,

405
00:19:00,140 --> 00:19:02,000
ma modulo sarebbe l'ingrediente fondamentale.

406
00:19:02,000 --> 00:19:03,330
>> Quindi, cortometraggio, se vuoi.

407
00:19:03,330 --> 00:19:05,780
Un'animazione che alcuni
gente di un'altra università

408
00:19:05,780 --> 00:19:08,060
messo insieme che abbiamo
adatto per questa discussione.

409
00:19:08,060 --> 00:19:12,630
Si tratta di Jack apprendimento della
fatti circa le code e le statistiche.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: C'era una volta,
c'era un ragazzo di nome Jack.

412
00:19:21,890 --> 00:19:25,330
Quando si trattava di farsi degli amici,
Jack non ha avuto un talento.

413
00:19:25,330 --> 00:19:28,220
Così Jack andò a parlare con il
ragazzo più popolare che conosceva.

414
00:19:28,220 --> 00:19:30,920
Andò a Lou e chiese, cosa devo fare?

415
00:19:30,920 --> 00:19:33,400
Lou vide che il suo amico
era davvero in difficoltà.

416
00:19:33,400 --> 00:19:36,050
Beh, ha iniziato, solo
guarda come sei vestito.

417
00:19:36,050 --> 00:19:38,680
Non hai i vestiti
con un look diverso?

418
00:19:38,680 --> 00:19:39,660
Sì, ha detto Jack.

419
00:19:39,660 --> 00:19:40,840
Certo che lo faccio.

420
00:19:40,840 --> 00:19:43,320
Vieni a casa mia e
Io farò vedere a voi.

421
00:19:43,320 --> 00:19:44,550
Così se ne andarono a Jack.

422
00:19:44,550 --> 00:19:47,520
E Jack ha mostrato Lou casella
dove teneva tutte le sue camicie,

423
00:19:47,520 --> 00:19:49,260
i suoi pantaloni e le calze.

424
00:19:49,260 --> 00:19:52,290
Lou ha detto, vedo che hai
tutti i vostri vestiti in un mucchio.

425
00:19:52,290 --> 00:19:54,870
Perché non indossare qualche
altri di tanto in tanto?

426
00:19:54,870 --> 00:19:58,020
>> Jack ha detto, bene, quando ho
rimuovere i vestiti e calzini,

427
00:19:58,020 --> 00:20:00,780
Io li lavo e mettere
loro via nella scatola.

428
00:20:00,780 --> 00:20:03,210
Poi viene il prossimo
mattina, e fino io hop.

429
00:20:03,210 --> 00:20:06,380
Vado in scatola e ottenere
i miei vestiti fuori dalla parte superiore.

430
00:20:06,380 --> 00:20:09,070
Lou si rese conto in fretta
il problema con Jack.

431
00:20:09,070 --> 00:20:12,080
Continuava a vestiti, CD,
e libri in pila.

432
00:20:12,080 --> 00:20:14,420
Quando ha raggiunto per
qualcosa da leggere o da indossare,

433
00:20:14,420 --> 00:20:17,100
aveva scelto il libro superiore o la biancheria intima.

434
00:20:17,100 --> 00:20:19,500
Poi, quando ebbe finito, lui
avrebbe messo subito indietro.

435
00:20:19,500 --> 00:20:21,970
Indietro andrebbe, in cima alla pila.

436
00:20:21,970 --> 00:20:24,460
So che la soluzione,
ha detto un forte trionfante.

437
00:20:24,460 --> 00:20:27,090
È necessario imparare a
iniziare a utilizzare una coda.

438
00:20:27,090 --> 00:20:29,870
Lou ha preso i vestiti di Jack e
li appesi nell'armadio.

439
00:20:29,870 --> 00:20:32,710
E, dopo aver svuotato
la scatola, ha appena lanciò.

440
00:20:32,710 --> 00:20:36,500
>> Poi disse, ora Jack, alla fine del
il giorno, mettere i vestiti a sinistra

441
00:20:36,500 --> 00:20:37,990
quando li metti via.

442
00:20:37,990 --> 00:20:41,300
Poi, domani mattina quando si
vedere la luce del sole, ottenere i vostri vestiti

443
00:20:41,300 --> 00:20:43,440
sulla destra, dalla fine della linea.

444
00:20:43,440 --> 00:20:44,880
Non vedi? ha detto Lou.

445
00:20:44,880 --> 00:20:46,370
Sarà così bello.

446
00:20:46,370 --> 00:20:49,770
Potrai indossare tutto una volta
prima di indossare qualcosa di due volte.

447
00:20:49,770 --> 00:20:52,670
E con tutto ciò che in coda
nel suo armadio e ripiano,

448
00:20:52,670 --> 00:20:55,160
Jack ha iniziato a sentirsi
abbastanza sicuro di se stesso.

449
00:20:55,160 --> 00:20:59,720
Tutto grazie a Lou e
la sua meravigliosa coda.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Va bene, è adorabile.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Quindi, ciò che è stato realmente accadendo
in sotto la cappa ora?

453
00:21:10,080 --> 00:21:12,370
Che abbiamo puntatori,
che abbiamo malloc,

454
00:21:12,370 --> 00:21:15,680
che abbiamo la capacità di creare
blocchi di memoria per noi stessi

455
00:21:15,680 --> 00:21:16,344
dinamicamente.

456
00:21:16,344 --> 00:21:18,510
Quindi questo è un quadro che
intravisto proprio l'altro giorno.

457
00:21:18,510 --> 00:21:21,180
Non abbiamo davvero soffermarsi
su di esso, ma questa immagine

458
00:21:21,180 --> 00:21:24,180
è andata avanti sotto
la cappa da settimane.

459
00:21:24,180 --> 00:21:27,050
E così ciò rappresenta, solo
un rettangolo che abbiamo disegnato,

460
00:21:27,050 --> 00:21:28,180
la memoria del computer.

461
00:21:28,180 --> 00:21:31,850
E forse il computer, o CS50
ID, ha un gigabyte di memoria o RAM

462
00:21:31,850 --> 00:21:33,050
o due gigabyte o quattro.

463
00:21:33,050 --> 00:21:34,450
Non ha molta importanza.

464
00:21:34,450 --> 00:21:37,240
Il sistema operativo
Windows o Mac OS o Linux,

465
00:21:37,240 --> 00:21:41,120
essenzialmente permette al vostro programma
pensare che abbia accesso

466
00:21:41,120 --> 00:21:42,982
alla totalità del
memoria del computer,

467
00:21:42,982 --> 00:21:45,440
anche se si potrebbe essere in esecuzione
più programmi contemporaneamente.

468
00:21:45,440 --> 00:21:46,990
Quindi, in realtà, che in realtà non funziona.

469
00:21:46,990 --> 00:21:49,448
Ma è una specie di illusione
dato a tutti i programmi.

470
00:21:49,448 --> 00:21:53,110
Quindi, se tu avessi due giga di RAM, questo
è come il computer potrebbe pensare ad esso.

471
00:21:53,110 --> 00:21:57,110
>> Ora guarda caso, uno di questi
cose, uno di questi segmenti di memoria,

472
00:21:57,110 --> 00:21:58,350
è chiamata una pila.

473
00:21:58,350 --> 00:22:01,680
E in effetti in qualsiasi momento
finora nella scrittura di codice

474
00:22:01,680 --> 00:22:05,900
che hai chiamato un
funzione, per esempio principale.

475
00:22:05,900 --> 00:22:08,410
Ricordo che ogni volta che ho
la memoria del computer disegnato,

476
00:22:08,410 --> 00:22:10,640
Ho sempre disegnare una sorta di
mezzo di un rettangolo qui

477
00:22:10,640 --> 00:22:12,520
e non si preoccupano di parlare
su ciò che è al di sopra.

478
00:22:12,520 --> 00:22:15,980
Perché quando principale si chiama, io rivendico
che si ottiene questo frammento di memoria

479
00:22:15,980 --> 00:22:16,970
che scende qui.

480
00:22:16,970 --> 00:22:20,650
E se principale chiamato una funzione
come scambio, ben di swap va qui.

481
00:22:20,650 --> 00:22:23,720
E si scopre, che è
dove è finire.

482
00:22:23,720 --> 00:22:26,277
Su una cosa chiamata una pila
all'interno della memoria del computer.

483
00:22:26,277 --> 00:22:28,360
Ora, alla fine della giornata,
questo è solo gli indirizzi.

484
00:22:28,360 --> 00:22:30,680
E 'come zero byte,
Byte uno, byte 2 miliardi.

485
00:22:30,680 --> 00:22:33,130
Ma se ci pensate
come questo oggetto rettangolare,

486
00:22:33,130 --> 00:22:35,130
tutto quello che stiamo facendo ogni
tempo che noi chiamiamo una funzione è

487
00:22:35,130 --> 00:22:37,180
stratificazione una nuova fetta di memoria.

488
00:22:37,180 --> 00:22:41,700
Stiamo dando quella funzione una fetta
della propria memoria per funzionare con.

489
00:22:41,700 --> 00:22:44,490
>> Ed ora ricordare che questo è importante.

490
00:22:44,490 --> 00:22:46,400
Perché se noi abbiamo
qualcosa di simile scambio

491
00:22:46,400 --> 00:22:51,610
e due variabili locali come A e B e
cambiamo quei valori da uno e due

492
00:22:51,610 --> 00:22:55,130
a due e uno, richiamo
che quando ritorna di swap,

493
00:22:55,130 --> 00:22:58,330
è come se questa fetta
di memoria è appena andato.

494
00:22:58,330 --> 00:23:00,080
In realtà, è ancora
lì forense.

495
00:23:00,080 --> 00:23:01,940
E qualcosa è ancora realmente lì.

496
00:23:01,940 --> 00:23:05,410
Ma concettualmente, è come
anche se è completamente sparito.

497
00:23:05,410 --> 00:23:10,910
E così principale non conosce alcun lavoro
che è stato fatto in quella funzione di scambio,

498
00:23:10,910 --> 00:23:14,890
a meno che in realtà è passato in quelli
argomenti di puntatore o di riferimento.

499
00:23:14,890 --> 00:23:17,790
Ora, la soluzione fondamentale
a questo problema con lo scambio

500
00:23:17,790 --> 00:23:19,970
sta passando le cose in base all'indirizzo.

501
00:23:19,970 --> 00:23:23,250
Ma si scopre, anche, che cosa è
sta succedendo sopra di tale parte

502
00:23:23,250 --> 00:23:26,330
del rettangolo tutto questo tempo è
ma non c'è più memoria lassù.

503
00:23:26,330 --> 00:23:28,790
E quando si dinamicamente
allocare la memoria,

504
00:23:28,790 --> 00:23:32,020
se è dentro di GetString, che
abbiamo fatto per voi in CS50

505
00:23:32,020 --> 00:23:34,710
biblioteca, o se voi ragazzi
chiamare malloc e chiedere

506
00:23:34,710 --> 00:23:37,950
il sistema operativo per un pezzo di
memoria, non viene dallo stack.

507
00:23:37,950 --> 00:23:40,960
Proviene da un altro luogo
nella memoria del computer

508
00:23:40,960 --> 00:23:42,220
che si chiama l'heap.

509
00:23:42,220 --> 00:23:43,430
E non è affatto differente.

510
00:23:43,430 --> 00:23:44,285
E 'la stessa RAM.

511
00:23:44,285 --> 00:23:45,160
E 'la stessa memoria.

512
00:23:45,160 --> 00:23:49,080
E 'solo la RAM che è fino
lì invece di quaggiù.

513
00:23:49,080 --> 00:23:50,750
>> E così che cosa significa?

514
00:23:50,750 --> 00:23:53,650
Beh, se il computer dispone
una quantità limitata di memoria

515
00:23:53,650 --> 00:23:57,450
e la pila sta crescendo, così
a parlare, e l'heap, secondo

516
00:23:57,450 --> 00:23:59,349
a questa freccia, è in crescita verso il basso.

517
00:23:59,349 --> 00:24:01,140
In altre parole, ogni
ora si chiama malloc,

518
00:24:01,140 --> 00:24:03,430
sei stato dato una fetta
della memoria dall'alto,

519
00:24:03,430 --> 00:24:06,630
allora forse un po 'più basso, poi un po'
più basso, ogni volta che si chiama malloc,

520
00:24:06,630 --> 00:24:10,100
mucchio, è l'utilizzo,
è una specie di crescita,

521
00:24:10,100 --> 00:24:11,950
cresce sempre più vicino a quello che?

522
00:24:11,950 --> 00:24:13,382
Lo stack.

523
00:24:13,382 --> 00:24:14,840
Così fa questo sembra una buona idea?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Voglio dire, dove non è davvero chiaro
cos'altro si può fare se si solo

526
00:24:22,140 --> 00:24:23,910
avere una quantità limitata di memoria.

527
00:24:23,910 --> 00:24:25,200
Ma questo è sicuramente male.

528
00:24:25,200 --> 00:24:27,920
Queste due frecce sono su una
Crash Course uno per l'altro.

529
00:24:27,920 --> 00:24:31,930
>> E si scopre che cattivo, le persone che
sono particolarmente buoni con la programmazione,

530
00:24:31,930 --> 00:24:36,140
e cercando di incidere in computer,
in grado di sfruttare questa realtà.

531
00:24:36,140 --> 00:24:38,290
Infatti, prendiamo in considerazione
un piccolo frammento.

532
00:24:38,290 --> 00:24:41,350
Quindi questo è un esempio si può leggere
circa più in dettaglio su Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Ti segnaliamo voi al
articolo, se curioso.

534
00:24:43,100 --> 00:24:45,650
Ma c'è un attacco generale
noto come buffer overflow che

535
00:24:45,650 --> 00:24:49,570
esiste finché umani
hanno avuto la capacità di manipolare

536
00:24:49,570 --> 00:24:53,120
memoria del computer, in particolare in C.
Quindi questo è un programma molto arbitraria,

537
00:24:53,120 --> 00:24:55,130
ma leggiamo dal basso verso l'alto.

538
00:24:55,130 --> 00:24:57,650
Principale in argc char stella argv.

539
00:24:57,650 --> 00:24:59,830
Quindi è un programma che prende
argomenti della riga di comando.

540
00:24:59,830 --> 00:25:03,620
E tutti i principali fa apparentemente è chiamata
una funzione, lo chiamano F per semplicità.

541
00:25:03,620 --> 00:25:04,610
E passa in ciò?

542
00:25:04,610 --> 00:25:05,490
Argv di uno.

543
00:25:05,490 --> 00:25:09,320
Così passa in qualunque F
la parola è che l'utente ha digitato

544
00:25:09,320 --> 00:25:11,500
al prompt dopo la
nome del programma a tutti.

545
00:25:11,500 --> 00:25:15,730
Così tanto come Cesare o Vigenere, che
si potrebbe ricordare facendo con argv.

546
00:25:15,730 --> 00:25:16,680
>> Allora, qual è F?

547
00:25:16,680 --> 00:25:19,760
F prende in una stringa
come unico argomento,

548
00:25:19,760 --> 00:25:22,100
AKA una stella char, stesso
cosa, come una stringa.

549
00:25:22,100 --> 00:25:24,920
E si chiama arbitrariamente
bar in questo esempio.

550
00:25:24,920 --> 00:25:27,710
E poi char c 12,
solo in termini profani,

551
00:25:27,710 --> 00:25:31,750
ciò che è char c staffa 12 che fa per noi?

552
00:25:31,750 --> 00:25:33,440
Che cosa fare?

553
00:25:33,440 --> 00:25:36,490
L'allocazione della memoria, in particolare
12 byte per 12 caratteri.

554
00:25:36,490 --> 00:25:36,990
Esattamente.

555
00:25:36,990 --> 00:25:40,000
E poi l'ultima riga, mescolare e
copia, probabilmente avete non si vedono.

556
00:25:40,000 --> 00:25:43,360
Questa è una copia della stringa
funzione la cui scopo nella vita

557
00:25:43,360 --> 00:25:48,160
è quello di copiare il suo secondo argomento
nel suo primo argomento,

558
00:25:48,160 --> 00:25:51,190
ma solo fino a un
certo numero di byte.

559
00:25:51,190 --> 00:25:53,860
Così il terzo argomento, dice,
quanti byte si dovrebbe copiare?

560
00:25:53,860 --> 00:25:56,720
La lunghezza della barra,
qualunque sia l'utente ha digitato in.

561
00:25:56,720 --> 00:25:59,320
E il contenuto di
bar, tale stringa, sono

562
00:25:59,320 --> 00:26:02,330
copiati nella memoria puntato a C.

563
00:26:02,330 --> 00:26:04,060
>> Quindi, questo sembra un po 'stupido, e lo è.

564
00:26:04,060 --> 00:26:06,300
E 'un esempio forzato,
ma è rappresentante

565
00:26:06,300 --> 00:26:10,100
di una classe di vettori di attacco,
un modo di attaccare un programma.

566
00:26:10,100 --> 00:26:15,050
Tutto è bello e buono se l'utente
tipi in una parola che è 11 caratteri

567
00:26:15,050 --> 00:26:18,040
o meno, più la barra rovesciata zero.

568
00:26:18,040 --> 00:26:22,830
Che cosa succede se l'utente digita in più di
11 o 12 o 20 o 50 caratteri?

569
00:26:22,830 --> 00:26:25,090
Che cosa è questo programma intenzione di fare?

570
00:26:25,090 --> 00:26:29,360
Colpa Potenzialmente seg. Sta andando
copiare ciecamente tutto nella barra in alto

571
00:26:29,360 --> 00:26:31,750
alla sua lunghezza, che è
letteralmente tutto in bar,

572
00:26:31,750 --> 00:26:36,307
nell'indirizzo puntato a C. Ma C
solo ha preventivamente dato come 12 byte.

573
00:26:36,307 --> 00:26:37,640
Ma non c'è alcun controllo aggiuntivo.

574
00:26:37,640 --> 00:26:38,700
Non c'è, se le condizioni.

575
00:26:38,700 --> 00:26:40,580
Non c'è alcun controllo qui l'errore.

576
00:26:40,580 --> 00:26:43,270
>> E così quello che questo programma è
intenzione di fare è appena ciecamente

577
00:26:43,270 --> 00:26:45,750
copiare una cosa all'altra.

578
00:26:45,750 --> 00:26:47,880
E così, se traiamo questo
come un quadro, ecco

579
00:26:47,880 --> 00:26:49,860
solo un frammento di spazio di memoria.

580
00:26:49,860 --> 00:26:53,470
Così notiamo in fondo, abbiamo
avere la variabile locale bar.

581
00:26:53,470 --> 00:26:57,330
In modo che il puntatore che sta per store--
piuttosto che l'argomento locale che è

582
00:26:57,330 --> 00:26:58,672
andando a memorizzare la barra di stringa.

583
00:26:58,672 --> 00:27:00,380
E poi notare solo
sopra di esso in una pila,

584
00:27:00,380 --> 00:27:02,505
perché ogni volta che si chiede
per la memoria in pila,

585
00:27:02,505 --> 00:27:04,310
va un po '
sopra di esso pittoricamente,

586
00:27:04,310 --> 00:27:06,270
nota che abbiamo 12 byte lì.

587
00:27:06,270 --> 00:27:10,690
Quello in alto a sinistra è C staffa zero e
il fondo quello di destra è C staffa 11.

588
00:27:10,690 --> 00:27:12,870
Questo è solo il modo i computer
andando a stenderlo.

589
00:27:12,870 --> 00:27:18,300
Quindi, solo intuitivamente, se ha più bar
di 12 caratteri in totale, tra cui

590
00:27:18,300 --> 00:27:25,790
il backslash a zero, dove si trova il
12 o la staffa C 12 intenzione di andare?

591
00:27:25,790 --> 00:27:28,440
O meglio dove è il 12 °
carattere o il carattere di 13 °,

592
00:27:28,440 --> 00:27:30,900
il personaggio centesima andare
per finire nella foto?

593
00:27:30,900 --> 00:27:33,400
Sopra o sotto?

594
00:27:33,400 --> 00:27:36,300
>> Giusto, perché, anche se
lo stack in sé cresce verso l'alto,

595
00:27:36,300 --> 00:27:39,590
una volta che hai messo roba in
esso, per motivi costruttivi,

596
00:27:39,590 --> 00:27:41,294
mette la memoria dall'alto verso il basso.

597
00:27:41,294 --> 00:27:44,460
Quindi, se hai più di 12 byte,
avete intenzione di iniziare a sovrascrivere bar.

598
00:27:44,460 --> 00:27:47,280
Ora che è un bug, ma è
Non è un grosso problema.

599
00:27:47,280 --> 00:27:51,130
Ma è un grosso problema, perché c'è
più cose in corso in memoria.

600
00:27:51,130 --> 00:27:53,074
Quindi, ecco come potremmo
mettere ciao, per essere chiari.

601
00:27:53,074 --> 00:27:54,490
Se ho digitato ciao al prompt.

602
00:27:54,490 --> 00:27:59,330
Backslash a zero H-E-L-L-O, finisce dentro
quei 12 byte, e siamo super sicuro.

603
00:27:59,330 --> 00:28:00,330
Tutto bene.

604
00:28:00,330 --> 00:28:03,020
Ma se digito qualcosa
più a lungo, potenzialmente è

605
00:28:03,020 --> 00:28:05,860
andando a insinuarsi nello spazio bar.

606
00:28:05,860 --> 00:28:08,405
Ma peggio ancora, si trasforma
tutto questo tempo,

607
00:28:08,405 --> 00:28:11,530
anche se non abbiamo mai parlato di
esso, lo stack viene utilizzato per altre cose.

608
00:28:11,530 --> 00:28:13,560
Non sono solo le variabili locali.

609
00:28:13,560 --> 00:28:15,100
>> C è un linguaggio di livello molto basso.

610
00:28:15,100 --> 00:28:17,810
Ed è una sorta di segreto
utilizza lo stack anche

611
00:28:17,810 --> 00:28:21,260
a ricordare quando un
funzione viene chiamata, cosa

612
00:28:21,260 --> 00:28:26,040
l'indirizzo è della funzione precedente,
in modo che possa tornare indietro a quella funzione.

613
00:28:26,040 --> 00:28:29,980
Così, quando le chiamate principali scambiano, tra
le cose inseriti nello stack

614
00:28:29,980 --> 00:28:34,380
Non sono scambia solo le variabili locali,
o dei suoi argomenti, anche segretamente spinti

615
00:28:34,380 --> 00:28:37,510
nello stack come rappresentato
al taglio il rosso,

616
00:28:37,510 --> 00:28:40,520
è l'indirizzo del principale fisicamente
nella memoria del computer,

617
00:28:40,520 --> 00:28:44,180
in modo che quando è fatto di swap, il computer
sa che ho bisogno di tornare a principale

618
00:28:44,180 --> 00:28:46,760
e terminare l'esecuzione della funzione principale.

619
00:28:46,760 --> 00:28:51,960
Quindi questo è pericoloso ora, perché se
l'utente digita in ben più di ciao,

620
00:28:51,960 --> 00:28:57,030
tale che l'input dell'utente clobbers
o sovrascrive quella sezione rosso,

621
00:28:57,030 --> 00:28:59,820
logicamente se del computer
solo intenzione di assumere ciecamente

622
00:28:59,820 --> 00:29:03,830
che i byte in quella fetta rosso sono
l'indirizzo al quale deve restituire,

623
00:29:03,830 --> 00:29:09,020
cosa succede se l'avversario è abbastanza intelligente o
la fortuna di mettere una sequenza di byte

624
00:29:09,020 --> 00:29:13,450
lì che sembra un indirizzo,
ma è l'indirizzo del codice

625
00:29:13,450 --> 00:29:18,730
che lui o lei vuole il computer
per eseguire invece di principale?

626
00:29:18,730 --> 00:29:21,670
>> In altre parole, se la cosa
utente sta digitando al prompt,

627
00:29:21,670 --> 00:29:23,850
non è solo qualcosa
come innocuo ciao,

628
00:29:23,850 --> 00:29:28,210
ma in realtà è il codice che è equivalente
eliminare tutti i file di questo utente?

629
00:29:28,210 --> 00:29:30,060
O e-mail la propria password a me?

630
00:29:30,060 --> 00:29:31,940
O avviare la registrazione loro
battiture, giusto?

631
00:29:31,940 --> 00:29:34,920
C'è un modo, cerchiamo di stipulare oggi,
che potrebbero digitare non solo ciao

632
00:29:34,920 --> 00:29:36,711
il loro nome o il mondo,
potevano essenzialmente

633
00:29:36,711 --> 00:29:39,570
passare in codice, zero e
quelli, che il computer

634
00:29:39,570 --> 00:29:43,450
errori sia per il codice e un indirizzo.

635
00:29:43,450 --> 00:29:48,950
Così anche se un po astrattamente, se il
utente digita abbastanza codice contraddittorio

636
00:29:48,950 --> 00:29:52,330
che saremo generalizzare qui
A. A è attacco o avversari.

637
00:29:52,330 --> 00:29:53,140
Quindi, solo cose cattive.

638
00:29:53,140 --> 00:29:55,306
Non ci interessa circa il
numeri o gli zeri o quelli

639
00:29:55,306 --> 00:29:59,470
oggi, in modo tale che si finisce per
sovrascrivendo quella sezione rosso,

640
00:29:59,470 --> 00:30:01,580
notare che sequenza di byte.

641
00:30:01,580 --> 00:30:05,020
O 835 C zero otto a zero.

642
00:30:05,020 --> 00:30:08,960
E ora come l'articolo di Wikipedia qui
ha proposto, se ora effettivamente iniziare

643
00:30:08,960 --> 00:30:12,460
etichettatura i byte nel computer di
la memoria, ciò che l'articolo Wikipedia

644
00:30:12,460 --> 00:30:19,060
proponente è che, quello che se l'indirizzo
di quel byte alto a sinistra è 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> In altre parole, se il cattivo è
abbastanza intelligente con il suo codice

646
00:30:22,200 --> 00:30:26,650
per mettere in realtà una serie qui che
corrisponde all'indirizzo del codice

647
00:30:26,650 --> 00:30:29,180
lui o lei iniettato
nel computer,

648
00:30:29,180 --> 00:30:31,050
può ingannare il computer
a fare qualsiasi cosa.

649
00:30:31,050 --> 00:30:34,140
Rimozione dei file, e-mail
cose, annusando il traffico,

650
00:30:34,140 --> 00:30:36,710
letteralmente qualsiasi cosa potrebbe essere
iniettato nel computer.

651
00:30:36,710 --> 00:30:39,220
E così un buffer overflow
attacco al suo interno

652
00:30:39,220 --> 00:30:43,530
è solo uno stupido, stupido
prevalente di un array

653
00:30:43,530 --> 00:30:45,840
non ha avuto i suoi confini controllati.

654
00:30:45,840 --> 00:30:48,850
E questo è ciò che è super pericoloso
e allo stesso tempo super potente

655
00:30:48,850 --> 00:30:52,560
in C è che abbiamo davvero
l'accesso a qualsiasi punto della memoria.

656
00:30:52,560 --> 00:30:55,320
Sta a noi, i programmatori,
che scrivono il codice originale

657
00:30:55,320 --> 00:30:59,330
per controllare la lunghezza di qualsiasi maledettamente
array che stiamo manipolando.

658
00:30:59,330 --> 00:31:00,750
Quindi, per essere chiaro, qual è la soluzione?

659
00:31:00,750 --> 00:31:03,190
Se il rollback a questo
codice, non dovrei solo

660
00:31:03,190 --> 00:31:08,000
modificare la lunghezza della barra, cosa
cosa dovrei controllare?

661
00:31:08,000 --> 00:31:10,620
Che altro dovrei fare per
prevenire questo attacco del tutto?

662
00:31:10,620 --> 00:31:14,110
Io non voglio solo dire alla cieca
che è necessario copiare tanti byte

663
00:31:14,110 --> 00:31:16,140
come è la lunghezza della barra.

664
00:31:16,140 --> 00:31:18,910
Voglio dire, come copiare
molti byte, come sono in bar

665
00:31:18,910 --> 00:31:24,090
fino al allocato
memoria, o 12 al massimo.

666
00:31:24,090 --> 00:31:27,450
Quindi ho bisogno di un qualche tipo di condizione if
che fa controllare la lunghezza della barra,

667
00:31:27,450 --> 00:31:32,800
ma se supera 12, abbiamo il codice solo difficile
12 come la massima distanza possibile.

668
00:31:32,800 --> 00:31:35,910
Altrimenti il ​​cosiddetto tampone
attacco overflow può succedere.

669
00:31:35,910 --> 00:31:38,451
Nella parte inferiore di dette slitte,
se siete curiosi di saperne di più

670
00:31:38,451 --> 00:31:41,200
è l'articolo originale reale
se volete dare un'occhiata.

671
00:31:41,200 --> 00:31:44,550
>> Ma ora, tra i prezzi
pagati qui era inefficienze.

672
00:31:44,550 --> 00:31:46,680
Così che era un rapido
basso livello di sguardo a ciò che

673
00:31:46,680 --> 00:31:49,709
problemi possono sorgere ora che abbiamo
avere accesso alla memoria del computer.

674
00:31:49,709 --> 00:31:51,750
Ma un altro problema che abbiamo
già inciampato il Lunedi

675
00:31:51,750 --> 00:31:53,800
era solo l'inefficienza
di una lista collegata.

676
00:31:53,800 --> 00:31:56,019
Siamo tornati al tempo lineare.

677
00:31:56,019 --> 00:31:57,560
Non abbiamo più un array contiguo.

678
00:31:57,560 --> 00:31:58,980
Non abbiamo accesso casuale.

679
00:31:58,980 --> 00:32:00,710
Non possiamo usare la notazione parentesi quadra.

680
00:32:00,710 --> 00:32:04,590
Abbiamo letteralmente dobbiamo usare un ciclo while
come quella che ho scritto poco fa.

681
00:32:04,590 --> 00:32:09,740
Ma il Lunedi, abbiamo dichiarato di essere in grado
strisciare indietro nel regno di efficienza

682
00:32:09,740 --> 00:32:13,040
raggiungimento di qualcosa che è
logaritmica forse, o meglio ancora,

683
00:32:13,040 --> 00:32:16,120
forse anche qualcosa che è
cosiddetto tempo costante.

684
00:32:16,120 --> 00:32:19,840
Quindi, come possiamo farlo usando questi nuovi
strumenti, questi indirizzi, i puntatori,

685
00:32:19,840 --> 00:32:22,210
e filettatura cose della nostra?

686
00:32:22,210 --> 00:32:23,960
Bene, supponiamo che
qui, si tratta di un gruppo

687
00:32:23,960 --> 00:32:27,170
di numeri che vogliamo conservare in un
struttura di dati e di ricerca in modo efficiente.

688
00:32:27,170 --> 00:32:30,960
Possiamo assolutamente tornare indietro a settimana
due, gettare queste in una matrice,

689
00:32:30,960 --> 00:32:33,150
e la ricerca utilizzando la ricerca binaria.

690
00:32:33,150 --> 00:32:34,040
Divide et impera.

691
00:32:34,040 --> 00:32:37,720
E infatti hai scritto
ricerca binaria in PSET3,

692
00:32:37,720 --> 00:32:40,100
dove è stato implementato il programma di scoperta.

693
00:32:40,100 --> 00:32:40,890
Ma si sa che cosa.

694
00:32:40,890 --> 00:32:45,060
C'è una specie di più
modo intelligente di fare questo.

695
00:32:45,060 --> 00:32:47,390
E 'un po' di più
forse sofisticato e

696
00:32:47,390 --> 00:32:50,830
ci permette di vedere perché binario
ricerca è molto più veloce.

697
00:32:50,830 --> 00:32:52,980
In primo luogo, introduciamo
il concetto di un albero.

698
00:32:52,980 --> 00:32:54,730
Che anche se in
alberi realtà tipo di

699
00:32:54,730 --> 00:32:57,730
crescere come questo, nel mondo di calcolatore
la scienza che tipo di crescere verso il basso

700
00:32:57,730 --> 00:33:00,830
come un albero di famiglia, dove si ha
i vostri nonni o bisnonni

701
00:33:00,830 --> 00:33:04,580
o roba del genere nella parte superiore, il patriarca e
la matriarca della famiglia, solo un

702
00:33:04,580 --> 00:33:07,930
cosiddetta radice, nodo, sotto
quali sono i suoi figli,

703
00:33:07,930 --> 00:33:11,442
sotto del quale sono i suoi figli, o
suoi discendenti più in generale.

704
00:33:11,442 --> 00:33:13,400
E chiunque appesi fuori
il fondo della famiglia

705
00:33:13,400 --> 00:33:16,070
albero, oltre ad essere la
più giovane della famiglia,

706
00:33:16,070 --> 00:33:19,520
può anche essere solo genericamente
chiamato le foglie dell'albero.

707
00:33:19,520 --> 00:33:21,800
>> Quindi questo è solo un mucchio
di parole e definizioni

708
00:33:21,800 --> 00:33:25,790
per qualcosa chiamato un albero di computer
scienza, proprio come un albero genealogico.

709
00:33:25,790 --> 00:33:28,770
Ma c'è incarnazioni amatore
di alberi, uno dei quali

710
00:33:28,770 --> 00:33:30,780
viene chiamato un albero binario di ricerca.

711
00:33:30,780 --> 00:33:34,380
E si può sorta di presa in giro
a parte ciò che questa cosa fa.

712
00:33:34,380 --> 00:33:37,180
Beh, è ​​binario in che senso?

713
00:33:37,180 --> 00:33:41,455
Da dove viene il binario viene da qui?

714
00:33:41,455 --> 00:33:41,955
Scusate?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Non è tanto una o.

717
00:33:47,210 --> 00:33:52,000
E 'più che ciascuno dei nodi non ha
più di due figli, come vediamo qui.

718
00:33:52,000 --> 00:33:54,990
In generale, un tree-- e
i vostri genitori e nonni

719
00:33:54,990 --> 00:33:57,640
può avere come molti ragazzi o
nipotini come realmente vogliono,

720
00:33:57,640 --> 00:34:00,820
e così per esempio non ci abbiamo tre
bambini fuori quel nodo mano destra,

721
00:34:00,820 --> 00:34:05,480
ma in un albero binario, un nodo ha
zero, uno o due bambini al massimo.

722
00:34:05,480 --> 00:34:08,496
E questa è una bella proprietà,
perché se è ricoperto da due,

723
00:34:08,496 --> 00:34:10,620
stiamo andando a essere in grado di
ottenere un po 'logaritmo in base due

724
00:34:10,620 --> 00:34:11,975
azione succedendo qui alla fine.

725
00:34:11,975 --> 00:34:13,350
Così abbiamo qualcosa logaritmica.

726
00:34:13,350 --> 00:34:14,558
Ma più su che in un momento.

727
00:34:14,558 --> 00:34:19,810
Cerca albero significa che i numeri sono
disposto in modo tale che il bambino sinistra di

728
00:34:19,810 --> 00:34:22,429
valore è maggiore rispetto alla radice.

729
00:34:22,429 --> 00:34:26,010
E suo figlio destro è
più grande della radice.

730
00:34:26,010 --> 00:34:29,290
In altre parole, se si prende una qualsiasi delle
nodi, i cerchi in questa immagine,

731
00:34:29,290 --> 00:34:31,840
e guarda la sua sinistra
bambino e suo figlio destro,

732
00:34:31,840 --> 00:34:34,739
il primo dovrebbe essere inferiore,
il secondo dovrebbe essere superiore.

733
00:34:34,739 --> 00:34:36,159
Così la sanità mentale di controllo 55.

734
00:34:36,159 --> 00:34:37,780
E 'figlio rimane è 33.

735
00:34:37,780 --> 00:34:38,620
E 'meno.

736
00:34:38,620 --> 00:34:40,929
55, suo figlio destro è 77.

737
00:34:40,929 --> 00:34:41,783
E 'più grande di.

738
00:34:41,783 --> 00:34:43,199
E questa è una definizione ricorsiva.

739
00:34:43,199 --> 00:34:46,480
Potremmo controllare ogni uno di quelli
nodi e lo stesso schema terrebbe.

740
00:34:46,480 --> 00:34:49,389
>> Così che cosa è bello in una
albero binario di ricerca, è

741
00:34:49,389 --> 00:34:52,204
che uno, possiamo attuarlo
con una struttura, proprio come questo.

742
00:34:52,204 --> 00:34:54,620
E anche se ci stiamo buttando
un sacco di strutture al vostro,

743
00:34:54,620 --> 00:34:56,560
sono un po '
intuitivo ora si spera.

744
00:34:56,560 --> 00:35:00,570
La sintassi è ancora arcana di sicuro,
ma il contenuto di un nodo in questo

745
00:35:00,570 --> 00:35:02,786
context-- e continuiamo
utilizzando il nodo parola,

746
00:35:02,786 --> 00:35:04,910
che si tratti di un rettangolo
sullo schermo o un cerchio,

747
00:35:04,910 --> 00:35:08,970
è solo un po 'di contenitore generico,
in questo caso di un albero, come quello

748
00:35:08,970 --> 00:35:11,780
abbiamo visto, abbiamo bisogno di un intero
in ciascuno dei nodi

749
00:35:11,780 --> 00:35:15,460
e poi ho bisogno di due puntatori di puntamento
al figlio sinistro e il figlio destro,

750
00:35:15,460 --> 00:35:16,590
rispettivamente.

751
00:35:16,590 --> 00:35:20,730
Ecco come potremmo
implementare che in una struttura.

752
00:35:20,730 --> 00:35:22,315
E come potrei implementarlo in codice?

753
00:35:22,315 --> 00:35:26,730
Bene, facciamo un rapido
un'occhiata a questo piccolo esempio.

754
00:35:26,730 --> 00:35:29,820
Non è funzionale, ma ho
copiati e incollati quella struttura.

755
00:35:29,820 --> 00:35:33,510
E se la mia funzione per un binario
Ricerca albero si chiama ricerca,

756
00:35:33,510 --> 00:35:36,980
e questo richiede due argomenti,
un numero intero N e un puntatore

757
00:35:36,980 --> 00:35:41,400
a un nodo, quindi un puntatore alla struttura
o un puntatore alla radice di un albero,

758
00:35:41,400 --> 00:35:43,482
come faccio ad andare sulla ricerca di N?

759
00:35:43,482 --> 00:35:45,440
Beh, in primo luogo, perché io sono
si occupano di puntatori,

760
00:35:45,440 --> 00:35:46,750
Ho intenzione di fare un controllo di integrità.

761
00:35:46,750 --> 00:35:54,279
Se eguali albero uguale a zero, è N
in questo albero o meno in questo albero?

762
00:35:54,279 --> 00:35:55,070
Non può essere, giusto?

763
00:35:55,070 --> 00:35:56,870
Se io sono passato nulla,
non c'è niente.

764
00:35:56,870 --> 00:35:59,230
Potrei anche solo
ciecamente dire return false.

765
00:35:59,230 --> 00:36:04,050
Se mi dai niente, io di certo non posso
trovare qualsiasi numero N. Quindi, che cosa potrebbe io

766
00:36:04,050 --> 00:36:04,750
controllare ora?

767
00:36:04,750 --> 00:36:12,830
Io vado a dire ben altro se N è
meno di ciò che è al nodo della struttura

768
00:36:12,830 --> 00:36:16,300
che ho consegnato valore N.

769
00:36:16,300 --> 00:36:20,270
In altre parole, se il numero sono
cercando, N, è inferiore al nodo

770
00:36:20,270 --> 00:36:21,340
che sto guardando.

771
00:36:21,340 --> 00:36:23,190
E il nodo sto cercando
a è chiamato albero,

772
00:36:23,190 --> 00:36:26,370
e richiamare dall'esempio precedente
per ottenere il valore di un puntatore,

773
00:36:26,370 --> 00:36:28,310
Io uso la notazione freccia.

774
00:36:28,310 --> 00:36:35,960
Quindi, se N è inferiore a albero freccia
N, voglio andare concettualmente sinistra.

775
00:36:35,960 --> 00:36:38,590
Come esprimo searching lasciato?

776
00:36:38,590 --> 00:36:41,560
Per essere chiari, se questa è
il quadro in questione,

777
00:36:41,560 --> 00:36:44,612
e sono stato passato che più in alto
freccia che è rivolta verso il basso.

778
00:36:44,612 --> 00:36:45,570
Questo è il mio puntatore albero.

779
00:36:45,570 --> 00:36:48,060
Sto indicando la radice dell'albero.

780
00:36:48,060 --> 00:36:52,100
E sto cercando per esempio, per
il numero 44, arbitrariamente.

781
00:36:52,100 --> 00:36:55,300
È 44 inferiore o
maggiore di 55 ovviamente?

782
00:36:55,300 --> 00:36:56,360
Quindi è inferiore.

783
00:36:56,360 --> 00:36:58,760
E così questo se la condizione si applica.

784
00:36:58,760 --> 00:37:03,981
Quindi concettualmente, quello che voglio
Ricerca prossimo se sto cercando 44?

785
00:37:03,981 --> 00:37:04,480
Sì?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Esattamente, voglio
cercare il figlio sinistro,

788
00:37:11,100 --> 00:37:12,789
o il sub-albero a sinistra dell'immagine.

789
00:37:12,789 --> 00:37:14,830
E infatti, lasciatemi attraverso
l'immagine qui

790
00:37:14,830 --> 00:37:17,770
solo per un momento, dal momento che
Non riesco a grattare questo fuori.

791
00:37:17,770 --> 00:37:21,150
Se inizio qui a 55, e
So che il valore 44

792
00:37:21,150 --> 00:37:23,180
Io sto cercando è a
la sinistra, è una specie

793
00:37:23,180 --> 00:37:26,010
'come strappare la rubrica telefonica in
metà o strappare l'albero a metà.

794
00:37:26,010 --> 00:37:29,660
Non ho più a cuore
questa intera metà dell'albero.

795
00:37:29,660 --> 00:37:33,270
Eppure, stranamente in termini di
Struttura, questa cosa qui che

796
00:37:33,270 --> 00:37:36,682
inizia con 33, che si
è un albero binario di ricerca.

797
00:37:36,682 --> 00:37:39,890
Ho detto la parola ricorsiva prima perché
anzi questa è una struttura di dati che

798
00:37:39,890 --> 00:37:41,707
per definizione ricorsiva.

799
00:37:41,707 --> 00:37:44,540
Si potrebbe avere un albero che è questo
grande, ma ognuno dei suoi figli

800
00:37:44,540 --> 00:37:46,870
rappresenta un albero appena un po 'più piccolo.

801
00:37:46,870 --> 00:37:50,910
Invece di essere il nonno
o la nonna, ora è solo la mamma

802
00:37:50,910 --> 00:37:54,300
or-- Non posso non say-- mamma
o papà, che sarebbe strano.

803
00:37:54,300 --> 00:37:59,000
Invece i due bambini lì
sarebbe come fratello e sorella.

804
00:37:59,000 --> 00:38:01,120
Una nuova generazione dell'albero genealogico.

805
00:38:01,120 --> 00:38:02,900
Ma strutturalmente, è la stessa idea.

806
00:38:02,900 --> 00:38:06,790
E si scopre Ho una funzione
con la quale posso cercare una ricerca binaria

807
00:38:06,790 --> 00:38:07,290
albero.

808
00:38:07,290 --> 00:38:08,680
Si chiama ricerca.

809
00:38:08,680 --> 00:38:17,870
Cerco N in albero freccia sinistra
altrimenti se N è maggiore del valore

810
00:38:17,870 --> 00:38:18,870
che sono attualmente a.

811
00:38:18,870 --> 00:38:20,800
55 nella storia un momento fa.

812
00:38:20,800 --> 00:38:23,780
Ho una funzione chiamata
di ricerca che posso solo

813
00:38:23,780 --> 00:38:29,660
N passare questo e ricorsivamente la ricerca
il sub-albero e proprio ritorno

814
00:38:29,660 --> 00:38:30,620
qualunque cosa quella risposta.

815
00:38:30,620 --> 00:38:33,530
Il resto che ho avuto qualche caso base finale qui.

816
00:38:33,530 --> 00:38:35,310
>> Qual è l'ultimo caso?

817
00:38:35,310 --> 00:38:36,570
Albero o è nullo.

818
00:38:36,570 --> 00:38:39,980
Il valore che sto cercando è uno
inferiore o superiore a quella

819
00:38:39,980 --> 00:38:42,610
o uguale ad esso.

820
00:38:42,610 --> 00:38:44,750
E potrei dire uguale
uguale, ma è logicamente

821
00:38:44,750 --> 00:38:46,500
pari a poco dire altro qui.

822
00:38:46,500 --> 00:38:49,150
Tanto è vero come trovo qualcosa.

823
00:38:49,150 --> 00:38:51,710
Quindi spero che questo è un
ancor esempio più convincente

824
00:38:51,710 --> 00:38:54,900
che la funzione di Sigma stupido
abbiamo fatto qualche lezione indietro,

825
00:38:54,900 --> 00:38:58,360
dove era altrettanto facile da utilizzare un ciclo
a contare tutti i numeri da uno

826
00:38:58,360 --> 00:39:02,390
a N. Qui con una struttura di dati
che è di per sé in modo ricorsivo

827
00:39:02,390 --> 00:39:07,050
definito e ricorsivamente attratti, ora siamo
hanno la capacità di esprimere noi stessi

828
00:39:07,050 --> 00:39:09,780
nel codice che si è ricorsivo.

829
00:39:09,780 --> 00:39:12,580
Quindi questo è esattamente lo stesso codice qui.

830
00:39:12,580 --> 00:39:14,400
>> Allora, cosa altro possiamo risolvere i problemi?

831
00:39:14,400 --> 00:39:18,160
Così un rapido passo dal
alberi per un attimo.

832
00:39:18,160 --> 00:39:20,130
Qui è, diciamo, la bandiera tedesca.

833
00:39:20,130 --> 00:39:22,020
E c'è chiaramente una
modello di questo flag.

834
00:39:22,020 --> 00:39:23,811
E c'è un sacco di
bandiere del mondo che

835
00:39:23,811 --> 00:39:27,560
sono semplice come questo in termini
dei loro colori e modelli.

836
00:39:27,560 --> 00:39:31,930
Ma supponiamo che questo è memorizzato come
.GIF, O una JPEG o bitmap o un ping,

837
00:39:31,930 --> 00:39:34,240
qualsiasi formato di file grafici
con il quale si ha familiarità,

838
00:39:34,240 --> 00:39:36,460
alcuni dei quali siamo
giocare con in PSET4.

839
00:39:36,460 --> 00:39:41,550
Questo non sembra utile per memorizzare
pixel nero, pixel nero, pixel nero,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, tutta una serie di
pixel neri per la prima linea di scansione,

841
00:39:44,790 --> 00:39:47,430
o riga, poi tutta una serie di
lo stesso, quindi un sacco

842
00:39:47,430 --> 00:39:49,530
della stessa, e quindi un
mucchio di pixel rossi,

843
00:39:49,530 --> 00:39:53,020
pixel rossi, pixel rossi, poi un intero
mazzo di giallo pixel, giallo, giusto?

844
00:39:53,020 --> 00:39:55,050
>> C'è tale inefficienza qui.

845
00:39:55,050 --> 00:39:59,040
Come sarebbe intuitivamente
comprimere la bandiera tedesca

846
00:39:59,040 --> 00:40:01,320
se la sua attuazione come un file?

847
00:40:01,320 --> 00:40:04,940
Come quello che informazioni possiamo non
fastidio la memorizzazione su disco in ordine

848
00:40:04,940 --> 00:40:08,040
per diminuire la nostra dimensione del file da come
un megabyte di un kilobyte, qualcosa

849
00:40:08,040 --> 00:40:09,430
più piccolo?

850
00:40:09,430 --> 00:40:13,130
Dove sta la ridondanza
qui per essere chiari?

851
00:40:13,130 --> 00:40:13,880
Che cosa si potrebbe fare?

852
00:40:13,880 --> 00:40:14,380
Sì?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Esattamente.

855
00:40:21,970 --> 00:40:24,550
Perché non ricordare piuttosto che
il colore di ogni pixel maledettamente

856
00:40:24,550 --> 00:40:28,200
proprio come si sta facendo in PSET4
con il formato di file bitmap,

857
00:40:28,200 --> 00:40:32,060
perché non solo rappresenti la
colonna più a sinistra di pixel, ad esempio

858
00:40:32,060 --> 00:40:35,370
un mucchio di pixel neri, un gruppo
di rosso, e un po 'di colore giallo,

859
00:40:35,370 --> 00:40:39,210
e poi basta qualche modo codificare il
idea di ripetere questo 100 volte

860
00:40:39,210 --> 00:40:41,020
o ripetere questo 1.000 volte?

861
00:40:41,020 --> 00:40:43,430
Dove 100 o 1000 è
solo un numero intero, in modo da

862
00:40:43,430 --> 00:40:47,290
può uscire solo con un numero unico
invece di centinaia o migliaia

863
00:40:47,290 --> 00:40:48,270
pixel di ulteriori.

864
00:40:48,270 --> 00:40:50,990
E in effetti, è così che
potrebbe comprimere la bandiera tedesca.

865
00:40:50,990 --> 00:40:51,490
E

866
00:40:51,490 --> 00:40:53,470
Ora, per quanto riguarda la bandiera francese?

867
00:40:53,470 --> 00:40:58,930
E un po sorta di
esercizio mentale, la cui bandiera

868
00:40:58,930 --> 00:41:01,040
può essere compresso più su disco?

869
00:41:01,040 --> 00:41:05,720
La bandiera tedesca o francese
Bandiera, se prendiamo questo approccio?

870
00:41:05,720 --> 00:41:08,490
La bandiera tedesca, perché non c'è
ridondanza più orizzontale.

871
00:41:08,490 --> 00:41:12,190
E in base alla progettazione, molti file grafico
Formati effettivamente funzionano come linee di scansione

872
00:41:12,190 --> 00:41:12,830
orizzontalmente.

873
00:41:12,830 --> 00:41:14,674
Potevano lavorare
verticalmente, solo l'umanità

874
00:41:14,674 --> 00:41:17,090
anni fa, che deciso faremo
generalmente pensare alle cose fila

875
00:41:17,090 --> 00:41:18,880
per riga invece di colonna per colonna.

876
00:41:18,880 --> 00:41:20,820
Quindi, in effetti, se tu fossi
a guardare il file

877
00:41:20,820 --> 00:41:24,670
dimensioni di una bandiera tedesca e una francese
bandiera, purché la risoluzione è

878
00:41:24,670 --> 00:41:27,530
la stessa, la stessa larghezza
e altezza, questo

879
00:41:27,530 --> 00:41:31,580
qui sta per essere più grande, perché si
devono ripetersi tre volte.

880
00:41:31,580 --> 00:41:35,570
È necessario specificare blu, ripetere
te, bianco, ripetere te stesso, rosso,

881
00:41:35,570 --> 00:41:36,740
ripetersi.

882
00:41:36,740 --> 00:41:39,000
Non si può semplicemente andare tutti
la strada verso destra.

883
00:41:39,000 --> 00:41:41,200
E per inciso, per rendere
cancellare la compressione

884
00:41:41,200 --> 00:41:43,910
è ovunque, se questi sono
quattro fotogrammi da un video-- te

885
00:41:43,910 --> 00:41:45,890
potrebbe ricordare che un film
o il video è in genere

886
00:41:45,890 --> 00:41:47,286
come 29 o 30 fotogrammi al secondo.

887
00:41:47,286 --> 00:41:50,410
E 'come un piccolo flip book dove
basta vedere l'immagine, immagine, immagine, immagine,

888
00:41:50,410 --> 00:41:54,410
immagine appena super veloce così sembra
gli attori sullo schermo sono in movimento.

889
00:41:54,410 --> 00:41:57,130
Ecco un calabrone su
cima di un mazzo di fiori.

890
00:41:57,130 --> 00:41:59,790
E anche se potrebbe essere una sorta di
difficile capire a prima vista,

891
00:41:59,790 --> 00:42:04,020
l'unica cosa che si muove in
questo film è l'ape.

892
00:42:04,020 --> 00:42:06,880
>> Che cosa è muto sulla memorizzazione
video non compresso?

893
00:42:06,880 --> 00:42:11,420
E 'una specie di uno spreco per memorizzare il video
come quattro immagini quasi identiche che

894
00:42:11,420 --> 00:42:13,670
differiscono solo in quanto se l'ape è.

895
00:42:13,670 --> 00:42:16,280
Si può buttare via la maggior parte
di tali informazioni

896
00:42:16,280 --> 00:42:20,190
e solo ricordare, per esempio,
il primo fotogramma e l'ultimo fotogramma,

897
00:42:20,190 --> 00:42:22,180
fotogrammi chiave se hai
mai sentito la parola,

898
00:42:22,180 --> 00:42:24,337
e solo memorizzare nella
mezzo dove l'ape è.

899
00:42:24,337 --> 00:42:26,170
E non c'è bisogno di
memorizzare tutti i rosa,

900
00:42:26,170 --> 00:42:28,330
e il blu, e il
valori del verde come bene.

901
00:42:28,330 --> 00:42:31,200
Quindi questo è quello di dire soltanto che
compressione è ovunque.

902
00:42:31,200 --> 00:42:34,900
E 'una tecnica che usiamo spesso
o dare per scontato in questi giorni.

903
00:42:34,900 --> 00:42:38,750
>> Ma come si fa a comprimere il testo?

904
00:42:38,750 --> 00:42:40,450
Come si fa a comprimere il testo?

905
00:42:40,450 --> 00:42:45,410
Ebbene, ciascuno dei caratteri
ASCII è un byte o otto bit.

906
00:42:45,410 --> 00:42:47,360
E questo è tipo di stupido, giusto?

907
00:42:47,360 --> 00:42:51,160
Perché probabilmente si digita A
ed E e I e O e U molto

908
00:42:51,160 --> 00:42:55,270
il più delle volte come W o Q o Z,
a seconda della lingua in cui

909
00:42:55,270 --> 00:42:56,610
stai scrivendo certamente.

910
00:42:56,610 --> 00:42:59,600
E allora perché stiamo usando
otto bit per ogni lettera,

911
00:42:59,600 --> 00:43:02,040
compresi i meno
lettere popolare, giusto?

912
00:43:02,040 --> 00:43:05,300
Perché non utilizzare un minor numero di bit per
le lettere super-popolari,

913
00:43:05,300 --> 00:43:07,760
E come, le cose che si indovinare
prima in Ruota della Fortuna,

914
00:43:07,760 --> 00:43:10,450
e utilizzare più bit per
le lettere meno popolari?

915
00:43:10,450 --> 00:43:10,950
Perché?

916
00:43:10,950 --> 00:43:13,130
Perché stiamo solo andando a
usarli con minore frequenza.

917
00:43:13,130 --> 00:43:15,838
>> Beh, si scopre che ci sono
stati tentativi di fare questo.

918
00:43:15,838 --> 00:43:18,630
E se vi ricordate dal grado
scuola o scuola superiore, il codice Morse.

919
00:43:18,630 --> 00:43:20,400
Codice Morse ha punti
e trattini che possono essere

920
00:43:20,400 --> 00:43:24,270
trasmessa lungo un filo come
suoni o segnali di qualche tipo.

921
00:43:24,270 --> 00:43:25,930
Ma il codice Morse è un super pulito.

922
00:43:25,930 --> 00:43:29,010
E 'una specie di un sistema binario a
di avere punti o trattini.

923
00:43:29,010 --> 00:43:30,977
Ma se si vede, per esempio, due punti.

924
00:43:30,977 --> 00:43:33,810
Oppure, se si ripensa al gestore
che va come bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
beep, colpendo un po 'innesco
che trasmette un segnale,

926
00:43:36,760 --> 00:43:40,360
se si, il destinatario riceve due
punti, quale messaggio hanno ricevuto?

927
00:43:40,360 --> 00:43:43,490
Del tutto arbitraria.

928
00:43:43,490 --> 00:43:44,450
>> IO?

929
00:43:44,450 --> 00:43:45,060
IO?

930
00:43:45,060 --> 00:43:47,500
O quello che about-- o io?

931
00:43:47,500 --> 00:43:49,570
Forse era solo due a destra di E?

932
00:43:49,570 --> 00:43:52,480
Quindi c'è questo problema
di decodificabilità con Morse

933
00:43:52,480 --> 00:43:54,890
codice, per cui a meno che il
persona che sta inviando il messaggio

934
00:43:54,890 --> 00:43:59,510
in realtà le pause in modo da poter ordinare di
vedere o sentire i vuoti tra lettere,

935
00:43:59,510 --> 00:44:02,990
non è sufficiente solo
inviare un flusso di zero e uno,

936
00:44:02,990 --> 00:44:05,610
o punti e linee,
perché non c'è ambiguità.

937
00:44:05,610 --> 00:44:08,640
E è un singolo punto, quindi se si
vedi due punti o sentire due punti,

938
00:44:08,640 --> 00:44:11,254
forse è il due di E o forse è uno I.

939
00:44:11,254 --> 00:44:13,670
Quindi abbiamo bisogno di un sistema che è un
poco più intelligente di quello.

940
00:44:13,670 --> 00:44:16,851
Così un uomo di nome Huffman anni
fa si avvicinò con esattamente questo.

941
00:44:16,851 --> 00:44:18,600
Quindi stiamo solo andando
di prendere una rapida occhiata

942
00:44:18,600 --> 00:44:20,114
il modo in cui gli alberi sono attinente a questo.

943
00:44:20,114 --> 00:44:22,530
Supponiamo che questo è un
messaggio stupido che si desidera inviare,

944
00:44:22,530 --> 00:44:26,342
composta solo A, B, C di D's ed E di,
ma c'è un sacco di ridondanza qui.

945
00:44:26,342 --> 00:44:27,550
Non è destinata ad essere inglese.

946
00:44:27,550 --> 00:44:28,341
Non è criptato.

947
00:44:28,341 --> 00:44:30,540
E 'solo un messaggio stupido
con un sacco di ripetizioni.

948
00:44:30,540 --> 00:44:34,010
Quindi, se effettivamente contano tutte le
A di B, di C di D's, ed E di, ecco

949
00:44:34,010 --> 00:44:34,890
la frequenza.

950
00:44:34,890 --> 00:44:37,800
20% delle lettere sono
Un di, il 45% delle lettere

951
00:44:37,800 --> 00:44:39,660
E sono di, e altri tre frequenze.

952
00:44:39,660 --> 00:44:41,960
Abbiamo contato lassù manualmente
e appena fatto la matematica.

953
00:44:41,960 --> 00:44:44,579
>> Così si scopre che
Huffman, qualche tempo fa,

954
00:44:44,579 --> 00:44:46,620
resi conto che, si sa
quello che, se comincio edificio

955
00:44:46,620 --> 00:44:51,172
un albero, o foresta di alberi, se si vuole,
come segue, posso effettuare le seguenti operazioni.

956
00:44:51,172 --> 00:44:53,880
Io vado a dare un nodo per ogni
delle lettere che mi preoccupo

957
00:44:53,880 --> 00:44:55,530
e ho intenzione di archiviare
all'interno di tale nodo

958
00:44:55,530 --> 00:44:58,610
le frequenze come virgola mobile
valore, oppure si potrebbe usare un N, troppo,

959
00:44:58,610 --> 00:45:00,210
ma ci limiteremo a utilizzare un galleggiante qui.

960
00:45:00,210 --> 00:45:03,100
E l'algoritmo che
ha proposto è che si

961
00:45:03,100 --> 00:45:07,210
prendere questa foresta di singolo nodo
alberi, alberi così super corti,

962
00:45:07,210 --> 00:45:11,920
e si inizia collegandoli con
nuovi gruppi, nuovi genitori, se si vuole.

963
00:45:11,920 --> 00:45:16,150
E si esegue questa operazione scegliendo il
due frequenze più piccoli alla volta.

964
00:45:16,150 --> 00:45:18,110
Così ho preso il 10% e il 10%.

965
00:45:18,110 --> 00:45:19,090
Creo un nuovo nodo.

966
00:45:19,090 --> 00:45:20,910
E io chiamo il nuovo nodo del 20%.

967
00:45:20,910 --> 00:45:22,750
>> Quali sono i due nodi combino prossimo?

968
00:45:22,750 --> 00:45:23,810
È un po 'ambiguo.

969
00:45:23,810 --> 00:45:26,643
Quindi ci sono alcuni casi angolo a
prendere in considerazione, ma per mantenere le cose abbastanza,

970
00:45:26,643 --> 00:45:29,300
Ho intenzione di scegliere il 20% -
Ora ignoro i bambini.

971
00:45:29,300 --> 00:45:33,640
Ho intenzione di scegliere il 20% e
15% e disegnare due nuovi bordi.

972
00:45:33,640 --> 00:45:35,624
E ora che due nodi
faccio logicamente combinare?

973
00:45:35,624 --> 00:45:38,540
Ignorare tutti i bambini, tutti i
nipoti, basta guardare alle radici

974
00:45:38,540 --> 00:45:39,070
adesso.

975
00:45:39,070 --> 00:45:42,220
Quali sono i due nodi si lego insieme?

976
00:45:42,220 --> 00:45:44,530
Punto due e 0,35.

977
00:45:44,530 --> 00:45:45,890
Così mi permetta di disegnare due nuovi bordi.

978
00:45:45,890 --> 00:45:47,570
E poi ho solo uno a sinistra.

979
00:45:47,570 --> 00:45:48,650
Quindi, ecco un albero.

980
00:45:48,650 --> 00:45:51,160
Ed è stato disegnato deliberatamente
a guardare tipo di bella,

981
00:45:51,160 --> 00:45:55,870
a meno di notare che i bordi hanno
anche definita zero e uno.

982
00:45:55,870 --> 00:45:59,510
Così tutti i bordi di sinistra sono zero
arbitrariamente, ma in modo coerente.

983
00:45:59,510 --> 00:46:01,170
Tutti i bordi a destra sono quelli.

984
00:46:01,170 --> 00:46:05,070
>> E così quello che Hoffman proposto è,
se si vuole rappresentare una B,

985
00:46:05,070 --> 00:46:10,080
piuttosto che rappresentare il numero 66 come
un Ascii, che è di otto bit interi,

986
00:46:10,080 --> 00:46:13,360
si sa che cosa, appena negozio
il modello zero, zero, zero,

987
00:46:13,360 --> 00:46:17,030
zero, perché questo è il percorso
dal mio albero, l'albero del signor Huffman,

988
00:46:17,030 --> 00:46:18,600
alla foglia dalla radice.

989
00:46:18,600 --> 00:46:20,970
Se si desidera memorizzare un
E, al contrario, non fare

990
00:46:20,970 --> 00:46:26,290
invia otto bit che rappresentano un E.
Invece, inviare quale schema di bit?

991
00:46:26,290 --> 00:46:26,890
Uno.

992
00:46:26,890 --> 00:46:30,410
E ciò che è bello di questo è
che E è la lettera più popolare,

993
00:46:30,410 --> 00:46:32,340
e si sta utilizzando la
codice breve per esso.

994
00:46:32,340 --> 00:46:34,090
Il prossimo più popolare
lettera sembra

995
00:46:34,090 --> 00:46:37,380
Era A. E così il numero di bit
ti ha proposto utilizzando per questo?

996
00:46:37,380 --> 00:46:38,270
Zero, uno.

997
00:46:38,270 --> 00:46:41,060
>> E poiché è implementato
come questo albero, per ora

998
00:46:41,060 --> 00:46:43,350
mi permetta di stipula le c'e '
nessuna ambiguità come in Morse

999
00:46:43,350 --> 00:46:46,090
codice, perché tutti i
lettere che ti interessano

1000
00:46:46,090 --> 00:46:48,780
sono alla fine di questi bordi.

1001
00:46:48,780 --> 00:46:50,580
Ecco, questo è solo uno
applicazione di un albero.

1002
00:46:50,580 --> 00:46:52,538
Questo è-- e io onda
la mia mano a questo come si

1003
00:46:52,538 --> 00:46:55,570
potrebbe implementare questa come una struttura C.

1004
00:46:55,570 --> 00:46:58,260
Abbiamo solo bisogno di combinare
un simbolo, come un char,

1005
00:46:58,260 --> 00:46:59,910
e la frequenza in a destra ea sinistra.

1006
00:46:59,910 --> 00:47:02,510
Ma diamo un'occhiata a due
esempi finali che avrai

1007
00:47:02,510 --> 00:47:06,070
ottenere abbastanza familiarità con dopo
quiz zero nel problema set five.

1008
00:47:06,070 --> 00:47:09,210
>> Quindi vi è la struttura dei dati
conosciuta come una tabella hash.

1009
00:47:09,210 --> 00:47:12,247
E una tabella di hash è una specie di
raffreddare in quanto ha secchi.

1010
00:47:12,247 --> 00:47:14,830
E supponiamo ci sono quattro secchi
qui, solo quattro spazi vuoti.

1011
00:47:14,830 --> 00:47:20,830
Ecco un mazzo di carte, e qui è
club, vanga, club, diamanti, club,

1012
00:47:20,830 --> 00:47:25,960
diamanti, club, diamanti,
clubs-- quindi questo è il caso.

1013
00:47:25,960 --> 00:47:30,330
Cuori, hearts-- quindi sono
bucketizing tutti gli ingressi qui.

1014
00:47:30,330 --> 00:47:32,430
E un bisogno tabella di hash
a guardare il tuo ingresso,

1015
00:47:32,430 --> 00:47:34,850
e poi metterlo in un certo
mettere in base a ciò che si vede.

1016
00:47:34,850 --> 00:47:35,600
Si tratta di un algoritmo.

1017
00:47:35,600 --> 00:47:37,980
E stavo usando un super
semplice algoritmo visivo.

1018
00:47:37,980 --> 00:47:40,030
La parte più difficile del quale era
ricordando quello che le foto erano.

1019
00:47:40,030 --> 00:47:41,590
E poi ci sono quattro cose totali.

1020
00:47:41,590 --> 00:47:45,440
>> Ora gli stack crescevano, che
è un disegno intenzionale cosa qui.

1021
00:47:45,440 --> 00:47:46,540
Ma che altro potrei fare?

1022
00:47:46,540 --> 00:47:49,080
Quindi, in realtà qui abbiamo una
mucchio di vecchi libri d'esame della scuola.

1023
00:47:49,080 --> 00:47:51,240
Supponiamo che un gruppo di
nomi degli studenti sono qui.

1024
00:47:51,240 --> 00:47:52,570
Ecco una tabella hash più grande.

1025
00:47:52,570 --> 00:47:54,867
Invece di quattro secchi,
Ho, diciamo 26.

1026
00:47:54,867 --> 00:47:57,950
E non volevamo andare in prestito 26
le cose dal di fuori [? Annenberg?], Così

1027
00:47:57,950 --> 00:48:00,289
ecco cinque che rappresentano
Dalla A alla Z. E se io

1028
00:48:00,289 --> 00:48:03,580
vedere uno studente il cui nome inizia con A,
Ho intenzione di mettere il proprio quiz lì.

1029
00:48:03,580 --> 00:48:08,850
Se qualcuno inizia con C, laggiù,
A-- in realtà, non voleva farlo.

1030
00:48:08,850 --> 00:48:10,060
B va qui.

1031
00:48:10,060 --> 00:48:13,390
Così ho A e B e C. E
ora ecco un altro Uno studente.

1032
00:48:13,390 --> 00:48:16,212
Ma se questa tabella hash è
implementato con una matrice,

1033
00:48:16,212 --> 00:48:17,920
Sono un po 'fregato
a questo punto, giusto?

1034
00:48:17,920 --> 00:48:19,510
I tipi di bisogno di mettere da qualche parte.

1035
00:48:19,510 --> 00:48:24,380
>> Così un modo per risolvere questo problema è, tutto
a destra, A è occupato, B è occupato, C è occupato.

1036
00:48:24,380 --> 00:48:28,880
Ho intenzione di metterlo in D. Quindi, a
prima, ho accesso immediato a caso

1037
00:48:28,880 --> 00:48:31,064
a ciascuna delle benne per gli studenti.

1038
00:48:31,064 --> 00:48:33,230
Ma ora è una specie di devoluto
in qualcosa di lineare,

1039
00:48:33,230 --> 00:48:36,750
perché se voglio cercare qualcuno
il cui nome inizia con A, controllo qui.

1040
00:48:36,750 --> 00:48:38,854
Ma se questo non è l'A
studente sto cercando,

1041
00:48:38,854 --> 00:48:41,520
I tipi di dover avviare il controllo
i secchi, perché quello che ho fatto

1042
00:48:41,520 --> 00:48:44,530
era una sorta di linearmente
sondare la struttura dei dati.

1043
00:48:44,530 --> 00:48:47,710
Un modo stupido di dire basta guardare
per la prima apertura disponibile,

1044
00:48:47,710 --> 00:48:51,850
e mettere come un piano B, per così dire,
o un piano D in questo caso, il valore

1045
00:48:51,850 --> 00:48:53,340
in quella posizione, invece.

1046
00:48:53,340 --> 00:48:56,470
Questo è solo così che se hai
ha ottenuto 26 posizioni e non gli studenti

1047
00:48:56,470 --> 00:49:00,600
con il nome di Q o Z, o qualcosa del genere
che, almeno si sta utilizzando lo spazio.

1048
00:49:00,600 --> 00:49:03,140
>> Ma abbiamo già visto più
soluzioni intelligenti qui, giusto?

1049
00:49:03,140 --> 00:49:04,870
Cosa fareste al posto
se si dispone di una collisione?

1050
00:49:04,870 --> 00:49:06,670
Se due persone hanno
il nome A, quale sarebbe

1051
00:49:06,670 --> 00:49:09,160
stato un intelligente o più
soluzione intuitiva che solo

1052
00:49:09,160 --> 00:49:12,840
mettendo A dove D dovrebbe essere?

1053
00:49:12,840 --> 00:49:14,810
Perché non mi basta andare
al di fuori [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
come malloc, un altro nodo, metterlo
qui, e poi mettere che uno studente qui.

1055
00:49:19,960 --> 00:49:22,120
In modo da avere essenzialmente
una sorta di un array,

1056
00:49:22,120 --> 00:49:25,590
o forse più elegante come siamo
iniziando a vedere una lista collegata.

1057
00:49:25,590 --> 00:49:29,520
>> E così una tabella hash è una struttura
che potrebbe apparire solo come questo,

1058
00:49:29,520 --> 00:49:33,900
ma più intelligente, qualcosa chiamato
concatenazioni separate, per cui una tabella hash

1059
00:49:33,900 --> 00:49:38,340
semplicemente è un array, ciascuno dei
i cui elementi non è un numero,

1060
00:49:38,340 --> 00:49:40,470
è esso stesso una lista collegata.

1061
00:49:40,470 --> 00:49:45,080
In modo da ottenere un accesso super veloce
decidere dove hash vostro valore a.

1062
00:49:45,080 --> 00:49:48,059
Proprio come con la carte esempio,
Ho fatto le decisioni super-veloci.

1063
00:49:48,059 --> 00:49:49,600
Cuori va qui, diamanti va qui.

1064
00:49:49,600 --> 00:49:52,180
Stesso qui, A va qui,
D va qui, B va qui.

1065
00:49:52,180 --> 00:49:55,740
Così super veloce look-up, e se
vi capita di imbattersi in un caso

1066
00:49:55,740 --> 00:49:59,429
collisioni in cui avete ottenuto, due
persone con lo stesso nome, beh, allora

1067
00:49:59,429 --> 00:50:00,970
basta avviare il collegamento insieme.

1068
00:50:00,970 --> 00:50:03,900
E forse tenerli ordinati
in ordine alfabetico, forse no.

1069
00:50:03,900 --> 00:50:05,900
Ma almeno ora abbiamo la dinamicità.

1070
00:50:05,900 --> 00:50:10,250
Così da un lato abbiamo super veloce
costante di tempo, e il tipo di tempo lineare

1071
00:50:10,250 --> 00:50:14,110
coinvolto se queste liste collegate
iniziare a ottenere un po 'lungo.

1072
00:50:14,110 --> 00:50:16,880
>> Quindi questo tipo di sciocco,
anni scherzo geeky fa.

1073
00:50:16,880 --> 00:50:19,590
Al CS50 hack-a-thon,
quando gli studenti check-in,

1074
00:50:19,590 --> 00:50:22,040
alcuni TF o CA ogni anno
pensa che sia divertente per mettere in su

1075
00:50:22,040 --> 00:50:27,772
un segno come questo, dove solo
significa che se il vostro nome inizia con una A,

1076
00:50:27,772 --> 00:50:28,870
andare in questo modo.

1077
00:50:28,870 --> 00:50:31,110
Se il tuo nome inizia
con una B, andare questo-- OK,

1078
00:50:31,110 --> 00:50:33,290
è divertente forse più tardi nel semestre.

1079
00:50:33,290 --> 00:50:36,420
Ma c'è un altro
modo di fare questo, anche.

1080
00:50:36,420 --> 00:50:37,410
Tornate a questo.

1081
00:50:37,410 --> 00:50:38,600
>> Quindi c'è questa struttura.

1082
00:50:38,600 --> 00:50:40,420
E questo è il nostro ultimo
Struttura per oggi,

1083
00:50:40,420 --> 00:50:42,400
che è qualcosa che si chiama un trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, che per qualche motivo è breve
per il recupero, ma si chiama trie.

1085
00:50:47,140 --> 00:50:51,389
Quindi un trie è un altro interessante
amalgama di molte di queste idee.

1086
00:50:51,389 --> 00:50:52,930
Si tratta di un albero, che abbiamo visto prima.

1087
00:50:52,930 --> 00:50:54,180
Non è un albero binario di ricerca.

1088
00:50:54,180 --> 00:50:58,410
E 'un albero con qualsiasi numero di figli,
ma ciascuno dei bambini in un trie

1089
00:50:58,410 --> 00:51:00,090
è un array.

1090
00:51:00,090 --> 00:51:04,790
Una serie di dimensioni, diciamo, 26 o forse 27
se si desidera supportare nomi sillabate

1091
00:51:04,790 --> 00:51:06,790
o apostrofi nei nomi delle persone.

1092
00:51:06,790 --> 00:51:08,280
>> E quindi questa è una struttura di dati.

1093
00:51:08,280 --> 00:51:10,290
E se si guarda dall'alto
in basso, come se si

1094
00:51:10,290 --> 00:51:13,710
guardare il nodo superiore là, M, è
indicando la cosa più a sinistra lì,

1095
00:51:13,710 --> 00:51:17,665
che viene poi A, X, W, E, L, L. Questo è
solo una struttura di dati che arbitrariamente

1096
00:51:17,665 --> 00:51:19,120
è memorizzare i nomi delle persone.

1097
00:51:19,120 --> 00:51:25,720
E Maxwell è memorizzato da solo seguendo
un percorso di array per array di array.

1098
00:51:25,720 --> 00:51:30,050
Ma la cosa sorprendente di un trie è
che, mentre una lista collegata e anche

1099
00:51:30,050 --> 00:51:34,520
un array, la migliore che abbiamo mai ottenuto è
tempo lineare o logaritmico cercando tempo

1100
00:51:34,520 --> 00:51:35,600
qualcuno.

1101
00:51:35,600 --> 00:51:40,530
In questa struttura di dati di un trie, se
la mia struttura di dati ha un nome in esso

1102
00:51:40,530 --> 00:51:43,720
e sto cercando di Maxwell, sono
andando a trovarlo abbastanza rapidamente.

1103
00:51:43,720 --> 00:51:47,910
Mi basta guardare per M-A-X-W-E-L-L. Se
questa struttura dati, per contrasto,

1104
00:51:47,910 --> 00:51:51,830
se N è un milione, se c'è un
milioni di nomi in questa struttura dati,

1105
00:51:51,830 --> 00:51:57,100
Maxwell è ancora in corso per essere
rilevabile dopo appena M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
gradini.

1107
00:51:58,090 --> 00:52:01,276
E passi David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
In altre parole, costruendo
una struttura di dati che è

1109
00:52:03,400 --> 00:52:07,240
ottenuto tutti questi array, tutte
si supportano l'accesso casuale,

1110
00:52:07,240 --> 00:52:11,090
Posso iniziare a guardare il popolo di
nome utilizzando una quantità di tempo che è

1111
00:52:11,090 --> 00:52:14,340
proporzionale non il numero
di cose nella struttura dati,

1112
00:52:14,340 --> 00:52:16,330
come un milione di nomi esistenti.

1113
00:52:16,330 --> 00:52:20,135
La quantità di tempo che ci vuole per trovare
M-A-X-W-E-L-L in questa struttura dati è

1114
00:52:20,135 --> 00:52:22,260
proporzionale non al
dimensioni della struttura di dati,

1115
00:52:22,260 --> 00:52:25,930
ma la lunghezza del nome.

1116
00:52:25,930 --> 00:52:28,440
E realisticamente la
nomi che stanno cercando su

1117
00:52:28,440 --> 00:52:29,970
sono mai andare a essere pazzo lungo.

1118
00:52:29,970 --> 00:52:32,600
Forse qualcuno ha un carattere 10
nome, 20 nome del personaggio.

1119
00:52:32,600 --> 00:52:33,900
E 'certamente finito, giusto?

1120
00:52:33,900 --> 00:52:37,110
C'è un umano sulla Terra che
ha il più lungo possibile nome,

1121
00:52:37,110 --> 00:52:39,920
ma che nome è una costante
lunghezza del valore, giusto?

1122
00:52:39,920 --> 00:52:41,980
Non varia in alcun senso.

1123
00:52:41,980 --> 00:52:45,090
Quindi, in questo modo, abbiamo
realizzato una struttura di dati

1124
00:52:45,090 --> 00:52:47,800
cioè costante di tempo di look-up.

1125
00:52:47,800 --> 00:52:50,670
Ci vuole un certo numero di passi
a seconda della lunghezza dell'input,

1126
00:52:50,670 --> 00:52:54,250
ma non il numero di nome
nella struttura dati.

1127
00:52:54,250 --> 00:52:58,700
Quindi, se raddoppiamo il numero di nomi
il prossimo anno da un miliardo a due miliardi,

1128
00:52:58,700 --> 00:53:03,720
scoperta Maxwell sta andando a prendere
esattamente lo stesso numero di sette passi

1129
00:53:03,720 --> 00:53:04,650
per trovarlo.

1130
00:53:04,650 --> 00:53:08,810
E così ci sembra di aver raggiunto
il nostro Santo Graal di tempo di esecuzione.

1131
00:53:08,810 --> 00:53:10,860
>> Così un paio di brevi annunci.

1132
00:53:10,860 --> 00:53:11,850
Quiz a zero sta arrivando.

1133
00:53:11,850 --> 00:53:14,600
Più su quello sul sito web del corso
nei prossimi due giorni.

1134
00:53:14,600 --> 00:53:17,120
Lunedi di lecture-- è una vacanza
qui a Harvard il Lunedi.

1135
00:53:17,120 --> 00:53:18,850
Non è a New Haven,
così noi stiamo prendendo la classe

1136
00:53:18,850 --> 00:53:20,310
a New Haven per conferenza il Lunedi.

1137
00:53:20,310 --> 00:53:22,550
Tutto sarà girato
e trasmesso in diretta, come al solito,

1138
00:53:22,550 --> 00:53:24,900
ma finiamo oggi
con una seconda clip 30

1139
00:53:24,900 --> 00:53:26,910
chiamati "Pensieri profondi"
da Daven Farnham, che

1140
00:53:26,910 --> 00:53:30,850
è stato ispirato lo scorso anno da Sabato
"Pensieri profondi" di Night Live

1141
00:53:30,850 --> 00:53:35,700
da Jack Handy, che
dovrebbe ora avere un senso.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: E ora, "Deep
Pensieri "di Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Tabella di hash.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Va bene, questo è tutto per ora.

1147
00:53:47,660 --> 00:53:48,805
Ci vediamo la prossima settimana.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: per vederlo in azione.

1150
00:53:56,680 --> 00:53:58,304
Quindi, diamo un'occhiata a che in questo momento.

1151
00:53:58,304 --> 00:53:59,890
Così qui, abbiamo un array non ordinato.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, si può andare avanti e ricominciare
questo per un solo secondo, per favore.

1153
00:54:04,860 --> 00:54:08,562
Va bene, le telecamere sono a rotazione, in modo da
azione quando sei pronto, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Va bene, allora quello che abbiamo
avere qui è un array non ordinato.

1155
00:54:11,020 --> 00:54:13,960
E ho colorato tutti gli elementi
rosso per indicare che è, in effetti,

1156
00:54:13,960 --> 00:54:14,460
indifferenziati.

1157
00:54:14,460 --> 00:54:17,960
Così Ricordiamo che la prima cosa che facciamo
è ordiniamo la metà di sinistra della matrice.

1158
00:54:17,960 --> 00:54:20,630
Poi noi ordiniamo il diritto
metà dell'array.

1159
00:54:20,630 --> 00:54:22,830
E ya-da, ya-da, ya-da,
noi li uniamo insieme.

1160
00:54:22,830 --> 00:54:24,520
E abbiamo una matrice completamente ordinato.

1161
00:54:24,520 --> 00:54:25,360
Ecco come merge sort funziona.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, ehi, ehi,
tagliare, tagliare, tagliare, tagliare.

1163
00:54:27,109 --> 00:54:30,130
Doug non si può solo ya-da, ya-da,
ya-da, il vostro senso attraverso merge sort.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Ho appena fatto.

1165
00:54:31,970 --> 00:54:32,832
Va bene.

1166
00:54:32,832 --> 00:54:33,540
Siamo pronti a partire.

1167
00:54:33,540 --> 00:54:34,760
Diciamo basta continuare a tirare.

1168
00:54:34,760 --> 00:54:35,380
Quindi, comunque,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Devi spiegare
più pienamente di quello.

1170
00:54:37,800 --> 00:54:39,999
Questo non è solo sufficiente.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, non lo facciamo
bisogno di tornare a uno.

1172
00:54:41,790 --> 00:54:42,350
Va bene.

1173
00:54:42,350 --> 00:54:45,690
Comunque, se continuiamo con merge--
Ian, siamo nel bel mezzo delle riprese.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Lo so.

1175
00:54:46,612 --> 00:54:49,320
E non possiamo solo ya-da, ya-da,
ya-da, attraverso l'intero processo.

1176
00:54:49,320 --> 00:54:52,200
Bisogna spiegare come il
due parti vengono fuse insieme.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: ma abbiamo già
ha spiegato come i due sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Hai appena mostrato
loro un array di unione.

1179
00:54:55,321 --> 00:54:56,486
DOUG: sanno il processo.

1180
00:54:56,486 --> 00:54:57,172
Che stanno bene.

1181
00:54:57,172 --> 00:54:58,380
Siamo andati oltre dieci volte.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Hai appena saltato diritto su di essa.

1183
00:55:00,330 --> 00:55:03,360
Stiamo tornando a uno,
non puoi ya-da, ya-da sopra.

1184
00:55:03,360 --> 00:55:05,480
Va bene, torna a uno.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Devo andare indietro
attraverso tutte le diapositive?

1186
00:55:07,833 --> 00:55:08,332
Mio Dio.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
E 'come la sesta volta, Ian.

1189
00:55:13,004 --> 00:55:13,940
Va bene.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Va bene.

1191
00:55:15,200 --> 00:55:16,590
Sei pronto?

1192
00:55:16,590 --> 00:55:17,400
Grande.

1193
00:55:17,400 --> 00:55:18,950
Azione.