DAVID MALAN: Très bien. Nous sommes de retour. Donc, dans ce segment sur la programmation ce Je pensais que nous ferions est un mélange de choses. Un, faire un peu de quelque chose pratique, mais en utilisant une plus ludique environment-- de programmation celui qui est démonstratif exactement le genre d'idées nous avons parlé, mais un peu plus formelle. Deux, regardons quelques-uns des les moyens plus techniques qu'un programmeur serait effectivement résoudre des problèmes tels que le problème de recherche que nous avons examiné avant et aussi plus fondamentalement problème intéressant de tri. 

Nous supposions dès le départ que ce répertoire a été réglé, mais ce seul est en fait une sorte de problème difficile avec de nombreuses façons différentes pour le résoudre. Donc, nous allons les utiliser comme une classe de problèmes représentant des choses qui pourraient être résolus en général. Et puis nous allons parler environ en détail ce que sont appelées données structures-- façons fantaisistes comme les listes chaînées et des tables de hachage et des arbres qui un programmeur serait effectivement utiliser et utilisent généralement sur un tableau blanc à peindre une image de ce qu'il ou elle envisage pour la mise en œuvre un morceau de logiciel. 

Alors, faisons les mains sur la première partie. Il suffit donc de vous salir les mains avec un environnement appelé scratch.mit.edu. Ceci est un outil que nous utilisons dans notre classe de premier cycle. Même si il est conçu pour 12 ans et plus, nous l'utilisons pour le haut une partie de ce tout à fait un peu car il est un beau, fun manière graphique de l'apprentissage un petit quelque chose sur la programmation. Ainsi, la tête à cette URL, où vous devrait voir une page tout à fait comme ça, et aller de l'avant et cliquez sur Joignez-vous à Scratch en haut à droite et de choisir un nom d'utilisateur et un mot de passe et, finalement, vous obtenez un scratch.mit.edu account--. Je pensais l'utiliser comme un première occasion de montrer cela. Une question a été soulevée pendant la pause à propos de ce que le code ressemble réellement. Et nous parlions pendant la pause à propos de C, en particulier un particular-- niveau inférieur dans une langue plus. Et je viens de faire un rapide Google recherche pour trouver le code C pour la recherche binaire, l'algorithme que nous utilisé pour la recherche que l'annuaire téléphonique plus tôt. Cet exemple particulier, bien sûr, ne recherche pas un livre de téléphone. Il cherche simplement tout un tas de les numéros dans la mémoire de l'ordinateur. Mais si vous souhaitez simplement obtenir un visuel sens de ce qu'est une programmation effective la langue ressemble, il semble un petit quelque chose comme ça. Il est donc environ 20 ans et plus, 30 ou si des lignes de code, mais la conversation que nous ont été ayant pendant les vacances était sur la façon dont cette réalité obtient transformé en zéros et des uns et si vous ne pouvez pas revenir que traiter et aller de zéros et de uns revenir à code. 

Malheureusement, le processus est si transformatrice qu'il est beaucoup plus facile à dire qu'à faire. Je suis allé de l'avant et effectivement tourné ce programme, recherche binaire, en zéros et par l'intermédiaire d'un Le programme appelé compilateur que je arrive d'avoir ici à droite sur mon Mac. Et si vous regardez l'écran ici, en se concentrant spécifiquement sur ces six colonnes intermédiaires uniquement, vous verrez que des zéros et des uns. Et ce sont les zéros et ceux qui composer exactement ce programme de recherche. 

Et de sorte que chaque morceau de cinq bits, chaque octet de zéros et de uns ici, représenter une certaine instruction typiquement à l'intérieur d'un ordinateur. Et en fait, si vous avez entendu le slogan "Intel inside" de marketing - que, bien sûr, signifie simplement que vous avez un Intel CPU ou du cerveau à l'intérieur de l'ordinateur. Et ce que cela signifie d'être un CPU est que vous avez un jeu d'instructions, pour ainsi dire. 

Chaque processeur dans le monde, dont beaucoup les faites par Intel ces jours-ci, comprend un ensemble fini nombre d'instructions. Et ces instructions sont si bas niveau comme ajouter ces deux nombres, multiplier ces deux nombres, déplacer ce morceau de données à partir d'ici ici en mémoire, enregistrez ce l'information d'ici à là en mémoire, et ainsi forth-- donc très, très bas niveau, les détails presque électroniques. Mais avec les mathématiques opérations couplées avec ce que nous avons discuté plus tôt, la représentation des données comme zéros et des uns, peut vous construisez tout qu'un ordinateur peut faire aujourd'hui, que ce soit il est textuel, graphique, musical, ou autrement. 

Donc, ce qui est très facile à obtenir perdu dans les mauvaises herbes de rapidement. Et il y a beaucoup de défis syntaxiques de sorte que si vous faites le plus simple, plus stupide des fautes de frappe aucune du programme ne fonctionnera que ce soit. Et donc au lieu d'utiliser un langage comme C ce matin, Je pensais que ce serait plus de plaisir à faire réellement quelque chose de plus visuel, qui tout en étant conçu pour les enfants est en fait une manifestation parfaite d'une programmation effective language-- arrive juste à utiliser des images au lieu de texte pour représenter ces idées. 

Donc, une fois que vous avez en effet un compte scratch.mit.edu, cliquez sur le bouton Créer en haut à gauche du site. Et vous devriez voir un environnement comme celui que je suis sur le point de voir sur mon écran ici. Et nous allons passer un peu peu de temps à jouer ici. Voyons voir si nous ne pouvons pas tout résoudre certains problèmes ensemble de la manière suivante. 

Donc, ce que vous verrez dans ce environment-- et en fait juste laisser moi une pause. Quelqu'un est-il pas ici? Pas ici? D'ACCORD. Alors permettez-moi de souligner quelques-uns caractéristiques de cet environnement. 

Donc, en haut à gauche de l'écran, nous avoir la scène de Scratch, pour ainsi dire. Scratch est non seulement le nom de ce langage de programmation; il est aussi le nom du chat qui vous voyez par défaut, il en orange. Il est sur une scène, de sorte un peu comme je l'ai décrit la tortue plus tôt comme étant dans un environnement de tableau blanc rectangulaire. le monde Ce chat se limite entièrement à ce rectangle en haut là. 

Pendant ce temps, sur la droite côté ici, il est juste une zone de scripts, un ardoise vierge si vous voulez. Voilà où nous allons écrire nos programmes en un instant. Et les blocs de construction que nous utiliser pour écrire cette program-- le puzzle morceaux, si vous êtes will-- ceux ici au milieu, et ils sont classés par fonctionnalité. Ainsi, par exemple, je vais aller de l'avant et de démontrer au moins un de ceux-ci. Je vais aller de l'avant et cliquez sur la catégorie de contrôle en haut. 

Donc, ce sont les catégories en haut. Je vais cliquer sur la catégorie de contrôle. Au contraire, je vais cliquer sur les événements catégorie, le tout premier en haut. Et si vous souhaitez suivre même comme nous le faisons, vous avez tout à fait bienvenue à. Je vais cliquer et faire glisser ce première, "lorsque le drapeau vert cliqué." Et puis je vais laisser tomber juste à peu près au sommet de mes pages blanches. 

Et ce qui est agréable au sujet Scratch est que cette pièce de puzzle, quand verrouillé avec un autre casse-tête morceaux, va faire littéralement ce que ces pièces de puzzle disent de faire. Ainsi, par exemple, Scratch est juste maintenant au milieu de son monde. Je vais aller de l'avant et de choisir maintenant, disons, la catégorie de mouvement, si vous souhaitez faire de same-- catégorie Motion. Et maintenant remarquer que j'ai un tout tas de pièces de puzzle ici que, encore une fois, sorte de faire ce qu'ils disent. Et je vais aller de l'avant et faire glisser et déposer le bloc de déplacement juste ici. 

Et remarquez que, dès que vous obtenez à proximité du fond du «drapeau vert cliqué sur "bouton, avis comment une ligne blanche apparaît, comme si elle est presque magnétique, il veut y aller. Il suffit de laisser aller, et il se cassera ensemble et les formes correspondront. Et maintenant, vous pouvez peut-être presque deviner où nous allons avec cela. 

Si vous regardez la scène de Scratch ici et regarder vers le haut de celui-ci, vous verrez une lumière rouge, arrêtez le signe, et un drapeau vert. Et je vais aller de l'avant et regarder mes screen-- pour un instant, si vous le pouviez. Je vais cliquer sur le drapeau vert en ce moment, et il a déménagé ce qui semble être 10 étapes ou 10 pixels, 10 points, sur l'écran. 

Et donc pas excitant, mais permettez-moi de proposer sans même enseigner cela, juste en utilisant le propre de votre propre let intuition-- me propose que vous comprendre comment faire Scratch pied droit hors de la scène. Demandez-lui de faire place à la droite de l'écran, tout le chemin vers la droite. Permettez-moi de vous donner un moment ou alors à se débattre avec cela. Vous pouvez jeter un coup d'oeil à d'autres catégories de blocs. D'accord. Donc, pour récapituler, lorsque nous avons le drapeau vert cliqué ici et déplacer 10 étapes est la seule instruction, chaque fois que je cliquez sur le drapeau vert, ce qui se passe? Eh bien, qui exécute mon programme. Donc, je pouvais le faire peut-être 10 fois manuellement, mais cela se sent un peu bit hackish, pour ainsi dire, de sorte que je ne suis pas vraiment la résolution du problème. Je suis juste essayer encore et Encore et encore et encore jusqu'à ce que je sorte de hasard parvenir à la directive que je me suis mis à réaliser plus tôt. 

Mais nous savons de notre pseudocode plus tôt qu'il ya cette notion dans la programmation de la boucle, faire encore et encore quelque chose. Et je l'ai vu qu'un groupe de vous atteint pour pièce ce puzzle? Répétez jusqu'à ce que. Donc, nous pourrions faire quelque chose comme répéter jusqu'à ce que. Et qu'est-ce que vous répétez jusqu'à ce exactement? 

D'ACCORD. Et laissez-moi aller avec celui qui est un peu plus simple pour un instant. Laissez-moi aller de l'avant et de faire cela. Notez que, comme vous pouvez avoir découvert sous contrôle, il y a ce bloc de répétition, qui ne regarde pas comme il est si grand. Il n'y a pas beaucoup de place dans entre ces deux lignes jaunes. Mais comme certains d'entre vous pourraient avoir remarqué, si vous faites glisser-déposer, remarquez comment il se développe pour remplir la forme. 

Et vous pouvez même entasser plus. Il va juste continuer de croître si vous faites glisser et survolez. Et je ne sais pas ce qui est mieux ici, alors laissez moi au moins répéter cinq fois, pour par exemple, et ensuite revenir à l'étape et cliquez sur le drapeau vert. Et maintenant, remarquez qu'il est pas tout à fait là. 

Maintenant, certains d'entre vous ont proposé, comme Victoria n'a tout simplement, répéter 10 fois. Et cela fait généralement lui faire tout le chemin, mais ne serait pas y avoir une plus robuste ainsi que de déterminer arbitrairement combien se déplace à faire? Quel pourrait être un meilleur bloc que répéter 10 fois être? 

Ouais, alors pourquoi ne pas faire quelque chose pour toujours? Et maintenant, laissez-moi passer cette pièce de puzzle à l'intérieur de là et se débarrasser de celui-ci. Maintenant, remarquez, peu importe où Scratch commence, il va vers le bord. Et heureusement MIT, qui fait Scratch, juste fait en sorte qu'il n'a jamais disparaît complètement. Vous pouvez toujours saisir sa queue. 

Et intuitivement, pourquoi at-il continuer à avancer? Qu'est-ce qui se passe ici? Il semble s'être arrêté, mais puis si je prends et faites glisser il continue à vouloir aller là-bas. Pourquoi donc? Vraiment, un ordinateur est littéralement allez faire ce que vous lui demandez de faire. Donc, si vous l'avez dit plus tôt faire la suivant chose pour toujours, déplacer 10 étapes, il va continuer et aller jusqu'à ce que je frappe le panneau d'arrêt rouge et arrêter complètement le programme. 

Donc, même si vous ne l'avez pas faire, comment pourrais-je faire Scratch aller plus vite à travers l'écran? Plus de mesures, non? Ainsi, au lieu de faire 10 à un moment, pourquoi ne pas nous aller de l'avant et le changer to-- que feriez-vous propose-- 50? Alors maintenant, je vais cliquer sur le vert drapeau, et en effet, il va très vite. 

Et cela, bien sûr, est juste une manifestation d'animation. Qu'est-ce que l'animation? Il est juste de vous montrer l'un humain tas ensemble d'images fixes vraiment, vraiment, vraiment rapide. Et si nous sommes en train de dire lui de se déplacer plusieurs étapes, nous juste avoir l'effet soit à changement où il est à l'écran tout l'appareil plus rapidement par temps. 

Maintenant, le prochain défi que je proposais devait avoir lui rebondir sur le bord. Et sans savoir ce casse-tête morceaux parce qu'elle est réalisée: amende si vous ne recevez pas à la étape du challenge-- ce voulez-vous faire intuitivement? Comment pourrions-nous le faire rebondir et etc., entre la gauche et la droite? 

Ouais. Nous avons donc besoin d'une sorte de l'état, et nous semblent avoir conditionals, ainsi dire, dans la catégorie de contrôle. Lequel de ces blocs voulons-nous sans doute? Ouais, peut-être «si, alors." Donc remarquer que, parmi les blocs jaunes nous avons ici, il y a ce "si" ou cette «if, else" bloc qui sera nous permettent de prendre une décision pour ce faire ou de le faire. Et vous pouvez même imbriquer à faire plusieurs choses. Ou si vous avez pas encore allé ici, aller de l'avant à la catégorie Sensing et-- nous allons voir si elle est ici. 

Donc, ce bloc peut être utile ici pour détecter s'il est hors de la scène? Ouais, notez que certains de ces blocs peuvent être paramétrées, pour ainsi dire. Ils peuvent être personnalisés en quelque sorte, pas contrairement HTML hier avec des attributs, où ces attributs type de personnaliser le comportement d'une balise. De même ici, je peux saisir cette touchante bloc et le changement et poser la question, touchez-vous la souris pointeur comme le curseur ou êtes-vous touchez le bord? 

Alors laissez-moi aller et le faire. Je vais faire un zoom arrière pour un moment. Permettez-moi de saisir cette pièce de puzzle ici, ce puzzle morceau cela, et je vais pêle-mêle les pour un moment. Je vais passer cela, changer cette arête touchante, et je vais faire le mouvement. Alors, voici quelques ingrédients. Je pense avoir tout ce que je veux suis. 

Quelqu'un voudrait-il proposer comment je peut se connecter ces peut-être haut en bas afin de résoudre le problème de devoir Scratch mouvement de droite à gauche à droite pour de gauche à droite à gauche, chaque temps juste rebondir sur le mur? Qu'est-ce que je veux faire? Quel bloc dois-je me connecter à "Drapeau quand vert cliqué premier"? 

OK, donc nous allons commencer avec le "pour toujours." Ce qui se passe à l'intérieur de la prochaine? Quelqu'un d'autre. OK, déplacer étapes. D'accord. Alors quoi? Alors le cas. Et remarquez, même si elle semble pris en sandwich ensemble étroitement, il va juste pousser à remplir. Il va juste sauter dans où je veux. 

Et qu'est-ce que je mets entre le cas et alors? Probablement "si touchant bord." Et remarquez, encore une fois, il est trop grand pour elle, mais elle va croître à combler. Et puis tourner à 15 degrés? Combien de degrés? Ouais, donc 180 va tourner moi tout autour. Voyons donc si je suis ce droit. Permettez-moi de faire un zoom arrière. 

Permettez-moi de glisser Scratch up. Donc, il est un peu déformée maintenant, mais ça va. Comment puis-je le réinitialiser facilement? Je vais tricher un peu. Je suis donc d'ajouter un autre bloc, juste pour être clair. Je veux qu'il pointe à 90 degrés à la droite par défaut, donc je vais juste lui dire de le faire par programme. Et c'est reparti. Nous semblons avoir fait. Il est un peu bizarre, parce que il marche à l'envers. Appelons qu'un bug. C'est une erreur. Un bug est une erreur dans un programme, un erreur logique que moi, l'être humain, fait. Pourquoi est-ce qu'il va à l'envers? Est-ce que MIT bousiller ou ai-je? 

Ouais, je veux dire, ce n'est pas MIT faute. On m'a donné une pièce de puzzle qui dit tourner un certain nombre de degrés. Et à la suggestion de Victoria, Je tourne à 180 degrés, qui est la bonne intuition. Mais tourner de 180 degrés littéralement des moyens de rotation de 180 degrés, et ce n'est pas vraiment ce que je veux, apparemment. Parce qu'au moins il est dans ce monde à deux dimensions, alors tournant va vraiment de lui retourner la tête en bas. 

Je veux probablement utiliser ce bloc à la place, sur la base de ce que vous voyez ici? Comment pourrions-nous résoudre ce problème? Ouais, donc nous pourrions pointer dans la direction opposée. Et en fait même que ce ne va pas être suffisant, parce que nous ne pouvons coder en dur à pointer gauche ou à droite. 

Vous savez ce que nous pourrions faire? Il semble que nous avons un bloc de commodité ici. Si je zoome, voir quelque chose que nous aimons ici? Donc, il semble que le MIT a un abstraction construite ici. Ce bloc semble être équivalent à laquelle d'autres blocs, pluriel? 

Celui-ci bloc semble être équivalent à l'ensemble de ce trio de blocs que nous avons ici. Donc, il se trouve que je peux simplifier ma programme en se débarrassant de tout cela et vient de mettre cela ici. Et maintenant, il est encore un peu poussette, et c'est très bien pour le moment. Nous allons laisser ce soit. Mais mon programme est encore plus simple, et cela, aussi, serait représentatif d'un but dans programming-- est de faire idéalement votre code comme simple, aussi compact que possible, tout en étant aussi lisible que possible. Vous ne voulez pas faire en sorte succincte qu'il est difficile à comprendre. 

Mais notez que j'ai remplacé trois blocs avec un, et c'est sans doute une bonne chose. Je suis loin de la notion abstraite de vérifier si vous êtes sur le bord d'un seul bloc. Maintenant, nous pouvons nous amuser avec cela, en fait. Cela ne correspond pas tellement valeur intellectuelle, mais la valeur ludique. Je vais aller de l'avant et de saisir ce son ici. Alors laissez-moi aller de l'avant, et laissez-moi arrêter le programme pendant un moment. Je vais enregistrer ce qui suit, permettant l'accès à mon micro. 

Et c'est parti. Aie. Essayons encore une fois. Et c'est parti. OK, j'ai enregistré la mauvaise chose. Et c'est parti. Aie. Aie. D'accord. Maintenant, je dois me débarrasser de cela. D'accord. 

Alors maintenant, je suis un enregistrement de juste "ouch." Alors maintenant, je vais aller avant et appeler cette "ouch." Je vais revenir en arrière à mes scripts, et maintenant avis il y a ce bloc qui est appelé jouer son "miaou" ou jouer son "ouch." Je vais faire traîner, et où dois-je mettre ce pour un effet comique? Ouais, alors maintenant il est une sorte de poussette, parce que maintenant ce block-- remarquez comment cette «si sur le bord, rebond "est une sorte d'auto-contenue. Je dois donc résoudre ce problème. Laissez-moi aller de l'avant et de faire cela. Permettez-moi de me débarrasser de cela et revenir à notre origine, plus délibérée la fonctionnalité. Donc, "si bord de toucher, puis" je veux à tourner, que Victoria a proposé, 180 degrés. Et ce que je veux jouer le son "ouch" il? 

Ouais, notez qu'il est à l'extérieur ce bloc jaune. Donc, cela aussi serait un bug, mais je l'ai remarqué. Donc, je vais le faire glisser ici, et un avis maintenant il est à l'intérieur du «si». Ainsi, le «si» est ce genre de comme blot en forme de bras que ça ne va faire ce qui est à l'intérieur de celui-ci. Alors maintenant, si je zoome sur au le risque de annoying-- 

COMPUTER: Aïe, aïe, aïe. 

DAVID MALAN: Et il va juste durer éternellement. Maintenant, il suffit d'accélérer les choses ici, laissez-moi aller de l'avant et d'ouvrir, nous allons say-- me laisser aller à quelques-uns de ma propre substance de la classe. Et laissez-moi ouvrir, disons, ce celle faite par un de nos compagnons d'enseignement Il y a quelques années. Donc, certains d'entre vous rappeler ce jeu d'antan, et il est en fait remarquable. Même si nous avons fait le la plus simple des programmes en ce moment, nous allons examiner ce que cela ressemble réellement. Permettez-moi de frapper le jeu. 

Donc, dans ce jeu, nous avons un grenouille, et en utilisant la flèche keys-- il prend de plus grandes étapes que je remember-- Je contrôle sur cette grenouille. Et le but est d'obtenir à travers le occupés route sans courir dans les voitures. Et soyons see-- si je vais ici, je avoir à attendre un journal pour faire défiler par. Cela se sent comme un bug. Ceci est une sorte de bug. D'accord. Je suis sur ce ici, là, et puis vous continuez à jusqu'à ce que vous obtenez tous les grenouilles aux nénuphars. Maintenant, cela pourrait ressembler d'autant plus complexe, mais nous allons essayer de briser cette mentalement et verbalement dans ses blocs de composants. Donc, il y a probablement un casse-tête pièce que nous avons pas encore vu mais que cela répond à des frappes, aux choses que je frappe sur le clavier. 

Donc, il y a probablement une sorte de bloc qui dit, si la clé est égale up, puis faire quelque chose avec Scratch-- peut-être déplacer 10 étapes de cette façon. Si la touche vers le bas est enfoncé, déplacez 10 étapes de cette façon, ou la touche gauche, déplacer 10 étapes De cette façon, 10 étapes que. J'ai clairement tourné le chat en grenouille. Voilà donc là où la costume, comme des appels à gratter it-- nous juste importé une image de la grenouille. 

Mais qu'est-ce qui se passe? Quelles autres lignes de code, ce que les autres pièces du puzzle Blake a fait, notre compagnon d'enseignement, utiliser dans ce programme, apparemment? Qu'est-ce tout faire move-- ce que la programmation construire? 

Mouvement, sure-- de sorte que le déplacer le bloc, pour sûr. Et ce qui est de ce bloc de déplacement intérieur, le plus probable? Oui, une sorte de boucle, peut-être un jamais bloquer, peut-être une répétition block-- répéter jusqu'à ce bloc. Et voilà ce qui rend les billes et les nénuphars et tout mouvement d'autre d'avant en arrière. Il est juste passe sans cesse. 

Pourquoi certains sont des voitures se déplaçant plus vite que les autres? Ce qui est différent au sujet de ces programmes? Oui, sans doute certains d'entre eux prennent plusieurs étapes à la fois et certains d'entre eux moins d'étapes à la fois. Et l'effet visuel est rapide par rapport lent. 

Que pensez-vous arrivé? Quand je suis arrivé ma grenouille tout le chemin dans la rue et la rivière sur la feuille de nénuphar, quelque chose remarquable est arrivé. Qu'est-il arrivé dès que je l'ai fait? Cela s'arrêta. Cette grenouille est arrêté, et Je suis une seconde grenouille. Alors, que doit être construit il utilisé, ce dispositif? 

Ouais, donc il y a une sorte de "Si" conditionner là-bas, aussi. Et il se out-- nous ne voyons pas this-- mais il y a d'autres blocs là que peut dire, si vous êtes toucher une autre chose sur l'écran, si vous touchez le nénuphar », alors." Et puis c'est lorsque nous faire la deuxième grenouille apparaît. Ainsi, même si ce jeu est certainement très daté, même si, à première vue il y a tellement de choses on-- et Blake n'a pas fouetter ce en deux minutes, il a probablement pris plusieurs lui heures pour créer ce jeu sur la base de sa mémoire ou de vidéos de la version d'antan de celui-ci. Mais toutes ces petites choses aller sur l'écran dans l'isolement résument à ces très simple mouvements ou déclarations constructs-- comme nous en avons discuté, des boucles et des conditions, et qui est à ce sujet. Il y a quelques autres fonctionnalités plus fantaisistes. Certains d'entre eux sont purement esthétique ou acoustique, comme les sons que j'ai joué avec. Mais pour la plupart, vous avoir dans cette langue, Scratch, tous les fondamentaux blocs de construction que vous avoir en C, Java, JavaScript, PHP, Ruby, Python, et un certain nombre d'autres langues. Une question sur Scratch? D'accord. Donc, nous ne pourrons pas plonger plus profondément pour Scratch, si vous êtes les bienvenus ce week-end, surtout si vous avez des enfants ou neveux et nièces et autres, pour leur présenter Scratch. Il est en fait une merveille ludique environnement avec, comme ses auteurs, très hauts plafonds. Même si nous avons commencé avec mêmes les détails de bas niveau, vous pouvez vraiment faire un peu avec elle, et cela est peut-être une démonstration de exactement cela. 

Mais nous allons transition maintenant un peu plus problèmes sophistiqués, si vous voulez, connu sous le nom de «recherche» et «Tri», plus généralement. Nous avons eu ce livre de téléphone, voici l'heure, à un autre juste pour discussion-- que nous étions en mesure de rechercher de façon plus efficace, car d'une hypothèse importante. Et juste pour être clair, ce qui hypothèse était je faire lors de la recherche à travers ce livre de téléphone? Ce Mike Smith était en le livre de téléphone, si je serait capable de gérer le scénario sans lui là si je viens d'arrêter prématurément. Le livre est alphabétique. Et c'est un très généreux hypothèse, parce que signifie someone-- Je suis un peu de couper un coin, comme je suis plus rapide parce que quelqu'un d'autre a fait beaucoup de travail difficile pour moi. 

Mais si le téléphone livre ont été unsorted? Peut-être que Verizon a obtenu paresseux, juste jeté Les noms et les numéros de chacun là-bas peut-être dans l'ordre dans lequel ils signé pour le service téléphonique. Et combien de temps faut-il me prendre de trouver quelqu'un comme Mike Smith? 1000 pages téléphone book-- combien pages que je dois regarder à travers? 

Tous. Vous êtes en quelque sorte hors de la chance. Vous avez littéralement à regarder tous les page si l'annuaire est juste triées aléatoirement. Vous pourriez avoir de la chance et trouver Mike sur la première page, parce qu'il a été le premier client de commander un service de téléphone. Mais il aurait pu être le dernier, aussi. 

Donc un ordre aléatoire est pas bon. Supposons donc que nous devons trier la annuaire téléphonique ou dans les données générales de tri que nous avons reçu. Comment peut-on faire ça? 

Eh bien, laissez-moi juste essayer un exemple simple ici. Laissez-moi aller de l'avant et de lancer une Quelques chiffres sur la carte. Supposons que les chiffres que nous avons sont, disons, quatre, deux, un, et trois. Et, Ben, trier ces chiffres pour nous. 

OK, bien. Comment as-tu fais ça? D'accord. Donc, commencer par le plus petit et la valeur la plus élevée, et c'est vraiment une bonne intuition. Et réaliser que nous les humains sont en fait assez bon à la résolution de problèmes comme celui-ci, au moins lorsque les données sont relativement faibles. Dès que vous commencez à avoir des centaines des nombres, des milliers de numéros, des millions de numéros, Ben probablement ne pouvait pas le faire tout à fait aussi vite, en supposant qu'il y avait les lacunes dans les chiffres. Assez facile de compter jusqu'à un million sinon, juste du temps. 

Donc, l'algorithme il sonne comme Ben utilisé tout à l'heure était la recherche du plus petit nombre. Donc, même si nous, les humains peuvent prendre dans un grand nombre d'informations visuelles, un ordinateur est en réalité un peu plus limitée. L'ordinateur ne peut regarder un octet à la fois ou peut-être quatre octets à time-- ces jours peut-être 8 octets à time-- mais un très petit nombre d'octets à un moment donné. 

Donc, étant donné que nous avons vraiment quatre valeurs distinctes ici-- et vous pouvez penser à Ben comme ayant oeillères s'il était un ordinateur tel qu'il ne peut pas voir autre chose d'un numéro à un time-- donc nous supposerons généralement, comme dans Anglais, nous allons lire de droite à gauche. Donc, le premier numéro Ben probablement regardé à était quatre, puis très rapidement réalisé que c'est un assez grand number-- permettez-moi de continuer à chercher. 

Il y a deux. Attends une minute. Deux est inférieur à quatre. Je vais vous rappeler. Deux est maintenant le plus petit. Maintenant One-- qui est encore mieux. C'est encore plus faible. Je vais oublier deux et rappelez-vous juste un maintenant. 

Et pourrait-il arrêter de regarder? Eh bien, il pouvait base cette information, mais il ferait mieux de recherche le reste de la liste. Parce que si zéro étaient dans la liste? Que si négatif on était dans la liste? Il sait seulement que sa réponse est correct s'il est exhaustive vérifier toute la liste. Donc, nous regardons le reste de cette. Three-- qui était une perte de temps. Got chance, mais j'étais toujours correct de le faire. Et maintenant il vraisemblablement choisi le plus petit nombre et vient de mettre au début de la liste, comme je vais le faire ici. Maintenant, qu'avez-vous fait à côté, même si vous ne pensez pas à ce sujet presque dans cette mesure? Répétez le processus, donc une sorte de boucle. Il y a une idée familière. Voici donc quatre. C'est actuellement le plus petit. C'est un candidat. Plus maintenant. Maintenant, je l'ai vu deux. Voilà l'élément suivant le plus petit. Three-- ce n'est pas plus petit, de sorte maintenant Ben peut arracher les deux. 

Et maintenant, nous répétons le processus et des cours de trois obtient retirée suivant. Répétez le processus. Quatre obtient retirée. Et maintenant, nous sommes sur le nombre, de sorte que la liste doit être triée. 

Et en effet, cela est un algorithme formel. Un informaticien serait appeler cette "sorte de sélection," l'idée étant un genre liste iteratively-- nouveau et encore et encore la sélection le plus petit nombre. Et ce qui est agréable à ce sujet est il est tellement sacrément intuitive. Il est si simple. Et vous pouvez répéter la même opération encore et encore. C'est simple. 

Dans ce cas, il a été rapide, mais combien de temps faut-il réellement prendre? Faisons croire et sentir un peu plus fastidieux. Donc, un, deux, trois, quatre, cinq six, sept, huit, neuf, 10, 11, 12, 13, 14, 15, 16-- nombre arbitraire. Je voulais simplement plus ce temps que juste quatre. Donc, si j'ai un ensemble tas de chiffres maintenant-- il n'a même pas d'importance ce qu'ils soient: LET penser à ce que cette algorithme est vraiment. 

Supposons qu'il y ait un nombre là-bas. Encore une fois, n'a pas d'importance ce que ils sont, mais ils sont aléatoires. Je demande l'algorithme de Ben. Je dois sélectionner le plus petit nombre. Que fais-je? Et je vais physiquement faire cette fois-ci d'agir it out. Regarder, regarder, à la recherche, à la recherche, à la recherche. Seulement le temps que je reçois à la fin de la liste peut Je me rends compte le plus petit nombre était deux cette fois. On est pas dans la liste. Donc, je pose deux. 

Je fais quoi ensuite? Regardant, regardant, regardant, regardant. Maintenant, je trouve le numéro sept, parce que il y a des lacunes dans ces numbers-- mais juste arbitraire. D'accord. Alors maintenant, je peux déposer sept. Regarder regarder, regarder. 

Maintenant, je suis en supposant, bien sûr, que Ben ne avoir la RAM supplémentaire, en sus la mémoire, parce que, bien sûr, Je regarde le même numéro. Certes, je pouvais me suis souvenu tous ces chiffres, et c'est absolument vrai. Mais si Ben se souvient tous des chiffres qu'il a vu, il n'a pas vraiment fait progrès fondamentaux parce qu'il a déjà la capacité de recherche à travers les numéros sur la carte. Se souvenant tous les numéros n'aide pas, parce qu'il peut encore comme un ordinateur seulement regarder, nous l'avons dit, un seul numéro à la fois. Donc, il n'y a aucune sorte de triche là que vous pouvez tirer parti. 

Donc, en réalité, comme je continuer à chercher la liste, Je dois littéralement juste continuer avant et en arrière à travers elle, arrachant le prochain plus petit nombre. Et comme vous pouvez le genre d'inférer de mes mouvements stupides, cela devient juste très fastidieuse très rapidement, et il me semble être revenir en arrière et avant, en arrière un peu. Maintenant, pour être honnête, je ne dois pas aller tout aussi bien, disons see-- pour être juste, Je ne dois marcher tout à fait autant d'étapes à chaque fois. Parce que, bien sûr, comme je sélectionner les numéros de la liste, la liste restante devient plus courte. 

Et donc nous allons réfléchir à combien d'étapes que je suis en fait traipsing à travers chaque fois. Dans le premier cas nous avons eu 16 numéros, et ainsi maximally-- de simplement laisser faire pour un discussion-- Je devais regarder à travers 16 numéros pour trouver le plus petit. Mais une fois que je tirais sur le plus petit nombre, comment longue est la liste restante, bien sûr? Juste 15. Alors, combien de numéros a fait Ben ou moi avons de regarder à travers la deuxième fois? 15, juste pour aller chercher le plus petit. Mais maintenant, bien sûr, la liste est, aussi, inférieure à ce qu'elle était avant. Alors, comment de nombreuses étapes ai-je prendre la prochaine fois? 14 puis 13, puis 12, plus de points, dot, dot, jusqu'à ce que je me retrouve avec un seul. Alors maintenant, un informaticien serait demander, eh bien, qu'est-ce que tous égaux? Elle est égale à fait du béton nombre que nous pourrions certainement faisons arithmétiquement, mais nous voulons parler à propos de l'efficacité des algorithmes un peu plus formulaically, indépendante de combien de temps la liste est. 

Et vous savez quoi? Ceci est 16, mais comme je l'ai dit avant, disons simplement appeler la taille du problème n, où n est un nombre. Peut-être qu'il est 16, peut-être il est trois, peut-être qu'il ya un million. Je ne sais pas. Je ne me soucie pas. Ce que je veux vraiment est une formule que je peux utiliser pour comparer cet algorithme contre d'autres algorithmes que quelqu'un pourrait prétendre sont mieux ou pire. 

Donc, il se trouve, et je ne le savoir de l'école primaire, que cela fonctionne réellement sur le même chose que n sur n plus un sur deux. Et cela arrive à égaler, de Bien sûr, n au carré plus n plus de deux. Donc, si je voulais une formule pour combien d'étapes ont participé à la recherche du tout de ces chiffres, encore et encore et encore et encore, je dirais il est n au carré plus n plus de deux. Mais tu sais quoi? Cela semble juste en désordre. Je veux juste vraiment un sens général des choses. Et vous souvenez peut-être de lycée qu'il y est la notion de la plus haute expression de l'ordre. Lequel de ces termes, la n carré, le n, ou de la moitié, a le plus d'impact au fil du temps? Le plus grand n obtient, qui de ces questions le plus? 

En d'autres termes, si je branche sur un million, n au carré va être le plus probable le facteur dominant, parce que un million de fois lui-même est beaucoup plus grand que plus un million supplémentaire. Donc, vous savez quoi? Ceci est un sacrément grand numéro si vous conciliez un numéro. Cela n'a pas d'importance. Nous allons juste croix oublier dehors et à ce sujet. Et un informaticien dirait que l'efficacité de cet algorithme, est de l'ordre de n squared-- Je veux dire vraiment une approximation. Il est en quelque sorte à peu près n au carré. Au fil du temps, plus et plus grand n obtient, cette est une bonne estimation de ce que le l'efficacité ou le manque d'efficacité de cet algorithme est en réalité. Et je tire cela, bien sûr, du fait de faire le calcul. Mais maintenant, je suis juste en agitant mes mains, parce que je viens veulent un sens général de cet algorithme. 

Donc, en utilisant la même logique, quant à lui, nous allons examiner un autre algorithme nous avons déjà regardé at-- recherche linéaire. Quand je cherchais pour le téléphone book-- pas trier, rechercher par l'intermédiaire du téléphone book-- nous avons continué en disant qu'il était 1000 marches, ou 500 étapes. Mais nous allons généraliser cela. S'il y a n pages le livre de téléphone, ce qui est le temps d'exécution ou de la efficacité de la recherche linéaire? Il est de l'ordre de combien d'étapes pour trouver Mike Smith en utilisant la recherche linéaire, la premier algorithme, ou même la deuxième? 

Dans le pire des cas, Mike est à la fin du livre. Donc, si le répertoire a 1.000 pages, nous avons dit la dernière fois, dans le pire des cas, il pourrait prendre à peu près comment beaucoup de pages pour trouver Mike? Comme 1000. Il est une limite supérieure. Il est une pire situation possible. Mais encore une fois, nous nous éloignons à partir des chiffres comme 1000 maintenant. Il est juste n. 

Alors, quelle est la conclusion logique? Trouver Mike dans un téléphone livre qui a n pages pourrait prendre, dans le pire des cas, combien d'étapes de l'ordre de n? Et en effet, un ordinateur scientifique dirait que le temps d'exécution, ou le rendement ou l'efficacité ou l'inefficacité, d'un algorithme comme une recherche linéaire est de l'ordre de n. Et nous pouvons appliquer le même la logique de traverser quelque chose comme je viens à la seconde algorithme que nous avions avec le livre de téléphone, où nous sommes allés deux pages à la fois. 

Donc 1000 pages annuaire pourrait nous prendre 500 page se tourne, plus un si nous doublons un peu en arrière. Donc, si un livre de téléphone a n pages, mais nous faisons deux pages à la fois, qui est plus ou moins quoi? N plus de deux, de sorte que est comme n sur deux. Mais j'ai fait la demande d'un il y a instant que n sur two-- qui est le genre de même que tout n. Il est juste un facteur constant, les informaticiens diraient. Concentrons uniquement sur les variables, really-- les plus grandes variables de l'équation. 

recherche donc linéaire, se fait un page à la fois ou deux pages à la fois, est une sorte de fondamentalement les mêmes. Il est encore de l'ordre de n. Mais je prétendais avec ma photo précédente que le troisième algorithme n'a pas été linéaire. Ce ne fut pas une ligne droite. Il était cette ligne courbe, et formule algébrique il y avait quoi? Connexion de n-- donc log base deux de n. Et nous ne devons pas aller trop beaucoup de détails sur logarithmes aujourd'hui, mais la plupart des informaticiens ne serait pas même vous dire ce que la base est. Parce qu'il est tout simplement facteurs constants, pour ainsi dire, seulement de légères différences numériques. Et ce serait un très commun façon pour ordinateur particulièrement formelle scientifiques à un conseil ou programmeurs à un tableau blanc fait valoir que algorithme qu'ils utiliseraient ou ce que l'efficacité de leur algorithme est. 

Et ce ne sont pas nécessairement quelque chose vous discutez dans le détail, mais un bon programmeur est quelqu'un qui a un arrière-plan formel solide. Il est capable de parler vous dans ce genre de façon et effectivement faire arguments qualitatifs que les raisons pour lesquelles un algorithme ou une pièce de logiciel est supérieure d'une certaine façon à l'autre. Parce que vous pourriez certainement il suffit d'exécuter le programme d'une personne et compter le nombre de secondes il faut trier certains numéros, et vous pouvez exécuter certains Le programme d'une autre personne et compter le nombre de secondes qu'il faut. Mais ceci est une façon plus générale que vous pouvez utiliser pour analyser des algorithmes, si vous voulez, juste papier ou tout simplement verbalement. Sans même en cours d'exécution, sans même essayer des entrées d'échantillons, vous pouvez simplement raisonner à travers elle. Et ainsi, avec l'embauche d'un développeur ou si qu'il y soit sorte d'argumenter pour vous pourquoi leur algorithme, leur secret sauce pour la recherche des milliards des pages web pour votre la société est mieux, ceux-ci sont les types d'arguments qu'ils devrait idéalement être en mesure de faire. Ou du moins ce sont le genre de choses qui viendrait en discussion, à moins dans une discussion très formelle. D'accord. Donc, Ben a proposé quelque chose appelé sélection tri. Mais je vais proposer qu'il ya d'autres façons de le faire, aussi. Ce que je n'aime vraiment à propos de l'algorithme de Ben est qu'il a continué à marcher, ou ayant moi marcher, aller et retour et en arrière et en arrière. Et si au lieu que je devais faire quelque chose comme ces chiffres ici et je devais traiter seulement avec chaque nombre à son tour que je suis donnée? 

En d'autres mots, voici ma liste de numéros. Quatre, une, trois, deux. Et je vais faire ce qui suit. Je vais insérer les numéros où ils appartiennent plutôt que de les sélectionner un à la fois. En d'autres mots, voici le numéro quatre. 

Voici ma liste originale. Et je vais maintenir essentiellement une nouvelle liste. Donc, c'est l'ancienne liste. Ceci est la nouvelle liste. Je vois le numéro quatre premiers. Ma nouvelle liste est initialement vide, il est donc trivialement le cas que quatre est maintenant la liste assorties. Je prends juste le nombre que je me donne, et je le mettre dans ma nouvelle liste. 

Est-ce que cette nouvelle liste triée? Ouais. Il est stupide parce qu'il n'y a qu'un seul élément, mais il est absolument triée. Il n'y a rien hors de l'endroit. Il est plus intéressant, cet algorithme, quand je passe à l'étape suivante. 

Maintenant, j'ai un. Donc, bien sûr, appartient à la début ou la fin de cette nouvelle liste? Le début. Je dois donc faire un travail maintenant. Je prends un peu libertés avec mon marqueur simplement en tirant les choses où je les veux, mais ce n'est pas vraiment précises dans un ordinateur. Un ordinateur, comme nous le savons, a RAM ou Random Access Memory, et c'est un octet et un autre octet et un autre octet. Et si vous avez un gigaoctet de RAM, vous avez un milliard d'octets, mais ils sont physiquement en un seul endroit. Vous ne pouvez pas déplacer des choses autour en dessinant sur le tableau où tu veux. Donc, si ma nouvelle liste a quatre emplacements en mémoire, malheureusement quatre est déjà dans le mauvais endroit. 

Donc, pour insérer le numéro un Je ne peux pas dessiner ici. n'existe pas cet emplacement mémoire. Ce serait tricher, et je l'ai été tricherie imagée pendant quelques minutes, ici. Alors, vraiment, si je veux mettre un ici, Je dois copier temporairement les quatre et puis mettre celui là. 

Ça va, c'est exact, qui est techniquement possible, mais se rendent compte que ce travail supplémentaire. Je ne viens de mettre le numéro en place. Je devais d'abord déplacer un numéro, puis le mettre en place, donc je sorte de doublé mon volume de travail. Alors garde cela en tête. 

Mais je suis maintenant fait avec cet élément. Maintenant, je veux saisir le numéro trois. Si, bien sûr, appartient-il? Entre. Je ne peux plus tricher et juste le mettre là, parce que, encore une fois, cette mémoire est dans des emplacements physiques. Je dois donc copier les quatre et de mettre les trois ici. Pas un gros problème. Il est juste une étape supplémentaire again-- sent très bon marché. 

Mais maintenant, je passe à deux. Les deux, bien sûr, appartient ici. Maintenant, vous commencez à voir comment le travail peut accumuler. Maintenant, que dois-je faire? Ouais, je dois déplacer les quatre, Je dois ensuite copier les trois, et maintenant je peux insérer les deux. Et la prise de cette algorithme, il est intéressant, est que supposons que nous avons une plus grande cas où il est, disons huit, sept, six, cinq, quatre, trois, deux, un. Ceci est, dans de nombreux contextes, le pire des cas, parce que la chose sacrément est littéralement en arrière. 

Il n'a pas vraiment affecter l'algorithme de Ben, parce que, dans la sélection de Ben sorte qu'il va garder des allers-retours dans la liste. Et parce qu'il était toujours à la recherche à travers toute la liste restante, ça ne fait rien où les éléments se trouvent. Mais dans ce cas avec mon insertion approach-- nous allons essayer cela. 

Donc, une, deux, trois, quatre, cinq, six, sept, huit. Un deux trois quatre, cinq, six, sept, huit. Je vais prendre les huit, et où dois-je le mettre? Eh bien, au début de ma liste, parce que cette nouvelle liste est triée. Et je croise dehors. 

Où dois-je mettre les sept? Mince. Il faut y aller, donc Je dois faire un peu de copie. Et maintenant sept va ici. Maintenant, je passe à six. Il est désormais encore plus de travail. 

Huit doit aller ici. Seven doit aller ici. Maintenant, les six peuvent aller ici. Je prends maintenant cinq. Maintenant, les huit doit aller ici, sept doit aller ici, six doit aller ici, et maintenant cinq et répéter. Et je suis à peu près déplacer constamment. 

Donc, à la fin, ce algorithm-- nous allons appeler insertion sort-- effectivement a beaucoup de travail, aussi. Il est juste différent genre de travail que Ben. Le travail de Ben m'a aller avant et en arrière tout le temps, sélection de la plus petite suivante élément encore et encore. Il était donc ce genre très visuel de travail. 

Cet autre algorithme, qui est toujours correct-- il va faire le travail done-- modifie simplement la quantité de travail. On dirait que vous êtes d'abord sauver, parce que vous êtes juste traiter chaque élément à l'avant sans marcher tout le chemin à travers la liste comme Ben était. Mais le problème est, en particulier dans ces cas fous où il est tout à l'envers, vous êtes juste un peu retarder le travail acharné jusqu'à ce que vous devez corriger vos erreurs. 

Et donc si vous pouvez imaginer ce huit et sept et six et cinq puis trois et quatre, et deux déplacer leur chemin à travers la liste, nous venons tout juste changé le type de travail que nous faisons. Au lieu de le faire à la à partir de mon itération, Je suis juste le faire à la la fin de chaque itération. Ainsi, il apparaît que cet algorithme, trop, généralement appelé tri par insertion, est également de l'ordre de n au carré. Il est en fait pas mieux, pas mieux du tout. 

Cependant, il y a une troisième approche Je voudrais nous encourager à envisager, qui est-ce. Supposons donc que ma liste, pour la simplicité encore, est de quatre, une, trois, two-- seulement quatre numéros. Ben avait une bonne intuition, bonne intuition humaine avant, par lequel nous avons fixé l'ensemble liste eventually-- tri par insertion. Je nous cajolé le long. Mais nous allons examiner la manière la plus simple de fixer cette liste. 

Cette liste ne sont pas triées. Pourquoi? En anglais, expliquer pourquoi il est pas réellement triée. Qu'est-ce que cela signifie de ne pas être triés? 

ÉTUDIANT: Il est pas séquentiel. 

DAVID MALAN: Non séquentiel. Donne moi un exemple. 

ÉTUDIANTS: Mettez-les dans l'ordre. 

DAVID MALAN: OK. Donnez-moi un exemple plus précis. 

ÉTUDIANTS: Ascendant. DAVID MALAN: Non ordre croissant. Soyez plus précis. Je ne sais pas ce que vous entendez par ordre croissant. Qu'est-ce qui ne va pas? 

ÉTUDIANTS: Le plus petit de la les numéros ne sont pas dans le premier espace. 

DAVID MALAN: Le plus petit nombre de pas dans le premier espace. Sois plus spécifique. Je commence à faire son chemin. Nous comptons, mais ce qui est hors d'ici? 

ÉTUDIANTS: séquence numérique. DAVID MALAN: séquence numérique. le genre de tenue de tout le monde il ici-- de très haut niveau. Dis-moi juste littéralement ce qui est tort comme une puissance de cinq ans. 

ÉTUDIANTS: Plus un. 

DAVID MALAN: Qu'est-ce que? 

ÉTUDIANTS: Plus un. 

DAVID MALAN: Qu'entendez-vous plus un? Donnez-moi un autre cinq ans. Qu'est-ce qui ne va pas, maman? Qu'est-ce qui ne va pas, papa? Que voulez-vous dire ce ne sont pas triées? 

ÉTUDIANT: Il est pas le bon endroit. 

DAVID MALAN: Quelle est pas à la bonne place? 

ÉTUDIANTS: Quatre. DAVID MALAN: OK, bon. Donc quatre est pas où il devrait être. En particulier, est-ce exact? Quatre et le premier deux chiffres que je vois. Est-ce correct? Non, ils sont hors d'usage, non? En fait, maintenant penser d'un ordinateur, aussi. Il ne peut que regarder peut-être un, peut-être deux choses à once-- et en fait une seule chose à un moment, mais il peut au moins regarder une chose alors la prochaine chose juste à côté. 

Ainsi sont-elles en ordre? Bien sûr que non. Donc, vous savez quoi? Pourquoi ne prenons pas de bébé étapes de fixation de ce problème au lieu de faire ces fantaisie des algorithmes comme Ben, où il est en quelque sorte de le fixer par une boucle à travers la liste au lieu de faire ce que je faisais, où Je viens de sorte de le fixe que nous allons? Disons simplement briser littéralement en bas de la notion d'ordre numérique order--, appeler tout ce que vous want-- dans ces comparaisons par paires. 

Quatre et un. Est-ce le bon ordre? Donc, nous allons corriger cela. Un et quatre, puis nous allons simplement copier cela. Bon, bon. Je fixe un et quatre. Trois et deux? Non. Que mes mots correspondent mes doigts. Quatre et trois? 

Il est pas dans l'ordre, alors je vais de faire un, trois, quatre, deux. OK, bien. Maintenant, quatre et deux? Nous devons résoudre ce problème, aussi. Donc un, trois, deux, quatre. Ainsi est-il réglé? Non, mais est-il plus proche de tri? 

Il est, parce que nous avons fixé cette erreur, nous avons corrigé cette erreur, et nous avons corrigé cette erreur. Donc, nous avons fixé trois erreurs sans doute. Encore ne pas vraiment regarder triée, mais il est objectivement plus proche de tri parce que nous avons corrigé certaines de ces erreurs. 

Maintenant, que dois-je faire? Je genre de arrivé à la fin de la liste. Il me semblait avoir fixé toutes les erreurs, mais non. Parce que dans ce cas, certains numéros auraient pu barboter jusqu'à rapprocher d'autres numéros sont encore hors d'usage. Donc, nous allons le faire à nouveau, et je vais il suffit de faire en place cette fois. Une et trois? C'est bien. Trois et deux? Bien sûr pas, donc nous allons changer cela. Donc, deux, trois. Trois et quatre? Et maintenant, nous allons juste être particulièrement pédant ici. Est-il réglé? Vous savez les humains est triée. 

Je devrais essayer à nouveau. Alors Olivia propose je tente à nouveau. Pourquoi? Parce qu'un ordinateur ne dispose pas le luxe de nos yeux humains de simplement en regardant back-- OK, je suis fait. Comment l'ordinateur déterminer que la liste est maintenant triée? Mécaniquement. 

Je devrais passer par Encore une fois, et seulement si je ne pas faire / trouver toutes les erreurs que je peux puis conclure que l'ordinateur, yep, nous sommes bons pour aller. Donc, un et deux, deux et trois, trois et quatre. Maintenant, je peux définitivement dire que c'est triés, parce que je fait aucun changement. Maintenant, ce serait un bug et juste fou si je, l'ordinateur, demandé à nouveau ces mêmes questions attend des réponses différentes. Ne devrait pas se produire. 

Et maintenant la liste est triée. Malheureusement, le temps de courir cet algorithme est également n carré. Pourquoi? Parce que vous avez n nombres, et dans la pire des cas, vous devez déplacer n nombres n fois parce que vous devez continuer en arrière pour vérifier et éventuellement corriger ces chiffres. Et nous pouvons faire plus analyse formelle, aussi. 

Donc, tout cela est de dire que nous avons pris trois approches différentes, l'une d'entre eux immédiatement intuitive le départ de Ben à mon insertion suggérée sorte à celui-ci où vous sorte de perdre de vue la forêt pour les arbres initialement. Mais alors, si vous prenez un peu de recul, voila, nous avons fixé la notion de tri. Donc, cela est, ose dire, un niveau inférieur peut-être que certains de ces autres algorithmes, mais nous allons voir si nous ne pouvons pas visualiser ceux-ci par le biais de cette. 

Donc, cela est un peu agréable logiciel que quelqu'un écrit en utilisant des barres colorées qui est va faire ce qui suit pour nous. Chacune de ces barres représente un nombre. Taller la barre, plus le nombre, plus la barre, plus le nombre. Donc, idéalement, nous voulons une pyramide belle où il commence petit et obtient grand, et cela signifierait que ces barres sont triées. Je vais donc aller de l'avant et de choisir, par exemple, l'algorithme de Ben first-- sorte de sélection. 

Et remarquez ce qu'il fait. La façon dont ils ont choisi de visualiser cet algorithme est que, tout comme moi marchant dans ma liste, ce programme marche à travers sa liste de numéros, soulignant en rose chaque numéro qu'il regarde. Et ce qui va se passer maintenant? 

Le plus petit nombre qui I ou Ben soudain trouvé est déplacé vers le début de la liste. Et ils l'ont fait expulser préavis le nombre qui était là, et c'est parfaitement bien. Je ne suis pas entrer dans ce niveau de détail. Mais nous avons besoin de mettre ce nombre quelque part, alors nous avons déménagé à la endroit ouvert qui a été créé. Donc, je vais accélérer ce , parce que sinon il devient très fastidieux rapidement. Animations speed-- nous y aller. Alors maintenant, même principe J'a été l'application, mais vous peut commencer à se sentir l'algorithme, si vous sera, ou voir un peu plus clair. Et cet algorithme a pour effet de la sélection du prochain élément le plus petit, de sorte que vous allez commencer à le voir monter en puissance sur la gauche. Et à chaque itération, comme je proposé, il fait un peu moins de travail. Il n'a pas besoin d'aller tout le chemin retour à l'extrémité gauche de la liste, parce qu'il a déjà connaît ceux qui sont triés. Donc, ce genre de sent comme il est accélère, même si chaque étape est en prenant la même quantité de temps. Il y a seulement moins d'étapes restantes. Et maintenant, vous pouvez sorte de sentir la algorithme de nettoyage à la fin de celui-ci, et même maintenant il est trié. 

Donc, le tri par insertion est tout fait. Je dois re-randomiser le tableau. Et remarquez que je peux juste garder randomisation il, et nous obtenons une approximation de la même approche, le tri par insertion. Permettez-moi de ralentir ici. Commençons que plus. Arrêtez. 

Sautons quatre. Nous y voilà. Randomize ils tableau. Et ici, nous go-- tri par insertion. Jouer. Notez qu'il a affaire à chaque élément qu'il rencontre tout de suite, mais si elle appartient à le lieu préavis mal tout le travail qui doit se produire. Nous devons continuer à déplacer plus et plus d'éléments pour faire de la place pour celui que nous voulons mettre en place. 

Nous sommes donc en se concentrant sur la extrémité gauche de la liste seulement. Notez que nous avons même pas regardé at-- nous ne sont pas mis en évidence dans quoi que ce soit rose à droite. Nous sommes en train de traiter avec les problèmes que nous allons, mais nous créons beaucoup de travailler pour nous-mêmes encore. Et donc si nous accélérons cette place maintenant aller à la fin, il a une sensation différente à elle en effet. Il est juste en se concentrant sur l'extrémité gauche, mais faire un peu plus de travail que needed-- genre de choses de lissage plus, réparer les choses, mais en fin de compte traiter avec chaque élément un à la fois jusqu'à ce que nous arrivons à bien the--, nous savons tous comment cela va se terminer, il est donc un peu décevant peut-être. 

Mais la liste dans le end-- spoiler-- va être triée. Alors regardons un dernier. Nous ne pouvons pas ignorer maintenant. Nous y sommes presque. Deux aller, un pour aller. Et voila. Excellent. 

Alors maintenant, nous allons faire une dernière, re-randomisation avec tri à bulles. Et remarque ici, surtout si je ralentis il vers le bas, cela ne tient élancées à travers. Mais remarquez il est tout simplement pairwise Tri comparisons-- de solutions locales. Mais dès que nous arrivons à la fin de la liste en rose, ce qui va devoir se reproduire? Ouais, il va devoir recommencer, car il ne erreurs appariées fixes. Et qui aurait pu encore révélé d'autres. Et donc si vous accélérez cette place, vous aurez voir que, tout comme le nom l'indique, la plus petite elements-- ou plutôt les elements-- plus grandes commencent bouillonner vers le haut, si vous voulez. Et les plus petits éléments sont commencer à faire des bulles vers le bas à gauche. Et en effet, que ce genre de l'effet visuel ainsi. Et cela va finir par finir d'une manière très similaire aussi. 

Nous ne devons pas demeurer sur celui-ci en particulier. Permettez-moi d'ouvrir maintenant, aussi. Il y a quelques autres algorithmes de tri dans le monde, dont quelques-unes sont capturés ici. Et surtout pour les apprenants qui ne sont pas forcément visuel ou mathématique, comme nous l'avons fait avant, nous pouvons aussi faire ce déficients auditifs si nous associons un son avec cela. Et juste pour le plaisir, voici un quelques algorithmes différents, et l'un d'eux en particulier que vous êtes va à remarquer que l'on appelle «tri par fusion." 

Il est en fait un fond meilleur algorithme, de telle sorte que le tri par fusion, l'un des ceux que vous êtes sur le point de voir, est pas l'ordre de n au carré. Il est de l'ordre de n fois log de n, ce qui est en fait plus petite et donc plus rapidement que ceux des trois autres. Et il y a un autre couple les stupides que nous allons voir. 

Alors on y va avec un certain bruit. Ceci est le tri par insertion, de sorte à nouveau il est juste traiter avec les éléments comme ils viennent. Ceci est tri à bulles, il est donc les considérant paires à la fois. Et encore, les plus grands éléments sont jaillissant vers le haut. 

Ensuite sélection tri. Ceci est l'algorithme de Ben, où de nouveau, il est la sélection itérative le prochain plus petit élément. Et encore une fois, vous pouvez maintenant vraiment entendre que il est l'accélération, mais seulement dans la mesure où comme il est fait de moins en moins travailler à chaque itération. Ceci est la plus rapide un, le tri par fusion, qui est le tri des groupes de nombres les combiner ensemble et ensuite. Si la gauche look-- la moitié est déjà trié. 

Maintenant, il est le tri de la moitié droite, et maintenant il va les combiner en un seul. Ceci est quelque chose appelé "Gnome genre." Et vous pouvez sorte de voir que ça va-et-vient, fixant le travail un peu ici et il avant qu'il ne procède à de nouveaux travaux. Et c'est tout. Il y a une autre sorte, qui est vraiment juste à des fins académiques, appelé «sorte stupide» qui prend vos données, trie au hasard, et vérifie ensuite si elle est triée. Et si ce n'est pas, il re-trie au hasard, vérifie si elle est triée, et sinon répète. Et en théorie, probabilistically cela va compléter, mais après un peu de temps. Il est pas le plus efficace des algorithmes. Donc, des questions sur les algorithmes ou tout particulier il lié aussi? 

Eh bien, nous allons maintenant taquiner à part ce que tout ces lignes sont que je dessine et ce que je suis en supposant que l'ordinateur peut faire sous le capot. Je dirais que tous ces chiffres Je garde drawing-- dont ils ont besoin pour obtenir stockés quelque part dans la mémoire. Nous allons nous débarrasser de ce gars maintenant, aussi. 

Ainsi, une partie de mémoire dans un computer-- donc RAM DIMM est ce que nous avons cherché hier, double inline memory module-- ressemble à ceci. Et chacun de ces petits jetons noirs est un certain nombre d'octets, typiquement. Et puis les broches d'or sont comme le fils qui se connectent à l'ordinateur, et le conseil de silicium vert est juste ce qui maintient tout tous ensemble. Alors qu'est-ce que cela signifie vraiment? Si je sorte de tire cette même image, Supposons pour simplifier que ce DIMM, dual Module de mémoire en ligne, est un gigaoctet de RAM, un gigaoctet de la mémoire, ce qui est le nombre d'octets total? Un gigaoctet est combien d'octets? Plus que ça. 1124 est le kilo, 1000. Mega est millions. Giga est un milliard. 

Suis-je mens? Peut-on même lire l'étiquette? Ceci est en fait 128 gigaoctets, il est donc plus. Mais nous prétendons cette est juste un gigaoctet. Donc, cela signifie qu'il ya un milliard octets de mémoire disponibles pour me ou 8 milliards de bits, mais nous allons pour parler en termes d'octets maintenant, avancer. 

Alors qu'est-ce que cela signifie est cela est un octet, ceci est un autre octet, ceci est un autre octet, et si nous voulions vraiment pour être précis, nous aurions à tirer un milliard de petits carrés. Mais qu'est ce que ça veut dire? Eh bien, permettez-moi de zoom sur cette photo. Si je dois quelque chose qui ressemble comme ça maintenant, c'est de quatre octets. 

Et pour que je puisse mettre quatre chiffres ici. Un deux trois quatre. Ou je pourrais mettre quatre lettres ou des symboles. "Hey!" pourrait aller là, parce que chacune des lettres, nous avons discuté plus tôt, pourraient être représentés avec huit bits ou ASCII ou un octet. Donc, en d'autres termes, vous pouvez mettre 8 milliards choses à l'intérieur de celui-ci bâton de mémoire. Maintenant, qu'est-ce que cela signifie pour remettre les choses à dos à dos dans la mémoire comme ça? Ceci est ce qu'un programmeur appellerait un «tableau». Dans un programme d'ordinateur, vous ne pensez pas le matériel utilisé, en tant que tel. Vous pensez juste de vous-même comme ayant l'accès à un total milliard d'octets, et vous pouvez tout ce que vous voulez avec elle. Mais pour plus de commodité il est généralement utile pour garder votre droit de mémoire à côté de l'autre comme ça. Donc, si je zoome sur this-- parce que nous allons certainement pas de tirer un milliard de petits squares-- supposons que ce conseil représente ce bâton de mémoire maintenant. Et je vais dessiner autant que mon marqueur finit par me donner ici. Nous avons donc maintenant un bâton de mémoire sur la carte qui a obtenu un, deux, trois, quatre, cinq, six, un, deux, trois, quatre, cinq, six, seven-- donc 42 octets de mémoire sur le total de l'écran. Je vous remercie. Oui, a fait mon arithmétique droite. Donc, 42 octets de mémoire ici. Alors qu'est-ce que cela signifie réellement? Eh bien, un programmeur informatique serait en fait généralement penser de cette mémoire adressable. En d'autres termes, chacun de ceux-ci emplacements en mémoire, dans le matériel, a une adresse unique. 

Il est pas aussi complexe que One Brattle Square, Cambridge, Mass., 02138. Au lieu de cela, il est juste un nombre. Ceci est l'octet numéro zéro, cela est l'un, cela est deux, cela est trois, et cela est 41. Attends une minute. Je pensais que je l'ai dit 42 il y a un instant. Je commencé à compter à zéro, de telle sorte que est en fait correcte. Maintenant, nous ne devons pas réellement dessiner comme une grille, et si vous dessinez comme une grille Je pense que les choses effectivement obtenir un peu trompeur. Quel programmeur, dans son propre esprit, pense généralement de cette mémoire est comme une bande, comme un morceau de ruban adhésif de masquage qui va juste encore et toujours ou jusqu'à ce que vous manquez de mémoire. Donc, d'une manière plus commune pour dessiner et il suffit de penser la mémoire serait que ce soit l'octet zéro, un, deux, trois, puis dot, dot, dot. Et vous avez 42 ces octets au total, même bien physiquement, il pourrait effectivement être quelque chose de plus comme ça. 

Donc, si vous pensez maintenant de votre mémoire comme cela, tout comme une bande, c'est ce qu'un programmeur à nouveau appellerait un tableau de mémoire. Et quand vous voulez stocker effectivement quelque chose dans la mémoire d'un ordinateur, vous faites généralement les choses en magasin back-to-back to back-to-back. Donc, nous avons parlé de chiffres. Et quand je voulais résoudre les problèmes comme quatre, un, trois, deux, même si je viens de dessiner seul le nombre de quatre, un, trois, deux sur le bord, l'ordinateur serait vraiment avoir cette configuration en mémoire. 

Et ce serait à côté de la deux dans la mémoire de l'ordinateur? Eh bien, il n'y a pas de réponse à cela. Nous ne savons pas vraiment. Et tant que le ordinateur n'a pas besoin, il n'a pas à prendre soin de ce qui est à côté les chiffres, il se soucie. Et quand je l'ai dit plus tôt qu'un ordinateur peut seulement regarder une adresse à la fois, c'est un peu pourquoi. 

Pas contrairement à un record joueur et une tête de lecture seulement être capable de regarder à un certain rainure dans un enregistrement physique de la vieille école à la fois, de la même peut un ordinateur grâce à son processeur et sa Intel jeu d'instructions, parmi dont l'instruction est lue dans la mémoire ou enregistrer memory-- un ordinateur ne peut que regarder à un endroit à un time-- parfois une combinaison d'entre eux, mais vraiment juste un endroit à la fois. Alors, quand nous faisions ces différents algorithmes, Je ne suis pas en train d'écrire dans un vacuum-- quatre, un, trois, deux. Ces chiffres appartiennent effectivement quelque part physique en mémoire. Donc, il y a tout petit transistors ou une sorte de l'électronique sous le hotte stocker ces valeurs. 

Et au total, combien de bits sont impliqué dès maintenant, juste pour être clair? Voilà donc quatre octets, ou il est maintenant de 32 bits au total. Donc, il y a effectivement 32 zéros et ceux qui composent ces quatre choses. Il y a encore plus ici, mais encore une fois nous ne nous soucions pas. 

Alors maintenant, nous allons demander une autre question en utilisant la mémoire, parce que, à la fin de la journée est la variance. Peu importe ce que nous pourrions faire avec l'ordinateur, à la fin de la journée le matériel est toujours le Même sous la hotte. Comment pourrais-je stocker un mot ici? Eh bien, un mot dans un ordinateur comme "Hey!" seraient stockés comme ça. Et si vous vouliez une plus mot, vous pouvez simplement écraser et dire quelque chose comme "bonjour" et un magasin ici. 

Et ici aussi, cette contiguïté est en fait un avantage, parce qu'un ordinateur peut simplement lire de droite à gauche. Mais voici une question. Dans le cadre de ce mot, h-e-l-l-o, point d'exclamation, comment l'ordinateur peut savoir où le mot commence et où le mot se termine? Dans le contexte de nombres, comment fonctionne l'ordinateur savoir combien de temps la séquence de numéros est ou où il commence? Eh bien, il se out-- et nous ne rentrerons pas trop dans ce niveau de detail-- ordinateurs déplacent choses autour de la mémoire littéralement par le biais de ces adresses. Donc, dans un ordinateur, si vous êtes écriture de code pour stocker les choses comme des mots, ce que vous êtes vraiment faire est de taper expressions qui rappellent où, en la mémoire de l'ordinateur sont ces mots. Alors laissez-moi faire une très, exemple très simple. 

Je vais aller de l'avant et ouvrir un programme de texte simple, et je vais créer un fichier appelé hello.c. La plupart de ces informations, nous ne va pas dans en détail, mais je vais écrire un programme dans cette même langue, C. Ceci est beaucoup plus intimidant, Je dirais, que Scratch, mais il est très similaire dans l'esprit. En fait, ces bouclés braces-- vous pouvez sorte de penser à ce que je viens de le faire comme cela. 

Faisons cela, en fait. Lorsque le drapeau vert cliqué, procédez comme suit. Je veux imprimer «bonjour». Donc, cela est maintenant pseudocode. Je suis une sorte de brouiller les lignes. En C, cette langue je parle à propos, cette ligne d'impression bonjour devient réalité "printf" avec des parenthèses et un point-virgule. 

Mais il est la même idée exacte. Et ce très convivial "Lorsque le drapeau vert cliqué" devient le plus mystérieux "void main int." Et cela n'a vraiment aucune cartographie, donc je vais juste l'ignorer. Mais les accolades sont comme le pièces de puzzle courbes comme celle-ci. 

Ainsi, vous pouvez sorte de deviner. Même si vous ne l'avez jamais programmé avant, qu'est-ce que ce programme probablement faire? imprime Probablement bonjour avec un point d'exclamation. 

Essayons donc cela. Je vais l'enregistrer. Et cela est, encore une fois, une très environnement old school. Je ne peux pas cliquer, je ne peux pas glisser. Je dois taper des commandes. Donc, je veux courir mon programme, de sorte Je pourrais le faire, comme hello.c. C'est le fichier que je courais. Mais attendez, je manque une étape. Qu'est-ce que nous disons est une condition nécessaire étape pour un langage comme C? Je viens de source écrite code, mais que dois-je? Ouais, je besoin d'un compilateur. Donc, sur mon Mac ici, j'ai un programme appelé GCC, compilateur GNU C, ce qui me permet de faire this-- tour mon code source en, nous allons l'appeler, langage machine. 

Et je peux voir que, encore une fois, comme suit, ceux-ci sont les zéros et ceux que je viens créé à partir de mon code source, tous les zéros et des uns. Et si je veux courir mon program-- il arrive d'être appelé a.out pour reasons-- historique "bonjour." Je peux courir à nouveau. Bonjour bonjour bonjour. Et il semble fonctionner. 

Mais cela signifie que quelque part dans mon la mémoire de l'ordinateur sont les mots h-e-l-l-o, point d'exclamation. Et il se trouve, tout comme un côté, ce qu'un ordinateur serait généralement faire ce qu'il sait où les choses commencent et end-- il est va mettre un symbole spécial ici. Et la convention est de mettre la Numéro de zéro à la fin d'un mot de sorte que vous savez où il se termine en fait, de sorte que vous ne gardez pas l'impression de plus en plus caractères que vous avez l'intention réellement. 

Mais les plats à emporter ici, même bien que ce soit assez obscur, est qu'il est en fin de compte relativement simple. On vous a donné une sorte de bande, une ébauche l'espace sur lequel vous pouvez écrire des lettres. Vous devez simplement avoir un symbole spécial, comme arbitraire le nombre zéro, de mettre à la fin de vos mots afin que l'ordinateur sait, oh, je devrais arrêter l'impression après Je vois le point d'exclamation. Parce que la chose suivante, il y est une valeur ASCII de zéro, ou le caractère nul comme quelqu'un l'appeler. Mais il y a une sorte de problème ici, et nous allons revenir à des numéros pour un moment. Supposons que je fais, en fait, avoir un tableau de nombres, et supposons que le programme que je vous écris est comme un carnet de notes pour un enseignant et une salle de classe des enseignants. Et ce programme lui permet taper les scores de leurs élèves sur des questionnaires. Et supposons que l'étudiant obtient 100 sur leur premier jeu-questionnaire, peut-être comme un 80 sur le prochain, puis un 75, puis un 90 sur le quatrième quiz. 

Donc, à ce moment de l'histoire, le tableau est de taille quatre. Il n'y a absolument plus de mémoire dans le ordinateur, mais le tableau, pour ainsi dire, est de taille quatre. Supposons maintenant que l'enseignant veut d'attribuer un cinquième jeu-questionnaire à la classe. Eh bien, l'une des choses qu'il ou elle va avoir à faire est maintenant stocker une valeur supplémentaire ici. Mais si le tableau l'enseignant créé dans ce programme est de taille pour, l'un des problèmes avec un tableau est que vous ne pouvez pas continuer à ajouter à la mémoire. Parce que si une autre partie de la programme a le mot "hey" juste là? 

En d'autres termes, la mémoire peut être ma utilisé pour quoi que ce soit dans un programme. Et si à l'avance que je tapé, hey, Je veux entrée quatre scores de quiz, ils pourraient aller ici et ici. Et si vous changez soudainement votre esprit plus tard et dire que je veux un cinquième jeu-questionnaire score, vous ne pouvez pas simplement mettre où vous voulez, parce que si cela La mémoire est utilisée pour quelque chose else-- un autre programme ou une autre caractéristique du programme que vous êtes en cours d'exécution? Donc, vous devez penser à l'avance comment vous souhaitez stocker vos données, parce que maintenant vous avez peint vous dans un coin numérique. 

Ainsi, un enseignant pourrait à la place dire lors de l'écriture d'un programme pour stocker son grades, vous savez quoi? Je vais demander, lors de l'écriture de mon programme, que je veux zéro, un, deux, trois, quatre, cinq, six, huit classes au total. Donc, une, deux, trois, quatre, cinq, six, sept, huit. L'enseignant peut simplement trop affecter la mémoire lors de l'écriture de son programme et dire, vous savez quoi? Je ne vais jamais affecter plus de huit questionnaires en un semestre. C'est tout simplement fou. Je ne serai jamais allouer cela. Alors que cette façon dont il ou elle a le flexibilité aux scores magasin d'étudiants, comme 75, 90, et peut-être un supplémentaire où l'étudiant a obtenu un crédit supplémentaire, 105. 

Mais si l'enseignant ne utilise ces trois espaces, il y a une livraison intuitive ici. Il ou elle est juste de gaspiller l'espace. Donc, en d'autres termes, il y a cette compromis commun dans la programmation où vous pouvez allouer exactement autant de mémoire que vous voulez, la hausse qui est que vous êtes super efficient-- vous n'êtes pas gaspiller à tous-- mais l'inconvénient qui est ce que si vous changez votre esprit lorsque en utilisant le programme que vous souhaitez stocker plus de données que vous avez initialement prévu. 

Alors peut-être la solution, puis, écrire vos programmes de manière qu'ils utilisent plus de mémoire que ce qu'ils ont réellement besoin. De cette façon, tu ne vas pas à courir dans ce problème, mais vous êtes gaspiller. Et plus la mémoire de votre programme utilise, comme nous avons discuté hier, moins la mémoire qui est disponible pour d'autres programmes, le plus tôt votre ordinateur peut ralentir à cause de la mémoire virtuelle. Et donc la solution idéale pourrait être quoi? 

Sous-allocation semble mauvais. Over-allocation semble mauvais. Alors, que peut-être une meilleure solution? Réaffectation. Soyez plus dynamique. Ne vous forcez pas à choisir un priori, au début, ce que vous voulez. Et certainement ne pas trop affecter, de peur que vous être un gaspillage. 

Et pour atteindre cet objectif, nous besoin de jeter cette structure de données, pour ainsi dire, loin. Et qu'est-ce qu'un programmeur utilisera habituellement est ce qu'on appelle pas un tableau, mais une liste liée. En d'autres termes, il ou elle sera commencer à penser à leur mémoire comme étant une sorte de forme qu'ils peut tirer de la manière suivante. Si je veux mémoriser un numéro dans un program-- il est donc Septembre, J'ai donné à mes élèves un questionnaire; je veux pour stocker premier quiz les étudiants, et ils ont obtenu 100 sur it-- I je vais demander à mon ordinateur, par le biais du programme que j'ai écrite, pour une partie de la mémoire. Et je vais stocker le numéro 100 en elle, et voilà. 

Puis, quelques semaines plus tard quand je reçois mon deuxième jeu-questionnaire, et il est temps de taper en ce que 90%, je vais de demander à l'ordinateur, hé, ordinateur, puis-je avoir un autre morceau de la mémoire? Ça va me donner cette morceau vide de la mémoire. Je vais mettre dans le numéro 90, mais dans mon programme d'une façon ou other-- et nous n'inquiéter la syntaxe pour this-- je besoin en quelque sorte enchaîner ces choses ensemble. Et je vais les enchaîner avec ce qui ressemble à une flèche ici. 

Le troisième questionnaire qui se lève, Je vais dire, hé, ordinateur, me donner une autre partie de la mémoire. Et je vais mettre bas quoi qu'il en soit, comme 75, et je dois chaîne cette ensemble maintenant en quelque sorte. Quatrième questionnaire vient le long, et peut-être qui est à la fin du semestre. Et en ce moment-là mon programme pourrait être en utilisant la mémoire partout, sur tout physiquement. Et juste pour le plaisir, je suis va tirer cette suite quiz-- j'oublie ce qu'il était; je pensez peut-être un 80 ou quelque chose-- venant ici. 

Mais ça va, parce que picturalement Je vais dessiner cette ligne. En d'autres termes, dans la réalité, dans le matériel de votre ordinateur, le premier score pourrait finir ici parce qu'il est dès le début du semestre. Le prochain pourrait finir ici parce qu'un peu de temps a passé et le programme continue à fonctionner. La prochaine partition, qui était 75, peut-être ici. Et le dernier résultat pourrait être 80, qui est ici. 

Donc, en réalité, physiquement, cela pourrait être ce que la mémoire de votre ordinateur ressemble. Mais ce n'est pas un mental utile paradigme pour un programmeur informatique. Pourquoi devriez-vous prendre soin où le heck vos données est de se retrouver? Vous voulez juste pour stocker des données. 

Ceci est un peu comme notre discussion antérieure du dessin du cube. Pourquoi tenez-vous ce l'angle est du cube et comment vous devez tourner à dessiner? Vous voulez juste un cube. De même ici, vous je veux juste carnet de notes. Vous voulez juste de penser à ceci comme une liste de numéros. Qui se soucie de la façon dont il est mis en œuvre en matériel? 

Donc, l'abstraction maintenant est cette image ici. Ceci est une liste liée, comme un programmeur appellerait, dans la mesure où vous avez un liste, de toute évidence des nombres. Mais il est lié picturalement par l'intermédiaire de ces flèches, et toutes ces flèches soient: sous le capot, si vous êtes curieux, rappeler que notre matériel physique a adresses zéro, un, deux, trois, quatre. Toutes ces flèches sont comme une carte est ou directions, où si 90 est-- maintenant Je dois compter. 

Zéro, un, deux, trois, quatre, cinq, six, sept. Il semble que le 90 est à adresse mémoire numéro sept. Toutes ces flèches sont est comme un petit morceau de papier que cela donne des directives à la programme qui dit suivre cette carte pour se rendre à l'emplacement sept. Et là, vous trouverez la deuxième score du quiz de l'étudiant. Pendant ce temps, le 75-- si je continue ce, c'est de sept, huit, neuf, 10, 11, 12, 13, 14, 15. 

Cette autre flèche représente juste une carte à l'emplacement de mémoire 15. Mais encore une fois, le programmeur le fait généralement ne se soucient pas ce niveau de détail. Et dans la plupart de chaque programmation langue aujourd'hui, le programmeur ne savent même pas où en mémoire ces chiffres sont en réalité. Tout ce qu'il ou elle doit prendre en compte est qu'ils sont en quelque sorte liés ensemble dans une structure de données comme celui-ci. 

Mais il se trouve pas pour obtenir trop technique. Mais juste parce que nous pouvons peut-être permettre d'avoir cette discussion ici, supposons que nous revisitons cette question ici d'une matrice. Voyons voir si nous regrettons de venir ici. Ceci est de 100, 90, 75 et 80. 

Permettez-moi brièvement faire cette affirmation. Ceci est un tableau, et encore une fois, la caractéristique saillante d'un tableau est que toutes vos données est de retour à dos à dos dans memory-- littéralement un octet ou peut-être quatre octets, un nombre fixe d'octets loin. Dans une liste liée, que nous pourrions tirer comme celui-ci, sous le capot qui sait où ce genre de choses est? Il n'a même pas besoin de couler comme ça. Certaines des données pourrait être Retour à la gauche là-haut. Vous ne savez même pas. 

Et ainsi, avec un tableau, vous avez un fonctionnalité appelée accès aléatoire. Et quels moyens d'accès aléatoire est que l'ordinateur peut sauter instantanément à tout emplacement dans une matrice. Pourquoi? Parce que l'ordinateur sait que le premier emplacement est zéro, un, deux et trois. 

Et donc si vous voulez aller de cet élément à l'élément suivant, vous littéralement, dans le l'esprit de l'ordinateur, il suffit d'ajouter un. Si vous voulez aller au troisième élément, il suffit d'ajouter One-- élément suivant, juste ajoute un. Toutefois, dans cette version, de l'histoire, supposons l'ordinateur est actuellement à la recherche à ou de traiter avec le numéro 100. Comment obtenez-vous à la prochaine grade dans le carnet de notes? 

Vous devez prendre sept étapes, qui est arbitraire. Pour se rendre à la suivante, vous devez prendre encore huit étapes pour arriver à 15. En d'autres termes, il est pas un écart constant entre les nombres, et donc il faut juste le ordinateur plus de temps est le point. L'ordinateur doit rechercher à travers la mémoire afin pour trouver ce que vous cherchez. 

Ainsi, alors que un tableau tend à être un structure-- de données rapide parce que vous peut littéralement faire des calculs simples et obtenir où vous voulez en ajoutant un, pour instance-- une liste liée, vous sacrifiez cette fonctionnalité. Vous ne pouvez pas simplement aller de la première à la seconde au troisième à la quatrième. Vous devez suivre la carte. Vous devez prendre plusieurs étapes pour arriver à ces valeurs, qui semble être l'ajout d'un coût. Donc, nous payons un prix, mais ce qui était la fonctionnalité que Dan cherchait ici? Qu'est-ce que une liste chaînée apparemment nous permettent de faire, qui était à l'origine de cette histoire? 

Exactement. Une taille dynamique pour elle. Nous pouvons ajouter à cette liste. On peut même réduire la liste, que nous sommes seulement en utilisant autant de mémoire que nous voulons réellement et ainsi nous ne sommes jamais trop allocation. 

Maintenant, juste pour être vraiment tatillon, il y a un coût caché. Donc, vous ne devriez pas laisser juste me convaincre vous que ceci est un compromis convaincant. Il y a un autre coût caché ici. L'avantage, pour être clair, est que nous obtenons dynamisme. Si je veux un autre élément, je peux juste dessiner et de mettre un certain nombre là-bas. Et puis je peux relier avec une photo ici, alors ici, encore une fois, si je l'ai moi-même peint dans un coin, si quelque chose est déjà utilisé la mémoire ici, je suis hors de la chance. Je me suis peint dans le coin. 

Mais ce qui est caché coût dans cette image? Il n'y a pas que le montant du temps qu'il faut pour aller d'ici à là, qui est sept étapes, puis huit étapes, ce qui est plus d'un. Quel est un autre coût caché? Non seulement le temps. Des informations supplémentaires sont nécessaire pour atteindre cette image. 

Oui, cette carte, ces petits bouts de papier, que je garde les décrivant comme. Ces arrows-- ceux qui ne sont pas libres. A computer-- vous savez ce qu'un ordinateur a. Il a des zéros et des uns. Si vous voulez représenter une flèche ou un carte ou un numéro, vous avez besoin d'un peu de mémoire. Donc, l'autre prix que vous payer pour une liste liée, une science informatique commun ressources, est également l'espace. 

Et en effet si, si souvent, parmi les compromis dans la conception de génie logiciel systèmes est temps et space-- sont deux de vos ingrédients, deux de vos ingrédients les plus coûteux. Cela me coûte plus de temps parce que je dois suivre ce plan, mais il est aussi me coûte plus d'espace parce que je dois garder cette carte autour. Donc, l'espoir, comme nous l'avons sorte de discuté plus hier et d'aujourd'hui, est que les avantages seront supérieurs aux coûts. 

Mais il n'y a pas de solution évidente ici. Peut-être est better-- a la rapide et sale, Kareem a proposé l'heure, à de jeter la mémoire au problème. Il suffit d'acheter plus de mémoire, penser moins difficile de résoudre le problème, et de le résoudre d'une manière plus facile. Et plus tôt en effet, quand nous avons parlé de compromis, il n'a pas été dans l'espace l'ordinateur et le temps. Il était temps de développeur, qui est encore une autre ressource. 

Encore une fois, il est cet équilibre essayant de décider lequel de ces choses êtes-vous prêt à dépenser? Ce qui est le moins cher? Ce qui donne les meilleurs résultats? Ouais? 

Effectivement. Dans ce cas, si vous êtes représentant des nombres dans le maps-- ceux-ci sont appelés dans de nombreuses langues "pointeurs" ou "adresses" - il est double de l'espace. Cela n'a pas besoin d'être aussi mauvais que doubler si en ce moment, nous sommes en train de stocker des numéros. Supposons que nous stockons les dossiers des patients dans un hospital-- donc les noms de Pierson, numéros de téléphone, numéros de sécurité sociale, médecin histoire. Cette boîte peut être beaucoup, beaucoup plus important, auquel cas un tout petit pointeur, l'adresse de la prochaine element-- ce n'est pas une grosse affaire. Il est une telle frange le coût n'a pas d'importance. Mais dans ce cas, oui, il est un doublement. Bonne question. 

Parlons un temps peu plus concrètement. Quelle est la durée de fonctionnement de la recherche de cette liste? Supposons que je voulais chercher à travers toutes les qualités »des élèves, et il y a n grades dans cette structure de données. Ici aussi, nous pouvons emprunter le vocabulaire plus tôt. Ceci est une structure de données linéaire. 

Big O n est ce qui est nécessaire pour obtenir à la fin de cette structure de données, whereas-- et nous avons pas vu ce before-- un tableau vous donne ce qu'on appelle la constante de temps, ce qui signifie une étape ou deux étapes ou 10 steps-- n'a pas d'importance. Il est un nombre fixe. Cela n'a rien à voir avec la taille de la matrice. Et la raison de cela, encore une fois, un accès aléatoire. L'ordinateur peut tout de suite sauter vers un autre emplacement, parce qu'ils sont tous les mêmes distance de tout le reste. Il n'y a pas de pensée impliqué. D'accord. Donc, si je peux, je vais essayer de peindre deux images finales. Un très commun connu sous le nom d'une table de hachage. Donc, pour motiver cette discussion, laissez-moi réfléchir sur la façon de le faire. 

Alors, comment à ce sujet? Supposons que le problème nous voulons résoudre maintenant est mise en œuvre dans un dictionary-- donc tout un tas de mots anglais Ou peu importe. Et l'objectif est d'être en mesure de répondre les questions de la forme est-ce un mot? Donc, vous voulez mettre en œuvre un correcteur orthographique, juste comme un dictionnaire physique que vous pouvez regarder les choses dans. Supposons que je devais le faire avec un tableau. Je pourrais le faire. 

Et supposons que les mots sont la pomme et de la banane et le cantaloup. Et je ne peux pas penser de fruits qui commencent par d, donc nous sommes juste va avoir trois fruits. Donc, c'est un tableau, et nous sommes stocker tous ces mots dans ce dictionnaire comme un tableau. La question, alors, est de savoir comment les autres pourriez-vous stocker cette information? 

Eh bien, je suis une sorte de tricherie ici, parce que chacune de ces lettres dans le mot est vraiment un octet individuel. Donc, si je voulais vraiment être tatillon, je devrais vraiment être divisant vers le haut dans beaucoup petits morceaux de mémoire, et nous pourrions faire exactement cela. Mais nous allons courir dans le même problème que précédemment. Que faire si, comme Merriam Webster ou Oxford fait chaque année-- ils ajoutent des mots à la dictionary-- nous ne faisons pas forcément envie de nous peindre dans un coin avec un tableau? 

Ainsi, au lieu, peut-être une approche plus intelligente est de mettre la pomme dans son propre noeud ou une boîte, comme nous dirions, la banane, et puis nous avons ici le cantaloup. Et nous string ces choses ensemble. Voici donc le tableau, et voici la liste liée. Si vous ne pouvez pas tout voir, juste dit «tableau», et cela dit "liste." 

Donc, nous avons le même questions précises comme avant, de sorte que nous avons maintenant dynamisme dans notre liste liée. Mais nous avons un dictionnaire assez lent. Supposons que je veux chercher un mot. Il pourrait me prendre grand O n étapes, parce que le mot pourrait soit tout le chemin à la fin de la liste, comme le cantaloup. Et il se trouve que dans la programmation, le tri du Saint-Graal des données structures, est quelque chose qui vous donne constante temps comme un tableau mais cela vous donne encore le dynamisme. 

Ainsi pouvons-nous avoir le meilleur des deux mondes? Et en effet, il y a quelque chose appelé la table de hachage qui vous permet de faire exactement que, bien qu'approximative. Une table de hachage est un amateur Structure de données que nous peut penser que le Combinaison d'un array-- et je vais dessiner comme this-- et listes chaînées que je vais dessiner comme ça ici. 

Et la façon dont cette chose ouvrages est le suivant. Si ce maintenant-- hachage table-- est ma troisième structure de données, et je veux stocker mots, je ne sais pas veulent simplement stocker tous les mots dos à dos à dos à dos. Je veux tirer parti de certains un bout d'information sur les mots qui vous permettra de moi obtenir là où il est plus rapide. 

Donc, étant donné la pomme de mots et de la banane et le cantaloup, Je choisis délibérément ces mots. Pourquoi? Quelle est une sorte de fond différent des trois? Quel est l'évidence? Ils commencent par des lettres différentes. 

Donc, vous savez quoi? Plutôt que de mettre tous mes mots le même seau, pour ainsi dire, comme dans une grande liste, pourquoi ne pas Au moins je tente une optimisation et de faire mes listes 1/26 aussi longtemps. Une optimisation convaincante peut-être pourquoi ne pas Je-- lors de l'insertion d'un mot dans cette structure de données, dans la mémoire de l'ordinateur, pour laquelle Je ne mets pas tous les «a» mots ici, tous les mots 'b' ici, et tous les 'c' mots ici? Donc, cela finit par mettre une pomme ici, banane ici, le cantaloup ici, et ainsi de suite. 

Et si je dois un montant supplémentaire mot like-- ce qui est une autre? Apple, banane, poire. Toute personne pense à un fruit qui commence par a, b, c? parfait Blueberry--. Cela va finir par ici. Et donc nous semblent avoir un légèrement meilleure solution, parce que maintenant si je veux à la recherche de la pomme, je first-- Je ne suis pas simplement plongée dans ma structure de données. Je ne plonge pas dans la mémoire de mon ordinateur. Je regarde d'abord à la première lettre. 

Et voici ce qu'est un ordinateur scientifique dirait. Vous hachage dans votre structure de données. Vous prenez votre entrée, qui ce cas est un mot comme la pomme. Vous analysez, en regardant la première lettre dans ce cas, le hachage de ce fait. Hashage est un terme général dans lequel vous prenez quelque chose comme entrée et que vous produisez une certaine sortie. Et la sortie en ce qu ' cas est l'emplacement vous voulez rechercher, le premier emplacement, deuxième emplacement, troisième. Donc, l'entrée est la pomme, la sortie est le premier. L'entrée est la banane, la sortie devrait être une seconde. L'entrée est cantaloup, la sortie devrait être troisième. L'entrée est myrtille, la sortie devrait être à nouveau deuxième. Et c'est ce que vous aide à prendre raccourcis à travers votre mémoire afin d'obtenir des mots ou des données de manière plus efficace. 

Maintenant, cela réduit notre temps potentiellement d'autant que l'un de 26, parce que si vous supposez que vous avoir autant de "a" mots comme "z" mots comme mots «q», qui est pas vraiment realistic-- vous allez avoir skew travers certaines lettres de l'alphabet-- mais ce serait une incrémental approche qui ne permet vous obtenez des mots beaucoup plus rapidement. Et en réalité, un système sophistiqué programme, le Googles du monde, le Facebooks du monde-- ils utilisent une table de hachage pour beaucoup d'usages différents. Mais ils ne seraient pas si naïf juste regarder la première lettre en pomme ou une banane ou poire ou cantaloup, parce que vous pouvez voir ces listes pourraient encore être longue. 

Et cela pourrait encore être une sorte de linear-- donc sorte de lent, comme avec le grand O n que nous avons discuté plus tôt. Alors qu'est-ce une vraie bonne table de hachage do-- il aura un beaucoup plus grand tableau. Et il utilisera beaucoup plus fonction de hachage sophistiquée, de sorte qu'il ne suffit de regarder le «a». Peut-être qu'il regarde "a-p-p-l-e» et convertit en quelque sorte ces cinq lettres à l'endroit où pomme doit être stocké. Nous sommes juste naïvement en utilisant la lettre 'a' seul, parce qu'il est simple et agréable. 

Mais une table de hachage, dans la fin, vous pouvez penser comme une combinaison de un tableau, dont chacune a une liste liée qu'idéalement doit être aussi courte que possible. Et ce n'est pas une solution évidente. En fait, une grande partie du réglage fin ce qui se passe sous le capot lorsque la mise en œuvre de ces types de structures de données complexes est ce qui est le droit la longueur de la matrice? Quelle est la fonction de hachage à droite? Comment pensez-vous de stocker des choses en mémoire? 

Mais se rendre compte de la rapidité ce genre de discussion escalade, soit si loin qu'il est le genre de dessus de la tête à ce point, ce qui c'est bien. Mais nous avons commencé, le rappel, avec vraiment bas niveau quelque chose et électronique. Et cela est encore cette thème de l'abstraction, où une fois que vous commencez à prendre pour accordée, OK, je l'ai it-- obtenu il y a mémoire physique, OK, il a obtenu, chaque emplacement physique a une adresse, OK, je l'ai eu, je peux représenter ces adresses comme arrows-- vous pouvez très rapidement commencer à avoir conversations plus sophistiquées à la fin semblent être nous permettant pour résoudre des problèmes tels que la recherche et trier plus efficacement. Et rassurez-vous, too-- parce que je pense que ce est le plus profond que nous sommes allés dans certains de ces sujets CS proper-- nous avons fait en un jour et demi à ce pointez ce que vous pourriez normalement faire plus au cours de huit semaines à un semestre. 

Toute question sur ces? Non? D'accord. Eh bien, pourquoi ne nous y arrêtons pas, commencer à déjeuner quelques minutes plus tôt, reprendre dans à peu près une heure? Et je vais persister pendant un peu avec des questions. Ensuite, je vais devoir aller prendre quelques appels si c'est OK. Je cède la parole de la musique, dans l'intervalle, mais le déjeuner devrait être dans le coin.