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

2
00:00:00,500 --> 00:00:03,340
[RIPRODUZIONE DI BRANI MUSICALI]

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

4
00:00:11,020 --> 00:00:14,010
>> DAVID MALAN: Questo è CS50.

5
00:00:14,010 --> 00:00:18,090
E questo è sia l'inizio e la
end-- come literally-- quasi alla fine

6
00:00:18,090 --> 00:00:18,825
di sei settimane.

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

8
00:00:20,030 --> 00:00:22,640
>> Ho pensato di condividere un
po 'di un fatto divertente.

9
00:00:22,640 --> 00:00:25,370
Ho tirato su questo da un
impostare i dati del semestre passato.

10
00:00:25,370 --> 00:00:29,710
Forse ricorderete che vi chiediamo in ogni
forma set p se hai guardato on-line

11
00:00:29,710 --> 00:00:31,580
o se avete partecipato di persona.

12
00:00:31,580 --> 00:00:33,020
Ed ecco i dati.

13
00:00:33,020 --> 00:00:34,710
Quindi oggi era molto prevedibile.

14
00:00:34,710 --> 00:00:37,126
Ma volevamo passare un po '
di tempo con voi comunque.

15
00:00:37,126 --> 00:00:40,599
Qualcuno vuole ipotizzare il motivo per cui questo
grafico è così frastagliato, su giù, su giù,

16
00:00:40,599 --> 00:00:41,265
così costantemente?

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

18
00:00:42,980 --> 00:00:45,130
Cosa fare ciascuno dei picchi
e depressioni rappresentano?

19
00:00:45,130 --> 00:00:46,005
>> PUBBLICO: [incomprensibile]

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

21
00:00:47,002 --> 00:00:47,835
DAVID MALAN: In effetti.

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

23
00:00:50,900 --> 00:00:55,480
E più in modo divertente, Dio non voglia,
teniamo una lezione di Venerdì

24
00:00:55,480 --> 00:00:58,960
all'inizio del semestre,
questo è quello che accadesse.

25
00:00:58,960 --> 00:01:03,430
Così oggi, noi partecipiamo in un po '
di più su strutture di dati.

26
00:01:03,430 --> 00:01:06,660
E per dare più di un solido
modello mentale per problemi alle cinque,

27
00:01:06,660 --> 00:01:07,450
che è ora fuori.

28
00:01:07,450 --> 00:01:10,817
Errori di ortografia, in cui, faremo
si a mano un file di testo circa 100.000

29
00:01:10,817 --> 00:01:12,650
più le parole inglesi, e
si sta andando ad avere

30
00:01:12,650 --> 00:01:17,770
per capire come caricarli abilmente
nella memoria, in RAM, utilizzando alcuni dati

31
00:01:17,770 --> 00:01:19,330
struttura della vostra scelta.

32
00:01:19,330 --> 00:01:22,470
>> Ora, una tale struttura di dati potrebbe
essere, ma probabilmente non dovrebbe essere,

33
00:01:22,470 --> 00:01:25,630
la lista collegata piuttosto semplicistica,
che abbiamo introdotto l'ultima volta.

34
00:01:25,630 --> 00:01:29,220
E una lista collegata avuto almeno
un vantaggio su un array.

35
00:01:29,220 --> 00:01:32,096
Qual è uno dei vantaggi di
una lista collegata forse?

36
00:01:32,096 --> 00:01:32,950
>> PUBBLICO: inserimento.

37
00:01:32,950 --> 00:01:33,908
>> DAVID MALAN: inserimento.

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

39
00:01:34,155 --> 00:01:35,196
Cosa vuoi dire con questo?

40
00:01:35,196 --> 00:01:37,872
>> PUBBLICO: Ovunque lungo
l'elenco [incomprensibile].

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

42
00:01:38,770 --> 00:01:42,090
Quindi, è possibile inserire un elemento ovunque
si desidera nel bel mezzo della lista

43
00:01:42,090 --> 00:01:45,490
senza dover mescolare nulla,
che abbiamo concluso, nel nostro ordinamento

44
00:01:45,490 --> 00:01:47,630
discussioni, non è
necessariamente una buona cosa,

45
00:01:47,630 --> 00:01:51,200
perché ci vuole tempo per muoversi in realtà
tutti quegli umani a sinistra oa destra.

46
00:01:51,200 --> 00:01:55,540
E così con una lista collegata, è possibile
solo allocare con malloc, un nuovo nodo,

47
00:01:55,540 --> 00:01:58,385
e quindi aggiornare un paio di
pointers-- due, tre operazioni max--

48
00:01:58,385 --> 00:02:01,480
e siamo in grado di scanalare qualcuno
in qualsiasi punto in un elenco.

49
00:02:01,480 --> 00:02:03,550
>> Che altro è stato vantaggioso
su una lista collegata?

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

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

52
00:02:05,659 --> 00:02:06,534
>> PUBBLICO: [incomprensibile]

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

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

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

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

57
00:02:11,090 --> 00:02:12,070
E 'davvero dinamico.

58
00:02:12,070 --> 00:02:15,100
E che non si sta commettendo,
in anticipo, in una certa dimensione fissa

59
00:02:15,100 --> 00:02:18,750
pezzo di memoria, come si avrebbe
a con un array, il lato positivo di cui

60
00:02:18,750 --> 00:02:22,455
è che è possibile allocare i nodi solo su
domanda usando così solo la quantità di spazio

61
00:02:22,455 --> 00:02:23,330
come hai veramente bisogno.

62
00:02:23,330 --> 00:02:26,830
Al contrario di una serie, si potrebbe
accidentalmente allocare troppo poco.

63
00:02:26,830 --> 00:02:28,871
E poi è solo andare
per essere un dolore al collo

64
00:02:28,871 --> 00:02:32,440
di riassegnare un nuovo array più grande, copiare
tutto sopra, libera la vecchia matrice,

65
00:02:32,440 --> 00:02:33,990
e quindi spostare sulla tua attività.

66
00:02:33,990 --> 00:02:37,479
O peggio, si potrebbe allocare modo
più memoria del necessario,

67
00:02:37,479 --> 00:02:40,520
e così si sta andando ad avere un
matrice scarsamente popolate, per così dire.

68
00:02:40,520 --> 00:02:44,350
>> Quindi, una lista collegata ti da questi
vantaggi di dinamismo e flessibilità

69
00:02:44,350 --> 00:02:46,080
con inserimenti ed eliminazioni.

70
00:02:46,080 --> 00:02:48,000
Ma sicuramente ci deve essere un prezzo pagato.

71
00:02:48,000 --> 00:02:50,000
In effetti, uno dei temi
esplorato su quiz a zero

72
00:02:50,000 --> 00:02:52,430
è stato un paio di trade-off
che abbiamo visto finora.

73
00:02:52,430 --> 00:02:56,161
Così che cosa è un prezzo pagato o di un
L'unico inconveniente di una lista concatenata?

74
00:02:56,161 --> 00:02:56,660
Sì.

75
00:02:56,660 --> 00:02:57,560
>> PUBBLICO: Nessun accesso casuale.

76
00:02:57,560 --> 00:02:58,809
>> DAVID MALAN: Nessun accesso casuale.

77
00:02:58,809 --> 00:02:59,540
Ma chi se ne frega?

78
00:02:59,540 --> 00:03:01,546
Accesso casuale non suona convincente.

79
00:03:01,546 --> 00:03:02,421
>> PUBBLICO: [incomprensibile]

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

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

82
00:03:05,740 --> 00:03:07,580
Se si desidera avere
un certo algorithm--

83
00:03:07,580 --> 00:03:10,170
e fammi realtà propongo
ricerca binaria in particolare, che

84
00:03:10,170 --> 00:03:12,600
è quello che abbiamo usato un bel bit--
se non si dispone di accesso casuale,

85
00:03:12,600 --> 00:03:15,516
Non si può fare così semplice aritmetica
di trovare come l'elemento centrale

86
00:03:15,516 --> 00:03:16,530
e saltare diritto.

87
00:03:16,530 --> 00:03:20,239
Devi invece iniziare al primo
elemento lineare e la ricerca da sinistra

88
00:03:20,239 --> 00:03:22,780
a destra se si vuole trovare
la metà o qualsiasi altro elemento.

89
00:03:22,780 --> 00:03:24,410
>> PUBBLICO: Ci vuole probabilmente più memoria.

90
00:03:24,410 --> 00:03:25,040
>> DAVID MALAN: prende più memoria.

91
00:03:25,040 --> 00:03:27,464
Dove è che ulteriore
costo che viene dalle in memoria?

92
00:03:27,464 --> 00:03:28,339
>> PUBBLICO: [incomprensibile]

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

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

95
00:03:33,440 --> 00:03:35,679
In questo caso qui, abbiamo avuto
una lista concatenata per i numeri interi,

96
00:03:35,679 --> 00:03:37,470
ma stiamo raddoppiando
la quantità di memoria

97
00:03:37,470 --> 00:03:39,680
abbiamo bisogno memorizzando anche questi puntatori.

98
00:03:39,680 --> 00:03:42,090
Ora, a meno di un grosso problema come
i tuoi struct si fanno più grandi

99
00:03:42,090 --> 00:03:45,320
e il gioco è la memorizzazione non è un numero, ma
forse uno studente o un qualche altro oggetto.

100
00:03:45,320 --> 00:03:46,880
Ma il punto rimane certamente.

101
00:03:46,880 --> 00:03:49,421
E così una serie di operazioni
su liste concatenate sono stati chiamati

102
00:03:49,421 --> 00:03:50,570
erano grandi o di lineari n--.

103
00:03:50,570 --> 00:03:54,730
Cose come l'inserimento o la ricerca
o cancellazione in caso di un elemento

104
00:03:54,730 --> 00:03:57,720
è capitato di essere alla fine del
l'elenco se è stato o meno ordinato.

105
00:03:57,720 --> 00:04:01,167
>> A volte si potrebbe ottenere fortunati e in
limiti così bassi su queste operazioni

106
00:04:01,167 --> 00:04:04,250
potrebbe anche essere la costante di tempo se siete
sempre guardando il primo elemento,

107
00:04:04,250 --> 00:04:05,070
per esempio.

108
00:04:05,070 --> 00:04:09,360
Ma alla fine, abbiamo promesso
per ottenere il Santo Graal

109
00:04:09,360 --> 00:04:12,630
di strutture di dati, o
un po 'della stessa approssimazione,

110
00:04:12,630 --> 00:04:14,290
a titolo di costante di tempo.

111
00:04:14,290 --> 00:04:17,579
Possiamo trovare elementi o aggiungere elementi
o rimuovere elementi da un elenco?

112
00:04:17,579 --> 00:04:19,059
Vedremo molto presto.

113
00:04:19,059 --> 00:04:21,100
E si scopre che uno
dei meccanismi di cui siamo

114
00:04:21,100 --> 00:04:23,464
intenzione di iniziare ad usare oggi,
utilizzo annuale in p set di cinque,

115
00:04:23,464 --> 00:04:24,630
è in realtà piuttosto familiare.

116
00:04:24,630 --> 00:04:27,430
Ad esempio, se questo è un mazzo
di libri esame, ciascuna delle quali

117
00:04:27,430 --> 00:04:29,660
ha uno studente di prima
nome e cognome su di esso,

118
00:04:29,660 --> 00:04:31,820
e li prendo da
al termine di un esame,

119
00:04:31,820 --> 00:04:33,746
e sono tutti abbastanza
tanto in un ordine casuale,

120
00:04:33,746 --> 00:04:36,370
e vogliamo andare sull'ordinamento
questi esami in modo che, una volta classificati

121
00:04:36,370 --> 00:04:38,661
è solo molto più facile e
più veloce a portata di mano di nuovo fuori

122
00:04:38,661 --> 00:04:40,030
agli studenti in ordine alfabetico.

123
00:04:40,030 --> 00:04:42,770
Che cosa il vostro istinto essere
per un mucchio di esami come questo?

124
00:04:42,770 --> 00:04:45,019
>> Beh, se siete come me, si
potrebbe vedere che questo è m,

125
00:04:45,019 --> 00:04:48,505
così ho intenzione di mettere questo tipo di in,
se questo è il mio tavolo o il mio piano dove

126
00:04:48,505 --> 00:04:50,650
Sto diffondendo le cose
fuori-- o la mia matrice really--

127
00:04:50,650 --> 00:04:52,210
Potrei mettere tutta la signora in là.

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

129
00:04:52,710 --> 00:04:55,020
Ecco un A. Quindi potrei
Come mettere i qui.

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

131
00:04:55,520 --> 00:04:57,980
Ecco un altro A. Vado
mettere che qui.

132
00:04:57,980 --> 00:05:02,490
Ecco una Z. Ecco un altro M. E così
Potrei iniziare a fare i mucchi come questo.

133
00:05:02,490 --> 00:05:06,620
E poi magari mi piacerebbe andare a più tardi
e una sorta di molto nitpicky-ly sorta

134
00:05:06,620 --> 00:05:07,710
i singoli pali.

135
00:05:07,710 --> 00:05:11,300
Ma il punto è che vorrei guardare
in ingresso che sono mano

136
00:05:11,300 --> 00:05:14,016
e vorrei fare qualche calcolato
decisione sulla base di tale ingresso.

137
00:05:14,016 --> 00:05:15,640
Se inizia con A, messo lì.

138
00:05:15,640 --> 00:05:18,980
Se inizia con Z, lo mise sopra
lì, e tutto il resto.

139
00:05:18,980 --> 00:05:22,730
>> Quindi questa è una tecnica che è
generalmente noto come hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
che generalmente significa prendere come
input e usando quell'ingresso per calcolare

141
00:05:26,550 --> 00:05:30,940
un valore, generalmente un numero, e che
numero è l'indice in una memorizzazione

142
00:05:30,940 --> 00:05:32,260
contenitore, come un array.

143
00:05:32,260 --> 00:05:35,490
Quindi, in altre parole, potrei avere un
funzione di hash, come faccio io nella mia testa,

144
00:05:35,490 --> 00:05:37,940
che se vedo qualcuno è
nome che inizia con A,

145
00:05:37,940 --> 00:05:40,190
Ho intenzione di mappa che
a zero nella mia testa.

146
00:05:40,190 --> 00:05:44,160
E se vedo qualcuno con Z, io sono
andando a mappare che a 25 nella mia testa

147
00:05:44,160 --> 00:05:46,220
e poi metterlo in
l'ultima più mucchio.

148
00:05:46,220 --> 00:05:50,990
>> Ora, se ci pensate non il mio cervello
ma un programma C, quali numeri potrebbero

149
00:05:50,990 --> 00:05:53,170
ci si affida per ottenere lo stesso risultato?

150
00:05:53,170 --> 00:05:55,594
In altre parole, se si
aveva il carattere ASCII A,

151
00:05:55,594 --> 00:05:57,510
come si fa a determinare
cosa secchio per mettere in?

152
00:05:57,510 --> 00:05:59,801
Probabilmente non si vuole
metterlo nel secchio 65, che

153
00:05:59,801 --> 00:06:01,840
sarebbe come laggiù
per nessuna buona ragione.

154
00:06:01,840 --> 00:06:04,320
Dove vuoi mettere un
in termini di valore ASCII?

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

156
00:06:05,600 --> 00:06:08,920
Dove vuoi fare per la sua ASCII
Valore a venire con un secchio intelligente

157
00:06:08,920 --> 00:06:09,480
per dirla in?

158
00:06:09,480 --> 00:06:10,206
>> PUBBLICO: Minus A.

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

160
00:06:10,956 --> 00:06:13,190
Quindi meno A o meno
in particolare 65 se si tratta di

161
00:06:13,190 --> 00:06:18,240
la A maiuscola o 98 se
si tratta di un minuscolo a.

162
00:06:18,240 --> 00:06:21,300
E in modo che sarebbe ci permettono di, molto
in modo semplice e molto aritmeticamente,

163
00:06:21,300 --> 00:06:23,260
mettere qualcosa in un secchio del genere.

164
00:06:23,260 --> 00:06:26,010
Così si scopre che in realtà facciamo
anche questo anche con i quiz.

165
00:06:26,010 --> 00:06:29,051
>> Così si potrebbe ricordare che si cerchiata la tua
Nome insegnamento del compagno sulla copertina.

166
00:06:29,051 --> 00:06:32,270
E nomi del TF sono state organizzate
in queste colonne in ordine alfabetico,

167
00:06:32,270 --> 00:06:34,400
beh, che ci crediate o no,
quando tutto 80, più di noi

168
00:06:34,400 --> 00:06:37,800
si sono riuniti l'altra sera al grado,
l'ultimo passo del nostro processo di classificazione

169
00:06:37,800 --> 00:06:41,830
è quello di eseguire l'hashing dei quiz in un grande
lo spazio di pavimento al [incomprensibile]

170
00:06:41,830 --> 00:06:45,110
nonché di definire i quiz di tutti i
esattamente l'ordine delle loro TF di

171
00:06:45,110 --> 00:06:47,700
nomi sulla copertina, in quanto
allora è molto più facile per noi

172
00:06:47,700 --> 00:06:51,290
per la ricerca in che l'utilizzo di lineare
ricerca o qualche tipo di intelligenza

173
00:06:51,290 --> 00:06:54,050
per un TF a trovare la sua o
quiz dei suoi studenti.

174
00:06:54,050 --> 00:06:56,060
>> Quindi questa idea di hashing
che vedrete è

175
00:06:56,060 --> 00:07:00,520
abbastanza potente è in realtà piuttosto
banale e molto intuitivo,

176
00:07:00,520 --> 00:07:03,000
molto simile forse dividere e
conquista era in settimana pari a zero.

177
00:07:03,000 --> 00:07:05,250
I fast forward al hackathon
un paio di anni fa.

178
00:07:05,250 --> 00:07:08,040
Questo era Zamyla e un paio di
altri studenti di auguri personale

179
00:07:08,040 --> 00:07:09,030
come sono venuti in.

180
00:07:09,030 --> 00:07:12,680
E abbiamo avuto un sacco di piegatura
tavoli lì con etichette nome.

181
00:07:12,680 --> 00:07:15,380
E avevamo i cartellini organizzata
con come le Come laggiù

182
00:07:15,380 --> 00:07:16,690
e la Zs laggiù.

183
00:07:16,690 --> 00:07:20,350
E così uno dei TF molto abilmente
ha scritto questo come le istruzioni

184
00:07:20,350 --> 00:07:21,030
per la giornata.

185
00:07:21,030 --> 00:07:24,480
E nella settimana 12 del semestre tale
tutto aveva un senso perfetto e tutti

186
00:07:24,480 --> 00:07:25,310
sapeva che cosa fare.

187
00:07:25,310 --> 00:07:27,900
Ma ogni volta che hai
coda nello stesso modo,

188
00:07:27,900 --> 00:07:30,272
sei l'attuazione del
stessa nozione di un hash.

189
00:07:30,272 --> 00:07:31,730
Quindi cerchiamo di formalizzare un po '.

190
00:07:31,730 --> 00:07:32,890
Qui è un array.

191
00:07:32,890 --> 00:07:36,820
E 'disegnato per essere un po'
ampia solo di rappresentare, visivamente,

192
00:07:36,820 --> 00:07:38,920
che potremmo mettere stringhe
in qualcosa di simile a questo.

193
00:07:38,920 --> 00:07:41,970
E questo array è
chiaramente di dimensione 26 in totale.

194
00:07:41,970 --> 00:07:43,935
E la cosa si chiama
tavolo arbitrariamente.

195
00:07:43,935 --> 00:07:48,930
Ma questo è solo resa di un artista
di quello che potrebbe essere una tabella hash.

196
00:07:48,930 --> 00:07:52,799
>> Quindi una tabella hash ora sta per
una struttura di dati di livello superiore.

197
00:07:52,799 --> 00:07:54,840
Alla fine della giornata
stiamo per vedere che si

198
00:07:54,840 --> 00:07:58,700
in grado di implementare una tabella hash, che
è molto simile alla linea del check-in

199
00:07:58,700 --> 00:08:02,059
ad un hackathon molto simile a questo
tavolo utilizzato per l'ordinamento di libri d'esame.

200
00:08:02,059 --> 00:08:03,850
Ma una tabella hash è
specie di questo elevato livello

201
00:08:03,850 --> 00:08:08,250
concetto che potrebbe utilizzare un array
sotto la cappa per la sua attuazione,

202
00:08:08,250 --> 00:08:11,890
o potrebbe utilizzare un elenco di lunghezza, o addirittura
forse alcune altre strutture di dati.

203
00:08:11,890 --> 00:08:15,590
Ed ora che è la presa theme--
alcuni di questi ingredienti fondamentali

204
00:08:15,590 --> 00:08:18,310
come un array e questo edificio
bloccare ora di una lista di lunghezza

205
00:08:18,310 --> 00:08:21,740
e vedere che cosa possiamo costruire
in cima a quelli, come ingredienti

206
00:08:21,740 --> 00:08:26,550
in una ricetta, rendendo più
risultati finali interessanti e utili.

207
00:08:26,550 --> 00:08:28,680
>> Quindi, con la tabella di hash
potremmo attuarlo

208
00:08:28,680 --> 00:08:32,540
in memoria pittoricamente come questo, ma
come potrebbe essere in realtà codificato up?

209
00:08:32,540 --> 00:08:33,789
Beh, forse nel modo più semplice è questo.

210
00:08:33,789 --> 00:08:38,270
Se la capacità in tutte le protezioni, è solo
alcuni constant-- per esempio 26,

211
00:08:38,270 --> 00:08:42,030
per le 26 lettere dell'alfabeto alphabet--
Potrei chiamare la mia tabella delle variabili,

212
00:08:42,030 --> 00:08:45,630
e potrei affermare che ho intenzione di
mettere stelle char in là, o una stringa.

213
00:08:45,630 --> 00:08:49,880
Quindi è semplice come questo se si
desidera implementare una tabella hash.

214
00:08:49,880 --> 00:08:51,490
Eppure, questo è in realtà solo un array.

215
00:08:51,490 --> 00:08:53,198
Ma ancora una volta, un hash
tabella è ora che cosa faremo

216
00:08:53,198 --> 00:08:57,470
chiamare un tipo di dato astratto che è solo
sorta di stratificazione concettuale in cima

217
00:08:57,470 --> 00:09:00,780
di qualcosa di più banale
ora come un array.

218
00:09:00,780 --> 00:09:02,960
>> Ora, come possiamo fare
di risolvere i problemi?

219
00:09:02,960 --> 00:09:06,980
Beh, in precedenza ho avuto il lusso
di avere abbastanza spazio tabella qui

220
00:09:06,980 --> 00:09:09,460
in modo da poter mettere il
quiz ovunque volevo.

221
00:09:09,460 --> 00:09:10,620
Così come potrebbe andare qui.

222
00:09:10,620 --> 00:09:12,100
Zs potrebbero andare qui.

223
00:09:12,100 --> 00:09:13,230
La signora potrebbe andare qui.

224
00:09:13,230 --> 00:09:14,740
E poi ho avuto un po 'di spazio in più.

225
00:09:14,740 --> 00:09:18,740
Ma questo è un po 'di un diritto imbroglio
ora perché questa tabella, se davvero

226
00:09:18,740 --> 00:09:22,720
pensato come una matrice, è solo
andando essere di qualche dimensione fissa.

227
00:09:22,720 --> 00:09:25,380
>> Tecnicamente, quindi, se tiro
up quiz di un altro studente

228
00:09:25,380 --> 00:09:28,490
e vedere, oh, questa persona di
nome inizia con una A troppo,

229
00:09:28,490 --> 00:09:30,980
I tipi di voglia di metterlo lì.

230
00:09:30,980 --> 00:09:34,740
Ma non appena ho messo lì, se
Questa tabella rappresenta infatti una matrice,

231
00:09:34,740 --> 00:09:37,840
Ho intenzione di essere priorità assoluta o sovrascrivere
chi quiz di questo studente è.

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

233
00:09:38,340 --> 00:09:41,972
Se questo è un array, solo una cosa può
andare in ciascuna di queste cellule o elementi.

234
00:09:41,972 --> 00:09:43,680
E così ho sorta di ho
di scegliere.

235
00:09:43,680 --> 00:09:45,735
>> Ora prima che tipo di
truffato e ha fatto questo o io

236
00:09:45,735 --> 00:09:47,526
solo tipo di impilati
li sopra l'altra.

237
00:09:47,526 --> 00:09:49,170
Ma che non sta andando a volare nel codice.

238
00:09:49,170 --> 00:09:52,260
Allora, dove posso mettere la
secondo studente il cui nome

239
00:09:52,260 --> 00:09:54,964
è A se tutto quello che avevo è questo
disponibile spazio di tabella?

240
00:09:54,964 --> 00:09:57,880
E io ho usato tre slot ed è
sembra che ci sia solo un pochi altri.

241
00:09:57,880 --> 00:09:58,959
Che cosa si potrebbe fare?

242
00:09:58,959 --> 00:09:59,834
PUBBLICO: [incomprensibile]

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

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

245
00:10:01,315 --> 00:10:02,370
Forse facciamo solo mantenere le cose semplici.

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

247
00:10:02,660 --> 00:10:04,243
Non si adatta dove voglio metterlo.

248
00:10:04,243 --> 00:10:07,450
Quindi ho intenzione di metterlo
tecnicamente in cui un B sarebbe andato.

249
00:10:07,450 --> 00:10:09,932
Ora, naturalmente, sto iniziando
a dipingere me stesso in un angolo.

250
00:10:09,932 --> 00:10:11,890
Se arrivare a uno studente
il cui nome è in realtà B,

251
00:10:11,890 --> 00:10:14,840
Ora B sta per essere spostato leggermente
in avanti, come potrebbe accadere, sì,

252
00:10:14,840 --> 00:10:17,530
se questo è un B, ora deve andare qui.

253
00:10:17,530 --> 00:10:20,180
>> E così questo molto rapidamente
potrebbe diventare problematico,

254
00:10:20,180 --> 00:10:23,850
ma è una tecnica che effettivamente
viene indicato come scansione lineare,

255
00:10:23,850 --> 00:10:26,650
per cui è sufficiente prendere in considerazione il vostro
array per essere lungo la linea.

256
00:10:26,650 --> 00:10:29,680
E tu solo tipo di sonda o
ispezionare ogni elemento disponibile

257
00:10:29,680 --> 00:10:31,360
alla ricerca di un posto disponibile.

258
00:10:31,360 --> 00:10:34,010
E non appena si trova
uno, viene rilasciato in là.

259
00:10:34,010 --> 00:10:38,390
>> Ora, il prezzo viene pagato ora
per questa soluzione è quello?

260
00:10:38,390 --> 00:10:41,300
Abbiamo un array di dimensione fissa,
e quando inserisco i nomi

261
00:10:41,300 --> 00:10:44,059
in esso, almeno inizialmente, ciò che è
il tempo di esecuzione di insertion

262
00:10:44,059 --> 00:10:46,350
per mettere gli studenti
quiz nei secchi giusto?

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

264
00:10:48,710 --> 00:10:50,002
Big O di che cosa?

265
00:10:50,002 --> 00:10:51,147
>> PUBBLICO: n.

266
00:10:51,147 --> 00:10:52,480
DAVID MALAN: Ho sentito grande O di n.

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

268
00:10:53,530 --> 00:10:54,300
Non è vero.

269
00:10:54,300 --> 00:10:56,490
Ma ci prendono in giro a parte
perché in un attimo.

270
00:10:56,490 --> 00:10:57,702
Che altro potrebbe essere?

271
00:10:57,702 --> 00:10:58,755
>> PUBBLICO: [incomprensibile]

272
00:10:58,755 --> 00:11:00,380
DAVID MALAN: E lasciate fare a me visivamente.

273
00:11:00,380 --> 00:11:04,720
Quindi supponiamo che questa è la lettera S.

274
00:11:04,720 --> 00:11:05,604
>> PUBBLICO: E 'una.

275
00:11:05,604 --> 00:11:06,520
DAVID MALAN: E 'uno.

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

277
00:11:06,710 --> 00:11:08,950
Questo è un array che
significa che abbiamo accesso casuale.

278
00:11:08,950 --> 00:11:11,790
E se pensiamo a questo
come zero e questo come 25,

279
00:11:11,790 --> 00:11:13,800
e ci rendiamo conto che,
oh, ecco il mio ingresso S,

280
00:11:13,800 --> 00:11:16,350
Posso certamente convertire
S, un carattere ASCII,

281
00:11:16,350 --> 00:11:18,540
di altrettante
tra zero e 25

282
00:11:18,540 --> 00:11:20,910
e poi subito
metterlo in cui essa appartiene.

283
00:11:20,910 --> 00:11:26,120
>> Ma, naturalmente, non appena arrivo al
seconda persona il cui nome è A o B o C

284
00:11:26,120 --> 00:11:29,300
alla fine, se ho usato il
scansione lineare come la mia soluzione,

285
00:11:29,300 --> 00:11:31,360
il tempo di esecuzione di
inserimento nel caso peggiore

286
00:11:31,360 --> 00:11:33,120
è in realtà andando a devolvere in che cosa?

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

288
00:11:34,270 --> 00:11:36,045
E ho sentito qui
correttamente nella fase iniziale.

289
00:11:36,045 --> 00:11:36,920
PUBBLICO: [incomprensibile]

290
00:11:36,920 --> 00:11:41,620
DAVID MALAN: Così è in effetti una volta n
si dispone di un numero sufficientemente ampio insieme di dati.

291
00:11:41,620 --> 00:11:44,410
Così, da un lato, se
la matrice è abbastanza grande

292
00:11:44,410 --> 00:11:48,287
ei dati sono abbastanza scarsa, è
ottenere questo bel tempo costante.

293
00:11:48,287 --> 00:11:50,620
Ma non appena si inizia a
sempre più elementi,

294
00:11:50,620 --> 00:11:53,200
e solo statisticamente si ottiene
più persone con la lettera

295
00:11:53,200 --> 00:11:56,030
A come il loro nome o la lettera
B, si potrebbe potenzialmente

296
00:11:56,030 --> 00:11:57,900
devolvere in qualcosa di più lineare.

297
00:11:57,900 --> 00:11:59,640
Quindi, non del tutto perfetto.

298
00:11:59,640 --> 00:12:00,690
Così abbiamo potuto fare di meglio?

299
00:12:00,690 --> 00:12:03,210
>> Beh, quello che era il nostro
soluzione prima quando abbiamo

300
00:12:03,210 --> 00:12:06,820
vogliono avere più dinamismo di
qualcosa di simile a un array permesso?

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

302
00:12:08,085 --> 00:12:08,960
PUBBLICO: [incomprensibile]

303
00:12:08,960 --> 00:12:10,030
DAVID MALAN: Cosa abbiamo presentiamo?

304
00:12:10,030 --> 00:12:10,530
Sì.

305
00:12:10,530 --> 00:12:11,430
Quindi, una lista collegata.

306
00:12:11,430 --> 00:12:14,430
Bene, vediamo cosa un legato
elenco potrebbe fare per noi, invece.

307
00:12:14,430 --> 00:12:17,630
Bene, lasciate che propongo di
disegnare l'immagine come segue.

308
00:12:17,630 --> 00:12:19,620
Ora questo è un diverso
un'immagine da un esempio

309
00:12:19,620 --> 00:12:24,750
da un testo diverso, in realtà, che
è in realtà utilizzando un array di dimensione 31.

310
00:12:24,750 --> 00:12:28,220
E questo autore semplicemente
deciso di hash stringhe

311
00:12:28,220 --> 00:12:32,430
non basata sui nomi della persona,
ma in base alle loro date di nascita.

312
00:12:32,430 --> 00:12:35,680
Indipendentemente mese, hanno pensato
se sei nato il primo di un mese

313
00:12:35,680 --> 00:12:39,580
o il 31 del mese, l'autore
si hash sulla base di tale valore,

314
00:12:39,580 --> 00:12:44,154
al fine di diffondere i nomi un po '
più di 26 punti potrebbero permettere.

315
00:12:44,154 --> 00:12:47,320
E forse è un po 'più uniforme
che andare con le lettere alfabetiche,

316
00:12:47,320 --> 00:12:50,236
perché naturalmente c'è probabilmente
maggior numero di persone nel mondo con nomi

317
00:12:50,236 --> 00:12:54,020
che iniziano con un certo rispetto
alcune altre lettere dell'alfabeto.

318
00:12:54,020 --> 00:12:56,380
Quindi forse questo è un po '
più uniforme, assumendo

319
00:12:56,380 --> 00:12:58,640
una distribuzione uniforme
dei neonati attraverso un mese.

320
00:12:58,640 --> 00:12:59,990
>> Ma, naturalmente, questo è ancora imperfetta.

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

322
00:13:00,370 --> 00:13:01,370
Stiamo avendo collisioni.

323
00:13:01,370 --> 00:13:04,680
Più persone in questo
struttura dei dati sono ancora

324
00:13:04,680 --> 00:13:08,432
aventi la stessa data di nascita almeno
sei a prescindere dal mese.

325
00:13:08,432 --> 00:13:09,640
Ma che cosa ha fatto l'autore?

326
00:13:09,640 --> 00:13:13,427
Beh, sembra che abbiamo un array
sul lato sinistro disegnata verticalmente,

327
00:13:13,427 --> 00:13:15,010
ma questo è solo resa di un artista.

328
00:13:15,010 --> 00:13:18,009
Non importa quale direzione si
disegnare un array, è ancora un array.

329
00:13:18,009 --> 00:13:20,225
Che cosa è questa una serie di apparenza?

330
00:13:20,225 --> 00:13:21,500
>> PUBBLICO: lista collegata.

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

332
00:13:21,650 --> 00:13:23,490
Sembra come se fosse un
serie di lista collegata.

333
00:13:23,490 --> 00:13:26,490
Quindi, di nuovo, a questo punto di genere
di utilizzare queste strutture di dati ora

334
00:13:26,490 --> 00:13:28,550
come ingredienti di più
soluzioni interessanti,

335
00:13:28,550 --> 00:13:30,862
si può assolutamente fare una
fondamentale, come un array,

336
00:13:30,862 --> 00:13:33,320
e poi prendere qualcosa di più
interessante come una lista concatenata

337
00:13:33,320 --> 00:13:36,660
e anche combinarli in un ancora
struttura dati più interessante.

338
00:13:36,660 --> 00:13:39,630
E in effetti, anche questo sarebbe
essere definito una tabella hash,

339
00:13:39,630 --> 00:13:42,610
per cui la matrice è
davvero la tabella di hash,

340
00:13:42,610 --> 00:13:45,600
ma che tabella di hash ha
catene, per così dire,

341
00:13:45,600 --> 00:13:50,220
che può crescere o diminuire in base alla
numero di elementi che si desidera inserire.

342
00:13:50,220 --> 00:13:52,990
>> Ora, di conseguenza, che cosa è
il tempo di esecuzione ora?

343
00:13:52,990 --> 00:13:58,030
Se voglio inserire qualcuno
il cui compleanno è il 31 ottobre,

344
00:13:58,030 --> 00:13:59,040
da dove viene lui o lei andare?

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

346
00:14:00,530 --> 00:14:01,030
Bene.

347
00:14:01,030 --> 00:14:02,819
In fondo molto dove c'è scritto 31.

348
00:14:02,819 --> 00:14:03,610
E questo è perfetto.

349
00:14:03,610 --> 00:14:05,060
E 'stato costante di tempo.

350
00:14:05,060 --> 00:14:08,760
Ma cosa succede se troviamo qualcun altro
il cui compleanno è, vediamo,

351
00:14:08,760 --> 00:14:10,950
Ottobre, novembre, 31 dicembre?

352
00:14:10,950 --> 00:14:12,790
Casi in cui è lui o lei sta per andare?

353
00:14:12,790 --> 00:14:13,290
Stessa cosa.

354
00:14:13,290 --> 00:14:13,970
Due step però.

355
00:14:13,970 --> 00:14:15,303
Questo è costante anche se non è vero?

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

357
00:14:16,360 --> 00:14:16,860
Bene.

358
00:14:16,860 --> 00:14:17,840
Al momento è.

359
00:14:17,840 --> 00:14:20,570
Ma nel caso generale,
più la gente aggiungiamo noi,

360
00:14:20,570 --> 00:14:23,790
probabilisticamente, stiamo andando
per ottenere sempre più collisioni.

361
00:14:23,790 --> 00:14:26,820
>> Ora questo è un po '
meglio perché tecnicamente

362
00:14:26,820 --> 00:14:34,580
ora le mie catene potrebbero essere in
il caso peggiore per quanto tempo?

363
00:14:34,580 --> 00:14:38,890
Se inserisco n persone in questo più
sofisticata struttura di dati, n persone,

364
00:14:38,890 --> 00:14:41,080
nel peggiore dei casi sarà n.

365
00:14:41,080 --> 00:14:41,815
Perché?

366
00:14:41,815 --> 00:14:43,332
>> PUBBLICO: Perché se tutti
ha lo stesso compleanno,

367
00:14:43,332 --> 00:14:44,545
si sta andando ad essere una linea.

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

369
00:14:45,420 --> 00:14:47,480
Potrebbe essere un po 'forzato,
ma veramente nel peggiore dei casi,

370
00:14:47,480 --> 00:14:50,117
se tutti hanno la stessa data di nascita,
dato gli input che avete,

371
00:14:50,117 --> 00:14:51,950
si sta andando ad avere un
massicciamente lunga catena.

372
00:14:51,950 --> 00:14:54,241
E così, si potrebbe chiamare un
hash tavolo, ma in realtà è

373
00:14:54,241 --> 00:14:56,810
solo un enorme lista collegata con
un sacco di spazio sprecato.

374
00:14:56,810 --> 00:15:00,460
Ma in generale, se si assume che
almeno compleanni sono uniform--

375
00:15:00,460 --> 00:15:01,750
e probabilmente non lo è.

376
00:15:01,750 --> 00:15:02,587
Sto facendo che fino.

377
00:15:02,587 --> 00:15:04,420
Ma se si assume, per
il bene della discussione

378
00:15:04,420 --> 00:15:07,717
che sono, poi, in teoria, se
questa è la rappresentazione verticale

379
00:15:07,717 --> 00:15:11,050
della matrice, beh, allora si spera che sei
intenzione di ottenere catene che sono, si sa,

380
00:15:11,050 --> 00:15:15,880
all'incirca la stessa lunghezza in cui ciascuno di
questi rappresenta un giorno del mese.

381
00:15:15,880 --> 00:15:19,930
>> Ora, se c'è 31 giorni in mese,
questo significa che il mio tempo di esecuzione davvero

382
00:15:19,930 --> 00:15:25,230
è grande O di n più di 31, che
si sente meglio che lineare.

383
00:15:25,230 --> 00:15:27,950
Ma quello che era uno dei nostri
impegni un paio di settimane

384
00:15:27,950 --> 00:15:31,145
fa ogni volta che si è trattato di esprimere
il tempo di esecuzione di un algoritmo?

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

386
00:15:33,450 --> 00:15:35,190
Basta guardare solo al termine di ordine superiore.

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

388
00:15:35,690 --> 00:15:37,400
31 è sicuramente utile.

389
00:15:37,400 --> 00:15:39,610
Ma questo è ancora un grande O di n.

390
00:15:39,610 --> 00:15:41,730
Ma uno dei temi
del problema ha impostato cinque

391
00:15:41,730 --> 00:15:43,950
sta per essere a
riconoscere che assolutamente,

392
00:15:43,950 --> 00:15:47,320
asintoticamente, in teoria
questa struttura dati

393
00:15:47,320 --> 00:15:50,470
non è meglio di un semplice
una massiccia lista collegata.

394
00:15:50,470 --> 00:15:53,550
E infatti, nel caso peggiore, questo
tabella hash potrebbe devolvere in quello.

395
00:15:53,550 --> 00:15:57,620
>> Ma nel mondo reale, con noi esseri umani
che proprio Mac o PC o qualsiasi altra cosa

396
00:15:57,620 --> 00:16:01,240
e sono in esecuzione mondo reale
software su dati reali,

397
00:16:01,240 --> 00:16:03,260
che algoritmo hai intenzione di preferire?

398
00:16:03,260 --> 00:16:09,180
Quello che fa passi finali o le
uno che prende n diviso per 31 passi

399
00:16:09,180 --> 00:16:12,900
di trovare qualche pezzo di dati o
per cercare qualche informazione?

400
00:16:12,900 --> 00:16:16,580
Voglio dire, assolutamente le 31 marche
la differenza nel mondo reale.

401
00:16:16,580 --> 00:16:18,540
E '31 volte più veloce.

402
00:16:18,540 --> 00:16:20,880
E noi esseri umani sono certamente
andare a capire che.

403
00:16:20,880 --> 00:16:23,004
>> Quindi realizzare la dicotomia
ci tra realtà

404
00:16:23,004 --> 00:16:25,920
parlando di cose teoricamente
e asintoticamente che sicuramente

405
00:16:25,920 --> 00:16:28,760
ha valore come abbiamo visto,
ma nel mondo reale,

406
00:16:28,760 --> 00:16:32,930
se ti interessa solo fare il
felice umana per gli ingressi generali,

407
00:16:32,930 --> 00:16:36,010
si potrebbe benissimo voler accettare
il fatto che, sì, questo è lineare,

408
00:16:36,010 --> 00:16:38,360
ma è 31 volte più veloce
che lineare potrebbe essere.

409
00:16:38,360 --> 00:16:41,610
E meglio ancora, non ci resta che
fare qualcosa di arbitrario come una data di nascita,

410
00:16:41,610 --> 00:16:44,030
abbiamo potuto trascorrere un po '
più tempo e intelligenza

411
00:16:44,030 --> 00:16:47,140
e pensare a ciò che potremmo fare,
dato il nome di una persona e forse

412
00:16:47,140 --> 00:16:50,130
la loro data di nascita di combinare quelle
ingredienti per capire qualcosa

413
00:16:50,130 --> 00:16:52,720
che è veramente più
uniforme e meno Jaggy,

414
00:16:52,720 --> 00:16:56,250
per così dire di questa immagine
Attualmente suggerisce che potrebbe essere.

415
00:16:56,250 --> 00:16:57,750
Come potremmo implementare questo in codice?

416
00:16:57,750 --> 00:17:00,280
Bene, lasciate che propongo di
solo prendere in prestito un po 'di sintassi che abbiamo

417
00:17:00,280 --> 00:17:01,799
usato un paio di volte finora.

418
00:17:01,799 --> 00:17:03,590
E ho intenzione di definire
un nodo, che di nuovo

419
00:17:03,590 --> 00:17:06,812
è un termine generico per solo alcuni
Contenitore per qualche struttura dati.

420
00:17:06,812 --> 00:17:09,020
Ho intenzione di proporre che
una stringa sta andando in là.

421
00:17:09,020 --> 00:17:11,369
Ma stiamo per iniziare a prendere
quelli formazione ruote fuori ora.

422
00:17:11,369 --> 00:17:13,230
>> Non più biblioteca CS50
in realtà, se non si desidera

423
00:17:13,230 --> 00:17:15,230
da utilizzare per il vostro finale
progetto, che va bene,

424
00:17:15,230 --> 00:17:18,569
ma ora stiamo andando a tirare indietro la
tenda e dire che è solo una stella char.

425
00:17:18,569 --> 00:17:22,069
Così la parola non sta per essere
il nome della persona in questione.

426
00:17:22,069 --> 00:17:25,079
E ora ho un link
Qui al nodo successivo

427
00:17:25,079 --> 00:17:28,170
in modo che questi rappresentano
ciascuno dei nodi

428
00:17:28,170 --> 00:17:30,950
nella catena, potenzialmente,
di una lista collegata.

429
00:17:30,950 --> 00:17:34,090
>> E adesso come faccio dichiaro
la tabella hash in sé?

430
00:17:34,090 --> 00:17:36,660
Come dichiaro tutta questa struttura?

431
00:17:36,660 --> 00:17:40,960
Beh, in realtà, proprio come ho usato un puntatore
a solo il primo elemento di una lista

432
00:17:40,960 --> 00:17:44,510
prima, allo stesso modo posso solo dire
Ho solo bisogno di un po 'di puntatori

433
00:17:44,510 --> 00:17:46,270
per attuare questa tabella intero hash.

434
00:17:46,270 --> 00:17:49,484
Ho intenzione di avere un array
chiamato tavolo per tabella hash.

435
00:17:49,484 --> 00:17:50,900
Sta andando essere di capacità dimensioni.

436
00:17:50,900 --> 00:17:52,525
Questo è il numero di elementi può andare bene in esso.

437
00:17:52,525 --> 00:17:56,180
E ciascuno di questi elementi in questo
serie sta per essere una stella nodo.

438
00:17:56,180 --> 00:17:56,810
Perché?

439
00:17:56,810 --> 00:18:00,160
Ebbene, a questa immagine, quello che sto
l'attuazione della tabella di hash come

440
00:18:00,160 --> 00:18:04,330
efficacemente in principio è solo
questo array che abbiamo disegnato in senso verticale,

441
00:18:04,330 --> 00:18:06,820
ciascuno dei quali piazze
rappresenta un puntatore.

442
00:18:06,820 --> 00:18:09,170
Che quelli che hanno barre
attraverso di loro sono proprio nulla.

443
00:18:09,170 --> 00:18:11,410
E quelli che hanno
frecce che vanno a destra

444
00:18:11,410 --> 00:18:16,140
sono puntatori effettivi nodi effettivi,
ergo l'inizio di una lista collegata.

445
00:18:16,140 --> 00:18:19,050
>> Ecco, allora, è il modo in cui potrebbe
implementare una tabella hash che

446
00:18:19,050 --> 00:18:21,580
implementa concatenazioni separate.

447
00:18:21,580 --> 00:18:22,840
Ora siamo in grado di fare di meglio?

448
00:18:22,840 --> 00:18:25,632
Va bene ho promesso l'ultima volta che
potremmo realizzare costante di tempo.

449
00:18:25,632 --> 00:18:27,381
E mi avete dato tipo di
costante di tempo qui,

450
00:18:27,381 --> 00:18:29,850
ma poi non è detto veramente
costante di tempo perché è ancora

451
00:18:29,850 --> 00:18:31,890
dipendente dal totale
numero di elementi

452
00:18:31,890 --> 00:18:34,500
si sta inserendo in
la struttura dei dati.

453
00:18:34,500 --> 00:18:35,980
Ma supponiamo che abbiamo fatto questo.

454
00:18:35,980 --> 00:18:39,550
Lasciatemi tornare alla schermata qui.

455
00:18:39,550 --> 00:18:44,520
Vorrei anche proietto questo qui, chiaro
lo schermo, e supponiamo che ho fatto questo.

456
00:18:44,520 --> 00:18:49,300
Supponiamo che io volevo inserire il nome
Daven in nella mia struttura dati.

457
00:18:49,300 --> 00:18:52,100
>> Quindi voglio inserire una stringa
Daven nella struttura dati.

458
00:18:52,100 --> 00:18:54,370
Cosa succede se non uso un
hash tavolo, ma io uso

459
00:18:54,370 --> 00:18:56,980
qualcosa che è più ad albero
come un albero genealogico, in cui

460
00:18:56,980 --> 00:18:59,670
avete qualche radice in
superiore e poi i nodi e foglie

461
00:18:59,670 --> 00:19:01,440
che vanno verso il basso e verso l'esterno.

462
00:19:01,440 --> 00:19:04,450
Supponiamo allora, che
desidera inserire Daven di

463
00:19:04,450 --> 00:19:06,430
in quello che è attualmente un elenco vuoto.

464
00:19:06,430 --> 00:19:09,780
Ho intenzione di fare quanto segue: io sono
andando a creare un nodo in questa famiglia

465
00:19:09,780 --> 00:19:15,170
albero-come struttura di dati che guarda
un po 'come questo, ciascuno dei quali

466
00:19:15,170 --> 00:19:19,640
rettangoli ha, diciamo,
per ora 26 elementi in esso.

467
00:19:19,640 --> 00:19:21,650
E ciascuna delle cellule
in questo array sta andando

468
00:19:21,650 --> 00:19:23,470
per rappresentare la lettera di un alfabeto.

469
00:19:23,470 --> 00:19:28,190
>> In particolare, ho intenzione di trattare
questo è A, poi B, poi C, poi D,

470
00:19:28,190 --> 00:19:29,310
questa qui.

471
00:19:29,310 --> 00:19:32,940
Quindi questo sta andando in modo efficace
rappresentare la lettera D.

472
00:19:32,940 --> 00:19:36,040
Ma per inserire tutti Daven di
nome che ho bisogno di fare un po 'di più.

473
00:19:36,040 --> 00:19:37,840
Così sto prima intenzione di hash, per così dire.

474
00:19:37,840 --> 00:19:41,049
Io vado a guardare la prima lettera
in Daven di che è ovviamente una D,

475
00:19:41,049 --> 00:19:42,840
e ho intenzione di allocare
un nodo che sembra

476
00:19:42,840 --> 00:19:45,570
Questa poi come un grande rettangolo grande
abbastanza da contenere l'intero alfabeto.

477
00:19:45,570 --> 00:19:47,140
>> Ora D è fatto.

478
00:19:47,140 --> 00:19:49,720
Ora A. D-A-V-E-N è l'obiettivo.

479
00:19:49,720 --> 00:19:51,220
Così ora che cosa ho intenzione di fare è questo.

480
00:19:51,220 --> 00:19:54,027
Non appena ho iniziato preavviso D
non c'è puntatore lì.

481
00:19:54,027 --> 00:19:56,860
Si tratta di valori di immondizia in questo momento,
o potrei inizializzarla a null.

482
00:19:56,860 --> 00:19:59,630
Ma mi permetta di andare avanti con
questa idea di costruire un albero.

483
00:19:59,630 --> 00:20:04,260
Mi permetta di allocare un altro uno di questi
nodi che ha 26 elementi in esso.

484
00:20:04,260 --> 00:20:05,150
>> E sai una cosa?

485
00:20:05,150 --> 00:20:09,130
Se questo è solo un nodo nella memoria
Ho creato con malloc, utilizzando una struct

486
00:20:09,130 --> 00:20:11,240
come vedremo tra poco,
Ho intenzione di fare questo--

487
00:20:11,240 --> 00:20:14,450
Ho intenzione di disegnare una freccia da
la cosa che rappresentava D verso il basso

488
00:20:14,450 --> 00:20:15,860
a questo nuovo nodo.

489
00:20:15,860 --> 00:20:19,240
E ora, in primo luogo il prossimo
lettera a nome di Daven,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- ho intenzione di andare avanti
e disegnare un altro nodo come questo,

491
00:20:24,150 --> 00:20:30,150
per cui, gli elementi di V qui, che
disegneremo per whoops instance--.

492
00:20:30,150 --> 00:20:31,020
Non disegnare lì.

493
00:20:31,020 --> 00:20:31,936
E 'intenzione di andare qui.

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

495
00:20:32,890 --> 00:20:35,712
>> Poi andremo a
ritiene che ciò sia V.

496
00:20:35,712 --> 00:20:44,920
E poi qui stiamo andando all'indice
giù da V in ciò che noi considereremo E.

497
00:20:44,920 --> 00:20:50,100
E poi da qui andremo a
andare avere uno di questi nodi qui.

498
00:20:50,100 --> 00:20:52,930
E ora abbiamo una domanda a cui rispondere.

499
00:20:52,930 --> 00:20:57,840
Ho bisogno di qualche modo indicare che
siamo alla fine della stringa Daven.

500
00:20:57,840 --> 00:20:59,490
Così ho potuto semplicemente lasciare nulla.

501
00:20:59,490 --> 00:21:02,670
>> Ma cosa succede se abbiamo Daven di
nome e cognome anche, che

502
00:21:02,670 --> 00:21:04,280
è, come abbiamo detto, Davenport?

503
00:21:04,280 --> 00:21:06,970
Che importa se è Daven
in realtà una sottostringa,

504
00:21:06,970 --> 00:21:08,960
un prefisso di una stringa molto più a lungo?

505
00:21:08,960 --> 00:21:11,450
Non possiamo solo in modo permanente
dire niente sta andando

506
00:21:11,450 --> 00:21:14,410
di andare lì, perché abbiamo potuto
non inserire mai una parola come Davenport

507
00:21:14,410 --> 00:21:15,840
in questa struttura dati

508
00:21:15,840 --> 00:21:19,560
>> Quindi quello che abbiamo potuto fare invece è
trattare ciascuno di questi elementi

509
00:21:19,560 --> 00:21:22,170
come forse avere due
elementi all'interno di essi.

510
00:21:22,170 --> 00:21:24,810
Uno è un puntatore, infatti,
come ho fatto.

511
00:21:24,810 --> 00:21:27,100
Così ognuno di queste caselle
non è solo una cellula.

512
00:21:27,100 --> 00:21:29,855
Ma cosa succede se la parte superiore
tra-- del quello inferiore

513
00:21:29,855 --> 00:21:32,230
sta per essere nullo, perché
c'è solo ancora Davenport.

514
00:21:32,230 --> 00:21:34,197
Che cosa succede se quella superiore
è un valore speciale?

515
00:21:34,197 --> 00:21:36,530
E sta andando ad essere un po '
difficile da elaborare in questo formato.

516
00:21:36,530 --> 00:21:38,130
Ma supponiamo che è solo un segno di spunta.

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

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N è una stringa
in questa struttura dati.

519
00:21:44,230 --> 00:21:48,350
>> Nel frattempo, se avessi più spazio
qui, ho potuto fare P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
e ho potuto mettere il check-in nel nodo
che ha la lettera T alla fine.

521
00:21:52,650 --> 00:21:55,460
Quindi questo è un massicciamente
complesso guardando struttura dati.

522
00:21:55,460 --> 00:21:57,210
E la mia scrittura a mano
di certo non aiuta.

523
00:21:57,210 --> 00:22:00,043
Ma se avessi voluto inserire qualcosa
altra cosa, consideriamo cosa avremmo fatto.

524
00:22:00,043 --> 00:22:03,370
Se volessimo mettere in David,
ci piacerebbe seguire la stessa logica, D-A-V,

525
00:22:03,370 --> 00:22:08,802
ma ora vorrei puntare nel prossimo
Elemento non da E, ma da I a D.

526
00:22:08,802 --> 00:22:10,760
Quindi ci sara '
più nodi in questo albero.

527
00:22:10,760 --> 00:22:12,325
Stiamo andando ad avere chiamata malloc più.

528
00:22:12,325 --> 00:22:14,700
Ma io non voglio fare una
completo disordine dell'immagine.

529
00:22:14,700 --> 00:22:17,710
Quindi diamo invece un'occhiata a uno
che è stato pre-formulato

530
00:22:17,710 --> 00:22:21,810
così con non dot, dot,
punti, ma gli array appena abbreviati.

531
00:22:21,810 --> 00:22:23,950
Ma ciascuno dei nodi
in questo albero qui

532
00:22:23,950 --> 00:22:26,700
rappresenta la stessa cosa--
una serie Ray di dimensioni 26.

533
00:22:26,700 --> 00:22:28,860
>> Oppure, se vogliamo essere
davvero corretto ora, cosa

534
00:22:28,860 --> 00:22:30,790
se il nome di qualcuno come
un apostrofo, cerchiamo di

535
00:22:30,790 --> 00:22:35,560
supporre che ciascun nodo ha effettivamente
come 27 indici in esso, non solo 26.

536
00:22:35,560 --> 00:22:42,020
Quindi questo ora sta per essere un dato
struttura chiamata trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
Un trie, che si suppone sia
storicamente un nome intelligente per un albero

538
00:22:46,120 --> 00:22:49,040
che è ottimizzato per
recupero, che naturalmente,

539
00:22:49,040 --> 00:22:50,870
è scritto con un I-E quindi è trie.

540
00:22:50,870 --> 00:22:52,710
Ma questa è la storia del trie.

541
00:22:52,710 --> 00:22:55,860
>> Quindi un trie è questi dati ad albero
struttura come un albero genealogico

542
00:22:55,860 --> 00:22:57,510
che si comporta in ultima analisi, come quella.

543
00:22:57,510 --> 00:23:00,890
E qui è solo un altro esempio di un
sacco di nomi di altre persone.

544
00:23:00,890 --> 00:23:03,540
Ma la questione ora
a portata di mano è quello che ha

545
00:23:03,540 --> 00:23:08,070
abbiamo ottenuto introducendo senza dubbio un più
struttura dati complessa, e uno,

546
00:23:08,070 --> 00:23:09,870
francamente, che utilizza molta memoria.

547
00:23:09,870 --> 00:23:11,703
>> Perché anche se,
in questo momento, io sono solo

548
00:23:11,703 --> 00:23:15,050
con puntatore D's e
A e V e Es e Ns,

549
00:23:15,050 --> 00:23:16,700
Sto sprecando un diavolo di molta memoria.

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

551
00:23:18,030 --> 00:23:22,660
Ma dove trascorro una risorsa,
Tendo a non ottenere indietro un altro.

552
00:23:22,660 --> 00:23:26,020
Quindi, se io sto spendendo più spazio,
ciò che è probabilmente la speranza?

553
00:23:26,020 --> 00:23:27,407
Che sto spendendo meno che cosa?

554
00:23:27,407 --> 00:23:28,240
PUBBLICO: Meno tempo.

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

556
00:23:28,990 --> 00:23:30,320
Ora, perché potrebbe essere?

557
00:23:30,320 --> 00:23:33,880
Ebbene, che cosa è l'inserimento
tempo, in termini di grande O ora,

558
00:23:33,880 --> 00:23:37,660
di un nome come Daven
o Davenport o David?

559
00:23:37,660 --> 00:23:39,340
Beh, Daven era cinque passi.

560
00:23:39,340 --> 00:23:42,350
Davenport sarebbe nove passi,
quindi sarebbe un altro paio di passi.

561
00:23:42,350 --> 00:23:44,250
David sarebbe cinque passi pure.

562
00:23:44,250 --> 00:23:47,230
Quindi questi sono di cemento
numeri, ma sicuramente non c'è

563
00:23:47,230 --> 00:23:49,550
un limite superiore sulla
lunghezza del nome di qualcuno.

564
00:23:49,550 --> 00:23:52,240
E infatti, nel problema
set di cinque specifiche,

565
00:23:52,240 --> 00:23:54,050
che andremo a proporre
che si tratta di qualcosa di

566
00:23:54,050 --> 00:23:55,470
questo è caratteri 40-qualche-dispari.

567
00:23:55,470 --> 00:23:58,180
>> Realisticamente, nessuno ha
un nome infinitamente lungo,

568
00:23:58,180 --> 00:24:01,542
vale a dire che la lunghezza di un
il nome o la lunghezza di una stringa potremmo

569
00:24:01,542 --> 00:24:03,750
hanno determinato lo stato di
la struttura è senza dubbio quello che?

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

571
00:24:05,550 --> 00:24:06,250
E 'costante.

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

573
00:24:06,430 --> 00:24:09,310
Potrebbe essere un grande costante come
40-qualcosa, ma è costante.

574
00:24:09,310 --> 00:24:13,752
E non ha alcuna dipendenza da quanti
altri nomi sono in questa struttura dati.

575
00:24:13,752 --> 00:24:15,460
In altre parole, se
voluto inserire ora

576
00:24:15,460 --> 00:24:20,540
Colton o Gabriel o Rob o Zamyla o
Alison o Belinda o qualsiasi altro nome

577
00:24:20,540 --> 00:24:23,940
dal personale in questi dati
struttura, è il tempo di esecuzione

578
00:24:23,940 --> 00:24:26,750
di inserimento di altri nomi
andando affatto impatto

579
00:24:26,750 --> 00:24:30,220
da come molti altri elementi sono
nella struttura dati già?

580
00:24:30,220 --> 00:24:31,040
Non è.

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

582
00:24:31,540 --> 00:24:36,150
Perché stiamo utilizzando in modo efficace
questa tabella hash multistrato.

583
00:24:36,150 --> 00:24:38,280
E il tempo di esecuzione di
una di queste operazioni

584
00:24:38,280 --> 00:24:41,510
non dipende dal numero di
elementi che sono nella struttura dati

585
00:24:41,510 --> 00:24:43,090
o che siano eventualmente andando
sia nella struttura dati,

586
00:24:43,090 --> 00:24:44,714
ma la lunghezza di quello specifico?

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

588
00:24:46,500 --> 00:24:49,200
>> La stringa essendo
inserito, che fa fare

589
00:24:49,200 --> 00:24:52,580
questo asintoticamente costante
tempo-- grande O di uno.

590
00:24:52,580 --> 00:24:54,720
E, francamente, proprio in
mondo reale, questo

591
00:24:54,720 --> 00:24:58,380
significa inserire il nome di Daven prende
come cinque passi, o Davenport nove

592
00:24:58,380 --> 00:25:00,100
passi, o David cinque passi.

593
00:25:00,100 --> 00:25:03,071
Questo è maledettamente piccoli tempi di esecuzione.

594
00:25:03,071 --> 00:25:05,320
E, in effetti, questo è un molto
buona cosa, soprattutto quando

595
00:25:05,320 --> 00:25:08,126
non è dipendente dal totale
numero di elementi in là.

596
00:25:08,126 --> 00:25:10,500
Così come si potrebbe implementare questa
tipo di struttura in codice?

597
00:25:10,500 --> 00:25:12,900
E 'un po' di più
complessa, ma comunque è

598
00:25:12,900 --> 00:25:15,050
semplice applicazione degli
elementi di base.

599
00:25:15,050 --> 00:25:17,830
Ho intenzione di ridefinire
nodo di noi nel modo seguente:

600
00:25:17,830 --> 00:25:21,100
bool chiamato word-- e questo
potrebbe essere chiamato nulla.

601
00:25:21,100 --> 00:25:23,970
Ma il bool rappresenta
quello che ho disegnato come un segno di spunta.

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

603
00:25:24,490 --> 00:25:26,720
Questa è la fine di una stringa
in questa struttura dati.

604
00:25:26,720 --> 00:25:30,702
>> E, naturalmente, la stella nodo
si fa riferimento ad i bambini.

605
00:25:30,702 --> 00:25:32,410
E, in effetti, proprio come
un albero genealogico, si

606
00:25:32,410 --> 00:25:34,370
prenderebbe in considerazione i nodi
che vengono appesi fuori

607
00:25:34,370 --> 00:25:36,920
del fondo di qualche genitore
Elemento di essere bambini.

608
00:25:36,920 --> 00:25:40,510
E così i bambini sta per
essere un array di 27, quella 27

609
00:25:40,510 --> 00:25:41,680
solo di essere per apostrofo.

610
00:25:41,680 --> 00:25:43,390
Stiamo andando a ordinare
di caso speciale che.

611
00:25:43,390 --> 00:25:45,400
Così si può avere certo
nomi con apostrofi.

612
00:25:45,400 --> 00:25:47,399
Forse anche trattino dovrebbe
andare in là, ma avrete

613
00:25:47,399 --> 00:25:50,330
vedi in p set 5 abbiamo solo la cura
su lettere e apostrofi.

614
00:25:50,330 --> 00:25:52,990
>> E allora come si fa a rappresentare
la struttura dati stessi?

615
00:25:52,990 --> 00:25:56,454
Come si fa a rappresentare la radice
questo trie, per così dire?

616
00:25:56,454 --> 00:25:59,620
Beh, proprio come con una lista collegata, è
serve un puntatore al primo elemento.

617
00:25:59,620 --> 00:26:04,270
Con un trie è sufficiente uno
puntatore alla radice di questo trie.

618
00:26:04,270 --> 00:26:07,290
E da lì si può hash
il vostro senso giù sempre più in profondità

619
00:26:07,290 --> 00:26:10,460
ad ogni altro nodo nella struttura.

620
00:26:10,460 --> 00:26:13,440
Quindi, semplicemente con questo can
noi rappresentiamo che struct.

621
00:26:13,440 --> 00:26:15,877
>> Ora Meanwhile-- Oh, domanda.

622
00:26:15,877 --> 00:26:17,220
>> PUBBLICO: Che cosa è la parola bool?

623
00:26:17,220 --> 00:26:20,490
>> DAVID MALAN: parola di Bool è
proprio questa incarnazione C

624
00:26:20,490 --> 00:26:22,920
di quello che ho descritto
in questa casella qui, quando

625
00:26:22,920 --> 00:26:26,000
Ho iniziato dividere ciascuno degli
elementi di array in due pezzi.

626
00:26:26,000 --> 00:26:27,600
Uno è un puntatore al nodo successivo.

627
00:26:27,600 --> 00:26:30,280
L'altro deve essere
qualcosa di simile a una casella di controllo

628
00:26:30,280 --> 00:26:33,770
a dire di sì, c'è un
parola Daven che finisce qui,

629
00:26:33,770 --> 00:26:35,610
perché non vogliamo,
Al momento, Dave.

630
00:26:35,610 --> 00:26:39,320
>> Anche se Dave sta per essere un
legittimo parola, che non è nel trie

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

632
00:26:39,830 --> 00:26:40,950
E D non è una parola.

633
00:26:40,950 --> 00:26:42,770
E D-A non è una parola o un nome.

634
00:26:42,770 --> 00:26:45,020
Così il segno di spunta
indica solo una volta che si

635
00:26:45,020 --> 00:26:48,190
ha colpito questo nodo è il
precedente percorso di personaggi

636
00:26:48,190 --> 00:26:50,700
in realtà una stringa che hai inserito.

637
00:26:50,700 --> 00:26:53,660
Ecco, questo è tutto il bool
si sta facendo per noi.

638
00:26:53,660 --> 00:26:55,500
>> Tutte le altre domande sui tentativi?

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

640
00:26:56,215 --> 00:26:58,035
>> PUBBLICO: Qual è la sovrapposizione?

641
00:26:58,035 --> 00:26:59,945
Che cosa succede se si dispone di un Dave e un Daven?

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

643
00:27:00,820 --> 00:27:02,580
Che cosa succede se si dispone di un Dave e un Daven?

644
00:27:02,580 --> 00:27:06,240
Quindi, se inseriamo, dire un soprannome,
per David-- Dave-- D-A-V-E?

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

646
00:27:07,370 --> 00:27:08,700
Questo in realtà è super semplice.

647
00:27:08,700 --> 00:27:10,325
Quindi stiamo solo andando a prendere quattro passi.

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

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. E che cosa devo
fare una volta mi ha colpito che il quarto nodo?

650
00:27:15,847 --> 00:27:16,680
Basta andare a controllare.

651
00:27:16,680 --> 00:27:18,000
Siamo già a posto.

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

653
00:27:18,840 --> 00:27:19,750
Quattro passi.

654
00:27:19,750 --> 00:27:21,590
Costante di tempo asintoticamente.

655
00:27:21,590 --> 00:27:26,300
E ora abbiamo indicato che sia Dave
e Daven sono stringhe nella struttura.

656
00:27:26,300 --> 00:27:27,710
Quindi non è un problema.

657
00:27:27,710 --> 00:27:30,200
E notare come la presenza
di Daven non ha fatto che

658
00:27:30,200 --> 00:27:34,750
prendere altro tempo o meno
tempo per Dave e viceversa.

659
00:27:34,750 --> 00:27:36,000
>> Quindi, che cosa possiamo fare ora?

660
00:27:36,000 --> 00:27:40,680
Abbiamo utilizzato questa metafora prima
di vassoi che rappresenta qualcosa.

661
00:27:40,680 --> 00:27:43,380
Ma si scopre che un
pila di vassoi è effettivamente

662
00:27:43,380 --> 00:27:47,187
dimostrativo di un altro dato astratto
type-- una struttura di dati di livello superiore

663
00:27:47,187 --> 00:27:49,770
che alla fine della giornata è solo
come un array o una lista concatenata

664
00:27:49,770 --> 00:27:50,970
o qualcosa di più banale.

665
00:27:50,970 --> 00:27:53,270
Ma è un più interessante
concetto concettuale.

666
00:27:53,270 --> 00:27:56,440
Una pila, come questi
vassoi qui a Mather,

667
00:27:56,440 --> 00:27:58,750
sono generalmente chiamati
solo che-- una pila.

668
00:27:58,750 --> 00:28:02,540
>> E in questo tipo di struttura dati
si hanno due operations--

669
00:28:02,540 --> 00:28:05,880
si dispone di uno chiamato spinta per
aggiungendo qualcosa alla pila,

670
00:28:05,880 --> 00:28:08,320
come mettere un altro vassoio
eseguire in cima alla pila.

671
00:28:08,320 --> 00:28:11,350
E poi pop, che significa
prendere il più in alto cassetto off.

672
00:28:11,350 --> 00:28:16,210
Ma cosa c'è di chiave su una pila è che
è ottenuto questa curiosa caratteristica.

673
00:28:16,210 --> 00:28:19,560
Mentre il personale di sala da pranzo sono
riorganizzare i vassoi per il pasto successivo,

674
00:28:19,560 --> 00:28:21,380
cosa sarà
vero circa come gli studenti

675
00:28:21,380 --> 00:28:22,856
Interazioni struttura dati?

676
00:28:22,856 --> 00:28:24,480
PUBBLICO: Stanno andando al pop una tantum.

677
00:28:24,480 --> 00:28:26,550
DAVID MALAN: Stanno andando a
pop una tantum, si spera la parte superiore.

678
00:28:26,550 --> 00:28:28,910
In caso contrario, è solo un po 'stupido
per andare fino al fondo.

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

680
00:28:29,070 --> 00:28:31,620
La struttura dei dati in realtà non permette
di afferrare il vassoio inferiore almeno

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

682
00:28:32,520 --> 00:28:35,040
Quindi c'è questo curioso
proprietà su una pila

683
00:28:35,040 --> 00:28:39,730
che l'ultimo elemento è
sarà il primo ad uscire.

684
00:28:39,730 --> 00:28:43,400
E gli informatici chiamano
questo LIFO-- last in, first out.

685
00:28:43,400 --> 00:28:45,540
E che ha realmente
interessanti applicazioni.

686
00:28:45,540 --> 00:28:50,090
Non è necessariamente così evidente come alcuni
altri, ma può, infatti, essere utile,

687
00:28:50,090 --> 00:28:54,040
e può, infatti, essere attuato
in un paio di modi diversi.

688
00:28:54,040 --> 00:28:58,550
>> Così uno, e in realtà, lasciate
me, non a tuffarsi in quella.

689
00:28:58,550 --> 00:28:59,860
Facciamo così, invece.

690
00:28:59,860 --> 00:29:03,700
Diamo un'occhiata a quello che è quasi il
stessa idea, ma è un po 'più giusto.

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

692
00:29:04,200 --> 00:29:07,560
Se siete uno di questi ragazzi fan o
ragazze che ama davvero i prodotti Apple

693
00:29:07,560 --> 00:29:10,130
e ti sei svegliato alle 3:00 AM
a schierarsi in qualche negozio

694
00:29:10,130 --> 00:29:14,150
per ottenere le più recenti iPhone, si
avrebbe potuto in coda in questo modo.

695
00:29:14,150 --> 00:29:15,800
>> Ora una coda è molto deliberatamente nome.

696
00:29:15,800 --> 00:29:18,190
E 'una linea perché c'è
un po 'di equità ad esso.

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

698
00:29:18,690 --> 00:29:21,690
Sarebbe tipo di risucchiato se avete
arrivati ​​prima presso l'Apple Store

699
00:29:21,690 --> 00:29:25,700
ma si sta effettivamente il più in basso
cassetto perché i dipendenti Apple poi

700
00:29:25,700 --> 00:29:28,189
pop l'ultima persona che
in realtà ha ottenuto in linea.

701
00:29:28,189 --> 00:29:31,230
Quindi, pile e code, ancorché
funzionalmente sono tipo di stesso--

702
00:29:31,230 --> 00:29:33,105
è solo questa collezione
delle risorse che è

703
00:29:33,105 --> 00:29:36,210
andando a crescere e shrink-- c'è
questo aspetto dell'equità ad esso,

704
00:29:36,210 --> 00:29:39,634
almeno nel mondo reale,
dove le operazioni che esercitano

705
00:29:39,634 --> 00:29:40,800
sono fondamentalmente diversi.

706
00:29:40,800 --> 00:29:43,360
Un stack-- una coda
rather-- si dice che abbia

707
00:29:43,360 --> 00:29:45,320
due operazioni: n coda e coda d.

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

709
00:29:46,341 --> 00:29:48,090
Oppure è possibile chiamare
qualsiasi numero di cose.

710
00:29:48,090 --> 00:29:50,770
Ma vuoi solo catturare
l'idea che si sta aggiungendo

711
00:29:50,770 --> 00:29:53,230
e si è in ultima analisi, sottraendo.

712
00:29:53,230 --> 00:29:58,840
>> Ora sotto la cappa, sia lo stack
e una coda può essere implementato come?

713
00:29:58,840 --> 00:30:01,390
Non entreremo nel codice di
perché il livello superiore

714
00:30:01,390 --> 00:30:03,387
idea è una sorta di più evidente.

715
00:30:03,387 --> 00:30:04,470
Voglio dire, che cosa fanno gli esseri umani?

716
00:30:04,470 --> 00:30:07,030
Se io sono la prima persona al di Apple
Conservare e questa è la porta d'ingresso,

717
00:30:07,030 --> 00:30:08,130
sai, ho intenzione di stare qui.

718
00:30:08,130 --> 00:30:09,750
E la prossima persona
andando a stare qui.

719
00:30:09,750 --> 00:30:11,500
E la prossima persona
andando a stare qui.

720
00:30:11,500 --> 00:30:13,792
Quindi, quale struttura dati
si presta a una coda?

721
00:30:13,792 --> 00:30:14,542
>> PUBBLICO: Una coda.

722
00:30:14,542 --> 00:30:15,667
DAVID MALAN: Beh, una coda.

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

724
00:30:16,390 --> 00:30:16,920
Cos'altro?

725
00:30:16,920 --> 00:30:17,600
>> PUBBLICO: Una lista concatenata.

726
00:30:17,600 --> 00:30:18,990
>> DAVID MALAN: una legata
l'elenco che si potrebbe implementare.

727
00:30:18,990 --> 00:30:22,500
E una lista collegata è bello perché poi
può crescere arbitrariamente lungo rispetto

728
00:30:22,500 --> 00:30:24,880
di avere un numero fisso
di persone nel negozio.

729
00:30:24,880 --> 00:30:27,030
Ma forse un numero fisso
di posti è legittimo.

730
00:30:27,030 --> 00:30:30,350
Perché se hanno solo come 20
iPhone il primo giorno, forse

731
00:30:30,350 --> 00:30:33,930
hanno solo bisogno di un array di dimensione
20 per rappresentare quella coda, che

732
00:30:33,930 --> 00:30:37,070
è solo per dire ora una volta che si comincia a parlare
su questi problemi di livello superiore,

733
00:30:37,070 --> 00:30:38,890
è possibile implementare
in qualsiasi numero di modi.

734
00:30:38,890 --> 00:30:42,030
E c'è probabilmente solo andando a
essere un compromesso nello spazio e nel tempo

735
00:30:42,030 --> 00:30:43,950
o semplicemente nel proprio la complessità del codice.

736
00:30:43,950 --> 00:30:45,380
>> Che dire di una pila?

737
00:30:45,380 --> 00:30:48,190
Beh, una pila, abbiamo visto anche
potrebbe essere solo questi vassoi.

738
00:30:48,190 --> 00:30:50,007
E si potrebbe implementare questa una matrice.

739
00:30:50,007 --> 00:30:53,090
Ma ad un certo punto se si utilizza una matrice,
cosa succederà ai vassoi

740
00:30:53,090 --> 00:30:54,173
si sta cercando di mettere giù?

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

742
00:30:55,170 --> 00:30:55,670
Bene.

743
00:30:55,670 --> 00:30:57,490
Stai andando solo a
essere in grado di andare così in alto.

744
00:30:57,490 --> 00:31:00,156
E penso che in Mather sono
effettivamente incassata in tale apertura.

745
00:31:00,156 --> 00:31:01,950
Così in effetti, è quasi
come Mather sta usando

746
00:31:01,950 --> 00:31:03,783
un array di dimensioni fisse,
perché è solo possibile

747
00:31:03,783 --> 00:31:08,302
inserire tanti vassoi in quella apertura in
il muro verso il basso sotto le ginocchia della gente.

748
00:31:08,302 --> 00:31:10,010
E così che potrebbe essere
ha detto di essere un array,

749
00:31:10,010 --> 00:31:14,300
ma potremmo certamente attuare tale
più in generale, con una lista collegata.

750
00:31:14,300 --> 00:31:16,390
>> Beh, che dire un'altra struttura dati?

751
00:31:16,390 --> 00:31:18,760
Permettetemi di tirare su un altro visiva qui.

752
00:31:18,760 --> 00:31:24,710
Qualcosa di simile che ne dici di questo qui?

753
00:31:24,710 --> 00:31:28,920
Perché potrebbe essere utile per non avere
qualcosa di sofisticato come un trie, che

754
00:31:28,920 --> 00:31:32,370
abbiamo visto avuto questi molto larghi nodi,
ciascuno dei quali è in un array?

755
00:31:32,370 --> 00:31:35,740
Ma cosa succede se facciamo qualcosa di più
semplicemente, come un vecchio albero di famiglia la scuola,

756
00:31:35,740 --> 00:31:38,110
ciascuno di cui nodi qui
è solo memorizzazione di un numero.

757
00:31:38,110 --> 00:31:42,180
Invece di un nome o discendente
è solo la memorizzazione di un numero come questo.

758
00:31:42,180 --> 00:31:45,250
>> Beh, il gergo usiamo in
strutture di dati è entrambe le mete

759
00:31:45,250 --> 00:31:49,510
e alberi, dove un trie, di nuovo, è
solo uno i cui nodi sono array,

760
00:31:49,510 --> 00:31:51,680
è ancora quello che si potrebbe
utilizzare dalla scuola elementare

761
00:31:51,680 --> 00:31:53,860
quando hai fatto una famiglia
tree-- foglie e la radice

762
00:31:53,860 --> 00:31:57,250
dell'albero e figli del
genitori e fratelli loro.

763
00:31:57,250 --> 00:32:03,670
E potremmo implementare un albero,
per esempio, nel modo più semplice questo.

764
00:32:03,670 --> 00:32:07,420
Un albero, se come un nodo, uno dei
questi cerchi che ha un numero,

765
00:32:07,420 --> 00:32:09,947
non sta andando ad avere
un puntatore, ma due.

766
00:32:09,947 --> 00:32:11,780
E non appena si aggiunge
un secondo puntatore, è

767
00:32:11,780 --> 00:32:13,905
può effettivamente ora fare tipo
dei dati bidimensionali

768
00:32:13,905 --> 00:32:14,780
strutture in memoria.

769
00:32:14,780 --> 00:32:16,660
Proprio come un bidimensionale
array, è possibile

770
00:32:16,660 --> 00:32:18,904
avere tipo bidimensionale
liste collegate, ma quelli

771
00:32:18,904 --> 00:32:20,820
che seguono un pattern
dove non ci sono cicli.

772
00:32:20,820 --> 00:32:24,487
E 'veramente un albero con una
modo nonni qui e poi

773
00:32:24,487 --> 00:32:27,320
alcuni genitori e figli e
nipoti e pronipoti.

774
00:32:27,320 --> 00:32:28,370
e così via.

775
00:32:28,370 --> 00:32:32,390
>> Ma ciò che è veramente pulito anche su questo,
solo per prendere in giro voi con un po 'di codice,

776
00:32:32,390 --> 00:32:35,370
richiamo ricorsione da
un po 'indietro, per cui

777
00:32:35,370 --> 00:32:38,220
si scrive una funzione che chiama se stessa.

778
00:32:38,220 --> 00:32:41,140
Questa è una bella opportunità
di implementare qualcosa

779
00:32:41,140 --> 00:32:42,920
come ricorsione, perché considerano questo.

780
00:32:42,920 --> 00:32:43,860
>> Questo è un albero.

781
00:32:43,860 --> 00:32:48,040
E io sono stato un po 'anale con il modo
Ho messo i numeri interi in mezzo alla strada.

782
00:32:48,040 --> 00:32:51,020
Tanto che ha una speciale
nome-- un albero binario di ricerca.

783
00:32:51,020 --> 00:32:53,460
Ora abbiamo sentito di binario
la ricerca, ma anche voi

784
00:32:53,460 --> 00:32:55,180
lavorare a ritroso dal nome di questa cosa?

785
00:32:55,180 --> 00:32:59,280
Qual è il modello di come ho
inserite i numeri interi in questo albero?

786
00:32:59,280 --> 00:33:00,696
Non è arbitrario.

787
00:33:00,696 --> 00:33:01,570
C'è qualche modello.

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

789
00:33:02,090 --> 00:33:03,370
>> PUBBLICO: quelli più piccoli a sinistra.

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

791
00:33:03,690 --> 00:33:05,062
Quelli più piccoli sono a sinistra.

792
00:33:05,062 --> 00:33:06,270
Quelli più grandi sono sulla destra.

793
00:33:06,270 --> 00:33:12,940
Tale che un'affermazione vera è un
genitore è maggiore del suo figlio sinistro,

794
00:33:12,940 --> 00:33:14,850
ma inferiore al suo figlio destro.

795
00:33:14,850 --> 00:33:17,750
E che da solo è ancora un
definizione verbale ricorsiva

796
00:33:17,750 --> 00:33:20,500
perché si può applicare tale
stessa logica ad ogni nodo

797
00:33:20,500 --> 00:33:23,080
e solo in battuta
fuori, un caso base, se si

798
00:33:23,080 --> 00:33:25,740
sarà, quando si preme uno dei
le foglie, per così dire,

799
00:33:25,740 --> 00:33:28,580
dove un congedo non ha più figli.

800
00:33:28,580 --> 00:33:30,614
>> Ora, come si potrebbe trovare il numero 44?

801
00:33:30,614 --> 00:33:32,280
Si potrebbe iniziare alla radice e dire, hm.

802
00:33:32,280 --> 00:33:35,690
55 non è 44 Quindi voglio andare
giusto fare o voglio andare a sinistra?

803
00:33:35,690 --> 00:33:37,190
Beh, ovviamente si vuole andare a sinistra.

804
00:33:37,190 --> 00:33:40,060
E così è proprio come il telefono
libro esempio in ricerca binaria

805
00:33:40,060 --> 00:33:41,099
più in generale.

806
00:33:41,099 --> 00:33:43,390
Ma stiamo attuazione
ora un po 'più dinamico

807
00:33:43,390 --> 00:33:45,339
di un array potrebbe consentire.

808
00:33:45,339 --> 00:33:48,130
E infatti, se si vuole guardare
il codice, a prima vista sicuro.

809
00:33:48,130 --> 00:33:49,671
Si presenta come un insieme di linee.

810
00:33:49,671 --> 00:33:51,220
Ma è meravigliosamente semplice.

811
00:33:51,220 --> 00:33:54,490
Se si desidera implementare una funzione
chiamata di ricerca il cui scopo nella vita

812
00:33:54,490 --> 00:33:57,290
è quello di cercare un valore
come n, un numero intero,

813
00:33:57,290 --> 00:34:01,756
e il gioco è passato in uno pointer--
un puntatore al nodo delle radici,

814
00:34:01,756 --> 00:34:04,380
piuttosto, di detto albero da cui
è possibile accedere a tutto il resto,

815
00:34:04,380 --> 00:34:08,850
notare come semplicemente
è possibile implementare la logica.

816
00:34:08,850 --> 00:34:10,880
Se l'albero è nullo,
ovviamente non c'è.

817
00:34:10,880 --> 00:34:11,880
Diciamo solo return false.

818
00:34:11,880 --> 00:34:12,000
Giusto?

819
00:34:12,000 --> 00:34:14,040
Se si passi nulla,
non c'è niente lì.

820
00:34:14,040 --> 00:34:17,900
>> Altrimenti, se n è minore di
albero freccia n-- ora freccia n,

821
00:34:17,900 --> 00:34:20,670
Ricordiamo abbiamo introdotto eccellente
brevemente l'altro giorno,

822
00:34:20,670 --> 00:34:25,100
e questo significa solo de-riferimento
puntatore e guardare il campo denominato n.

823
00:34:25,100 --> 00:34:27,690
Quindi vuol dire andare lì e
guardare il campo denominato n.

824
00:34:27,690 --> 00:34:33,810
Quindi, se n, il valore si è dato, è meno
al valore in intero alberi,

825
00:34:33,810 --> 00:34:35,449
dove vuoi andare?

826
00:34:35,449 --> 00:34:36,389
A sinistra.

827
00:34:36,389 --> 00:34:37,780
>> Così notare la ricorsione.

828
00:34:37,780 --> 00:34:39,860
Sto returning-- non è vero.

829
00:34:39,860 --> 00:34:40,989
Non falso.

830
00:34:40,989 --> 00:34:45,670
Sto tornando qualunque sia la risposta
è da una chiamata a me stesso, passando

831
00:34:45,670 --> 00:34:50,100
nuovo un n, che è ridondante,
ma ciò che è un po 'diverso ora?

832
00:34:50,100 --> 00:34:51,989
Come sto facendo il problema più piccolo?

833
00:34:51,989 --> 00:34:54,920
Sto passando come secondo
argomento, non la radice dell'albero,

834
00:34:54,920 --> 00:34:59,616
ma il figlio sinistro in questo caso.

835
00:34:59,616 --> 00:35:00,990
Così sto passando il figlio sinistro.

836
00:35:00,990 --> 00:35:04,720
>> Nel frattempo, se n è maggiore di
il nodo Attualmente sto guardando,

837
00:35:04,720 --> 00:35:06,690
Cerco il lato destro della strada.

838
00:35:06,690 --> 00:35:10,880
Altrimenti, se l'albero non è nullo, e
se l'elemento non è a fianco

839
00:35:10,880 --> 00:35:13,240
e non è a destra,
ciò che è meravigliosamente il caso?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Abbiamo davvero trovato il nodo
domanda, e così torniamo vero.

842
00:35:18,440 --> 00:35:21,490
>> Quindi, abbiamo appena scalfito la superficie
Ora alcune di queste strutture di dati.

843
00:35:21,490 --> 00:35:24,370
Nel problema ha impostato cinque avrete
esplorare questi ulteriormente,

844
00:35:24,370 --> 00:35:27,250
e ti verrà dato il vostro disegno
scelta di come fare per questo.

845
00:35:27,250 --> 00:35:30,250
Quello che mi piacerebbe concludere il
è solo un secondo teaser di 30

846
00:35:30,250 --> 00:35:32,080
di ciò che attende la prossima settimana e oltre.

847
00:35:32,080 --> 00:35:35,390
>> Come abbiamo begin-- per fortuna si potrebbe
think-- nostra transizione lentamente

848
00:35:35,390 --> 00:35:38,680
dal mondo di C e inferiori
dettagli di implementazione di livello,

849
00:35:38,680 --> 00:35:42,090
a un mondo in cui possiamo dare per
scontato che qualcun altro ha, infine,

850
00:35:42,090 --> 00:35:44,010
implementato questi dati
strutture per noi,

851
00:35:44,010 --> 00:35:47,570
e inizieremo a capire la
mondo reale mezzo di attuazione

852
00:35:47,570 --> 00:35:50,560
programmi web-based e
i siti web più in generale

853
00:35:50,560 --> 00:35:52,910
ed anche la stessa sicurezza
implicazioni che abbiamo solo

854
00:35:52,910 --> 00:35:54,850
cominciato a graffiare la superficie del.

855
00:35:54,850 --> 00:35:57,320
Ecco cosa ci aspetta
nei giorni a venire.

856
00:35:57,320 --> 00:36:00,480
>> [RIPRODUZIONE VIDEO]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -Ha È venuto con un messaggio,
con un protocollo tutto suo.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Egli è venuto per un mondo di crudele
firewall, router indifferente,

861
00:36:30,894 --> 00:36:33,368
e pericoli di gran lunga peggiore della morte.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
E 'veloce.

864
00:36:36,236 --> 00:36:37,980
Lui è forte.

865
00:36:37,980 --> 00:36:42,830
E 'il protocollo TCP / IP, e lui ha il vostro indirizzo.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Guerrieri della Rete."

868
00:36:48,074 --> 00:36:49,660
[FINE RIPRODUZIONE VIDEO]

869
00:36:49,660 --> 00:36:50,910
DAVID MALAN: Settimana prossima.

870
00:36:50,910 --> 00:36:51,880
Vedremo allora.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[RIPRODUZIONE VIDEO]

873
00:36:56,060 --> 00:36:59,240
-E Ora, "Pensieri profondi"
da Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Inizia sempre
conferenze con: "Va bene."

876
00:37:05,820 --> 00:37:08,750
Perché no, "Ecco la soluzione
al problema di set di questa settimana "

877
00:37:08,750 --> 00:37:12,180
o "Stiamo dando a tutti voi un A?"

878
00:37:12,180 --> 00:37:13,380
[Ride]

879
00:37:13,380 --> 00:37:15,530
[FINE RIPRODUZIONE VIDEO]