DAVID MALAN: Alles in Ordnung. Wir sind zurück. Also in diesem Segment über die Programmierung, was Ich dachte, wir tun würde, eine Mischung aus Dingen. Eins, tun ein wenig von etwas hands-on, wenn auch mit einer spielerischen Programmierung environment-- eine, die demonstrativ von genau die Art von Ideen Wir haben darüber gesprochen, aber ein wenig mehr formal. Zwei, Blick auf einige Je mehr technische Möglichkeiten, dass ein Programmierer lösen würde tatsächlich Probleme wie die Suche Problem dass wir vor geschaut und auch ein grundsätzlicher interessantes Problem des Sortierens. 

Wir gingen davon nur aus der get gehen dass das Telefonbuch wurde sortiert, aber das allein ist eigentlich ganz ein schweres Problem mit vielen verschiedenen Möglichkeiten, es zu lösen. Also werden wir diese verwenden, wie eine Klasse von Problemen Vertreter der Dinge, die könnte im Allgemeinen gelöst werden. Und dann werden wir reden etwa im Detail, was werden Daten genannt structures-- ausgefallenere Möglichkeiten wie verkettete Listen und Hash-Tabellen und Bäume, die ein Programmierer würde tatsächlich verwenden und verwenden in der Regel auf einer Tafel zu malen ein Bild von dem, was er oder sie sieht für die Umsetzung einige Stück Software. 

Also lassen Sie uns die hands-on zu tun Teil zuerst. Deshalb sollte man nur die Hände schmutzig mit ein Umwelt genannt scratch.mit.edu. Dies ist ein Werkzeug, das wir verwenden in unserem Bachelor-Klasse. Auch wenn es entworfen ab 12 Jahren auf, wir nutzen es für die oben Teil dieser ziemlich viel da es ein schönes, Spaß grafische Art und Weise des Lernens ein wenig etwas über die Programmierung. Also Kopf zu dieser URL, wo Sie sehen sollte eine Seite ganz wie diese, und gehen Sie vor und klicken Sie auf Join Scratch oben rechts und wählen Sie einen Benutzernamen und ein Passwort und erhalten letztlich selbst ein account-- scratch.mit.edu. Ich dachte, ich dies als ein verwenden würde, Gelegenheit erste, dies zu zeigen. Eine Frage kam in der Pause über das, was Code tatsächlich aussieht. Und wir sprachen während der Pause über C, in particular-- insbesondere ein untere Ebene in einer älteren Sprache. Und ich habe gerade eine schnelle Google-Suche C-Code zu finden für binäre Suche, der Algorithmus, wir die früher verwendet wurde, dass die Telefonbuch zu suchen. Dieses spezielle Beispiel ist natürlich nicht ein Telefonbuch zu suchen. Es sucht nur eine ganze Reihe von Nummern in den Speicher des Computers. Aber wenn Sie möchten, erhalten nur eine visuelle Sinn dessen, was eine tatsächliche Programmierung Sprache sieht aus wie es aussieht ein wenig so etwas wie dieses. So ist es etwa 20-plus, 30 oder so Zeilen Code, aber das Gespräch, das wir wurden mit über Pause war darüber, wie diese tatsächlich wird in Nullen und Einsen verwandelt und wenn Sie nicht nur rückgängig machen können, dass verarbeiten und gehen von Nullen und Einsen zurück zum Code. 

Leider ist der Prozess ist so transformierende dass es viel einfacher ist, gesagt als getan. Ich ging weiter und tatsächlich drehte das Programm, Binäre Suche, in Nullen und Einsen durch eine Programm namens den Compiler, dass ich passieren hier direkt auf meinem Mac zu haben. Und wenn Sie den Bildschirm schauen hier, die sich speziell auf diesen mittleren sechs Spalten nur, Sie werden sehen, nur Nullen und Einsen. Und das sind die Nullen und Einsen, dass komponieren genau das Suchprogramm. 

Und so jedes Stück von fünf Bits, Jedes Byte von Nullen und Einsen hier, repräsentieren einige Anweisungen typischerweise innerhalb eines Computers. Und in der Tat, wenn Sie gehört haben, die Marketing-Slogan "Intel inside" - das, natürlich nur bedeutet, dass Sie eine haben Intel CPU oder Gehirn im Computer. Und was das bedeutet eine CPU zu sein dass Sie einen Befehlssatz, sozusagen. 

Jede CPU in der Welt viele sie von Intel in diesen Tagen, versteht eine endliche Anzahl von Instruktionen. Und diese Anweisungen sind so niedrigen Niveau so fügen Sie diese beiden Zahlen zusammen, multiplizieren diese beiden Zahlen zusammen, bewegen, dieses Stück von Daten von hier im Speicher hier, speichern diese Informationen von hier in Erinnerung zu hier, und so forth-- so sehr, sehr Low-Level, fast elektronische Details. Aber mit diesen mathematischen Operationen gekoppelt mit dem, was wir früher diskutiert, die Darstellung von Daten, als Nullen und Einsen, können Sie bauen alles dass ein Computer heute tun kann, ob es ist Text-, Grafik-, Musical, oder andernfalls. 

Das ist also sehr leicht zu bekommen in das Unkraut verloren rasch. Und es gibt eine Menge von syntaktische Herausforderungen wobei, wenn Sie die einfachste machen, dümmsten Fehler keines des Programms funktioniert auch immer. Und so stattdessen eine der Verwendung Sprache wie C an diesem Morgen, Ich dachte, es wäre mehr Spaß, um tatsächlich tun etwas mehr visuelle, die während für Kinder entwickelt tatsächlich ist eine perfekte Manifestation einer tatsächlichen Programmierung language-- passiert einfach zu Verwenden Sie Bilder anstelle von Text diese Ideen zu vertreten. 

Also, wenn Sie in der Tat eine haben Konto auf scratch.mit.edu, klicken Sie auf die Schaltfläche Erstellen am oberen Rand der Seite links. Und Sie sollten eine Umgebung zu sehen wie die, die ich bin etwa auf meinem Bildschirm zu sehen Hier. Und wir verbringen nur ein wenig wenig Zeit, hier zu spielen. Mal sehen, ob wir nicht alle etwas lösen können Probleme in der folgenden Weise zusammen. 

Also, was Sie in dieser sehen environment-- und eigentlich nur lassen mich innehalten. Ist jemand hier nicht? Nicht hier? OK. Also lassen Sie mich ein paar weisen darauf hin, Eigenschaften dieser Umgebung. 

So ganz oben links auf dem Bildschirm, wir haben Scratch Bühne, sozusagen. Scratch ist nicht nur der Name dieser Programmiersprache; es ist auch der Name der Katze, Sie sehen dort standardmäßig in Orange. Er ist auf einer Bühne, so ähnlich wie ich beschrieben die Schildkröte früher als in einem Wesen rechteckigen weißen Tafel Umwelt. Diese Katze der Welt ist völlig beschränkt zu diesem Rechteck nach oben oben gibt. 

Inzwischen auf der rechten Seite hier, es ist nur Skripte Bereich, ein unbeschriebenes Blatt, wenn man so will. Das ist, wohin wir gehen zu schreiben unsere Programme in nur einem Augenblick. Und die Bausteine, dass wir verwenden zu schreiben diese program-- das Rätsel Stücke, wenn Sie will-- sind denen hier in der Mitte, und sie sind kategorisiert durch Funktionalität. So zum Beispiel, ich gehe voran gehen und zeigen zumindest eine von diesen. Ich gehe voran gehen und klicken Sie auf die Kategorie bis oben. 

Das sind also die Kategorien bis oben. Ich werde die Steuerungskategorie zu klicken. Vielmehr werde ich die Ereignisse zu klicken Kategorie, die allererste bis oben. Und wenn Sie möchten, dass entlang zu folgen, auch wie wir dies tun, sind Sie recht herzlich willkommen auf. Ich werde dies zu klicken und ziehen erste, "wenn grüne Fahne geklickt haben." Und dann werde ich es einfach fallen zu lassen etwa auf der Spitze meiner leeren Schiefer. 

Und was ist schön, über Scratch ist, dass dieses Puzzle-Stück, wenn mit anderen Puzzle verzahnt Stücke, wird buchstäblich zu tun was diese Puzzleteile sagen zu tun. So zum Beispiel, Scratch ist richtig jetzt in der Mitte seiner Welt. Ich gehe voran gehen und wählen jetzt, sagen wir mal, die Motion Kategorie, wenn Sie möchten, dass das zu tun same-- Bewegung Kategorie. Und jetzt merke ich, eine ganze haben Haufen Puzzleteile hier dass, wieder, eine Art zu tun, was sie sagen. Und ich werde weitermachen und ziehen Drop die Bewegung Block rechts hier. 

Und feststellen, dass, sobald Sie bekommen nah an der Unterseite der "grünen Flagge geklickt "Taste, Ankündigung wie eine weiße Linie erscheint, als ob es fast magnetisch, sie will, dorthin zu gehen. gehen Lassen Sie einfach, und es wird Snap zusammen und passen Sie die Formen. Und jetzt können Sie vielleicht fast erraten, wo wir mit diesem fahren. 

Wenn man sich die Scratch Bühne aussehen hier und schauen nach oben davon, Sie werden ein rotes Licht sehen, ein Stop-Schild und eine grüne Fahne. Und ich werde voran gehen und beobachte meine screen-- nur für einen Moment, wenn man könnte. Ich werde das zu klicken grüne Fahne gerade jetzt, und er bewegt, was 10 Stufen zu sein scheint oder 10 Pixel, 10 Punkte, auf dem Bildschirm. 

Und so nicht so aufregend, aber lassen Sie mich vorschlagen ohne auch nur diese Lehre, nur mit der eigenen Ihre eigene intuition-- let mich schlagen vor, dass Sie herausfinden, wie man machen Scratch zu Fuß rechts von der Bühne. Habe ihn Weg für die rechte Seite machen von der Bildschirm, den ganzen Weg nach rechts. Lassen Sie mich Ihnen einen Moment oder so damit zu ringen. Vielleicht möchten Sie einen Blick zu nehmen in anderen Kategorien von Blöcken. Gut. Also nur zu rekapitulieren, wenn wir die grüne Fahne geklickt hier und bewegen 10 Schritten wird die nur Anweisung, jedes Mal, wenn ich klicken Sie auf die grüne Fahne, was passiert? Nun, das läuft mein Programm. So konnte ich dies tun vielleicht 10 mal manuell, aber das fühlt sich ein wenig Bit hackish, so zu sprechen, wobei ich bin nicht wirklich Lösung des Problems. Ich versuche nur, wieder und wieder und wieder und wieder bis ich irgendwie aus Versehen erreichen die Richtlinie dass ich früher gesetzt zu erreichen werden. 

Aber wir wissen aus unserer Pseudo-Code früher, dass es dieser Begriff in der Programmierung von looping, etwas zu tun, wieder und wieder. Und so sah ich, dass ein paar von euch erreicht zu welchem ​​Puzzlestück? Wiederhole bis. So konnten wir etwas tun wie oft wiederholen, bis. Und was haben Sie wiederholen, bis sich genau? 

OK. Und lassen Sie mich mit einem gehen, das ist etwas einfacher für einen Moment. Lassen Sie mich gehen Sie vor und tun dies. Beachten Sie, dass, wie Sie haben können unter Kontrolle entdeckt, gibt es diese Wiederholungsblock, der sieht nicht wie es ist so groß. Es gibt nicht viel Raum in zwischen diesen beiden gelben Linien. Aber wie einige von euch vielleicht haben bemerkt, wenn Sie per Drag & Drop, feststellen, wie es wächst die Form zu füllen. 

Und Sie können sogar noch mehr stopfen. Es wird einfach weiter wachsen, wenn Sie ziehen und schweben über sie. Und ich weiß nicht, was ist am besten hier, also lassen mir mindestens fünf Mal wiederholen, für Beispiel, und dann auf die Bühne zurück und klicken Sie auf die grüne Fahne. Und jetzt bemerken, es ist nicht ganz da. 

Nun, einige von Ihnen vorgeschlagen, wie Victoria gerade haben, 10-mal wiederholen. Und dass in der Regel tut erhalten ihn den ganzen Weg, aber würde nicht ein robuster sein Art und Weise als willkürlich herauszufinden wie viele Züge zu machen? Was könnte eine bessere Block sein als Wiederholung sein 10-mal? 

Ja, also warum nicht etwas für immer? Und lassen Sie mich jetzt dieses Puzzle-Stück bewegen im Inneren gibt und werde diese eine befreien. Beachten Sie jetzt, egal wo Scratch beginnt, geht er an den Rand. Und zum Glück MIT, wer macht Scratch, nur macht, dass er sicher nie vollständig verschwindet. Sie können jederzeit mit dem Schwanz zu greifen. 

Und nur intuitiv, warum behält er bewegte? Was geht hier vor sich? Er scheint stehen geblieben zu sein, aber dann, wenn ich abholen und ziehen er hält wollen dorthin gehen. Warum das? Wahrlich, ist ein Computer buchstäblich gehen zu tun, was Sie sagen, es zu tun. Also, wenn Sie es gesagt, früher tun die folgende Sache für immer, bewegen 10 Stufen, es geht zu halten zu gehen und gehen bis ich traf den roten Stoppschild und beenden Sie das Programm zusammen. 

Also selbst wenn Sie nicht taten dies zu tun, wie könnte ich machen Scratch schneller bewegen über den Bildschirm? Weitere Schritte, nicht wahr? So anstelle von 10 zu tun zu einer Zeit, zu tun, warum nicht wir gehen Sie vor und ändern Sie es zu-- was würden Sie propose-- 50? So, jetzt werde ich das Grün zu klicken Flagge, und in der Tat, er geht wirklich schnell. 

Und das ist natürlich nur eine Manifestation der Animation. Was ist Animation? Es zeigt Ihnen nur den Menschen ein ganze Reihe von Standbildern wirklich, wirklich, wirklich schnell. Und so, wenn wir nur sagen, ihm mehr Schritte zu bewegen, wir haben nur die Wirkung sein, Veränderung, wo er auf dem Bildschirm umso schneller je Zeiteinheit. 

Nun ist die nächste Herausforderung, die ich vorgeschlagen war ihm die Kante abprallen haben. Und ohne zu wissen, was Puzzle Stücke exist-- weil es ist in Ordnung wenn Sie nicht bekommen, um die Stufe des challenge-- was wollen Sie intuitiv zu tun? Wie würden wir ihn haben wieder auf die Beine und her, zwischen dem linken und rechten? 

Ja. Wir brauchen also eine Art der Zustand, und wir scheinen conditionals zu haben, so zu sprechen, unter der Kategorie Steuerung. Welche dieser Blöcke wollen wir wahrscheinlich? Ja, vielleicht "wenn, dann". So fest, dass unter den gelben Blöcke Wir haben es hier, da dieses "wenn" ist oder das "if, else" -Block das wird ermöglichen es uns, eine Entscheidung zu treffen, dies zu tun oder das zu tun. Und Sie können sie sogar Nest mehrere Dinge zu tun. Oder wenn Sie noch nicht hier noch gegangen, gehen Sie vor, um die Sensing Kategorie und- mal sehen, ob es hier ist. 

Also, was Block könnte hier hilfreich sein zu erkennen, ob er von der Bühne ist? Ja, feststellen, dass einige dieser Blöcke kann parametrisiert, sozusagen. Sie können Art besonders angefertigt werden, nicht im Gegensatz zu HTML gestern mit Attributen, wo Art diese Attribute das Verhalten eines Tags anpassen. Ebenso hier, kann ich diese berührend greifen Blocks und ändern und stellen die Frage, berühren Sie die Maus Zeiger wie der Cursor oder berühren Sie den Rand? 

Also lassen Sie mich gehen und tun dies. Ich werde für einen Moment, um zu verkleinern. Lassen Sie mich dieses Puzzleteil greifen hier, dieses Puzzleteil dieses, und ich werde durcheinander sie sich für einen kurzen Moment. Ich werde dies zu bewegen, ändern, um dies zu berührenden Kante, und ich werde Bewegung dies tun. Also hier sind einige Zutaten. Ich glaube, ich habe alles, was ich will. 

Würde jemand vorschlagen, wie ich verbinden können diese oben vielleicht nach unten Um das Problem zu lösen, mit Scratch Schritt nach rechts und nach links zu von links nach rechts, die jeweils nach links Zeit Prellen direkt an der Wand? Was soll ich tun? Welcher Block sollte ich die Verbindung "Wenn grüne Fahne geklickt zuerst"? 

OK, also lassen Sie uns mit dem Start "für immer." Was geht im Inneren als nächstes? Jemand anderes. OK, bewegen Schritte. Gut. Dann was? Also dann die if. Und bemerken, auch wenn es aussieht zusammen dicht eingeklemmt, es wird nur zu füllen wachsen. Es springt nur in wo ich es will. 

Und was habe ich zwischen die, wenn und dann? Wahrscheinlich "Kante, wenn zu berühren." Und beachten Sie, wieder, es ist zu groß dafür, aber es wird zu füllen wachsen. Und dann um 15 Grad drehen? Wie viel Grad? Ja, so 180 drehen sich mich den ganzen Weg um. Also mal sehen, ob ich das richtig verstanden habe. Lassen Sie mich verkleinern. 

Lassen Sie mich Scratch oben ziehen. Er ist also ein wenig verzerrt jetzt, aber das ist in Ordnung. Wie kann ich ihn einfach zurück? Ich werde etwas zu betrügen. Also habe ich das Hinzufügen eines weiteren Block, um nur klar sein. Ich will ihn um 90 Grad zu zeigen nach rechts standardmäßig also werde ich nur ihm zu sagen, dass programmatisch zu tun. Und es geht los. Wir scheinen es getan zu haben. Es ist ein wenig seltsam, weil er zu Fuß den Kopf. Nennen wir, dass ein Bug. Das ist ein Fehler. Ein Fehler ist ein Fehler in einem Programm ein logische Fehler, die ich, der Mensch, gemacht. Warum geht er den Kopf? Hat MIT vermasseln oder ich? 

Ja, ich meine, es ist nicht der MIT Fehler. Sie gaben mir ein Puzzlestück das sagt eine bestimmte Anzahl von Grad drehen. Und bei Victoria Vorschlag, Ich bin Drehen um 180 Grad, Das ist die richtige Intuition. Aber Drehen um 180 Grad wahrsten Sinne des Wortes Mittel um 180 Grad gedreht, und das ist nicht wirklich was ich will, offenbar. Da zumindest ist er in Diese zweidimensionale Welt, so Wende wirklich geht Flip ihm den Kopf. 

Ich möchte wohl, was Block zu verwenden, stattdessen auf das, was Sie hier sehen? Wie können wir dieses Problem beheben? Ja, und so konnten wir zeigen In die andere Richtung. Und eigentlich auch das ist nicht genug sein würde, weil wir es können nur schwer Code zu zeigen links oder rechts. 

Sie wissen, was wir tun könnten? Es sieht aus wie wir eine haben Bequemlichkeit Block hier. Wenn ich in vergrößern, sehen etwas, das wir gerne hier? So sieht es aus wie MIT eine hat Abstraktion in hier gebaut. Dieser Block scheint äquivalent zu sein auf die anderen Blöcke, Plural? 

Dieser Block scheint äquivalent zu sein dieser ganze Trio von Blöcken dass wir hier haben. So stellt sich heraus kann ich meine vereinfachen Programm durch all das loszuwerden und setzen diese einfach hier. Und jetzt ist er immer noch ein wenig Buggy, und das ist jetzt in Ordnung. Wir lassen das sein. Aber mein Programm ist auch einfacher und auch dies wäre Vertreter eines Ziels in programming-- ist in idealer Weise Ihren Code machen, wie einfach, so kompakt wie möglich ist, während immer noch zu sein als lesbar wie möglich. Sie wollen es nicht so prägnant zu machen dass es schwer zu verstehen. 

Aber merke ich ersetzt habe drei Blöcke mit einem, und das ist wohl eine gute Sache. Ich habe den Begriff wegabstrahiert zu überprüfen, ob Sie am Rande mit nur einem Block. Jetzt können wir Spaß mit diesem haben, in der Tat. Dies fügt nicht so viel geistigen Wert, sondern spielerisch Wert. Ich gehe voran gehen und greifen diesen Sound hier. Also lassen Sie mich los, und lassen Sie mich stoppen Sie das Programm für einen Moment. Ich werde die folgende aufnehmen, den Zugriff auf das Mikrofon. 

Auf geht's. Autsch. Lassen Sie uns versuchen schon wieder. Auf geht's. OK, ich nahm die falsche Sache. Auf geht's. Autsch. Autsch. Gut. Jetzt muss ich davon loszuwerden. Gut. 

So, jetzt habe ich eine Aufnahme von nur "autsch." So, jetzt werde ich gehen vor und nennen das "Aua." Ich gehe zurück zu gehen meine Skripte, und jetzt Hinweis Es ist dieser Block die aufgerufen wird, Ton abspielen "Miau" oder spielen sound "autsch." Ich werde dies zu ziehen, und wo sollte ich das für komische Wirkung setzen? Ja, so jetzt ist es Art von Buggy, denn jetzt diese BLOCK-- feststellen, wie diese ", wenn am Rand, Bounce "ist eine Art selbstständig. Also muss ich dies zu beheben. Lassen Sie mich gehen Sie vor und tun dies. Lassen Sie mich dies loszuwerden und gehen Sie zurück zu unserer ursprünglichen, bewusster Funktionalität. So ", wenn Rand zu berühren, dann" Ich möchte, zu drehen, wie Victoria vorgeschlagen, 180 Grad. Und ich will spielen der Klang "autsch" da? 

Ja, bemerken es draußen dass gelben Block. Also auch dies wäre ein Fehler, aber ich habe es bemerkt. So, hier werde ich es nach oben ziehen, und Mitteilung jetzt ist es in der "if". So ist das "wenn" ist diese Art von wie armförmigen Blot das wird nur zu tun, was in ihm ist. So, jetzt, wenn ich Verkleinern bei die Gefahr von annoying-- 

COMPUTER: Aua, aua, aua. 

DAVID MALAN: Und es gehen wird nur für immer. Jetzt nur noch die Dinge beschleunigen hier, lassen Sie mich gehen Sie vor und öffnen, Lassen Sie uns sagen-- mich einige gehen lassen meiner eigenen Sachen aus der Klasse. Und lassen Sie mich öffnen, lassen Sie uns sagen, diese ein von einem unserer Lehre Gefährten gemacht vor ein paar Jahren. So einige von euch vielleicht erinnern Dieses Spiel von gestern, und es ist tatsächlich bemerkenswert. Auch wenn wir getan haben, die einfachste jetzt von Programmen, lassen Sie uns überlegen, was diese tatsächlich aussieht. Lassen Sie mich spielen getroffen. 

Also in diesem Spiel haben wir ein Frosch, und mit den Pfeil keys-- er nimmt größere Schritte als ich remember-- Ich habe die Kontrolle über diesen Frosch. Und das Ziel ist, über das zu bekommen beschäftigt Straße, ohne in die Autos laufen. Und lassen Sie uns see--, wenn ich hier steigen, ich warten müssen, für ein Protokoll zu blättern durch. Das fühlt sich an wie ein Bug. Dies ist eine Art eines Fehlers. Gut. Ich bin auf das hier, dort, und Sie dann halten , bis Sie alle bekommen die Frösche zu den Lilienauflagen. Nun könnte so aussehen umso komplexer, aber lassen Sie uns versuchen zu brechen diese nach unten geistig und verbal in seine Komponentenblöcke. So gibt es wahrscheinlich ein Rätsel Stück, das wir noch nicht gesehen haben aber das ist die Reaktion auf Tastatureingaben, um die Dinge traf ich auf der Tastatur. 

So gibt es wahrscheinlich eine Art von Block, der sagt, wenn Schlüssel gleich hoch, dann tun Sie etwas mit Scratch-- verschieben Sie es vielleicht 10 Schritte auf diese Weise. Wenn nach unten gedrückt wird, bewegen sich 10 Stufen auf diese Weise, oder linke Taste, bewegen sich 10 Stufen auf diese Weise, 10 Schritte, dass. Ich habe gedreht deutlich die Katze in einen Frosch. Also das ist genau dort, wo die Kostüm, als Scratch Anrufe es-- wir gerade importiert ein Bild des Frosches. 

Aber was sonst geschieht? Welche anderen Zeilen Code, was andere Puzzleteile tat Blake, unsere Lehre Kerl, Verwenden Sie in diesem Programm, offenbar? Was macht alles move-- was Programmierung konstruieren? 

Bewegung, sure-- so die Block verschieben, sicher. Und was ist das Zug-Block innerhalb von, wahrscheinlich? Ja, eine Art Schleife, vielleicht ein für immer blockieren, vielleicht eine Wiederholung BLOCK-- wiederholen, bis Block. Und das ist es, was die Protokolle machen und die Lilienauflagen und alles andere bewegen vor und zurück. Es passiert einfach endlos. 

Warum sind einige der Autos bewegt sich schneller als die anderen? Was ist anders an diesen Programmen? Ja, wahrscheinlich einige von ihnen nehmen mehr Stufen auf einmal und einige von ihnen weniger Schritte auf einmal. Und die optische Wirkung ist schnell im Vergleich zu langsam. 

Was denken Sie, ist passiert? Als ich meinen Frosch bekam den ganzen Weg über die Straße und den Fluss auf der Lilienauflage, etwas Bemerkenswert ist passiert. Was ist passiert, sobald ich das getan? Es hielt an. Das Frosch gestoppt und Ich bekam einen zweiten Frosch. Also, was Konstrukt muss sein verwendet es, was Funktion? 

Ja, so gibt es eine Art von "If" Bedingung dort oben auch. Und es stellt sich out-- wir nicht sehen this-- aber es gibt andere Blöcke in dort, dass wenn man sagen kann, berühren eine andere Sache, auf dem Bildschirm, wenn Sie die Seerosenblatt sind zu berühren, "dann." Und dann, wenn wir machen die zweite Frosch erscheinen. Also auch wenn dieses Spiel ist sicher sehr veraltet, auch wenn auf den ersten Blick es gibt so viel los on-- und Blake nicht das in zwei Minuten Peitsche, es nahm ihn wahrscheinlich mehrere Stunden um dieses Spiel zu erstellen basierend auf seinem Gedächtnis oder Videos des vergangenen Jahres die Version davon. Aber all diese kleinen Dinge geht auf dem Bildschirm in Isolation lässt sich auf diese sehr einfach constructs-- Bewegungen oder Aussagen wie wir haben diskutiert, Loops und Bedingungen, und das ist es. Es gibt ein paar andere ausgefallener Funktionen. Einige von ihnen sind rein ästhetischen oder akustisch, wie die Geräusche, die ich mit nur gespielt. Aber in den meisten Fällen, Sie haben in dieser Sprache, Scratch, alle grundlegenden Bausteine, dass Sie haben in C, Java, JavaScript, PHP, Ruby, Python, und jede Anzahl von anderen Sprachen. Haben Sie Fragen zu Scratch? Gut. So werden wir nicht in tiefer Kratzer tauchen, obwohl sind Sie an diesem Wochenende willkommen, besonders wenn Sie Kinder haben, oder Nichten und Neffen und solche, sie Scratch einzuführen. Es ist eigentlich eine wunderbar spielerische Umwelt mit, wie die Autoren sagen, sehr hohe Decken. Auch wenn wir begannen mit sehr Low-Level-Details, Sie können wirklich tun ziemlich viel mit sich, und dies ist vielleicht eine Demonstration genau das. 

Aber lassen Sie uns den Übergang jetzt zu etwas mehr anspruchsvolle Probleme, wenn man so will, bekannt als "Suche" und "Sortierung" im Allgemeinen. Wir hatten dieses Telefonbuch earlier-- hier ein anderer nur für discussion-- dass wir waren in der Lage zu suchen effizienter, weil einer wesentlichen Annahme. Und nur klar zu sein, was Annahme war ich machen bei der Suche durch dieses Telefonbuch? Dass Mike Smith war in das Telefonbuch, obwohl ich wäre in der Lage zu handhaben das Szenario ohne ihn da, wenn ich gerade aufgehört zu früh. Das Buch ist alphabetisch. Und das ist ein sehr großzügiges Annahme, denn das bedeutet someone-- Ich bin ein bisschen von Kurvenschneiden, wie ich bin schneller, weil jemand sonst tat für mich eine Menge harter Arbeit. 

Aber was, wenn das Telefon Buch wurden unsortiert? Vielleicht Verizon bekam faul, warf nur alle Namen und Nummern drin vielleicht in der Reihenfolge, in der sie haben sich für Telefon-Service. Und wie lange dauert es mir jemanden wie Mike Smith zu finden? 1000 Seite Telefon book--, wie viele Seiten muss ich schauen Sie durch? 

Alle von ihnen. Sie sind eine Art von Glück. Sie müssen buchstäblich an jeder Blick Seite, wenn das Telefonbuch gerade ist zufällig geordnet. Sie könnten mit etwas Glück und Mike finden auf der ersten Seite, weil er war der erste Kunde Telefon-Service zu bestellen. Aber er könnte die letzte gewesen, auch. 

So zufälliger Reihenfolge ist nicht gut. Also angenommen, wir haben das zu sortieren Telefonbuch oder im allgemeinen Sortierdaten dass wir gegeben habe. Wie können wir das machen? 

Nun, lassen Sie mich nur versuchen, ein einfaches Beispiel hier. Lassen Sie mich gehen Sie vor und werfen ein paar Zahlen auf dem Brett. Nehmen wir an, die Zahlen, die wir haben sind, lassen Sie uns sagen, vier, zwei, eins und drei. Und Ben, sortieren Sie diese Zahlen für uns. 

OK gut. Wie hast du das gemacht? Gut. So beginnen Sie mit dem kleinsten Wert und die höchste, und das ist wirklich eine gute Intuition. Und erkennen, dass wir Menschen sind eigentlich ziemlich gut bei der Lösung von Problemen wie diese, zumindest wenn die Daten relativ klein ist. Sobald Sie Hunderte haben starten aus Zahlen, Tausende von Zahlen, Millionen von Zahlen, Ben wahrscheinlich konnte es nicht tun recht schnell, unter der Annahme, dass es Lücken in den Zahlen. Ziemlich einfach zu einer Million zu zählen ansonsten aufwendig nur Zeit. 

So ist der Algorithmus es klingt wie Ben gerade jetzt verwendet war für die kleinste Nummer suchen. Also auch wenn wir Menschen nehmen in einer Vielzahl von Informationen visuell, ein Computer ist eigentlich ein wenig begrenzt. Der Computer kann nur Blick auf ein Byte zu einem Zeitpunkt, oder vielleicht vier Bytes auf Zeit-- in diesen Tagen vielleicht 8 Bytes auf Zeit-- aber eine sehr kleine Zahl von Bytes zu einem gegebenen Zeitpunkt. 

Also da wir wirklich haben vier separate Werte hier-- und Sie können von Ben denken, wie mit Scheuklappen auf, wenn er einen Computer so waren dass er kann nichts anderes sehen als eine Nummer in einem Zeit-- so werden wir im Allgemeinen annehmen, wie in Englisch, wir werden von rechts nach links zu lesen. So ist die erste Zahl Ben wahrscheinlich angesehen an war vier und dann sehr schnell erkannte, dass ein ziemlich großer ist number-- lassen Sie mich halten suchen. 

Es gibt zwei. Warte eine Minute. Zwei kleiner als vier. Ich werde zu erinnern. Zwei ist jetzt das kleinste. Nun one-- das ist noch besser. Das ist sogar noch kleiner. Ich werde über zwei zu vergessen und nur ein erinnere mich jetzt. 

Und konnte er suchen stoppen? Nun, er könnte auf der Grundlage Die Informationen in diesem, aber er würde besser Suche der Rest der Liste. Denn was ist, wenn Null waren in der Liste? Was ist, wenn negative in der Liste waren? Er weiß nur, dass seine Antwort richtig ist, wenn er erschöpfend überprüft die gesamte Liste. Also schauen wir uns den Rest davon. Three-- das war eine Verschwendung von Zeit. Haben Sie Pech, aber ich war noch richtig, dies zu tun. Und so jetzt ist er vermutlich die kleinste Zahl, ausgewählt und legte es erst am Anfang der Liste, wie ich hier finden. Nun, was hast du als nächstes, obwohl Sie dachte nicht daran, es fast in diesem Umfang? Wiederholen Sie den Vorgang, so eine Art Schleife. Es gibt eine bekannte Idee. Hier ist also vier. Das ist derzeit der kleinste. Das ist ein Kandidat. Nicht länger. Jetzt habe ich zwei gesehen. Das ist der nächste kleinste Element. Three-- das ist nicht kleiner, so Ben kann nun die beiden auszureißen. 

Und jetzt wiederholen wir den Prozess und natürlich drei wird nächstes herausgezogen. Wiederholen Sie den Vorgang. Vier wird herausgezogen. Und jetzt sind wir aus Zahlen, so muss die Liste sortiert werden. 

Und in der Tat ist dies ein formaler Algorithmus. Ein Informatiker würde nennen diese "Auswahl sortieren" die Idee ist, sortieren ein Liste iteratively-- wieder und immer wieder die Auswahl die kleinste Zahl. Und was ist das über es nett ist, es ist nur so verdammt intuitiv. Es ist so einfach. Und Sie können das gleiche wiederholen Betrieb wieder und wieder. Es ist einfach. 

In diesem Fall war es schnell, aber wie lange dauert es eigentlich? Lassen Sie uns machen es scheinen, und fühle mich ein wenig langweiliger. So eins, zwei, drei, vier, fünf sechs, sieben, acht, neun, 10, 11, 12, 13, 14, 15, 16-- willkürliche Zahl. Ich wollte nur mehr diese Zeit als nur die vier. Also, wenn ich habe eine ganze bekam Reihe von Zahlen now-- es nicht einmal eine Rolle, was sie sind-- wir darüber nachdenken, was diese Algorithmus ist wirklich wie. 

Angenommen, es gibt dort Zahlen. Auch hier spielt es keine Rolle, was sie sind, aber sie sind zufällig. Ich bewerbe mich Ben-Algorithmus. Ich brauche die kleinste Nummer auszuwählen. Was mache ich? Und ich werde körperlich tun sie es diesmal zu handeln. Suchen, suchen, suchen, suchen, suchen. Erst durch die Zeit, die ich bekommen das Ende der Liste können Ich weiß, das kleinste Zahl war zwei diesmal. Man ist nicht in der Liste. Also habe ich zwei zurückgewiesen. 

Was mache ich als nächstes? Suchen, suchen, suchen, suchen. Nun fand ich die Nummer sieben, weil es gibt Lücken in diesen numbers-- sondern nur willkürlich. Gut. So, jetzt kann ich sieben niedergeschlagen. Suchen Sie suchen, suchen. 

Jetzt gehe davon aus I, natürlich, dass Ben nicht haben extra RAM, extra Speicher, denn, natürlich, Ich freue mich auf die gleiche Zahl. Sicherlich hätte ich in Erinnerung alle diese Zahlen, und das ist absolut wahr. Aber wenn Ben alles erinnert der Zahlen, die er gesehen hat, er hat sich nicht wirklich gemacht wesentliche Fortschritte weil er bereits die Fähigkeit zur Suche durch die Zahlen auf dem Brett. Erinnern an alle der Zahlen nicht hilft, denn er kann immer noch als ein Computer schauen nur auf, wir haben gesagt, eine Nummer zu einem Zeitpunkt. Also gibt es keine Art von Cheat dort, dass Sie nutzen können. 

So in Wirklichkeit, wie ich halten Sie die Liste der Suche, Ich habe buchstäblich nur weitermachen hin und her durch sie und zupft aus der nächste kleinste Zahl. Und wie Sie können Art schließen von meinem dummen Bewegungen, dies wird nur sehr sehr schnell langweilig, und ich scheinen zu gehen zurück und her, hin und her ziemlich viel. Nun, fair zu sein, ich habe nicht zu gehen ganz so, na ja, lassen Sie uns see-- fair zu sein, Ich muss nicht ganz gehen so viele Schritte jedes Mal. Denn natürlich, wie ich Wählen Sie Nummern aus der Liste, die verbleibende Liste wird kürzer. 

Und so lassen Sie uns darüber nachdenken, wie viele Schritte ich bin eigentlich durch jedes Mal latschen. In der ersten Situation wir hatten 16 Zahlen, und so maximally-- lassen Sie uns einfach tun dies für einen discussion-- Ich hatte bis 16 zu sehen Zahlen die kleinste zu finden. Aber einmal gezupft ich aus die kleinste Zahl, wie lange war die restliche Liste, natürlich? Nur 15. So, wie viele Zahlen tat Ben oder ich habe um durch das zweite Mal zu suchen? 15, nur zu gehen und die kleinste finden. Aber jetzt, natürlich, die Liste ist, Auch kleiner, als es vorher war. So, wie viele Schritte habe ich haben die nächste Zeit in Anspruch nehmen? 14 und dann 13 und dann 12 plus Punkt, Punkt, Punkt, bis ich mit nur einem links bin. So, jetzt ein Informatiker würde fragen, na ja, was alles gleich macht das? Es entspricht tatsächlich einige konkrete Eine Zahl, die wir könnten sicher arithmetisch zu tun, aber wir wollen reden über die Effizienz der Algorithmen ein wenig mehr formelhaft, unabhängig davon, wie lange die Liste ist. 

Und so wissen Sie was? Dies ist 16, aber wie ich schon sagte, Nennen wir nur die Größe des Problems n, wobei n eine Zahl ist. Vielleicht ist es 16, vielleicht ist es drei, vielleicht ist es eine Million. Ich weiß es nicht. Ich interessiere mich nicht. Was ich wirklich will, ist Eine Formel, die ich kann, Mit diesem Algorithmus zu vergleichen gegen andere Algorithmen dass jemand behaupten besser oder schlechter sind. 

So stellt sich heraus, und ich nur weiß, dass dies von der Grundschule, dass dies tatsächlich funktioniert, um die gleiche etwas wie n über n plus eins mehr als zwei. Und dies geschieht auf gleich, von Natürlich n Quadrat plus n mehr als zwei. Also, wenn ich wollte eine Formel für wie viele Schritte Beteiligt waren überhaupt in der Suche dieser Zahlen immer wieder und immer wieder, würde ich sagen, es ist n Quadrat plus n mehr als zwei. Aber weißt du was? Das sieht einfach unordentlich. Ich will nur wirklich ein allgemeinen Sinn der Dinge. Und Sie erinnern sich vielleicht aus High School, dass es ist der Begriff der höchsten Ordnung Begriff. Welche dieser Bedingungen, die n quadriert, die n oder die Hälfte, hat den größten Einfluss im Laufe der Zeit? Je größer n wird, die dieser Angelegenheiten am meisten? 

Mit anderen Worten, wenn ich stecken in einer Million, n quadriert wird sehr wahrscheinlich zu sein der dominierende Faktor, weil eine Million Mal selbst ist viel größer als plus eine zusätzliche Million. So wissen Sie was? Dies ist so ein verdammt groß Anzahl, wenn Sie eine Zahl-Platz. Dies ist nicht wirklich wichtig. Wir gehen nur Kreuz, und vergessen Sie es. Und so würde ein Informatiker sagen dass die Effizienz dieses Algorithmus in der Größenordnung von n squared-- Ich meine wirklich eine Annäherung. Es ist eine Art von ungefähr n im Quadrat. Im Laufe der Zeit ist, desto größer und größer n wird, diese ist eine gute Schätzung für das, was die Effizienz oder mangelnde Effizienz tatsächlich dieses Algorithmus ist. Und ich ableiten, dass, natürlich, von tatsächlich die Mathematik zu tun. Aber jetzt bin ich nur winken meine Hände, weil ich gerade ein allgemeines Gefühl dieses Algorithmus soll. 

Also mit der gleichen Logik, inzwischen Lassen Sie uns einen anderen Algorithmus betrachten wir sahen bereits at-- lineare Suche. Wenn ich war auf der Suche für das Telefon book-- Sortierung es nicht, auf der Suche über das Telefon book-- wir immer wieder gesagt, dass es 1.000 Schritte oder 500 Stufen. Aber lassen wir das verallgemeinern. Wenn es gibt, n-Seiten in das Telefonbuch, was ist die Laufzeit oder die Effizienz der linearen Suche? Es ist in der Größenordnung von wie viele Schritte zu finden Mike Smith durch lineare Suche, die erste Algorithmus oder auch der zweite? 

Im schlimmsten Fall, Mike ist am Ende des Buches. Also, wenn das Telefonbuch hat 1.000 Seiten, wir das letzte Mal, im schlimmsten Fall, es könnte dauern ungefähr, wie viele Seiten Mike zu finden? Wie 1000. Es ist eine obere Schranke. Es ist eine denkbar schlechteste Situation. Aber noch einmal, wir ziehen weg von Zahlen wie 1000 jetzt. Es ist nur n. 

Was ist also die logische Schlussfolgerung? Die Suche nach Mike in einem Telefon Buch, das n-Seiten hat nehmen könnte, im schlimmsten Fall, wie viele Schritte in der Größenordnung von n? Und in der Tat ein Computer Wissenschaftler sagen würde daß die Laufzeit oder die Leistung oder der Wirkungsgrad oder Ineffizienz eines Algorithmus wie eine lineare Suche ist in der Größenordnung von n. Und wir können das gleiche gelten Logik der etwas aus der Kreuzung wie ich gerade in die zweite Algorithmus hatten wir mit dem Telefonbuch, wo gingen wir zwei Seiten auf einmal. 

So 1000 Seite Telefonbuch könnte nehmen uns 500 Seite dreht, plus eins wenn wir doppelt so ein wenig zurück. Also, wenn ein Telefonbuch n Seiten hat, aber wir tun zwei Seiten zu einer Zeit, das ist ungefähr das, was? N über zwei, so dass ist wie n mehr als zwei. Aber ich habe den Anspruch ein Moment vor, dass n über two-- das ist irgendwie der gleiche wie nur n. Es ist nur ein konstanter Faktor, Informatiker sagen würde. Lassen Sie uns nur konzentrieren sich auf die Variablen, really-- die größten Variablen in der Gleichung. 

So lineare Suche, ob man getan Seite zu einem Zeitpunkt oder zwei Seiten zu einer Zeit, Art ist im Grunde das gleiche. Es ist immer noch in der Größenordnung von n. Aber ich behauptete, mit meinem Bild früher dass der dritte Algorithmus war nicht linear. Es war nicht eine gerade Linie. Es war diese gekrümmte Linie, und die algebraischen Formel da war was? Protokoll der n-- so log Basis zwei von n. Und wir müssen auch nicht gehen in viele Details über Logarithmen heute, aber die meisten Informatiker würde nicht sagen Sie selbst, was die Basis ist. Denn es ist alles nur konstante Faktoren, so zu sprechen, nur leichte numerische Unterschiede. Und so wäre dies ein sehr häufig Weg für besonders formale Computer Wissenschaftler an einem Brett oder Programmierer auf eine weiße Tafel tatsächlich argumentieren die Algorithmus sie verwenden würden oder was die Effizienz ihres Algorithmus ist. 

Und das ist nicht unbedingt etwas, Sie diskutieren in allen Einzelheiten, aber ein guter Programmierer ist jemand, die hat einen soliden, formalen Hintergrund. Er ist in der Lage zu sprechen Sie in dieser Art und Weise und tatsächlich machen qualitative Argumente warum ein Algorithmus oder ein Stück Software überlegen ist, auf eine andere in irgendeiner Weise. Da konnte man sicher nur eine Person das Programm ausführen und zählen die Anzahl der Sekunden Es dauert ein paar Zahlen zu sortieren, und Sie können einige laufen Person Programm und zählen die Anzahl Sekunden dauert es. Aber das ist eine allgemeinere Art und Weise, Sie können Algorithmen zur Analyse verwenden, wenn man so will, nur auf Papier oder einfach nur verbal. Ohne läuft sogar ohne auch nur zu versuchen Probe-Eingänge, Sie können nur durch sie argumentieren. Und so mit einem Entwickler der Einstellung oder wenn mit ihm oder argumentieren sie dir Art warum ihr Algorithmus, ihr Geheimnis Sauce für die Suche Milliarden von Web-Seiten für Ihre Unternehmen ist besser, diese sie sind die Arten von Argumenten im Idealfall der Lage sein, zu machen sollte. Oder zumindest sind diese die Art von Dingen das würde kommen in der Diskussion, bei dest in einem sehr formalen Diskussion. Gut. Deshalb schlug Ben etwas Auswahl Art genannt. Aber ich werde vorschlagen, dass es andere Möglichkeiten, dies zu tun, zu. Was ich nicht wirklich mochte über Ben-Algorithmus Wandern ist, dass er gehalten wird, oder hat mich gehen, hin und her und hin und her und hin und her. Was ist, wenn stattdessen waren ich tun so etwas wie diese Zahlen hier und ich waren nur mit jedem umgehen Zahl wiederum als ich es gegeben? 

Mit anderen Worten, hier ist meine Liste von Zahlen. Vier, eins, drei, zwei. Und ich werde folgendes tun. Ich werde die Zahlen einfügen wo sie gehören eher als sie einzeln zu einer Zeit auszuwählen. Mit anderen Worten, hier ist die Nummer vier. 

Hier ist meine ursprüngliche Liste. Und ich werde zu halten im Wesentlichen eine neue Liste hier. Das ist also die alte Liste. Dies ist die neue Liste. Ich sehe die Nummer vier erste. Meine neue Liste ist zunächst leer, so ist es trivialerweise der Fall dass vier ist nun sortiert Liste. Ich nehme nur die Nummer, die ich gegeben habe, und ich stelle es in meiner neuen Liste. 

Ist diese neue Liste sortiert? Ja. Es ist dumm, weil es nur ein Element, aber es ist absolut sortiert. Es gibt nichts fehl am Platz. Es ist interessanter, dieser Algorithmus, wenn ich an den nächsten Schritt. 

Jetzt habe ich ein. So ein, natürlich, gehört zu den Anfang oder am Ende dieser neuen Liste? Der Anfang. Also muss ich jetzt einige Arbeit zu tun. Ich habe dabei, einige Freiheiten mit meinem Marker nur um Dinge zeichnen wo ich will, dass sie, aber das ist nicht wirklich in einem Computer genau. Ein Computer, wie wir wissen, hat RAM oder Direktzugriffsspeicher, und das ist ein Byte und ein weiteres Byte und ein weiteres Byte. Und wenn Sie ein Gigabyte RAM, Sie haben eine Milliarde Bytes, aber sie sind physisch an einem Ort. Sie können nicht nur Sachen bewegen indem sie sie auf dem Reißbrett wo immer Sie wollen. Also, wenn meine neue Liste vier Stellen im Speicher, leider die vier ist bereits an der falschen Stelle. 

Also die Nummer einzufügen ein Ich kann es nicht nur hier ziehen. Dieser Speicherplatz existiert nicht. Das wäre Betrug, und ich habe bildhaft für ein paar Minuten zu betrügen Hier. Also wirklich, wenn ich will hier ein zu setzen, Ich muss vorübergehend die vier kopieren und dann setzen die man dort. 

Das ist in Ordnung, das ist richtig, das ist technisch möglich, aber erkennen, das ist zusätzliche Arbeit. Ich habe einfach nicht die Zahl in Stelle zu setzen. Ich musste zuerst ein bewegen Nummer, legte es dann an Ort und Stelle, so verdoppelte ich meine Art von Menge an Arbeit. So sollte man nicht vergessen. 

Aber ich bin jetzt mit diesem Element getan. Jetzt möchte ich die Nummer drei zu greifen. Wo, natürlich, es gehören? Zwischen. Ich kann nicht mehr betrügen und legte sie einfach da, da wieder dieser Speicher ist in physischen Standorten. Also muss ich die vier kopieren und legte die drei hier. Keine große Sache. Es ist nur ein zusätzlicher Schritt again-- fühlt sich sehr preiswert. 

Aber jetzt gehe ich zu den beiden auf. Die beiden, natürlich, gehört hier. Nun beginnen Sie zu sehen, wie die Arbeit anhäufen können. Nun, was soll ich tun? Ja, ich habe die vier bewegen, Ich muss dann die drei zu kopieren, und jetzt kann ich die beiden ein. Und der Fang mit diesem Algorithmus, interessanterweise, das ist angenommen, wir haben eine extreme Fall, in dem es acht lassen Sie uns sagen, sieben, sechs, fünf, vier, drei, zwei, ein. Dies ist in vielen Zusammenhängen, das Worst-Case-Szenario, weil das verflixte Ding buchstäblich nach hinten ist. 

Es ist nicht wirklich beeinflussen Ben-Algorithmus, weil in Bens Auswahl Art, er wird zu halten hin und her durch die Liste. Und weil er immer auf der Suche durch die ganze restliche Liste, es spielt keine Rolle wobei die Elemente sind. Aber in diesem Fall mit meinem Einsetzrichtung approach-- lassen Sie uns dies versuchen. 

So ein, zwei, drei, vier, fünf, sechs, sieben, acht. Eins zwei drei vier, fünf, sechs, sieben, acht. Ich werde die acht zu nehmen, und wo stelle ich es? Nun, am Anfang meiner Liste, denn diese neue Liste sortiert ist. Und ich überqueren Sie es heraus. 

Wo habe ich die sieben? Darn es. Es muss dorthin gehen, so Ich muss etwas tun, das Kopieren. Und jetzt geht die sieben hier. Nun gehe ich auf die sechs auf. Jetzt ist es noch mehr Arbeit. 

Acht hat hier zu gehen. Seven hat hier zu gehen. Nun kann die sechs hier. Jetzt packe ich die fünf. Nun ist die acht muss gehen hier sieben hier zu gehen, sechs hat hier zu gehen, und jetzt die fünf und wiederholen. Und ich bin mir ziemlich viel Bewegen sie sich ständig. 

So am Ende dieses algorithm-- wir werden nennen es Einfügung sort-- tatsächlich hat auch eine Menge Arbeit. Es ist einfach anders Art der Arbeit als Bens. Ben Arbeit hatte mich gehen hin und her die ganze Zeit, Auswahl des nächsten kleinsten Element wieder und wieder. So war es auch dieses sehr visuelle Art von Arbeit. 

Dieser andere Algorithmus, der immer noch correct-- es wird den Job zu bekommen done-- nur ändert sich die Menge an Arbeit. Es sieht aus wie zunächst du bist zu speichern, weil Sie gerade sind wobei jedes Element Umgang vorne ohne alle zu Fuß die Art und Weise durch die Liste wie Ben war. Aber das Problem ist, insbesondere in diesen verrückt Fällen, in denen es nach hinten ist, Sie sind nur eine Art von Verschiebung der harten Arbeit bis müssen Sie Ihre Fehler zu beheben. 

Und so, wenn Sie können sich das vorstellen acht und sieben und sechs und fünf und später vier und drei und zwei ihren Weg durch die Liste zu bewegen, wir haben gerade verändert die Art der Arbeit, die wir tun. Anstatt es auf das Tun Anfang meiner Iteration, Ich tue es nur bei der Ende jeder Iteration. So stellt sich heraus, dass dieser Algorithmus, Auch allgemein als Insertion Sort, ist ebenfalls von n in der Größenordnung quadriert. Es ist eigentlich nicht besser, nicht gar besser. 

Allerdings gibt es einen dritten Ansatz Ich würde uns ermutigen, zu prüfen, was diese. Also meine Liste annehmen, der Einfachheit halber wieder ist vier, eins, drei, two-- nur vier Zahlen. Ben hatte eine gute Intuition, gute menschliche Intuition vor, durch die feste wir die ganze Liste eventually-- Insertionsort. Ich schmeichelte uns zusammen. Aber lassen Sie uns betrachten die einfachste Weg, um diese Liste zu beheben. 

Diese Liste ist nicht sortiert. Warum? In Englisch, erklären, warum Es ist nicht wirklich sortiert. Was bedeutet es, nicht sortiert werden? 

STUDENT: Es ist nicht sequentiell. 

DAVID MALAN: nicht sequentiell. Gib mir ein Beispiel. 

STUDENT: Setzen Sie sie um. 

DAVID MALAN: OK. Geben Sie mir ein konkretes Beispiel. 

STUDENT: aufsteigende Reihenfolge. DAVID MALAN: Nicht aufsteigend sortieren. Genauer gesagt. Ich weiß nicht, was Sie mit aufsteigend. Was ist los mit dir? 

STUDENT: Die kleinste der Zahlen in dem ersten Raum nicht. 

DAVID MALAN: Kleinste Nummer nicht in den ersten Raum. Sei genauer. Ich fange an zu fangen. Wir zählen, aber was ist hier nicht in Ordnung? 

STUDENT: Numerische Folge. DAVID MALAN: Numerische Folge. Jeder Art von Führung es hier-- sehr hohem Niveau. Sag mir einfach, was wörtlich falsch wie ein fünf-jährige Macht. 

STUDENT: plus eins. 

DAVID MALAN: Was ist das? 

STUDENT: plus eins. 

DAVID MALAN: Was meinst du plus eins? Geben Sie mir eine andere fünf Jahre alt. Was ist los, Mama? Was ist los, Dad? Was meinst du damit nicht sortiert ist? 

STUDENT: Es ist nicht der richtige Ort. 

DAVID MALAN: Was ist nicht an der richtigen Stelle? 

STUDENT: Vier. DAVID MALAN: OK, gut. So vier ist nicht, wo es sein sollte. Insbesondere ist dies der richtige? Vier und eine, die erste zwei Zahlen, die ich zu sehen. Ist das richtig? Nein, sie sind nicht in Ordnung, nicht wahr? In der Tat, jetzt denken, zu einem Computer, zu. Es kann nur auf vielleicht aussehen, vielleicht zwei Dinge auf once-- und eigentlich nur eine Sache, zu einer Zeit, aber es kann zumindest Blick auf eine Sache, dann die nächste, was sich direkt daneben. 

So sind diese um? Natürlich nicht. So wissen Sie was? Warum nehmen wir Baby nicht Schritte, um dieses Problem zu beheben Anstelle dieser Phantasie zu tun Algorithmen wie Ben, wo Er ist eine Art der Befestigung durch Schleife durch die Liste anstatt das zu tun, was ich tat, wo Ich habe gerade Art es von festen, wie wir gehen? Lassen Sie uns einfach buchstäblich die brechen Begriff der order-- numerischer Reihenfolge, nennen Sie es, was Sie want-- in diese paarweise Vergleiche. 

Vier und Eins. Ist das die richtige Reihenfolge? Also lassen Sie uns das in Ordnung bringen. Ein und vier, und dann wir werden nur das kopieren. In Ordnung, gut. Ich reparierte eins und vier. Drei und zwei? Nein. Lassen Sie meine Worte meine Finger passen. Vier und drei? 

Es ist nicht in Ordnung, so werde ich zu tun, eins, drei, vier, zwei. OK gut. Jetzt vier und zwei? Wir müssen dieses Problem zu beheben, auch. So eins, drei, zwei, vier. So ist es sortiert? Nein, aber ist es näher an sortiert? 

Es ist, weil wir dieses Problem behoben Fehler, Fest wir diesen Fehler, und wir festgelegt, diesen Fehler. So fixiert wir wohl drei Fehler. immer noch nicht wirklich aussehen sortiert, aber es ist objektiv näher an sortierten weil wir einige dieser Fehler behoben. 

Nun, was mache ich als nächstes? Ich erreichte Art das Ende der Liste. Ich schien behoben haben alle Fehler, aber nein. Da in diesem Fall einige Zahlen könnte sprudelte näher auf andere Zahlen, die aus der Ordnung sind nach wie vor. So wollen wir es wieder tun, und ich werde nur tun es diesmal an ihrem Platz. Ein und drei? Das ist gut. Drei und zwei? Natürlich nicht, also lassen Sie uns das ändern. So zwei, drei. Drei und vier? Und nun lassen Sie uns einfach sein hier besonders pedantisch. Ist es sortiert? Ihr Menschen wissen, dass es sortiert. 

Ich sollte noch einmal versuchen. So Olivia schlägt ich versuche es erneut. Warum? Da ein Computer nicht der Luxus unserer menschlichen Augen von nur einem Blick back-- OK, ich bin fertig. Wie funktioniert der Computer bestimmen dass die Liste wird nun sortiert? Mechanisch. 

Ich sollte gehen durch noch einmal, und nur wenn I nicht machen / zu finden keine Fehler kann ich dann wie auf dem Computer schließen, yep, wir sind gut zu gehen. So eins und zwei, zwei und drei, drei und vier. Jetzt kann ich definitiv sagen, dass dies sortiert, weil ich keine Änderungen vorgenommen. Nun wäre es ein Fehler sein, und nur dumm, wenn ich, der Computer, die gleichen Fragen wieder erwarten verschiedene Antworten. Sollte nicht passieren. 

Und jetzt ist die Liste sortiert. Leider Laufzeit Dieser Algorithmus ist auch n im Quadrat. Warum? Denn Sie haben n Zahlen, und in der schlimmsten Fall müssen Sie n Zahlen bewegen n-mal, weil Sie müssen weitermachen zurück zu überprüfen und möglicherweise zu beheben diese Zahlen. Und wir können eine mehr tun formalen Analyse, auch. 

So ist das alles zu sagen, wir genommen haben drei verschiedene Ansätze, ein von ihnen sofort intuitiv von der Fledermaus von Ben Zu meiner vorgeschlagenen Einfügung Art wie diese wo man Art von den Augen verlieren der Wald für die anfänglich Bäume. Aber dann, wenn Sie einen Schritt zurück, voila, haben wir die Sortier Begriff fixiert. Das ist also, es wagen, sagen, ein niedrigeres Niveau vielleicht als einige dieser anderen Algorithmen, aber lassen Sie uns sehen, ob wir nicht visualisieren diese haft dafür. 

Also das ist ein paar nette Software, dass jemand Verwendung schrieb bunten Bars, das ist, gehen die folgenden für uns zu tun. Jeder dieser Stäbe für eine Zahl. Taller der Balken, desto größer die Anzahl, die kleiner ist die Bar, Je kleiner die Zahl. Also ideal wollen wir eine schöne Pyramide wo es beginnt klein und wird groß, und das würde bedeuten, dass Diese Stäbe werden sortiert. Also werde ich voran gehen und wählen, beispielsweise Ben-Algorithmus first-- Auswahl sortieren. 

Und bemerken, was es tut. Die Art, wie sie sich entschieden haben zu visualisieren diesen Algorithmus ist, dass, wie ich gerade war zu Fuß durch meine Liste, Dieses Programm ist zu Fuß durch seine Liste von Zahlen, in rosa hervorgehoben jeder Zahl, die es betrachten. Und wie sieht es jetzt geschehen? 

Die kleinste Zahl, die I oder Ben plötzlich wird an den Anfang der Liste verschoben. Und merkte sie evict die Zahl, die es gab, und das ist völlig in Ordnung. Ich habe nicht in diesem Maß an Detail. Aber wir müssen zu setzen diese Zahl irgendwo, wir zogen es so nur auf die offene Stelle, die erstellt wurde. Also werde ich dies zu beschleunigen , denn sonst ist es schnell wird sehr mühsam. Animation speed-- dort gehen wir. So, jetzt gleiche Prinzip Ich war die Anwendung, aber Sie kann beginnen, den Algorithmus zu fühlen, wenn Sie wird, oder es ein wenig klarer zu sehen. Und dieser Algorithmus hat den Effekt, das nächste kleinste Element der Auswahl, so dass Sie gehen, um zu starten sehen sie auf der linken Rampe. Und bei jeder Iteration, wie ich vorgeschlagen, es hat ein bisschen weniger Arbeit. Es hat nicht den ganzen Weg zu gehen zurück zum linken Ende der Liste, da es bereits kennt solche sortiert werden. So fühlt es sich ein bisschen wie es ist beschleunigt, obwohl jeder Schritt die gleiche Menge an Zeit. Es gibt nur noch wenige Schritte. Und jetzt können Sie Art von Gefühl, die Algorithmus Reinigung das Ende davon auf, und in der Tat jetzt ist es sortiert. 

So Insertionsort ist alles getan. Ich muss das Array neu zu randomisieren. Und bemerken kann ich nur halten Randomisierung es, und wir bekommen eine Annäherung an der gleiche Ansatz, Insertionsort. Lassen Sie es mich langsam hier unten. Lassen Sie uns beginnen, dass über. Halt. 

Lassen Sie uns vier überspringen. Da gehen wir. Randomize sie Array. Und hier go-- wir Insertionsort. Spielen. Beachten Sie, dass es mit jedem zu tun hat Element es sofort begegnet, aber wenn es gehört in der falsche Ort Bekanntmachung all der Arbeit, die zu geschehen hat. Wir müssen weiter mehr Verschiebung und weitere Elemente, um Platz für den einen wollen wir an Ort und Stelle zu bringen. 

So konzentrieren wir uns auf die linken Ende der Liste nur. Beachten wir haben nicht einmal at-- wir sahen nicht in rosa etwas hervorgehoben auf der rechten Seite. Wir haben es nur mit die Probleme, wie wir gehen, aber wir schaffen eine Menge noch für uns arbeiten. Und so, wenn wir dies beschleunigen jetzt gehen bis zur Fertigstellung, es hat ein anderes Gefühl, es in der Tat. Es ist nur auf der linken Ende konzentriert, aber dabei ein wenig mehr Arbeit als needed-- Art der Glättung Dinge über die Dinge Festsetzung, aber den Umgang schließlich mit jedes Element einzeln nacheinander bis wir gut zu the-- bekommen, wir alle wissen, wie das enden wird, so ist es ein wenig berauschend vielleicht. 

Aber die Liste in der end-- spoiler-- wird sortiert werden. Lassen Sie uns also auf einen letzten Blick. Wir können nicht nur jetzt überspringen. Wir sind fast da. Zwei zu gehen, ein zu gehen. Und voila. Ausgezeichnet. 

So, jetzt lassen Sie uns eine letzte tun, Re-Randomisierung mit Bubble-Sort. Und hier bemerken, vor allem, wenn ich es langsam dies ist nach unten, halten Sie durch Swooping. Beachten Sie aber, es macht nur paarweise comparisons-- Art lokaler Lösungen. Aber sobald wir bekommen das Ende der Liste in rosa, was los ist wieder geschehen zu lassen? Ja, es gehen zu müssen, zu beginnen, weil es nur fest paarweise Fehler. Und das könnte noch andere offenbart haben. Und so, wenn Sie diese nach oben zu beschleunigen, werden Sie sehen, dass, so wie der Name schon sagt, der kleinere elements-- oder vielmehr die größeren elements-- beginnen zu sprudeln an die Spitze, wenn man so will. Und die kleineren Elemente nach links unten zu sprudeln beginnen. Und in der Tat ist diese Art von der visuelle Effekt auch. Und so wird diese am Ende Veredelung in sehr ähnlicher Weise zu. 

Wir müssen nicht wohnen an diesem ein. Lassen Sie mich das jetzt öffnen, auch. Es gibt ein paar andere Sortieralgorithmen in der Welt, von denen einige werden hier erfasst. Und vor allem für Lernende, die nicht notwendigerweise visuell oder mathematisch, wie wir schon haben, können wir auch dies tun hör- wenn wir assoziieren einen Ton mit diesem. Und nur zum Spaß, hier ist ein paar verschiedene Algorithmen, und einer von ihnen insbesondere du bist gehen zu bemerken, wird als "merge sort." 

Es ist eigentlich ein grundlegend besseren Algorithmus, solche, die Art verschmelzen, einer der die, die Sie über zu sehen sind, Quadrat ist nicht Ordnung von n. Es ist in der Größenordnung von n-mal log von n, was tatsächlich kleiner ist, und somit schneller als die anderen drei. Und es gibt ein paar andere albern diejenigen, die wir sehen werden. 

Also hier gehen wir mit einem gewissen Sound. Dies ist Insertionsort, so wieder es handelt nur mit den Elementen wie sie kommen. Dies ist Bubble Sort, so dass es sie paarweise zu einem Zeitpunkt betrachten. Und wieder die größten Elemente sprudeln ganz nach oben. 

Als nächstes Auswahl sortieren. Dies ist Ben-Algorithmus, wo er wieder die Auswahl iterativ der nächste kleinste Element. Und wieder, jetzt können Sie wirklich, dass hören es beschleunigt, sondern nur so weit in wie es tut immer weniger bei jeder Iteration arbeiten. Dies ist die schnellere, fusionieren zu sortieren, die Cluster von Zahlen ist das Sortieren zusammen und kombiniert sie dann. So look-- die linke die Hälfte ist bereits sortiert. 

Jetzt wird es die Sortierung der rechten Hälfte, und Jetzt geht es ihnen zu einem zu kombinieren. Das ist etwas, genannt "Gnome Art." Und Sie können Art sehen, dass es geht hin und her, Festsetzung der Arbeit hier ein wenig und dort, bevor er geht, um neue Arbeit. Und das ist es. Es ist eine andere Art, das ist wirklich nur für akademische Zwecke, "Dumme Art" genannt, was nimmt Ihre Daten, sortiert sie nach dem Zufall, und prüft dann, ob es sortiert wird. Und wenn es nicht ist, ist es neu sortiert sie zufällig, überprüft, ob es sortiert, und wenn nicht, wiederholt. Und in der Theorie, probabilistically Dies wird vollenden, aber nach einer ziemlich viel Zeit. Es ist nicht die effiziente Algorithmen. Also Fragen auf diejenigen insbesondere Algorithmen oder irgendetwas auch da zu tun? 

Nun, lassen Sie uns jetzt necken auseinander, was alle diese Zeilen sind, dass ich habe Zeichnung und was ich nehme an, dass Sie den Computer kann unter der Haube zu tun. Ich würde, dass all diese Zahlen argumentieren Ich halte drawing-- die sie brauchen irgendwo im Speicher gespeichert. Wir werden jetzt die Befreiung von diesem Kerl bekommen, auch. 

So ein Stück Erinnerung in ein computer-- so RAM DIMM was wir suchten nach gestern, Dual Inline Memory module-- sieht wie folgt aus. Und jeder dieser kleinen schwarzen Chips typischerweise eine Anzahl von Bytes. Und dann sind die Gold-Pins wie die Drähte, die es an den Computer anschließen, und die grüne Siliziumplatte ist nur was hält alle zusammen alles. Also, was bedeutet das eigentlich? Wenn ich irgendwie das gleiche Bild zu zeichnen, Lassen Sie uns der Einfachheit halber annehmen, dass dieses DIMM, Dual Inline-Speichermodul, ist ein Gigabyte RAM, ein Gigabyte Speicher, der wie viele Bytes insgesamt ist? Ein Gigabyte ist, wie viele Bytes? Mehr als das. 1124 ist Kilo, 1000. Mega ist Millionen. Giga ist eine Milliarde. 

Liege ich? Können wir sogar das Etikett lesen? Dies ist eigentlich 128 Gigabyte, es ist so mehr. Aber wir werden dies so tun, ist nur ein Gigabyte. Das heißt also, es gibt eine Milliarde Byte Speicher zur Verfügung zu mir oder 8 Milliarden Bits, aber wir gehen in Bezug auf die Bytes jetzt zu reden, voran. 

Also, was das bedeutet, ist dies ein Byte, ist dies ein weiteres Byte, dies ist ein weiteres Byte, und wenn wir wirklich wollten um genau zu sein müssen wir würden ziehen eine Milliarde kleinen Plätzen. Aber was bedeutet das? Nun, lassen Sie mich nur vergrößern in auf diesem Bild. Wenn ich etwas haben, die aussieht nun wie folgt, ist, dass vier Bytes. 

Und so konnte ich hier vier Zahlen setzen. Eins zwei drei vier. Oder ich könnte vier Buchstaben oder Symbole setzen. "Hallo!" gehen könnte genau dort, da jeder der Buchstaben, wir früher diskutiert, könnte vertreten mit acht Bits oder ASCII oder ein Byte. Also mit anderen Worten, können Sie setzen 8 Milliarden Dinge im Inneren dieses einen Stick von Speicher. Nun, was bedeutet es, Sachen zu setzen zurück im Speicher zu sichern, wie dies zu unterstützen? Dies ist, was ein Programmierer ein "Array". nennen würde In einem Computerprogramm, denken Sie nicht, über die zugrunde liegenden Hardware, per se. Sie denken an sich selbst genauso wie mit Zugriff auf insgesamt Milliarde Byte, und Sie können alles wollen Sie mit ihm. Aber der Einfachheit halber es in der Regel sinnvoll Ihr Gedächtnis richtig zu halten nebeneinander wie folgt. Also, wenn ich Zoom auf this-- weil wir sicher nicht gehen eine Milliarde wenig squares-- zu ziehen nehmen wir an, dass dieses Board repräsentiert dass Stick von Speicher jetzt. Und ich werde genauso viele ziehen, wie meine Marker landet mich hier zu geben. Deshalb haben wir jetzt einen Stock der Speicher auf der Platine das hat ein, zwei, drei, vier, fünf, sechs, eins, zwei, drei, vier, fünf, sechs, seven-- so 42 Bytes Speicher auf dem Bildschirm insgesamt. Vielen Dank. Ja, habe meine Arithmetik richtig. So 42 Byte Speicher hier. Also, was bedeutet das eigentlich? Nun, ein Computer-Programmierer würde tatsächlich im Allgemeinen denken Sie an dieses Speichers als adressierbar. Mit anderen Worten, jeder von diesen Stellen im Speicher, in Hardware, hat eine eindeutige Adresse. 

Es ist nicht so komplex wie ein Brattle Square, Cambridge, Mass., 02138. Stattdessen ist es nur eine Zahl. Dies ist Byte-Zahl Null, das ist ein, ist dies zwei dieser drei ist, und dies ist 41. Warte eine Minute. Ich dachte, ich sagte 42 vor einem Augenblick. Ich begann bei Null zu zählen, so das ist eigentlich richtig. wir müssen es jetzt eigentlich gar nicht ziehen als Gitter, und wenn Sie es als ein Gitter ziehen Ich denke, die Dinge tatsächlich bekommen ein wenig irreführend. Was würde ein Programmierer, in seinem eigenen Geist, im Allgemeinen denken Sie an dieses Speicher wie ist wie ein Band, wie einem Stück Abdeckband das geht einfach weiter und weiter für immer oder bis Sie aus dem Speicher ausgeführt werden. So ein häufiger Weg zu zeichnen und man denke nur an Speicher wäre, dass dies Byte null, eins, zwei, drei, und dann Punkt, Punkt, Punkt. Und Sie haben 42 solcher Bytes insgesamt, auch obwohl es physisch könnte in der Tat etwas mehr so ​​sein. 

Also, wenn Sie jetzt denken Sie an Ihre Speicher als diese, so wie ein Band, das ist, was ein Programmierer wieder würde ein Array von Speicher nennen. Und wenn Sie möchten, um tatsächlich speichern etwas in einem Speicher des Computers, Sie speichern Dinge im Allgemeinen tun Rücken an Rücken an Rücken an Rücken. So reden wir seit über Zahlen. Und wenn ich wollte, um Probleme zu lösen wie vier, eins, drei, zwei, obwohl ich gerade Zeichnung nur die Nummern vier, eins, drei, zwei auf dem Board, würde der Computer wirklich haben diese Einrichtung im Speicher. 

Und was wäre neben der zwei in dem Speicher des Computers? Nun, es gibt keine Antwort auf diese Frage. Wir wissen es nicht wirklich. Und so lange, wie die Computer braucht es nicht, es muss nicht, was als nächstes auf die Zahlen macht es Sorge um. Und wenn ich vorhin gesagt, dass ein Computer kann nur zu einer Zeit an einer Adresse sucht, Dies ist eine Art, warum. 

Nicht anders als ein Rekord Spieler und ein Lesekopf in der Lage zu schauen nur auf einem bestimmten Nut in einem physischen Satz der alten Schule zu einer Zeit, ähnlich Ein Computer kann dank seine CPU und ihre Intel-Befehlssatz, unter dessen Anweisung wird aus dem Speicher gelesen oder speichern eine zu memory-- Computer können nur schauen an einer Stelle in einem Zeit-- manchmal eine Kombination von ihnen, aber wirklich nur ein Ort zu einer Zeit. Also, wenn wir taten, Diese verschiedenen Algorithmen, Ich schreibe nicht nur in ein vacuum-- vier, eins, drei, zwei. Diese Zahlen tatsächlich gehören irgendwo physisch im Speicher. So gibt es winzig kleine Transistoren oder irgendeine Art Elektronik unterhalb der Kapuze Speicherung dieser Werte. 

Und insgesamt, wie viele Bits jetzt beteiligt, um nur klar sein? Das ist also vier Bytes oder es ist jetzt 32 Bits insgesamt. So gibt es tatsächlich 32 Nullen und diejenigen, diese vier Dinge zu komponieren. Es gibt noch mehr hier, aber wieder kümmern wir uns nicht darüber. 

So, jetzt lassen Sie uns eine andere fragen Frage mit Speicher, denn das am Ende des Tages ist in Abweichung. Egal, was wir tun könnten mit der Computer am Ende des Tages die Hardware noch die gleiche unter der Haube. Wie würde ich hier ein Wort zu speichern? Nun, ein Wort in einem Computer wie "Hallo!" würde wie diese gespeichert. Und wenn Sie wollten eine längere Wort, können Sie einfach überschreiben, dass und etwas sagen wie "Hallo" und speichern Sie das hier. 

Und so auch hier diese contiguousness ist eigentlich ein Vorteil, weil ein Computer kann nur gelesen von rechts nach links. Aber hier ist eine Frage. Im Rahmen dieses Wortes, h-e-l-l-o, Ausrufezeichen, wie könnte wissen, dass der Computer, auf dem die Wort beginnt und wo das Wort endet? Im Rahmen der Zahlen, Wie funktioniert der Computer wissen, wie lange die Sequenz Zahlen ist oder wo es beginnt? Nun, es stellt sich out-- und wir werden nicht zu viel gehen in dieser Ebene der detail-- Computer bewegen Material um im Speicher buchstäblich über dieser Adressen. Also in einem Computer, wenn Sie Schreiben von Code Dinge zu speichern wie Wörter, was du bist wirklich tun ist die Eingabe Ausdrücke, die wo in erinnern Speicher des Computers diese Worte sind. Also lassen Sie mich ein tun sehr, sehr einfaches Beispiel. 

Ich gehe voran gehen und Öffnen Sie mit einem einfachen Textprogramm auf, und ich werde zu erstellen eine Datei namens hello.c. Die meisten dieser Informationen wir gehen in nicht sehr ausführlich, aber ich werde ein zu schreiben Programm in derselben Sprache, C. Das ist weit mehr von Einschüchterungen, Ich würde behaupten, als Scratch, aber es ist sehr ähnlich im Geiste. In der Tat, diese geschweiften braces-- Sie können Art von denken Sie an, was ich da dies gerade getan. 

Lassen Sie uns dies tun, eigentlich. Wenn grüne Fahne geklickt haben, Mach Folgendes. Ich möchte auszudrucken "Hallo." Also das ist jetzt Pseudo-Code. Ich bin Verwischung Art der Linien. In C, diese Sprache ich spreche über diese Linie Druck hallo tatsächlich wird "printf" mit Einige Klammern und ein Semikolon. 

Aber es ist genau die gleiche Idee. Und das ist sehr benutzerfreundlich "Wenn grüne Fahne geklickt" wird die viel mehr obskure "int main nichtig." Und das hat wirklich keine Zuordnung, so werde ich nur, dass zu ignorieren. Aber die geschweiften Klammern sind wie die gekrümmte Puzzleteile so. 

So können Sie Art erraten. Selbst wenn Sie noch nie programmiert haben, Was macht dieses Programm wahrscheinlich? Wahrscheinlich druckt hallo mit einem Ausrufezeichen. 

Also lassen Sie uns versuchen, dass. Ich werde es zu retten. Und dies ist wiederum ein sehr alte Schulumgebung. Ich kann nicht klicken, kann ich nicht ziehen. Ich muss Befehle eingeben. Deshalb möchte ich mein Programm laufen zu lassen, so dass Ich könnte dies zu tun, wie hello.c. Das ist die Datei, die ich lief. Aber warten Sie, ich bin ein Schritt fehlt. Was haben wir sagen, ist eine notwendige Schritt für eine Sprache wie C? Ich habe gerade Quelle geschrieben Code, aber was brauche ich? Ja, ich brauche einen Compiler. Also auf meinem Mac hier, ich habe ein Programm namens GCC, GNU-C-Compiler, das erlaubt mir this-- wiederum zu tun mein Quellcode in, werden wir es nennen, Maschinensprache. 

Und das kann ich sehen, wieder, wie folgt, diese nur sind die Nullen und Einsen I erstellt von meinem Quellcode, alle der Nullen und Einsen. Und wenn ich will laufen mein program-- es passiert werden für genannt a.out historische reasons-- "Hallo." Ich kann es wieder laufen. Hallo hallo hallo. Und es scheint zu funktionieren. 

Das bedeutet aber, irgendwo in meinem Computerspeichers sind die Worte h-e-l-l-o, Ausrufezeichen. Und es stellt sich heraus, ebenso wie eine Seite, was wäre ein Computer typischerweise tun, damit es weiß, wo Dinge beginnen, und es ist end-- hier geht ein spezielles Symbol zu setzen. Und der Konvention ist das zu setzen Zahl Null am Ende eines Wortes so dass Sie wissen, wo es tatsächlich endet, so dass Sie halten nicht mehr Druck und mehr Zeichen, als Sie eigentlich beabsichtigen. 

Aber das Essen zum Mitnehmen hier, auch obwohl dies ziemlich obskur ist, letztendlich ist, dass es Ziemlich einfach. Sie waren eine Art von Band gegeben, ein leeres Raum, auf dem Sie Briefe schreiben kann. Sie haben einfach eine zu haben, Sonderzeichen, wie willkürlich die Zahl Null, am Ende zu setzen Ihre Worte, so dass der Computer weiß, oh, ich sollte aufhören Druck nach Ich sehe das Ausrufezeichen. Da das nächste, was es ist ein ASCII-Wert von Null, oder das Nullzeichen jemand würde es nennen. Aber es ist irgendwie ein Problem hier, und lassen Sie uns wieder zurück In den Zahlen für einen Moment. Angenommen, dass ich in der Tat, haben eine Reihe von Zahlen, und nehmen wir an, dass die Programm Ich schreibe ist wie ein Notenbuch für Lehrer und ein Lehrer Unterricht. Und dieses Programm erlaubt es ihm oder ihr ihre Schüler Noten eingeben auf Quiz. Und angenommen, dass der Student bekommt 100 auf ihre erste Quiz, vielleicht wie ein 80 auf der nächsten, dann ein 75, dann eine 90 auf der vierten Quiz. 

Deshalb an dieser Stelle in der Geschichte, das Array von der Größe vier. Es gibt absolut mehr Speicher in der Computer, aber das Array, sozusagen vier ist von ihrer Größe. Nehmen wir nun an, dass der Lehrer will ein fünftes Quiz der Klasse zuzuweisen. Nun, eines der Dinge, die er oder sie gehen zu müssen, zu tun Hier ist nun einen zusätzlichen Wert zu speichern. Aber wenn das Array der Lehrer hat in diesem Programm erstellt ist von Größe für, Eines der Probleme mit einer Anordnung ist, dass halten Sie können nicht nur in den Speicher hinzufügen. Denn was ist, wenn ein anderer Teil der Programm hat das Wort "hey" genau dort? 

Mit anderen Worten kann mein Gedächtnis sein für alles in einem Programm verwendet. Und wenn im Voraus getippt ich in, hey, Ich möchte Eingang vier Quiz Partituren, sie könnten hier und hier. Und wenn Sie plötzlich Ihre Meinung ändern später und sagen, dass ich ein fünftes Quiz wollen Score, können Sie nicht einfach setzen sie, wo immer Sie wollen, denn was ist, wenn diese Speicher verwendet für etwas else-- ein anderes Programm oder ein anderes Merkmal des Programms dass Sie laufen? So haben Sie im Voraus zu denken wie Sie möchten, dass Ihre Daten zu speichern, denn jetzt haben Sie gemalt sich in eine digitale Ecke. 

So könnte ein Lehrer statt sagen, wenn ein Programm schreiben, zu speichern, seine oder ihre Noten, weißt du was? Ich werde beantragen, wenn mein Programm zu schreiben, dass ich will null, eins, zwei, drei, vier, fünf, sechs, acht Sorten insgesamt. So ein, zwei, drei, vier, fünf, sechs, sieben, acht. Der Lehrer kann nur über zuteilen Speicher, wenn sein oder ihr Programm zu schreiben und sagen, Sie wissen, was? Ich werde nie mehr vergeben als acht Tests in einem Semester. Das ist einfach verrückt. Das werde ich nie vergeben. Damit diese Art, wie er oder sie hat die Flexibilität zu speichern Student Partituren, wie 75, 90, und vielleicht ein extra wo der Student bekam zusätzliche Kredite, 105. 

Aber wenn der Lehrer nie verwendet diese drei Räume, gibt es eine intuitive Mitnehmen hier. Er oder sie ist nur verschwenden Sie Platz. Also mit anderen Worten, es ist das gemeinsamen Kompromisses in der Programmierung wo Sie entweder zuweisen genau so viel Speicher wie Sie wollen, der Kopf davon ist, dass Sie sind super efficient-- Sie sind nicht verschwenderisch bei all-- aber der Nachteil davon ist was passiert, wenn Sie Ihre Meinung ändern, wenn mit dem Programm, das Sie speichern möchten, mehr Daten, als Sie ursprünglich gedacht. 

Also vielleicht die Lösung ist, dann, Schreiben Sie Ihre Programme in einer solchen Art und Weise dass sie mehr Speicherplatz als sie tatsächlich benötigen. Auf diese Weise Sie nicht gehen laufen in dieses Problem, aber du bist verschwenderisch. Und je mehr Speicher Ihr Programm, wie wir gestern besprochen, die weniger Speicher, der verfügbar ist für andere Programme, Je früher Sie Ihren Computer verlangsamen könnte nach unten wegen des virtuellen Speichers. Und so könnte die ideale Lösung, was sein? 

Unter-Aufteilung scheint schlecht. Über Aufteilung scheint schlecht. Also, was könnte eine bessere Lösung? Die Neuverteilung. Sei dynamischer. Zwingen Sie sich nicht zu wählen priori, am Anfang, was Sie wollen. Und schon gar nicht über zuteilen, damit du nicht verschwenderisch sein. 

Und so, dieses Ziel zu erreichen, haben wir müssen diese Datenstruktur zu werfen, sozusagen weg. Und so was ein Programmierer wird in der Regel verwenden etwas ist kein genannt Array aber eine verknüpfte Liste. Mit anderen Worten, wird er oder sie Start ihres Gedächtnisses zu denken als Art einer Form, dass sie kann auf die folgende Art und Weise zu ziehen. Wenn ich will, eine Nummer zu speichern in ein program-- so ist es September, Ich habe meine Schüler ein Quiz gegeben; Ich will Für die Speicherung der ersten Quiz 'Studenten, und sie haben eine 100 auf es-- I werde meinen Computer zu fragen, über das Programm, das ich habe geschrieben, für einen Teil des Speichers. Und ich werde das zu speichern Nummer 100 in sie, und das ist es. 

Dann ein paar Wochen später wenn ich mein zweites Quiz bekommen, und es ist Zeit zu geben dass 90%, ich werde um den Computer zu fragen, hey, Computer, kann ich einen anderen Teil des Speichers haben? Es wird mir das zu geben leeren Teil des Speichers. Ich werde 90 in der Zahl zu setzen, aber in meinem Programm irgendwie other-- und wir werden keine Sorgen über die Syntax für this-- Ich brauche um die Kette irgendwie zusammen, um diese Dinge. Und ich werde die Kette sie zusammen mit was aussieht wie ein Pfeil hier. 

Die dritte Quiz, die aufkommt, Ich werde sagen, hey, Computer, geben Sie mir einen anderen Teil des Speichers. Und ich werde nach unten zu setzen was auch immer es war, wie 75, und ich habe an die Kette dieser zusammen jetzt irgendwie. Vierte Quiz kommt, und vielleicht das ist gegen Ende des Semesters. Und zu diesem Zeitpunkt mein Programm könnte sein, Speicher mit alle über den Ort, die alle über körperlich. Und so nur zum Spaß, ich bin geht dies zu ziehen weiter quiz-- ich vergessen, was es war; ich denken vielleicht ein 80 oder something-- Weg hierher. 

Aber das ist in Ordnung, weil bildhaft Ich werde diese Linie zu zeichnen. Mit anderen Worten, in der Realität, in der Hardware Ihres Computers, die erste Punktzahl könnte landen sie hier, weil es Gleich zu Beginn des Semesters. Der nächste könnte hier am Ende weil ein wenig Zeit vergangen und das Programm läuft weiter. Die nächste Partitur, die war ein 75 könnte hier sein. Und die letzte Partitur könnte sein, eine 80, der hier ist. 

Also in Wirklichkeit physisch, könnte dies sein was den Arbeitsspeicher Ihres Computers aussieht. Aber dies ist nicht eine nützliche mental Paradigma für einen Computer-Programmierer. Warum sollten Sie darauf, wo die Heck Ihre Daten landen? Sie wollen einfach nur Daten zu speichern. 

Dies ist eine Art, wie unsere Diskussion Zuvor hatte der Würfel der Zeichnung. Warum interessieren Sie sich, was der Winkel des Würfels und wie müssen Sie drehen zu ziehen? Sie wollen einfach nur einen Würfel. Ebenso hier, Sie wollen einfach nur Klasse Buch. Sie wollen einfach nur zu denken, dies als eine Liste von Zahlen. Wen kümmert es, wie es ist in Hardware implementiert? 

So ist die Abstraktion jetzt hier ist das Bild. Dies ist eine Liste verknüpft, wie würde ein Programmierer es nennen, soweit Sie haben eine Liste offensichtlich von Zahlen. Aber es ist verknüpft bildhaft mittels dieser Pfeile, und all diese Pfeile sind-- unter die Haube, wenn Sie neugierig sind, daran erinnern, dass unsere physische Hardware hat Adressen null, eins, zwei, drei, vier. Alle diese Pfeile sind, ist wie eine Landkarte oder Richtungen, wo, wenn 90 ist-- jetzt Ich habe zu zählen. 

Null, eins, zwei, drei, vier, fünf, sechs, sieben. Es sieht aus wie die 90 ist Speicheradresse Nummer sieben. Alle diese Pfeile sind, ist wie ein kleines Stück Papier das ist Erteilung von Anweisungen an die Programm, das diese Karte sagt folgen In den Standort sieben zu bekommen. Und dort finden Sie die Studenten zweite Quiz-Score. Inzwischen hat die 75--, wenn ich weitermachen, dies ist sieben, acht, neun, 10, 11, 12, 13, 14, 15. 

Dieser andere Pfeil stellt nur eine Karte auf einen Speicherbereich 15. Aber auch hier hat der Programmierer im Allgemeinen nicht über dieses Maß an Detail kümmern. Und in den meisten jedem Programmier Sprache heute, der Programmierer wissen nicht einmal in Erinnerung, wo diese Zahlen tatsächlich sind. er oder sie alles hat zu kümmern ist dass sie irgendwie miteinander verbunden sind in einer Datenstruktur wie diese. 

Aber es stellt sich heraus, nicht zu technisch zu bekommen. Aber nur, weil wir können vielleicht leisten, diese Diskussion hier zu haben, nehme an, dass wir erneut dieses Problem hier eines Arrays. Mal sehen, ob wir hier bedauern würde. Dieses ist 100, 90, 75 und 80. 

Lassen Sie mich kurz diesen Anspruch. Dies ist ein Array, und wieder, die hervorstechendste Merkmal eines Arrays Sie alle Ihre Daten ist, dass es wieder zu zurück wahrsten Sinne des Wortes in memory-- an Rücken ein Byte oder vielleicht vier Bytes, einige feste Anzahl von Bytes entfernt. In einer verknüpften Liste, die wir vielleicht ziehen wie diese, unter der Haube, die weiß, wo das Zeug? Es braucht nicht einmal so zu fließen. Einige der Daten könnte zurück zu den dort überlassen. Sie wissen nicht einmal. 

Und so mit einem Array, haben Sie eine Funktion als Random Access bekannt. Und was Direktzugriffsmittel dass der Computer sofort springen an eine beliebige Stelle in einem Array. Warum? Da der Computer kennt dass die erste Lage ist null, eins, zwei und drei. 

Und so, wenn Sie aus gehen wollen Dieses Element zum nächsten Element, Sie buchstäblich, in der Computer Geist, fügen Sie einfach ein. Wenn Sie auf das dritte Element gehen wollen, fügen Sie einfach one-- nächste Element, nur füge eins hinzu. Jedoch in dieser Version der Geschichte an, dass der Computer derzeit auf der Suche bei oder mit der Nummer 100 zu tun haben. Wie kommen Sie auf die nächste Klasse in der Klasse Buch? 

Sie haben sieben zu nehmen Schritte, die willkürlich ist. Um zum nächsten zu erhalten, müssen Sie nehmen acht weitere Schritte bis 15 zu erhalten. Mit anderen Worten, es ist nicht ein konstanten Abstand zwischen den Zahlen, und so nur dauert es die Computer mehr Zeit ist der Punkt. Der Computer hat zu suchen durch Speicher um zu finden, was Sie suchen. 

Während also ein Array neigt dazu, ein zu sein schnelle Daten structure--, weil Sie kann buchstäblich tun, nur einfache arithmetische und wo Sie wollen, indem man hinzufügen, für instance-- eine verknüpfte Liste, Sie diese Funktion zu opfern. Sie können einfach nicht von der ersten gehen In den zweiten bis dritten bis vierten Platz. Sie müssen die Karte folgen. Sie müssen mehr Schritte unternehmen, auf diese Werte zu erhalten, die scheint eine Kosten zu addieren. Also wir zahlen einen Preis, aber was war das Merkmal, dass Dan hier suchte? Was bedeutet eine verknüpfte Liste anscheinend erlauben uns zu tun, das war der Ursprung diese besondere Geschichte? 

Genau. Eine dynamische Größe zu. Wir können zu dieser Liste hinzufügen. Wir können auch die Liste schrumpfen, so dass wir verwenden nur so viel Speicher wie wir eigentlich wollen, und so wir sind nie über Aufteilung. 

Jetzt nur noch, um wirklich nit-picky, gibt es eine versteckte Kosten. So sollten Sie nicht nur lassen Sie mich überzeugen Sie, dass dies ein zwingender Kompromiss. Es gibt eine andere versteckte Kosten hier. Der Vorteil, klar zu sein, ist, dass wir die Dynamik erhalten. Wenn ich ein anderes Element will, kann ich nur ziehen sie und eine Zahl in dort setzen. Und dann kann ich es verlinken mit einem Bild hier, wenn ich habe, während hier, wieder, gemalt mich in eine Ecke, wenn etwas anderes ist bereits mit die Erinnerung hier, ich bin kein Glück. Ich habe mich in die Ecke manövriert. 

Aber was ist die verborgene kosten in diesem Bild? Es ist nicht nur die Menge der Zeit, die es dauert, gehen von hier nach hier, Das ist sieben Schritte, dann acht Stufen, die mehr als eins ist. Was ist eine andere versteckte Kosten? Nicht nur Zeit. Weitere Informationen finden Sie notwendig, um dieses Bild zu erzielen. 

Ja, das Karte, die kleinen Fetzen Papier, als ich halten beschrieb sie als. Diese arrows-- diejenigen sind nicht frei. Ein computer-- Sie wissen was ein Computer hat. Es hat Nullen und Einsen. Wenn Sie einen Pfeil darstellen oder eine Karte oder eine Zahl, benötigen Sie eine Erinnerung. So anderen Preis, den Sie zahlen für eine verknüpfte Liste, eine gemeinsame Informatik Ressource, ist auch Raum. 

Und in der Tat so, so häufig, unter den Kompromissen bei der Gestaltung Software-Engineering Systeme ist Zeit und space-- sind zwei Ihrer Zutaten, zwei Ihrer teuersten Zutaten. Das kostet mich mehr Zeit weil ich diese Karte zu folgen, aber es kostet mich auch mehr Platz weil ich um diese Karte zu halten. So ist die Hoffnung, als wir haben Art diskutiert über gestern und heute, ist, dass die Vorteile die Kosten überwiegen. 

Aber es gibt keine offensichtliche Lösung. Vielleicht ist es better-- a la schnell und schmutzig, wie Kareem vorgeschlagen earlier-- Speicher auf das Problem zu werfen. Nur mehr Speicher kaufen, denken weniger schwer, über das Problem zu lösen, und lösen es in einen einfacheren Weg. Und in der Tat früher, als wir sprachen über Vor- und Nachteile, es war kein Platz in der Computer und der Zeit. Es war Entwickler Zeit, die ist noch eine andere Ressource. 

Also noch einmal, es ist dieser Spagat versuchen, die diese Dinge zu entscheiden, zu verbringen sind Sie bereit? Welches ist die am wenigsten teuer? Welche liefert die besseren Ergebnisse? Ja? 

Tatsächlich. In diesem Fall, wenn Sie Darstellung von Zahlen in der maps-- diese sind in vielen Sprachen genannt "Zeiger" oder "Adressen" - es ist die doppelte Raum. Das muss nicht so schlimm, wie doppelt so hoch sein, wenn jetzt gerade speichern wir nur Zahlen. Nehmen wir an, dass wir die Speicherung Patientenakten in einem hospital-- so Piersons Namen, Telefonnummern, Sozialversicherungsnummern, Arzt Geschichte. Dieses Feld könnte sein, viel, viel größer, in welchem ​​Fall ein kleiner kleiner Zeiger, die Adresse der nächste element-- es ist keine große Sache. Es ist so eine Franse kostet es spielt keine Rolle. Aber in diesem Fall, ja, es ist eine Verdoppelung. Gute Frage. 

Lassen Sie uns über Zeit ein Gespräch wenig konkreter. Was ist die Laufzeit der Suche dieser Liste? Angenommen, ich wollte zu suchen durch alle Noten der Schüler, und es gibt n-Typen in dieser Datenstruktur. Auch hier können wir leihen das Vokabular der früher. Dies ist eine lineare Datenstruktur. 

Big O von n ist, was erforderlich ist, um zu bekommen bis zum Ende dieser Datenstruktur, whereas-- und wir haben nicht gesehen diese before-- ein Array gibt Ihnen was konstante Zeit genannt, was bedeutet, einem Schritt oder in zwei Schritten oder 10 steps-- spielt keine Rolle. Es ist eine feste Zahl. Es hat nichts damit zu tun, die Größe des Arrays. Und der Grund dafür, wiederum ist mit wahlfreiem Zugriff. Der Computer kann nur sofort Sprung zu einem anderen Ort, denn sie sind alle gleich Abstand von allem anderen. Es ist beteiligt kein Denken. Gut. Also, wenn ich kann, lassen Sie mich versuchen, malen zwei letzte Bilder. Eine sehr häufige man als Hash-Tabelle bekannt. Also, diese Diskussion zu motivieren, Lassen Sie mich darüber nachdenken, wie dies zu tun. 

Also, wie wäre es damit? Nehmen wir an, dass das Problem Wir wollen jetzt zu lösen in einem dictionary-- implementiert so eine ganze Reihe von englischen Wörtern oder Wasauchimmer. Und das Ziel ist es, zu beantworten Fragen der Form ist dies ein Wort? So wollen Sie implementieren ein Spell Checker, nur wie ein physischer Wörterbuch dass Sie die Dinge sehen in kann. Nehmen wir an, ich wäre dies mit einer Reihe zu tun. Ich konnte dies tun. 

Und wenn die Worte Apfel sind und Banane und Melone. Und ich kann nicht denken Früchte dass mit d beginnen, so dass wir nur gehen drei Früchte zu haben. Das ist also ein Array ist, und wir sind all dieser Worte zu speichern in diesem Wörterbuch als Array. Die Frage ist also, wie sonst könnten Sie diese Informationen speichern? 

Nun, ich bin betrügt Art von hier, weil jeder dieser Buchstaben im Wort ist wirklich ein einzelnes Byte. Also, wenn ich wollte wirklich sein nit-picky, sollte ich wirklich werden Aufteilung dies in viel kleinere Stücke der Erinnerung, und wir konnten genau das tun. Aber wir werden den Weg laufen das gleiche Problem wie zuvor. Was ist, wenn, wie Merriam Webster oder Oxford jeder tut year-- sie Wörter hinzufügen zum dictionary-- tun wir nicht unbedingt wollen uns zu malen in eine Ecke mit einem Array? 

Anstatt also, vielleicht ein intelligenter Ansatz ist Apple in seinem eigenen Knoten oder Box zu setzen, wie wir sagen würden, Banane, und dann haben wir hier Cantaloupe. Und wir String diese Dinge zusammen. Das ist also das Array, und dies ist die verknüpfte Liste. Wenn Sie nicht ganz sehen, es ist einfach "Array", sagt und das sagt "-Liste." 

Wir haben also die gleiche genaue Fragen wie zuvor, wobei wir jetzt haben, Dynamik in unserer verknüpften Liste. Aber wir haben eine ziemlich langsame Wörterbuch. Angenommen, ich möchte ein Wort nachschlagen. Es könnte nehmen mir große O n Schritte, weil das Wort Macht sein, den ganzen Weg am Ende der die Liste, wie Cantaloupe. Und es stellt sich heraus, dass in der Programmierung, sortieren der heilige Gral der Daten Strukturen, ist etwas, das gibt Ihnen konstant Zeit wie ein Array aber das gibt Ihnen weiterhin Dynamik. 

So können wir haben das Beste aus beiden Welten? Und in der Tat, es ist etwas die Hash-Tabelle genannt das es Ihnen ermöglicht, genau zu tun dass, wenn auch etwa. Eine Hash-Tabelle ist ein schicker Datenstruktur, die wir denken Sie an wie die Kombination eines array-- und ich werde es zu zeichnen wie this-- und verkettete Listen dass ich hier wie diese ziehen. 

Und die Art und Weise dieses Ding Arbeiten ist wie folgt. Wenn diese now-- Hash table-- meine dritte Datenstruktur ist, und ich möchte zu speichern in diesen Worten, weiß ich nicht möchte nur all die Speicherung Worte, Rücken an Rücken Rücken an Rücken. Ich möchte einige zu nutzen Stück Information über die Worte, die lassen wird mir bekommen sie, wo es schneller. 

Also angesichts der Worte Apfel und Banane und Melone, Ich wählte absichtlich diese Worte. Warum? Was ist eine Art grundlegend anders über die drei? Was ist das offensichtlich? Sie beginnen mit verschiedenen Buchstaben. 

So wissen Sie was? Anstatt alle meine setzen Worte in die gleichen Eimer, so zu sprechen, wie in einer großen Liste, warum nicht Ich zumindest versuchen, eine Optimierung und machen meine Listen 1/26 so lang. Eine überzeugende Optimierung könnte sein, warum nicht tun I-- beim Einfügen eines Wortes in dieser Datenstruktur, in den Speicher des Computers, warum nicht habe ich alle hier 'a' Worte, hier alle 'b' Worte, und all die 'c' Worte hier? So endet das einen Apfel Aufstellen hier, Banane hier, Melone hier, und so weiter. 

Und wenn ich einen zusätzlichen Wort like--, was ein anderer ist? Apfel, Banane, Birne. Wer glaube, einer Frucht Dies beginnt mit einem, b oder c? Blueberry-- perfekt. Das wird hier enden. Und so scheinen wir zu haben geringfügig bessere Lösung, denn jetzt, wenn ich will für Apfel zu suchen, ich first-- ich nicht nur tauchen in meine Datenstruktur. Ich tauchen nicht in meinem Speicher des Computers. Ich schaue zuerst auf den ersten Buchstaben. 

Und das ist es, was einen Computer Wissenschaftler sagen würde. Sie Hash in der Datenstruktur. Sie nehmen Ihre Eingabe, die in Dieser Fall ist ein Wort wie Apfel. Sie analysieren, mit Blick auf der erste Buchstabe in diesem Fall Hashing es dabei. Hashing ist ein allgemeiner Begriff, wobei Sie nehmen etwas als Eingabe und Sie erzeugen eine Ausgabe. Und der Ausgang daß Fall ist die Lage Sie wollen, die erste zu suchen Lage, die zweite Lage, die dritte. So ist der Eingang ist Apfel, der Ausgang zuerst. Der Eingang ist Banane, dem Ausgabe sollte Sekunde. Der Eingang ist Melone, sollte die Ausgabe dritte sein. Der Eingang ist Heidelbeeren, die Ausgabe sollte wieder zweite sein. Und das ist, was hilft Ihnen nehmen Abkürzungen durch Ihr Gedächtnis um Worte zu bekommen oder Daten effektiver zu gestalten. 

Nun schneidet diese unsere Zeit nach unten potentiell um so viel wie eine von 26, denn wenn man davon ausgehen, dass Sie haben so viele "a" Wörter wie "z" Wörter wie "q" Worte, die nicht wirklich realistic-- Sie gehen Skew über zu haben bestimmte Buchstaben des alphabet-- aber dies wäre eine inkrementelle Ansatz, erlaubt es Sie Wörter sehr viel schneller zu bekommen. Und in Wirklichkeit ein ausgeklügeltes Programm, das Googles der Welt, die Facebooks der world-- sie würden eine Hash-Tabelle verwenden für viele verschiedene Zwecke. Aber sie würden nicht so naiv sein auf den ersten Buchstaben zu suchen einfach in Apfel oder Banane oder Birne oder Melone, weil, wie Sie diese sehen können Listen bekommen könnte noch lang. 

Und so könnte dies noch Art sein von linear-- so eine Art langsam, wie mit dem großen O n dass wir früher diskutiert. Also, was eine wirklich gute Hash-Tabelle wird do-- es wird eine viel größere Array. Und es wird eine viel mehr verwenden anspruchsvolle Hashing-Funktion, so dass es sieht nicht nur auf dem "a". Vielleicht sieht es bei "a-p-p-l-e" und irgendwie wandelt diese fünf Buchstaben in den Ort, an dem Apple sollte aufbewahrt werden. Wir verwenden nur naiv den Buchstaben "a" allein, denn es ist schön und einfach. 

Aber eine Hash-Tabelle, in Am Ende können Sie denken, als eine Kombination aus ein Array, von denen jede hat eine verknüpfte Liste, die im Idealfall sollte so kurz wie möglich sein. Und das ist nicht offensichtlich, dass die Lösung. In der Tat, ein Großteil der Feinabstimmung das geht unter der Haube auf, wenn Umsetzung dieser Arten von anspruchsvolle Datenstrukturen ist das, was das Recht ist Länge des Arrays? Was ist die richtige Hash-Funktion? Wie lagere man die Dinge in Erinnerung? 

Aber klar, wie schnell diese Art der Diskussion Art eskaliert, entweder so weit, dass es über den Kopf an dieser Stelle, die ist gut. Aber wir begannen, Rückruf, mit wirklich etwas niedriger Ebene und Elektronik. Und so ist das auch in diesem Thema der Abstraktion, wo sobald Sie anfangen zu nehmen gewährt, OK, habe ich es-- es bekam physischen Speicher, OK, bekam es, jede physischen Standort hat eine Adresse, OK, ich habe es, kann ich darstellen diese Adressen als arrows-- Sie können sehr schnell zu haben, starten anspruchsvollere Gespräche, die am Ende scheinen uns zu ermöglichen um Probleme zu lösen wie die Suche und Sortieren effektiver. Und seien Sie versichert, too-- weil ich denke, das ist ist der tiefste haben wir in einige gegangen dieser CS Themen proper-- wir haben an einem Tag und eine Hälfte an das getan zeigen, was Sie in der Regel über tun könnte der Verlauf von acht Wochen in einem Semester. 

Haben Sie Fragen zu diesen? Nein? Gut. Nun, warum wir dort nicht anhalten, beginnen Mittagessen ein paar Minuten zu früh, Wiederaufnahme nur etwa eine Stunde in? Und ich werde verweilen ein bisschen mit Fragen. Dann werde ich gehen zu müssen Nehmen Sie ein paar Anrufe, wenn das OK ist. Ich werde in der Zwischenzeit etwas Musik drehen, aber das Mittagessen sollte um die Ecke sein.