1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> KEVIN SCHMID: A volte, quando si costruisce una
programma, si potrebbe desiderare di utilizzare un

3
00:00:10,890 --> 00:00:13,190
struttura di dati nota come un dizionario.

4
00:00:13,190 --> 00:00:17,960
A mappe Dizionario chiavi, che sono
di solito stringhe, ai valori, int,

5
00:00:17,960 --> 00:00:21,900
caratteri, un puntatore ad un oggetto,
quello che vogliamo.

6
00:00:21,900 --> 00:00:26,510
E 'proprio come dizionari ordinarie
che sugli parole attraverso definizioni.

7
00:00:26,510 --> 00:00:29,440
>> Dizionari ci forniscono l'
capacità di immagazzinare informazioni

8
00:00:29,440 --> 00:00:32,750
associato a qualcosa
e guardare più tardi.

9
00:00:32,750 --> 00:00:36,620
Quindi, come possiamo realmente attuare una
dizionario, per esempio, il codice C che possiamo

10
00:00:36,620 --> 00:00:38,460
utilizzare in uno dei nostri programmi?

11
00:00:38,460 --> 00:00:41,790
Ebbene, ci sono molti modi in cui
potremmo implementare un dizionario.

12
00:00:41,790 --> 00:00:45,930
>> Per uno, potremmo utilizzare un array che
dinamicamente ridimensionare o potremmo usare un

13
00:00:45,930 --> 00:00:49,150
lista collegata, tabella hash
o un albero binario.

14
00:00:49,150 --> 00:00:52,250
Ma qualsiasi cosa scegliamo, dobbiamo
essere consapevoli della efficienza e

15
00:00:52,250 --> 00:00:54,300
prestazioni dell'implementazione.

16
00:00:54,300 --> 00:00:57,930
Dovremmo pensare l'algoritmo usato
di inserire e ricercare elementi in

17
00:00:57,930 --> 00:00:59,120
la nostra struttura dati.

18
00:00:59,120 --> 00:01:03,060
>> Per ora, supponiamo che ci
voler usare le stringhe come chiavi.

19
00:01:03,060 --> 00:01:07,290
Parliamo di una possibilità,
una struttura di dati chiamata trie.

20
00:01:07,290 --> 00:01:11,210
Quindi, ecco una rappresentazione visiva
di un trie.

21
00:01:11,210 --> 00:01:14,590
>> Come l'immagine suggerisce, un trie
è una struttura di dati ad albero con

22
00:01:14,590 --> 00:01:16,050
nodi collegati tra loro.

23
00:01:16,050 --> 00:01:19,420
Vediamo che c'è chiaramente una radice
nodo con alcuni link che estende alla

24
00:01:19,420 --> 00:01:20,500
altri nodi.

25
00:01:20,500 --> 00:01:23,040
Ma cosa significa ogni nodo consiste?

26
00:01:23,040 --> 00:01:26,700
Se assumiamo che stiamo memorizzazione delle chiavi
con soli caratteri alfabetici e

27
00:01:26,700 --> 00:01:30,150
non ci preoccupiamo di capitalizzazione,
ecco una definizione di un nodo che

28
00:01:30,150 --> 00:01:31,100
sarà sufficiente.

29
00:01:31,100 --> 00:01:34,130
>> Un oggetto il cui tipo è struct
nodo ha due parti

30
00:01:34,130 --> 00:01:35,740
chiamata dati e bambini.

31
00:01:35,740 --> 00:01:39,200
Abbiamo lasciato la parte di dati come un commento
per essere sostituito da un componente

32
00:01:39,200 --> 00:01:43,190
dichiarazione quando il nodo è struct
incorporata in un programma C.

33
00:01:43,190 --> 00:01:47,040
La parte di dati di un nodo può essere un
Valore booleano per indicare se

34
00:01:47,040 --> 00:01:51,160
non il nodo rappresenta il completamento
di una chiave di dizionario o potrebbe essere un

35
00:01:51,160 --> 00:01:54,240
stringa che rappresenta la definizione
di una parola nel dizionario.

36
00:01:54,240 --> 00:01:58,870
>> Useremo una faccina sorridente per indicare
quando è presente in un nodo di dati.

37
00:01:58,870 --> 00:02:02,310
Ci sono 26 elementi nella nostra
matrice bambini, un indice

38
00:02:02,310 --> 00:02:03,690
per carattere alfabetico.

39
00:02:03,690 --> 00:02:06,570
Vedremo il significato
di questo presto.

40
00:02:06,570 --> 00:02:10,759
>> Prendiamo uno sguardo più da vicino del nodo radice
nel nostro schema, che non ha dati

41
00:02:10,759 --> 00:02:14,740
ad esso associati, come indicato dal
assenza della faccina sorridente nel

42
00:02:14,740 --> 00:02:16,110
porzione di dati.

43
00:02:16,110 --> 00:02:19,910
Le frecce che si estendono dalle parti di
la matrice bambini rappresentano non-node

44
00:02:19,910 --> 00:02:21,640
puntatori ad altri nodi.

45
00:02:21,640 --> 00:02:25,500
Ad esempio, la freccia estende dal
il secondo elemento di bambini

46
00:02:25,500 --> 00:02:28,400
rappresenta la lettera B
in una chiave di dizionario.

47
00:02:28,400 --> 00:02:31,920
E nello schema più grande
etichettiamo con una B.

48
00:02:31,920 --> 00:02:35,810
>> Si noti che nello schema più grande, quando abbiamo
disegnare un puntatore ad un altro nodo, esso

49
00:02:35,810 --> 00:02:39,100
Non importa se la punta della freccia
risponda a tale nodo.

50
00:02:39,100 --> 00:02:43,850
Il nostro trie Dizionario campione contiene
due parole, che e zoom.

51
00:02:43,850 --> 00:02:47,040
Camminiamo attraverso un esempio di
cerca i dati per una chiave.

52
00:02:47,040 --> 00:02:50,800
>> Supponiamo di voler cercare l'
valore corrispondente per il bagno chiave.

53
00:02:50,800 --> 00:02:53,610
Inizieremo il nostro sguardo su
al nodo radice.

54
00:02:53,610 --> 00:02:57,870
Poi ci prenderemo la prima lettera del nostro
chiave, B, e trovare il corrispondente

55
00:02:57,870 --> 00:03:00,020
posto nella nostra matrice bambini.

56
00:03:00,020 --> 00:03:04,490
Si noti che ci sono esattamente 26 punti
nella matrice, una per ogni lettera

57
00:03:04,490 --> 00:03:05,330
l'alfabeto.

58
00:03:05,330 --> 00:03:08,800
E avremo i punti rappresentano il
lettere dell'alfabeto in ordine.

59
00:03:08,800 --> 00:03:13,960
>> Vedremo il secondo indice, allora,
indice uno, per B. In generale, se

60
00:03:13,960 --> 00:03:17,990
avere qualche alfabetico carattere C che
potrebbe determinare il punto corrispondente

61
00:03:17,990 --> 00:03:21,520
nella matrice dei minori che usano
un calcolo come questo.

62
00:03:21,520 --> 00:03:25,140
Abbiamo potuto utilizzare per bambini più grandi
array se abbiamo voluto offrire sguardo di

63
00:03:25,140 --> 00:03:28,380
tasti con una vasta gamma di personaggi,
ad esempio l'intera

64
00:03:28,380 --> 00:03:29,880
Set di caratteri ASCII.

65
00:03:29,880 --> 00:03:32,630
>> In questo caso, il puntatore
nei nostri bambini array

66
00:03:32,630 --> 00:03:34,320
indice non è nullo.

67
00:03:34,320 --> 00:03:36,600
Quindi noi continueremo cercando
la vasca chiave.

68
00:03:36,600 --> 00:03:40,130
Se mai incontrato un puntatore nullo
nel punto corretto nei bambini

69
00:03:40,130 --> 00:03:43,230
matrice mentre abbiamo attraversato i nodi,
allora dovremo dire che abbiamo

70
00:03:43,230 --> 00:03:45,630
non riusciva a trovare nulla per quella chiave.

71
00:03:45,630 --> 00:03:49,370
>> Ora, prendiamo la seconda lettera di
la nostra chiave, A, e continuare a seguire

72
00:03:49,370 --> 00:03:52,400
puntatori in questo modo fino a noi
raggiungere la fine della nostra chiave.

73
00:03:52,400 --> 00:03:56,530
Se arriviamo alla fine della chiave senza
colpire gli vicoli ciechi, puntatori nulli,

74
00:03:56,530 --> 00:03:59,730
come è il caso qui, allora abbiamo solo
deve controllare una cosa.

75
00:03:59,730 --> 00:04:02,110
È questo tasto realtà
nel dizionario?

76
00:04:02,110 --> 00:04:07,660
>> Se è così, dovremmo trovare un valore, un bene
smiley Icona volto nel nostro diagramma in cui

77
00:04:07,660 --> 00:04:08,750
la parola finisce.

78
00:04:08,750 --> 00:04:12,270
Se c'è qualcos'altro memorizzato con
i dati, quindi siamo in grado di restituirlo.

79
00:04:12,270 --> 00:04:16,500
Ad esempio, lo zoo chiave non è nella
dizionario, anche se potremmo avere

80
00:04:16,500 --> 00:04:19,810
raggiunto la fine di questa chiave senza mai
colpire un puntatore nullo, mentre noi

81
00:04:19,810 --> 00:04:21,089
scorrere l'trie.

82
00:04:21,089 --> 00:04:25,436
>> Se abbiamo provato a cercare il bagno tasto, il
secondo per indice di matrice di ultimo nodo,

83
00:04:25,436 --> 00:04:28,750
corrispondente alla lettera H, sarebbe
hanno tenuto un puntatore nullo.

84
00:04:28,750 --> 00:04:31,120
Quindi il bagno non è presente nel dizionario.

85
00:04:31,120 --> 00:04:34,800
E così un trie è unico in quanto le chiavi
vengono mai esplicitamente memorizzati in

86
00:04:34,800 --> 00:04:36,650
la struttura di dati.

87
00:04:36,650 --> 00:04:38,810
Quindi, come possiamo inseriamo qualcosa
in un trie?

88
00:04:38,810 --> 00:04:41,780
>> Inseriamo la chiave
zoo nel nostro trie.

89
00:04:41,780 --> 00:04:46,120
Ricordate che una faccina sorridente in un nodo
potrebbe corrispondere in codice per un semplice

90
00:04:46,120 --> 00:04:50,170
Valore booleano per indicare che zoo
è nel dizionario o potrebbe

91
00:04:50,170 --> 00:04:53,710
corrispondono a maggiori informazioni che abbiamo
desidera associare con lo zoo chiave,

92
00:04:53,710 --> 00:04:56,860
come la definizione del
parola o qualcos'altro.

93
00:04:56,860 --> 00:05:00,350
In qualche modo, il processo per inserire
qualcosa in un trie è simile a

94
00:05:00,350 --> 00:05:02,060
guardando qualcosa in un trie.

95
00:05:02,060 --> 00:05:05,720
>> Inizieremo con il nodo principale di nuovo,
seguenti indicazioni corrispondenti a

96
00:05:05,720 --> 00:05:07,990
le lettere della nostra chiave.

97
00:05:07,990 --> 00:05:11,310
Per fortuna, siamo riusciti a seguire i puntatori
tutta la strada fino a quando abbiamo raggiunto

98
00:05:11,310 --> 00:05:12,770
la fine della chiave.

99
00:05:12,770 --> 00:05:16,480
Poiché zoo è un prefisso della parola
zoom, che è membro del

100
00:05:16,480 --> 00:05:19,440
dizionario, non abbiamo bisogno di
destinare eventuali nuovi nodi.

101
00:05:19,440 --> 00:05:23,140
>> Possiamo modificare il nodo per indicare che
il percorso di protagonisti a

102
00:05:23,140 --> 00:05:25,360
rappresenta una chiave nel nostro dizionario.

103
00:05:25,360 --> 00:05:28,630
Ora, proviamo inserendo il
BAGNO chiave nel trie.

104
00:05:28,630 --> 00:05:32,260
Inizieremo al nodo radice
e seguire di nuovo i puntatori.

105
00:05:32,260 --> 00:05:35,620
Ma in questa situazione, ci ha colpito un morto
terminare prima che siamo in grado di ottenere il

106
00:05:35,620 --> 00:05:36,940
fine della chiave.

107
00:05:36,940 --> 00:05:40,980
Ora, abbiamo bisogno di allocare una nuova
nodi dovranno allocare una nuova

108
00:05:40,980 --> 00:05:43,660
nodo per ogni restante
lettera della nostra chiave.

109
00:05:43,660 --> 00:05:46,740
>> In questo caso, dobbiamo solo
attribuire un nuovo nodo.

110
00:05:46,740 --> 00:05:50,590
Poi abbiamo bisogno di rendere l'indice H
riferimento a questo nuovo nodo.

111
00:05:50,590 --> 00:05:54,070
Ancora una volta, possiamo modificare il nodo
indicare che il percorso di caratteri

112
00:05:54,070 --> 00:05:57,120
conduce ad esso rappresenta un
chiave nel nostro dizionario.

113
00:05:57,120 --> 00:06:00,730
Facciamo ragionare sulla asintotico
complessità delle nostre procedure per tali

114
00:06:00,730 --> 00:06:02,110
due operazioni.

115
00:06:02,110 --> 00:06:06,420
>> Notiamo che in entrambi i casi il numero
di passaggi nostro algoritmo ha preso è stato

116
00:06:06,420 --> 00:06:09,470
proporzionale al numero di
lettere della parola chiave.

117
00:06:09,470 --> 00:06:10,220
Che è di destra.

118
00:06:10,220 --> 00:06:13,470
Se si vuole cercare una parola in un
trie basta scorrere

119
00:06:13,470 --> 00:06:17,100
le lettere una ad una finché non si
raggiungere la fine della parola o

120
00:06:17,100 --> 00:06:19,060
colpito un vicolo cieco nel trie.

121
00:06:19,060 --> 00:06:22,470
>> E quando si desidera inserire una chiave
coppia di valori in un trie usando l'

122
00:06:22,470 --> 00:06:26,250
procedura abbiamo discusso, il caso peggiore
vi farà assegnazione di un nuovo nodo

123
00:06:26,250 --> 00:06:27,550
per ogni lettera.

124
00:06:27,550 --> 00:06:31,290
E noi assumiamo che l'assegnazione
è un'operazione a tempo costante.

125
00:06:31,290 --> 00:06:35,850
Quindi, se si assume che la lunghezza della chiave è
delimitata da una costante fissa, sia

126
00:06:35,850 --> 00:06:39,400
inserimento e guardare in alto sono costanti
operazioni di tempo per un trie.

127
00:06:39,400 --> 00:06:42,930
>> Se non facciamo questo presupposto che
la lunghezza della chiave è delimitato da una fissa

128
00:06:42,930 --> 00:06:46,650
costante, quindi dell'inserimento e guardare in alto,
nel caso peggiore, sono lineari nella

129
00:06:46,650 --> 00:06:48,240
lunghezza della chiave.

130
00:06:48,240 --> 00:06:51,800
Si noti che il numero di elementi memorizzati
nel trie non pregiudica il look up

131
00:06:51,800 --> 00:06:52,820
o il tempo di inserimento.

132
00:06:52,820 --> 00:06:55,360
È influenzato solo dal
lunghezza della chiave.

133
00:06:55,360 --> 00:06:59,300
>> Per contro, l'aggiunta di voci, per dire,
una tabella hash tende a rendere

134
00:06:59,300 --> 00:07:01,250
futuro sguardo lento.

135
00:07:01,250 --> 00:07:04,520
Anche se questo può sembrare attraente in un primo momento,
dovremmo tenere a mente che un

136
00:07:04,520 --> 00:07:08,740
favorevole complessità asintotica non
significa che in pratica i dati

137
00:07:08,740 --> 00:07:11,410
struttura è necessariamente
irreprensibile.

138
00:07:11,410 --> 00:07:15,860
Dobbiamo anche considerare che per memorizzare un
parola in un trie abbiamo bisogno, nella peggiore

139
00:07:15,860 --> 00:07:19,700
caso, un numero di nodi proporzionale
alla lunghezza della parola stessa.

140
00:07:19,700 --> 00:07:21,880
>> Tenta tendono ad usare un sacco di spazio.

141
00:07:21,880 --> 00:07:25,620
Questo è in contrasto con una tabella di hash,
dove abbiamo solo bisogno di un nuovo nodo

142
00:07:25,620 --> 00:07:27,940
memorizzare alcune coppia chiave-valore.

143
00:07:27,940 --> 00:07:31,370
Ora, sempre in teoria, ampio spazio
consumo non sembra un grande

144
00:07:31,370 --> 00:07:34,620
affrontare, soprattutto considerando che la moderna
computer hanno gigabyte e

145
00:07:34,620 --> 00:07:36,180
gigabyte di memoria.

146
00:07:36,180 --> 00:07:39,200
Ma si scopre che abbiamo ancora
preoccuparsi di utilizzo della memoria e

147
00:07:39,200 --> 00:07:42,540
organizzazione per il bene della
prestazioni, dato che i computer moderni

148
00:07:42,540 --> 00:07:46,960
disporre di meccanismi in atto sotto la
Cappa per accelerare l'accesso alla memoria.

149
00:07:46,960 --> 00:07:51,180
>> Ma questi meccanismi funzionano meglio quando
accessi alla memoria sono realizzati in versione ridotta

150
00:07:51,180 --> 00:07:52,810
regioni o zone.

151
00:07:52,810 --> 00:07:55,910
E i nodi di un trie potrebbero risiedere
ovunque in quel mucchio.

152
00:07:55,910 --> 00:07:58,390
Ma questi sono compromessi
che dobbiamo considerare.

153
00:07:58,390 --> 00:08:01,440
>> Ricordate che, quando si sceglie un dato
struttura per un certo compito, abbiamo

154
00:08:01,440 --> 00:08:04,420
dovrebbe pensare a quali tipi di
operazioni la struttura di dati deve

155
00:08:04,420 --> 00:08:07,140
supporto e qual è il rendimento
di ciascuno di tali

156
00:08:07,140 --> 00:08:09,080
operazioni è importante per noi.

157
00:08:09,080 --> 00:08:11,300
Queste operazioni possono anche
estendersi oltre la semplice

158
00:08:11,300 --> 00:08:13,430
aspetto di base e di inserimento.

159
00:08:13,430 --> 00:08:17,010
Supponiamo di voler realizzare una sorta
di funzionalità di completamento automatico, molto

160
00:08:17,010 --> 00:08:18,890
come motore di ricerca di Google fa.

161
00:08:18,890 --> 00:08:22,210
Cioè, restituire tutte le chiavi e
potenzialmente valori che

162
00:08:22,210 --> 00:08:24,130
avere un determinato prefisso.

163
00:08:24,130 --> 00:08:27,050
>> Un trie è unicamente utile
per questa operazione.

164
00:08:27,050 --> 00:08:29,890
E 'semplice da scorrere
trie per ogni carattere di

165
00:08:29,890 --> 00:08:30,950
il prefisso.

166
00:08:30,950 --> 00:08:33,559
Proprio come un guardare in alto funzionamento,
abbiamo potuto seguire i puntatori

167
00:08:33,559 --> 00:08:35,400
carattere per carattere.

168
00:08:35,400 --> 00:08:38,659
Poi, quando si arriva alla fine del
prefisso, potremmo scorrere l'

169
00:08:38,659 --> 00:08:42,049
porzione rimanente della struttura dati
poiché uno dei tasti di là

170
00:08:42,049 --> 00:08:43,980
questo punto hanno il prefisso.

171
00:08:43,980 --> 00:08:47,670
>> E 'anche facile da ottenere questo annuncio
in ordine alfabetico poiché l'

172
00:08:47,670 --> 00:08:50,970
elementi della matrice bambini
sono elencate in ordine alfabetico.

173
00:08:50,970 --> 00:08:54,420
Così si spera che prenderemo in considerazione
dando prova una prova.

174
00:08:54,420 --> 00:08:56,085
Sono Kevin Schmid, e questo è CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> Ah, questo è l'inizio
del declino.

177
00:09:00,790 --> 00:09:01,350
Mi dispiace.

178
00:09:01,350 --> 00:09:01,870
Scusi.

179
00:09:01,870 --> 00:09:02,480
Scusi.

180
00:09:02,480 --> 00:09:03,130
Scusi.

181
00:09:03,130 --> 00:09:03,950
>> Sciopero di quattro.

182
00:09:03,950 --> 00:09:04,360
Sono fuori.

183
00:09:04,360 --> 00:09:05,280
Scusi.

184
00:09:05,280 --> 00:09:06,500
Scusi.

185
00:09:06,500 --> 00:09:07,490
Scusi.

186
00:09:07,490 --> 00:09:12,352
Ci scusiamo per fare la persona che
deve modificare questa impazzire.

187
00:09:12,352 --> 00:09:13,280
>> Scusi.

188
00:09:13,280 --> 00:09:13,880
Scusi.

189
00:09:13,880 --> 00:09:15,080
Scusi.

190
00:09:15,080 --> 00:09:15,680
Scusi.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: Ben fatto.

192
00:09:16,280 --> 00:09:17,530
Che è stato davvero ben fatto.

193
00:09:17,530 --> 00:09:18,430