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

2
00:00:00,030 --> 00:00:00,460
>> DAVID MALAN: Alles in Ordnung.

3
00:00:00,460 --> 00:00:01,094
Wir sind zurück.

4
00:00:01,094 --> 00:00:04,260
Also in diesem Segment über die Programmierung, was
Ich dachte, wir tun würde, eine Mischung aus Dingen.

5
00:00:04,260 --> 00:00:06,340
Eins, tun ein wenig
von etwas hands-on,

6
00:00:06,340 --> 00:00:08,690
wenn auch mit einer spielerischen
Programmierung environment--

7
00:00:08,690 --> 00:00:11,620
eine, die demonstrativ von
genau die Art von Ideen

8
00:00:11,620 --> 00:00:14,220
Wir haben darüber gesprochen,
aber ein wenig mehr formal.

9
00:00:14,220 --> 00:00:18,200
Zwei, Blick auf einige
Je mehr technische Möglichkeiten,

10
00:00:18,200 --> 00:00:21,520
dass ein Programmierer lösen würde tatsächlich
Probleme wie die Suche Problem

11
00:00:21,520 --> 00:00:24,530
dass wir vor geschaut und
auch ein grundsätzlicher

12
00:00:24,530 --> 00:00:26,020
interessantes Problem des Sortierens.

13
00:00:26,020 --> 00:00:28,840
>> Wir gingen davon nur aus der get gehen
dass das Telefonbuch wurde sortiert,

14
00:00:28,840 --> 00:00:31,980
aber das allein ist eigentlich ganz ein
schweres Problem mit vielen verschiedenen Möglichkeiten,

15
00:00:31,980 --> 00:00:32,479
es zu lösen.

16
00:00:32,479 --> 00:00:34,366
Also werden wir diese verwenden, wie
eine Klasse von Problemen

17
00:00:34,366 --> 00:00:36,740
Vertreter der Dinge, die
könnte im Allgemeinen gelöst werden.

18
00:00:36,740 --> 00:00:38,980
Und dann werden wir reden
etwa im Detail, was

19
00:00:38,980 --> 00:00:42,360
werden Daten genannt structures--
ausgefallenere Möglichkeiten wie verkettete Listen

20
00:00:42,360 --> 00:00:46,290
und Hash-Tabellen und Bäume, die
ein Programmierer würde tatsächlich

21
00:00:46,290 --> 00:00:48,890
verwenden und verwenden in der Regel
auf einer Tafel zu malen

22
00:00:48,890 --> 00:00:51,840
ein Bild von dem, was er oder sie
sieht für die Umsetzung

23
00:00:51,840 --> 00:00:52,980
einige Stück Software.

24
00:00:52,980 --> 00:00:55,130
>> Also lassen Sie uns die hands-on zu tun Teil zuerst.

25
00:00:55,130 --> 00:01:00,090
Deshalb sollte man nur die Hände schmutzig mit ein
Umwelt genannt scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Dies ist ein Werkzeug, das wir verwenden
in unserem Bachelor-Klasse.

27
00:01:02,636 --> 00:01:04,510
Auch wenn es entworfen
ab 12 Jahren auf,

28
00:01:04,510 --> 00:01:07,570
wir nutzen es für die oben
Teil dieser ziemlich viel

29
00:01:07,570 --> 00:01:10,020
da es ein schönes, Spaß
grafische Art und Weise des Lernens

30
00:01:10,020 --> 00:01:12,160
ein wenig etwas über die Programmierung.

31
00:01:12,160 --> 00:01:17,600
Also Kopf zu dieser URL, wo Sie
sehen sollte eine Seite ganz wie diese,

32
00:01:17,600 --> 00:01:23,330
und gehen Sie vor und klicken Sie auf
Join Scratch oben rechts

33
00:01:23,330 --> 00:01:28,300
und wählen Sie einen Benutzernamen und ein
Passwort und erhalten letztlich selbst

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

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

36
00:01:32,165 --> 00:01:34,665
Ich dachte, ich dies als ein verwenden würde,
Gelegenheit erste, dies zu zeigen.

37
00:01:34,665 --> 00:01:39,120
Eine Frage kam in der Pause
über das, was Code tatsächlich aussieht.

38
00:01:39,120 --> 00:01:41,315
Und wir sprachen
während der Pause über C,

39
00:01:41,315 --> 00:01:45,060
in particular-- insbesondere ein
untere Ebene in einer älteren Sprache.

40
00:01:45,060 --> 00:01:47,750
Und ich habe gerade eine schnelle
Google-Suche C-Code zu finden

41
00:01:47,750 --> 00:01:51,574
für binäre Suche, der Algorithmus, wir
die früher verwendet wurde, dass die Telefonbuch zu suchen.

42
00:01:51,574 --> 00:01:54,240
Dieses spezielle Beispiel ist natürlich
nicht ein Telefonbuch zu suchen.

43
00:01:54,240 --> 00:01:57,840
Es sucht nur eine ganze Reihe von
Nummern in den Speicher des Computers.

44
00:01:57,840 --> 00:02:01,000
Aber wenn Sie möchten, erhalten nur eine visuelle
Sinn dessen, was eine tatsächliche Programmierung

45
00:02:01,000 --> 00:02:05,370
Sprache sieht aus wie es aussieht
ein wenig so etwas wie dieses.

46
00:02:05,370 --> 00:02:09,759
So ist es etwa 20-plus,
30 oder so Zeilen Code,

47
00:02:09,759 --> 00:02:12,640
aber das Gespräch, das wir
wurden mit über Pause

48
00:02:12,640 --> 00:02:16,000
war darüber, wie diese tatsächlich
wird in Nullen und Einsen verwandelt

49
00:02:16,000 --> 00:02:19,200
und wenn Sie nicht nur rückgängig machen können, dass
verarbeiten und gehen von Nullen und Einsen

50
00:02:19,200 --> 00:02:20,210
zurück zum Code.

51
00:02:20,210 --> 00:02:22,620
>> Leider ist der Prozess
ist so transformierende

52
00:02:22,620 --> 00:02:24,890
dass es viel einfacher ist, gesagt als getan.

53
00:02:24,890 --> 00:02:29,400
Ich ging weiter und tatsächlich drehte
das Programm, Binäre Suche,

54
00:02:29,400 --> 00:02:32,700
in Nullen und Einsen durch eine
Programm namens den Compiler, dass ich

55
00:02:32,700 --> 00:02:34,400
passieren hier direkt auf meinem Mac zu haben.

56
00:02:34,400 --> 00:02:37,850
Und wenn Sie den Bildschirm schauen
hier, die sich speziell

57
00:02:37,850 --> 00:02:43,520
auf diesen mittleren sechs Spalten nur,
Sie werden sehen, nur Nullen und Einsen.

58
00:02:43,520 --> 00:02:48,290
Und das sind die Nullen und Einsen, dass
komponieren genau das Suchprogramm.

59
00:02:48,290 --> 00:02:53,720
>> Und so jedes Stück von fünf Bits,
Jedes Byte von Nullen und Einsen hier,

60
00:02:53,720 --> 00:02:57,310
repräsentieren einige Anweisungen
typischerweise innerhalb eines Computers.

61
00:02:57,310 --> 00:03:00,730
Und in der Tat, wenn Sie gehört haben, die
Marketing-Slogan "Intel inside" - das,

62
00:03:00,730 --> 00:03:04,610
natürlich nur bedeutet, dass Sie eine haben
Intel CPU oder Gehirn im Computer.

63
00:03:04,610 --> 00:03:08,000
Und was das bedeutet eine CPU zu sein
dass Sie einen Befehlssatz,

64
00:03:08,000 --> 00:03:08,840
sozusagen.

65
00:03:08,840 --> 00:03:11,620
>> Jede CPU in der Welt viele
sie von Intel in diesen Tagen,

66
00:03:11,620 --> 00:03:13,690
versteht eine endliche
Anzahl von Instruktionen.

67
00:03:13,690 --> 00:03:18,690
Und diese Anweisungen sind so niedrigen Niveau
so fügen Sie diese beiden Zahlen zusammen,

68
00:03:18,690 --> 00:03:22,560
multiplizieren diese beiden Zahlen zusammen,
bewegen, dieses Stück von Daten von hier

69
00:03:22,560 --> 00:03:27,340
im Speicher hier, speichern diese
Informationen von hier in Erinnerung zu hier,

70
00:03:27,340 --> 00:03:32,200
und so forth-- so sehr, sehr
Low-Level, fast elektronische Details.

71
00:03:32,200 --> 00:03:34,780
Aber mit diesen mathematischen
Operationen gekoppelt

72
00:03:34,780 --> 00:03:37,410
mit dem, was wir früher diskutiert,
die Darstellung von Daten,

73
00:03:37,410 --> 00:03:40,450
als Nullen und Einsen, können
Sie bauen alles

74
00:03:40,450 --> 00:03:44,180
dass ein Computer heute tun kann, ob
es ist Text-, Grafik-, Musical,

75
00:03:44,180 --> 00:03:45,580
oder andernfalls.

76
00:03:45,580 --> 00:03:49,450
>> Das ist also sehr leicht zu bekommen
in das Unkraut verloren rasch.

77
00:03:49,450 --> 00:03:52,150
Und es gibt eine Menge von
syntaktische Herausforderungen

78
00:03:52,150 --> 00:03:56,630
wobei, wenn Sie die einfachste machen,
dümmsten Fehler keines des Programms

79
00:03:56,630 --> 00:03:57,860
funktioniert auch immer.

80
00:03:57,860 --> 00:04:00,366
Und so stattdessen eine der Verwendung
Sprache wie C an diesem Morgen,

81
00:04:00,366 --> 00:04:02,240
Ich dachte, es wäre
mehr Spaß, um tatsächlich tun

82
00:04:02,240 --> 00:04:04,840
etwas mehr visuelle, die
während für Kinder entwickelt

83
00:04:04,840 --> 00:04:08,079
tatsächlich ist eine perfekte Manifestation
einer tatsächlichen Programmierung

84
00:04:08,079 --> 00:04:10,370
language-- passiert einfach zu
Verwenden Sie Bilder anstelle von Text

85
00:04:10,370 --> 00:04:11,710
diese Ideen zu vertreten.

86
00:04:11,710 --> 00:04:15,470
>> Also, wenn Sie in der Tat eine haben
Konto auf scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
klicken Sie auf die Schaltfläche Erstellen
am oberen Rand der Seite links.

88
00:04:21,070 --> 00:04:24,620
Und Sie sollten eine Umgebung zu sehen wie
die, die ich bin etwa auf meinem Bildschirm zu sehen

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

90
00:04:26,310 --> 00:04:29,350
Und wir verbringen nur ein wenig
wenig Zeit, hier zu spielen.

91
00:04:29,350 --> 00:04:34,080
Mal sehen, ob wir nicht alle etwas lösen können
Probleme in der folgenden Weise zusammen.

92
00:04:34,080 --> 00:04:39,420
>> Also, was Sie in dieser sehen
environment-- und eigentlich nur lassen

93
00:04:39,420 --> 00:04:40,050
mich innehalten.

94
00:04:40,050 --> 00:04:42,680
Ist jemand hier nicht?

95
00:04:42,680 --> 00:04:45,070
Nicht hier?

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

97
00:04:45,800 --> 00:04:49,030
Also lassen Sie mich ein paar weisen darauf hin,
Eigenschaften dieser Umgebung.

98
00:04:49,030 --> 00:04:55,024
>> So ganz oben links auf dem Bildschirm, wir
haben Scratch Bühne, sozusagen.

99
00:04:55,024 --> 00:04:57,440
Scratch ist nicht nur der Name
dieser Programmiersprache;

100
00:04:57,440 --> 00:05:00,356
es ist auch der Name der Katze,
Sie sehen dort standardmäßig in Orange.

101
00:05:00,356 --> 00:05:02,160
Er ist auf einer Bühne, so
ähnlich wie ich beschrieben

102
00:05:02,160 --> 00:05:05,770
die Schildkröte früher als in einem Wesen
rechteckigen weißen Tafel Umwelt.

103
00:05:05,770 --> 00:05:09,800
Diese Katze der Welt ist völlig beschränkt
zu diesem Rechteck nach oben oben gibt.

104
00:05:09,800 --> 00:05:12,210
>> Inzwischen auf der rechten
Seite hier, es ist

105
00:05:12,210 --> 00:05:15,610
nur Skripte Bereich, ein
unbeschriebenes Blatt, wenn man so will.

106
00:05:15,610 --> 00:05:18,590
Das ist, wohin wir gehen zu schreiben
unsere Programme in nur einem Augenblick.

107
00:05:18,590 --> 00:05:22,935
Und die Bausteine, dass wir
verwenden zu schreiben diese program-- das Rätsel

108
00:05:22,935 --> 00:05:25,310
Stücke, wenn Sie will-- sind
denen hier in der Mitte,

109
00:05:25,310 --> 00:05:27,500
und sie sind kategorisiert
durch Funktionalität.

110
00:05:27,500 --> 00:05:31,000
So zum Beispiel, ich gehe voran gehen
und zeigen zumindest eine von diesen.

111
00:05:31,000 --> 00:05:33,690
Ich gehe voran gehen und klicken Sie auf
die Kategorie bis oben.

112
00:05:33,690 --> 00:05:35,720
>> Das sind also die Kategorien bis oben.

113
00:05:35,720 --> 00:05:39,410
Ich werde die Steuerungskategorie zu klicken.

114
00:05:39,410 --> 00:05:44,020
Vielmehr werde ich die Ereignisse zu klicken
Kategorie, die allererste bis oben.

115
00:05:44,020 --> 00:05:47,790
Und wenn Sie möchten, dass entlang zu folgen, auch
wie wir dies tun, sind Sie recht herzlich willkommen auf.

116
00:05:47,790 --> 00:05:52,180
Ich werde dies zu klicken und ziehen
erste, "wenn grüne Fahne geklickt haben."

117
00:05:52,180 --> 00:05:58,410
Und dann werde ich es einfach fallen zu lassen
etwa auf der Spitze meiner leeren Schiefer.

118
00:05:58,410 --> 00:06:01,450
>> Und was ist schön, über Scratch
ist, dass dieses Puzzle-Stück, wenn

119
00:06:01,450 --> 00:06:04,560
mit anderen Puzzle verzahnt
Stücke, wird buchstäblich zu tun

120
00:06:04,560 --> 00:06:06,460
was diese Puzzleteile sagen zu tun.

121
00:06:06,460 --> 00:06:09,710
So zum Beispiel, Scratch ist richtig
jetzt in der Mitte seiner Welt.

122
00:06:09,710 --> 00:06:14,660
Ich gehe voran gehen und wählen
jetzt, sagen wir mal, die Motion Kategorie,

123
00:06:14,660 --> 00:06:18,000
wenn Sie möchten, dass das zu tun
same-- Bewegung Kategorie.

124
00:06:18,000 --> 00:06:20,430
Und jetzt merke ich, eine ganze haben
Haufen Puzzleteile hier

125
00:06:20,430 --> 00:06:23,370
dass, wieder, eine Art zu tun, was sie sagen.

126
00:06:23,370 --> 00:06:28,110
Und ich werde weitermachen und ziehen
Drop die Bewegung Block rechts hier.

127
00:06:28,110 --> 00:06:31,860
>> Und feststellen, dass, sobald Sie bekommen
nah an der Unterseite der "grünen Flagge

128
00:06:31,860 --> 00:06:34,580
geklickt "Taste, Ankündigung
wie eine weiße Linie erscheint,

129
00:06:34,580 --> 00:06:36,950
als ob es fast
magnetisch, sie will, dorthin zu gehen.

130
00:06:36,950 --> 00:06:43,070
gehen Lassen Sie einfach, und es wird Snap
zusammen und passen Sie die Formen.

131
00:06:43,070 --> 00:06:46,620
Und jetzt können Sie vielleicht fast
erraten, wo wir mit diesem fahren.

132
00:06:46,620 --> 00:06:51,570
>> Wenn man sich die Scratch Bühne aussehen
hier und schauen nach oben davon,

133
00:06:51,570 --> 00:06:55,142
Sie werden ein rotes Licht sehen, ein
Stop-Schild und eine grüne Fahne.

134
00:06:55,142 --> 00:06:57,100
Und ich werde voran gehen
und beobachte meine screen--

135
00:06:57,100 --> 00:06:58,460
nur für einen Moment, wenn man könnte.

136
00:06:58,460 --> 00:07:01,960
Ich werde das zu klicken
grüne Fahne gerade jetzt,

137
00:07:01,960 --> 00:07:07,850
und er bewegt, was 10 Stufen zu sein scheint
oder 10 Pixel, 10 Punkte, auf dem Bildschirm.

138
00:07:07,850 --> 00:07:13,390
>> Und so nicht so aufregend,
aber lassen Sie mich vorschlagen

139
00:07:13,390 --> 00:07:17,440
ohne auch nur diese Lehre, nur
mit der eigenen Ihre eigene intuition-- let

140
00:07:17,440 --> 00:07:22,560
mich schlagen vor, dass Sie herausfinden, wie man
machen Scratch zu Fuß rechts von der Bühne.

141
00:07:22,560 --> 00:07:28,700
Habe ihn Weg für die rechte Seite machen von
der Bildschirm, den ganzen Weg nach rechts.

142
00:07:28,700 --> 00:07:32,200
Lassen Sie mich Ihnen einen Moment
oder so damit zu ringen.

143
00:07:32,200 --> 00:07:37,681
Vielleicht möchten Sie einen Blick zu nehmen
in anderen Kategorien von Blöcken.

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

145
00:07:38,180 --> 00:07:41,290
Also nur zu rekapitulieren, wenn wir
die grüne Fahne geklickt hier

146
00:07:41,290 --> 00:07:44,850
und bewegen 10 Schritten wird die
nur Anweisung, jedes Mal, wenn ich

147
00:07:44,850 --> 00:07:46,720
klicken Sie auf die grüne Fahne, was passiert?

148
00:07:46,720 --> 00:07:50,070
Nun, das läuft mein Programm.

149
00:07:50,070 --> 00:07:52,450
So konnte ich dies tun
vielleicht 10 mal manuell,

150
00:07:52,450 --> 00:07:55,130
aber das fühlt sich ein wenig
Bit hackish, so zu sprechen,

151
00:07:55,130 --> 00:07:57,480
wobei ich bin nicht wirklich
Lösung des Problems.

152
00:07:57,480 --> 00:08:00,530
Ich versuche nur, wieder und
wieder und wieder und wieder

153
00:08:00,530 --> 00:08:03,180
bis ich irgendwie aus Versehen
erreichen die Richtlinie

154
00:08:03,180 --> 00:08:05,560
dass ich früher gesetzt zu erreichen werden.

155
00:08:05,560 --> 00:08:08,200
>> Aber wir wissen aus unserer
Pseudo-Code früher, dass es

156
00:08:08,200 --> 00:08:11,870
dieser Begriff in der Programmierung von looping,
etwas zu tun, wieder und wieder.

157
00:08:11,870 --> 00:08:14,888
Und so sah ich, dass ein paar von euch
erreicht zu welchem ​​Puzzlestück?

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

159
00:08:17,870 --> 00:08:18,730
Wiederhole bis.

160
00:08:18,730 --> 00:08:21,400
So konnten wir etwas tun
wie oft wiederholen, bis.

161
00:08:21,400 --> 00:08:23,760
Und was haben Sie wiederholen, bis sich genau?

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

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

164
00:08:28,540 --> 00:08:31,974
Und lassen Sie mich mit einem gehen, das ist
etwas einfacher für einen Moment.

165
00:08:31,974 --> 00:08:33,140
Lassen Sie mich gehen Sie vor und tun dies.

166
00:08:33,140 --> 00:08:35,559
Beachten Sie, dass, wie Sie haben können
unter Kontrolle entdeckt,

167
00:08:35,559 --> 00:08:38,409
gibt es diese Wiederholungsblock, der
sieht nicht wie es ist so groß.

168
00:08:38,409 --> 00:08:41,039
Es gibt nicht viel Raum in
zwischen diesen beiden gelben Linien.

169
00:08:41,039 --> 00:08:43,539
Aber wie einige von euch vielleicht haben
bemerkt, wenn Sie per Drag & Drop,

170
00:08:43,539 --> 00:08:45,150
feststellen, wie es wächst die Form zu füllen.

171
00:08:45,150 --> 00:08:46,274
>> Und Sie können sogar noch mehr stopfen.

172
00:08:46,274 --> 00:08:48,670
Es wird einfach weiter wachsen, wenn
Sie ziehen und schweben über sie.

173
00:08:48,670 --> 00:08:51,110
Und ich weiß nicht, was ist
am besten hier, also lassen

174
00:08:51,110 --> 00:08:54,760
mir mindestens fünf Mal wiederholen, für
Beispiel, und dann auf die Bühne zurück

175
00:08:54,760 --> 00:08:56,720
und klicken Sie auf die grüne Fahne.

176
00:08:56,720 --> 00:08:59,110
Und jetzt bemerken, es ist nicht ganz da.

177
00:08:59,110 --> 00:09:02,400
>> Nun, einige von Ihnen vorgeschlagen, wie
Victoria gerade haben, 10-mal wiederholen.

178
00:09:02,400 --> 00:09:05,140
Und dass in der Regel tut
erhalten ihn den ganzen Weg,

179
00:09:05,140 --> 00:09:10,510
aber würde nicht ein robuster sein
Art und Weise als willkürlich herauszufinden

180
00:09:10,510 --> 00:09:12,640
wie viele Züge zu machen?

181
00:09:12,640 --> 00:09:17,680
Was könnte eine bessere Block sein
als Wiederholung sein 10-mal?

182
00:09:17,680 --> 00:09:20,380
>> Ja, also warum nicht etwas für immer?

183
00:09:20,380 --> 00:09:24,390
Und lassen Sie mich jetzt dieses Puzzle-Stück bewegen
im Inneren gibt und werde diese eine befreien.

184
00:09:24,390 --> 00:09:28,300
Beachten Sie jetzt, egal wo Scratch
beginnt, geht er an den Rand.

185
00:09:28,300 --> 00:09:30,700
Und zum Glück MIT,
wer macht Scratch, nur

186
00:09:30,700 --> 00:09:33,190
macht, dass er sicher nie
vollständig verschwindet.

187
00:09:33,190 --> 00:09:35,360
Sie können jederzeit mit dem Schwanz zu greifen.

188
00:09:35,360 --> 00:09:37,680
>> Und nur intuitiv,
warum behält er bewegte?

189
00:09:37,680 --> 00:09:38,892
Was geht hier vor sich?

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

191
00:09:41,440 --> 00:09:43,824
Er scheint stehen geblieben zu sein, aber
dann, wenn ich abholen und ziehen

192
00:09:43,824 --> 00:09:45,240
er hält wollen dorthin gehen.

193
00:09:45,240 --> 00:09:46,123
Warum das?

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

195
00:09:51,610 --> 00:09:54,360
Wahrlich, ist ein Computer buchstäblich
gehen zu tun, was Sie sagen, es zu tun.

196
00:09:54,360 --> 00:09:58,380
Also, wenn Sie es gesagt, früher tun die
folgende Sache für immer, bewegen 10 Stufen,

197
00:09:58,380 --> 00:10:01,860
es geht zu halten zu gehen und gehen
bis ich traf den roten Stoppschild

198
00:10:01,860 --> 00:10:04,620
und beenden Sie das Programm zusammen.

199
00:10:04,620 --> 00:10:06,610
>> Also selbst wenn Sie nicht taten
dies zu tun, wie könnte ich

200
00:10:06,610 --> 00:10:09,510
machen Scratch schneller bewegen
über den Bildschirm?

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

202
00:10:12,060 --> 00:10:13,280
Weitere Schritte, nicht wahr?

203
00:10:13,280 --> 00:10:15,710
So anstelle von 10 zu tun
zu einer Zeit, zu tun, warum nicht wir

204
00:10:15,710 --> 00:10:20,100
gehen Sie vor und ändern Sie es zu--
was würden Sie propose-- 50?

205
00:10:20,100 --> 00:10:24,410
So, jetzt werde ich das Grün zu klicken
Flagge, und in der Tat, er geht wirklich schnell.

206
00:10:24,410 --> 00:10:27,180
>> Und das ist natürlich nur
eine Manifestation der Animation.

207
00:10:27,180 --> 00:10:28,060
Was ist Animation?

208
00:10:28,060 --> 00:10:33,090
Es zeigt Ihnen nur den Menschen ein
ganze Reihe von Standbildern wirklich,

209
00:10:33,090 --> 00:10:34,160
wirklich, wirklich schnell.

210
00:10:34,160 --> 00:10:36,500
Und so, wenn wir nur sagen,
ihm mehr Schritte zu bewegen,

211
00:10:36,500 --> 00:10:39,750
wir haben nur die Wirkung sein,
Veränderung, wo er auf dem Bildschirm

212
00:10:39,750 --> 00:10:42,900
umso schneller je Zeiteinheit.

213
00:10:42,900 --> 00:10:46,454
>> Nun ist die nächste Herausforderung, die ich vorgeschlagen
war ihm die Kante abprallen haben.

214
00:10:46,454 --> 00:10:49,120
Und ohne zu wissen, was Puzzle
Stücke exist-- weil es ist in Ordnung

215
00:10:49,120 --> 00:10:53,030
wenn Sie nicht bekommen, um die
Stufe des challenge-- was

216
00:10:53,030 --> 00:10:54,280
wollen Sie intuitiv zu tun?

217
00:10:54,280 --> 00:10:58,030
Wie würden wir ihn haben wieder auf die Beine und
her, zwischen dem linken und rechten?

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

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

220
00:11:03,810 --> 00:11:05,680
Wir brauchen also eine Art
der Zustand, und wir

221
00:11:05,680 --> 00:11:09,710
scheinen conditionals zu haben, so zu
sprechen, unter der Kategorie Steuerung.

222
00:11:09,710 --> 00:11:14,110
Welche dieser Blöcke
wollen wir wahrscheinlich?

223
00:11:14,110 --> 00:11:15,200
Ja, vielleicht "wenn, dann".

224
00:11:15,200 --> 00:11:18,780
So fest, dass unter den gelben Blöcke
Wir haben es hier, da dieses "wenn" ist

225
00:11:18,780 --> 00:11:23,920
oder das "if, else" -Block das wird
ermöglichen es uns, eine Entscheidung zu treffen, dies zu tun

226
00:11:23,920 --> 00:11:25,000
oder das zu tun.

227
00:11:25,000 --> 00:11:27,380
Und Sie können sie sogar Nest
mehrere Dinge zu tun.

228
00:11:27,380 --> 00:11:34,910
Oder wenn Sie noch nicht hier noch gegangen,
gehen Sie vor, um die Sensing Kategorie

229
00:11:34,910 --> 00:11:39,612
und- mal sehen, ob es hier ist.

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

231
00:11:43,050 --> 00:11:52,050
>> Also, was Block könnte hier hilfreich sein
zu erkennen, ob er von der Bühne ist?

232
00:11:52,050 --> 00:11:56,740
Ja, feststellen, dass einige dieser Blöcke
kann parametrisiert, sozusagen.

233
00:11:56,740 --> 00:12:00,706
Sie können Art besonders angefertigt werden, nicht
im Gegensatz zu HTML gestern mit Attributen,

234
00:12:00,706 --> 00:12:03,330
wo Art diese Attribute
das Verhalten eines Tags anpassen.

235
00:12:03,330 --> 00:12:08,880
Ebenso hier, kann ich diese berührend greifen
Blocks und ändern und stellen die Frage,

236
00:12:08,880 --> 00:12:11,500
berühren Sie die Maus
Zeiger wie der Cursor

237
00:12:11,500 --> 00:12:13,250
oder berühren Sie den Rand?

238
00:12:13,250 --> 00:12:15,210
>> Also lassen Sie mich gehen und tun dies.

239
00:12:15,210 --> 00:12:18,130
Ich werde für einen Moment, um zu verkleinern.

240
00:12:18,130 --> 00:12:21,320
Lassen Sie mich dieses Puzzleteil greifen
hier, dieses Puzzleteil dieses,

241
00:12:21,320 --> 00:12:24,570
und ich werde durcheinander
sie sich für einen kurzen Moment.

242
00:12:24,570 --> 00:12:27,620
Ich werde dies zu bewegen,
ändern, um dies zu berührenden Kante,

243
00:12:27,620 --> 00:12:38,590
und ich werde Bewegung dies tun.

244
00:12:38,590 --> 00:12:40,490
Also hier sind einige Zutaten.

245
00:12:40,490 --> 00:12:42,570
Ich glaube, ich habe alles, was ich will.

246
00:12:42,570 --> 00:12:47,710
>> Würde jemand vorschlagen, wie ich
verbinden können diese oben vielleicht nach unten

247
00:12:47,710 --> 00:12:52,020
Um das Problem zu lösen, mit
Scratch Schritt nach rechts und nach links zu

248
00:12:52,020 --> 00:12:57,020
von links nach rechts, die jeweils nach links
Zeit Prellen direkt an der Wand?

249
00:12:57,020 --> 00:12:58,050
Was soll ich tun?

250
00:12:58,050 --> 00:13:01,097
Welcher Block sollte ich die Verbindung
"Wenn grüne Fahne geklickt zuerst"?

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

252
00:13:04,060 --> 00:13:06,200
>> OK, also lassen Sie uns mit dem Start "für immer."

253
00:13:06,200 --> 00:13:07,170
Was geht im Inneren als nächstes?

254
00:13:07,170 --> 00:13:10,290
Jemand anderes.

255
00:13:10,290 --> 00:13:11,850
OK, bewegen Schritte.

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

257
00:13:12,350 --> 00:13:14,470
Dann was?

258
00:13:14,470 --> 00:13:15,120
Also dann die if.

259
00:13:15,120 --> 00:13:17,720
Und bemerken, auch wenn es aussieht
zusammen dicht eingeklemmt,

260
00:13:17,720 --> 00:13:19,500
es wird nur zu füllen wachsen.

261
00:13:19,500 --> 00:13:21,500
Es springt nur in wo ich es will.

262
00:13:21,500 --> 00:13:25,920
>> Und was habe ich zwischen
die, wenn und dann?

263
00:13:25,920 --> 00:13:27,180
Wahrscheinlich "Kante, wenn zu berühren."

264
00:13:27,180 --> 00:13:31,800
Und beachten Sie, wieder, es ist zu groß
dafür, aber es wird zu füllen wachsen.

265
00:13:31,800 --> 00:13:35,002
Und dann um 15 Grad drehen?

266
00:13:35,002 --> 00:13:35,710
Wie viel Grad?

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

268
00:13:38,800 --> 00:13:41,196
Ja, so 180 drehen sich
mich den ganzen Weg um.

269
00:13:41,196 --> 00:13:42,570
Also mal sehen, ob ich das richtig verstanden habe.

270
00:13:42,570 --> 00:13:43,930
Lassen Sie mich verkleinern.

271
00:13:43,930 --> 00:13:45,130
>> Lassen Sie mich Scratch oben ziehen.

272
00:13:45,130 --> 00:13:50,030
Er ist also ein wenig verzerrt
jetzt, aber das ist in Ordnung.

273
00:13:50,030 --> 00:13:52,231
Wie kann ich ihn einfach zurück?

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

275
00:13:59,879 --> 00:14:01,045
Ich werde etwas zu betrügen.

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

277
00:14:04,074 --> 00:14:05,990
Also habe ich das Hinzufügen eines weiteren
Block, um nur klar sein.

278
00:14:05,990 --> 00:14:08,424
Ich will ihn um 90 Grad zu zeigen
nach rechts standardmäßig

279
00:14:08,424 --> 00:14:10,840
also werde ich nur ihm zu sagen,
dass programmatisch zu tun.

280
00:14:10,840 --> 00:14:11,632
Und es geht los.

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

282
00:14:14,740 --> 00:14:15,740
Wir scheinen es getan zu haben.

283
00:14:15,740 --> 00:14:19,980
Es ist ein wenig seltsam, weil
er zu Fuß den Kopf.

284
00:14:19,980 --> 00:14:21,250
Nennen wir, dass ein Bug.

285
00:14:21,250 --> 00:14:22,120
Das ist ein Fehler.

286
00:14:22,120 --> 00:14:27,320
Ein Fehler ist ein Fehler in einem Programm ein
logische Fehler, die ich, der Mensch, gemacht.

287
00:14:27,320 --> 00:14:28,985
Warum geht er den Kopf?

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

289
00:14:33,560 --> 00:14:35,250
Hat MIT vermasseln oder ich?

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

291
00:14:38,840 --> 00:14:42,550
>> Ja, ich meine, es ist nicht der MIT
Fehler. Sie gaben mir ein Puzzlestück

292
00:14:42,550 --> 00:14:44,970
das sagt eine bestimmte Anzahl von Grad drehen.

293
00:14:44,970 --> 00:14:47,672
Und bei Victoria Vorschlag,
Ich bin Drehen um 180 Grad,

294
00:14:47,672 --> 00:14:48,880
Das ist die richtige Intuition.

295
00:14:48,880 --> 00:14:53,700
Aber Drehen um 180 Grad wahrsten Sinne des Wortes
Mittel um 180 Grad gedreht,

296
00:14:53,700 --> 00:14:55,860
und das ist nicht wirklich
was ich will, offenbar.

297
00:14:55,860 --> 00:14:58,026
Da zumindest ist er in
Diese zweidimensionale Welt,

298
00:14:58,026 --> 00:15:00,740
so Wende wirklich geht
Flip ihm den Kopf.

299
00:15:00,740 --> 00:15:04,030
>> Ich möchte wohl, was Block zu verwenden,
stattdessen auf das, was Sie hier sehen?

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

301
00:15:11,890 --> 00:15:14,790
Wie können wir dieses Problem beheben?

302
00:15:14,790 --> 00:15:18,380
Ja, und so konnten wir zeigen
In die andere Richtung.

303
00:15:18,380 --> 00:15:22,300
Und eigentlich auch das ist
nicht genug sein würde,

304
00:15:22,300 --> 00:15:26,410
weil wir es können nur schwer Code
zu zeigen links oder rechts.

305
00:15:26,410 --> 00:15:27,920
>> Sie wissen, was wir tun könnten?

306
00:15:27,920 --> 00:15:30,160
Es sieht aus wie wir eine haben
Bequemlichkeit Block hier.

307
00:15:30,160 --> 00:15:32,987
Wenn ich in vergrößern, sehen
etwas, das wir gerne hier?

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

309
00:15:36,120 --> 00:15:40,020
So sieht es aus wie MIT eine hat
Abstraktion in hier gebaut.

310
00:15:40,020 --> 00:15:45,440
Dieser Block scheint äquivalent zu sein
auf die anderen Blöcke, Plural?

311
00:15:45,440 --> 00:15:49,510
>> Dieser Block scheint äquivalent zu sein
dieser ganze Trio von Blöcken

312
00:15:49,510 --> 00:15:50,880
dass wir hier haben.

313
00:15:50,880 --> 00:15:54,670
So stellt sich heraus kann ich meine vereinfachen
Programm durch all das loszuwerden

314
00:15:54,670 --> 00:15:58,270
und setzen diese einfach hier.

315
00:15:58,270 --> 00:16:01,620
Und jetzt ist er immer noch ein wenig
Buggy, und das ist jetzt in Ordnung.

316
00:16:01,620 --> 00:16:03,370
Wir lassen das sein.

317
00:16:03,370 --> 00:16:06,000
Aber mein Programm ist auch
einfacher und auch dies

318
00:16:06,000 --> 00:16:09,060
wäre Vertreter
eines Ziels in programming--

319
00:16:09,060 --> 00:16:13,430
ist in idealer Weise Ihren Code machen, wie
einfach, so kompakt wie möglich ist,

320
00:16:13,430 --> 00:16:15,650
während immer noch zu sein als
lesbar wie möglich.

321
00:16:15,650 --> 00:16:20,310
Sie wollen es nicht so prägnant zu machen
dass es schwer zu verstehen.

322
00:16:20,310 --> 00:16:22,826
>> Aber merke ich ersetzt habe
drei Blöcke mit einem,

323
00:16:22,826 --> 00:16:24,200
und das ist wohl eine gute Sache.

324
00:16:24,200 --> 00:16:27,280
Ich habe den Begriff wegabstrahiert
zu überprüfen, ob Sie

325
00:16:27,280 --> 00:16:29,120
am Rande mit nur einem Block.

326
00:16:29,120 --> 00:16:31,520
Jetzt können wir Spaß mit diesem haben, in der Tat.

327
00:16:31,520 --> 00:16:35,790
Dies fügt nicht so viel
geistigen Wert, sondern spielerisch Wert.

328
00:16:35,790 --> 00:16:39,730
Ich gehe voran gehen
und greifen diesen Sound hier.

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

330
00:16:42,900 --> 00:16:46,420
Also lassen Sie mich los, und lassen Sie mich
stoppen Sie das Programm für einen Moment.

331
00:16:46,420 --> 00:16:52,070
Ich werde die folgende aufnehmen,
den Zugriff auf das Mikrofon.

332
00:16:52,070 --> 00:16:53,181
>> Auf geht's.

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

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

335
00:16:58,710 --> 00:17:01,140
Lassen Sie uns versuchen schon wieder.

336
00:17:01,140 --> 00:17:02,279
Auf geht's.

337
00:17:02,279 --> 00:17:03,570
OK, ich nahm die falsche Sache.

338
00:17:03,570 --> 00:17:04,580
Auf geht's.

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

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

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

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

343
00:17:09,300 --> 00:17:10,791
Jetzt muss ich davon loszuwerden.

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

345
00:17:11,290 --> 00:17:13,950
>> So, jetzt habe ich eine
Aufnahme von nur "autsch."

346
00:17:13,950 --> 00:17:18,040
So, jetzt werde ich gehen
vor und nennen das "Aua."

347
00:17:18,040 --> 00:17:20,270
Ich gehe zurück zu gehen
meine Skripte, und jetzt

348
00:17:20,270 --> 00:17:25,460
Hinweis Es ist dieser Block die aufgerufen wird,
Ton abspielen "Miau" oder spielen sound "autsch."

349
00:17:25,460 --> 00:17:28,920
Ich werde dies zu ziehen, und wo
sollte ich das für komische Wirkung setzen?

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

351
00:17:31,740 --> 00:17:37,860
Ja, so jetzt ist es Art von
Buggy, denn jetzt diese BLOCK--

352
00:17:37,860 --> 00:17:42,050
feststellen, wie diese ", wenn am Rand,
Bounce "ist eine Art selbstständig.

353
00:17:42,050 --> 00:17:43,704
Also muss ich dies zu beheben.

354
00:17:43,704 --> 00:17:44,870
Lassen Sie mich gehen Sie vor und tun dies.

355
00:17:44,870 --> 00:17:48,630
Lassen Sie mich dies loszuwerden und gehen Sie zurück
zu unserer ursprünglichen, bewusster

356
00:17:48,630 --> 00:17:49,870
Funktionalität.

357
00:17:49,870 --> 00:18:01,080
So ", wenn Rand zu berühren, dann" Ich möchte,
zu drehen, wie Victoria vorgeschlagen,

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

359
00:18:02,480 --> 00:18:05,497
Und ich will spielen
der Klang "autsch" da?

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

361
00:18:11,800 --> 00:18:15,580
>> Ja, bemerken es draußen
dass gelben Block.

362
00:18:15,580 --> 00:18:17,680
Also auch dies wäre ein
Fehler, aber ich habe es bemerkt.

363
00:18:17,680 --> 00:18:21,290
So, hier werde ich es nach oben ziehen,
und Mitteilung jetzt ist es in der "if".

364
00:18:21,290 --> 00:18:24,250
So ist das "wenn" ist diese Art
von wie armförmigen Blot

365
00:18:24,250 --> 00:18:26,260
das wird nur zu
tun, was in ihm ist.

366
00:18:26,260 --> 00:18:30,216
So, jetzt, wenn ich Verkleinern bei
die Gefahr von annoying--

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

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Aua, aua, aua.

369
00:18:36,470 --> 00:18:39,910
>> DAVID MALAN: Und es
gehen wird nur für immer.

370
00:18:39,910 --> 00:18:44,160
Jetzt nur noch die Dinge beschleunigen
hier, lassen Sie mich gehen Sie vor und öffnen,

371
00:18:44,160 --> 00:18:50,460
Lassen Sie uns sagen-- mich einige gehen lassen
meiner eigenen Sachen aus der Klasse.

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

373
00:18:53,000 --> 00:19:00,220
Und lassen Sie mich öffnen, lassen Sie uns sagen, diese
ein von einem unserer Lehre Gefährten gemacht

374
00:19:00,220 --> 00:19:01,500
vor ein paar Jahren.

375
00:19:01,500 --> 00:19:04,732
So einige von euch vielleicht erinnern
Dieses Spiel von gestern,

376
00:19:04,732 --> 00:19:05,940
und es ist tatsächlich bemerkenswert.

377
00:19:05,940 --> 00:19:08,190
Auch wenn wir getan haben, die
einfachste jetzt von Programmen,

378
00:19:08,190 --> 00:19:09,980
lassen Sie uns überlegen, was diese
tatsächlich aussieht.

379
00:19:09,980 --> 00:19:10,650
Lassen Sie mich spielen getroffen.

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

381
00:19:14,210 --> 00:19:18,980
>> Also in diesem Spiel haben wir ein
Frosch, und mit den Pfeil keys--

382
00:19:18,980 --> 00:19:23,340
er nimmt größere Schritte als ich remember--
Ich habe die Kontrolle über diesen Frosch.

383
00:19:23,340 --> 00:19:29,630
Und das Ziel ist, über das zu bekommen beschäftigt
Straße, ohne in die Autos laufen.

384
00:19:29,630 --> 00:19:34,735
Und lassen Sie uns see--, wenn ich hier steigen, ich
warten müssen, für ein Protokoll zu blättern durch.

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

386
00:19:38,130 --> 00:19:39,274
Das fühlt sich an wie ein Bug.

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

388
00:19:42,240 --> 00:19:43,495
Dies ist eine Art eines Fehlers.

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

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

391
00:19:46,480 --> 00:19:51,550
Ich bin auf das hier,
dort, und Sie dann halten

392
00:19:51,550 --> 00:19:54,100
, bis Sie alle bekommen
die Frösche zu den Lilienauflagen.

393
00:19:54,100 --> 00:19:55,920
Nun könnte so aussehen
umso komplexer,

394
00:19:55,920 --> 00:19:57,840
aber lassen Sie uns versuchen zu brechen
diese nach unten geistig

395
00:19:57,840 --> 00:20:00,040
und verbal in seine Komponentenblöcke.

396
00:20:00,040 --> 00:20:03,910
So gibt es wahrscheinlich ein Rätsel
Stück, das wir noch nicht gesehen haben

397
00:20:03,910 --> 00:20:07,440
aber das ist die Reaktion auf Tastatureingaben,
um die Dinge traf ich auf der Tastatur.

398
00:20:07,440 --> 00:20:11,660
>> So gibt es wahrscheinlich eine Art von
Block, der sagt, wenn Schlüssel gleich hoch,

399
00:20:11,660 --> 00:20:15,965
dann tun Sie etwas mit Scratch--
verschieben Sie es vielleicht 10 Schritte auf diese Weise.

400
00:20:15,965 --> 00:20:20,240
Wenn nach unten gedrückt wird, bewegen sich 10 Stufen
auf diese Weise, oder linke Taste, bewegen sich 10 Stufen

401
00:20:20,240 --> 00:20:21,710
auf diese Weise, 10 Schritte, dass.

402
00:20:21,710 --> 00:20:23,644
Ich habe gedreht deutlich die Katze in einen Frosch.

403
00:20:23,644 --> 00:20:26,060
Also das ist genau dort, wo die
Kostüm, als Scratch Anrufe es-- wir

404
00:20:26,060 --> 00:20:28,440
gerade importiert ein Bild des Frosches.

405
00:20:28,440 --> 00:20:29,570
>> Aber was sonst geschieht?

406
00:20:29,570 --> 00:20:32,794
Welche anderen Zeilen Code,
was andere Puzzleteile

407
00:20:32,794 --> 00:20:35,460
tat Blake, unsere Lehre Kerl,
Verwenden Sie in diesem Programm, offenbar?

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

409
00:20:38,320 --> 00:20:42,730
Was macht alles move--
was Programmierung konstruieren?

410
00:20:42,730 --> 00:20:44,950
>> Bewegung, sure-- so die
Block verschieben, sicher.

411
00:20:44,950 --> 00:20:49,330
Und was ist das Zug-Block
innerhalb von, wahrscheinlich?

412
00:20:49,330 --> 00:20:52,850
Ja, eine Art Schleife, vielleicht ein
für immer blockieren, vielleicht eine Wiederholung BLOCK--

413
00:20:52,850 --> 00:20:54,070
wiederholen, bis Block.

414
00:20:54,070 --> 00:20:57,330
Und das ist es, was die Protokolle machen und
die Lilienauflagen und alles andere bewegen

415
00:20:57,330 --> 00:20:57,990
vor und zurück.

416
00:20:57,990 --> 00:21:00,270
Es passiert einfach endlos.

417
00:21:00,270 --> 00:21:03,180
>> Warum sind einige der Autos
bewegt sich schneller als die anderen?

418
00:21:03,180 --> 00:21:06,607
Was ist anders an diesen Programmen?

419
00:21:06,607 --> 00:21:09,690
Ja, wahrscheinlich einige von ihnen nehmen
mehr Stufen auf einmal und einige von ihnen

420
00:21:09,690 --> 00:21:10,690
weniger Schritte auf einmal.

421
00:21:10,690 --> 00:21:14,670
Und die optische Wirkung
ist schnell im Vergleich zu langsam.

422
00:21:14,670 --> 00:21:16,030
>> Was denken Sie, ist passiert?

423
00:21:16,030 --> 00:21:19,700
Als ich meinen Frosch bekam den ganzen Weg
über die Straße und den Fluss

424
00:21:19,700 --> 00:21:23,560
auf der Lilienauflage, etwas
Bemerkenswert ist passiert.

425
00:21:23,560 --> 00:21:26,540
Was ist passiert, sobald ich das getan?

426
00:21:26,540 --> 00:21:27,210
Es hielt an.

427
00:21:27,210 --> 00:21:29,680
Das Frosch gestoppt und
Ich bekam einen zweiten Frosch.

428
00:21:29,680 --> 00:21:33,155
Also, was Konstrukt muss sein
verwendet es, was Funktion?

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

430
00:21:36,020 --> 00:21:38,660
>> Ja, so gibt es eine Art von
"If" Bedingung dort oben auch.

431
00:21:38,660 --> 00:21:41,909
Und es stellt sich out-- wir nicht sehen this--
aber es gibt andere Blöcke in dort, dass

432
00:21:41,909 --> 00:21:45,300
wenn man sagen kann, berühren
eine andere Sache, auf dem Bildschirm,

433
00:21:45,300 --> 00:21:47,720
wenn Sie die Seerosenblatt sind zu berühren, "dann."

434
00:21:47,720 --> 00:21:50,810
Und dann, wenn wir
machen die zweite Frosch erscheinen.

435
00:21:50,810 --> 00:21:54,969
Also auch wenn dieses Spiel ist sicher
sehr veraltet, auch wenn auf den ersten Blick

436
00:21:54,969 --> 00:21:58,010
es gibt so viel los on-- und Blake
nicht das in zwei Minuten Peitsche,

437
00:21:58,010 --> 00:22:00,390
es nahm ihn wahrscheinlich mehrere
Stunden um dieses Spiel zu erstellen

438
00:22:00,390 --> 00:22:03,850
basierend auf seinem Gedächtnis oder Videos
des vergangenen Jahres die Version davon.

439
00:22:03,850 --> 00:22:07,940
Aber all diese kleinen Dinge
geht auf dem Bildschirm in Isolation

440
00:22:07,940 --> 00:22:11,550
lässt sich auf diese sehr einfach
constructs-- Bewegungen oder Aussagen

441
00:22:11,550 --> 00:22:15,519
wie wir haben diskutiert, Loops und
Bedingungen, und das ist es.

442
00:22:15,519 --> 00:22:17,060
Es gibt ein paar andere ausgefallener Funktionen.

443
00:22:17,060 --> 00:22:19,130
Einige von ihnen sind rein
ästhetischen oder akustisch,

444
00:22:19,130 --> 00:22:20,964
wie die Geräusche, die ich mit nur gespielt.

445
00:22:20,964 --> 00:22:23,380
Aber in den meisten Fällen, Sie
haben in dieser Sprache, Scratch,

446
00:22:23,380 --> 00:22:25,350
alle grundlegenden
Bausteine, dass Sie

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

448
00:22:29,280 --> 00:22:32,960
und jede Anzahl von anderen Sprachen.

449
00:22:32,960 --> 00:22:36,720
Haben Sie Fragen zu Scratch?

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

451
00:22:37,220 --> 00:22:40,303
So werden wir nicht in tiefer Kratzer tauchen,
obwohl sind Sie an diesem Wochenende willkommen,

452
00:22:40,303 --> 00:22:42,860
besonders wenn Sie Kinder haben, oder
Nichten und Neffen und solche,

453
00:22:42,860 --> 00:22:44,220
sie Scratch einzuführen.

454
00:22:44,220 --> 00:22:47,960
Es ist eigentlich eine wunderbar spielerische
Umwelt mit, wie die Autoren sagen,

455
00:22:47,960 --> 00:22:49,120
sehr hohe Decken.

456
00:22:49,120 --> 00:22:51,670
Auch wenn wir begannen mit
sehr Low-Level-Details,

457
00:22:51,670 --> 00:22:54,890
Sie können wirklich tun ziemlich viel
mit sich, und dies ist vielleicht

458
00:22:54,890 --> 00:22:57,360
eine Demonstration genau das.

459
00:22:57,360 --> 00:23:02,920
>> Aber lassen Sie uns den Übergang jetzt zu etwas mehr
anspruchsvolle Probleme, wenn man so will,

460
00:23:02,920 --> 00:23:05,870
bekannt als "Suche" und
"Sortierung" im Allgemeinen.

461
00:23:05,870 --> 00:23:09,500
Wir hatten dieses Telefonbuch earlier-- hier
ein anderer nur für discussion--

462
00:23:09,500 --> 00:23:13,460
dass wir waren in der Lage zu suchen
effizienter, weil

463
00:23:13,460 --> 00:23:15,270
einer wesentlichen Annahme.

464
00:23:15,270 --> 00:23:17,655
Und nur klar zu sein, was
Annahme war ich machen

465
00:23:17,655 --> 00:23:19,280
bei der Suche durch dieses Telefonbuch?

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

467
00:23:23,342 --> 00:23:25,300
Dass Mike Smith war in
das Telefonbuch, obwohl ich

468
00:23:25,300 --> 00:23:27,410
wäre in der Lage zu handhaben
das Szenario ohne ihn

469
00:23:27,410 --> 00:23:30,720
da, wenn ich gerade aufgehört zu früh.

470
00:23:30,720 --> 00:23:31,806
Das Buch ist alphabetisch.

471
00:23:31,806 --> 00:23:33,930
Und das ist ein sehr großzügiges
Annahme, denn das

472
00:23:33,930 --> 00:23:36,580
bedeutet someone-- Ich bin ein bisschen
von Kurvenschneiden,

473
00:23:36,580 --> 00:23:40,580
wie ich bin schneller, weil jemand
sonst tat für mich eine Menge harter Arbeit.

474
00:23:40,580 --> 00:23:43,120
>> Aber was, wenn das Telefon
Buch wurden unsortiert?

475
00:23:43,120 --> 00:23:47,050
Vielleicht Verizon bekam faul, warf nur
alle Namen und Nummern drin

476
00:23:47,050 --> 00:23:50,120
vielleicht in der Reihenfolge, in der sie
haben sich für Telefon-Service.

477
00:23:50,120 --> 00:23:54,570
Und wie lange dauert es mir
jemanden wie Mike Smith zu finden?

478
00:23:54,570 --> 00:23:58,160
1000 Seite Telefon book--, wie viele
Seiten muss ich schauen Sie durch?

479
00:23:58,160 --> 00:23:58,905
>> Alle von ihnen.

480
00:23:58,905 --> 00:24:00,030
Sie sind eine Art von Glück.

481
00:24:00,030 --> 00:24:03,420
Sie müssen buchstäblich an jeder Blick
Seite, wenn das Telefonbuch gerade ist

482
00:24:03,420 --> 00:24:04,450
zufällig geordnet.

483
00:24:04,450 --> 00:24:06,910
Sie könnten mit etwas Glück und Mike finden
auf der ersten Seite, weil er

484
00:24:06,910 --> 00:24:08,826
war der erste Kunde
Telefon-Service zu bestellen.

485
00:24:08,826 --> 00:24:10,760
Aber er könnte die letzte gewesen, auch.

486
00:24:10,760 --> 00:24:12,500
>> So zufälliger Reihenfolge ist nicht gut.

487
00:24:12,500 --> 00:24:16,750
Also angenommen, wir haben das zu sortieren
Telefonbuch oder im allgemeinen Sortierdaten

488
00:24:16,750 --> 00:24:18,520
dass wir gegeben habe.

489
00:24:18,520 --> 00:24:19,440
Wie können wir das machen?

490
00:24:19,440 --> 00:24:21,360
>> Nun, lassen Sie mich nur versuchen,
ein einfaches Beispiel hier.

491
00:24:21,360 --> 00:24:24,290
Lassen Sie mich gehen Sie vor und werfen ein
paar Zahlen auf dem Brett.

492
00:24:24,290 --> 00:24:35,480
Nehmen wir an, die Zahlen, die wir haben sind,
lassen Sie uns sagen, vier, zwei, eins und drei.

493
00:24:35,480 --> 00:24:38,390
Und Ben, sortieren Sie diese Zahlen für uns.

494
00:24:38,390 --> 00:24:39,017
>> OK gut.

495
00:24:39,017 --> 00:24:39,850
Wie hast du das gemacht?

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

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

498
00:24:43,230 --> 00:24:44,710
So beginnen Sie mit dem kleinsten
Wert und die höchste,

499
00:24:44,710 --> 00:24:46,084
und das ist wirklich eine gute Intuition.

500
00:24:46,084 --> 00:24:48,080
Und erkennen, dass wir
Menschen sind eigentlich ziemlich

501
00:24:48,080 --> 00:24:49,913
gut bei der Lösung von Problemen
wie diese, zumindest

502
00:24:49,913 --> 00:24:51,810
wenn die Daten relativ klein ist.

503
00:24:51,810 --> 00:24:54,860
Sobald Sie Hunderte haben starten
aus Zahlen, Tausende von Zahlen,

504
00:24:54,860 --> 00:24:58,440
Millionen von Zahlen, Ben wahrscheinlich
konnte es nicht tun recht schnell,

505
00:24:58,440 --> 00:25:00,620
unter der Annahme, dass es
Lücken in den Zahlen.

506
00:25:00,620 --> 00:25:03,450
Ziemlich einfach zu einer Million zu zählen
ansonsten aufwendig nur Zeit.

507
00:25:03,450 --> 00:25:07,150
>> So ist der Algorithmus es klingt
wie Ben gerade jetzt verwendet

508
00:25:07,150 --> 00:25:08,930
war für die kleinste Nummer suchen.

509
00:25:08,930 --> 00:25:12,900
Also auch wenn wir Menschen nehmen
in einer Vielzahl von Informationen visuell,

510
00:25:12,900 --> 00:25:14,830
ein Computer ist eigentlich
ein wenig begrenzt.

511
00:25:14,830 --> 00:25:17,560
Der Computer kann nur
Blick auf ein Byte zu einem Zeitpunkt,

512
00:25:17,560 --> 00:25:20,770
oder vielleicht vier Bytes auf Zeit--
in diesen Tagen vielleicht 8 Bytes auf Zeit--

513
00:25:20,770 --> 00:25:24,450
aber eine sehr kleine Zahl
von Bytes zu einem gegebenen Zeitpunkt.

514
00:25:24,450 --> 00:25:28,480
>> Also da wir wirklich haben
vier separate Werte hier--

515
00:25:28,480 --> 00:25:32,440
und Sie können von Ben denken, wie mit
Scheuklappen auf, wenn er einen Computer so waren

516
00:25:32,440 --> 00:25:36,450
dass er kann nichts anderes sehen
als eine Nummer in einem Zeit--

517
00:25:36,450 --> 00:25:39,720
so werden wir im Allgemeinen annehmen, wie in
Englisch, wir werden von rechts nach links zu lesen.

518
00:25:39,720 --> 00:25:42,870
So ist die erste Zahl Ben wahrscheinlich angesehen
an war vier und dann sehr schnell

519
00:25:42,870 --> 00:25:44,770
erkannte, dass ein ziemlich großer ist
number-- lassen Sie mich halten suchen.

520
00:25:44,770 --> 00:25:45,357
>> Es gibt zwei.

521
00:25:45,357 --> 00:25:45,940
Warte eine Minute.

522
00:25:45,940 --> 00:25:47,070
Zwei kleiner als vier.

523
00:25:47,070 --> 00:25:47,986
Ich werde zu erinnern.

524
00:25:47,986 --> 00:25:49,070
Zwei ist jetzt das kleinste.

525
00:25:49,070 --> 00:25:50,417
Nun one-- das ist noch besser.

526
00:25:50,417 --> 00:25:51,250
Das ist sogar noch kleiner.

527
00:25:51,250 --> 00:25:54,000
Ich werde über zwei zu vergessen
und nur ein erinnere mich jetzt.

528
00:25:54,000 --> 00:25:56,550
>> Und konnte er suchen stoppen?

529
00:25:56,550 --> 00:25:58,360
Nun, er könnte auf der Grundlage
Die Informationen in diesem,

530
00:25:58,360 --> 00:26:00,477
aber er würde besser Suche
der Rest der Liste.

531
00:26:00,477 --> 00:26:02,060
Denn was ist, wenn Null waren in der Liste?

532
00:26:02,060 --> 00:26:03,643
Was ist, wenn negative in der Liste waren?

533
00:26:03,643 --> 00:26:07,720
Er weiß nur, dass seine Antwort
richtig ist, wenn er erschöpfend

534
00:26:07,720 --> 00:26:08,729
überprüft die gesamte Liste.

535
00:26:08,729 --> 00:26:10,020
Also schauen wir uns den Rest davon.

536
00:26:10,020 --> 00:26:11,394
Three-- das war eine Verschwendung von Zeit.

537
00:26:11,394 --> 00:26:13,540
Haben Sie Pech, aber ich war
noch richtig, dies zu tun.

538
00:26:13,540 --> 00:26:17,857
Und so jetzt ist er vermutlich
die kleinste Zahl, ausgewählt

539
00:26:17,857 --> 00:26:20,440
und legte es erst am Anfang
der Liste, wie ich hier finden.

540
00:26:20,440 --> 00:26:23,480
Nun, was hast du als nächstes, obwohl
Sie dachte nicht daran, es fast

541
00:26:23,480 --> 00:26:25,962
in diesem Umfang?

542
00:26:25,962 --> 00:26:27,670
Wiederholen Sie den Vorgang,
so eine Art Schleife.

543
00:26:27,670 --> 00:26:28,920
Es gibt eine bekannte Idee.

544
00:26:28,920 --> 00:26:30,860
Hier ist also vier.

545
00:26:30,860 --> 00:26:32,110
Das ist derzeit der kleinste.

546
00:26:32,110 --> 00:26:33,220
Das ist ein Kandidat.

547
00:26:33,220 --> 00:26:33,900
Nicht länger.

548
00:26:33,900 --> 00:26:34,770
Jetzt habe ich zwei gesehen.

549
00:26:34,770 --> 00:26:36,630
Das ist der nächste kleinste Element.

550
00:26:36,630 --> 00:26:40,800
Three-- das ist nicht kleiner, so
Ben kann nun die beiden auszureißen.

551
00:26:40,800 --> 00:26:44,510
>> Und jetzt wiederholen wir den Prozess und
natürlich drei wird nächstes herausgezogen.

552
00:26:44,510 --> 00:26:45,420
Wiederholen Sie den Vorgang.

553
00:26:45,420 --> 00:26:46,990
Vier wird herausgezogen.

554
00:26:46,990 --> 00:26:50,140
Und jetzt sind wir aus Zahlen,
so muss die Liste sortiert werden.

555
00:26:50,140 --> 00:26:51,960
>> Und in der Tat ist dies ein formaler Algorithmus.

556
00:26:51,960 --> 00:26:56,610
Ein Informatiker würde
nennen diese "Auswahl sortieren"

557
00:26:56,610 --> 00:27:00,880
die Idee ist, sortieren ein
Liste iteratively-- wieder

558
00:27:00,880 --> 00:27:03,807
und immer wieder die Auswahl
die kleinste Zahl.

559
00:27:03,807 --> 00:27:06,140
Und was ist das über es nett ist,
es ist nur so verdammt intuitiv.

560
00:27:06,140 --> 00:27:07,470
Es ist so einfach.

561
00:27:07,470 --> 00:27:11,100
Und Sie können das gleiche wiederholen
Betrieb wieder und wieder.

562
00:27:11,100 --> 00:27:12,150
Es ist einfach.

563
00:27:12,150 --> 00:27:17,170
>> In diesem Fall war es schnell, aber
wie lange dauert es eigentlich?

564
00:27:17,170 --> 00:27:19,880
Lassen Sie uns machen es scheinen, und
fühle mich ein wenig langweiliger.

565
00:27:19,880 --> 00:27:24,150
So eins, zwei, drei, vier, fünf sechs,
sieben, acht, neun, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- willkürliche Zahl.

567
00:27:26,160 --> 00:27:28,780
Ich wollte nur mehr diese
Zeit als nur die vier.

568
00:27:28,780 --> 00:27:30,780
Also, wenn ich habe eine ganze bekam
Reihe von Zahlen now-- es

569
00:27:30,780 --> 00:27:32,420
nicht einmal eine Rolle,
was sie sind-- wir

570
00:27:32,420 --> 00:27:34,380
darüber nachdenken, was diese
Algorithmus ist wirklich wie.

571
00:27:34,380 --> 00:27:35,857
>> Angenommen, es gibt dort Zahlen.

572
00:27:35,857 --> 00:27:38,190
Auch hier spielt es keine Rolle, was
sie sind, aber sie sind zufällig.

573
00:27:38,190 --> 00:27:39,679
Ich bewerbe mich Ben-Algorithmus.

574
00:27:39,679 --> 00:27:41,220
Ich brauche die kleinste Nummer auszuwählen.

575
00:27:41,220 --> 00:27:41,761
Was mache ich?

576
00:27:41,761 --> 00:27:44,240
Und ich werde körperlich
tun sie es diesmal zu handeln.

577
00:27:44,240 --> 00:27:46,099
Suchen, suchen,
suchen, suchen, suchen.

578
00:27:46,099 --> 00:27:48,140
Erst durch die Zeit, die ich bekommen
das Ende der Liste können

579
00:27:48,140 --> 00:27:51,230
Ich weiß, das kleinste
Zahl war zwei diesmal.

580
00:27:51,230 --> 00:27:52,720
Man ist nicht in der Liste.

581
00:27:52,720 --> 00:27:54,400
Also habe ich zwei zurückgewiesen.

582
00:27:54,400 --> 00:27:55,590
>> Was mache ich als nächstes?

583
00:27:55,590 --> 00:27:58,600
Suchen, suchen, suchen, suchen.

584
00:27:58,600 --> 00:28:02,250
Nun fand ich die Nummer sieben, weil
es gibt Lücken in diesen numbers--

585
00:28:02,250 --> 00:28:03,300
sondern nur willkürlich.

586
00:28:03,300 --> 00:28:03,800
Gut.

587
00:28:03,800 --> 00:28:06,030
So, jetzt kann ich sieben niedergeschlagen.

588
00:28:06,030 --> 00:28:08,860
Suchen Sie suchen, suchen.

589
00:28:08,860 --> 00:28:11,030
>> Jetzt gehe davon aus I,
natürlich, dass Ben nicht

590
00:28:11,030 --> 00:28:14,780
haben extra RAM, extra
Speicher, denn, natürlich,

591
00:28:14,780 --> 00:28:16,080
Ich freue mich auf die gleiche Zahl.

592
00:28:16,080 --> 00:28:18,246
Sicherlich hätte ich in Erinnerung
alle diese Zahlen,

593
00:28:18,246 --> 00:28:19,930
und das ist absolut wahr.

594
00:28:19,930 --> 00:28:22,610
Aber wenn Ben alles erinnert
der Zahlen, die er gesehen hat,

595
00:28:22,610 --> 00:28:24,430
er hat sich nicht wirklich gemacht
wesentliche Fortschritte

596
00:28:24,430 --> 00:28:26,170
weil er bereits
die Fähigkeit zur Suche

597
00:28:26,170 --> 00:28:27,540
durch die Zahlen auf dem Brett.

598
00:28:27,540 --> 00:28:29,373
Erinnern an alle der
Zahlen nicht hilft,

599
00:28:29,373 --> 00:28:32,490
denn er kann immer noch als ein Computer
schauen nur auf, wir haben gesagt, eine Nummer

600
00:28:32,490 --> 00:28:33,080
zu einem Zeitpunkt.

601
00:28:33,080 --> 00:28:35,760
Also gibt es keine Art von Cheat
dort, dass Sie nutzen können.

602
00:28:35,760 --> 00:28:39,170
>> So in Wirklichkeit, wie ich
halten Sie die Liste der Suche,

603
00:28:39,170 --> 00:28:44,200
Ich habe buchstäblich nur weitermachen
hin und her durch sie und zupft aus

604
00:28:44,200 --> 00:28:45,710
der nächste kleinste Zahl.

605
00:28:45,710 --> 00:28:48,810
Und wie Sie können Art schließen
von meinem dummen Bewegungen,

606
00:28:48,810 --> 00:28:50,860
dies wird nur sehr
sehr schnell langweilig,

607
00:28:50,860 --> 00:28:54,850
und ich scheinen zu gehen zurück und
her, hin und her ziemlich viel.

608
00:28:54,850 --> 00:29:03,220
Nun, fair zu sein, ich habe nicht zu gehen
ganz so, na ja, lassen Sie uns see-- fair zu sein,

609
00:29:03,220 --> 00:29:06,310
Ich muss nicht ganz gehen
so viele Schritte jedes Mal.

610
00:29:06,310 --> 00:29:09,200
Denn natürlich, wie ich
Wählen Sie Nummern aus der Liste,

611
00:29:09,200 --> 00:29:11,860
die verbleibende Liste wird kürzer.

612
00:29:11,860 --> 00:29:14,240
>> Und so lassen Sie uns darüber nachdenken,
wie viele Schritte ich bin eigentlich

613
00:29:14,240 --> 00:29:16,010
durch jedes Mal latschen.

614
00:29:16,010 --> 00:29:18,950
In der ersten Situation
wir hatten 16 Zahlen,

615
00:29:18,950 --> 00:29:22,210
und so maximally-- lassen Sie uns einfach
tun dies für einen discussion--

616
00:29:22,210 --> 00:29:25,640
Ich hatte bis 16 zu sehen
Zahlen die kleinste zu finden.

617
00:29:25,640 --> 00:29:28,420
Aber einmal gezupft ich aus
die kleinste Zahl, wie

618
00:29:28,420 --> 00:29:30,590
lange war die restliche Liste, natürlich?

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

620
00:29:31,420 --> 00:29:34,670
So, wie viele Zahlen tat Ben oder ich habe
um durch das zweite Mal zu suchen?

621
00:29:34,670 --> 00:29:36,832
15, nur zu gehen und die kleinste finden.

622
00:29:36,832 --> 00:29:39,540
Aber jetzt, natürlich, die Liste ist,
Auch kleiner, als es vorher war.

623
00:29:39,540 --> 00:29:42,540
So, wie viele Schritte habe ich
haben die nächste Zeit in Anspruch nehmen?

624
00:29:42,540 --> 00:29:49,970
14 und dann 13 und dann 12 plus Punkt,
Punkt, Punkt, bis ich mit nur einem links bin.

625
00:29:49,970 --> 00:29:53,146
So, jetzt ein Informatiker würde
fragen, na ja, was alles gleich macht das?

626
00:29:53,146 --> 00:29:55,770
Es entspricht tatsächlich einige konkrete
Eine Zahl, die wir könnten sicher

627
00:29:55,770 --> 00:30:00,490
arithmetisch zu tun, aber wir wollen reden
über die Effizienz der Algorithmen

628
00:30:00,490 --> 00:30:04,940
ein wenig mehr formelhaft,
unabhängig davon, wie lange die Liste ist.

629
00:30:04,940 --> 00:30:06,240
>> Und so wissen Sie was?

630
00:30:06,240 --> 00:30:09,860
Dies ist 16, aber wie ich schon sagte,
Nennen wir nur die Größe des Problems

631
00:30:09,860 --> 00:30:10,970
n, wobei n eine Zahl ist.

632
00:30:10,970 --> 00:30:13,220
Vielleicht ist es 16, vielleicht ist es
drei, vielleicht ist es eine Million.

633
00:30:13,220 --> 00:30:13,761
Ich weiß es nicht.

634
00:30:13,761 --> 00:30:14,390
Ich interessiere mich nicht.

635
00:30:14,390 --> 00:30:16,520
Was ich wirklich will, ist
Eine Formel, die ich kann,

636
00:30:16,520 --> 00:30:19,420
Mit diesem Algorithmus zu vergleichen
gegen andere Algorithmen

637
00:30:19,420 --> 00:30:22,350
dass jemand behaupten
besser oder schlechter sind.

638
00:30:22,350 --> 00:30:25,430
>> So stellt sich heraus, und ich nur
weiß, dass dies von der Grundschule,

639
00:30:25,430 --> 00:30:34,790
dass dies tatsächlich funktioniert, um die gleiche
etwas wie n über n plus eins mehr als zwei.

640
00:30:34,790 --> 00:30:40,020
Und dies geschieht auf gleich, von
Natürlich n Quadrat plus n mehr als zwei.

641
00:30:40,020 --> 00:30:43,250
Also, wenn ich wollte eine Formel
für wie viele Schritte

642
00:30:43,250 --> 00:30:46,330
Beteiligt waren überhaupt in der Suche
dieser Zahlen immer wieder

643
00:30:46,330 --> 00:30:52,681
und immer wieder, würde ich sagen,
es ist n Quadrat plus n mehr als zwei.

644
00:30:52,681 --> 00:30:53,430
Aber weißt du was?

645
00:30:53,430 --> 00:30:54,500
Das sieht einfach unordentlich.

646
00:30:54,500 --> 00:30:56,470
Ich will nur wirklich ein
allgemeinen Sinn der Dinge.

647
00:30:56,470 --> 00:30:58,810
Und Sie erinnern sich vielleicht aus
High School, dass es

648
00:30:58,810 --> 00:31:00,660
ist der Begriff der höchsten Ordnung Begriff.

649
00:31:00,660 --> 00:31:05,300
Welche dieser Bedingungen, die n
quadriert, die n oder die Hälfte,

650
00:31:05,300 --> 00:31:07,550
hat den größten Einfluss im Laufe der Zeit?

651
00:31:07,550 --> 00:31:11,920
Je größer n wird, die
dieser Angelegenheiten am meisten?

652
00:31:11,920 --> 00:31:15,560
>> Mit anderen Worten, wenn ich stecken
in einer Million, n quadriert

653
00:31:15,560 --> 00:31:17,900
wird sehr wahrscheinlich zu sein
der dominierende Faktor,

654
00:31:17,900 --> 00:31:21,670
weil eine Million Mal
selbst ist viel größer

655
00:31:21,670 --> 00:31:23,682
als plus eine zusätzliche Million.

656
00:31:23,682 --> 00:31:24,390
So wissen Sie was?

657
00:31:24,390 --> 00:31:27,305
Dies ist so ein verdammt groß
Anzahl, wenn Sie eine Zahl-Platz.

658
00:31:27,305 --> 00:31:28,430
Dies ist nicht wirklich wichtig.

659
00:31:28,430 --> 00:31:30,596
Wir gehen nur Kreuz,
und vergessen Sie es.

660
00:31:30,596 --> 00:31:34,250
Und so würde ein Informatiker sagen
dass die Effizienz dieses Algorithmus

661
00:31:34,250 --> 00:31:37,850
in der Größenordnung von n squared--
Ich meine wirklich eine Annäherung.

662
00:31:37,850 --> 00:31:40,810
Es ist eine Art von ungefähr n im Quadrat.

663
00:31:40,810 --> 00:31:44,130
Im Laufe der Zeit ist, desto größer
und größer n wird, diese

664
00:31:44,130 --> 00:31:47,610
ist eine gute Schätzung für das, was die
Effizienz oder mangelnde Effizienz

665
00:31:47,610 --> 00:31:49,400
tatsächlich dieses Algorithmus ist.

666
00:31:49,400 --> 00:31:52,040
Und ich ableiten, dass, natürlich,
von tatsächlich die Mathematik zu tun.

667
00:31:52,040 --> 00:31:54,040
Aber jetzt bin ich nur winken
meine Hände, weil ich gerade

668
00:31:54,040 --> 00:31:55,790
ein allgemeines Gefühl dieses Algorithmus soll.

669
00:31:55,790 --> 00:31:58,850
>> Also mit der gleichen Logik, inzwischen
Lassen Sie uns einen anderen Algorithmus betrachten

670
00:31:58,850 --> 00:32:01,162
wir sahen bereits at-- lineare Suche.

671
00:32:01,162 --> 00:32:02,870
Wenn ich war auf der Suche
für das Telefon book--

672
00:32:02,870 --> 00:32:05,980
Sortierung es nicht, auf der Suche
über das Telefon book--

673
00:32:05,980 --> 00:32:09,197
wir immer wieder gesagt, dass es
1.000 Schritte oder 500 Stufen.

674
00:32:09,197 --> 00:32:10,280
Aber lassen wir das verallgemeinern.

675
00:32:10,280 --> 00:32:12,860
Wenn es gibt, n-Seiten in
das Telefonbuch, was ist

676
00:32:12,860 --> 00:32:17,250
die Laufzeit oder die
Effizienz der linearen Suche?

677
00:32:17,250 --> 00:32:19,750
Es ist in der Größenordnung von
wie viele Schritte zu finden

678
00:32:19,750 --> 00:32:24,210
Mike Smith durch lineare Suche, die
erste Algorithmus oder auch der zweite?

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

680
00:32:27,240 --> 00:32:31,710
>> Im schlimmsten Fall, Mike
ist am Ende des Buches.

681
00:32:31,710 --> 00:32:35,590
Also, wenn das Telefonbuch hat 1.000 Seiten,
wir das letzte Mal, im schlimmsten Fall,

682
00:32:35,590 --> 00:32:38,380
es könnte dauern ungefähr, wie
viele Seiten Mike zu finden?

683
00:32:38,380 --> 00:32:38,990
Wie 1000.

684
00:32:38,990 --> 00:32:39,830
Es ist eine obere Schranke.

685
00:32:39,830 --> 00:32:41,790
Es ist eine denkbar schlechteste Situation.

686
00:32:41,790 --> 00:32:44,410
Aber noch einmal, wir ziehen weg
von Zahlen wie 1000 jetzt.

687
00:32:44,410 --> 00:32:45,730
Es ist nur n.

688
00:32:45,730 --> 00:32:47,470
>> Was ist also die logische Schlussfolgerung?

689
00:32:47,470 --> 00:32:50,210
Die Suche nach Mike in einem Telefon
Buch, das n-Seiten hat

690
00:32:50,210 --> 00:32:55,280
nehmen könnte, im schlimmsten Fall,
wie viele Schritte in der Größenordnung von n?

691
00:32:55,280 --> 00:32:58,110
Und in der Tat ein Computer
Wissenschaftler sagen würde

692
00:32:58,110 --> 00:33:02,340
daß die Laufzeit oder die
Leistung oder der Wirkungsgrad

693
00:33:02,340 --> 00:33:07,470
oder Ineffizienz eines Algorithmus wie
eine lineare Suche ist in der Größenordnung von n.

694
00:33:07,470 --> 00:33:10,010
Und wir können das gleiche gelten
Logik der etwas aus der Kreuzung

695
00:33:10,010 --> 00:33:13,170
wie ich gerade in die zweite
Algorithmus hatten wir mit dem Telefonbuch,

696
00:33:13,170 --> 00:33:16,040
wo gingen wir zwei Seiten auf einmal.

697
00:33:16,040 --> 00:33:20,120
>> So 1000 Seite Telefonbuch könnte
nehmen uns 500 Seite dreht, plus eins

698
00:33:20,120 --> 00:33:21,910
wenn wir doppelt so ein wenig zurück.

699
00:33:21,910 --> 00:33:26,590
Also, wenn ein Telefonbuch n Seiten hat, aber
wir tun zwei Seiten zu einer Zeit,

700
00:33:26,590 --> 00:33:28,900
das ist ungefähr das, was?

701
00:33:28,900 --> 00:33:33,190
N über zwei, so dass ist wie n mehr als zwei.

702
00:33:33,190 --> 00:33:38,490
Aber ich habe den Anspruch ein
Moment vor, dass n über two--

703
00:33:38,490 --> 00:33:41,060
das ist irgendwie der gleiche wie nur n.

704
00:33:41,060 --> 00:33:44,050
Es ist nur ein konstanter Faktor,
Informatiker sagen würde.

705
00:33:44,050 --> 00:33:45,970
Lassen Sie uns nur konzentrieren sich auf
die Variablen, really--

706
00:33:45,970 --> 00:33:47,780
die größten Variablen in der Gleichung.

707
00:33:47,780 --> 00:33:52,530
>> So lineare Suche, ob man getan
Seite zu einem Zeitpunkt oder zwei Seiten zu einer Zeit,

708
00:33:52,530 --> 00:33:54,810
Art ist im Grunde das gleiche.

709
00:33:54,810 --> 00:33:56,880
Es ist immer noch in der Größenordnung von n.

710
00:33:56,880 --> 00:34:01,930
Aber ich behauptete, mit meinem Bild früher
dass der dritte Algorithmus war nicht

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

712
00:34:02,480 --> 00:34:03,605
Es war nicht eine gerade Linie.

713
00:34:03,605 --> 00:34:08,659
Es war diese gekrümmte Linie, und die
algebraischen Formel da war was?

714
00:34:08,659 --> 00:34:11,812
Protokoll der n-- so log Basis zwei von n.

715
00:34:11,812 --> 00:34:14,520
Und wir müssen auch nicht gehen in
viele Details über Logarithmen heute,

716
00:34:14,520 --> 00:34:17,394
aber die meisten Informatiker würde nicht
sagen Sie selbst, was die Basis ist.

717
00:34:17,394 --> 00:34:20,639
Denn es ist alles nur
konstante Faktoren, so zu sprechen,

718
00:34:20,639 --> 00:34:22,659
nur leichte numerische Unterschiede.

719
00:34:22,659 --> 00:34:31,179
Und so wäre dies ein sehr häufig
Weg für besonders formale Computer

720
00:34:31,179 --> 00:34:33,949
Wissenschaftler an einem Brett oder
Programmierer auf eine weiße Tafel

721
00:34:33,949 --> 00:34:36,889
tatsächlich argumentieren die
Algorithmus sie verwenden würden

722
00:34:36,889 --> 00:34:39,500
oder was die Effizienz
ihres Algorithmus ist.

723
00:34:39,500 --> 00:34:42,960
>> Und das ist nicht unbedingt etwas,
Sie diskutieren in allen Einzelheiten,

724
00:34:42,960 --> 00:34:47,889
aber ein guter Programmierer ist jemand,
die hat einen soliden, formalen Hintergrund.

725
00:34:47,889 --> 00:34:50,120
Er ist in der Lage zu sprechen
Sie in dieser Art und Weise

726
00:34:50,120 --> 00:34:53,350
und tatsächlich machen
qualitative Argumente

727
00:34:53,350 --> 00:34:56,870
warum ein Algorithmus oder
ein Stück Software

728
00:34:56,870 --> 00:35:00,165
überlegen ist, auf eine andere in irgendeiner Weise.

729
00:35:00,165 --> 00:35:02,540
Da konnte man sicher
nur eine Person das Programm ausführen

730
00:35:02,540 --> 00:35:04,980
und zählen die Anzahl der Sekunden
Es dauert ein paar Zahlen zu sortieren,

731
00:35:04,980 --> 00:35:06,710
und Sie können einige laufen
Person Programm

732
00:35:06,710 --> 00:35:08,418
und zählen die Anzahl
Sekunden dauert es.

733
00:35:08,418 --> 00:35:12,840
Aber das ist eine allgemeinere Art und Weise,
Sie können Algorithmen zur Analyse verwenden,

734
00:35:12,840 --> 00:35:15,520
wenn man so will, nur auf
Papier oder einfach nur verbal.

735
00:35:15,520 --> 00:35:18,430
Ohne läuft sogar ohne
auch nur zu versuchen Probe-Eingänge,

736
00:35:18,430 --> 00:35:20,180
Sie können nur durch sie argumentieren.

737
00:35:20,180 --> 00:35:24,670
Und so mit einem Entwickler der Einstellung oder wenn
mit ihm oder argumentieren sie dir Art

738
00:35:24,670 --> 00:35:28,460
warum ihr Algorithmus, ihr Geheimnis
Sauce für die Suche Milliarden

739
00:35:28,460 --> 00:35:30,580
von Web-Seiten für Ihre
Unternehmen ist besser, diese

740
00:35:30,580 --> 00:35:33,302
sie sind die Arten von Argumenten
im Idealfall der Lage sein, zu machen sollte.

741
00:35:33,302 --> 00:35:35,010
Oder zumindest sind diese
die Art von Dingen

742
00:35:35,010 --> 00:35:40,211
das würde kommen in der Diskussion, bei
dest in einem sehr formalen Diskussion.

743
00:35:40,211 --> 00:35:40,710
Gut.

744
00:35:40,710 --> 00:35:44,400
Deshalb schlug Ben etwas
Auswahl Art genannt.

745
00:35:44,400 --> 00:35:48,200
Aber ich werde vorschlagen, dass es
andere Möglichkeiten, dies zu tun, zu.

746
00:35:48,200 --> 00:35:50,400
Was ich nicht wirklich mochte
über Ben-Algorithmus

747
00:35:50,400 --> 00:35:54,400
Wandern ist, dass er gehalten wird, oder
hat mich gehen, hin und her

748
00:35:54,400 --> 00:35:56,930
und hin und her und hin und her.

749
00:35:56,930 --> 00:36:04,130
Was ist, wenn stattdessen waren ich tun
so etwas wie diese Zahlen hier

750
00:36:04,130 --> 00:36:08,200
und ich waren nur mit jedem umgehen
Zahl wiederum als ich es gegeben?

751
00:36:08,200 --> 00:36:10,780
>> Mit anderen Worten, hier ist
meine Liste von Zahlen.

752
00:36:10,780 --> 00:36:12,944
Vier, eins, drei, zwei.

753
00:36:12,944 --> 00:36:14,360
Und ich werde folgendes tun.

754
00:36:14,360 --> 00:36:17,230
Ich werde die Zahlen einfügen
wo sie gehören eher

755
00:36:17,230 --> 00:36:18,980
als sie einzeln zu einer Zeit auszuwählen.

756
00:36:18,980 --> 00:36:20,820
Mit anderen Worten, hier ist die Nummer vier.

757
00:36:20,820 --> 00:36:22,430
>> Hier ist meine ursprüngliche Liste.

758
00:36:22,430 --> 00:36:25,290
Und ich werde zu halten
im Wesentlichen eine neue Liste hier.

759
00:36:25,290 --> 00:36:26,710
Das ist also die alte Liste.

760
00:36:26,710 --> 00:36:28,560
Dies ist die neue Liste.

761
00:36:28,560 --> 00:36:30,220
Ich sehe die Nummer vier erste.

762
00:36:30,220 --> 00:36:34,500
Meine neue Liste ist zunächst leer,
so ist es trivialerweise der Fall

763
00:36:34,500 --> 00:36:36,410
dass vier ist nun sortiert Liste.

764
00:36:36,410 --> 00:36:39,560
Ich nehme nur die Nummer, die ich gegeben habe,
und ich stelle es in meiner neuen Liste.

765
00:36:39,560 --> 00:36:41,460
>> Ist diese neue Liste sortiert?

766
00:36:41,460 --> 00:36:41,990
Ja.

767
00:36:41,990 --> 00:36:45,090
Es ist dumm, weil es nur ein
Element, aber es ist absolut sortiert.

768
00:36:45,090 --> 00:36:46,390
Es gibt nichts fehl am Platz.

769
00:36:46,390 --> 00:36:49,290
Es ist interessanter, dieser Algorithmus,
wenn ich an den nächsten Schritt.

770
00:36:49,290 --> 00:36:50,550
>> Jetzt habe ich ein.

771
00:36:50,550 --> 00:36:55,430
So ein, natürlich, gehört zu den
Anfang oder am Ende dieser neuen Liste?

772
00:36:55,430 --> 00:36:56,360
Der Anfang.

773
00:36:56,360 --> 00:36:58,530
Also muss ich jetzt einige Arbeit zu tun.

774
00:36:58,530 --> 00:37:01,410
Ich habe dabei, einige
Freiheiten mit meinem Marker

775
00:37:01,410 --> 00:37:03,120
nur um Dinge zeichnen
wo ich will, dass sie,

776
00:37:03,120 --> 00:37:05,320
aber das ist nicht wirklich
in einem Computer genau.

777
00:37:05,320 --> 00:37:08,530
Ein Computer, wie wir wissen, hat
RAM oder Direktzugriffsspeicher,

778
00:37:08,530 --> 00:37:12,411
und das ist ein Byte und
ein weiteres Byte und ein weiteres Byte.

779
00:37:12,411 --> 00:37:14,910
Und wenn Sie ein Gigabyte
RAM, Sie haben eine Milliarde Bytes,

780
00:37:14,910 --> 00:37:16,680
aber sie sind physisch an einem Ort.

781
00:37:16,680 --> 00:37:19,540
Sie können nicht nur Sachen bewegen
indem sie sie auf dem Reißbrett

782
00:37:19,540 --> 00:37:20,750
wo immer Sie wollen.

783
00:37:20,750 --> 00:37:24,090
Also, wenn meine neue Liste
vier Stellen im Speicher,

784
00:37:24,090 --> 00:37:27,480
leider die vier ist
bereits an der falschen Stelle.

785
00:37:27,480 --> 00:37:30,410
>> Also die Nummer einzufügen ein
Ich kann es nicht nur hier ziehen.

786
00:37:30,410 --> 00:37:31,901
Dieser Speicherplatz existiert nicht.

787
00:37:31,901 --> 00:37:35,150
Das wäre Betrug, und ich habe
bildhaft für ein paar Minuten zu betrügen

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

789
00:37:35,800 --> 00:37:40,950
Also wirklich, wenn ich will hier ein zu setzen,
Ich muss vorübergehend die vier kopieren

790
00:37:40,950 --> 00:37:43,030
und dann setzen die man dort.

791
00:37:43,030 --> 00:37:45,500
>> Das ist in Ordnung, das ist richtig,
das ist technisch möglich,

792
00:37:45,500 --> 00:37:48,410
aber erkennen, das ist zusätzliche Arbeit.

793
00:37:48,410 --> 00:37:50,460
Ich habe einfach nicht die Zahl in Stelle zu setzen.

794
00:37:50,460 --> 00:37:53,026
Ich musste zuerst ein bewegen
Nummer, legte es dann an Ort und Stelle,

795
00:37:53,026 --> 00:37:54,650
so verdoppelte ich meine Art von Menge an Arbeit.

796
00:37:54,650 --> 00:37:55,660
So sollte man nicht vergessen.

797
00:37:55,660 --> 00:37:57,120
>> Aber ich bin jetzt mit diesem Element getan.

798
00:37:57,120 --> 00:37:59,056
Jetzt möchte ich die Nummer drei zu greifen.

799
00:37:59,056 --> 00:38:00,430
Wo, natürlich, es gehören?

800
00:38:00,430 --> 00:38:01,480
Zwischen.

801
00:38:01,480 --> 00:38:03,650
Ich kann nicht mehr betrügen
und legte sie einfach da,

802
00:38:03,650 --> 00:38:06,770
da wieder dieser Speicher
ist in physischen Standorten.

803
00:38:06,770 --> 00:38:10,900
Also muss ich die vier kopieren
und legte die drei hier.

804
00:38:10,900 --> 00:38:11,550
Keine große Sache.

805
00:38:11,550 --> 00:38:14,610
Es ist nur ein zusätzlicher Schritt
again-- fühlt sich sehr preiswert.

806
00:38:14,610 --> 00:38:16,445
>> Aber jetzt gehe ich zu den beiden auf.

807
00:38:16,445 --> 00:38:17,820
Die beiden, natürlich, gehört hier.

808
00:38:17,820 --> 00:38:20,990
Nun beginnen Sie zu sehen, wie
die Arbeit anhäufen können.

809
00:38:20,990 --> 00:38:23,520
Nun, was soll ich tun?

810
00:38:23,520 --> 00:38:28,570
Ja, ich habe die vier bewegen,
Ich muss dann die drei zu kopieren,

811
00:38:28,570 --> 00:38:31,200
und jetzt kann ich die beiden ein.

812
00:38:31,200 --> 00:38:34,460
Und der Fang mit diesem
Algorithmus, interessanterweise,

813
00:38:34,460 --> 00:38:41,050
das ist angenommen, wir haben eine extreme
Fall, in dem es acht lassen Sie uns sagen, sieben,

814
00:38:41,050 --> 00:38:45,150
sechs, fünf, vier, drei, zwei, ein.

815
00:38:45,150 --> 00:38:49,450
Dies ist in vielen Zusammenhängen,
das Worst-Case-Szenario,

816
00:38:49,450 --> 00:38:51,570
weil das verflixte Ding
buchstäblich nach hinten ist.

817
00:38:51,570 --> 00:38:53,670
>> Es ist nicht wirklich
beeinflussen Ben-Algorithmus,

818
00:38:53,670 --> 00:38:55,940
weil in Bens Auswahl
Art, er wird zu halten

819
00:38:55,940 --> 00:38:58,359
hin und her durch die Liste.

820
00:38:58,359 --> 00:39:01,150
Und weil er immer auf der Suche
durch die ganze restliche Liste,

821
00:39:01,150 --> 00:39:02,858
es spielt keine Rolle
wobei die Elemente sind.

822
00:39:02,858 --> 00:39:05,630
Aber in diesem Fall mit meinem Einsetzrichtung
approach-- lassen Sie uns dies versuchen.

823
00:39:05,630 --> 00:39:08,616
>> So ein, zwei, drei, vier,
fünf, sechs, sieben, acht.

824
00:39:08,616 --> 00:39:11,630
Eins zwei drei vier,
fünf, sechs, sieben, acht.

825
00:39:11,630 --> 00:39:14,320
Ich werde die acht zu nehmen,
und wo stelle ich es?

826
00:39:14,320 --> 00:39:17,260
Nun, am Anfang meiner Liste,
denn diese neue Liste sortiert ist.

827
00:39:17,260 --> 00:39:18,760
Und ich überqueren Sie es heraus.

828
00:39:18,760 --> 00:39:20,551
>> Wo habe ich die sieben?

829
00:39:20,551 --> 00:39:21,050
Darn es.

830
00:39:21,050 --> 00:39:23,174
Es muss dorthin gehen, so
Ich muss etwas tun, das Kopieren.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
Und jetzt geht die sieben hier.

833
00:39:28,480 --> 00:39:29,860
Nun gehe ich auf die sechs auf.

834
00:39:29,860 --> 00:39:30,980
Jetzt ist es noch mehr Arbeit.

835
00:39:30,980 --> 00:39:32,570
>> Acht hat hier zu gehen.

836
00:39:32,570 --> 00:39:33,920
Seven hat hier zu gehen.

837
00:39:33,920 --> 00:39:35,450
Nun kann die sechs hier.

838
00:39:35,450 --> 00:39:37,950
Jetzt packe ich die fünf.

839
00:39:37,950 --> 00:39:40,560
Nun ist die acht muss gehen
hier sieben hier zu gehen,

840
00:39:40,560 --> 00:39:43,650
sechs hat hier zu gehen, und
jetzt die fünf und wiederholen.

841
00:39:43,650 --> 00:39:46,610
Und ich bin mir ziemlich viel
Bewegen sie sich ständig.

842
00:39:46,610 --> 00:39:52,950
>> So am Ende dieses algorithm-- wir werden
nennen es Einfügung sort-- tatsächlich

843
00:39:52,950 --> 00:39:55,020
hat auch eine Menge Arbeit.

844
00:39:55,020 --> 00:39:56,970
Es ist einfach anders
Art der Arbeit als Bens.

845
00:39:56,970 --> 00:40:00,090
Ben Arbeit hatte mich gehen
hin und her die ganze Zeit,

846
00:40:00,090 --> 00:40:03,510
Auswahl des nächsten kleinsten
Element wieder und wieder.

847
00:40:03,510 --> 00:40:06,660
So war es auch dieses sehr visuelle Art von Arbeit.

848
00:40:06,660 --> 00:40:10,600
>> Dieser andere Algorithmus, der immer noch
correct-- es wird den Job zu bekommen done--

849
00:40:10,600 --> 00:40:12,800
nur ändert sich die Menge an Arbeit.

850
00:40:12,800 --> 00:40:15,420
Es sieht aus wie zunächst du bist
zu speichern, weil Sie gerade sind

851
00:40:15,420 --> 00:40:19,190
wobei jedes Element Umgang
vorne ohne alle zu Fuß

852
00:40:19,190 --> 00:40:20,930
die Art und Weise durch die Liste wie Ben war.

853
00:40:20,930 --> 00:40:25,300
Aber das Problem ist, insbesondere in diesen
verrückt Fällen, in denen es nach hinten ist,

854
00:40:25,300 --> 00:40:27,830
Sie sind nur eine Art von
Verschiebung der harten Arbeit

855
00:40:27,830 --> 00:40:30,360
bis müssen Sie Ihre Fehler zu beheben.

856
00:40:30,360 --> 00:40:33,919
>> Und so, wenn Sie können sich das vorstellen
acht und sieben und sechs und fünf

857
00:40:33,919 --> 00:40:36,710
und später vier und drei und zwei
ihren Weg durch die Liste zu bewegen,

858
00:40:36,710 --> 00:40:39,060
wir haben gerade verändert die
Art der Arbeit, die wir tun.

859
00:40:39,060 --> 00:40:42,340
Anstatt es auf das Tun
Anfang meiner Iteration,

860
00:40:42,340 --> 00:40:45,250
Ich tue es nur bei der
Ende jeder Iteration.

861
00:40:45,250 --> 00:40:50,550
So stellt sich heraus, dass dieser Algorithmus,
Auch allgemein als Insertion Sort,

862
00:40:50,550 --> 00:40:52,190
ist ebenfalls von n in der Größenordnung quadriert.

863
00:40:52,190 --> 00:40:56,480
Es ist eigentlich nicht besser,
nicht gar besser.

864
00:40:56,480 --> 00:41:00,810
>> Allerdings gibt es einen dritten Ansatz
Ich würde uns ermutigen, zu prüfen,

865
00:41:00,810 --> 00:41:02,970
was diese.

866
00:41:02,970 --> 00:41:07,850
Also meine Liste annehmen, der Einfachheit halber
wieder ist vier, eins, drei,

867
00:41:07,850 --> 00:41:11,080
two-- nur vier Zahlen.

868
00:41:11,080 --> 00:41:13,300
Ben hatte eine gute Intuition,
gute menschliche Intuition

869
00:41:13,300 --> 00:41:16,340
vor, durch die feste wir die ganze
Liste eventually-- Insertionsort.

870
00:41:16,340 --> 00:41:18,020
Ich schmeichelte uns zusammen.

871
00:41:18,020 --> 00:41:22,530
Aber lassen Sie uns betrachten die
einfachste Weg, um diese Liste zu beheben.

872
00:41:22,530 --> 00:41:24,110
>> Diese Liste ist nicht sortiert.

873
00:41:24,110 --> 00:41:26,130
Warum?

874
00:41:26,130 --> 00:41:31,920
In Englisch, erklären, warum
Es ist nicht wirklich sortiert.

875
00:41:31,920 --> 00:41:33,400
Was bedeutet es, nicht sortiert werden?

876
00:41:33,400 --> 00:41:34,220
>> STUDENT: Es ist nicht sequentiell.

877
00:41:34,220 --> 00:41:34,990
>> DAVID MALAN: nicht sequentiell.

878
00:41:34,990 --> 00:41:35,822
Gib mir ein Beispiel.

879
00:41:35,822 --> 00:41:37,180
>> STUDENT: Setzen Sie sie um.

880
00:41:37,180 --> 00:41:37,440
>> DAVID MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Geben Sie mir ein konkretes Beispiel.

882
00:41:38,790 --> 00:41:39,832
>> STUDENT: aufsteigende Reihenfolge.

883
00:41:39,832 --> 00:41:41,206
DAVID MALAN: Nicht aufsteigend sortieren.

884
00:41:41,206 --> 00:41:42,100
Genauer gesagt.

885
00:41:42,100 --> 00:41:45,190
Ich weiß nicht, was Sie mit aufsteigend.

886
00:41:45,190 --> 00:41:47,150
Was ist los mit dir?

887
00:41:47,150 --> 00:41:49,930
>> STUDENT: Die kleinste der
Zahlen in dem ersten Raum nicht.

888
00:41:49,930 --> 00:41:51,140
>> DAVID MALAN: Kleinste Nummer
nicht in den ersten Raum.

889
00:41:51,140 --> 00:41:52,120
Sei genauer.

890
00:41:52,120 --> 00:41:55,000
Ich fange an zu fangen.

891
00:41:55,000 --> 00:41:59,470
Wir zählen, aber
was ist hier nicht in Ordnung?

892
00:41:59,470 --> 00:42:00,707
>> STUDENT: Numerische Folge.

893
00:42:00,707 --> 00:42:02,040
DAVID MALAN: Numerische Folge.

894
00:42:02,040 --> 00:42:04,248
Jeder Art von Führung
es hier-- sehr hohem Niveau.

895
00:42:04,248 --> 00:42:07,450
Sag mir einfach, was wörtlich
falsch wie ein fünf-jährige Macht.

896
00:42:07,450 --> 00:42:08,310
>> STUDENT: plus eins.

897
00:42:08,310 --> 00:42:08,750
>> DAVID MALAN: Was ist das?

898
00:42:08,750 --> 00:42:09,610
>> STUDENT: plus eins.

899
00:42:09,610 --> 00:42:11,235
>> DAVID MALAN: Was meinst du plus eins?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Geben Sie mir eine andere fünf Jahre alt.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Was ist los, Mama?

904
00:42:18,330 --> 00:42:19,940
Was ist los, Dad?

905
00:42:19,940 --> 00:42:22,808
Was meinst du damit nicht sortiert ist?

906
00:42:22,808 --> 00:42:24,370
>> STUDENT: Es ist nicht der richtige Ort.

907
00:42:24,370 --> 00:42:25,580
>> DAVID MALAN: Was ist
nicht an der richtigen Stelle?

908
00:42:25,580 --> 00:42:26,174
>> STUDENT: Vier.

909
00:42:26,174 --> 00:42:27,090
DAVID MALAN: OK, gut.

910
00:42:27,090 --> 00:42:29,110
So vier ist nicht, wo es sein sollte.

911
00:42:29,110 --> 00:42:30,590
Insbesondere ist dies der richtige?

912
00:42:30,590 --> 00:42:33,000
Vier und eine, die erste
zwei Zahlen, die ich zu sehen.

913
00:42:33,000 --> 00:42:34,930
Ist das richtig?

914
00:42:34,930 --> 00:42:36,427
Nein, sie sind nicht in Ordnung, nicht wahr?

915
00:42:36,427 --> 00:42:38,135
In der Tat, jetzt denken,
zu einem Computer, zu.

916
00:42:38,135 --> 00:42:40,824
Es kann nur auf vielleicht aussehen,
vielleicht zwei Dinge auf once--

917
00:42:40,824 --> 00:42:43,240
und eigentlich nur eine Sache,
zu einer Zeit, aber es kann zumindest

918
00:42:43,240 --> 00:42:45,790
Blick auf eine Sache, dann die
nächste, was sich direkt daneben.

919
00:42:45,790 --> 00:42:47,380
>> So sind diese um?

920
00:42:47,380 --> 00:42:48,032
Natürlich nicht.

921
00:42:48,032 --> 00:42:48,740
So wissen Sie was?

922
00:42:48,740 --> 00:42:51,020
Warum nehmen wir Baby nicht
Schritte, um dieses Problem zu beheben

923
00:42:51,020 --> 00:42:53,410
Anstelle dieser Phantasie zu tun
Algorithmen wie Ben, wo

924
00:42:53,410 --> 00:42:56,440
Er ist eine Art der Befestigung durch
Schleife durch die Liste

925
00:42:56,440 --> 00:42:59,670
anstatt das zu tun, was ich tat, wo
Ich habe gerade Art es von festen, wie wir gehen?

926
00:42:59,670 --> 00:43:03,650
Lassen Sie uns einfach buchstäblich die brechen
Begriff der order-- numerischer Reihenfolge,

927
00:43:03,650 --> 00:43:06,990
nennen Sie es, was Sie want--
in diese paarweise Vergleiche.

928
00:43:06,990 --> 00:43:07,590
>> Vier und Eins.

929
00:43:07,590 --> 00:43:09,970
Ist das die richtige Reihenfolge?

930
00:43:09,970 --> 00:43:11,310
Also lassen Sie uns das in Ordnung bringen.

931
00:43:11,310 --> 00:43:14,700
Ein und vier, und dann
wir werden nur das kopieren.

932
00:43:14,700 --> 00:43:15,560
In Ordnung, gut.

933
00:43:15,560 --> 00:43:17,022
Ich reparierte eins und vier.

934
00:43:17,022 --> 00:43:18,320
Drei und zwei?

935
00:43:18,320 --> 00:43:18,820
Nein.

936
00:43:18,820 --> 00:43:21,690
Lassen Sie meine Worte meine Finger passen.

937
00:43:21,690 --> 00:43:23,695
Vier und drei?

938
00:43:23,695 --> 00:43:27,930
>> Es ist nicht in Ordnung, so werde ich
zu tun, eins, drei, vier, zwei.

939
00:43:27,930 --> 00:43:28,680
OK gut.

940
00:43:28,680 --> 00:43:32,310
Jetzt vier und zwei?

941
00:43:32,310 --> 00:43:33,370
Wir müssen dieses Problem zu beheben, auch.

942
00:43:33,370 --> 00:43:36,700
So eins, drei, zwei, vier.

943
00:43:36,700 --> 00:43:39,820
So ist es sortiert?

944
00:43:39,820 --> 00:43:43,170
Nein, aber ist es näher an sortiert?

945
00:43:43,170 --> 00:43:48,930
>> Es ist, weil wir dieses Problem behoben
Fehler, Fest wir diesen Fehler,

946
00:43:48,930 --> 00:43:50,370
und wir festgelegt, diesen Fehler.

947
00:43:50,370 --> 00:43:52,420
So fixiert wir wohl drei Fehler.

948
00:43:52,420 --> 00:43:58,100
immer noch nicht wirklich aussehen sortiert, aber
es ist objektiv näher an sortierten

949
00:43:58,100 --> 00:44:00,080
weil wir einige dieser Fehler behoben.

950
00:44:00,080 --> 00:44:02,047
>> Nun, was mache ich als nächstes?

951
00:44:02,047 --> 00:44:03,630
Ich erreichte Art das Ende der Liste.

952
00:44:03,630 --> 00:44:05,680
Ich schien behoben haben
alle Fehler, aber nein.

953
00:44:05,680 --> 00:44:08,510
Da in diesem Fall einige Zahlen
könnte sprudelte näher

954
00:44:08,510 --> 00:44:10,410
auf andere Zahlen, die
aus der Ordnung sind nach wie vor.

955
00:44:10,410 --> 00:44:12,951
So wollen wir es wieder tun, und ich werde
nur tun es diesmal an ihrem Platz.

956
00:44:12,951 --> 00:44:14,170
Ein und drei?

957
00:44:14,170 --> 00:44:14,720
Das ist gut.

958
00:44:14,720 --> 00:44:16,070
Drei und zwei?

959
00:44:16,070 --> 00:44:17,560
Natürlich nicht, also lassen Sie uns das ändern.

960
00:44:17,560 --> 00:44:19,160
So zwei, drei.

961
00:44:19,160 --> 00:44:21,340
Drei und vier?

962
00:44:21,340 --> 00:44:24,370
Und nun lassen Sie uns einfach sein
hier besonders pedantisch.

963
00:44:24,370 --> 00:44:26,350
Ist es sortiert?

964
00:44:26,350 --> 00:44:29,280
Ihr Menschen wissen, dass es sortiert.

965
00:44:29,280 --> 00:44:30,400
>> Ich sollte noch einmal versuchen.

966
00:44:30,400 --> 00:44:31,900
So Olivia schlägt ich versuche es erneut.

967
00:44:31,900 --> 00:44:32,530
Warum?

968
00:44:32,530 --> 00:44:35,810
Da ein Computer nicht
der Luxus unserer menschlichen Augen

969
00:44:35,810 --> 00:44:38,080
von nur einem Blick back-- OK, ich bin fertig.

970
00:44:38,080 --> 00:44:41,610
Wie funktioniert der Computer bestimmen
dass die Liste wird nun sortiert?

971
00:44:41,610 --> 00:44:44,590
Mechanisch.

972
00:44:44,590 --> 00:44:47,650
>> Ich sollte gehen durch
noch einmal, und nur wenn I

973
00:44:47,650 --> 00:44:51,190
nicht machen / zu finden keine Fehler kann ich
dann wie auf dem Computer schließen, yep,

974
00:44:51,190 --> 00:44:51,980
wir sind gut zu gehen.

975
00:44:51,980 --> 00:44:54,850
So eins und zwei, zwei und
drei, drei und vier.

976
00:44:54,850 --> 00:44:58,030
Jetzt kann ich definitiv sagen, dass dies
sortiert, weil ich keine Änderungen vorgenommen.

977
00:44:58,030 --> 00:45:01,940
Nun wäre es ein Fehler sein, und nur
dumm, wenn ich, der Computer,

978
00:45:01,940 --> 00:45:05,640
die gleichen Fragen wieder
erwarten verschiedene Antworten.

979
00:45:05,640 --> 00:45:07,110
Sollte nicht passieren.

980
00:45:07,110 --> 00:45:08,600
>> Und jetzt ist die Liste sortiert.

981
00:45:08,600 --> 00:45:12,630
Leider Laufzeit
Dieser Algorithmus ist auch n im Quadrat.

982
00:45:12,630 --> 00:45:13,130
Warum?

983
00:45:13,130 --> 00:45:19,520
Denn Sie haben n Zahlen, und in der
schlimmsten Fall müssen Sie n Zahlen bewegen

984
00:45:19,520 --> 00:45:23,637
n-mal, weil Sie müssen weitermachen
zurück zu überprüfen und möglicherweise zu beheben

985
00:45:23,637 --> 00:45:24,220
diese Zahlen.

986
00:45:24,220 --> 00:45:26,280
Und wir können eine mehr tun
formalen Analyse, auch.

987
00:45:26,280 --> 00:45:29,530
>> So ist das alles zu sagen, wir genommen haben
drei verschiedene Ansätze, ein

988
00:45:29,530 --> 00:45:32,210
von ihnen sofort intuitiv
von der Fledermaus von Ben

989
00:45:32,210 --> 00:45:35,170
Zu meiner vorgeschlagenen Einfügung
Art wie diese

990
00:45:35,170 --> 00:45:38,540
wo man Art von den Augen verlieren
der Wald für die anfänglich Bäume.

991
00:45:38,540 --> 00:45:41,760
Aber dann, wenn Sie einen Schritt zurück,
voila, haben wir die Sortier Begriff fixiert.

992
00:45:41,760 --> 00:45:43,824
Das ist also, es wagen, sagen,
ein niedrigeres Niveau vielleicht

993
00:45:43,824 --> 00:45:45,740
als einige dieser anderen
Algorithmen, aber lassen Sie uns

994
00:45:45,740 --> 00:45:48,550
sehen, ob wir nicht visualisieren
diese haft dafür.

995
00:45:48,550 --> 00:45:51,450
>> Also das ist ein paar nette
Software, dass jemand

996
00:45:51,450 --> 00:45:56,110
Verwendung schrieb bunten Bars, das ist,
gehen die folgenden für uns zu tun.

997
00:45:56,110 --> 00:45:57,736
Jeder dieser Stäbe für eine Zahl.

998
00:45:57,736 --> 00:46:00,026
Taller der Balken, desto größer
die Anzahl, die kleiner ist die Bar,

999
00:46:00,026 --> 00:46:00,990
Je kleiner die Zahl.

1000
00:46:00,990 --> 00:46:05,880
Also ideal wollen wir eine schöne Pyramide
wo es beginnt klein und wird groß,

1001
00:46:05,880 --> 00:46:08,330
und das würde bedeuten, dass
Diese Stäbe werden sortiert.

1002
00:46:08,330 --> 00:46:11,200
Also werde ich voran gehen und wählen,
beispielsweise Ben-Algorithmus

1003
00:46:11,200 --> 00:46:13,990
first-- Auswahl sortieren.

1004
00:46:13,990 --> 00:46:16,220
>> Und bemerken, was es tut.

1005
00:46:16,220 --> 00:46:18,670
Die Art, wie sie sich entschieden haben zu
visualisieren diesen Algorithmus

1006
00:46:18,670 --> 00:46:22,090
ist, dass, wie ich gerade war
zu Fuß durch meine Liste,

1007
00:46:22,090 --> 00:46:24,710
Dieses Programm ist zu Fuß
durch seine Liste von Zahlen,

1008
00:46:24,710 --> 00:46:28,160
in rosa hervorgehoben jeder
Zahl, die es betrachten.

1009
00:46:28,160 --> 00:46:32,360
Und wie sieht es jetzt geschehen?

1010
00:46:32,360 --> 00:46:35,154
>> Die kleinste Zahl, die
I oder Ben plötzlich

1011
00:46:35,154 --> 00:46:36,820
wird an den Anfang der Liste verschoben.

1012
00:46:36,820 --> 00:46:40,037
Und merkte sie evict
die Zahl, die es gab,

1013
00:46:40,037 --> 00:46:41,120
und das ist völlig in Ordnung.

1014
00:46:41,120 --> 00:46:42,600
Ich habe nicht in diesem Maß an Detail.

1015
00:46:42,600 --> 00:46:44,308
Aber wir müssen zu setzen
diese Zahl irgendwo,

1016
00:46:44,308 --> 00:46:47,775
wir zogen es so nur auf die
offene Stelle, die erstellt wurde.

1017
00:46:47,775 --> 00:46:49,900
Also werde ich dies zu beschleunigen
, denn sonst ist es

1018
00:46:49,900 --> 00:46:51,871
schnell wird sehr mühsam.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animation speed-- dort gehen wir.

1021
00:46:58,600 --> 00:47:01,850
So, jetzt gleiche Prinzip
Ich war die Anwendung, aber Sie

1022
00:47:01,850 --> 00:47:06,540
kann beginnen, den Algorithmus zu fühlen, wenn Sie
wird, oder es ein wenig klarer zu sehen.

1023
00:47:06,540 --> 00:47:13,190
Und dieser Algorithmus hat den Effekt,
das nächste kleinste Element der Auswahl,

1024
00:47:13,190 --> 00:47:16,422
so dass Sie gehen, um zu starten
sehen sie auf der linken Rampe.

1025
00:47:16,422 --> 00:47:19,130
Und bei jeder Iteration, wie ich
vorgeschlagen, es hat ein bisschen weniger Arbeit.

1026
00:47:19,130 --> 00:47:21,921
Es hat nicht den ganzen Weg zu gehen
zurück zum linken Ende der Liste,

1027
00:47:21,921 --> 00:47:23,900
da es bereits
kennt solche sortiert werden.

1028
00:47:23,900 --> 00:47:28,129
So fühlt es sich ein bisschen wie es ist
beschleunigt, obwohl jeder Schritt

1029
00:47:28,129 --> 00:47:29,420
die gleiche Menge an Zeit.

1030
00:47:29,420 --> 00:47:31,600
Es gibt nur noch wenige Schritte.

1031
00:47:31,600 --> 00:47:35,240
Und jetzt können Sie Art von Gefühl, die
Algorithmus Reinigung das Ende davon auf,

1032
00:47:35,240 --> 00:47:37,040
und in der Tat jetzt ist es sortiert.

1033
00:47:37,040 --> 00:47:41,620
>> So Insertionsort ist alles getan.

1034
00:47:41,620 --> 00:47:43,600
Ich muss das Array neu zu randomisieren.

1035
00:47:43,600 --> 00:47:45,940
Und bemerken kann ich nur
halten Randomisierung es,

1036
00:47:45,940 --> 00:47:50,630
und wir bekommen eine Annäherung an
der gleiche Ansatz, Insertionsort.

1037
00:47:50,630 --> 00:47:55,050
Lassen Sie es mich langsam hier unten.

1038
00:47:55,050 --> 00:47:56,915
Lassen Sie uns beginnen, dass über.

1039
00:47:56,915 --> 00:47:57,414
Halt.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> Lassen Sie uns vier überspringen.

1042
00:48:02,410 --> 00:48:03,200
Da gehen wir.

1043
00:48:03,200 --> 00:48:04,190
Randomize sie Array.

1044
00:48:04,190 --> 00:48:05,555
Und hier go-- wir Insertionsort.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Spielen.

1047
00:48:12,800 --> 00:48:17,280
Beachten Sie, dass es mit jedem zu tun hat
Element es sofort begegnet,

1048
00:48:17,280 --> 00:48:20,282
aber wenn es gehört in
der falsche Ort Bekanntmachung

1049
00:48:20,282 --> 00:48:21,740
all der Arbeit, die zu geschehen hat.

1050
00:48:21,740 --> 00:48:24,700
Wir müssen weiter mehr Verschiebung
und weitere Elemente, um Platz

1051
00:48:24,700 --> 00:48:27,340
für den einen wollen wir an Ort und Stelle zu bringen.

1052
00:48:27,340 --> 00:48:30,740
>> So konzentrieren wir uns auf die
linken Ende der Liste nur.

1053
00:48:30,740 --> 00:48:34,460
Beachten wir haben nicht einmal at-- wir sahen
nicht in rosa etwas hervorgehoben

1054
00:48:34,460 --> 00:48:35,610
auf der rechten Seite.

1055
00:48:35,610 --> 00:48:38,180
Wir haben es nur mit
die Probleme, wie wir gehen,

1056
00:48:38,180 --> 00:48:40,430
aber wir schaffen eine Menge
noch für uns arbeiten.

1057
00:48:40,430 --> 00:48:44,410
Und so, wenn wir dies beschleunigen
jetzt gehen bis zur Fertigstellung,

1058
00:48:44,410 --> 00:48:46,210
es hat ein anderes Gefühl, es in der Tat.

1059
00:48:46,210 --> 00:48:50,150
Es ist nur auf der linken Ende konzentriert, aber
dabei ein wenig mehr Arbeit als needed--

1060
00:48:50,150 --> 00:48:53,230
Art der Glättung Dinge
über die Dinge Festsetzung,

1061
00:48:53,230 --> 00:48:58,350
aber den Umgang schließlich mit
jedes Element einzeln nacheinander

1062
00:48:58,350 --> 00:49:07,740
bis wir gut zu the-- bekommen, wir
alle wissen, wie das enden wird,

1063
00:49:07,740 --> 00:49:09,700
so ist es ein wenig berauschend vielleicht.

1064
00:49:09,700 --> 00:49:12,830
>> Aber die Liste in der end--
spoiler-- wird sortiert werden.

1065
00:49:12,830 --> 00:49:15,300
Lassen Sie uns also auf einen letzten Blick.

1066
00:49:15,300 --> 00:49:16,840
Wir können nicht nur jetzt überspringen.

1067
00:49:16,840 --> 00:49:18,000
Wir sind fast da.

1068
00:49:18,000 --> 00:49:19,980
Zwei zu gehen, ein zu gehen.

1069
00:49:19,980 --> 00:49:22,680
Und voila.

1070
00:49:22,680 --> 00:49:23,450
Ausgezeichnet.

1071
00:49:23,450 --> 00:49:27,220
>> So, jetzt lassen Sie uns eine letzte tun,
Re-Randomisierung mit Bubble-Sort.

1072
00:49:27,220 --> 00:49:31,690
Und hier bemerken, vor allem, wenn ich es langsam
dies ist nach unten, halten Sie durch Swooping.

1073
00:49:31,690 --> 00:49:36,830
Beachten Sie aber, es macht nur paarweise
comparisons-- Art lokaler Lösungen.

1074
00:49:36,830 --> 00:49:39,050
Aber sobald wir bekommen
das Ende der Liste in rosa,

1075
00:49:39,050 --> 00:49:40,690
was los ist wieder geschehen zu lassen?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Ja, es gehen zu müssen,
zu beginnen, weil es nur

1078
00:49:46,830 --> 00:49:49,870
fest paarweise Fehler.

1079
00:49:49,870 --> 00:49:53,120
Und das könnte noch andere offenbart haben.

1080
00:49:53,120 --> 00:49:58,950
Und so, wenn Sie diese nach oben zu beschleunigen, werden Sie
sehen, dass, so wie der Name schon sagt,

1081
00:49:58,950 --> 00:50:01,870
der kleinere elements-- oder vielmehr
die größeren elements-- beginnen

1082
00:50:01,870 --> 00:50:03,740
zu sprudeln an die Spitze, wenn man so will.

1083
00:50:03,740 --> 00:50:07,380
Und die kleineren Elemente
nach links unten zu sprudeln beginnen.

1084
00:50:07,380 --> 00:50:10,780
Und in der Tat ist diese Art von
der visuelle Effekt auch.

1085
00:50:10,780 --> 00:50:17,150
Und so wird diese am Ende Veredelung
in sehr ähnlicher Weise zu.

1086
00:50:17,150 --> 00:50:19,160
>> Wir müssen nicht wohnen
an diesem ein.

1087
00:50:19,160 --> 00:50:21,010
Lassen Sie mich das jetzt öffnen, auch.

1088
00:50:21,010 --> 00:50:24,040
Es gibt ein paar andere Sortieralgorithmen
in der Welt, von denen einige

1089
00:50:24,040 --> 00:50:25,580
werden hier erfasst.

1090
00:50:25,580 --> 00:50:29,960
Und vor allem für Lernende, die nicht
notwendigerweise visuell oder mathematisch,

1091
00:50:29,960 --> 00:50:31,930
wie wir schon haben, können wir
auch dies tun hör-

1092
00:50:31,930 --> 00:50:34,210
wenn wir assoziieren einen Ton mit diesem.

1093
00:50:34,210 --> 00:50:36,990
Und nur zum Spaß, hier ist ein
paar verschiedene Algorithmen,

1094
00:50:36,990 --> 00:50:40,950
und einer von ihnen insbesondere du bist
gehen zu bemerken, wird als "merge sort."

1095
00:50:40,950 --> 00:50:43,250
>> Es ist eigentlich ein grundlegend
besseren Algorithmus,

1096
00:50:43,250 --> 00:50:45,860
solche, die Art verschmelzen, einer der
die, die Sie über zu sehen sind,

1097
00:50:45,860 --> 00:50:49,170
Quadrat ist nicht Ordnung von n.

1098
00:50:49,170 --> 00:50:57,280
Es ist in der Größenordnung von n-mal log von
n, was tatsächlich kleiner ist, und somit

1099
00:50:57,280 --> 00:50:58,940
schneller als die anderen drei.

1100
00:50:58,940 --> 00:51:00,670
Und es gibt ein paar andere
albern diejenigen, die wir sehen werden.

1101
00:51:00,670 --> 00:51:01,933
>> Also hier gehen wir mit einem gewissen Sound.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Dies ist Insertionsort, so wieder
es handelt nur mit den Elementen

1104
00:51:10,490 --> 00:51:13,420
wie sie kommen.

1105
00:51:13,420 --> 00:51:17,180
Dies ist Bubble Sort, so dass es
sie paarweise zu einem Zeitpunkt betrachten.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
Und wieder die größten Elemente
sprudeln ganz nach oben.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Als nächstes Auswahl sortieren.

1110
00:51:41,710 --> 00:51:45,420
Dies ist Ben-Algorithmus, wo
er wieder die Auswahl iterativ

1111
00:51:45,420 --> 00:51:46,843
der nächste kleinste Element.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
Und wieder, jetzt können Sie wirklich, dass hören
es beschleunigt, sondern nur so weit in

1114
00:51:53,900 --> 00:51:58,230
wie es tut immer weniger
bei jeder Iteration arbeiten.

1115
00:51:58,230 --> 00:52:04,170
Dies ist die schnellere, fusionieren zu sortieren,
die Cluster von Zahlen ist das Sortieren

1116
00:52:04,170 --> 00:52:05,971
zusammen und kombiniert sie dann.

1117
00:52:05,971 --> 00:52:07,720
So look-- die linke
die Hälfte ist bereits sortiert.

1118
00:52:07,720 --> 00:52:14,165
>> Jetzt wird es die Sortierung der rechten Hälfte, und
Jetzt geht es ihnen zu einem zu kombinieren.

1119
00:52:14,165 --> 00:52:19,160
Das ist etwas, genannt "Gnome Art."

1120
00:52:19,160 --> 00:52:23,460
Und Sie können Art sehen, dass
es geht hin und her,

1121
00:52:23,460 --> 00:52:27,950
Festsetzung der Arbeit hier ein wenig und
dort, bevor er geht, um neue Arbeit.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
Und das ist es.

1124
00:52:33,692 --> 00:52:36,400
Es ist eine andere Art, das ist
wirklich nur für akademische Zwecke,

1125
00:52:36,400 --> 00:52:40,980
"Dumme Art" genannt, was nimmt
Ihre Daten, sortiert sie nach dem Zufall,

1126
00:52:40,980 --> 00:52:43,350
und prüft dann, ob es sortiert wird.

1127
00:52:43,350 --> 00:52:47,880
Und wenn es nicht ist, ist es neu sortiert sie
zufällig, überprüft, ob es sortiert,

1128
00:52:47,880 --> 00:52:49,440
und wenn nicht, wiederholt.

1129
00:52:49,440 --> 00:52:52,660
Und in der Theorie, probabilistically
Dies wird vollenden,

1130
00:52:52,660 --> 00:52:54,140
aber nach einer ziemlich viel Zeit.

1131
00:52:54,140 --> 00:52:56,930
Es ist nicht die
effiziente Algorithmen.

1132
00:52:56,930 --> 00:53:02,550
Also Fragen auf diejenigen
insbesondere Algorithmen oder irgendetwas

1133
00:53:02,550 --> 00:53:04,720
auch da zu tun?

1134
00:53:04,720 --> 00:53:09,430
>> Nun, lassen Sie uns jetzt necken auseinander, was alle
diese Zeilen sind, dass ich habe Zeichnung

1135
00:53:09,430 --> 00:53:15,090
und was ich nehme an, dass Sie den Computer
kann unter der Haube zu tun.

1136
00:53:15,090 --> 00:53:18,650
Ich würde, dass all diese Zahlen argumentieren
Ich halte drawing-- die sie brauchen

1137
00:53:18,650 --> 00:53:21,330
irgendwo im Speicher gespeichert.

1138
00:53:21,330 --> 00:53:24,130
Wir werden jetzt die Befreiung von diesem Kerl bekommen, auch.

1139
00:53:24,130 --> 00:53:30,110
>> So ein Stück Erinnerung in ein
computer-- so RAM DIMM

1140
00:53:30,110 --> 00:53:35,480
was wir suchten nach gestern, Dual
Inline Memory module-- sieht wie folgt aus.

1141
00:53:35,480 --> 00:53:39,370
Und jeder dieser kleinen schwarzen Chips
typischerweise eine Anzahl von Bytes.

1142
00:53:39,370 --> 00:53:44,380
Und dann sind die Gold-Pins wie die
Drähte, die es an den Computer anschließen,

1143
00:53:44,380 --> 00:53:47,521
und die grüne Siliziumplatte ist nur
was hält alle zusammen alles.

1144
00:53:47,521 --> 00:53:48,770
Also, was bedeutet das eigentlich?

1145
00:53:48,770 --> 00:53:53,180
Wenn ich irgendwie das gleiche Bild zu zeichnen,
Lassen Sie uns der Einfachheit halber annehmen,

1146
00:53:53,180 --> 00:53:55,280
dass dieses DIMM, Dual
Inline-Speichermodul,

1147
00:53:55,280 --> 00:54:00,530
ist ein Gigabyte RAM, ein Gigabyte
Speicher, der wie viele Bytes insgesamt ist?

1148
00:54:00,530 --> 00:54:02,100
Ein Gigabyte ist, wie viele Bytes?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Mehr als das.

1151
00:54:06,030 --> 00:54:09,960
1124 ist Kilo, 1000.

1152
00:54:09,960 --> 00:54:11,730
Mega ist Millionen.

1153
00:54:11,730 --> 00:54:14,570
Giga ist eine Milliarde.

1154
00:54:14,570 --> 00:54:15,070
>> Liege ich?

1155
00:54:15,070 --> 00:54:16,670
Können wir sogar das Etikett lesen?

1156
00:54:16,670 --> 00:54:19,920
Dies ist eigentlich 128
Gigabyte, es ist so mehr.

1157
00:54:19,920 --> 00:54:22,130
Aber wir werden dies so tun,
ist nur ein Gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Das heißt also, es gibt eine Milliarde
Byte Speicher zur Verfügung zu mir

1159
00:54:25,640 --> 00:54:29,770
oder 8 Milliarden Bits, aber wir gehen
in Bezug auf die Bytes jetzt zu reden,

1160
00:54:29,770 --> 00:54:30,750
voran.

1161
00:54:30,750 --> 00:54:36,330
>> Also, was das bedeutet, ist dies
ein Byte, ist dies ein weiteres Byte,

1162
00:54:36,330 --> 00:54:38,680
dies ist ein weiteres Byte,
und wenn wir wirklich wollten

1163
00:54:38,680 --> 00:54:43,280
um genau zu sein müssen wir würden
ziehen eine Milliarde kleinen Plätzen.

1164
00:54:43,280 --> 00:54:44,320
Aber was bedeutet das?

1165
00:54:44,320 --> 00:54:46,420
Nun, lassen Sie mich nur vergrößern
in auf diesem Bild.

1166
00:54:46,420 --> 00:54:50,900
Wenn ich etwas haben, die aussieht
nun wie folgt, ist, dass vier Bytes.

1167
00:54:50,900 --> 00:54:53,710
>> Und so konnte ich hier vier Zahlen setzen.

1168
00:54:53,710 --> 00:54:54,990
Eins zwei drei vier.

1169
00:54:54,990 --> 00:55:00,170
Oder ich könnte vier Buchstaben oder Symbole setzen.

1170
00:55:00,170 --> 00:55:02,620
"Hallo!" gehen könnte genau dort,
da jeder der Buchstaben,

1171
00:55:02,620 --> 00:55:04,370
wir früher diskutiert,
könnte vertreten

1172
00:55:04,370 --> 00:55:06,650
mit acht Bits oder ASCII oder ein Byte.

1173
00:55:06,650 --> 00:55:09,370
Also mit anderen Worten, können Sie
setzen 8 Milliarden Dinge im Inneren

1174
00:55:09,370 --> 00:55:11,137
dieses einen Stick von Speicher.

1175
00:55:11,137 --> 00:55:14,345
Nun, was bedeutet es, Sachen zu setzen zurück
im Speicher zu sichern, wie dies zu unterstützen?

1176
00:55:14,345 --> 00:55:17,330
Dies ist, was ein Programmierer
ein "Array". nennen würde

1177
00:55:17,330 --> 00:55:21,250
In einem Computerprogramm, denken Sie nicht,
über die zugrunde liegenden Hardware, per se.

1178
00:55:21,250 --> 00:55:24,427
Sie denken an sich selbst genauso wie mit
Zugriff auf insgesamt Milliarde Byte,

1179
00:55:24,427 --> 00:55:26,010
und Sie können alles wollen Sie mit ihm.

1180
00:55:26,010 --> 00:55:27,880
Aber der Einfachheit halber
es in der Regel sinnvoll

1181
00:55:27,880 --> 00:55:31,202
Ihr Gedächtnis richtig zu halten
nebeneinander wie folgt.

1182
00:55:31,202 --> 00:55:33,660
Also, wenn ich Zoom auf this--
weil wir sicher nicht gehen

1183
00:55:33,660 --> 00:55:39,310
eine Milliarde wenig squares-- zu ziehen
nehmen wir an, dass dieses Board repräsentiert

1184
00:55:39,310 --> 00:55:40,610
dass Stick von Speicher jetzt.

1185
00:55:40,610 --> 00:55:43,800
Und ich werde genauso viele ziehen, wie meine
Marker landet mich hier zu geben.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Deshalb haben wir jetzt einen Stock
der Speicher auf der Platine

1188
00:55:52,300 --> 00:55:56,400
das hat ein, zwei, drei, vier, fünf,
sechs, eins, zwei, drei, vier, fünf, sechs,

1189
00:55:56,400 --> 00:56:01,130
seven-- so 42 Bytes
Speicher auf dem Bildschirm insgesamt.

1190
00:56:01,130 --> 00:56:01,630
Vielen Dank.

1191
00:56:01,630 --> 00:56:02,838
Ja, habe meine Arithmetik richtig.

1192
00:56:02,838 --> 00:56:05,120
So 42 Byte Speicher hier.

1193
00:56:05,120 --> 00:56:06,660
Also, was bedeutet das eigentlich?

1194
00:56:06,660 --> 00:56:09,830
Nun, ein Computer-Programmierer
würde tatsächlich im Allgemeinen

1195
00:56:09,830 --> 00:56:12,450
denken Sie an dieses Speichers als adressierbar.

1196
00:56:12,450 --> 00:56:16,630
Mit anderen Worten, jeder von diesen
Stellen im Speicher, in Hardware,

1197
00:56:16,630 --> 00:56:18,030
hat eine eindeutige Adresse.

1198
00:56:18,030 --> 00:56:22,020
>> Es ist nicht so komplex wie ein Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Stattdessen ist es nur eine Zahl.

1200
00:56:23,830 --> 00:56:27,930
Dies ist Byte-Zahl Null, das ist
ein, ist dies zwei dieser drei ist,

1201
00:56:27,930 --> 00:56:30,327
und dies ist 41.

1202
00:56:30,327 --> 00:56:30,910
Warte eine Minute.

1203
00:56:30,910 --> 00:56:32,510
Ich dachte, ich sagte 42 vor einem Augenblick.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Ich begann bei Null zu zählen,
so das ist eigentlich richtig.

1206
00:56:37,772 --> 00:56:40,980
wir müssen es jetzt eigentlich gar nicht ziehen
als Gitter, und wenn Sie es als ein Gitter ziehen

1207
00:56:40,980 --> 00:56:43,520
Ich denke, die Dinge tatsächlich
bekommen ein wenig irreführend.

1208
00:56:43,520 --> 00:56:46,650
Was würde ein Programmierer,
in seinem eigenen Geist,

1209
00:56:46,650 --> 00:56:50,310
im Allgemeinen denken Sie an dieses
Speicher wie ist wie ein Band,

1210
00:56:50,310 --> 00:56:53,340
wie einem Stück Abdeckband
das geht einfach weiter und weiter für immer

1211
00:56:53,340 --> 00:56:54,980
oder bis Sie aus dem Speicher ausgeführt werden.

1212
00:56:54,980 --> 00:56:59,200
So ein häufiger Weg zu zeichnen
und man denke nur an Speicher

1213
00:56:59,200 --> 00:57:03,710
wäre, dass dies Byte null, eins,
zwei, drei, und dann Punkt, Punkt, Punkt.

1214
00:57:03,710 --> 00:57:07,650
Und Sie haben 42 solcher Bytes insgesamt, auch
obwohl es physisch könnte in der Tat

1215
00:57:07,650 --> 00:57:09,480
etwas mehr so ​​sein.

1216
00:57:09,480 --> 00:57:12,850
>> Also, wenn Sie jetzt denken Sie an Ihre
Speicher als diese, so wie ein Band,

1217
00:57:12,850 --> 00:57:17,640
das ist, was ein Programmierer wieder
würde ein Array von Speicher nennen.

1218
00:57:17,640 --> 00:57:20,660
Und wenn Sie möchten, um tatsächlich speichern
etwas in einem Speicher des Computers,

1219
00:57:20,660 --> 00:57:23,290
Sie speichern Dinge im Allgemeinen tun
Rücken an Rücken an Rücken an Rücken.

1220
00:57:23,290 --> 00:57:25,010
So reden wir seit über Zahlen.

1221
00:57:25,010 --> 00:57:30,880
Und wenn ich wollte, um Probleme zu lösen
wie vier, eins, drei, zwei,

1222
00:57:30,880 --> 00:57:33,820
obwohl ich gerade Zeichnung
nur die Nummern vier, eins, drei,

1223
00:57:33,820 --> 00:57:39,490
zwei auf dem Board, würde der Computer
wirklich haben diese Einrichtung im Speicher.

1224
00:57:39,490 --> 00:57:43,347
>> Und was wäre neben der
zwei in dem Speicher des Computers?

1225
00:57:43,347 --> 00:57:44,680
Nun, es gibt keine Antwort auf diese Frage.

1226
00:57:44,680 --> 00:57:45,770
Wir wissen es nicht wirklich.

1227
00:57:45,770 --> 00:57:48,200
Und so lange, wie die
Computer braucht es nicht,

1228
00:57:48,200 --> 00:57:51,440
es muss nicht, was als nächstes
auf die Zahlen macht es Sorge um.

1229
00:57:51,440 --> 00:57:55,130
Und wenn ich vorhin gesagt, dass ein Computer
kann nur zu einer Zeit an einer Adresse sucht,

1230
00:57:55,130 --> 00:57:56,170
Dies ist eine Art, warum.

1231
00:57:56,170 --> 00:57:59,490
>> Nicht anders als ein Rekord
Spieler und ein Lesekopf

1232
00:57:59,490 --> 00:58:03,030
in der Lage zu schauen nur auf einem bestimmten
Nut in einem physischen Satz der alten Schule

1233
00:58:03,030 --> 00:58:06,500
zu einer Zeit, ähnlich
Ein Computer kann dank

1234
00:58:06,500 --> 00:58:09,810
seine CPU und ihre
Intel-Befehlssatz,

1235
00:58:09,810 --> 00:58:12,480
unter dessen Anweisung
wird aus dem Speicher gelesen

1236
00:58:12,480 --> 00:58:15,590
oder speichern eine zu memory--
Computer können nur schauen

1237
00:58:15,590 --> 00:58:19,210
an einer Stelle in einem Zeit--
manchmal eine Kombination von ihnen,

1238
00:58:19,210 --> 00:58:21,770
aber wirklich nur ein Ort zu einer Zeit.

1239
00:58:21,770 --> 00:58:24,770
Also, wenn wir taten,
Diese verschiedenen Algorithmen,

1240
00:58:24,770 --> 00:58:28,110
Ich schreibe nicht nur in ein
vacuum-- vier, eins, drei, zwei.

1241
00:58:28,110 --> 00:58:30,849
Diese Zahlen tatsächlich gehören
irgendwo physisch im Speicher.

1242
00:58:30,849 --> 00:58:32,890
So gibt es winzig kleine
Transistoren oder irgendeine Art

1243
00:58:32,890 --> 00:58:35,840
Elektronik unterhalb der
Kapuze Speicherung dieser Werte.

1244
00:58:35,840 --> 00:58:40,460
>> Und insgesamt, wie viele Bits
jetzt beteiligt, um nur klar sein?

1245
00:58:40,460 --> 00:58:45,580
Das ist also vier Bytes oder
es ist jetzt 32 Bits insgesamt.

1246
00:58:45,580 --> 00:58:49,280
So gibt es tatsächlich 32 Nullen und
diejenigen, diese vier Dinge zu komponieren.

1247
00:58:49,280 --> 00:58:52,070
Es gibt noch mehr hier, aber
wieder kümmern wir uns nicht darüber.

1248
00:58:52,070 --> 00:58:55,120
>> So, jetzt lassen Sie uns eine andere fragen
Frage mit Speicher,

1249
00:58:55,120 --> 00:58:57,519
denn das am Ende
des Tages ist in Abweichung.

1250
00:58:57,519 --> 00:59:00,310
Egal, was wir tun könnten mit
der Computer am Ende des Tages

1251
00:59:00,310 --> 00:59:02,560
die Hardware noch die
gleiche unter der Haube.

1252
00:59:02,560 --> 00:59:04,670
Wie würde ich hier ein Wort zu speichern?

1253
00:59:04,670 --> 00:59:09,710
Nun, ein Wort in einem Computer wie
"Hallo!" würde wie diese gespeichert.

1254
00:59:09,710 --> 00:59:12,300
Und wenn Sie wollten eine längere
Wort, können Sie einfach

1255
00:59:12,300 --> 00:59:19,120
überschreiben, dass und etwas sagen
wie "Hallo" und speichern Sie das hier.

1256
00:59:19,120 --> 00:59:23,930
>> Und so auch hier diese contiguousness
ist eigentlich ein Vorteil,

1257
00:59:23,930 --> 00:59:26,530
weil ein Computer kann nur
gelesen von rechts nach links.

1258
00:59:26,530 --> 00:59:28,680
Aber hier ist eine Frage.

1259
00:59:28,680 --> 00:59:33,480
Im Rahmen dieses Wortes,
h-e-l-l-o, Ausrufezeichen,

1260
00:59:33,480 --> 00:59:38,740
wie könnte wissen, dass der Computer, auf dem die
Wort beginnt und wo das Wort endet?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
Im Rahmen der Zahlen,
Wie funktioniert der Computer

1263
00:59:43,800 --> 00:59:48,396
wissen, wie lange die Sequenz
Zahlen ist oder wo es beginnt?

1264
00:59:48,396 --> 00:59:50,270
Nun, es stellt sich out--
und wir werden nicht zu viel gehen

1265
00:59:50,270 --> 00:59:54,970
in dieser Ebene der detail--
Computer bewegen Material um im Speicher

1266
00:59:54,970 --> 00:59:57,800
buchstäblich über dieser Adressen.

1267
00:59:57,800 --> 01:00:02,080
Also in einem Computer, wenn Sie
Schreiben von Code Dinge zu speichern

1268
01:00:02,080 --> 01:00:05,800
wie Wörter, was du bist
wirklich tun ist die Eingabe

1269
01:00:05,800 --> 01:00:11,320
Ausdrücke, die wo in erinnern
Speicher des Computers diese Worte sind.

1270
01:00:11,320 --> 01:00:14,370
Also lassen Sie mich ein tun sehr,
sehr einfaches Beispiel.

1271
01:00:14,370 --> 01:00:18,260
>> Ich gehe voran gehen und
Öffnen Sie mit einem einfachen Textprogramm auf,

1272
01:00:18,260 --> 01:00:20,330
und ich werde zu erstellen
eine Datei namens hello.c.

1273
01:00:20,330 --> 01:00:22,849
Die meisten dieser Informationen wir
gehen in nicht sehr ausführlich,

1274
01:00:22,849 --> 01:00:25,140
aber ich werde ein zu schreiben
Programm in derselben Sprache,

1275
01:00:25,140 --> 01:00:31,140
C. Das ist weit mehr von Einschüchterungen,
Ich würde behaupten, als Scratch,

1276
01:00:31,140 --> 01:00:32,490
aber es ist sehr ähnlich im Geiste.

1277
01:00:32,490 --> 01:00:34,364
In der Tat, diese geschweiften
braces-- Sie können Art von

1278
01:00:34,364 --> 01:00:37,820
denken Sie an, was ich da dies gerade getan.

1279
01:00:37,820 --> 01:00:39,240
>> Lassen Sie uns dies tun, eigentlich.

1280
01:00:39,240 --> 01:00:45,100
Wenn grüne Fahne geklickt haben,
Mach Folgendes.

1281
01:00:45,100 --> 01:00:50,210
Ich möchte auszudrucken "Hallo."

1282
01:00:50,210 --> 01:00:51,500
Also das ist jetzt Pseudo-Code.

1283
01:00:51,500 --> 01:00:53,000
Ich bin Verwischung Art der Linien.

1284
01:00:53,000 --> 01:00:56,750
In C, diese Sprache ich spreche
über diese Linie Druck hallo

1285
01:00:56,750 --> 01:01:01,940
tatsächlich wird "printf" mit
Einige Klammern und ein Semikolon.

1286
01:01:01,940 --> 01:01:03,480
>> Aber es ist genau die gleiche Idee.

1287
01:01:03,480 --> 01:01:06,730
Und das ist sehr benutzerfreundlich
"Wenn grüne Fahne geklickt" wird

1288
01:01:06,730 --> 01:01:10,182
die viel mehr obskure "int main nichtig."

1289
01:01:10,182 --> 01:01:12,890
Und das hat wirklich keine Zuordnung,
so werde ich nur, dass zu ignorieren.

1290
01:01:12,890 --> 01:01:17,210
Aber die geschweiften Klammern sind wie die
gekrümmte Puzzleteile so.

1291
01:01:17,210 --> 01:01:18,700
>> So können Sie Art erraten.

1292
01:01:18,700 --> 01:01:22,357
Selbst wenn Sie noch nie programmiert haben,
Was macht dieses Programm wahrscheinlich?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Wahrscheinlich druckt hallo
mit einem Ausrufezeichen.

1295
01:01:28,000 --> 01:01:29,150
>> Also lassen Sie uns versuchen, dass.

1296
01:01:29,150 --> 01:01:30,800
Ich werde es zu retten.

1297
01:01:30,800 --> 01:01:34,000
Und dies ist wiederum ein sehr
alte Schulumgebung.

1298
01:01:34,000 --> 01:01:35,420
Ich kann nicht klicken, kann ich nicht ziehen.

1299
01:01:35,420 --> 01:01:36,910
Ich muss Befehle eingeben.

1300
01:01:36,910 --> 01:01:41,320
Deshalb möchte ich mein Programm laufen zu lassen, so dass
Ich könnte dies zu tun, wie hello.c.

1301
01:01:41,320 --> 01:01:42,292
Das ist die Datei, die ich lief.

1302
01:01:42,292 --> 01:01:43,500
Aber warten Sie, ich bin ein Schritt fehlt.

1303
01:01:43,500 --> 01:01:46,470
Was haben wir sagen, ist eine notwendige
Schritt für eine Sprache wie C?

1304
01:01:46,470 --> 01:01:49,470
Ich habe gerade Quelle geschrieben
Code, aber was brauche ich?

1305
01:01:49,470 --> 01:01:50,670
Ja, ich brauche einen Compiler.

1306
01:01:50,670 --> 01:01:57,670
Also auf meinem Mac hier, ich habe ein
Programm namens GCC, GNU-C-Compiler,

1307
01:01:57,670 --> 01:02:03,990
das erlaubt mir this-- wiederum zu tun
mein Quellcode in, werden wir es nennen,

1308
01:02:03,990 --> 01:02:04,930
Maschinensprache.

1309
01:02:04,930 --> 01:02:10,180
>> Und das kann ich sehen,
wieder, wie folgt, diese

1310
01:02:10,180 --> 01:02:14,090
nur sind die Nullen und Einsen I
erstellt von meinem Quellcode,

1311
01:02:14,090 --> 01:02:15,730
alle der Nullen und Einsen.

1312
01:02:15,730 --> 01:02:17,770
Und wenn ich will laufen
mein program-- es passiert

1313
01:02:17,770 --> 01:02:23,010
werden für genannt a.out
historische reasons-- "Hallo."

1314
01:02:23,010 --> 01:02:24,070
Ich kann es wieder laufen.

1315
01:02:24,070 --> 01:02:25,690
Hallo hallo hallo.

1316
01:02:25,690 --> 01:02:27,430
Und es scheint zu funktionieren.

1317
01:02:27,430 --> 01:02:31,000
>> Das bedeutet aber, irgendwo in meinem
Computerspeichers sind die Worte

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, Ausrufezeichen.

1319
01:02:35,279 --> 01:02:38,070
Und es stellt sich heraus, ebenso wie eine Seite,
was wäre ein Computer typischerweise

1320
01:02:38,070 --> 01:02:40,550
tun, damit es weiß, wo
Dinge beginnen, und es ist end--

1321
01:02:40,550 --> 01:02:42,460
hier geht ein spezielles Symbol zu setzen.

1322
01:02:42,460 --> 01:02:46,064
Und der Konvention ist das zu setzen
Zahl Null am Ende eines Wortes

1323
01:02:46,064 --> 01:02:48,230
so dass Sie wissen, wo es
tatsächlich endet, so dass Sie

1324
01:02:48,230 --> 01:02:52,750
halten nicht mehr Druck und mehr
Zeichen, als Sie eigentlich beabsichtigen.

1325
01:02:52,750 --> 01:02:55,400
>> Aber das Essen zum Mitnehmen hier, auch
obwohl dies ziemlich obskur ist,

1326
01:02:55,400 --> 01:02:58,140
letztendlich ist, dass es
Ziemlich einfach.

1327
01:02:58,140 --> 01:03:04,550
Sie waren eine Art von Band gegeben, ein leeres
Raum, auf dem Sie Briefe schreiben kann.

1328
01:03:04,550 --> 01:03:07,150
Sie haben einfach eine zu haben,
Sonderzeichen, wie willkürlich

1329
01:03:07,150 --> 01:03:10,316
die Zahl Null, am Ende zu setzen
Ihre Worte, so dass der Computer weiß,

1330
01:03:10,316 --> 01:03:13,410
oh, ich sollte aufhören Druck nach
Ich sehe das Ausrufezeichen.

1331
01:03:13,410 --> 01:03:16,090
Da das nächste, was es
ist ein ASCII-Wert von Null,

1332
01:03:16,090 --> 01:03:19,125
oder das Nullzeichen
jemand würde es nennen.

1333
01:03:19,125 --> 01:03:21,500
Aber es ist irgendwie ein Problem
hier, und lassen Sie uns wieder zurück

1334
01:03:21,500 --> 01:03:23,320
In den Zahlen für einen Moment.

1335
01:03:23,320 --> 01:03:28,720
Angenommen, dass ich in der Tat,
haben eine Reihe von Zahlen,

1336
01:03:28,720 --> 01:03:30,730
und nehmen wir an, dass die
Programm Ich schreibe ist

1337
01:03:30,730 --> 01:03:34,680
wie ein Notenbuch für Lehrer
und ein Lehrer Unterricht.

1338
01:03:34,680 --> 01:03:38,720
Und dieses Programm erlaubt es ihm oder ihr
ihre Schüler Noten eingeben

1339
01:03:38,720 --> 01:03:39,960
auf Quiz.

1340
01:03:39,960 --> 01:03:43,750
Und angenommen, dass der Student bekommt
100 auf ihre erste Quiz, vielleicht

1341
01:03:43,750 --> 01:03:49,920
wie ein 80 auf der nächsten, dann ein
75, dann eine 90 auf der vierten Quiz.

1342
01:03:49,920 --> 01:03:54,150
>> Deshalb an dieser Stelle in der Geschichte,
das Array von der Größe vier.

1343
01:03:54,150 --> 01:03:58,470
Es gibt absolut mehr Speicher in der
Computer, aber das Array, sozusagen

1344
01:03:58,470 --> 01:04:00,350
vier ist von ihrer Größe.

1345
01:04:00,350 --> 01:04:06,060
Nehmen wir nun an, dass der Lehrer will
ein fünftes Quiz der Klasse zuzuweisen.

1346
01:04:06,060 --> 01:04:08,510
Nun, eines der Dinge, die er
oder sie gehen zu müssen, zu tun

1347
01:04:08,510 --> 01:04:10,650
Hier ist nun einen zusätzlichen Wert zu speichern.

1348
01:04:10,650 --> 01:04:15,490
Aber wenn das Array der Lehrer hat
in diesem Programm erstellt ist von Größe für,

1349
01:04:15,490 --> 01:04:22,440
Eines der Probleme mit einer Anordnung ist, dass
halten Sie können nicht nur in den Speicher hinzufügen.

1350
01:04:22,440 --> 01:04:26,470
Denn was ist, wenn ein anderer Teil der
Programm hat das Wort "hey" genau dort?

1351
01:04:26,470 --> 01:04:29,650
>> Mit anderen Worten kann mein Gedächtnis sein
für alles in einem Programm verwendet.

1352
01:04:29,650 --> 01:04:33,250
Und wenn im Voraus getippt ich in, hey,
Ich möchte Eingang vier Quiz Partituren,

1353
01:04:33,250 --> 01:04:34,784
sie könnten hier und hier.

1354
01:04:34,784 --> 01:04:37,700
Und wenn Sie plötzlich Ihre Meinung ändern
später und sagen, dass ich ein fünftes Quiz wollen

1355
01:04:37,700 --> 01:04:40,872
Score, können Sie nicht einfach
setzen sie, wo immer Sie wollen,

1356
01:04:40,872 --> 01:04:42,580
denn was ist, wenn diese
Speicher verwendet

1357
01:04:42,580 --> 01:04:45,990
für etwas else-- ein anderes Programm
oder ein anderes Merkmal des Programms

1358
01:04:45,990 --> 01:04:46,910
dass Sie laufen?

1359
01:04:46,910 --> 01:04:50,650
So haben Sie im Voraus zu denken
wie Sie möchten, dass Ihre Daten zu speichern,

1360
01:04:50,650 --> 01:04:54,480
denn jetzt haben Sie gemalt
sich in eine digitale Ecke.

1361
01:04:54,480 --> 01:04:57,280
>> So könnte ein Lehrer statt
sagen, wenn ein Programm schreiben,

1362
01:04:57,280 --> 01:04:59,360
zu speichern, seine oder ihre
Noten, weißt du was?

1363
01:04:59,360 --> 01:05:04,180
Ich werde beantragen,
wenn mein Programm zu schreiben,

1364
01:05:04,180 --> 01:05:12,070
dass ich will null, eins, zwei, drei,
vier, fünf, sechs, acht Sorten insgesamt.

1365
01:05:12,070 --> 01:05:15,320
So ein, zwei, drei, vier,
fünf, sechs, sieben, acht.

1366
01:05:15,320 --> 01:05:18,612
Der Lehrer kann nur über zuteilen
Speicher, wenn sein oder ihr Programm zu schreiben

1367
01:05:18,612 --> 01:05:19,570
und sagen, Sie wissen, was?

1368
01:05:19,570 --> 01:05:22,236
Ich werde nie mehr vergeben
als acht Tests in einem Semester.

1369
01:05:22,236 --> 01:05:23,130
Das ist einfach verrückt.

1370
01:05:23,130 --> 01:05:24,470
Das werde ich nie vergeben.

1371
01:05:24,470 --> 01:05:28,270
Damit diese Art, wie er oder sie hat die
Flexibilität zu speichern Student Partituren,

1372
01:05:28,270 --> 01:05:33,010
wie 75, 90, und vielleicht ein extra wo
der Student bekam zusätzliche Kredite, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Aber wenn der Lehrer nie
verwendet diese drei Räume,

1374
01:05:36,130 --> 01:05:38,860
gibt es eine intuitive Mitnehmen hier.

1375
01:05:38,860 --> 01:05:41,410
Er oder sie ist nur verschwenden Sie Platz.

1376
01:05:41,410 --> 01:05:44,790
Also mit anderen Worten, es ist das
gemeinsamen Kompromisses in der Programmierung

1377
01:05:44,790 --> 01:05:48,241
wo Sie entweder zuweisen
genau so viel Speicher wie Sie wollen,

1378
01:05:48,241 --> 01:05:51,490
der Kopf davon ist, dass Sie sind super
efficient-- Sie sind nicht verschwenderisch

1379
01:05:51,490 --> 01:05:54,640
bei all-- aber der Nachteil davon
ist was passiert, wenn Sie Ihre Meinung ändern, wenn

1380
01:05:54,640 --> 01:05:58,780
mit dem Programm, das Sie speichern möchten,
mehr Daten, als Sie ursprünglich gedacht.

1381
01:05:58,780 --> 01:06:03,030
>> Also vielleicht die Lösung ist, dann,
Schreiben Sie Ihre Programme in einer solchen Art und Weise

1382
01:06:03,030 --> 01:06:05,605
dass sie mehr Speicherplatz
als sie tatsächlich benötigen.

1383
01:06:05,605 --> 01:06:07,730
Auf diese Weise Sie nicht gehen
laufen in dieses Problem,

1384
01:06:07,730 --> 01:06:09,730
aber du bist verschwenderisch.

1385
01:06:09,730 --> 01:06:12,960
Und je mehr Speicher Ihr Programm,
wie wir gestern besprochen, die weniger

1386
01:06:12,960 --> 01:06:15,410
Speicher, der verfügbar ist
für andere Programme,

1387
01:06:15,410 --> 01:06:18,790
Je früher Sie Ihren Computer verlangsamen könnte
nach unten wegen des virtuellen Speichers.

1388
01:06:18,790 --> 01:06:22,670
Und so könnte die ideale Lösung, was sein?

1389
01:06:22,670 --> 01:06:24,610
>> Unter-Aufteilung scheint schlecht.

1390
01:06:24,610 --> 01:06:27,030
Über Aufteilung scheint schlecht.

1391
01:06:27,030 --> 01:06:31,120
Also, was könnte eine bessere Lösung?

1392
01:06:31,120 --> 01:06:32,390
Die Neuverteilung.

1393
01:06:32,390 --> 01:06:33,590
Sei dynamischer.

1394
01:06:33,590 --> 01:06:37,520
Zwingen Sie sich nicht zu wählen
priori, am Anfang, was Sie wollen.

1395
01:06:37,520 --> 01:06:41,370
Und schon gar nicht über zuteilen,
damit du nicht verschwenderisch sein.

1396
01:06:41,370 --> 01:06:45,770
>> Und so, dieses Ziel zu erreichen, haben wir
müssen diese Datenstruktur zu werfen,

1397
01:06:45,770 --> 01:06:48,100
sozusagen weg.

1398
01:06:48,100 --> 01:06:51,080
Und so was ein Programmierer
wird in der Regel verwenden

1399
01:06:51,080 --> 01:06:55,940
etwas ist kein genannt
Array aber eine verknüpfte Liste.

1400
01:06:55,940 --> 01:07:00,860
Mit anderen Worten, wird er oder sie
Start ihres Gedächtnisses zu denken

1401
01:07:00,860 --> 01:07:05,280
als Art einer Form, dass sie
kann auf die folgende Art und Weise zu ziehen.

1402
01:07:05,280 --> 01:07:08,520
Wenn ich will, eine Nummer zu speichern in
ein program-- so ist es September,

1403
01:07:08,520 --> 01:07:12,600
Ich habe meine Schüler ein Quiz gegeben; Ich will
Für die Speicherung der ersten Quiz 'Studenten,

1404
01:07:12,600 --> 01:07:16,220
und sie haben eine 100 auf es-- I
werde meinen Computer zu fragen,

1405
01:07:16,220 --> 01:07:19,540
über das Programm, das ich habe
geschrieben, für einen Teil des Speichers.

1406
01:07:19,540 --> 01:07:22,570
Und ich werde das zu speichern
Nummer 100 in sie, und das ist es.

1407
01:07:22,570 --> 01:07:24,820
>> Dann ein paar Wochen später
wenn ich mein zweites Quiz bekommen,

1408
01:07:24,820 --> 01:07:27,890
und es ist Zeit zu geben
dass 90%, ich werde

1409
01:07:27,890 --> 01:07:32,129
um den Computer zu fragen, hey, Computer,
kann ich einen anderen Teil des Speichers haben?

1410
01:07:32,129 --> 01:07:34,170
Es wird mir das zu geben
leeren Teil des Speichers.

1411
01:07:34,170 --> 01:07:39,370
Ich werde 90 in der Zahl zu setzen,
aber in meinem Programm irgendwie other--

1412
01:07:39,370 --> 01:07:42,100
und wir werden keine Sorgen über
die Syntax für this-- Ich brauche

1413
01:07:42,100 --> 01:07:44,430
um die Kette irgendwie zusammen, um diese Dinge.

1414
01:07:44,430 --> 01:07:47,430
Und ich werde die Kette sie zusammen mit
was aussieht wie ein Pfeil hier.

1415
01:07:47,430 --> 01:07:50,050
>> Die dritte Quiz, die aufkommt,
Ich werde sagen, hey, Computer,

1416
01:07:50,050 --> 01:07:51,680
geben Sie mir einen anderen Teil des Speichers.

1417
01:07:51,680 --> 01:07:54,660
Und ich werde nach unten zu setzen
was auch immer es war, wie 75,

1418
01:07:54,660 --> 01:07:56,920
und ich habe an die Kette dieser
zusammen jetzt irgendwie.

1419
01:07:56,920 --> 01:08:00,290
Vierte Quiz kommt, und vielleicht
das ist gegen Ende des Semesters.

1420
01:08:00,290 --> 01:08:03,140
Und zu diesem Zeitpunkt mein Programm
könnte sein, Speicher mit

1421
01:08:03,140 --> 01:08:05,540
alle über den Ort, die alle über körperlich.

1422
01:08:05,540 --> 01:08:08,170
Und so nur zum Spaß, ich bin
geht dies zu ziehen weiter

1423
01:08:08,170 --> 01:08:11,260
quiz-- ich vergessen, was es war; ich
denken vielleicht ein 80 oder something--

1424
01:08:11,260 --> 01:08:12,500
Weg hierher.

1425
01:08:12,500 --> 01:08:15,920
>> Aber das ist in Ordnung, weil bildhaft
Ich werde diese Linie zu zeichnen.

1426
01:08:15,920 --> 01:08:19,063
Mit anderen Worten, in der Realität,
in der Hardware Ihres Computers,

1427
01:08:19,063 --> 01:08:20,979
die erste Punktzahl könnte
landen sie hier, weil es

1428
01:08:20,979 --> 01:08:22,529
Gleich zu Beginn des Semesters.

1429
01:08:22,529 --> 01:08:25,810
Der nächste könnte hier am Ende
weil ein wenig Zeit vergangen

1430
01:08:25,810 --> 01:08:27,210
und das Programm läuft weiter.

1431
01:08:27,210 --> 01:08:30,060
Die nächste Partitur, die war
ein 75 könnte hier sein.

1432
01:08:30,060 --> 01:08:33,420
Und die letzte Partitur könnte sein,
eine 80, der hier ist.

1433
01:08:33,420 --> 01:08:38,729
>> Also in Wirklichkeit physisch, könnte dies sein
was den Arbeitsspeicher Ihres Computers aussieht.

1434
01:08:38,729 --> 01:08:41,569
Aber dies ist nicht eine nützliche mental
Paradigma für einen Computer-Programmierer.

1435
01:08:41,569 --> 01:08:44,649
Warum sollten Sie darauf, wo die
Heck Ihre Daten landen?

1436
01:08:44,649 --> 01:08:46,200
Sie wollen einfach nur Daten zu speichern.

1437
01:08:46,200 --> 01:08:49,390
>> Dies ist eine Art, wie unsere Diskussion
Zuvor hatte der Würfel der Zeichnung.

1438
01:08:49,390 --> 01:08:52,200
Warum interessieren Sie sich, was
der Winkel des Würfels

1439
01:08:52,200 --> 01:08:53,740
und wie müssen Sie drehen zu ziehen?

1440
01:08:53,740 --> 01:08:54,950
Sie wollen einfach nur einen Würfel.

1441
01:08:54,950 --> 01:08:57,359
Ebenso hier, Sie
wollen einfach nur Klasse Buch.

1442
01:08:57,359 --> 01:08:59,559
Sie wollen einfach nur zu denken,
dies als eine Liste von Zahlen.

1443
01:08:59,559 --> 01:09:01,350
Wen kümmert es, wie es ist
in Hardware implementiert?

1444
01:09:01,350 --> 01:09:05,180
>> So ist die Abstraktion jetzt
hier ist das Bild.

1445
01:09:05,180 --> 01:09:07,580
Dies ist eine Liste verknüpft, wie
würde ein Programmierer es nennen,

1446
01:09:07,580 --> 01:09:10,640
soweit Sie haben eine
Liste offensichtlich von Zahlen.

1447
01:09:10,640 --> 01:09:14,990
Aber es ist verknüpft bildhaft
mittels dieser Pfeile,

1448
01:09:14,990 --> 01:09:18,510
und all diese Pfeile sind-- unter
die Haube, wenn Sie neugierig sind,

1449
01:09:18,510 --> 01:09:23,210
daran erinnern, dass unsere physische Hardware hat
Adressen null, eins, zwei, drei, vier.

1450
01:09:23,210 --> 01:09:28,465
Alle diese Pfeile sind, ist wie eine Landkarte
oder Richtungen, wo, wenn 90 ist-- jetzt

1451
01:09:28,465 --> 01:09:29,090
Ich habe zu zählen.

1452
01:09:29,090 --> 01:09:31,750
>> Null, eins, zwei, drei,
vier, fünf, sechs, sieben.

1453
01:09:31,750 --> 01:09:35,640
Es sieht aus wie die 90 ist
Speicheradresse Nummer sieben.

1454
01:09:35,640 --> 01:09:38,460
Alle diese Pfeile sind, ist
wie ein kleines Stück Papier

1455
01:09:38,460 --> 01:09:42,439
das ist Erteilung von Anweisungen an die
Programm, das diese Karte sagt folgen

1456
01:09:42,439 --> 01:09:43,880
In den Standort sieben zu bekommen.

1457
01:09:43,880 --> 01:09:46,680
Und dort finden Sie die
Studenten zweite Quiz-Score.

1458
01:09:46,680 --> 01:09:52,100
Inzwischen hat die 75--, wenn ich weitermachen,
dies ist sieben, acht, neun, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Dieser andere Pfeil stellt nur
eine Karte auf einen Speicherbereich 15.

1461
01:09:59,080 --> 01:10:02,550
Aber auch hier hat der Programmierer im Allgemeinen
nicht über dieses Maß an Detail kümmern.

1462
01:10:02,550 --> 01:10:05,530
Und in den meisten jedem Programmier
Sprache heute, der Programmierer

1463
01:10:05,530 --> 01:10:10,490
wissen nicht einmal in Erinnerung, wo
diese Zahlen tatsächlich sind.

1464
01:10:10,490 --> 01:10:14,830
er oder sie alles hat zu kümmern ist
dass sie irgendwie miteinander verbunden sind

1465
01:10:14,830 --> 01:10:18,390
in einer Datenstruktur wie diese.

1466
01:10:18,390 --> 01:10:21,580
>> Aber es stellt sich heraus, nicht
zu technisch zu bekommen.

1467
01:10:21,580 --> 01:10:27,430
Aber nur, weil wir können vielleicht
leisten, diese Diskussion hier zu haben,

1468
01:10:27,430 --> 01:10:33,630
nehme an, dass wir erneut
dieses Problem hier eines Arrays.

1469
01:10:33,630 --> 01:10:35,780
Mal sehen, ob wir hier bedauern würde.

1470
01:10:35,780 --> 01:10:42,950
Dieses ist 100, 90, 75 und 80.

1471
01:10:42,950 --> 01:10:44,980
>> Lassen Sie mich kurz diesen Anspruch.

1472
01:10:44,980 --> 01:10:48,980
Dies ist ein Array, und wieder, die
hervorstechendste Merkmal eines Arrays

1473
01:10:48,980 --> 01:10:52,400
Sie alle Ihre Daten ist, dass es wieder zu
zurück wahrsten Sinne des Wortes in memory-- an Rücken

1474
01:10:52,400 --> 01:10:56,830
ein Byte oder vielleicht vier Bytes,
einige feste Anzahl von Bytes entfernt.

1475
01:10:56,830 --> 01:11:00,710
In einer verknüpften Liste, die wir vielleicht ziehen
wie diese, unter der Haube, die

1476
01:11:00,710 --> 01:11:02,000
weiß, wo das Zeug?

1477
01:11:02,000 --> 01:11:03,630
Es braucht nicht einmal so zu fließen.

1478
01:11:03,630 --> 01:11:06,050
Einige der Daten könnte
zurück zu den dort überlassen.

1479
01:11:06,050 --> 01:11:07,530
Sie wissen nicht einmal.

1480
01:11:07,530 --> 01:11:15,430
>> Und so mit einem Array, haben Sie eine
Funktion als Random Access bekannt.

1481
01:11:15,430 --> 01:11:20,570
Und was Direktzugriffsmittel
dass der Computer sofort springen

1482
01:11:20,570 --> 01:11:22,730
an eine beliebige Stelle in einem Array.

1483
01:11:22,730 --> 01:11:23,580
Warum?

1484
01:11:23,580 --> 01:11:26,000
Da der Computer kennt
dass die erste Lage ist

1485
01:11:26,000 --> 01:11:29,540
null, eins, zwei und drei.

1486
01:11:29,540 --> 01:11:33,890
>> Und so, wenn Sie aus gehen wollen
Dieses Element zum nächsten Element,

1487
01:11:33,890 --> 01:11:36,099
Sie buchstäblich, in der
Computer Geist, fügen Sie einfach ein.

1488
01:11:36,099 --> 01:11:39,140
Wenn Sie auf das dritte Element gehen wollen,
fügen Sie einfach one-- nächste Element, nur

1489
01:11:39,140 --> 01:11:40,290
füge eins hinzu.

1490
01:11:40,290 --> 01:11:42,980
Jedoch in dieser Version
der Geschichte an, dass

1491
01:11:42,980 --> 01:11:46,080
der Computer derzeit auf der Suche
bei oder mit der Nummer 100 zu tun haben.

1492
01:11:46,080 --> 01:11:49,770
Wie kommen Sie auf die nächste
Klasse in der Klasse Buch?

1493
01:11:49,770 --> 01:11:52,560
>> Sie haben sieben zu nehmen
Schritte, die willkürlich ist.

1494
01:11:52,560 --> 01:11:58,120
Um zum nächsten zu erhalten, müssen Sie
nehmen acht weitere Schritte bis 15 zu erhalten.

1495
01:11:58,120 --> 01:12:02,250
Mit anderen Worten, es ist nicht ein
konstanten Abstand zwischen den Zahlen,

1496
01:12:02,250 --> 01:12:04,857
und so nur dauert es die
Computer mehr Zeit ist der Punkt.

1497
01:12:04,857 --> 01:12:06,940
Der Computer hat zu suchen
durch Speicher um

1498
01:12:06,940 --> 01:12:08,990
zu finden, was Sie suchen.

1499
01:12:08,990 --> 01:12:14,260
>> Während also ein Array neigt dazu, ein zu sein
schnelle Daten structure--, weil Sie

1500
01:12:14,260 --> 01:12:17,610
kann buchstäblich tun, nur einfache arithmetische
und wo Sie wollen, indem man hinzufügen,

1501
01:12:17,610 --> 01:12:21,300
für instance-- eine verknüpfte Liste,
Sie diese Funktion zu opfern.

1502
01:12:21,300 --> 01:12:24,020
Sie können einfach nicht von der ersten gehen
In den zweiten bis dritten bis vierten Platz.

1503
01:12:24,020 --> 01:12:25,240
Sie müssen die Karte folgen.

1504
01:12:25,240 --> 01:12:28,160
Sie müssen mehr Schritte unternehmen,
auf diese Werte zu erhalten, die

1505
01:12:28,160 --> 01:12:30,230
scheint eine Kosten zu addieren.

1506
01:12:30,230 --> 01:12:35,910
Also wir zahlen einen Preis, aber was war
das Merkmal, dass Dan hier suchte?

1507
01:12:35,910 --> 01:12:38,110
Was bedeutet eine verknüpfte Liste
anscheinend erlauben uns zu tun,

1508
01:12:38,110 --> 01:12:40,240
das war der Ursprung
diese besondere Geschichte?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Genau.

1511
01:12:43,830 --> 01:12:46,220
Eine dynamische Größe zu.

1512
01:12:46,220 --> 01:12:48,040
Wir können zu dieser Liste hinzufügen.

1513
01:12:48,040 --> 01:12:51,430
Wir können auch die Liste schrumpfen, so
dass wir verwenden nur so viel Speicher

1514
01:12:51,430 --> 01:12:55,560
wie wir eigentlich wollen, und so
wir sind nie über Aufteilung.

1515
01:12:55,560 --> 01:12:58,470
>> Jetzt nur noch, um wirklich nit-picky,
gibt es eine versteckte Kosten.

1516
01:12:58,470 --> 01:13:01,980
So sollten Sie nicht nur lassen Sie mich überzeugen
Sie, dass dies ein zwingender Kompromiss.

1517
01:13:01,980 --> 01:13:04,190
Es gibt eine andere versteckte Kosten hier.

1518
01:13:04,190 --> 01:13:06,550
Der Vorteil, klar zu sein,
ist, dass wir die Dynamik erhalten.

1519
01:13:06,550 --> 01:13:10,359
Wenn ich ein anderes Element will, kann ich nur
ziehen sie und eine Zahl in dort setzen.

1520
01:13:10,359 --> 01:13:12,150
Und dann kann ich es verlinken
mit einem Bild hier,

1521
01:13:12,150 --> 01:13:14,970
wenn ich habe, während hier, wieder,
gemalt mich in eine Ecke,

1522
01:13:14,970 --> 01:13:19,410
wenn etwas anderes ist bereits mit
die Erinnerung hier, ich bin kein Glück.

1523
01:13:19,410 --> 01:13:21,700
Ich habe mich in die Ecke manövriert.

1524
01:13:21,700 --> 01:13:24,390
>> Aber was ist die verborgene
kosten in diesem Bild?

1525
01:13:24,390 --> 01:13:27,690
Es ist nicht nur die Menge
der Zeit, die es dauert,

1526
01:13:27,690 --> 01:13:29,870
gehen von hier nach hier,
Das ist sieben Schritte, dann

1527
01:13:29,870 --> 01:13:32,820
acht Stufen, die mehr als eins ist.

1528
01:13:32,820 --> 01:13:34,830
Was ist eine andere versteckte Kosten?

1529
01:13:34,830 --> 01:13:35,440
Nicht nur Zeit.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Weitere Informationen finden Sie
notwendig, um dieses Bild zu erzielen.

1532
01:13:49,940 --> 01:13:53,210
>> Ja, das Karte, die kleinen Fetzen
Papier, als ich halten beschrieb sie als.

1533
01:13:53,210 --> 01:13:55,650
Diese arrows-- diejenigen sind nicht frei.

1534
01:13:55,650 --> 01:13:57,660
Ein computer-- Sie wissen
was ein Computer hat.

1535
01:13:57,660 --> 01:13:58,790
Es hat Nullen und Einsen.

1536
01:13:58,790 --> 01:14:03,170
Wenn Sie einen Pfeil darstellen oder eine
Karte oder eine Zahl, benötigen Sie eine Erinnerung.

1537
01:14:03,170 --> 01:14:05,950
So anderen Preis, den Sie
zahlen für eine verknüpfte Liste,

1538
01:14:05,950 --> 01:14:09,070
eine gemeinsame Informatik
Ressource, ist auch Raum.

1539
01:14:09,070 --> 01:14:11,710
>> Und in der Tat so, so häufig,
unter den Kompromissen

1540
01:14:11,710 --> 01:14:15,580
bei der Gestaltung Software-Engineering
Systeme ist Zeit und space--

1541
01:14:15,580 --> 01:14:18,596
sind zwei Ihrer Zutaten, zwei
Ihrer teuersten Zutaten.

1542
01:14:18,596 --> 01:14:21,220
Das kostet mich mehr Zeit
weil ich diese Karte zu folgen,

1543
01:14:21,220 --> 01:14:25,730
aber es kostet mich auch mehr Platz
weil ich um diese Karte zu halten.

1544
01:14:25,730 --> 01:14:28,730
So ist die Hoffnung, als wir haben Art
diskutiert über gestern und heute,

1545
01:14:28,730 --> 01:14:31,720
ist, dass die Vorteile
die Kosten überwiegen.

1546
01:14:31,720 --> 01:14:33,870
>> Aber es gibt keine offensichtliche Lösung.

1547
01:14:33,870 --> 01:14:35,870
Vielleicht ist es better--
a la schnell und schmutzig,

1548
01:14:35,870 --> 01:14:38,660
wie Kareem vorgeschlagen earlier--
Speicher auf das Problem zu werfen.

1549
01:14:38,660 --> 01:14:42,520
Nur mehr Speicher kaufen, denken weniger
schwer, über das Problem zu lösen,

1550
01:14:42,520 --> 01:14:44,595
und lösen es in einen einfacheren Weg.

1551
01:14:44,595 --> 01:14:46,720
Und in der Tat früher, als
wir sprachen über Vor- und Nachteile,

1552
01:14:46,720 --> 01:14:49,190
es war kein Platz in
der Computer und der Zeit.

1553
01:14:49,190 --> 01:14:51,810
Es war Entwickler Zeit, die
ist noch eine andere Ressource.

1554
01:14:51,810 --> 01:14:54,829
>> Also noch einmal, es ist dieser Spagat
versuchen, die diese Dinge zu entscheiden,

1555
01:14:54,829 --> 01:14:55,870
zu verbringen sind Sie bereit?

1556
01:14:55,870 --> 01:14:57,380
Welches ist die am wenigsten teuer?

1557
01:14:57,380 --> 01:15:01,040
Welche liefert die besseren Ergebnisse?

1558
01:15:01,040 --> 01:15:01,540
Ja?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Tatsächlich.

1561
01:15:12,580 --> 01:15:15,970
In diesem Fall, wenn Sie
Darstellung von Zahlen in der maps--

1562
01:15:15,970 --> 01:15:18,820
diese sind in vielen Sprachen genannt
"Zeiger" oder "Adressen" -

1563
01:15:18,820 --> 01:15:20,390
es ist die doppelte Raum.

1564
01:15:20,390 --> 01:15:24,390
Das muss nicht so schlimm, wie doppelt so hoch sein, wenn
jetzt gerade speichern wir nur Zahlen.

1565
01:15:24,390 --> 01:15:27,410
Nehmen wir an, dass wir die Speicherung
Patientenakten in einem hospital--

1566
01:15:27,410 --> 01:15:30,870
so Piersons Namen, Telefonnummern,
Sozialversicherungsnummern, Arzt

1567
01:15:30,870 --> 01:15:31,540
Geschichte.

1568
01:15:31,540 --> 01:15:34,160
Dieses Feld könnte sein, viel,
viel größer, in welchem ​​Fall

1569
01:15:34,160 --> 01:15:38,000
ein kleiner kleiner Zeiger, die Adresse
der nächste element-- es ist keine große Sache.

1570
01:15:38,000 --> 01:15:40,620
Es ist so eine Franse
kostet es spielt keine Rolle.

1571
01:15:40,620 --> 01:15:43,210
Aber in diesem Fall, ja, es ist eine Verdoppelung.

1572
01:15:43,210 --> 01:15:45,290
Gute Frage.

1573
01:15:45,290 --> 01:15:47,900
>> Lassen Sie uns über Zeit ein Gespräch
wenig konkreter.

1574
01:15:47,900 --> 01:15:50,380
Was ist die Laufzeit
der Suche dieser Liste?

1575
01:15:50,380 --> 01:15:53,640
Angenommen, ich wollte zu suchen
durch alle Noten der Schüler,

1576
01:15:53,640 --> 01:15:55,980
und es gibt n-Typen
in dieser Datenstruktur.

1577
01:15:55,980 --> 01:15:58,830
Auch hier können wir leihen
das Vokabular der früher.

1578
01:15:58,830 --> 01:16:00,890
Dies ist eine lineare Datenstruktur.

1579
01:16:00,890 --> 01:16:04,570
>> Big O von n ist, was erforderlich ist, um zu bekommen
bis zum Ende dieser Datenstruktur,

1580
01:16:04,570 --> 01:16:08,410
whereas-- und wir haben nicht gesehen
diese before-- ein Array gibt Ihnen

1581
01:16:08,410 --> 01:16:13,555
was konstante Zeit genannt, was bedeutet,
einem Schritt oder in zwei Schritten oder 10 steps--

1582
01:16:13,555 --> 01:16:14,180
spielt keine Rolle.

1583
01:16:14,180 --> 01:16:15,440
Es ist eine feste Zahl.

1584
01:16:15,440 --> 01:16:17,440
Es hat nichts damit zu tun,
die Größe des Arrays.

1585
01:16:17,440 --> 01:16:20,130
Und der Grund dafür,
wiederum ist mit wahlfreiem Zugriff.

1586
01:16:20,130 --> 01:16:23,180
Der Computer kann nur sofort
Sprung zu einem anderen Ort,

1587
01:16:23,180 --> 01:16:27,770
denn sie sind alle gleich
Abstand von allem anderen.

1588
01:16:27,770 --> 01:16:29,112
Es ist beteiligt kein Denken.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Gut.

1591
01:16:32,400 --> 01:16:39,230
Also, wenn ich kann, lassen Sie mich versuchen,
malen zwei letzte Bilder.

1592
01:16:39,230 --> 01:16:42,830
Eine sehr häufige man als Hash-Tabelle bekannt.

1593
01:16:42,830 --> 01:16:51,120
Also, diese Diskussion zu motivieren,
Lassen Sie mich darüber nachdenken, wie dies zu tun.

1594
01:16:51,120 --> 01:16:52,610
>> Also, wie wäre es damit?

1595
01:16:52,610 --> 01:16:55,160
Nehmen wir an, dass das Problem
Wir wollen jetzt zu lösen

1596
01:16:55,160 --> 01:16:58,360
in einem dictionary-- implementiert
so eine ganze Reihe von englischen Wörtern

1597
01:16:58,360 --> 01:16:59,330
oder Wasauchimmer.

1598
01:16:59,330 --> 01:17:02,724
Und das Ziel ist es, zu beantworten
Fragen der Form ist dies ein Wort?

1599
01:17:02,724 --> 01:17:04,640
So wollen Sie implementieren
ein Spell Checker, nur

1600
01:17:04,640 --> 01:17:07,220
wie ein physischer Wörterbuch
dass Sie die Dinge sehen in kann.

1601
01:17:07,220 --> 01:17:10,490
Nehmen wir an, ich wäre dies mit einer Reihe zu tun.

1602
01:17:10,490 --> 01:17:12,590
Ich konnte dies tun.

1603
01:17:12,590 --> 01:17:20,756
>> Und wenn die Worte Apfel sind
und Banane und Melone.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
Und ich kann nicht denken Früchte
dass mit d beginnen, so dass wir nur

1606
01:17:26,465 --> 01:17:27,590
gehen drei Früchte zu haben.

1607
01:17:27,590 --> 01:17:31,510
Das ist also ein Array ist, und wir sind
all dieser Worte zu speichern

1608
01:17:31,510 --> 01:17:34,200
in diesem Wörterbuch als Array.

1609
01:17:34,200 --> 01:17:39,350
Die Frage ist also, wie sonst
könnten Sie diese Informationen speichern?

1610
01:17:39,350 --> 01:17:43,160
>> Nun, ich bin betrügt Art von hier, weil
jeder dieser Buchstaben im Wort

1611
01:17:43,160 --> 01:17:44,490
ist wirklich ein einzelnes Byte.

1612
01:17:44,490 --> 01:17:46,740
Also, wenn ich wollte wirklich sein
nit-picky, sollte ich wirklich

1613
01:17:46,740 --> 01:17:49,600
werden Aufteilung dies in viel
kleinere Stücke der Erinnerung,

1614
01:17:49,600 --> 01:17:51,289
und wir konnten genau das tun.

1615
01:17:51,289 --> 01:17:53,580
Aber wir werden den Weg laufen
das gleiche Problem wie zuvor.

1616
01:17:53,580 --> 01:17:56,674
Was ist, wenn, wie Merriam Webster oder Oxford
jeder tut year-- sie Wörter hinzufügen

1617
01:17:56,674 --> 01:17:59,340
zum dictionary-- tun wir nicht
unbedingt wollen uns zu malen

1618
01:17:59,340 --> 01:18:00,780
in eine Ecke mit einem Array?

1619
01:18:00,780 --> 01:18:05,710
>> Anstatt also, vielleicht ein intelligenter Ansatz
ist Apple in seinem eigenen Knoten oder Box zu setzen,

1620
01:18:05,710 --> 01:18:11,190
wie wir sagen würden, Banane, und
dann haben wir hier Cantaloupe.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
Und wir String diese Dinge zusammen.

1623
01:18:16,790 --> 01:18:19,980
Das ist also das Array, und
dies ist die verknüpfte Liste.

1624
01:18:19,980 --> 01:18:23,300
Wenn Sie nicht ganz sehen, es ist einfach
"Array", sagt und das sagt "-Liste."

1625
01:18:23,300 --> 01:18:25,780
>> Wir haben also die gleiche
genaue Fragen wie zuvor,

1626
01:18:25,780 --> 01:18:28,600
wobei wir jetzt haben,
Dynamik in unserer verknüpften Liste.

1627
01:18:28,600 --> 01:18:31,090
Aber wir haben eine ziemlich langsame Wörterbuch.

1628
01:18:31,090 --> 01:18:32,870
Angenommen, ich möchte ein Wort nachschlagen.

1629
01:18:32,870 --> 01:18:35,430
Es könnte nehmen mir große O n
Schritte, weil das Wort Macht

1630
01:18:35,430 --> 01:18:37,840
sein, den ganzen Weg am Ende der
die Liste, wie Cantaloupe.

1631
01:18:37,840 --> 01:18:40,600
Und es stellt sich heraus, dass
in der Programmierung, sortieren

1632
01:18:40,600 --> 01:18:42,700
der heilige Gral der Daten
Strukturen, ist etwas,

1633
01:18:42,700 --> 01:18:46,620
das gibt Ihnen konstant
Zeit wie ein Array

1634
01:18:46,620 --> 01:18:50,870
aber das gibt Ihnen weiterhin Dynamik.

1635
01:18:50,870 --> 01:18:52,940
>> So können wir haben das Beste aus beiden Welten?

1636
01:18:52,940 --> 01:18:55,570
Und in der Tat, es ist etwas
die Hash-Tabelle genannt

1637
01:18:55,570 --> 01:18:59,320
das es Ihnen ermöglicht, genau zu tun
dass, wenn auch etwa.

1638
01:18:59,320 --> 01:19:03,140
Eine Hash-Tabelle ist ein schicker
Datenstruktur, die wir

1639
01:19:03,140 --> 01:19:06,340
denken Sie an wie die
Kombination eines array--

1640
01:19:06,340 --> 01:19:12,390
und ich werde es zu zeichnen
wie this-- und verkettete Listen

1641
01:19:12,390 --> 01:19:17,310
dass ich hier wie diese ziehen.

1642
01:19:17,310 --> 01:19:19,760
>> Und die Art und Weise dieses Ding
Arbeiten ist wie folgt.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Wenn diese now-- Hash table--
meine dritte Datenstruktur ist,

1645
01:19:29,540 --> 01:19:32,590
und ich möchte zu speichern
in diesen Worten, weiß ich nicht

1646
01:19:32,590 --> 01:19:35,440
möchte nur all die Speicherung
Worte, Rücken an Rücken Rücken an Rücken.

1647
01:19:35,440 --> 01:19:37,430
Ich möchte einige zu nutzen
Stück Information

1648
01:19:37,430 --> 01:19:40,330
über die Worte, die lassen wird
mir bekommen sie, wo es schneller.

1649
01:19:40,330 --> 01:19:43,666
>> Also angesichts der Worte Apfel
und Banane und Melone,

1650
01:19:43,666 --> 01:19:45,040
Ich wählte absichtlich diese Worte.

1651
01:19:45,040 --> 01:19:45,340
Warum?

1652
01:19:45,340 --> 01:19:47,631
Was ist eine Art grundlegend
anders über die drei?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Was ist das offensichtlich?

1655
01:19:51,484 --> 01:19:52,900
Sie beginnen mit verschiedenen Buchstaben.

1656
01:19:52,900 --> 01:19:53,900
>> So wissen Sie was?

1657
01:19:53,900 --> 01:19:57,120
Anstatt alle meine setzen Worte in
die gleichen Eimer, so zu sprechen,

1658
01:19:57,120 --> 01:20:00,390
wie in einer großen Liste, warum nicht
Ich zumindest versuchen, eine Optimierung

1659
01:20:00,390 --> 01:20:04,180
und machen meine Listen 1/26 so lang.

1660
01:20:04,180 --> 01:20:07,440
Eine überzeugende Optimierung
könnte sein, warum nicht tun

1661
01:20:07,440 --> 01:20:10,650
I-- beim Einfügen eines Wortes
in dieser Datenstruktur,

1662
01:20:10,650 --> 01:20:14,300
in den Speicher des Computers, warum
nicht habe ich alle hier 'a' Worte,

1663
01:20:14,300 --> 01:20:17,270
hier alle 'b' Worte,
und all die 'c' Worte hier?

1664
01:20:17,270 --> 01:20:24,610
So endet das einen Apfel Aufstellen
hier, Banane hier, Melone hier,

1665
01:20:24,610 --> 01:20:25,730
und so weiter.

1666
01:20:25,730 --> 01:20:31,700
>> Und wenn ich einen zusätzlichen
Wort like--, was ein anderer ist?

1667
01:20:31,700 --> 01:20:36,640
Apfel, Banane, Birne.

1668
01:20:36,640 --> 01:20:39,370
Wer glaube, einer Frucht
Dies beginnt mit einem, b oder c?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- perfekt.

1670
01:20:40,570 --> 01:20:43,990
Das wird hier enden.

1671
01:20:43,990 --> 01:20:47,530
Und so scheinen wir zu haben
geringfügig bessere Lösung,

1672
01:20:47,530 --> 01:20:50,820
denn jetzt, wenn ich will
für Apfel zu suchen, ich

1673
01:20:50,820 --> 01:20:53,200
first-- ich nicht nur tauchen
in meine Datenstruktur.

1674
01:20:53,200 --> 01:20:54,850
Ich tauchen nicht in meinem Speicher des Computers.

1675
01:20:54,850 --> 01:20:56,530
Ich schaue zuerst auf den ersten Buchstaben.

1676
01:20:56,530 --> 01:20:58,610
>> Und das ist es, was einen Computer
Wissenschaftler sagen würde.

1677
01:20:58,610 --> 01:21:00,760
Sie Hash in der Datenstruktur.

1678
01:21:00,760 --> 01:21:04,100
Sie nehmen Ihre Eingabe, die in
Dieser Fall ist ein Wort wie Apfel.

1679
01:21:04,100 --> 01:21:07,150
Sie analysieren, mit Blick auf
der erste Buchstabe in diesem Fall

1680
01:21:07,150 --> 01:21:08,340
Hashing es dabei.

1681
01:21:08,340 --> 01:21:10,950
Hashing ist ein allgemeiner Begriff, wobei
Sie nehmen etwas als Eingabe

1682
01:21:10,950 --> 01:21:12,116
und Sie erzeugen eine Ausgabe.

1683
01:21:12,116 --> 01:21:15,090
Und der Ausgang daß
Fall ist die Lage

1684
01:21:15,090 --> 01:21:18,150
Sie wollen, die erste zu suchen
Lage, die zweite Lage, die dritte.

1685
01:21:18,150 --> 01:21:22,160
So ist der Eingang ist Apfel,
der Ausgang zuerst.

1686
01:21:22,160 --> 01:21:25,054
Der Eingang ist Banane, dem
Ausgabe sollte Sekunde.

1687
01:21:25,054 --> 01:21:27,220
Der Eingang ist Melone,
sollte die Ausgabe dritte sein.

1688
01:21:27,220 --> 01:21:30,320
Der Eingang ist Heidelbeeren, die
Ausgabe sollte wieder zweite sein.

1689
01:21:30,320 --> 01:21:34,010
Und das ist, was hilft Ihnen nehmen
Abkürzungen durch Ihr Gedächtnis

1690
01:21:34,010 --> 01:21:39,050
um Worte zu bekommen
oder Daten effektiver zu gestalten.

1691
01:21:39,050 --> 01:21:43,330
>> Nun schneidet diese unsere Zeit nach unten potentiell
um so viel wie eine von 26,

1692
01:21:43,330 --> 01:21:45,850
denn wenn man davon ausgehen, dass Sie
haben so viele "a" Wörter wie "z"

1693
01:21:45,850 --> 01:21:48,080
Wörter wie "q" Worte, die
nicht wirklich realistic--

1694
01:21:48,080 --> 01:21:50,830
Sie gehen Skew über zu haben
bestimmte Buchstaben des alphabet--

1695
01:21:50,830 --> 01:21:53,204
aber dies wäre eine inkrementelle
Ansatz, erlaubt es

1696
01:21:53,204 --> 01:21:55,930
Sie Wörter sehr viel schneller zu bekommen.

1697
01:21:55,930 --> 01:21:59,660
Und in Wirklichkeit ein ausgeklügeltes
Programm, das Googles der Welt,

1698
01:21:59,660 --> 01:22:02,180
die Facebooks der world--
sie würden eine Hash-Tabelle verwenden

1699
01:22:02,180 --> 01:22:03,740
für viele verschiedene Zwecke.

1700
01:22:03,740 --> 01:22:06,590
Aber sie würden nicht so naiv sein
auf den ersten Buchstaben zu suchen einfach

1701
01:22:06,590 --> 01:22:09,700
in Apfel oder Banane oder
Birne oder Melone,

1702
01:22:09,700 --> 01:22:13,420
weil, wie Sie diese sehen können
Listen bekommen könnte noch lang.

1703
01:22:13,420 --> 01:22:17,130
>> Und so könnte dies noch Art sein
von linear-- so eine Art langsam,

1704
01:22:17,130 --> 01:22:19,980
wie mit dem großen O n
dass wir früher diskutiert.

1705
01:22:19,980 --> 01:22:25,290
Also, was eine wirklich gute Hash-Tabelle wird
do-- es wird eine viel größere Array.

1706
01:22:25,290 --> 01:22:28,574
Und es wird eine viel mehr verwenden
anspruchsvolle Hashing-Funktion,

1707
01:22:28,574 --> 01:22:30,240
so dass es sieht nicht nur auf dem "a".

1708
01:22:30,240 --> 01:22:35,480
Vielleicht sieht es bei "a-p-p-l-e" und
irgendwie wandelt diese fünf Buchstaben

1709
01:22:35,480 --> 01:22:38,400
in den Ort, an dem
Apple sollte aufbewahrt werden.

1710
01:22:38,400 --> 01:22:42,660
Wir verwenden nur naiv den Buchstaben "a"
allein, denn es ist schön und einfach.

1711
01:22:42,660 --> 01:22:44,600
>> Aber eine Hash-Tabelle, in
Am Ende können Sie denken,

1712
01:22:44,600 --> 01:22:47,270
als eine Kombination aus
ein Array, von denen jede

1713
01:22:47,270 --> 01:22:51,700
hat eine verknüpfte Liste, die im Idealfall
sollte so kurz wie möglich sein.

1714
01:22:51,700 --> 01:22:54,364
Und das ist nicht offensichtlich, dass die Lösung.

1715
01:22:54,364 --> 01:22:57,280
In der Tat, ein Großteil der Feinabstimmung
das geht unter der Haube auf, wenn

1716
01:22:57,280 --> 01:22:59,654
Umsetzung dieser Arten von
anspruchsvolle Datenstrukturen

1717
01:22:59,654 --> 01:23:01,640
ist das, was das Recht ist
Länge des Arrays?

1718
01:23:01,640 --> 01:23:03,250
Was ist die richtige Hash-Funktion?

1719
01:23:03,250 --> 01:23:04,830
Wie lagere man die Dinge in Erinnerung?

1720
01:23:04,830 --> 01:23:07,249
>> Aber klar, wie schnell
diese Art der Diskussion

1721
01:23:07,249 --> 01:23:10,540
Art eskaliert, entweder so weit, dass es
über den Kopf an dieser Stelle, die

1722
01:23:10,540 --> 01:23:11,360
ist gut.

1723
01:23:11,360 --> 01:23:18,820
Aber wir begannen, Rückruf, mit wirklich
etwas niedriger Ebene und Elektronik.

1724
01:23:18,820 --> 01:23:20,819
Und so ist das auch in diesem
Thema der Abstraktion,

1725
01:23:20,819 --> 01:23:23,610
wo sobald Sie anfangen zu nehmen
gewährt, OK, habe ich es-- es bekam

1726
01:23:23,610 --> 01:23:26,680
physischen Speicher, OK, bekam es, jede
physischen Standort hat eine Adresse,

1727
01:23:26,680 --> 01:23:29,910
OK, ich habe es, kann ich darstellen
diese Adressen als arrows--

1728
01:23:29,910 --> 01:23:34,650
Sie können sehr schnell zu haben, starten
anspruchsvollere Gespräche, die

1729
01:23:34,650 --> 01:23:38,360
am Ende scheinen uns zu ermöglichen
um Probleme zu lösen wie die Suche

1730
01:23:38,360 --> 01:23:41,620
und Sortieren effektiver.

1731
01:23:41,620 --> 01:23:44,190
Und seien Sie versichert, too--
weil ich denke, das ist

1732
01:23:44,190 --> 01:23:48,700
ist der tiefste haben wir in einige gegangen
dieser CS Themen proper-- wir haben

1733
01:23:48,700 --> 01:23:51,880
an einem Tag und eine Hälfte an das getan
zeigen, was Sie in der Regel über tun könnte

1734
01:23:51,880 --> 01:23:55,520
der Verlauf von acht Wochen in einem Semester.

1735
01:23:55,520 --> 01:23:59,670
>> Haben Sie Fragen zu diesen?

1736
01:23:59,670 --> 01:24:01,100
Nein?

1737
01:24:01,100 --> 01:24:01,940
Gut.

1738
01:24:01,940 --> 01:24:05,610
Nun, warum wir dort nicht anhalten,
beginnen Mittagessen ein paar Minuten zu früh,

1739
01:24:05,610 --> 01:24:07,052
Wiederaufnahme nur etwa eine Stunde in?

1740
01:24:07,052 --> 01:24:08,760
Und ich werde verweilen
ein bisschen mit Fragen.

1741
01:24:08,760 --> 01:24:11,343
Dann werde ich gehen zu müssen
Nehmen Sie ein paar Anrufe, wenn das OK ist.

1742
01:24:11,343 --> 01:24:15,000
Ich werde in der Zwischenzeit etwas Musik drehen,
aber das Mittagessen sollte um die Ecke sein.

1743
01:24:15,000 --> 01:24:17,862