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

2
00:00:10,900 --> 00:00:15,860
>> ENCEINTE 1: Très bien, donc cela est
CS50 Ceci est la fin de la semaine de cinq.

3
00:00:15,860 --> 00:00:19,220
Et de rappeler que la dernière fois nous
commencé à regarder les données fantaisistes

4
00:00:19,220 --> 00:00:22,310
structures qui ont commencé à résoudre
problèmes, qui ont commencé à introduire des

5
00:00:22,310 --> 00:00:25,640
de nouveaux problèmes, mais la clé de cette
était le genre de filetage que nous

6
00:00:25,640 --> 00:00:27,940
commencé à faire de nœud à nœud.

7
00:00:27,940 --> 00:00:30,085
Donc, cela est bien sûr
une liste chaînée.

8
00:00:30,085 --> 00:00:31,960
Et par chaînée,
Je veux dire il ya juste un

9
00:00:31,960 --> 00:00:33,380
faufiler entre chacun de ces nœuds.

10
00:00:33,380 --> 00:00:35,890
Avère que vous pouvez faire colombophile
des choses comme des listes doublement chaînées

11
00:00:35,890 --> 00:00:38,470
par lequel vous avez une flèche
aller dans les deux sens, ce qui

12
00:00:38,470 --> 00:00:40,320
peut aider avec une certaine efficacité.

13
00:00:40,320 --> 00:00:42,000
Mais cela a résolu le problème?

14
00:00:42,000 --> 00:00:43,500
Quel problème est-ce à résoudre?

15
00:00:43,500 --> 00:00:46,620
Pourquoi avons-nous soucions le lundi?

16
00:00:46,620 --> 00:00:49,820
Pourquoi, en théorie, ne nous nous soucions le lundi?

17
00:00:49,820 --> 00:00:50,630
Qu'est ce que ça fait?

18
00:00:50,630 --> 00:00:51,950
>> PUBLIC: Nous pouvons dynamiquement redimensionner.

19
00:00:51,950 --> 00:00:53,740
>> ENCEINTE 1: OK, alors nous pouvons
redimensionner dynamiquement.

20
00:00:53,740 --> 00:00:54,710
Bravo à vous deux.

21
00:00:54,710 --> 00:00:57,560
Ainsi, vous pouvez redimensionner dynamiquement cette
Structure de données, alors un tableau,

22
00:00:57,560 --> 00:01:00,760
rappel, vous avez à connaître
priori comment vous voulez beaucoup d'espace

23
00:01:00,760 --> 00:01:03,870
et si vous avez besoin d'un peu plus
espace, vous êtes un peu hors de la chance.

24
00:01:03,870 --> 00:01:05,560
Vous devez créer un tout nouveau tableau.

25
00:01:05,560 --> 00:01:07,893
Vous devez déplacer tous vos
les données d'un à l'autre,

26
00:01:07,893 --> 00:01:10,600
finalement libérer l'ancien tableau
si vous le pouvez, et ensuite procéder.

27
00:01:10,600 --> 00:01:13,891
Qui se sent juste très coûteux et très
inefficace, et en effet il peut être.

28
00:01:13,891 --> 00:01:14,890
Mais ce ne sont pas tous bons.

29
00:01:14,890 --> 00:01:18,180
Nous payons un prix, ce qui a été l'un
des prix plus évidentes, nous

30
00:01:18,180 --> 00:01:20,550
payer en utilisant une liste chaînée?

31
00:01:20,550 --> 00:01:22,825
>> PUBLIC: Nous devons utiliser
espace double pour chacun.

32
00:01:22,825 --> 00:01:25,200
ENCEINTE 1: Ouais, donc nous avons besoin
au moins deux fois autant d'espace.

33
00:01:25,200 --> 00:01:27,700
En fait, je me rendis compte de cette image
même un peu trompeur,

34
00:01:27,700 --> 00:01:32,200
parce que sur CS50 IDE dans un lot de moderne
ordinateurs, un pointeur ou une adresse

35
00:01:32,200 --> 00:01:33,700
est pas en fait quatre octets.

36
00:01:33,700 --> 00:01:36,090
Il est très souvent ceux-ci
huit jours octets, ce qui

37
00:01:36,090 --> 00:01:38,530
des moyens le plus bas
rectangles là dans la réalité

38
00:01:38,530 --> 00:01:40,900
sont sorte de deux fois
grand que ce que je l'ai dessiné,

39
00:01:40,900 --> 00:01:44,409
ce qui signifie que vous utilisez trois fois plus
autant d'espace que nous pourrions avoir autrement.

40
00:01:44,409 --> 00:01:46,700
Maintenant, dans le même temps, nous sommes
parle encore octets, non?

41
00:01:46,700 --> 00:01:49,140
Nous ne parlons pas nécessairement
mégaoctets ou gigaoctets,

42
00:01:49,140 --> 00:01:51,000
sauf si ces structures de données deviennent grands.

43
00:01:51,000 --> 00:01:54,510
>> Et aujourd'hui, nous commençons à considérer
comment nous pourrions explorer les données

44
00:01:54,510 --> 00:01:57,310
plus efficacement en cas de
fait, les données devient plus grand.

45
00:01:57,310 --> 00:02:00,360
Mais nous allons essayer de canoniser
les premières opérations

46
00:02:00,360 --> 00:02:02,460
que vous pouvez faire sur ces
les types de structures de données.

47
00:02:02,460 --> 00:02:04,790
Donc, quelque chose comme un lien
liste prend généralement en charge

48
00:02:04,790 --> 00:02:07,514
Les opérations telles que supprimer,
insérer et rechercher.

49
00:02:07,514 --> 00:02:08,639
Et qu'est-ce que je veux dire par là?

50
00:02:08,639 --> 00:02:11,222
Cela signifie juste que généralement,
si les gens utilisent liste chaînée,

51
00:02:11,222 --> 00:02:14,287
ils ou quelqu'un d'autre a mis en place
fonctions telles que supprimer, insérer,

52
00:02:14,287 --> 00:02:16,120
et la recherche, afin que vous puissiez
réellement faire quelque chose

53
00:02:16,120 --> 00:02:18,030
utile avec la structure de données.

54
00:02:18,030 --> 00:02:20,760
Donc, nous allons jeter un coup d'œil
comment nous pourrions mettre en œuvre

55
00:02:20,760 --> 00:02:24,530
un peu de code pour une liste chaînée comme suit.

56
00:02:24,530 --> 00:02:27,885
>> Donc, ceci est juste un peu de code C,
même pas un programme complet

57
00:02:27,885 --> 00:02:29,260
que je très rapidement fouetté.

58
00:02:29,260 --> 00:02:32,300
Il est pas en ligne dans la distribution
code, car il ne sera pas réellement fonctionner.

59
00:02:32,300 --> 00:02:33,790
Mais remarquez que je viens
avec un commentaire dit,

60
00:02:33,790 --> 00:02:36,130
Dot Dot Dot, il ya quelque chose
là, Dot Dot Dot, quelque chose là.

61
00:02:36,130 --> 00:02:38,410
Et disons simplement Regardons
ce que les parties sont juteuses.

62
00:02:38,410 --> 00:02:40,790
Donc, sur la ligne de trois,
Rappelons que ce est maintenant

63
00:02:40,790 --> 00:02:45,960
nous avons proposé de déclarer un nœud dernière
temps, l'un de ces objets rectangulaires.

64
00:02:45,960 --> 00:02:48,790
Il a un int que nous appellerons N,
mais nous pourrions l'appeler quelque chose,

65
00:02:48,790 --> 00:02:51,920
puis une star du noeud de struct appelé prochaine.

66
00:02:51,920 --> 00:02:55,520
Et juste pour être clair, ce deuxième
ligne, sur la ligne de six, ce qui est qui?

67
00:02:55,520 --> 00:02:57,930
Que fait-il pour nous?

68
00:02:57,930 --> 00:03:01,044
Parce qu'il ressemble certainement plus
cryptique que nos variables habituelles.

69
00:03:01,044 --> 00:03:02,740
>> PUBLIC: Il fait bouger plus d'un.

70
00:03:02,740 --> 00:03:04,650
>> ENCEINTE 1: Il fait bouger plus d'un.

71
00:03:04,650 --> 00:03:08,580
Et pour être plus précis,
il va stocker l'adresse

72
00:03:08,580 --> 00:03:11,582
du noeud qui est destiné à être
sémantiquement à côté de lui, non?

73
00:03:11,582 --> 00:03:13,540
Donc, il ne va pas
déplacer nécessairement quelque chose.

74
00:03:13,540 --> 00:03:15,290
Il va juste
stocker une valeur, qui est

75
00:03:15,290 --> 00:03:17,170
va être l'adresse
d'un autre noeud,

76
00:03:17,170 --> 00:03:20,810
et voilà pourquoi nous avons dit struct
noeud étoiles, l'étoile dénotant

77
00:03:20,810 --> 00:03:22,370
un pointeur ou une adresse.

78
00:03:22,370 --> 00:03:26,390
OK, maintenant si vous supposer que nous avons
ce N disponible pour nous, et nous allons

79
00:03:26,390 --> 00:03:29,490
supposer que quelqu'un d'autre a
inséré tout un tas d'entiers

80
00:03:29,490 --> 00:03:30,400
dans une liste chaînée.

81
00:03:30,400 --> 00:03:35,640
Et cette liste est liée
pointée par un certain point

82
00:03:35,640 --> 00:03:39,040
une variable appelée liste qui est
adoptée ici en tant que paramètre,

83
00:03:39,040 --> 00:03:43,120
comment puis-je aller sur la ligne
14 mise en œuvre de la recherche?

84
00:03:43,120 --> 00:03:45,990
En d'autres termes, si je suis la mise en œuvre
fonction dont le but dans la vie

85
00:03:45,990 --> 00:03:48,889
est de prendre un int, puis le
début d'une liste chaînée,

86
00:03:48,889 --> 00:03:50,430
qui est un pointeur vers la liste chaînée.

87
00:03:50,430 --> 00:03:52,992
Comme la première, qui, je pense David
était notre bénévole le lundi,

88
00:03:52,992 --> 00:03:54,700
il pointait
toute la liste chaînée,

89
00:03:54,700 --> 00:03:57,820
il est comme si nous passons
David en tant que notre argumentation ici.

90
00:03:57,820 --> 00:03:59,990
Comment allons-nous traverser cette liste?

91
00:03:59,990 --> 00:04:04,640
Eh bien, il se trouve que même si
pointeurs sont relativement nouvelle pour nous maintenant,

92
00:04:04,640 --> 00:04:07,010
nous pouvons le faire relativement
carrément.

93
00:04:07,010 --> 00:04:09,500
>> Je vais aller de l'avant et
déclarer une variable temporaire

94
00:04:09,500 --> 00:04:12,364
par convention va tout simplement
d'être appelé pointeur, ou PTR,

95
00:04:12,364 --> 00:04:14,030
mais vous pourriez l'appeler ce que vous voulez.

96
00:04:14,030 --> 00:04:16,470
Et je vais initialiser
au début de la liste.

97
00:04:16,470 --> 00:04:20,050
Ainsi, vous pouvez sorte de penser de cette
comme me l'enseignant, l'autre jour,

98
00:04:20,050 --> 00:04:23,580
sorte de pointage à quelqu'un
parmi nos humains en tant que bénévoles.

99
00:04:23,580 --> 00:04:26,470
Je suis donc une variable temporaire qui est
pointant simplement la même chose

100
00:04:26,470 --> 00:04:31,390
que notre hasard nommé
David a également été bénévole soulignant.

101
00:04:31,390 --> 00:04:35,440
Maintenant, alors que le pointeur est
non nulle, parce rappel

102
00:04:35,440 --> 00:04:40,350
que nulle est une valeur sentinelle spéciale
la délimite la fin de la liste,

103
00:04:40,350 --> 00:04:44,280
Ainsi, alors que je ne suis pas au pointage
sol comme notre dernière bénévoles

104
00:04:44,280 --> 00:04:47,190
était, Allons de l'avant
et faire ce qui suit.

105
00:04:47,190 --> 00:04:51,820
Si pointer-- et maintenant je veux sorte de
de faire ce que nous avons fait avec l'étudiant

106
00:04:51,820 --> 00:04:57,410
structure-- si le pointeur point à côté
equals-- plutôt, si le pointeur point N est égal

107
00:04:57,410 --> 00:05:02,290
est égal à la variable N, la
l'argument qui a été transmis,

108
00:05:02,290 --> 00:05:05,370
alors je veux aller de l'avant
et dire return true.

109
00:05:05,370 --> 00:05:11,020
Je l'ai trouvé le numéro N intérieur de
l'un des nœuds de ma liste chaînée.

110
00:05:11,020 --> 00:05:13,500
Mais le point plus
qui fonctionne dans ce contexte,

111
00:05:13,500 --> 00:05:17,260
parce pointeur, PTR, est
en effet un pointeur, une adresse,

112
00:05:17,260 --> 00:05:20,632
Nous pouvons en fait merveille
enfin utiliser un morceau de syntaxe

113
00:05:20,632 --> 00:05:22,590
ce genre de marques
sens intuitif et effectivement

114
00:05:22,590 --> 00:05:27,870
utiliser une flèche ici, ce qui signifie aller de
cette adresse à l'entier là dans.

115
00:05:27,870 --> 00:05:30,160
Il est donc très similaire dans
esprit de l'opérateur point,

116
00:05:30,160 --> 00:05:33,860
mais parce que le pointeur est pas un pointeur
et pas une structure elle-même,

117
00:05:33,860 --> 00:05:35,380
nous utilisons simplement la flèche.

118
00:05:35,380 --> 00:05:40,620
>> Donc, si le noeud courant que moi,
variable temporaire, me montre du doigt

119
00:05:40,620 --> 00:05:43,060
N est pas, qu'est-ce que je veux faire?

120
00:05:43,060 --> 00:05:45,910
Eh bien, avec mes volontaires humains
que nous avons eu ici l'autre jour,

121
00:05:45,910 --> 00:05:49,710
si mon premier humain est pas celui que je
veut, et peut-être le deuxième homme est pas

122
00:05:49,710 --> 00:05:52,660
celui que je veux, et le troisième, je
besoin de bouger physiquement.

123
00:05:52,660 --> 00:05:54,690
Comme comment puis-je passerai une liste?

124
00:05:54,690 --> 00:05:57,470
Quand nous avons eu un tableau, vous
juste fait comme je l'ai plus plus.

125
00:05:57,470 --> 00:06:03,660
Mais dans ce cas, il suffit de
faire pointeur, obtient, pointeur, à côté.

126
00:06:03,660 --> 00:06:07,580
En d'autres termes, le champ suivant
est comme toutes les mains gauches

127
00:06:07,580 --> 00:06:10,880
que nos volontaires humains lundi
utilisaient pour pointer vers un autre nœud.

128
00:06:10,880 --> 00:06:12,890
Ce sont leurs prochains voisins.

129
00:06:12,890 --> 00:06:17,060
>> Donc, si je veux passer en revue cette liste,
Je ne peux pas le faire, je plus plus plus,

130
00:06:17,060 --> 00:06:20,120
Je dois dire à la place
I, pointeur, va

131
00:06:20,120 --> 00:06:24,650
à égale quel que soit le champ suivant est,
le champ suivant est, le champ suivant est,

132
00:06:24,650 --> 00:06:28,350
suivant toutes ces mains gauches
que nous avions sur le pointage de scène

133
00:06:28,350 --> 00:06:30,000
pour certaines valeurs suivantes.

134
00:06:30,000 --> 00:06:32,590
Et si je reçois par
que l'ensemble de l'itération,

135
00:06:32,590 --> 00:06:39,330
et enfin, je frappe null ne pas avoir
N trouvé encore, je reviens tout simplement fausse.

136
00:06:39,330 --> 00:06:44,100
Encore une fois, tout ce que nous faisons ici,
selon l'image il ya un instant,

137
00:06:44,100 --> 00:06:47,840
commence en pointant à la
début de la liste sans doute.

138
00:06:47,840 --> 00:06:50,970
Et puis je vérifie, est la valeur
Je cherche égal à neuf?

139
00:06:50,970 --> 00:06:52,650
Si oui, je reviens vrai et je suis fait.

140
00:06:52,650 --> 00:06:56,450
Si non, je mets à jour ma main,
Alias ​​pointeur, pour pointer

141
00:06:56,450 --> 00:06:59,540
à l'emplacement de la prochaine flèche, et
puis l'emplacement de la prochaine flèche,

142
00:06:59,540 --> 00:07:00,480
et la suivante.

143
00:07:00,480 --> 00:07:03,770
Je suis tout simplement la marche à travers ce réseau.

144
00:07:03,770 --> 00:07:06,010
>> Donc encore une fois, qui se soucie?

145
00:07:06,010 --> 00:07:07,861
Comme quoi est-ce un ingrédient pour?

146
00:07:07,861 --> 00:07:10,360
Eh bien, rappelons que nous avons lancé
la notion d'une pile, qui

147
00:07:10,360 --> 00:07:15,400
est de type dans la mesure où une donnée abstraite comme il est
pas une chose de C, il est pas une chose de CS50,

148
00:07:15,400 --> 00:07:19,430
il est une idée abstraite, cette idée de
empiler sur des choses dessus de l'autre

149
00:07:19,430 --> 00:07:21,820
qui peut être mis en œuvre dans
des grappes de différentes manières.

150
00:07:21,820 --> 00:07:25,600
Et une façon que nous avons proposé était avec
un tableau, ou avec une liste chaînée.

151
00:07:25,600 --> 00:07:29,570
Et il se trouve que canoniquement, un
pile prend en charge au moins deux opérations.

152
00:07:29,570 --> 00:07:32,320
Et les mots à la mode sont poussée, à
pousser quelque chose sur la pile,

153
00:07:32,320 --> 00:07:34,770
comme un nouveau plateau dans le
salle à manger, ou de la pop,

154
00:07:34,770 --> 00:07:39,000
ce qui signifie pour enlever le plus élevé
plateau de la pile dans la salle

155
00:07:39,000 --> 00:07:41,500
salle, et puis peut-être un peu
d'autres opérations ainsi.

156
00:07:41,500 --> 00:07:45,770
Alors, comment pouvons-nous définir la structure
que nous appelons maintenant une pile?

157
00:07:45,770 --> 00:07:50,020
>> Eh bien, nous avons tout le nécessaire
la syntaxe à notre disposition en C. Je dis,

158
00:07:50,020 --> 00:07:53,830
me donner une définition de type de
une structure à l'intérieur d'une pile,

159
00:07:53,830 --> 00:07:58,030
Je vais dire est un tableau, d'un
tas ensemble de nombres, puis la taille.

160
00:07:58,030 --> 00:08:00,930
Donc, en d'autres termes, si je veux
à mettre en œuvre dans votre code,

161
00:08:00,930 --> 00:08:03,830
laissez-moi partir et juste sorte de
dessiner ce que cela veut dire.

162
00:08:03,830 --> 00:08:06,317
Donc, cela veut dire, me donner un
la structure qui a obtenu un tableau,

163
00:08:06,317 --> 00:08:09,400
et je ne sais pas quelle est la capacité,
il est apparemment une constante que je l'ai

164
00:08:09,400 --> 00:08:10,858
définis ailleurs, et ça va.

165
00:08:10,858 --> 00:08:15,260
Mais supposons qu'il est juste un,
deux, trois, quatre, cinq.

166
00:08:15,260 --> 00:08:16,700
Donc, la capacité est de 5.

167
00:08:16,700 --> 00:08:21,730
Cet élément intérieur de ma
structure sera appelée numéros.

168
00:08:21,730 --> 00:08:24,020
Et puis je besoin d'un
une autre variable apparemment

169
00:08:24,020 --> 00:08:27,814
appelé taille qui d'abord je vais
à prévoir est initialisée à zéro.

170
00:08:27,814 --> 00:08:29,730
Si il n'y a rien dans
la pile, la taille est égale à zéro,

171
00:08:29,730 --> 00:08:31,420
et il est des valeurs parasites en nombre.

172
00:08:31,420 --> 00:08:33,450
Je ne sais pas ce qu'il ya dedans pour l'instant.

173
00:08:33,450 --> 00:08:36,059
>> Donc, si je veux pousser
quelque chose sur la pile,

174
00:08:36,059 --> 00:08:40,780
suppose que je l'appelle la fonction Push, et
Je dis pousser 50, comme le nombre 50,

175
00:08:40,780 --> 00:08:44,090
où voulez-vous proposer
Je dessine dans ce tableau?

176
00:08:44,090 --> 00:08:47,124
Il ya cinq réponses différentes possibles.

177
00:08:47,124 --> 00:08:48,790
Où voulez-vous de pousser le numéro 50?

178
00:08:48,790 --> 00:08:51,899
Si le but ici, encore une fois, appeler le
fonction Push, passer dans un argument

179
00:08:51,899 --> 00:08:52,940
50, où dois-je le mettre?

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

181
00:08:55,680 --> 00:08:59,052
Cinq possible-- 20% de chances
de deviner correctement.

182
00:08:59,052 --> 00:08:59,896
Oui?

183
00:08:59,896 --> 00:09:00,740
>> AUDIENCE: Extrême droite.

184
00:09:00,740 --> 00:09:01,990
>> ENCEINTE 1: Extrême droite.

185
00:09:01,990 --> 00:09:08,359
Il ya maintenant une chance de 25%
de deviner correctement.

186
00:09:08,359 --> 00:09:09,650
Donc, ce serait effectivement bien.

187
00:09:09,650 --> 00:09:12,770
Par convention, je vais le dire avec un tableau,
nous aurions commence généralement à gauche,

188
00:09:12,770 --> 00:09:14,519
mais nous pourrions certainement
commence à la droite.

189
00:09:14,519 --> 00:09:17,478
Donc, le spoiler ici serait que je suis
va probablement dessiner sur la gauche,

190
00:09:17,478 --> 00:09:20,060
Tout comme dans un tableau normal où
Je commencer à aller de gauche à droite.

191
00:09:20,060 --> 00:09:21,780
Mais si vous pouvez retourner
l'arithmétique, très bien.

192
00:09:21,780 --> 00:09:23,060
Il est tout simplement pas conventionnelle.

193
00:09:23,060 --> 00:09:24,880
OK, je dois faire un
plus de changement cependant.

194
00:09:24,880 --> 00:09:27,710
Maintenant que je l'ai poussé quelque chose
sur la pile, ce qui est la prochaine étape?

195
00:09:27,710 --> 00:09:29,400
>> Très bien, je dois augmenter la taille.

196
00:09:29,400 --> 00:09:32,600
Alors laissez-moi aller de l'avant et juste
mettre à jour ce qui était de zéro.

197
00:09:32,600 --> 00:09:35,950
Et au lieu maintenant, je vais
de mettre en la valeur un.

198
00:09:35,950 --> 00:09:39,460
Et maintenant suppose que je pousse un autre
numéro sur la pile, comme 51.

199
00:09:39,460 --> 00:09:42,680
Eh bien, je dois faire un de plus
changement, qui est à la taille deux.

200
00:09:42,680 --> 00:09:46,100
Et puis suppose que je pousse un de plus
numéro sur la pile comme 61,

201
00:09:46,100 --> 00:09:52,530
maintenant je dois mettre à jour la taille d'un plus
temps, et obtenir la valeur 3 comme la taille.

202
00:09:52,530 --> 00:09:54,690
Et maintenant, je suppose appelle pop.

203
00:09:54,690 --> 00:09:57,250
Maintenant, pop, par convention,
ne prenez pas un argument.

204
00:09:57,250 --> 00:10:00,430
Avec une pile, l'ensemble
point de la métaphore de plateau

205
00:10:00,430 --> 00:10:03,450
est que vous ne disposez pas de la discrétion
d'aller chercher ce plateau, tout ce que vous pouvez faire

206
00:10:03,450 --> 00:10:06,330
est pop la plus haute un de
la pile, juste parce que.

207
00:10:06,330 --> 00:10:08,010
Voilà ce que cette structure de données fait.

208
00:10:08,010 --> 00:10:12,250
>> Ainsi, en ce que si la logique I
dire pop, ce qui se détache?

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

210
00:10:13,080 --> 00:10:15,402
Donc ce qui est vraiment l'ordinateur
va faire dans la mémoire?

211
00:10:15,402 --> 00:10:16,610
Qu'est-ce que mon code a à voir?

212
00:10:16,610 --> 00:10:20,330
Que proposeriez-vous
nous changeons sur l'écran?

213
00:10:20,330 --> 00:10:23,410
Qu'est-ce qui devrait changer?

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

215
00:10:24,960 --> 00:10:26,334
Nous sommes tellement débarrassés de 61.

216
00:10:26,334 --> 00:10:27,500
Donc, je peux certainement le faire.

217
00:10:27,500 --> 00:10:28,640
Et je peux me débarrasser de 61.

218
00:10:28,640 --> 00:10:30,980
Et puis ce que les autres
le changement doit se produire?

219
00:10:30,980 --> 00:10:33,160
Taille a probablement revenir à deux.

220
00:10:33,160 --> 00:10:34,210
Et alors ça va.

221
00:10:34,210 --> 00:10:36,690
Mais attendez une minute, la taille
il ya un moment était trois.

222
00:10:36,690 --> 00:10:38,240
Disons simplement faire une vérification de cohérence rapide.

223
00:10:38,240 --> 00:10:41,810
Comment avons-nous savons que nous
voulait se débarrasser de 61?

224
00:10:41,810 --> 00:10:42,760
Parce que nous sommes popping.

225
00:10:42,760 --> 00:10:46,450
Et donc je dois cette seconde taille de la propriété.

226
00:10:46,450 --> 00:10:48,470
>> Attendez une minute, je suis
repensant à deux semaines

227
00:10:48,470 --> 00:10:51,660
lorsque nous avons commencé à parler
tableaux, où cela était l'emplacement zéro,

228
00:10:51,660 --> 00:10:55,920
ce fut l'un emplacement, ce fut emplacement
deux, cet emplacement est trois, quatre,

229
00:10:55,920 --> 00:10:58,460
il semble que le
relation entre la taille

230
00:10:58,460 --> 00:11:02,780
et l'élément que je veux supprimer
à partir du tableau semble juste être quoi?

231
00:11:02,780 --> 00:11:05,120
Taille moins un.

232
00:11:05,120 --> 00:11:07,786
Et voilà comment en tant qu'êtres humains
nous savons 61 vient en premier.

233
00:11:07,786 --> 00:11:09,160
Comment est l'ordinateur va savoir?

234
00:11:09,160 --> 00:11:11,701
Lorsque votre code, où vous avez probablement
vouloir faire la taille moins un,

235
00:11:11,701 --> 00:11:14,950
donc trois moins un est de deux, et que
signifie que nous voulons nous débarrasser de 61 ans.

236
00:11:14,950 --> 00:11:18,000
Et puis, nous pouvons en effet de mettre à jour
la taille de sorte que la taille maintenant

237
00:11:18,000 --> 00:11:20,300
va de trois à deux seulement.

238
00:11:20,300 --> 00:11:24,520
Et juste pour être pédant, je vais
de proposer que je suis fait, non?

239
00:11:24,520 --> 00:11:27,660
Vous avez proposé intuitivement
correctement je devrais me débarrasser de 61.

240
00:11:27,660 --> 00:11:30,700
Mais avoir pas que je sorte de
sorte d'débarrassé de 61?

241
00:11:30,700 --> 00:11:33,790
Je l'ai effectivement oublié
qu'il est vraiment là.

242
00:11:33,790 --> 00:11:37,680
Et penser à PSET4, si vous avez lu
l'article sur la médecine légale, le PDF

243
00:11:37,680 --> 00:11:40,780
que nous devions vous les gars lire, ou vous
lira cette semaine pour PSET4.

244
00:11:40,780 --> 00:11:44,300
Rappelons que ce soit réellement germane à
l'idée de la criminalistique informatique.

245
00:11:44,300 --> 00:11:47,820
Qu'est-ce que le fait généralement un ordinateur est
il oublie juste où quelque chose est,

246
00:11:47,820 --> 00:11:51,300
mais il ne va pas et comme
essayer de gratter sur ou override

247
00:11:51,300 --> 00:11:54,560
ces bits avec zéros et de uns
ou quelque autre motif aléatoire

248
00:11:54,560 --> 00:11:56,690
sauf si vous vous le faire volontairement.

249
00:11:56,690 --> 00:11:58,930
Donc, votre intuition était
droite, débarrassons-nous de 61 ans.

250
00:11:58,930 --> 00:12:00,650
Mais en réalité, nous ne devons pas la peine.

251
00:12:00,650 --> 00:12:04,040
Nous avons juste besoin d'oublier que
il est là en changeant notre taille.

252
00:12:04,040 --> 00:12:05,662
>> Maintenant, il ya un problème avec cette pile.

253
00:12:05,662 --> 00:12:07,620
Si je continue à pousser les choses
sur la pile, ce qui est

254
00:12:07,620 --> 00:12:11,167
évidemment va se passer
en un temps de quelques instants?

255
00:12:11,167 --> 00:12:12,500
Nous allons manquer d'espace.

256
00:12:12,500 --> 00:12:13,580
Et que faisons-nous?

257
00:12:13,580 --> 00:12:14,680
Nous sommes en quelque sorte des foutus.

258
00:12:14,680 --> 00:12:19,000
Cette mise en œuvre ne laisse pas
nous redimensionner le tableau, parce que l'utilisation

259
00:12:19,000 --> 00:12:21,240
cette syntaxe, si vous
penser à la deuxième semaine,

260
00:12:21,240 --> 00:12:23,520
une fois que vous avez déclaré
la taille d'un tableau,

261
00:12:23,520 --> 00:12:26,780
nous avons pas encore vu où un mécanisme
vous pouvez changer la taille du tableau.

262
00:12:26,780 --> 00:12:29,020
Et en effet, C n'a pas cette fonctionnalité.

263
00:12:29,020 --> 00:12:32,524
Si vous dites me donner cinq
NTHS, appeler les numéros,

264
00:12:32,524 --> 00:12:33,940
voilà tout, vous allez obtenir.

265
00:12:33,940 --> 00:12:38,790
Donc, nous faisons maintenant à partir de lundi, avons
la capacité à exprimer une solution

266
00:12:38,790 --> 00:12:42,480
cependant, nous avons juste besoin de tordre
la définition de notre pile

267
00:12:42,480 --> 00:12:46,840
de ne pas être d'un tableau codé en dur,
mais juste pour stocker une adresse.

268
00:12:46,840 --> 00:12:47,890
>> Maintenant, pourquoi est-ce?

269
00:12:47,890 --> 00:12:51,690
Maintenant, nous devons juste être à l'aise avec
le fait que lorsque mon programme court,

270
00:12:51,690 --> 00:12:53,730
Je vais sans doute
avoir à demander l'humain,

271
00:12:53,730 --> 00:12:55,110
combien de numéros voulez-vous stocker?

272
00:12:55,110 --> 00:12:56,776
Donc, l'entrée doit venir de quelque part.

273
00:12:56,776 --> 00:12:59,140
Mais une fois que je sais que
nombre, alors je peux juste

274
00:12:59,140 --> 00:13:02,470
utiliser ce fonctionnement pour donner
moi un morceau de la mémoire?

275
00:13:02,470 --> 00:13:03,580
Je peux utiliser malloc.

276
00:13:03,580 --> 00:13:06,710
Et je peux dire un certain nombre de
octets Je veux revenir pour ces NTHS.

277
00:13:06,710 --> 00:13:10,910
Et tout ce que je dois stocker dans les numéros
la variable ici à l'intérieur de cette structure

278
00:13:10,910 --> 00:13:13,480
devrait être quoi?

279
00:13:13,480 --> 00:13:18,440
Ce qui se passe réellement dans le
numéros dans ce scénario?

280
00:13:18,440 --> 00:13:21,300
Oui, un pointeur vers le premier
octet de ce morceau de mémoire,

281
00:13:21,300 --> 00:13:24,940
ou plus spécifiquement, l'adresse
du premier de ces octets.

282
00:13:24,940 --> 00:13:27,300
N'a pas d'importance si elle est l'un
octets ou un milliard d'octets,

283
00:13:27,300 --> 00:13:28,890
Je dois juste se soucier de la première.

284
00:13:28,890 --> 00:13:31,530
Parce que ce que les garanties de malloc et
mes garanties de système d'exploitation,

285
00:13:31,530 --> 00:13:34,170
est ce que le bloc de mémoire que je
obtenir, ça va être contigus.

286
00:13:34,170 --> 00:13:35,378
Il ne va pas y avoir des lacunes.

287
00:13:35,378 --> 00:13:38,576
Donc, si je l'ai demandé 50
octets ou 1000 octets,

288
00:13:38,576 --> 00:13:40,450
ils vont tous être
dos à dos à dos.

289
00:13:40,450 --> 00:13:44,500
Et aussi longtemps que je me souviens comment grand, comment
que je demandais, tout ce que je dois savoir

290
00:13:44,500 --> 00:13:46,230
est la première adresse.

291
00:13:46,230 --> 00:13:48,660
>> Alors maintenant, nous avons la capacité dans le code.

292
00:13:48,660 --> 00:13:51,280
Quoique, ça va nous prendre
plus de temps pour écrire cette place,

293
00:13:51,280 --> 00:13:55,900
nous pourrions maintenant réaffecter que la mémoire par
simplement mémoriser une adresse différente il

294
00:13:55,900 --> 00:13:59,060
si nous voulons une plus grande ou même
un morceau plus petit de la mémoire.

295
00:13:59,060 --> 00:14:00,170
Donc ici pour un hors commerce.

296
00:14:00,170 --> 00:14:01,360
Maintenant, nous arrivons dynamisme.

297
00:14:01,360 --> 00:14:03,350
Nous avons toujours
contiguousness Je prétendant.

298
00:14:03,350 --> 00:14:05,881
Parce que malloc nous donnera
un morceau de la mémoire contiguë.

299
00:14:05,881 --> 00:14:08,630
Mais cela va être une douleur dans
le cou pour nous, le programmeur,

300
00:14:08,630 --> 00:14:09,770
à coder réellement.

301
00:14:09,770 --> 00:14:10,730
Il est juste plus de travail.

302
00:14:10,730 --> 00:14:13,930
Nous avons besoin d'un code semblable à ce que je faisais
taper sur il ya un instant.

303
00:14:13,930 --> 00:14:16,120
Très faisable, mais il ajoute à la complexité.

304
00:14:16,120 --> 00:14:19,520
Et donc le temps de développeur, programmeur
Il est encore une autre ressource

305
00:14:19,520 --> 00:14:22,520
que nous pourrions avoir besoin de dépenser
peu de temps pour obtenir de nouvelles fonctionnalités.

306
00:14:22,520 --> 00:14:24,020
Et puis bien sûr il ya une file d'attente.

307
00:14:24,020 --> 00:14:26,227
Nous ne rentrerons pas dans ce
un dans beaucoup de détails.

308
00:14:26,227 --> 00:14:27,560
Mais il est très similaire dans l'esprit.

309
00:14:27,560 --> 00:14:31,220
Je pourrais mettre en œuvre une file d'attente, et
ses opérations correspondantes,

310
00:14:31,220 --> 00:14:35,660
enqueue ou dequeue, comme ajouter ou supprimer,
il est juste une façon de dire qu'il colombophile,

311
00:14:35,660 --> 00:14:38,100
enqueue ou dequeue, comme suit.

312
00:14:38,100 --> 00:14:41,170
Je peux juste me donner une struct
a cette fois le tableau d'un certain nombre,

313
00:14:41,170 --> 00:14:44,000
a cette fois une taille,
mais pourquoi dois-je maintenant

314
00:14:44,000 --> 00:14:46,940
de garder une trace de l'avant de la file d'attente?

315
00:14:46,940 --> 00:14:50,630
Je ne l'ai pas besoin de savoir
l'avant de ma pile.

316
00:14:50,630 --> 00:14:53,570
Eh bien, si je encore pour un
queue-- Disons simplement dur

317
00:14:53,570 --> 00:14:57,870
coder comme ayant comme cinq
entiers dans ici potentiellement.

318
00:14:57,870 --> 00:15:00,940
Donc, cela est zéro, un, deux, trois, quatre.

319
00:15:00,940 --> 00:15:03,430
Cela va être
appelé de nouveau les numéros.

320
00:15:03,430 --> 00:15:06,940
Et ce sera appelée taille.

321
00:15:06,940 --> 00:15:10,056
>> Pourquoi est-il ne suffit pas
d'avoir juste la taille?

322
00:15:10,056 --> 00:15:11,680
Eh bien, nous allons pousser ces mêmes numéros sur.

323
00:15:11,680 --> 00:15:14,220
Donc, je pushed-- je en file d'attente, ou poussé.

324
00:15:14,220 --> 00:15:20,150
Maintenant, je vais ENQUEUE 50, puis
51, puis 61, et Dot Dot Dot.

325
00:15:20,150 --> 00:15:21,070
Voilà donc enqueue.

326
00:15:21,070 --> 00:15:23,176
Je en file d'attente 50, puis 51, puis 61.

327
00:15:23,176 --> 00:15:25,050
Et cela semble identique
pour une pile à ce jour,

328
00:15:25,050 --> 00:15:27,190
sauf que je ne dois faire un changement.

329
00:15:27,190 --> 00:15:33,680
Je dois mettre à jour cette taille, donc je vais
de zéro à un à deux à trois maintenant.

330
00:15:33,680 --> 00:15:35,760
Comment puis-je DEQUEUE?

331
00:15:35,760 --> 00:15:36,890
Qu'est-ce qui se passe avec dequeue?

332
00:15:36,890 --> 00:15:41,950
Qui doit se détacher de cette première liste
si elle est la ligne sur l'Apple Store?

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

334
00:15:42,780 --> 00:15:44,700
Donc, il est un peu plus délicat cette fois.

335
00:15:44,700 --> 00:15:47,880
Considérant que la dernière fois qu'il a été super
facile de simplement faire la taille moins un,

336
00:15:47,880 --> 00:15:51,440
Je reçois à la fin de mon tableau efficacement
où les chiffres sont, il supprime 61.

337
00:15:51,440 --> 00:15:52,920
Mais je ne veux pas retirer 61.

338
00:15:52,920 --> 00:15:55,030
Je veux profiter de 50 ans, qui
était là à 5h00

339
00:15:55,030 --> 00:15:56,790
faire la queue pour le
nouvel iPhone ou autres joyeusetés.

340
00:15:56,790 --> 00:16:01,200
Et donc de se débarrasser des 50, je
ne peut pas simplement faire cela, non?

341
00:16:01,200 --> 00:16:02,547
Je peux rayer 50.

342
00:16:02,547 --> 00:16:04,380
Mais nous venons de dire, nous
ne doivent pas être si anal

343
00:16:04,380 --> 00:16:06,330
à gratter ou de masquer les données.

344
00:16:06,330 --> 00:16:08,090
Nous ne pouvons tout simplement d'oublier d'où il est.

345
00:16:08,090 --> 00:16:12,330
>> Mais si je change ma taille maintenant
deux, cette information est suffisante

346
00:16:12,330 --> 00:16:15,711
savoir ce qui se passait dans ma file d'attente?

347
00:16:15,711 --> 00:16:16,680
Pas vraiment.

348
00:16:16,680 --> 00:16:19,830
Comme ma taille est de deux, mais
où la file d'attente ne commencent,

349
00:16:19,830 --> 00:16:22,980
surtout si je dois encore
ces mêmes nombres dans la mémoire.

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

351
00:16:24,260 --> 00:16:27,090
Donc, je dois me rappeler
maintenant où le front est.

352
00:16:27,090 --> 00:16:29,630
Et comme je l'ai proposé jusqu'à
là, nous venons d'appeler

353
00:16:29,630 --> 00:16:33,729
Avant Nième, dont la première
valeur aurait dû être quoi?

354
00:16:33,729 --> 00:16:35,270
Zero, que le début de la liste.

355
00:16:35,270 --> 00:16:40,876
Mais maintenant, en plus de décrémentation
la taille, nous avons juste incrémenter l'avant.

356
00:16:40,876 --> 00:16:42,000
Maintenant, voici un autre problème.

357
00:16:42,000 --> 00:16:43,030
Donc, une fois je continue.

358
00:16:43,030 --> 00:16:47,520
Supposons que ce est le nombre de
comme 121, 124, puis, merde,

359
00:16:47,520 --> 00:16:48,610
Je suis hors de l'espace.

360
00:16:48,610 --> 00:16:50,390
Mais attendez une minute, je ne suis pas.

361
00:16:50,390 --> 00:16:55,630
Donc, à ce moment de l'histoire,
Supposons que la taille est un, deux,

362
00:16:55,630 --> 00:17:00,370
trois, quatre, de sorte que le supposer
la taille est de quatre, l'avant est un,

363
00:17:00,370 --> 00:17:01,621
donc 51 est à l'avant.

364
00:17:01,621 --> 00:17:04,329
Je veux mettre un autre numéro ici,
mais, bon sang, je suis hors de l'espace.

365
00:17:04,329 --> 00:17:06,710
Mais je ne suis pas vraiment, non?

366
00:17:06,710 --> 00:17:11,192
Où pourrais-je mettre un peu
valeur ajoutée, comme 171?

367
00:17:11,192 --> 00:17:13,400
Ouais, je pouvais juste genre de
revenir sur là, non?

368
00:17:13,400 --> 00:17:18,161
Et puis traverser le 50, ou
simplement le remplacer par 171.

369
00:17:18,161 --> 00:17:20,410
Et si vous vous demandez pourquoi
nos numéros se sont tellement aléatoire,

370
00:17:20,410 --> 00:17:24,150
ceux-ci sont souvent prises ordinateur
cours de sciences à Harvard après CS50.

371
00:17:24,150 --> 00:17:27,510
Mais ce fut une bonne optimisation,
parce que maintenant je ne suis pas gaspiller de l'espace.

372
00:17:27,510 --> 00:17:30,750
Je dois encore rappeler
l'ampleur de cette chose est totale.

373
00:17:30,750 --> 00:17:31,500
Il est cinq heures au total.

374
00:17:31,500 --> 00:17:33,375
Parce que je ne veux pas
commencera à remplacer les 51.

375
00:17:33,375 --> 00:17:36,260
Alors maintenant, je suis encore plus d'espace,
de sorte que le même problème que précédemment.

376
00:17:36,260 --> 00:17:39,140
Mais vous pouvez voir comment l'entreprise
dans votre code, vous avez probablement

377
00:17:39,140 --> 00:17:41,910
avoir à l'écrire un peu plus
la complexité de faire que cela se produise.

378
00:17:41,910 --> 00:17:44,510
Et en fait, ce que l'opérateur
en C permet probablement

379
00:17:44,510 --> 00:17:48,110
vous faites cette magie la circularité?

380
00:17:48,110 --> 00:17:50,160
Ouais l'opérateur modulo,
le signe pour cent.

381
00:17:50,160 --> 00:17:53,160
Alors, quel est plutôt cool sur une file d'attente,
même si nous gardons les tableaux de dessin

382
00:17:53,160 --> 00:17:56,520
que ces lignes droites comme, si vous
sorte de penser à cela comme courbe

383
00:17:56,520 --> 00:18:00,341
autour d'un cercle, puis juste
intuitivement cela fonctionne sorte de mental

384
00:18:00,341 --> 00:18:01,590
Je pense un peu plus proprement.

385
00:18:01,590 --> 00:18:05,190
Vous auriez encore à mettre en œuvre
ce modèle mentale dans le code.

386
00:18:05,190 --> 00:18:07,550
Donc, pas si difficile,
en fin de compte, à mettre en oeuvre,

387
00:18:07,550 --> 00:18:12,430
mais nous perdons toujours le size-- plutôt la
possibilité de redimensionner, à moins que nous faisons cela.

388
00:18:12,430 --> 00:18:15,310
>> Nous devons nous débarrasser de la matrice, nous
le remplacer par un seul pointeur,

389
00:18:15,310 --> 00:18:20,010
puis quelque part dans mon code, je dois
Un appel qui fonctionne pour créer réellement

390
00:18:20,010 --> 00:18:23,720
le tableau des numéros appelés?

391
00:18:23,720 --> 00:18:26,190
Malloc, ou quelques similaires
fonction, exactement.

392
00:18:26,190 --> 00:18:30,481
Des questions sur piles ou des files d'attente.

393
00:18:30,481 --> 00:18:30,980
Ouais?

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

395
00:18:33,657 --> 00:18:34,240
Bonne question.

396
00:18:34,240 --> 00:18:35,830
Que voulez-vous utiliser modulo ici.

397
00:18:35,830 --> 00:18:38,520
Donc, en général, lors de l'utilisation
mod, vous ferait

398
00:18:38,520 --> 00:18:40,620
avec la taille de la
structure de données ensemble.

399
00:18:40,620 --> 00:18:44,120
Donc, quelque chose comme cinq ou capacité, si
il est constant, est probablement impliqué.

400
00:18:44,120 --> 00:18:47,100
Mais juste faire modulo cinq
est sans doute pas suffisante,

401
00:18:47,100 --> 00:18:51,380
parce que nous devons savoir faire nous
enrouler autour ici ou ici ou ici.

402
00:18:51,380 --> 00:18:54,160
Donc, vous êtes probablement aussi
allez vouloir impliquer

403
00:18:54,160 --> 00:18:57,220
la taille de la chose, ou
la variable avant ainsi.

404
00:18:57,220 --> 00:19:00,140
Donc, il est juste ce relativement
expression arithmétique simple,

405
00:19:00,140 --> 00:19:02,000
mais modulo serait l'ingrédient clé.

406
00:19:02,000 --> 00:19:03,330
>> Donc court métrage si vous voulez.

407
00:19:03,330 --> 00:19:05,780
Une animation que certaines
les gens d'une autre université

408
00:19:05,780 --> 00:19:08,060
mettons ensemble que nous avons
adapté à cette discussion.

409
00:19:08,060 --> 00:19:12,630
Elle implique l'apprentissage de la Jack
faits sur les files d'attente et les statistiques.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Il était une fois,
il y avait un gars nommé Jack.

412
00:19:21,890 --> 00:19:25,330
Quand il est venu à se faire des amis,
Jack n'a pas de talent.

413
00:19:25,330 --> 00:19:28,220
Donc, Jack est allé parler à la
plus gars populaire qu'il savait.

414
00:19:28,220 --> 00:19:30,920
Il est allé à Lou et a demandé, Que dois-je faire?

415
00:19:30,920 --> 00:19:33,400
Lou a vu que son ami
était vraiment en détresse.

416
00:19:33,400 --> 00:19:36,050
Eh bien, il a commencé, juste
regardez comment vous êtes habillé.

417
00:19:36,050 --> 00:19:38,680
Ne vous avez des vêtements
avec un regard différent?

418
00:19:38,680 --> 00:19:39,660
Oui, dit Jack.

419
00:19:39,660 --> 00:19:40,840
Je fais bien sûr.

420
00:19:40,840 --> 00:19:43,320
Venez à ma maison et
Je vais leur montrer à vous.

421
00:19:43,320 --> 00:19:44,550
Ils partirent donc à Jack.

422
00:19:44,550 --> 00:19:47,520
Et Jack a montré Lou la boîte
où il a gardé toutes ses chemises,

423
00:19:47,520 --> 00:19:49,260
et son pantalon, et ses chaussettes.

424
00:19:49,260 --> 00:19:52,290
Lou a dit: Je vois que vous avez
tous vos vêtements dans un tas.

425
00:19:52,290 --> 00:19:54,870
Pourquoi ne portez-vous pas un peu
d'autres de temps en temps?

426
00:19:54,870 --> 00:19:58,020
>> Jack dit, eh bien, quand je
enlever les vêtements et les chaussettes,

427
00:19:58,020 --> 00:20:00,780
Je les lave et mets
les dans la boîte.

428
00:20:00,780 --> 00:20:03,210
Vient ensuite la prochaine
matin, et jusqu'à je hop.

429
00:20:03,210 --> 00:20:06,380
Je vais à la boîte et obtiens
mes vêtements sur le haut.

430
00:20:06,380 --> 00:20:09,070
Lou a rapidement réalisé
le problème avec Jack.

431
00:20:09,070 --> 00:20:12,080
Il a gardé des vêtements, des CD,
et des livres de la pile.

432
00:20:12,080 --> 00:20:14,420
Quand il a atteint pour
quelque chose à lire ou à l'usure,

433
00:20:14,420 --> 00:20:17,100
il choisirait le livre dessus ou sous-vêtements.

434
00:20:17,100 --> 00:20:19,500
Puis, quand il a été fait, il
mettrait le droit de retour.

435
00:20:19,500 --> 00:20:21,970
Retour il irait, sur le dessus de la pile.

436
00:20:21,970 --> 00:20:24,460
Je sais que la solution,
dit un fort triomphante.

437
00:20:24,460 --> 00:20:27,090
Vous devez apprendre à
commencer à utiliser une file d'attente.

438
00:20:27,090 --> 00:20:29,870
Lou a pris les vêtements de Jack et
les pendu dans le placard.

439
00:20:29,870 --> 00:20:32,710
Et quand il avait vidé
la boîte, il a juste le lança.

440
00:20:32,710 --> 00:20:36,500
>> Puis il dit, maintenant Jack, à la fin de
le jour, mettez vos vêtements sur la gauche

441
00:20:36,500 --> 00:20:37,990
quand vous mettez les éloigner.

442
00:20:37,990 --> 00:20:41,300
Puis demain matin lorsque vous
voir le soleil, vos vêtements

443
00:20:41,300 --> 00:20:43,440
sur la droite, à partir de la fin de la ligne.

444
00:20:43,440 --> 00:20:44,880
Ne voyez-vous pas? a déclaré Lou.

445
00:20:44,880 --> 00:20:46,370
Ce sera tellement agréable.

446
00:20:46,370 --> 00:20:49,770
Vous portez une fois tout
avant que vous portez quelque chose deux fois.

447
00:20:49,770 --> 00:20:52,670
Et avec tout dans les files d'attente
dans son placard et étagère,

448
00:20:52,670 --> 00:20:55,160
Jack a commencé à se sentir
tout à fait sûr de lui-même.

449
00:20:55,160 --> 00:20:59,720
Tout cela grâce à Lou et
sa merveilleuse file d'attente.

450
00:20:59,720 --> 00:21:01,220
ENCEINTE 1: Très bien, il est adorable.

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

452
00:21:05,920 --> 00:21:10,080
Donc, ce qui a été vraiment va
sur sous le capot maintenant?

453
00:21:10,080 --> 00:21:12,370
Que nous avons des pointeurs,
que nous avons malloc,

454
00:21:12,370 --> 00:21:15,680
que nous avons la capacité de créer
morceaux de mémoire pour nous

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

456
00:21:16,344 --> 00:21:18,510
Donc, ce que nous est une image
entrevu l'autre jour.

457
00:21:18,510 --> 00:21:21,180
Nous ne sommes pas vraiment demeurons
sur elle, mais cette image

458
00:21:21,180 --> 00:21:24,180
a été en dessous de passe
le capot pendant des semaines maintenant.

459
00:21:24,180 --> 00:21:27,050
Et cela représente donc, juste
un rectangle que nous avons établi,

460
00:21:27,050 --> 00:21:28,180
la mémoire de votre ordinateur.

461
00:21:28,180 --> 00:21:31,850
Et peut-être votre ordinateur, ou CS50
ID, dispose d'un gigaoctet de mémoire vive ou RAM

462
00:21:31,850 --> 00:21:33,050
ou deux gigaoctets ou quatre.

463
00:21:33,050 --> 00:21:34,450
Il n'a pas vraiment d'importance.

464
00:21:34,450 --> 00:21:37,240
Votre système d'exploitation
Windows ou Mac OS ou Linux,

465
00:21:37,240 --> 00:21:41,120
permet essentiellement votre programme
à penser qu'il a accès

466
00:21:41,120 --> 00:21:42,982
pour la totalité de
la mémoire de votre ordinateur,

467
00:21:42,982 --> 00:21:45,440
même si vous pourriez exécuter
plusieurs programmes à la fois.

468
00:21:45,440 --> 00:21:46,990
Donc, en réalité, cela ne fonctionne pas vraiment.

469
00:21:46,990 --> 00:21:49,448
Mais il est une sorte d'illusion
donné à tous vos programmes.

470
00:21:49,448 --> 00:21:53,110
Donc, si vous aviez deux concerts de RAM, ce
est de savoir comment l'ordinateur peut penser.

471
00:21:53,110 --> 00:21:57,110
>> Maintenant, par hasard, l'un de ces
choses, l'un de ces segments de mémoire,

472
00:21:57,110 --> 00:21:58,350
est appelée une pile.

473
00:21:58,350 --> 00:22:01,680
Et en effet tout moment
à ce jour dans l'écriture de code

474
00:22:01,680 --> 00:22:05,900
que vous avez appelé un
fonction, par exemple principal.

475
00:22:05,900 --> 00:22:08,410
Rappelons que chaque fois que je l'ai
la mémoire de l'ordinateur dessinée,

476
00:22:08,410 --> 00:22:10,640
Je dessine toujours sorte de
la moitié d'un rectangle ici

477
00:22:10,640 --> 00:22:12,520
et ne vous embêtez pas à parler
sur ce qui est ci-dessus.

478
00:22:12,520 --> 00:22:15,980
Parce que quand principale est appelée, je prétends
que vous obtenez ce ruban de mémoire

479
00:22:15,980 --> 00:22:16,970
qui descend ici.

480
00:22:16,970 --> 00:22:20,650
Et si principale appelée fonction
comme swap, ainsi échange va ici.

481
00:22:20,650 --> 00:22:23,720
Et il se trouve, qui est
où il est de se retrouver.

482
00:22:23,720 --> 00:22:26,277
Sur ce qu'on appelle une pile
l'intérieur de la mémoire de votre ordinateur.

483
00:22:26,277 --> 00:22:28,360
Or, à la fin de la journée,
cette adresse est juste.

484
00:22:28,360 --> 00:22:30,680
Il est comme octet nul,
un octet, l'octet 2 milliards de dollars.

485
00:22:30,680 --> 00:22:33,130
Mais si vous pensez à ce sujet
que cet objet rectangulaire,

486
00:22:33,130 --> 00:22:35,130
tout ce que nous faisons tous les
fois que nous appelons une fonction est

487
00:22:35,130 --> 00:22:37,180
superposition d'une nouvelle tranche de mémoire.

488
00:22:37,180 --> 00:22:41,700
Nous donnons à cette fonction une tranche
de sa propre mémoire pour travailler avec.

489
00:22:41,700 --> 00:22:44,490
>> Et maintenant rappeler que cela est important.

490
00:22:44,490 --> 00:22:46,400
Parce que si nous ne disposons
quelque chose comme de swap

491
00:22:46,400 --> 00:22:51,610
et deux variables locales telles que A et B et
nous changeons les valeurs d'un et deux

492
00:22:51,610 --> 00:22:55,130
à deux et un, le rappel
que lorsque swap de revient,

493
00:22:55,130 --> 00:22:58,330
il est comme si cette tranche
de mémoire est tout simplement disparu.

494
00:22:58,330 --> 00:23:00,080
En réalité, il est toujours
il médicolégal.

495
00:23:00,080 --> 00:23:01,940
Et quelque chose est encore vraiment là.

496
00:23:01,940 --> 00:23:05,410
Mais conceptuellement, il est aussi
si elle est complètement disparu.

497
00:23:05,410 --> 00:23:10,910
Et principale ne sait pas tout le travail
cela a été fait dans cette fonction d'échange,

498
00:23:10,910 --> 00:23:14,890
sauf si elle est effectivement passé dans les
arguments par pointeur ou par référence.

499
00:23:14,890 --> 00:23:17,790
Maintenant, la solution fondamentale
à ce problème avec l'échange d'

500
00:23:17,790 --> 00:23:19,970
se passe des choses dans d'adresse.

501
00:23:19,970 --> 00:23:23,250
Mais il se trouve, aussi, ce qui est
été passe au-dessus de la partie

502
00:23:23,250 --> 00:23:26,330
du rectangle tout ce temps est
Pourtant, il ya plus de mémoire là-haut.

503
00:23:26,330 --> 00:23:28,790
Et quand vous dynamiquement
allouer de la mémoire,

504
00:23:28,790 --> 00:23:32,020
si elle est à l'intérieur de GetString, qui
nous avons fait pour vous dans le CS50

505
00:23:32,020 --> 00:23:34,710
bibliothèque, ou si vous les gars
appeler malloc et demander

506
00:23:34,710 --> 00:23:37,950
le système d'exploitation pour un morceau de
mémoire, il ne vient pas de la pile.

507
00:23:37,950 --> 00:23:40,960
Il vient d'un autre lieu
dans la mémoire de votre ordinateur

508
00:23:40,960 --> 00:23:42,220
qui est ce qu'on appelle le tas.

509
00:23:42,220 --> 00:23:43,430
Et ce ne est pas différent.

510
00:23:43,430 --> 00:23:44,285
Il en est de même de RAM.

511
00:23:44,285 --> 00:23:45,160
Il est la même mémoire.

512
00:23:45,160 --> 00:23:49,080
Il est juste de la RAM qui est en place
il lieu d'ici-bas.

513
00:23:49,080 --> 00:23:50,750
>> Et qu'est-ce que cela signifie?

514
00:23:50,750 --> 00:23:53,650
Eh bien, si votre ordinateur possède
une quantité limitée de mémoire

515
00:23:53,650 --> 00:23:57,450
et la pile grandit, donc
de parler, et le tas, selon

516
00:23:57,450 --> 00:23:59,349
à cette flèche, est de plus en plus bas.

517
00:23:59,349 --> 00:24:01,140
En d'autres termes, chaque
fois que vous appelez malloc,

518
00:24:01,140 --> 00:24:03,430
vous étant donné une tranche
de mémoire à partir de ci-dessus,

519
00:24:03,430 --> 00:24:06,630
alors peut-être un peu plus bas, puis un peu
inférieur, à chaque fois que vous appelez malloc,

520
00:24:06,630 --> 00:24:10,100
le tas, il est l'utilisation,
est une sorte de croissant,

521
00:24:10,100 --> 00:24:11,950
de plus en plus de proche en proche à quoi?

522
00:24:11,950 --> 00:24:13,382
La pile.

523
00:24:13,382 --> 00:24:14,840
Donc, cela semble être une bonne idée?

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

525
00:24:18,420 --> 00:24:22,140
Je veux dire, où il est pas vraiment clair
ce que vous pouvez faire si vous ne

526
00:24:22,140 --> 00:24:23,910
avoir une quantité limitée de mémoire.

527
00:24:23,910 --> 00:24:25,200
Mais cela est certainement mauvais.

528
00:24:25,200 --> 00:24:27,920
Ces deux flèches sont sur un
Crash Course pour l'autre.

529
00:24:27,920 --> 00:24:31,930
>> Et il se trouve que méchant, les gens qui
sont particulièrement bonnes avec la programmation,

530
00:24:31,930 --> 00:24:36,140
et d'essayer de pirater des ordinateurs,
peut exploiter cette réalité.

531
00:24:36,140 --> 00:24:38,290
En fait, nous allons examiner
un petit extrait.

532
00:24:38,290 --> 00:24:41,350
Donc, ceci est un exemple que vous pouvez lire
environ plus en détail sur Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Nous vous indiquerons au
article si curieux.

534
00:24:43,100 --> 00:24:45,650
Mais il ya une attaque générale
connu comme dépassement de tampon qui

535
00:24:45,650 --> 00:24:49,570
existe aussi longtemps que les humains
ont eu la possibilité de manipuler

536
00:24:49,570 --> 00:24:53,120
la mémoire de l'ordinateur, en particulier en C.
Donc, ce programme est très arbitraire,

537
00:24:53,120 --> 00:24:55,130
mais nous allons le lire de bas en haut.

538
00:24:55,130 --> 00:24:57,650
Principale dans argC omble étoiles argv.

539
00:24:57,650 --> 00:24:59,830
Donc, il est un programme qui prend
arguments de ligne de commande.

540
00:24:59,830 --> 00:25:03,620
Et tout ne principale est apparemment appel
une fonction, appeler F pour plus de simplicité.

541
00:25:03,620 --> 00:25:04,610
Et il passe en quoi?

542
00:25:04,610 --> 00:25:05,490
Argv d'un.

543
00:25:05,490 --> 00:25:09,320
Donc, il passe dans ce que F
le mot est que l'utilisateur a tapé

544
00:25:09,320 --> 00:25:11,500
à l'invite après la
le nom de programme du tout.

545
00:25:11,500 --> 00:25:15,730
Donc, un peu comme César ou Vigenère, qui
vous pourriez faire rappeler avec argv.

546
00:25:15,730 --> 00:25:16,680
>> Alors, quelle est F?

547
00:25:16,680 --> 00:25:19,760
F prend dans une chaîne
que son seul argument,

548
00:25:19,760 --> 00:25:22,100
Alias ​​une star de char, même
chose, comme une chaîne.

549
00:25:22,100 --> 00:25:24,920
Et il a appelé arbitrairement
bar dans cet exemple.

550
00:25:24,920 --> 00:25:27,710
Et puis char c 12,
seulement en termes simples,

551
00:25:27,710 --> 00:25:31,750
ce qui est char c support 12 faire pour nous?

552
00:25:31,750 --> 00:25:33,440
Qu'est-ce qu'il fait?

553
00:25:33,440 --> 00:25:36,490
Allocation de mémoire, en particulier
12 octets pour 12 caractères.

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

555
00:25:36,990 --> 00:25:40,000
Et puis la dernière ligne, remuer et
copie, vous avez sans doute pas vu.

556
00:25:40,000 --> 00:25:43,360
Ceci est une copie de chaîne
fonction dont le but dans la vie

557
00:25:43,360 --> 00:25:48,160
est de copier son deuxième argument
dans son premier argument,

558
00:25:48,160 --> 00:25:51,190
mais seulement jusqu'à un
certain nombre d'octets.

559
00:25:51,190 --> 00:25:53,860
Ainsi, le troisième argument dit,
combien d'octets vous devez copier?

560
00:25:53,860 --> 00:25:56,720
La longueur de la barre,
quelle que soit l'utilisateur a tapé dans.

561
00:25:56,720 --> 00:25:59,320
Et le contenu de
bar, cette chaîne, sont

562
00:25:59,320 --> 00:26:02,330
copié dans la mémoire pointé au C.

563
00:26:02,330 --> 00:26:04,060
>> Donc, cela semble un peu stupide, et il est.

564
00:26:04,060 --> 00:26:06,300
Il est un exemple artificiel,
mais il est représentatif

565
00:26:06,300 --> 00:26:10,100
d'une classe de vecteurs d'attaque,
une façon d'attaquer un programme.

566
00:26:10,100 --> 00:26:15,050
Tout est beau et bon si l'utilisateur
types dans un mot qui est 11 caractères

567
00:26:15,050 --> 00:26:18,040
ou moins, ainsi que la barre oblique inverse zéro.

568
00:26:18,040 --> 00:26:22,830
Que faire si les types d'utilisateurs dans plus de
11 ou 12 ou 20 ou 50 caractères?

569
00:26:22,830 --> 00:26:25,090
Quel est ce programme va faire?

570
00:26:25,090 --> 00:26:29,360
Faute potentiellement seg. Ça va
de copier aveuglément tout en bar jusqu'à

571
00:26:29,360 --> 00:26:31,750
à sa longueur, qui est
littéralement tout en bar,

572
00:26:31,750 --> 00:26:36,307
dans l'adresse pointée à C. Mais C
a seulement préventivement donné que 12 octets.

573
00:26:36,307 --> 00:26:37,640
Mais il n'y a pas de vérification supplémentaire.

574
00:26:37,640 --> 00:26:38,700
Il n'y a pas si les conditions.

575
00:26:38,700 --> 00:26:40,580
Il n'y a pas ici de vérifier l'erreur.

576
00:26:40,580 --> 00:26:43,270
>> Et donc ce que ce programme est
va faire est aveuglément

577
00:26:43,270 --> 00:26:45,750
copier une chose à l'autre.

578
00:26:45,750 --> 00:26:47,880
Et si nous tirons cette
comme une image, voici

579
00:26:47,880 --> 00:26:49,860
juste un petit morceau de l'espace mémoire.

580
00:26:49,860 --> 00:26:53,470
Donc remarquons au fond, nous
avoir la barre variable locale.

581
00:26:53,470 --> 00:26:57,330
Donc, ce pointeur qui va store--
plutôt cet argument locale qui est

582
00:26:57,330 --> 00:26:58,672
allez stocker la barre de chaîne.

583
00:26:58,672 --> 00:27:00,380
Et puis notez simplement
au-dessus d'une pile,

584
00:27:00,380 --> 00:27:02,505
parce que chaque fois que vous demandez
pour la mémoire sur la pile,

585
00:27:02,505 --> 00:27:04,310
il va un peu
au-dessus imagé,

586
00:27:04,310 --> 00:27:06,270
Notez que nous avons 12 octets il.

587
00:27:06,270 --> 00:27:10,690
L'un en haut à gauche est C support de zéro et
celui en bas à droite est C support 11.

588
00:27:10,690 --> 00:27:12,870
Voilà à quel point les ordinateurs
va jeter dehors.

589
00:27:12,870 --> 00:27:18,300
Il suffit donc intuitivement, si la barre a plus
de 12 caractères au total, y compris

590
00:27:18,300 --> 00:27:25,790
la barre oblique inverse zéro, où est le
12 ou le support de C 12 va aller?

591
00:27:25,790 --> 00:27:28,440
Ou plutôt où est le 12e
caractère ou le caractère 13,

592
00:27:28,440 --> 00:27:30,900
le caractère centième aller
pour finir dans l'image?

593
00:27:30,900 --> 00:27:33,400
Dessus ou en dessous?

594
00:27:33,400 --> 00:27:36,300
>> Droit, parce que même si
la pile se pousse vers le haut,

595
00:27:36,300 --> 00:27:39,590
une fois que vous avez mis des choses dans
ce, pour des raisons de conception,

596
00:27:39,590 --> 00:27:41,294
met la mémoire de haut en bas.

597
00:27:41,294 --> 00:27:44,460
Donc, si vous avez plus de 12 octets,
vous allez commencer à remplacer bar.

598
00:27:44,460 --> 00:27:47,280
Voilà un bug, mais il est
pas vraiment un gros problème.

599
00:27:47,280 --> 00:27:51,130
Mais il est un gros problème, car il ya
plus de choses se passe dans la mémoire.

600
00:27:51,130 --> 00:27:53,074
Alors, voici comment nous pourrions
mettre bonjour, pour être clair.

601
00:27:53,074 --> 00:27:54,490
Si je tapé dans bonjour à l'invite.

602
00:27:54,490 --> 00:27:59,330
Barre oblique inverse zéro H-E-L-L-O, finit dans les
ces 12 octets, et nous sommes très sûr.

603
00:27:59,330 --> 00:28:00,330
Tout est bien.

604
00:28:00,330 --> 00:28:03,020
Mais si je tape quelque chose
plus, il est potentiellement

605
00:28:03,020 --> 00:28:05,860
va glisser dans l'espace bar.

606
00:28:05,860 --> 00:28:08,405
Mais pire encore, il se
sur tout ce temps,

607
00:28:08,405 --> 00:28:11,530
même si nous ne l'avons jamais parlé
elle, la pile est utilisé pour d'autres choses.

608
00:28:11,530 --> 00:28:13,560
Il n'y a pas que les variables locales.

609
00:28:13,560 --> 00:28:15,100
>> C est un langage de très faible niveau.

610
00:28:15,100 --> 00:28:17,810
Et ce genre de secret
utilise la pile aussi

611
00:28:17,810 --> 00:28:21,260
se souvenir quand un
fonction est appelée, ce qui

612
00:28:21,260 --> 00:28:26,040
l'adresse est de la fonction précédente,
de sorte qu'il peut revenir en arrière à cette fonction.

613
00:28:26,040 --> 00:28:29,980
Ainsi, lorsque les appels principaux échanger, entre
les choses ont poussé sur la pile

614
00:28:29,980 --> 00:28:34,380
ne sont pas simplement les swaps variables locales,
ou de ses arguments, aussi secrètement poussé

615
00:28:34,380 --> 00:28:37,510
sur la pile comme représenté
par la tranche rouge ici,

616
00:28:37,510 --> 00:28:40,520
est l'adresse du principal physiquement
dans la mémoire de votre ordinateur,

617
00:28:40,520 --> 00:28:44,180
de sorte que lorsque swap est fait, l'ordinateur
sait que je dois retourner au principal

618
00:28:44,180 --> 00:28:46,760
et terminer l'exécution de la fonction principale.

619
00:28:46,760 --> 00:28:51,960
Donc, cela est dangereux maintenant, parce que si
les types d'utilisateurs dans plus de bien bonjour,

620
00:28:51,960 --> 00:28:57,030
de telle sorte que l'entrée de l'utilisateur aplatit
ou remplace cette section rouge,

621
00:28:57,030 --> 00:28:59,820
logiquement, si de l'ordinateur
juste aller à assumer aveuglément

622
00:28:59,820 --> 00:29:03,830
que les octets dans cette tranche rouge sont
l'adresse à laquelle elle doit retourner,

623
00:29:03,830 --> 00:29:09,020
si l'adversaire est assez intelligent ou
la chance de mettre une séquence d'octets

624
00:29:09,020 --> 00:29:13,450
il qui ressemble à une adresse,
mais il est l'adresse du Code

625
00:29:13,450 --> 00:29:18,730
qu'il ou elle veut l'ordinateur
à exécuter au lieu de principale?

626
00:29:18,730 --> 00:29:21,670
>> En d'autres termes, si ce que le
utilisateur tape à l'invite,

627
00:29:21,670 --> 00:29:23,850
est pas seulement quelque chose
comme inoffensive bonjour,

628
00:29:23,850 --> 00:29:28,210
mais il est en fait le code qui est équivalent
supprimer tous les fichiers de cet utilisateur?

629
00:29:28,210 --> 00:29:30,060
Ou envoyer leur mot de passe pour moi?

630
00:29:30,060 --> 00:29:31,940
Ou commencer à enregistrer leur
frappes, non?

631
00:29:31,940 --> 00:29:34,920
Il ya une façon, disons stipulent aujourd'hui,
qu'ils pouvaient saisir non seulement bonjour

632
00:29:34,920 --> 00:29:36,711
monde ou de leur nom,
qu'ils pouvaient essentiellement

633
00:29:36,711 --> 00:29:39,570
passer dans le code, et de zéros
celles que l'ordinateur

634
00:29:39,570 --> 00:29:43,450
erreurs à la fois le code et une adresse.

635
00:29:43,450 --> 00:29:48,950
Donc, bien que quelque peu abstraite, si le
types d'utilisateurs en code assez contradictoire

636
00:29:48,950 --> 00:29:52,330
que nous allons généralisons ici
A. A est l'attaque ou adversaires.

637
00:29:52,330 --> 00:29:53,140
Il suffit donc de mauvaises choses.

638
00:29:53,140 --> 00:29:55,306
Nous ne nous soucions pas de la
les numéros ou les zéros ou

639
00:29:55,306 --> 00:29:59,470
aujourd'hui, de telle sorte que vous vous retrouvez
écraser cette section rouge,

640
00:29:59,470 --> 00:30:01,580
remarquerez que séquence d'octets.

641
00:30:01,580 --> 00:30:05,020
O 835 C zéro huit zéro.

642
00:30:05,020 --> 00:30:08,960
Et maintenant, comme l'article de Wikipedia ici
a proposé, si vous commencez maintenant réalité

643
00:30:08,960 --> 00:30:12,460
étiqueter les octets dans votre ordinateur de
la mémoire, ce que l'article de Wikipedia est

644
00:30:12,460 --> 00:30:19,060
proposante est que, si l'adresse
de l'octet haut à gauche est 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> En d'autres termes, si le méchant est
assez intelligent avec son code

646
00:30:22,200 --> 00:30:26,650
de mettre réellement un certain nombre ici que
correspond à l'adresse du code

647
00:30:26,650 --> 00:30:29,180
il ou elle injecté
dans l'ordinateur, vous

648
00:30:29,180 --> 00:30:31,050
peut tromper l'ordinateur
en faire quelque chose.

649
00:30:31,050 --> 00:30:34,140
Suppression de fichiers, e-mailing
choses, renifler votre trafic,

650
00:30:34,140 --> 00:30:36,710
littéralement tout ce que pourrait être
injecté dans l'ordinateur.

651
00:30:36,710 --> 00:30:39,220
Et si un débordement de tampon
attaque à sa base

652
00:30:39,220 --> 00:30:43,530
est juste un stupide, stupide
impérieuse d'un tableau

653
00:30:43,530 --> 00:30:45,840
ne disposent pas de ses frontières vérifiés.

654
00:30:45,840 --> 00:30:48,850
Et voici ce que est super dangereux
et en même temps super puissant

655
00:30:48,850 --> 00:30:52,560
C est dans ce que nous avons en effet
l'accès à n'importe où dans la mémoire.

656
00:30:52,560 --> 00:30:55,320
Il est à nous, les programmeurs,
qui écrivent le code original

657
00:30:55,320 --> 00:30:59,330
pour vérifier la longueur de reprise de tout
tableaux que nous manipulation.

658
00:30:59,330 --> 00:31:00,750
Donc, pour être clair, quelle est la solution?

659
00:31:00,750 --> 00:31:03,190
Si nous revenir à cette
code, je ne devrais pas simplement

660
00:31:03,190 --> 00:31:08,000
changer la longueur de la barre, ce qui
dois-je vérifierai?

661
00:31:08,000 --> 00:31:10,620
Que dois-je faire pour
empêcher cette attaque entièrement?

662
00:31:10,620 --> 00:31:14,110
Je ne veux pas juste dire aveuglément
que vous devez copier autant d'octets

663
00:31:14,110 --> 00:31:16,140
comme l'est la longueur de la barre.

664
00:31:16,140 --> 00:31:18,910
Je tiens à dire, comme copier
le nombre d'octets que sont en bar

665
00:31:18,910 --> 00:31:24,090
jusqu'à la alloué
la mémoire, ou 12 au maximum.

666
00:31:24,090 --> 00:31:27,450
Donc je besoin d'une sorte de condition if
qui ne vérifie la longueur de la barre,

667
00:31:27,450 --> 00:31:32,800
mais si elle dépasse 12, on code juste dur
12 comme la distance maximale possible.

668
00:31:32,800 --> 00:31:35,910
Sinon le tampon dite
attaque de dépassement peut arriver.

669
00:31:35,910 --> 00:31:38,451
Au bas de ces lames,
Si vous êtes curieux de lire la suite

670
00:31:38,451 --> 00:31:41,200
est l'article original réel
Si vous souhaitez jeter un oeil.

671
00:31:41,200 --> 00:31:44,550
>> Mais maintenant, parmi les prix
payés ici était inefficacités.

672
00:31:44,550 --> 00:31:46,680
Ce qui fut une rapide
faible niveau look à quel

673
00:31:46,680 --> 00:31:49,709
des problèmes peuvent survenir maintenant que nous
avoir accès à la mémoire de l'ordinateur.

674
00:31:49,709 --> 00:31:51,750
Mais un autre problème que nous
déjà trébuché lundi

675
00:31:51,750 --> 00:31:53,800
était juste l'inefficacité
d'une liste chaînée.

676
00:31:53,800 --> 00:31:56,019
Nous sommes de retour à temps linéaire.

677
00:31:56,019 --> 00:31:57,560
Nous ne sommes plus un tableau contigu.

678
00:31:57,560 --> 00:31:58,980
Nous ne disposons pas accès aléatoire.

679
00:31:58,980 --> 00:32:00,710
Nous ne pouvons pas utiliser la notation crochet.

680
00:32:00,710 --> 00:32:04,590
Nous avons littéralement à utiliser une boucle while
comme celui que je écrit il ya un moment.

681
00:32:04,590 --> 00:32:09,740
Mais lundi, nous avons affirmé que nous pouvons
grimper à nouveau dans le domaine de l'efficacité

682
00:32:09,740 --> 00:32:13,040
la réalisation de quelque chose qui est
logarithmique peut-être, ou mieux encore,

683
00:32:13,040 --> 00:32:16,120
peut-être même quelque chose qui est
dite constante de temps.

684
00:32:16,120 --> 00:32:19,840
Alors, comment pouvons-nous le faire en utilisant ces nouveaux
outils, ces adresses, ces pointeurs,

685
00:32:19,840 --> 00:32:22,210
et le filetage choses de notre propre?

686
00:32:22,210 --> 00:32:23,960
Eh bien, supposons que
ici, ce sont un tas

687
00:32:23,960 --> 00:32:27,170
des nombres que nous voulons stocker dans un
structure de données et de recherche efficace.

688
00:32:27,170 --> 00:32:30,960
Nous ne pouvons absolument revenir en arrière pour la semaine
deux, jeter ceux-ci dans un tableau,

689
00:32:30,960 --> 00:32:33,150
et les rechercher en utilisant la recherche binaire.

690
00:32:33,150 --> 00:32:34,040
Diviser et conquérir.

691
00:32:34,040 --> 00:32:37,720
Et en fait, vous avez écrit
recherche binaire dans PSET3,

692
00:32:37,720 --> 00:32:40,100
où vous en œuvre le programme de recherche.

693
00:32:40,100 --> 00:32:40,890
Mais vous savez quoi.

694
00:32:40,890 --> 00:32:45,060
Il ya une sorte de plus
façon intelligente de le faire.

695
00:32:45,060 --> 00:32:47,390
Il est un peu plus
sophistiqué et ce peut-être

696
00:32:47,390 --> 00:32:50,830
nous permet de voir pourquoi binaire
la recherche est tellement plus rapide.

697
00:32:50,830 --> 00:32:52,980
Premièrement, nous allons introduire
la notion d'un arbre.

698
00:32:52,980 --> 00:32:54,730
Qui, même si dans
arbres de type de réalité

699
00:32:54,730 --> 00:32:57,730
grandir comme ça, dans le monde de l'informatique
la science, ils poussent à la baisse type de

700
00:32:57,730 --> 00:33:00,830
comme un arbre de la famille, où vous avez
vos grands-parents ou grands-parents

701
00:33:00,830 --> 00:33:04,580
ou quoi au sommet, le patriarche et
la matriarche de la famille, un seul

702
00:33:04,580 --> 00:33:07,930
dite racine, noeud, ci-dessous
Quelles sont ses enfants,

703
00:33:07,930 --> 00:33:11,442
ci-dessous, qui sont ses enfants, ou
ses descendants plus généralement.

704
00:33:11,442 --> 00:33:13,400
Et quiconque pendait
le fond de la famille

705
00:33:13,400 --> 00:33:16,070
arbre, en plus d'être le
plus jeune dans la famille,

706
00:33:16,070 --> 00:33:19,520
peut aussi être juste générique
appelle les feuilles de l'arbre.

707
00:33:19,520 --> 00:33:21,800
>> Donc, ceci est juste un tas
des mots et des définitions

708
00:33:21,800 --> 00:33:25,790
pour quelque chose appelé un arbre dans l'ordinateur
la science, un peu comme un arbre généalogique.

709
00:33:25,790 --> 00:33:28,770
Mais il ya incarnations fantaisistes
des arbres, dont l'un

710
00:33:28,770 --> 00:33:30,780
est appelé un arbre de recherche binaire.

711
00:33:30,780 --> 00:33:34,380
Et vous pouvez sorte de taquinerie
Outre ce que cette chose fait.

712
00:33:34,380 --> 00:33:37,180
Eh bien, il est binaire dans quel sens?

713
00:33:37,180 --> 00:33:41,455
D'où vient le binaire viennent ici?

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

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

716
00:33:45,961 --> 00:33:47,210
Il est pas tellement un ou.

717
00:33:47,210 --> 00:33:52,000
Il est plus que chacun des noeuds n'a pas
plus de deux enfants, que nous voyons ici.

718
00:33:52,000 --> 00:33:54,990
En général, un tree-- et
vos parents et grands parents

719
00:33:54,990 --> 00:33:57,640
peut avoir autant d'enfants ou
petits-enfants qu'ils veulent réellement,

720
00:33:57,640 --> 00:34:00,820
et ainsi par exemple, il nous en avons trois
enfants hors de ce nœud de la main droite,

721
00:34:00,820 --> 00:34:05,480
mais dans un arbre binaire, un noeud a
zéro, un ou deux enfants au maximum.

722
00:34:05,480 --> 00:34:08,496
Et voilà une belle propriété,
parce que si elle est couronnée par deux,

723
00:34:08,496 --> 00:34:10,620
nous allons être en mesure de
obtenir un peu logarithme en base deux

724
00:34:10,620 --> 00:34:11,975
l'action se passe ici en fin de compte.

725
00:34:11,975 --> 00:34:13,350
Donc, nous avons quelque chose logarithmique.

726
00:34:13,350 --> 00:34:14,558
Mais plus sur cela dans un instant.

727
00:34:14,558 --> 00:34:19,810
Des moyens pour rechercher arbre que les chiffres sont
agencé de telle sorte que l'enfant de gauche

728
00:34:19,810 --> 00:34:22,429
La valeur est supérieure à la racine.

729
00:34:22,429 --> 00:34:26,010
Et son enfant droite est
plus grande que la racine.

730
00:34:26,010 --> 00:34:29,290
En d'autres termes, si vous prenez un des
nœuds, les cercles dans cette image,

731
00:34:29,290 --> 00:34:31,840
et regarde à sa gauche
enfant et son droit de l'enfant,

732
00:34:31,840 --> 00:34:34,739
le premier devrait être inférieure à,
le second doit être supérieure.

733
00:34:34,739 --> 00:34:36,159
Donc, test de cohérence 55.

734
00:34:36,159 --> 00:34:37,780
Il a laissé l'enfant est de 33.

735
00:34:37,780 --> 00:34:38,620
Il est moins.

736
00:34:38,620 --> 00:34:40,929
55, son droit de l'enfant est 77.

737
00:34:40,929 --> 00:34:41,783
Il est supérieur.

738
00:34:41,783 --> 00:34:43,199
Et voilà une définition récursive.

739
00:34:43,199 --> 00:34:46,480
Nous pourrions vérifier chaque un de ceux
nœuds et le même schéma tiendrait.

740
00:34:46,480 --> 00:34:49,389
>> Donc, ce qui est agréable dans un
arbre binaire de recherche, est

741
00:34:49,389 --> 00:34:52,204
celui-là, nous pouvons mettre en œuvre
avec une struct, juste comme ça.

742
00:34:52,204 --> 00:34:54,620
Et même si nous jetons
beaucoup de structures à votre,

743
00:34:54,620 --> 00:34:56,560
ils sont peu
intuitive maintenant je l'espère.

744
00:34:56,560 --> 00:35:00,570
La syntaxe est encore obscur pour sûr,
mais le contenu d'un noeud dans cette

745
00:35:00,570 --> 00:35:02,786
context-- et nous gardons
en utilisant le mot node,

746
00:35:02,786 --> 00:35:04,910
que ce soit un rectangle
sur l'écran ou d'un cercle,

747
00:35:04,910 --> 00:35:08,970
il est juste un conteneur générique,
dans ce cas, d'un arbre, tel que celui

748
00:35:08,970 --> 00:35:11,780
nous avons vu, nous avons besoin d'un entier
dans chacun des noeuds

749
00:35:11,780 --> 00:35:15,460
et puis je besoin de deux pointeurs pointage
à l'enfant gauche et la droite enfant,

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

751
00:35:16,590 --> 00:35:20,730
Voilà donc comment nous pourrions
mettre en œuvre que dans une structure.

752
00:35:20,730 --> 00:35:22,315
Et comment pourrais-je mettre en œuvre dans le code?

753
00:35:22,315 --> 00:35:26,730
Eh bien, nous allons jeter un rapide
regarder ce petit exemple.

754
00:35:26,730 --> 00:35:29,820
Il est non fonctionnel, mais je l'ai
copié et collé cette structure.

755
00:35:29,820 --> 00:35:33,510
Et si ma fonction pour un binaire
arbre de recherche est appelé recherche,

756
00:35:33,510 --> 00:35:36,980
et cela prend deux arguments,
un nombre entier N et d'un pointeur

757
00:35:36,980 --> 00:35:41,400
à un noeud, de sorte qu'un pointeur vers l'arborescence
ou un pointeur vers la racine d'un arbre,

758
00:35:41,400 --> 00:35:43,482
comment puis-je aller sur la recherche de N?

759
00:35:43,482 --> 00:35:45,440
Eh bien, d'abord, parce que je suis
traitement des pointeurs,

760
00:35:45,440 --> 00:35:46,750
Je vais faire une vérification de cohérence.

761
00:35:46,750 --> 00:35:54,279
Si égaux d'arbres égal nulle, est N
dans cet arbre ou non dans cet arbre?

762
00:35:54,279 --> 00:35:55,070
Il ne peut pas être, non?

763
00:35:55,070 --> 00:35:56,870
Si je suis passé null,
il n'y a rien.

764
00:35:56,870 --> 00:35:59,230
Je pourrais tout aussi bien
aveuglément dire return false.

765
00:35:59,230 --> 00:36:04,050
Si vous me donnez rien, je ne peux pas sûrement
trouver un certain nombre N. Alors quoi d'autre pourrais-je

766
00:36:04,050 --> 00:36:04,750
vérifie maintenant?

767
00:36:04,750 --> 00:36:12,830
Je vais bien dire d'autre si N est
inférieur à ce qui est au niveau du noeud de l'arbre

768
00:36:12,830 --> 00:36:16,300
que je ai été remis valeur N.

769
00:36:16,300 --> 00:36:20,270
En d'autres termes, si le nombre je suis
la recherche de N, est inférieur au nœud

770
00:36:20,270 --> 00:36:21,340
que je suis à la recherche.

771
00:36:21,340 --> 00:36:23,190
Et le nœud je cherche
est appelé à arbre,

772
00:36:23,190 --> 00:36:26,370
et de rappeler à partir de l'exemple précédent
pour obtenir la valeur dans un pointeur,

773
00:36:26,370 --> 00:36:28,310
Je l'utilise la notation de flèche.

774
00:36:28,310 --> 00:36:35,960
Donc, si N est inférieur Arbre Sous-
N, je veux aller conceptuellement gauche.

775
00:36:35,960 --> 00:36:38,590
Comment puis-je exprimer recherchez quitté?

776
00:36:38,590 --> 00:36:41,560
Pour être clair, si cela est
l'image en question,

777
00:36:41,560 --> 00:36:44,612
et je l'ai été adoptée que le plus haut
flèche pointant vers le bas que ça.

778
00:36:44,612 --> 00:36:45,570
Voilà mon pointeur de l'arbre.

779
00:36:45,570 --> 00:36:48,060
Je fais remarquer à la racine de l'arbre.

780
00:36:48,060 --> 00:36:52,100
Et je suis à la recherche par exemple, pour
le nombre 44, arbitrairement.

781
00:36:52,100 --> 00:36:55,300
44 est inférieur ou
évidemment supérieure à 55?

782
00:36:55,300 --> 00:36:56,360
Il est donc moins.

783
00:36:56,360 --> 00:36:58,760
Et donc cela si l'état applique.

784
00:36:58,760 --> 00:37:03,981
Donc, sur le plan conceptuel, ce que je veux
rechercher prochaine si je suis à la recherche pour les 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Exactement, je veux
chercher l'enfant à gauche,

788
00:37:11,100 --> 00:37:12,789
ou le sous-arbre gauche de cette image.

789
00:37:12,789 --> 00:37:14,830
Et en fait, permettez-moi de grâce
la photo ici

790
00:37:14,830 --> 00:37:17,770
pour un instant, depuis
Je ne peux pas rayer cela.

791
00:37:17,770 --> 00:37:21,150
Si je commence ici à 55 ans, et
Je sais que la valeur 44

792
00:37:21,150 --> 00:37:23,180
Je cherche est de
la gauche, il est un peu

793
00:37:23,180 --> 00:37:26,010
comme de déchirer le livre de téléphone dans
la moitié ou déchirement de l'arbre en deux.

794
00:37:26,010 --> 00:37:29,660
Je ne ai plus à se soucier
toute cette moitié de l'arbre.

795
00:37:29,660 --> 00:37:33,270
Et pourtant, curieusement en termes de
la structure, cette chose ici que

796
00:37:33,270 --> 00:37:36,682
commence par 33, qui se
est un arbre de recherche binaire.

797
00:37:36,682 --> 00:37:39,890
Je l'ai dit le mot récursive avant parce
en effet ceci est une structure de données qui

798
00:37:39,890 --> 00:37:41,707
par définition est récursive.

799
00:37:41,707 --> 00:37:44,540
Vous pourriez avoir un arbre qui est présent
grand, mais chacun de ses enfants

800
00:37:44,540 --> 00:37:46,870
représente un arbre un peu plus petite.

801
00:37:46,870 --> 00:37:50,910
Au lieu d'être grand-père
ou grand-mère, maintenant il est juste maman

802
00:37:50,910 --> 00:37:54,300
ou-- Je ne peux pas say-- pas maman
ou papa, ce serait bizarre.

803
00:37:54,300 --> 00:37:59,000
Au contraire, les deux enfants là-bas
serait comme frère et sœur.

804
00:37:59,000 --> 00:38:01,120
Une nouvelle génération de l'arbre généalogique.

805
00:38:01,120 --> 00:38:02,900
Mais structurellement, il est la même idée.

806
00:38:02,900 --> 00:38:06,790
Et il se trouve que je dois une fonction
avec laquelle je peux chercher une recherche binaire

807
00:38:06,790 --> 00:38:07,290
arbre.

808
00:38:07,290 --> 00:38:08,680
Il est appelé recherche.

809
00:38:08,680 --> 00:38:17,870
Je cherche N dans l'arbre flèche gauche
sinon si N est supérieur à la valeur

810
00:38:17,870 --> 00:38:18,870
que je suis actuellement à.

811
00:38:18,870 --> 00:38:20,800
55 dans l'histoire il ya un instant.

812
00:38:20,800 --> 00:38:23,780
Je dois une fonction appelée
la recherche que je peux juste

813
00:38:23,780 --> 00:38:29,660
N passer cela et rechercher de manière récursive
le sous-arbre et juste retour

814
00:38:29,660 --> 00:38:30,620
quelle que soit cette réponse.

815
00:38:30,620 --> 00:38:33,530
Sinon je dois certains cas, de base finale ici.

816
00:38:33,530 --> 00:38:35,310
>> Quel est le dernier cas?

817
00:38:35,310 --> 00:38:36,570
Arbre est soit null.

818
00:38:36,570 --> 00:38:39,980
La valeur soit je cherche est
inférieur à ce qu'il ou supérieure à celle

819
00:38:39,980 --> 00:38:42,610
ou égal à elle.

820
00:38:42,610 --> 00:38:44,750
Et je pourrais dire égale
égal, mais logiquement, il est

821
00:38:44,750 --> 00:38:46,500
équivalent à simplement dire d'autre ici.

822
00:38:46,500 --> 00:38:49,150
Tant il est vrai que je trouve quelque chose.

823
00:38:49,150 --> 00:38:51,710
Il en est ainsi, espérons une
exemple encore plus convaincante

824
00:38:51,710 --> 00:38:54,900
que la fonction de sigma stupide
nous avons fait quelques conférences dos,

825
00:38:54,900 --> 00:38:58,360
où il était tout aussi facile à utiliser une boucle
compter tous les chiffres de un

826
00:38:58,360 --> 00:39:02,390
N. Ici, avec une structure de données
qui est lui-même de façon récursive

827
00:39:02,390 --> 00:39:07,050
définis et de manière récursive attirés, maintenant nous
avoir la capacité de nous exprimer

828
00:39:07,050 --> 00:39:09,780
dans le code qui lui-même est récursive.

829
00:39:09,780 --> 00:39:12,580
Donc, cela est exactement le même code ici.

830
00:39:12,580 --> 00:39:14,400
>> Alors que d'autres problèmes que nous pouvons résoudre?

831
00:39:14,400 --> 00:39:18,160
Donc, un pas rapide loin de
arbres pour un moment.

832
00:39:18,160 --> 00:39:20,130
Ici est, disons, le drapeau allemand.

833
00:39:20,130 --> 00:39:22,020
Et il ya clairement un
motif à ce drapeau.

834
00:39:22,020 --> 00:39:23,811
Et il ya beaucoup de
drapeaux dans le monde qui

835
00:39:23,811 --> 00:39:27,560
sont aussi simple que cela en termes
de leurs couleurs et de motifs.

836
00:39:27,560 --> 00:39:31,930
Mais supposons que cela est stocké en tant que
.GIF, Ou d'un JPEG ou bitmap, ou une table de ping,

837
00:39:31,930 --> 00:39:34,240
quel format de fichier graphique
avec lequel vous êtes familier,

838
00:39:34,240 --> 00:39:36,460
dont certains que nous sommes
jouer avec dans PSET4.

839
00:39:36,460 --> 00:39:41,550
Cela ne semble pas utile de stocker
pixel noir, pixel noir, pixel noir,

840
00:39:41,550 --> 00:39:44,790
dot, point, point, tout un tas de
pixels noirs pour la première ligne de balayage,

841
00:39:44,790 --> 00:39:47,430
ou une ligne, puis tout un tas de
de même, puis un tas

842
00:39:47,430 --> 00:39:49,530
de même, puis une
tas ensemble de pixels rouges,

843
00:39:49,530 --> 00:39:53,020
pixels rouges et les pixels rouges, puis tout un
tas de pixels jaunes, jaune, non?

844
00:39:53,020 --> 00:39:55,050
>> Il ya une telle inefficacité ici.

845
00:39:55,050 --> 00:39:59,040
Comment feriez-vous intuitivement
comprimer le drapeau allemand

846
00:39:59,040 --> 00:40:01,320
si la mise en œuvre dans un fichier?

847
00:40:01,320 --> 00:40:04,940
Comme quoi informations pouvons-nous pas
peine stocker sur le disque afin

848
00:40:04,940 --> 00:40:08,040
pour diminuer la taille de notre fichier à partir comme
un mégaoctet à un kilo-octet, quelque chose

849
00:40:08,040 --> 00:40:09,430
plus petit?

850
00:40:09,430 --> 00:40:13,130
Dans laquelle se trouve la redondance
ici pour être clair?

851
00:40:13,130 --> 00:40:13,880
Que pourriez-vous faire?

852
00:40:13,880 --> 00:40:14,380
Ouais?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Exactement.

855
00:40:21,970 --> 00:40:24,550
Pourquoi ne pas plutôt que de se rappeler
la couleur de chaque pixel sacrément

856
00:40:24,550 --> 00:40:28,200
tout comme vous faites dans PSET4
avec le format de fichier bitmap,

857
00:40:28,200 --> 00:40:32,060
pourquoi ne vous représentez pas seulement le
colonne de gauche de pixels, par exemple

858
00:40:32,060 --> 00:40:35,370
un tas de pixels noirs, un tas
de rouge, et un tas de jaune,

859
00:40:35,370 --> 00:40:39,210
et puis juste en quelque sorte l'encoder
idée de répéter cette 100 fois

860
00:40:39,210 --> 00:40:41,020
ou répéter cette 1000 fois?

861
00:40:41,020 --> 00:40:43,430
Où est 100 ou 1000
juste un nombre entier, de sorte que vous

862
00:40:43,430 --> 00:40:47,290
peut sortir avec un seul numéro
au lieu de centaines ou de milliers

863
00:40:47,290 --> 00:40:48,270
de pixels supplémentaires.

864
00:40:48,270 --> 00:40:50,990
Et en effet, ce est comment nous
pourrait comprimer le drapeau allemand.

865
00:40:50,990 --> 00:40:51,490
Et

866
00:40:51,490 --> 00:40:53,470
Maintenant, qu'en est-il le drapeau français?

867
00:40:53,470 --> 00:40:58,930
Et un peu une sorte de
exercice mental, quel drapeau

868
00:40:58,930 --> 00:41:01,040
peut être comprimé plus sur le disque?

869
00:41:01,040 --> 00:41:05,720
Le drapeau allemand ou les Français
drapeau, si nous prenons cette approche?

870
00:41:05,720 --> 00:41:08,490
Le drapeau allemand, parce qu'il ya
plus de redondance horizontale.

871
00:41:08,490 --> 00:41:12,190
Et par la conception, de nombreux fichiers graphiques
formats ne fonctionnent en effet comme les lignes de balayage

872
00:41:12,190 --> 00:41:12,830
horizontalement.

873
00:41:12,830 --> 00:41:14,674
Ils pourraient travailler
verticalement, juste l'humanité

874
00:41:14,674 --> 00:41:17,090
il ya des années décidé que nous allons
pensent généralement des choses rangée

875
00:41:17,090 --> 00:41:18,880
par ligne à la place de la colonne par colonne.

876
00:41:18,880 --> 00:41:20,820
Donc, en effet, si vous étiez
à regarder le fichier

877
00:41:20,820 --> 00:41:24,670
taille d'un drapeau allemand et un français
drapeau, tant que la résolution est

878
00:41:24,670 --> 00:41:27,530
de même, la même largeur
et la hauteur, à celui-ci

879
00:41:27,530 --> 00:41:31,580
ici va être plus grand, parce que vous
avoir à vous répéter trois fois.

880
00:41:31,580 --> 00:41:35,570
Vous devez spécifier bleu, répétez
vous, blanc, répétez-vous, rouge,

881
00:41:35,570 --> 00:41:36,740
vous répétez.

882
00:41:36,740 --> 00:41:39,000
Vous ne pouvez pas aller tout
le chemin vers la droite.

883
00:41:39,000 --> 00:41:41,200
Et en passant, à faire
désactiver la compression

884
00:41:41,200 --> 00:41:43,910
est partout, si ceux-ci sont
quatre trames d'une video-- vous

885
00:41:43,910 --> 00:41:45,890
pourrait rappeler qu'un film
ou vidéo est en général

886
00:41:45,890 --> 00:41:47,286
comme 29 ou 30 images par seconde.

887
00:41:47,286 --> 00:41:50,410
Il est comme un petit flip book où vous
juste voir l'image, l'image, l'image, l'image,

888
00:41:50,410 --> 00:41:54,410
l'image juste super rapide de sorte qu'il ressemble
les acteurs sur l'écran sont en mouvement.

889
00:41:54,410 --> 00:41:57,130
Voici un bourdon sur
dessus d'un bouquet de fleurs.

890
00:41:57,130 --> 00:41:59,790
Et si cela peut être une sorte de
difficile de voir au premier coup d'œil,

891
00:41:59,790 --> 00:42:04,020
la seule chose se déplaçant dans
ce film est l'abeille.

892
00:42:04,020 --> 00:42:06,880
>> Quel est muet sur le stockage
vidéo non compressée?

893
00:42:06,880 --> 00:42:11,420
Il est une sorte de déchets à stocker de la vidéo
que quatre images presque identiques que

894
00:42:11,420 --> 00:42:13,670
ne diffèrent que dans la mesure où lorsque l'abeille est.

895
00:42:13,670 --> 00:42:16,280
Vous pouvez jeter plus
de cette information

896
00:42:16,280 --> 00:42:20,190
et rappelez-vous que, par exemple,
la première image et la dernière image,

897
00:42:20,190 --> 00:42:22,180
cadres clés Si vous avez
jamais entendu le mot,

898
00:42:22,180 --> 00:42:24,337
et juste stocker dans le
milieu où l'abeille est.

899
00:42:24,337 --> 00:42:26,170
Et vous ne devez pas
stocker la totalité de la rose,

900
00:42:26,170 --> 00:42:28,330
et le bleu, et de la
valeurs vertes ainsi.

901
00:42:28,330 --> 00:42:31,200
Donc cela pour dire seulement que
la compression est partout.

902
00:42:31,200 --> 00:42:34,900
Il est une technique que nous utilisons souvent
ou tenir pour acquis ces jours.

903
00:42:34,900 --> 00:42:38,750
>> Mais comment ne vous compressez texte?

904
00:42:38,750 --> 00:42:40,450
Comment allez-vous comprimer texte?

905
00:42:40,450 --> 00:42:45,410
Eh bien, chacun des personnages dans
ASCII est un octet, ou huit bits.

906
00:42:45,410 --> 00:42:47,360
Et cela est un peu idiot, non?

907
00:42:47,360 --> 00:42:51,160
Parce que vous avez probablement de type A
et E et I et O et U a beaucoup

908
00:42:51,160 --> 00:42:55,270
le plus souvent comme W ou Q ou Z,
en fonction de la langue dans laquelle

909
00:42:55,270 --> 00:42:56,610
vous écrivez certainement.

910
00:42:56,610 --> 00:42:59,600
Et alors pourquoi utilisons-nous
huit bits pour chaque lettre,

911
00:42:59,600 --> 00:43:02,040
y compris les moins
lettres populaires, non?

912
00:43:02,040 --> 00:43:05,300
Pourquoi ne pas utiliser moins de bits pour
les lettres super populaire,

913
00:43:05,300 --> 00:43:07,760
comme E, les choses que vous devinez
d'abord dans Roue de la Fortune,

914
00:43:07,760 --> 00:43:10,450
et utiliser plus de bits pour
les lettres moins populaires?

915
00:43:10,450 --> 00:43:10,950
Pourquoi?

916
00:43:10,950 --> 00:43:13,130
Parce que nous allons juste
utiliser moins fréquemment.

917
00:43:13,130 --> 00:43:15,838
>> Eh bien, il se trouve qu'il ya eu
les tentatives faites pour ce faire été.

918
00:43:15,838 --> 00:43:18,630
Et si vous vous souvenez du grade
l'école ou au lycée, le code Morse.

919
00:43:18,630 --> 00:43:20,400
Morse a points
et tirets qui peuvent être

920
00:43:20,400 --> 00:43:24,270
transmis le long d'un fil comme
des sons ou des signaux de quelque sorte.

921
00:43:24,270 --> 00:43:25,930
Mais le code Morse est un super propre.

922
00:43:25,930 --> 00:43:29,010
Il est une sorte de système binaire
que vous avez des points ou des tirets.

923
00:43:29,010 --> 00:43:30,977
Mais si vous voyez, par exemple, deux points.

924
00:43:30,977 --> 00:43:33,810
Ou si vous pensez à l'opérateur
qui va comme bip, bip, bip,

925
00:43:33,810 --> 00:43:36,760
bip, frapper un peu de déclenchement
qui transmet un signal,

926
00:43:36,760 --> 00:43:40,360
si vous, le destinataire, reçoit deux
points, quel message avez-vous reçu?

927
00:43:40,360 --> 00:43:43,490
Complètement arbitraire.

928
00:43:43,490 --> 00:43:44,450
>> JE?

929
00:43:44,450 --> 00:43:45,060
JE?

930
00:43:45,060 --> 00:43:47,500
Ou ce about-- ou moi?

931
00:43:47,500 --> 00:43:49,570
Peut-être qu'il était juste deux droit de l'E?

932
00:43:49,570 --> 00:43:52,480
Donc, il ya ce problème
de décodabilité avec Morse

933
00:43:52,480 --> 00:43:54,890
code, de sorte que, sauf si le
personne vous envoyer le message

934
00:43:54,890 --> 00:43:59,510
les pauses dans effectivement de sorte que vous pouvez trier des
voir ou entendre les écarts entre les lettres,

935
00:43:59,510 --> 00:44:02,990
il ne suffit pas simplement pour
envoyer un flux de zéros et de uns,

936
00:44:02,990 --> 00:44:05,610
ou points et de traits,
parce qu'il ya ambiguïté.

937
00:44:05,610 --> 00:44:08,640
E est un point unique, donc si vous
voir deux points ou entendre deux points,

938
00:44:08,640 --> 00:44:11,254
il est peut être deux de E ou peut-être il est l'un I.

939
00:44:11,254 --> 00:44:13,670
Nous avons donc besoin d'un système qui est un
peu plus intelligent que cela.

940
00:44:13,670 --> 00:44:16,851
Ainsi, un homme du nom de Huffman ans
Il ya venu avec exactement cela.

941
00:44:16,851 --> 00:44:18,600
Donc, nous allons juste
de prendre un coup d'oeil rapide

942
00:44:18,600 --> 00:44:20,114
comment les arbres sont pertinentes à cet égard.

943
00:44:20,114 --> 00:44:22,530
Supposons que ce soit un peu
stupide message que vous souhaitez envoyer,

944
00:44:22,530 --> 00:44:26,342
composé de seulement A, B, C et D de s E'S,
mais il ya beaucoup de redondance ici.

945
00:44:26,342 --> 00:44:27,550
Il est pas censé être l'anglais.

946
00:44:27,550 --> 00:44:28,341
Il est pas crypté.

947
00:44:28,341 --> 00:44:30,540
Il est juste un message stupide
avec beaucoup de répétition.

948
00:44:30,540 --> 00:44:34,010
Donc, si vous comptez réellement toutes les
A'S, B, C de, D's, et E de, voici

949
00:44:34,010 --> 00:44:34,890
la fréquence.

950
00:44:34,890 --> 00:44:37,800
20% des lettres sont
A'S, 45% des lettres

951
00:44:37,800 --> 00:44:39,660
sont de E, et trois autres fréquences.

952
00:44:39,660 --> 00:44:41,960
Nous avons compté là-haut la main
et juste fait le calcul.

953
00:44:41,960 --> 00:44:44,579
>> Donc, il se trouve que
Huffman, il ya quelque temps,

954
00:44:44,579 --> 00:44:46,620
réalisé que, vous savez
ce qui, si je commence bâtiment

955
00:44:46,620 --> 00:44:51,172
un arbre, ou une forêt d'arbres, si vous voulez,
comme suit, je peux faire ce qui suit.

956
00:44:51,172 --> 00:44:53,880
Je vais donner un noeud à chaque
des lettres que je me soucie

957
00:44:53,880 --> 00:44:55,530
et je vais stocker
à l'intérieur de ce noeud

958
00:44:55,530 --> 00:44:58,610
les fréquences en flottant
valeur, ou vous pouvez utiliser un N, aussi,

959
00:44:58,610 --> 00:45:00,210
mais nous allons simplement utiliser un flotteur ici.

960
00:45:00,210 --> 00:45:03,100
Et l'algorithme qui
il a proposé est que vous

961
00:45:03,100 --> 00:45:07,210
prendre cette forêt de noeud unique
arbres, arbres si super court,

962
00:45:07,210 --> 00:45:11,920
et vous commencez à les relier à
de nouveaux groupes, de nouveaux parents, si vous voulez.

963
00:45:11,920 --> 00:45:16,150
Et vous faites cela en choisissant la
deux plus petites fréquences à la fois.

964
00:45:16,150 --> 00:45:18,110
Je pris donc 10% et 10%.

965
00:45:18,110 --> 00:45:19,090
Je crée un nouveau nœud.

966
00:45:19,090 --> 00:45:20,910
Et je l'appelle le nouveau nœud de 20%.

967
00:45:20,910 --> 00:45:22,750
>> Quels sont les deux noeuds je combine ensuite?

968
00:45:22,750 --> 00:45:23,810
Il est un peu ambiguë.

969
00:45:23,810 --> 00:45:26,643
Donc, il ya certains cas de coin à
envisager, mais de garder les choses assez,

970
00:45:26,643 --> 00:45:29,300
Je vais choisir 20% -
Je l'ignore maintenant les enfants.

971
00:45:29,300 --> 00:45:33,640
Je vais choisir 20% et
15% et tracez deux nouveaux bords.

972
00:45:33,640 --> 00:45:35,624
Et maintenant, qui deux noeuds
puis-je combiner logiquement?

973
00:45:35,624 --> 00:45:38,540
Ignorer tous les enfants, tous les
petits-enfants, il suffit de regarder les racines

974
00:45:38,540 --> 00:45:39,070
maintenant.

975
00:45:39,070 --> 00:45:42,220
Quels sont les deux nœuds puis-je attacher ensemble?

976
00:45:42,220 --> 00:45:44,530
Point de deux et 0,35.

977
00:45:44,530 --> 00:45:45,890
Alors permettez-moi d'attirer deux nouveaux bords.

978
00:45:45,890 --> 00:45:47,570
Et puis je ne ai qu'une gauche.

979
00:45:47,570 --> 00:45:48,650
Alors, voici un arbre.

980
00:45:48,650 --> 00:45:51,160
Et il a été tiré délibérément
à regarder sorte de joli,

981
00:45:51,160 --> 00:45:55,870
de remarquer que les bords ont
également été marqué zéro et un.

982
00:45:55,870 --> 00:45:59,510
Donc tous les bords gauche sont à zéro
arbitrairement, mais constamment.

983
00:45:59,510 --> 00:46:01,170
Tous les bons bords sont chers.

984
00:46:01,170 --> 00:46:05,070
>> Et donc ce que Hoffman proposé est,
si vous voulez représenter un B,

985
00:46:05,070 --> 00:46:10,080
plutôt que de représenter le nombre 66 comme
ASCII qui est entières huit bits,

986
00:46:10,080 --> 00:46:13,360
vous savez quoi, magasin juste
le modèle zéro, zéro, zéro,

987
00:46:13,360 --> 00:46:17,030
zéro, parce que le chemin est
de mon arbre, l'arbre de M. Huffman,

988
00:46:17,030 --> 00:46:18,600
de la feuille à partir de la racine.

989
00:46:18,600 --> 00:46:20,970
Si vous souhaitez enregistrer un
E, en revanche, ne sont pas

990
00:46:20,970 --> 00:46:26,290
envoyer huit bits qui représentent un E.
Au lieu de cela, envoyez ce motif de bits?

991
00:46:26,290 --> 00:46:26,890
One.

992
00:46:26,890 --> 00:46:30,410
Et ce qui est bon à ce sujet est
que E est la lettre la plus populaire,

993
00:46:30,410 --> 00:46:32,340
et vous utilisez le
le plus court code pour elle.

994
00:46:32,340 --> 00:46:34,090
La prochaine plus populaire
lettre ressemble à elle

995
00:46:34,090 --> 00:46:37,380
était A. Et si le nombre de bits
at-il proposer en utilisant pour cela?

996
00:46:37,380 --> 00:46:38,270
Zéro, un.

997
00:46:38,270 --> 00:46:41,060
>> Et parce qu'il est mis en œuvre
comme cet arbre, pour l'instant

998
00:46:41,060 --> 00:46:43,350
laissez-moi stipule par il ya
aucune ambiguïté quant à Morse

999
00:46:43,350 --> 00:46:46,090
code, parce que tous les
lettres que vous vous souciez

1000
00:46:46,090 --> 00:46:48,780
sont à la fin de ces bords.

1001
00:46:48,780 --> 00:46:50,580
Voilà donc un seul
application d'un arbre.

1002
00:46:50,580 --> 00:46:52,538
Cette est-- et je vais vague
ma main à ce comment vous

1003
00:46:52,538 --> 00:46:55,570
pourrait mettre en œuvre ce que une structure C.

1004
00:46:55,570 --> 00:46:58,260
Nous avons juste besoin de combiner
un symbole, comme un char,

1005
00:46:58,260 --> 00:46:59,910
et la fréquence à gauche et à droite.

1006
00:46:59,910 --> 00:47:02,510
Mais regardons deux
derniers exemples que vous aurez

1007
00:47:02,510 --> 00:47:06,070
être assez familier avec après
Quiz zéro problème réglé cinq.

1008
00:47:06,070 --> 00:47:09,210
>> Donc, il ya la structure de données
connu comme une table de hachage.

1009
00:47:09,210 --> 00:47:12,247
Et une table de hachage est une sorte de
refroidir en ce qu'il comporte des seaux.

1010
00:47:12,247 --> 00:47:14,830
Et suppose qu'il ya quatre seaux
ici, seulement quatre espaces.

1011
00:47:14,830 --> 00:47:20,830
Voici un jeu de cartes, et est ici
club, pelle, club, diamants, club,

1012
00:47:20,830 --> 00:47:25,960
diamants, clubs, diamants,
clubs-- ce est donc le hasard.

1013
00:47:25,960 --> 00:47:30,330
Coeurs, hearts-- donc je suis
bucketizing toutes les entrées ici.

1014
00:47:30,330 --> 00:47:32,430
Et un besoins de table de hachage
de regarder votre entrée,

1015
00:47:32,430 --> 00:47:34,850
et puis le mettre dans un certain
placer sur la base de ce que vous voyez.

1016
00:47:34,850 --> 00:47:35,600
Il est un algorithme.

1017
00:47:35,600 --> 00:47:37,980
Et je me sers d'un super-
algorithme visuel simple.

1018
00:47:37,980 --> 00:47:40,030
La partie la plus difficile de ce qui était
rappelant ce que les photos étaient.

1019
00:47:40,030 --> 00:47:41,590
Et puis il ya quatre choses totaux.

1020
00:47:41,590 --> 00:47:45,440
>> Maintenant, les piles ont été de plus en plus, ce qui
est une conception délibérée chose ici.

1021
00:47:45,440 --> 00:47:46,540
Mais quoi d'autre pourrais-je faire?

1022
00:47:46,540 --> 00:47:49,080
Donc en fait nous avons ici un
tas de vieux livres d'examen de l'école.

1023
00:47:49,080 --> 00:47:51,240
Supposons qu'un groupe de
noms étudiants sont ici.

1024
00:47:51,240 --> 00:47:52,570
Voici une grande table de hachage.

1025
00:47:52,570 --> 00:47:54,867
Au lieu de quatre seaux,
Je suis, disons 26.

1026
00:47:54,867 --> 00:47:57,950
Et nous ne voulons pas aller emprunter 26
choses de [l'extérieur? Annenberg?], De sorte

1027
00:47:57,950 --> 00:48:00,289
voici cinq qui représentent
A à Z. Et si je

1028
00:48:00,289 --> 00:48:03,580
voir un étudiant dont le nom commence par A,
Je vais à son questionnaire mis là.

1029
00:48:03,580 --> 00:48:08,850
Si quelqu'un commence par C, là-bas,
A- effectivement, ne voulait pas le faire.

1030
00:48:08,850 --> 00:48:10,060
B va ici.

1031
00:48:10,060 --> 00:48:13,390
Donc, je dois A et B et C. Et
voici maintenant un autre étudiant.

1032
00:48:13,390 --> 00:48:16,212
Mais si cette table de hachage est
mis en oeuvre avec un réseau,

1033
00:48:16,212 --> 00:48:17,920
Je suis un peu foiré
à ce point, non?

1034
00:48:17,920 --> 00:48:19,510
Je sorte de besoin de le mettre quelque part.

1035
00:48:19,510 --> 00:48:24,380
>> Donc, d'une manière que je peux résoudre ce problème est, tout
à droite, un est occupé, B est occupé, C est occupé.

1036
00:48:24,380 --> 00:48:28,880
Je vais le mettre dans D. Ainsi, à
Premièrement, je dois accès instantané aléatoire

1037
00:48:28,880 --> 00:48:31,064
à chacun des godets pour les étudiants.

1038
00:48:31,064 --> 00:48:33,230
Mais maintenant, il est une sorte de dévolue
en quelque chose linéaire,

1039
00:48:33,230 --> 00:48:36,750
parce que si je veux chercher quelqu'un
dont le nom commence par A, je vérifie ici.

1040
00:48:36,750 --> 00:48:38,854
Mais si tel est le pas A
étudiant, je suis à la recherche,

1041
00:48:38,854 --> 00:48:41,520
Je dois sorte de commencer à vérifier
les seaux, parce que ce que je faisais

1042
00:48:41,520 --> 00:48:44,530
était en quelque sorte linéairement
sonder la structure de données.

1043
00:48:44,530 --> 00:48:47,710
Une façon stupide de dire il suffit de regarder
pour la première ouverture disponibles,

1044
00:48:47,710 --> 00:48:51,850
et de mettre comme un plan B, pour ainsi dire,
ou le plan D dans ce cas, la valeur

1045
00:48:51,850 --> 00:48:53,340
à cet endroit à la place.

1046
00:48:53,340 --> 00:48:56,470
Ceci est juste de sorte que si vous avez
obtenu 26 endroits et pas d'étudiants

1047
00:48:56,470 --> 00:49:00,600
avec le nom Q ou Z, ou quelque chose comme
que, au moins vous utilisez l'espace.

1048
00:49:00,600 --> 00:49:03,140
>> Mais nous avons déjà vu plus
solutions intelligentes ici, non?

1049
00:49:03,140 --> 00:49:04,870
Que feriez-vous à la place
si vous avez une collision?

1050
00:49:04,870 --> 00:49:06,670
Si deux personnes ont
Un nom, ce serait

1051
00:49:06,670 --> 00:49:09,160
ont été plus intelligents ou plus
solution intuitive que juste

1052
00:49:09,160 --> 00:49:12,840
Mettre un où D est censé être?

1053
00:49:12,840 --> 00:49:14,810
Pourquoi dois-je pas simplement aller
dehors [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
comme malloc, un autre nœud, le mettre
ici, et ensuite mettre qu'un étudiant ici.

1055
00:49:19,960 --> 00:49:22,120
Alors que je dois essentiellement
une sorte d'un tableau,

1056
00:49:22,120 --> 00:49:25,590
ou peut-être avec plus d'élégance que nous sommes
commençons à voir une liste chaînée.

1057
00:49:25,590 --> 00:49:29,520
>> Et donc une table de hachage est une structure
qui pourrait ressembler à cela,

1058
00:49:29,520 --> 00:49:33,900
mais plus intelligemment, vous quelque chose appelé
chaînage séparé, dans lequel une table de hachage

1059
00:49:33,900 --> 00:49:38,340
est tout simplement un tableau, chacun des
dont les éléments ne sont pas un certain nombre,

1060
00:49:38,340 --> 00:49:40,470
est lui-même une liste chaînée.

1061
00:49:40,470 --> 00:49:45,080
Alors que vous obtenez un accès ultra-rapide
décider où votre valeur à hacher.

1062
00:49:45,080 --> 00:49:48,059
Tout comme avec l'exemple des cartes,
Je pris des décisions super rapide.

1063
00:49:48,059 --> 00:49:49,600
Coeurs va ici, diamants va ici.

1064
00:49:49,600 --> 00:49:52,180
Même ici, A va ici,
D va ici, B va ici.

1065
00:49:52,180 --> 00:49:55,740
Donc super rapides look-ups, et si
vous arrive de courir dans un cas

1066
00:49:55,740 --> 00:49:59,429
collisions où vous avez, deux
les personnes ayant le même nom, eh bien

1067
00:49:59,429 --> 00:50:00,970
vous venez de commencer les reliant.

1068
00:50:00,970 --> 00:50:03,900
Et peut-être vous les gardez triées
par ordre alphabétique, peut-être vous ne le faites pas.

1069
00:50:03,900 --> 00:50:05,900
Mais au moins maintenant nous avons le dynamisme.

1070
00:50:05,900 --> 00:50:10,250
Donc, d'une part, nous avons super rapide
constante de temps, et le type de temps linéaire

1071
00:50:10,250 --> 00:50:14,110
impliqués si ces listes chaînées
commencer à obtenir un peu long.

1072
00:50:14,110 --> 00:50:16,880
>> Donc, ce genre de stupide,
Il ya plaisanterie ans geek.

1073
00:50:16,880 --> 00:50:19,590
Au CS50 bidouille-o-thon,
lorsque les élèves check-in,

1074
00:50:19,590 --> 00:50:22,040
certains TF ou CA chaque année
pense qu'il est drôle à mettre en place

1075
00:50:22,040 --> 00:50:27,772
un signe de ce genre, où il vient
signifie que si votre nom commence par un A,

1076
00:50:27,772 --> 00:50:28,870
aller dans cette voie.

1077
00:50:28,870 --> 00:50:31,110
Si votre nom commence
avec un B, aller this-- OK,

1078
00:50:31,110 --> 00:50:33,290
il est drôle peut-être plus tard dans le semestre.

1079
00:50:33,290 --> 00:50:36,420
Mais il ya un autre
façon de le faire, aussi.

1080
00:50:36,420 --> 00:50:37,410
Revenez à cela.

1081
00:50:37,410 --> 00:50:38,600
>> Donc, il ya cette structure.

1082
00:50:38,600 --> 00:50:40,420
Et ceci est notre dernière
la structure pour aujourd'hui,

1083
00:50:40,420 --> 00:50:42,400
qui est quelque chose appelé un trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, qui pour une raison est courte
pour la récupération, mais il est appelé Trie.

1085
00:50:47,140 --> 00:50:51,389
Donc un trie est une autre intéressante
amalgame de beaucoup de ces idées.

1086
00:50:51,389 --> 00:50:52,930
Il est un arbre, que nous avons vu auparavant.

1087
00:50:52,930 --> 00:50:54,180
Il est pas un arbre de recherche binaire.

1088
00:50:54,180 --> 00:50:58,410
Il est un arbre avec un certain nombre d'enfants,
mais chacun des enfants dans un trie

1089
00:50:58,410 --> 00:51:00,090
est un tableau.

1090
00:51:00,090 --> 00:51:04,790
Un tableau de taille, disons, 26 ou peut-être 27
si vous voulez soutenir noms trait d'union

1091
00:51:04,790 --> 00:51:06,790
ou apostrophes dans les noms des personnes.

1092
00:51:06,790 --> 00:51:08,280
>> Et si cela est une structure de données.

1093
00:51:08,280 --> 00:51:10,290
Et si vous regardez de haut
en bas, comme si vous

1094
00:51:10,290 --> 00:51:13,710
regarder le nœud supérieur là, M, est
pointant à la chose la plus à gauche il,

1095
00:51:13,710 --> 00:51:17,665
qui est alors A, X, W, E, L, L. Ceci est
seulement une structure de données qui arbitrairement

1096
00:51:17,665 --> 00:51:19,120
est mémoriser les noms des personnes.

1097
00:51:19,120 --> 00:51:25,720
Et Maxwell est stocké en suivant simplement
un chemin de tableau en tableau en tableau.

1098
00:51:25,720 --> 00:51:30,050
Mais ce qui est étonnant sur un trie est
que, si une liste chaînée et même

1099
00:51:30,050 --> 00:51:34,520
un tableau, le meilleur que nous ayons eu est
temps linéaire ou logarithmique à la recherche du temps

1100
00:51:34,520 --> 00:51:35,600
quelqu'un.

1101
00:51:35,600 --> 00:51:40,530
Dans cette structure de données d'une trie, si
ma structure de données a un nom dans ce

1102
00:51:40,530 --> 00:51:43,720
et je suis à la recherche pour Maxwell, je suis
va le trouver assez rapidement.

1103
00:51:43,720 --> 00:51:47,910
Je viens de regarder pour M-A-X-W-E-L-L. Si
cette structure de données, en revanche,

1104
00:51:47,910 --> 00:51:51,830
si N est un million, si il ya un
millions de noms dans cette structure de données,

1105
00:51:51,830 --> 00:51:57,100
Maxwell va encore être
détectable après seulement M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
étapes.

1107
00:51:58,090 --> 00:52:01,276
Et étapes David-- D-A-V-I-D.

1108
00:52:01,276 --> 00:52:03,400
En d'autres termes, en construisant
une structure de données qui est

1109
00:52:03,400 --> 00:52:07,240
obtenu l'ensemble de ces matrices, qui
se soutenir l'accès aléatoire,

1110
00:52:07,240 --> 00:52:11,090
Je peux commencer à chercher jusqu'à autrui
nom en utilisant une quantité de temps qui est

1111
00:52:11,090 --> 00:52:14,340
proportionnelle à pas le nombre
des choses dans la structure de données,

1112
00:52:14,340 --> 00:52:16,330
comme un million de noms existants.

1113
00:52:16,330 --> 00:52:20,135
La quantité de temps qu'il me faut pour trouver
M-A-X-W-E-L-L dans cette structure de données est

1114
00:52:20,135 --> 00:52:22,260
pas proportionnelle à la
taille de la structure de données,

1115
00:52:22,260 --> 00:52:25,930
mais à la longueur du nom.

1116
00:52:25,930 --> 00:52:28,440
Et réaliste le
noms Nous sommes regardant

1117
00:52:28,440 --> 00:52:29,970
ne vont jamais être fou longtemps.

1118
00:52:29,970 --> 00:52:32,600
Peut-être quelqu'un a un caractère 10
nom, nom de 20 caractères.

1119
00:52:32,600 --> 00:52:33,900
Il est certainement finie, non?

1120
00:52:33,900 --> 00:52:37,110
Il est un être humain sur Terre qui
a le nom le plus long possible,

1121
00:52:37,110 --> 00:52:39,920
mais ce nom est une constante
longueur de valeur, non?

1122
00:52:39,920 --> 00:52:41,980
Il ne varie pas dans tous les sens.

1123
00:52:41,980 --> 00:52:45,090
Donc, dans ce sens, nous avons
atteint une structure de données

1124
00:52:45,090 --> 00:52:47,800
qui est constante de temps look-up.

1125
00:52:47,800 --> 00:52:50,670
Il prend un certain nombre de mesures
en fonction de la longueur de l'entrée,

1126
00:52:50,670 --> 00:52:54,250
mais pas le nombre de nom
dans la structure de données.

1127
00:52:54,250 --> 00:52:58,700
Donc, si nous doublons le nombre de noms
l'année prochaine d'un milliard à deux milliards,

1128
00:52:58,700 --> 00:53:03,720
constatation Maxwell va prendre
exactement le même nombre de sept étapes

1129
00:53:03,720 --> 00:53:04,650
pour le retrouver.

1130
00:53:04,650 --> 00:53:08,810
Et si nous semblons avoir atteint
notre saint Graal de la durée de fonctionnement.

1131
00:53:08,810 --> 00:53:10,860
>> Alors quelques annonces rapides.

1132
00:53:10,860 --> 00:53:11,850
Quiz zéro est à venir.

1133
00:53:11,850 --> 00:53:14,600
Plus de détails sur ce que sur le site Web de cours
au cours des prochains jours.

1134
00:53:14,600 --> 00:53:17,120
Lundis lecture-- il est un jour férié
ici à Harvard lundi.

1135
00:53:17,120 --> 00:53:18,850
Il est pas à New Haven,
nous sommes donc en prenant la classe

1136
00:53:18,850 --> 00:53:20,310
à New Haven pour conférence le lundi.

1137
00:53:20,310 --> 00:53:22,550
Tout sera filmé
et retransmis en direct comme d'habitude,

1138
00:53:22,550 --> 00:53:24,900
mais finissons aujourd'hui
avec un deuxième clip 30

1139
00:53:24,900 --> 00:53:26,910
appelés "pensées profondes"
par Daven Farnham, qui

1140
00:53:26,910 --> 00:53:30,850
a été inspiré l'an dernier le samedi
"Pensées profondes" de Night Live

1141
00:53:30,850 --> 00:53:35,700
par Jack Handy, qui
devrait maintenant donner un sens.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Et maintenant, "Deep
Pensées "de Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Table de hachage.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> ENCEINTE 1: Très bien, qui est pour l'instant.

1147
00:53:47,660 --> 00:53:48,805
Nous vous verrons la semaine prochaine.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Pour le voir en action.

1150
00:53:56,680 --> 00:53:58,304
Donc, nous allons jeter un oeil à ce droit maintenant.

1151
00:53:58,304 --> 00:53:59,890
Donc, ici, nous avons un tableau non triés.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, pouvez-vous aller de l'avant et de redémarrage
cela pour seulement une seconde, s'il vous plaît.

1153
00:54:04,860 --> 00:54:08,562
Tout droit, caméras tournent, donc
l'action chaque fois que vous êtes prêt, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Très bien, alors ce que nous
avons ici est un tableau non triés.

1155
00:54:11,020 --> 00:54:13,960
Et je l'ai colorié tous les éléments
rouge pour indiquer qu'il est, en fait,

1156
00:54:13,960 --> 00:54:14,460
non triés.

1157
00:54:14,460 --> 00:54:17,960
Donc, rappelons que la première chose que nous faisons
est que nous trions la moitié gauche du tableau.

1158
00:54:17,960 --> 00:54:20,630
Ensuite, nous trions le droit
moitié de la matrice.

1159
00:54:20,630 --> 00:54:22,830
Et ya-da, da-Ya, ya-da,
nous fusionnons ensemble.

1160
00:54:22,830 --> 00:54:24,520
Et nous avons un tableau complètement triée.

1161
00:54:24,520 --> 00:54:25,360
Voilà donc comment fonctionne le tri par fusion.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Whoa, whoa, whoa,
couper, couper, couper, couper.

1163
00:54:27,109 --> 00:54:30,130
Doug, vous ne pouvez pas simplement Ya-da, ya-da,
Ya-da, votre chemin à travers le tri par fusion.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: Je viens de faire.

1165
00:54:31,970 --> 00:54:32,832
C'est bien.

1166
00:54:32,832 --> 00:54:33,540
Nous sommes bon pour aller.

1167
00:54:33,540 --> 00:54:34,760
Gardons laminage.

1168
00:54:34,760 --> 00:54:35,380
De toute façon,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Vous devez expliquer
plus pleinement que cela.

1170
00:54:37,800 --> 00:54:39,999
Voilà tout simplement pas assez.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, nous ne faisons pas
besoin de revenir à un.

1172
00:54:41,790 --> 00:54:42,350
C'est bien.

1173
00:54:42,350 --> 00:54:45,690
Donc de toute façon, si nous continuons avec merge--
Ian, nous sommes dans le milieu du tournage.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Je sais.

1175
00:54:46,612 --> 00:54:49,320
Et nous ne pouvons pas simplement Ya-da, ya-da,
Ya-da, à travers l'ensemble du processus.

1176
00:54:49,320 --> 00:54:52,200
Vous devez expliquer comment le
deux côtés se fusionnés.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Mais nous avons déjà
expliqué comment les deux sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Vous venez montré
elle toute une gamme de fusion.

1179
00:54:55,321 --> 00:54:56,486
DOUG: ils savent le processus.

1180
00:54:56,486 --> 00:54:57,172
Ils vont bien.

1181
00:54:57,172 --> 00:54:58,380
Nous avons dépassé dix fois.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Vous venez sauté droit sur elle.

1183
00:55:00,330 --> 00:55:03,360
Nous allons revenir à un, vous
tu ne peux pas Ya-da, da ya-dessus.

1184
00:55:03,360 --> 00:55:05,480
Tout droit, le dos à un.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Je dois retourner
à travers toutes les diapositives?

1186
00:55:07,833 --> 00:55:08,332
Mon Dieu.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Il est comme la sixième fois, Ian.

1189
00:55:13,004 --> 00:55:13,940
C'est bien.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Très bien.

1191
00:55:15,200 --> 00:55:16,590
Tu es prêt?

1192
00:55:16,590 --> 00:55:17,400
Génial.

1193
00:55:17,400 --> 00:55:18,950
Action.