>> ENCEINTE 1: Très bien, donc cela est CS50 Ceci est la fin de la semaine de cinq.
Et de rappeler que la dernière fois nous commencé à regarder les données fantaisistes
structures qui ont commencé à résoudre problèmes, qui ont commencé à introduire des
de nouveaux problèmes, mais la clé de cette était le genre de filetage que nous
commencé à faire de nœud à nœud.
Donc, cela est bien sûr une liste chaînée.
Et par chaînée, Je veux dire il ya juste un
faufiler entre chacun de ces nœuds.
Avère que vous pouvez faire colombophile des choses comme des listes doublement chaînées
par lequel vous avez une flèche aller dans les deux sens, ce qui
peut aider avec une certaine efficacité.
Mais cela a résolu le problème?
Quel problème est-ce à résoudre?
Pourquoi avons-nous soucions le lundi?
Pourquoi, en théorie, ne nous nous soucions le lundi?
Qu'est ce que ça fait?
>> PUBLIC: Nous pouvons dynamiquement redimensionner.
>> ENCEINTE 1: OK, alors nous pouvons redimensionner dynamiquement.
Bravo à vous deux.
Ainsi, vous pouvez redimensionner dynamiquement cette Structure de données, alors un tableau,
rappel, vous avez à connaître priori comment vous voulez beaucoup d'espace
et si vous avez besoin d'un peu plus espace, vous êtes un peu hors de la chance.
Vous devez créer un tout nouveau tableau.
Vous devez déplacer tous vos les données d'un à l'autre,
finalement libérer l'ancien tableau si vous le pouvez, et ensuite procéder.
Qui se sent juste très coûteux et très inefficace, et en effet il peut être.
Mais ce ne sont pas tous bons.
Nous payons un prix, ce qui a été l'un des prix plus évidentes, nous
payer en utilisant une liste chaînée?
>> PUBLIC: Nous devons utiliser espace double pour chacun.
ENCEINTE 1: Ouais, donc nous avons besoin au moins deux fois autant d'espace.
En fait, je me rendis compte de cette image même un peu trompeur,
parce que sur CS50 IDE dans un lot de moderne ordinateurs, un pointeur ou une adresse
est pas en fait quatre octets.
Il est très souvent ceux-ci huit jours octets, ce qui
des moyens le plus bas rectangles là dans la réalité
sont sorte de deux fois grand que ce que je l'ai dessiné,
ce qui signifie que vous utilisez trois fois plus autant d'espace que nous pourrions avoir autrement.
Maintenant, dans le même temps, nous sommes parle encore octets, non?
Nous ne parlons pas nécessairement mégaoctets ou gigaoctets,
sauf si ces structures de données deviennent grands.
>> Et aujourd'hui, nous commençons à considérer comment nous pourrions explorer les données
plus efficacement en cas de fait, les données devient plus grand.
Mais nous allons essayer de canoniser les premières opérations
que vous pouvez faire sur ces les types de structures de données.
Donc, quelque chose comme un lien liste prend généralement en charge
Les opérations telles que supprimer, insérer et rechercher.
Et qu'est-ce que je veux dire par là?
Cela signifie juste que généralement, si les gens utilisent liste chaînée,
ils ou quelqu'un d'autre a mis en place fonctions telles que supprimer, insérer,
et la recherche, afin que vous puissiez réellement faire quelque chose
utile avec la structure de données.
Donc, nous allons jeter un coup d'œil comment nous pourrions mettre en œuvre
un peu de code pour une liste chaînée comme suit.
>> Donc, ceci est juste un peu de code C, même pas un programme complet
que je très rapidement fouetté.
Il est pas en ligne dans la distribution code, car il ne sera pas réellement fonctionner.
Mais remarquez que je viens avec un commentaire dit,
Dot Dot Dot, il ya quelque chose là, Dot Dot Dot, quelque chose là.
Et disons simplement Regardons ce que les parties sont juteuses.
Donc, sur la ligne de trois, Rappelons que ce est maintenant
nous avons proposé de déclarer un nœud dernière temps, l'un de ces objets rectangulaires.
Il a un int que nous appellerons N, mais nous pourrions l'appeler quelque chose,
puis une star du noeud de struct appelé prochaine.
Et juste pour être clair, ce deuxième ligne, sur la ligne de six, ce qui est qui?
Que fait-il pour nous?
Parce qu'il ressemble certainement plus cryptique que nos variables habituelles.
>> PUBLIC: Il fait bouger plus d'un.
>> ENCEINTE 1: Il fait bouger plus d'un.
Et pour être plus précis, il va stocker l'adresse
du noeud qui est destiné à être sémantiquement à côté de lui, non?
Donc, il ne va pas déplacer nécessairement quelque chose.
Il va juste stocker une valeur, qui est
va être l'adresse d'un autre noeud,
et voilà pourquoi nous avons dit struct noeud étoiles, l'étoile dénotant
un pointeur ou une adresse.
OK, maintenant si vous supposer que nous avons ce N disponible pour nous, et nous allons
supposer que quelqu'un d'autre a inséré tout un tas d'entiers
dans une liste chaînée.
Et cette liste est liée pointée par un certain point
une variable appelée liste qui est adoptée ici en tant que paramètre,
comment puis-je aller sur la ligne 14 mise en œuvre de la recherche?
En d'autres termes, si je suis la mise en œuvre fonction dont le but dans la vie
est de prendre un int, puis le début d'une liste chaînée,
qui est un pointeur vers la liste chaînée.
Comme la première, qui, je pense David était notre bénévole le lundi,
il pointait toute la liste chaînée,
il est comme si nous passons David en tant que notre argumentation ici.
Comment allons-nous traverser cette liste?
Eh bien, il se trouve que même si pointeurs sont relativement nouvelle pour nous maintenant,
nous pouvons le faire relativement carrément.
>> Je vais aller de l'avant et déclarer une variable temporaire
par convention va tout simplement d'être appelé pointeur, ou PTR,
mais vous pourriez l'appeler ce que vous voulez.
Et je vais initialiser au début de la liste.
Ainsi, vous pouvez sorte de penser de cette comme me l'enseignant, l'autre jour,
sorte de pointage à quelqu'un parmi nos humains en tant que bénévoles.
Je suis donc une variable temporaire qui est pointant simplement la même chose
que notre hasard nommé David a également été bénévole soulignant.
Maintenant, alors que le pointeur est non nulle, parce rappel
que nulle est une valeur sentinelle spéciale la délimite la fin de la liste,
Ainsi, alors que je ne suis pas au pointage sol comme notre dernière bénévoles
était, Allons de l'avant et faire ce qui suit.
Si pointer-- et maintenant je veux sorte de de faire ce que nous avons fait avec l'étudiant
structure-- si le pointeur point à côté equals-- plutôt, si le pointeur point N est égal
est égal à la variable N, la l'argument qui a été transmis,
alors je veux aller de l'avant et dire return true.
Je l'ai trouvé le numéro N intérieur de l'un des nœuds de ma liste chaînée.
Mais le point plus qui fonctionne dans ce contexte,
parce pointeur, PTR, est en effet un pointeur, une adresse,
Nous pouvons en fait merveille enfin utiliser un morceau de syntaxe
ce genre de marques sens intuitif et effectivement
utiliser une flèche ici, ce qui signifie aller de cette adresse à l'entier là dans.
Il est donc très similaire dans esprit de l'opérateur point,
mais parce que le pointeur est pas un pointeur et pas une structure elle-même,
nous utilisons simplement la flèche.
>> Donc, si le noeud courant que moi, variable temporaire, me montre du doigt
N est pas, qu'est-ce que je veux faire?
Eh bien, avec mes volontaires humains que nous avons eu ici l'autre jour,
si mon premier humain est pas celui que je veut, et peut-être le deuxième homme est pas
celui que je veux, et le troisième, je besoin de bouger physiquement.
Comme comment puis-je passerai une liste?
Quand nous avons eu un tableau, vous juste fait comme je l'ai plus plus.
Mais dans ce cas, il suffit de faire pointeur, obtient, pointeur, à côté.
En d'autres termes, le champ suivant est comme toutes les mains gauches
que nos volontaires humains lundi utilisaient pour pointer vers un autre nœud.
Ce sont leurs prochains voisins.
>> Donc, si je veux passer en revue cette liste, Je ne peux pas le faire, je plus plus plus,
Je dois dire à la place I, pointeur, va
à égale quel que soit le champ suivant est, le champ suivant est, le champ suivant est,
suivant toutes ces mains gauches que nous avions sur le pointage de scène
pour certaines valeurs suivantes.
Et si je reçois par que l'ensemble de l'itération,
et enfin, je frappe null ne pas avoir N trouvé encore, je reviens tout simplement fausse.
Encore une fois, tout ce que nous faisons ici, selon l'image il ya un instant,
commence en pointant à la début de la liste sans doute.
Et puis je vérifie, est la valeur Je cherche égal à neuf?
Si oui, je reviens vrai et je suis fait.
Si non, je mets à jour ma main, Alias ​​pointeur, pour pointer
à l'emplacement de la prochaine flèche, et puis l'emplacement de la prochaine flèche,
et la suivante.
Je suis tout simplement la marche à travers ce réseau.
>> Donc encore une fois, qui se soucie?
Comme quoi est-ce un ingrédient pour?
Eh bien, rappelons que nous avons lancé la notion d'une pile, qui
est de type dans la mesure où une donnée abstraite comme il est pas une chose de C, il est pas une chose de CS50,
il est une idée abstraite, cette idée de empiler sur des choses dessus de l'autre
qui peut être mis en œuvre dans des grappes de différentes manières.
Et une façon que nous avons proposé était avec un tableau, ou avec une liste chaînée.
Et il se trouve que canoniquement, un pile prend en charge au moins deux opérations.
Et les mots à la mode sont poussée, à pousser quelque chose sur la pile,
comme un nouveau plateau dans le salle à manger, ou de la pop,
ce qui signifie pour enlever le plus élevé plateau de la pile dans la salle
salle, et puis peut-être un peu d'autres opérations ainsi.
Alors, comment pouvons-nous définir la structure que nous appelons maintenant une pile?
>> Eh bien, nous avons tout le nécessaire la syntaxe à notre disposition en C. Je dis,
me donner une définition de type de une structure à l'intérieur d'une pile,
Je vais dire est un tableau, d'un tas ensemble de nombres, puis la taille.
Donc, en d'autres termes, si je veux à mettre en œuvre dans votre code,
laissez-moi partir et juste sorte de dessiner ce que cela veut dire.
Donc, cela veut dire, me donner un la structure qui a obtenu un tableau,
et je ne sais pas quelle est la capacité, il est apparemment une constante que je l'ai
définis ailleurs, et ça va.
Mais supposons qu'il est juste un, deux, trois, quatre, cinq.
Donc, la capacité est de 5.
Cet élément intérieur de ma structure sera appelée numéros.
Et puis je besoin d'un une autre variable apparemment
appelé taille qui d'abord je vais à prévoir est initialisée à zéro.
Si il n'y a rien dans la pile, la taille est égale à zéro,
et il est des valeurs parasites en nombre.
Je ne sais pas ce qu'il ya dedans pour l'instant.
>> Donc, si je veux pousser quelque chose sur la pile,
suppose que je l'appelle la fonction Push, et Je dis pousser 50, comme le nombre 50,
où voulez-vous proposer Je dessine dans ce tableau?
Il ya cinq réponses différentes possibles.
Où voulez-vous de pousser le numéro 50?
Si le but ici, encore une fois, appeler le fonction Push, passer dans un argument
50, où dois-je le mettre?
Cinq possible-- 20% de chances de deviner correctement.
Oui?
>> AUDIENCE: Extrême droite.
>> ENCEINTE 1: Extrême droite.
Il ya maintenant une chance de 25% de deviner correctement.
Donc, ce serait effectivement bien.
Par convention, je vais le dire avec un tableau, nous aurions commence généralement à gauche,
mais nous pourrions certainement commence à la droite.
Donc, le spoiler ici serait que je suis va probablement dessiner sur la gauche,
Tout comme dans un tableau normal où Je commencer à aller de gauche à droite.
Mais si vous pouvez retourner l'arithmétique, très bien.
Il est tout simplement pas conventionnelle.
OK, je dois faire un plus de changement cependant.
Maintenant que je l'ai poussé quelque chose sur la pile, ce qui est la prochaine étape?
>> Très bien, je dois augmenter la taille.
Alors laissez-moi aller de l'avant et juste mettre à jour ce qui était de zéro.
Et au lieu maintenant, je vais de mettre en la valeur un.
Et maintenant suppose que je pousse un autre numéro sur la pile, comme 51.
Eh bien, je dois faire un de plus changement, qui est à la taille deux.
Et puis suppose que je pousse un de plus numéro sur la pile comme 61,
maintenant je dois mettre à jour la taille d'un plus temps, et obtenir la valeur 3 comme la taille.
Et maintenant, je suppose appelle pop.
Maintenant, pop, par convention, ne prenez pas un argument.
Avec une pile, l'ensemble point de la métaphore de plateau
est que vous ne disposez pas de la discrétion d'aller chercher ce plateau, tout ce que vous pouvez faire
est pop la plus haute un de la pile, juste parce que.
Voilà ce que cette structure de données fait.
>> Ainsi, en ce que si la logique I dire pop, ce qui se détache?
Donc 61.
Donc ce qui est vraiment l'ordinateur va faire dans la mémoire?
Qu'est-ce que mon code a à voir?
Que proposeriez-vous nous changeons sur l'écran?
Qu'est-ce qui devrait changer?
Pardon?
Nous sommes tellement débarrassés de 61.
Donc, je peux certainement le faire.
Et je peux me débarrasser de 61.
Et puis ce que les autres le changement doit se produire?
Taille a probablement revenir à deux.
Et alors ça va.
Mais attendez une minute, la taille il ya un moment était trois.
Disons simplement faire une vérification de cohérence rapide.
Comment avons-nous savons que nous voulait se débarrasser de 61?
Parce que nous sommes popping.
Et donc je dois cette seconde taille de la propriété.
>> Attendez une minute, je suis repensant à deux semaines
lorsque nous avons commencé à parler tableaux, où cela était l'emplacement zéro,
ce fut l'un emplacement, ce fut emplacement deux, cet emplacement est trois, quatre,
il semble que le relation entre la taille
et l'élément que je veux supprimer à partir du tableau semble juste être quoi?
Taille moins un.
Et voilà comment en tant qu'êtres humains nous savons 61 vient en premier.
Comment est l'ordinateur va savoir?
Lorsque votre code, où vous avez probablement vouloir faire la taille moins un,
donc trois moins un est de deux, et que signifie que nous voulons nous débarrasser de 61 ans.
Et puis, nous pouvons en effet de mettre à jour la taille de sorte que la taille maintenant
va de trois à deux seulement.
Et juste pour être pédant, je vais de proposer que je suis fait, non?
Vous avez proposé intuitivement correctement je devrais me débarrasser de 61.
Mais avoir pas que je sorte de sorte d'débarrassé de 61?
Je l'ai effectivement oublié qu'il est vraiment là.
Et penser à PSET4, si vous avez lu l'article sur la médecine légale, le PDF
que nous devions vous les gars lire, ou vous lira cette semaine pour PSET4.
Rappelons que ce soit réellement germane à l'idée de la criminalistique informatique.
Qu'est-ce que le fait généralement un ordinateur est il oublie juste où quelque chose est,
mais il ne va pas et comme essayer de gratter sur ou override
ces bits avec zéros et de uns ou quelque autre motif aléatoire
sauf si vous vous le faire volontairement.
Donc, votre intuition était droite, débarrassons-nous de 61 ans.
Mais en réalité, nous ne devons pas la peine.
Nous avons juste besoin d'oublier que il est là en changeant notre taille.
>> Maintenant, il ya un problème avec cette pile.
Si je continue à pousser les choses sur la pile, ce qui est
évidemment va se passer en un temps de quelques instants?
Nous allons manquer d'espace.
Et que faisons-nous?
Nous sommes en quelque sorte des foutus.
Cette mise en œuvre ne laisse pas nous redimensionner le tableau, parce que l'utilisation
cette syntaxe, si vous penser à la deuxième semaine,
une fois que vous avez déclaré la taille d'un tableau,
nous avons pas encore vu où un mécanisme vous pouvez changer la taille du tableau.
Et en effet, C n'a pas cette fonctionnalité.
Si vous dites me donner cinq NTHS, appeler les numéros,
voilà tout, vous allez obtenir.
Donc, nous faisons maintenant à partir de lundi, avons la capacité à exprimer une solution
cependant, nous avons juste besoin de tordre la définition de notre pile
de ne pas être d'un tableau codé en dur, mais juste pour stocker une adresse.
>> Maintenant, pourquoi est-ce?
Maintenant, nous devons juste être à l'aise avec le fait que lorsque mon programme court,
Je vais sans doute avoir à demander l'humain,
combien de numéros voulez-vous stocker?
Donc, l'entrée doit venir de quelque part.
Mais une fois que je sais que nombre, alors je peux juste
utiliser ce fonctionnement pour donner moi un morceau de la mémoire?
Je peux utiliser malloc.
Et je peux dire un certain nombre de octets Je veux revenir pour ces NTHS.
Et tout ce que je dois stocker dans les numéros la variable ici à l'intérieur de cette structure
devrait être quoi?
Ce qui se passe réellement dans le numéros dans ce scénario?
Oui, un pointeur vers le premier octet de ce morceau de mémoire,
ou plus spécifiquement, l'adresse du premier de ces octets.
N'a pas d'importance si elle est l'un octets ou un milliard d'octets,
Je dois juste se soucier de la première.
Parce que ce que les garanties de malloc et mes garanties de système d'exploitation,
est ce que le bloc de mémoire que je obtenir, ça va être contigus.
Il ne va pas y avoir des lacunes.
Donc, si je l'ai demandé 50 octets ou 1000 octets,
ils vont tous être dos à dos à dos.
Et aussi longtemps que je me souviens comment grand, comment que je demandais, tout ce que je dois savoir
est la première adresse.
>> Alors maintenant, nous avons la capacité dans le code.
Quoique, ça va nous prendre plus de temps pour écrire cette place,
nous pourrions maintenant réaffecter que la mémoire par simplement mémoriser une adresse différente il
si nous voulons une plus grande ou même un morceau plus petit de la mémoire.
Donc ici pour un hors commerce.
Maintenant, nous arrivons dynamisme.
Nous avons toujours contiguousness Je prétendant.
Parce que malloc nous donnera un morceau de la mémoire contiguë.
Mais cela va être une douleur dans le cou pour nous, le programmeur,
à coder réellement.
Il est juste plus de travail.
Nous avons besoin d'un code semblable à ce que je faisais taper sur il ya un instant.
Très faisable, mais il ajoute à la complexité.
Et donc le temps de développeur, programmeur Il est encore une autre ressource
que nous pourrions avoir besoin de dépenser peu de temps pour obtenir de nouvelles fonctionnalités.
Et puis bien sûr il ya une file d'attente.
Nous ne rentrerons pas dans ce un dans beaucoup de détails.
Mais il est très similaire dans l'esprit.
Je pourrais mettre en œuvre une file d'attente, et ses opérations correspondantes,
enqueue ou dequeue, comme ajouter ou supprimer, il est juste une façon de dire qu'il colombophile,
enqueue ou dequeue, comme suit.
Je peux juste me donner une struct a cette fois le tableau d'un certain nombre,
a cette fois une taille, mais pourquoi dois-je maintenant
de garder une trace de l'avant de la file d'attente?
Je ne l'ai pas besoin de savoir l'avant de ma pile.
Eh bien, si je encore pour un queue-- Disons simplement dur
coder comme ayant comme cinq entiers dans ici potentiellement.
Donc, cela est zéro, un, deux, trois, quatre.
Cela va être appelé de nouveau les numéros.
Et ce sera appelée taille.
>> Pourquoi est-il ne suffit pas d'avoir juste la taille?
Eh bien, nous allons pousser ces mêmes numéros sur.
Donc, je pushed-- je en file d'attente, ou poussé.
Maintenant, je vais ENQUEUE 50, puis 51, puis 61, et Dot Dot Dot.
Voilà donc enqueue.
Je en file d'attente 50, puis 51, puis 61.
Et cela semble identique pour une pile à ce jour,
sauf que je ne dois faire un changement.
Je dois mettre à jour cette taille, donc je vais de zéro à un à deux à trois maintenant.
Comment puis-je DEQUEUE?
Qu'est-ce qui se passe avec dequeue?
Qui doit se détacher de cette première liste si elle est la ligne sur l'Apple Store?
Donc 50.
Donc, il est un peu plus délicat cette fois.
Considérant que la dernière fois qu'il a été super facile de simplement faire la taille moins un,
Je reçois à la fin de mon tableau efficacement où les chiffres sont, il supprime 61.
Mais je ne veux pas retirer 61.
Je veux profiter de 50 ans, qui était là à 5h00
faire la queue pour le nouvel iPhone ou autres joyeusetés.
Et donc de se débarrasser des 50, je ne peut pas simplement faire cela, non?
Je peux rayer 50.
Mais nous venons de dire, nous ne doivent pas être si anal
à gratter ou de masquer les données.
Nous ne pouvons tout simplement d'oublier d'où il est.
>> Mais si je change ma taille maintenant deux, cette information est suffisante
savoir ce qui se passait dans ma file d'attente?
Pas vraiment.
Comme ma taille est de deux, mais où la file d'attente ne commencent,
surtout si je dois encore ces mêmes nombres dans la mémoire.
50, 51, 61.
Donc, je dois me rappeler maintenant où le front est.
Et comme je l'ai proposé jusqu'à là, nous venons d'appeler
Avant Nième, dont la première valeur aurait dû être quoi?
Zero, que le début de la liste.
Mais maintenant, en plus de décrémentation la taille, nous avons juste incrémenter l'avant.
Maintenant, voici un autre problème.
Donc, une fois je continue.
Supposons que ce est le nombre de comme 121, 124, puis, merde,
Je suis hors de l'espace.
Mais attendez une minute, je ne suis pas.
Donc, à ce moment de l'histoire, Supposons que la taille est un, deux,
trois, quatre, de sorte que le supposer la taille est de quatre, l'avant est un,
donc 51 est à l'avant.
Je veux mettre un autre numéro ici, mais, bon sang, je suis hors de l'espace.
Mais je ne suis pas vraiment, non?
Où pourrais-je mettre un peu valeur ajoutée, comme 171?
Ouais, je pouvais juste genre de revenir sur là, non?
Et puis traverser le 50, ou simplement le remplacer par 171.
Et si vous vous demandez pourquoi nos numéros se sont tellement aléatoire,
ceux-ci sont souvent prises ordinateur cours de sciences à Harvard après CS50.
Mais ce fut une bonne optimisation, parce que maintenant je ne suis pas gaspiller de l'espace.
Je dois encore rappeler l'ampleur de cette chose est totale.
Il est cinq heures au total.
Parce que je ne veux pas commencera à remplacer les 51.
Alors maintenant, je suis encore plus d'espace, de sorte que le même problème que précédemment.
Mais vous pouvez voir comment l'entreprise dans votre code, vous avez probablement
avoir à l'écrire un peu plus la complexité de faire que cela se produise.
Et en fait, ce que l'opérateur en C permet probablement
vous faites cette magie la circularité?
Ouais l'opérateur modulo, le signe pour cent.
Alors, quel est plutôt cool sur une file d'attente, même si nous gardons les tableaux de dessin
que ces lignes droites comme, si vous sorte de penser à cela comme courbe
autour d'un cercle, puis juste intuitivement cela fonctionne sorte de mental
Je pense un peu plus proprement.
Vous auriez encore à mettre en œuvre ce modèle mentale dans le code.
Donc, pas si difficile, en fin de compte, à mettre en oeuvre,
mais nous perdons toujours le size-- plutôt la possibilité de redimensionner, à moins que nous faisons cela.
>> Nous devons nous débarrasser de la matrice, nous le remplacer par un seul pointeur,
puis quelque part dans mon code, je dois Un appel qui fonctionne pour créer réellement
le tableau des numéros appelés?
Malloc, ou quelques similaires fonction, exactement.
Des questions sur piles ou des files d'attente.
Ouais?
Bonne question.
Que voulez-vous utiliser modulo ici.
Donc, en général, lors de l'utilisation mod, vous ferait
avec la taille de la structure de données ensemble.
Donc, quelque chose comme cinq ou capacité, si il est constant, est probablement impliqué.
Mais juste faire modulo cinq est sans doute pas suffisante,
parce que nous devons savoir faire nous enrouler autour ici ou ici ou ici.
Donc, vous êtes probablement aussi allez vouloir impliquer
la taille de la chose, ou la variable avant ainsi.
Donc, il est juste ce relativement expression arithmétique simple,
mais modulo serait l'ingrédient clé.
>> Donc court métrage si vous voulez.
Une animation que certaines les gens d'une autre université
mettons ensemble que nous avons adapté à cette discussion.
Elle implique l'apprentissage de la Jack faits sur les files d'attente et les statistiques.
>> FILM: Il était une fois, il y avait un gars nommé Jack.
Quand il est venu à se faire des amis, Jack n'a pas de talent.
Donc, Jack est allé parler à la plus gars populaire qu'il savait.
Il est allé à Lou et a demandé, Que dois-je faire?
Lou a vu que son ami était vraiment en détresse.
Eh bien, il a commencé, juste regardez comment vous êtes habillé.
Ne vous avez des vêtements avec un regard différent?
Oui, dit Jack.
Je fais bien sûr.
Venez à ma maison et Je vais leur montrer à vous.
Ils partirent donc à Jack.
Et Jack a montré Lou la boîte où il a gardé toutes ses chemises,
et son pantalon, et ses chaussettes.
Lou a dit: Je vois que vous avez tous vos vêtements dans un tas.
Pourquoi ne portez-vous pas un peu d'autres de temps en temps?
>> Jack dit, eh bien, quand je enlever les vêtements et les chaussettes,
Je les lave et mets les dans la boîte.
Vient ensuite la prochaine matin, et jusqu'à je hop.
Je vais à la boîte et obtiens mes vêtements sur le haut.
Lou a rapidement réalisé le problème avec Jack.
Il a gardé des vêtements, des CD, et des livres de la pile.
Quand il a atteint pour quelque chose à lire ou à l'usure,
il choisirait le livre dessus ou sous-vêtements.
Puis, quand il a été fait, il mettrait le droit de retour.
Retour il irait, sur le dessus de la pile.
Je sais que la solution, dit un fort triomphante.
Vous devez apprendre à commencer à utiliser une file d'attente.
Lou a pris les vêtements de Jack et les pendu dans le placard.
Et quand il avait vidé la boîte, il a juste le lança.
>> Puis il dit, maintenant Jack, à la fin de le jour, mettez vos vêtements sur la gauche
quand vous mettez les éloigner.
Puis demain matin lorsque vous voir le soleil, vos vêtements
sur la droite, à partir de la fin de la ligne.
Ne voyez-vous pas? a déclaré Lou.
Ce sera tellement agréable.
Vous portez une fois tout avant que vous portez quelque chose deux fois.
Et avec tout dans les files d'attente dans son placard et étagère,
Jack a commencé à se sentir tout à fait sûr de lui-même.
Tout cela grâce à Lou et sa merveilleuse file d'attente.
ENCEINTE 1: Très bien, il est adorable.
Donc, ce qui a été vraiment va sur sous le capot maintenant?
Que nous avons des pointeurs, que nous avons malloc,
que nous avons la capacité de créer morceaux de mémoire pour nous
dynamiquement.
Donc, ce que nous est une image entrevu l'autre jour.
Nous ne sommes pas vraiment demeurons sur elle, mais cette image
a été en dessous de passe le capot pendant des semaines maintenant.
Et cela représente donc, juste un rectangle que nous avons établi,
la mémoire de votre ordinateur.
Et peut-être votre ordinateur, ou CS50 ID, dispose d'un gigaoctet de mémoire vive ou RAM
ou deux gigaoctets ou quatre.
Il n'a pas vraiment d'importance.
Votre système d'exploitation Windows ou Mac OS ou Linux,
permet essentiellement votre programme à penser qu'il a accès
pour la totalité de la mémoire de votre ordinateur,
même si vous pourriez exécuter plusieurs programmes à la fois.
Donc, en réalité, cela ne fonctionne pas vraiment.
Mais il est une sorte d'illusion donné à tous vos programmes.
Donc, si vous aviez deux concerts de RAM, ce est de savoir comment l'ordinateur peut penser.
>> Maintenant, par hasard, l'un de ces choses, l'un de ces segments de mémoire,
est appelée une pile.
Et en effet tout moment à ce jour dans l'écriture de code
que vous avez appelé un fonction, par exemple principal.
Rappelons que chaque fois que je l'ai la mémoire de l'ordinateur dessinée,
Je dessine toujours sorte de la moitié d'un rectangle ici
et ne vous embêtez pas à parler sur ce qui est ci-dessus.
Parce que quand principale est appelée, je prétends que vous obtenez ce ruban de mémoire
qui descend ici.
Et si principale appelée fonction comme swap, ainsi échange va ici.
Et il se trouve, qui est où il est de se retrouver.
Sur ce qu'on appelle une pile l'intérieur de la mémoire de votre ordinateur.
Or, à la fin de la journée, cette adresse est juste.
Il est comme octet nul, un octet, l'octet 2 milliards de dollars.
Mais si vous pensez à ce sujet que cet objet rectangulaire,
tout ce que nous faisons tous les fois que nous appelons une fonction est
superposition d'une nouvelle tranche de mémoire.
Nous donnons à cette fonction une tranche de sa propre mémoire pour travailler avec.
>> Et maintenant rappeler que cela est important.
Parce que si nous ne disposons quelque chose comme de swap
et deux variables locales telles que A et B et nous changeons les valeurs d'un et deux
à deux et un, le rappel que lorsque swap de revient,
il est comme si cette tranche de mémoire est tout simplement disparu.
En réalité, il est toujours il médicolégal.
Et quelque chose est encore vraiment là.
Mais conceptuellement, il est aussi si elle est complètement disparu.
Et principale ne sait pas tout le travail cela a été fait dans cette fonction d'échange,
sauf si elle est effectivement passé dans les arguments par pointeur ou par référence.
Maintenant, la solution fondamentale à ce problème avec l'échange d'
se passe des choses dans d'adresse.
Mais il se trouve, aussi, ce qui est été passe au-dessus de la partie
du rectangle tout ce temps est Pourtant, il ya plus de mémoire là-haut.
Et quand vous dynamiquement allouer de la mémoire,
si elle est à l'intérieur de GetString, qui nous avons fait pour vous dans le CS50
bibliothèque, ou si vous les gars appeler malloc et demander
le système d'exploitation pour un morceau de mémoire, il ne vient pas de la pile.
Il vient d'un autre lieu dans la mémoire de votre ordinateur
qui est ce qu'on appelle le tas.
Et ce ne est pas différent.
Il en est de même de RAM.
Il est la même mémoire.
Il est juste de la RAM qui est en place il lieu d'ici-bas.
>> Et qu'est-ce que cela signifie?
Eh bien, si votre ordinateur possède une quantité limitée de mémoire
et la pile grandit, donc de parler, et le tas, selon
à cette flèche, est de plus en plus bas.
En d'autres termes, chaque fois que vous appelez malloc,
vous étant donné une tranche de mémoire à partir de ci-dessus,
alors peut-être un peu plus bas, puis un peu inférieur, à chaque fois que vous appelez malloc,
le tas, il est l'utilisation, est une sorte de croissant,
de plus en plus de proche en proche à quoi?
La pile.
Donc, cela semble être une bonne idée?
Je veux dire, où il est pas vraiment clair ce que vous pouvez faire si vous ne
avoir une quantité limitée de mémoire.
Mais cela est certainement mauvais.
Ces deux flèches sont sur un Crash Course pour l'autre.
>> Et il se trouve que méchant, les gens qui sont particulièrement bonnes avec la programmation,
et d'essayer de pirater des ordinateurs, peut exploiter cette réalité.
En fait, nous allons examiner un petit extrait.
Donc, ceci est un exemple que vous pouvez lire environ plus en détail sur Wikipedia.
Nous vous indiquerons au article si curieux.
Mais il ya une attaque générale connu comme dépassement de tampon qui
existe aussi longtemps que les humains ont eu la possibilité de manipuler
la mémoire de l'ordinateur, en particulier en C. Donc, ce programme est très arbitraire,
mais nous allons le lire de bas en haut.
Principale dans argC omble étoiles argv.
Donc, il est un programme qui prend arguments de ligne de commande.
Et tout ne principale est apparemment appel une fonction, appeler F pour plus de simplicité.
Et il passe en quoi?
Argv d'un.
Donc, il passe dans ce que F le mot est que l'utilisateur a tapé
à l'invite après la le nom de programme du tout.
Donc, un peu comme César ou Vigenère, qui vous pourriez faire rappeler avec argv.
>> Alors, quelle est F?
F prend dans une chaîne que son seul argument,
Alias ​​une star de char, même chose, comme une chaîne.
Et il a appelé arbitrairement bar dans cet exemple.
Et puis char c 12, seulement en termes simples,
ce qui est char c support 12 faire pour nous?
Qu'est-ce qu'il fait?
Allocation de mémoire, en particulier 12 octets pour 12 caractères.
Exactement.
Et puis la dernière ligne, remuer et copie, vous avez sans doute pas vu.
Ceci est une copie de chaîne fonction dont le but dans la vie
est de copier son deuxième argument dans son premier argument,
mais seulement jusqu'à un certain nombre d'octets.
Ainsi, le troisième argument dit, combien d'octets vous devez copier?
La longueur de la barre, quelle que soit l'utilisateur a tapé dans.
Et le contenu de bar, cette chaîne, sont
copié dans la mémoire pointé au C.
>> Donc, cela semble un peu stupide, et il est.
Il est un exemple artificiel, mais il est représentatif
d'une classe de vecteurs d'attaque, une façon d'attaquer un programme.
Tout est beau et bon si l'utilisateur types dans un mot qui est 11 caractères
ou moins, ainsi que la barre oblique inverse zéro.
Que faire si les types d'utilisateurs dans plus de 11 ou 12 ou 20 ou 50 caractères?
Quel est ce programme va faire?
Faute potentiellement seg. Ça va de copier aveuglément tout en bar jusqu'à
à sa longueur, qui est littéralement tout en bar,
dans l'adresse pointée à C. Mais C a seulement préventivement donné que 12 octets.
Mais il n'y a pas de vérification supplémentaire.
Il n'y a pas si les conditions.
Il n'y a pas ici de vérifier l'erreur.
>> Et donc ce que ce programme est va faire est aveuglément
copier une chose à l'autre.
Et si nous tirons cette comme une image, voici
juste un petit morceau de l'espace mémoire.
Donc remarquons au fond, nous avoir la barre variable locale.
Donc, ce pointeur qui va store-- plutôt cet argument locale qui est
allez stocker la barre de chaîne.
Et puis notez simplement au-dessus d'une pile,
parce que chaque fois que vous demandez pour la mémoire sur la pile,
il va un peu au-dessus imagé,
Notez que nous avons 12 octets il.
L'un en haut à gauche est C support de zéro et celui en bas à droite est C support 11.
Voilà à quel point les ordinateurs va jeter dehors.
Il suffit donc intuitivement, si la barre a plus de 12 caractères au total, y compris
la barre oblique inverse zéro, où est le 12 ou le support de C 12 va aller?
Ou plutôt où est le 12e caractère ou le caractère 13,
le caractère centième aller pour finir dans l'image?
Dessus ou en dessous?
>> Droit, parce que même si la pile se pousse vers le haut,
une fois que vous avez mis des choses dans ce, pour des raisons de conception,
met la mémoire de haut en bas.
Donc, si vous avez plus de 12 octets, vous allez commencer à remplacer bar.
Voilà un bug, mais il est pas vraiment un gros problème.
Mais il est un gros problème, car il ya plus de choses se passe dans la mémoire.
Alors, voici comment nous pourrions mettre bonjour, pour être clair.
Si je tapé dans bonjour à l'invite.
Barre oblique inverse zéro H-E-L-L-O, finit dans les ces 12 octets, et nous sommes très sûr.
Tout est bien.
Mais si je tape quelque chose plus, il est potentiellement
va glisser dans l'espace bar.
Mais pire encore, il se sur tout ce temps,
même si nous ne l'avons jamais parlé elle, la pile est utilisé pour d'autres choses.
Il n'y a pas que les variables locales.
>> C est un langage de très faible niveau.
Et ce genre de secret utilise la pile aussi
se souvenir quand un fonction est appelée, ce qui
l'adresse est de la fonction précédente, de sorte qu'il peut revenir en arrière à cette fonction.
Ainsi, lorsque les appels principaux échanger, entre les choses ont poussé sur la pile
ne sont pas simplement les swaps variables locales, ou de ses arguments, aussi secrètement poussé
sur la pile comme représenté par la tranche rouge ici,
est l'adresse du principal physiquement dans la mémoire de votre ordinateur,
de sorte que lorsque swap est fait, l'ordinateur sait que je dois retourner au principal
et terminer l'exécution de la fonction principale.
Donc, cela est dangereux maintenant, parce que si les types d'utilisateurs dans plus de bien bonjour,
de telle sorte que l'entrée de l'utilisateur aplatit ou remplace cette section rouge,
logiquement, si de l'ordinateur juste aller à assumer aveuglément
que les octets dans cette tranche rouge sont l'adresse à laquelle elle doit retourner,
si l'adversaire est assez intelligent ou la chance de mettre une séquence d'octets
il qui ressemble à une adresse, mais il est l'adresse du Code
qu'il ou elle veut l'ordinateur à exécuter au lieu de principale?
>> En d'autres termes, si ce que le utilisateur tape à l'invite,
est pas seulement quelque chose comme inoffensive bonjour,
mais il est en fait le code qui est équivalent supprimer tous les fichiers de cet utilisateur?
Ou envoyer leur mot de passe pour moi?
Ou commencer à enregistrer leur frappes, non?
Il ya une façon, disons stipulent aujourd'hui, qu'ils pouvaient saisir non seulement bonjour
monde ou de leur nom, qu'ils pouvaient essentiellement
passer dans le code, et de zéros celles que l'ordinateur
erreurs à la fois le code et une adresse.
Donc, bien que quelque peu abstraite, si le types d'utilisateurs en code assez contradictoire
que nous allons généralisons ici A. A est l'attaque ou adversaires.
Il suffit donc de mauvaises choses.
Nous ne nous soucions pas de la les numéros ou les zéros ou
aujourd'hui, de telle sorte que vous vous retrouvez écraser cette section rouge,
remarquerez que séquence d'octets.
O 835 C zéro huit zéro.
Et maintenant, comme l'article de Wikipedia ici a proposé, si vous commencez maintenant réalité
étiqueter les octets dans votre ordinateur de la mémoire, ce que l'article de Wikipedia est
proposante est que, si l'adresse de l'octet haut à gauche est 80 C 0 3508.
>> En d'autres termes, si le méchant est assez intelligent avec son code
de mettre réellement un certain nombre ici que correspond à l'adresse du code
il ou elle injecté dans l'ordinateur, vous
peut tromper l'ordinateur en faire quelque chose.
Suppression de fichiers, e-mailing choses, renifler votre trafic,
littéralement tout ce que pourrait être injecté dans l'ordinateur.
Et si un débordement de tampon attaque à sa base
est juste un stupide, stupide impérieuse d'un tableau
ne disposent pas de ses frontières vérifiés.
Et voici ce que est super dangereux et en même temps super puissant
C est dans ce que nous avons en effet l'accès à n'importe où dans la mémoire.
Il est à nous, les programmeurs, qui écrivent le code original
pour vérifier la longueur de reprise de tout tableaux que nous manipulation.
Donc, pour être clair, quelle est la solution?
Si nous revenir à cette code, je ne devrais pas simplement
changer la longueur de la barre, ce qui dois-je vérifierai?
Que dois-je faire pour empêcher cette attaque entièrement?
Je ne veux pas juste dire aveuglément que vous devez copier autant d'octets
comme l'est la longueur de la barre.
Je tiens à dire, comme copier le nombre d'octets que sont en bar
jusqu'à la alloué la mémoire, ou 12 au maximum.
Donc je besoin d'une sorte de condition if qui ne vérifie la longueur de la barre,
mais si elle dépasse 12, on code juste dur 12 comme la distance maximale possible.
Sinon le tampon dite attaque de dépassement peut arriver.
Au bas de ces lames, Si vous êtes curieux de lire la suite
est l'article original réel Si vous souhaitez jeter un oeil.
>> Mais maintenant, parmi les prix payés ici était inefficacités.
Ce qui fut une rapide faible niveau look à quel
des problèmes peuvent survenir maintenant que nous avoir accès à la mémoire de l'ordinateur.
Mais un autre problème que nous déjà trébuché lundi
était juste l'inefficacité d'une liste chaînée.
Nous sommes de retour à temps linéaire.
Nous ne sommes plus un tableau contigu.
Nous ne disposons pas accès aléatoire.
Nous ne pouvons pas utiliser la notation crochet.
Nous avons littéralement à utiliser une boucle while comme celui que je écrit il ya un moment.
Mais lundi, nous avons affirmé que nous pouvons grimper à nouveau dans le domaine de l'efficacité
la réalisation de quelque chose qui est logarithmique peut-être, ou mieux encore,
peut-être même quelque chose qui est dite constante de temps.
Alors, comment pouvons-nous le faire en utilisant ces nouveaux outils, ces adresses, ces pointeurs,
et le filetage choses de notre propre?
Eh bien, supposons que ici, ce sont un tas
des nombres que nous voulons stocker dans un structure de données et de recherche efficace.
Nous ne pouvons absolument revenir en arrière pour la semaine deux, jeter ceux-ci dans un tableau,
et les rechercher en utilisant la recherche binaire.
Diviser et conquérir.
Et en fait, vous avez écrit recherche binaire dans PSET3,
où vous en œuvre le programme de recherche.
Mais vous savez quoi.
Il ya une sorte de plus façon intelligente de le faire.
Il est un peu plus sophistiqué et ce peut-être
nous permet de voir pourquoi binaire la recherche est tellement plus rapide.
Premièrement, nous allons introduire la notion d'un arbre.
Qui, même si dans arbres de type de réalité
grandir comme ça, dans le monde de l'informatique la science, ils poussent à la baisse type de
comme un arbre de la famille, où vous avez vos grands-parents ou grands-parents
ou quoi au sommet, le patriarche et la matriarche de la famille, un seul
dite racine, noeud, ci-dessous Quelles sont ses enfants,
ci-dessous, qui sont ses enfants, ou ses descendants plus généralement.
Et quiconque pendait le fond de la famille
arbre, en plus d'être le plus jeune dans la famille,
peut aussi être juste générique appelle les feuilles de l'arbre.
>> Donc, ceci est juste un tas des mots et des définitions
pour quelque chose appelé un arbre dans l'ordinateur la science, un peu comme un arbre généalogique.
Mais il ya incarnations fantaisistes des arbres, dont l'un
est appelé un arbre de recherche binaire.
Et vous pouvez sorte de taquinerie Outre ce que cette chose fait.
Eh bien, il est binaire dans quel sens?
D'où vient le binaire viennent ici?
Pardon?
Il est pas tellement un ou.
Il est plus que chacun des noeuds n'a pas plus de deux enfants, que nous voyons ici.
En général, un tree-- et vos parents et grands parents
peut avoir autant d'enfants ou petits-enfants qu'ils veulent réellement,
et ainsi par exemple, il nous en avons trois enfants hors de ce nœud de la main droite,
mais dans un arbre binaire, un noeud a zéro, un ou deux enfants au maximum.
Et voilà une belle propriété, parce que si elle est couronnée par deux,
nous allons être en mesure de obtenir un peu logarithme en base deux
l'action se passe ici en fin de compte.
Donc, nous avons quelque chose logarithmique.
Mais plus sur cela dans un instant.
Des moyens pour rechercher arbre que les chiffres sont agencé de telle sorte que l'enfant de gauche
La valeur est supérieure à la racine.
Et son enfant droite est plus grande que la racine.
En d'autres termes, si vous prenez un des nœuds, les cercles dans cette image,
et regarde à sa gauche enfant et son droit de l'enfant,
le premier devrait être inférieure à, le second doit être supérieure.
Donc, test de cohérence 55.
Il a laissé l'enfant est de 33.
Il est moins.
55, son droit de l'enfant est 77.
Il est supérieur.
Et voilà une définition récursive.
Nous pourrions vérifier chaque un de ceux nœuds et le même schéma tiendrait.
>> Donc, ce qui est agréable dans un arbre binaire de recherche, est
celui-là, nous pouvons mettre en œuvre avec une struct, juste comme ça.
Et même si nous jetons beaucoup de structures à votre,
ils sont peu intuitive maintenant je l'espère.
La syntaxe est encore obscur pour sûr, mais le contenu d'un noeud dans cette
context-- et nous gardons en utilisant le mot node,
que ce soit un rectangle sur l'écran ou d'un cercle,
il est juste un conteneur générique, dans ce cas, d'un arbre, tel que celui
nous avons vu, nous avons besoin d'un entier dans chacun des noeuds
et puis je besoin de deux pointeurs pointage à l'enfant gauche et la droite enfant,
respectivement.
Voilà donc comment nous pourrions mettre en œuvre que dans une structure.
Et comment pourrais-je mettre en œuvre dans le code?
Eh bien, nous allons jeter un rapide regarder ce petit exemple.
Il est non fonctionnel, mais je l'ai copié et collé cette structure.
Et si ma fonction pour un binaire arbre de recherche est appelé recherche,
et cela prend deux arguments, un nombre entier N et d'un pointeur
à un noeud, de sorte qu'un pointeur vers l'arborescence ou un pointeur vers la racine d'un arbre,
comment puis-je aller sur la recherche de N?
Eh bien, d'abord, parce que je suis traitement des pointeurs,
Je vais faire une vérification de cohérence.
Si égaux d'arbres égal nulle, est N dans cet arbre ou non dans cet arbre?
Il ne peut pas être, non?
Si je suis passé null, il n'y a rien.
Je pourrais tout aussi bien aveuglément dire return false.
Si vous me donnez rien, je ne peux pas sûrement trouver un certain nombre N. Alors quoi d'autre pourrais-je
vérifie maintenant?
Je vais bien dire d'autre si N est inférieur à ce qui est au niveau du noeud de l'arbre
que je ai été remis valeur N.
En d'autres termes, si le nombre je suis la recherche de N, est inférieur au nœud
que je suis à la recherche.
Et le nœud je cherche est appelé à arbre,
et de rappeler à partir de l'exemple précédent pour obtenir la valeur dans un pointeur,
Je l'utilise la notation de flèche.
Donc, si N est inférieur Arbre Sous- N, je veux aller conceptuellement gauche.
Comment puis-je exprimer recherchez quitté?
Pour être clair, si cela est l'image en question,
et je l'ai été adoptée que le plus haut flèche pointant vers le bas que ça.
Voilà mon pointeur de l'arbre.
Je fais remarquer à la racine de l'arbre.
Et je suis à la recherche par exemple, pour le nombre 44, arbitrairement.
44 est inférieur ou évidemment supérieure à 55?
Il est donc moins.
Et donc cela si l'état applique.
Donc, sur le plan conceptuel, ce que je veux rechercher prochaine si je suis à la recherche pour les 44?
Ouais?
>> Exactement, je veux chercher l'enfant à gauche,
ou le sous-arbre gauche de cette image.
Et en fait, permettez-moi de grâce la photo ici
pour un instant, depuis Je ne peux pas rayer cela.
Si je commence ici à 55 ans, et Je sais que la valeur 44
Je cherche est de la gauche, il est un peu
comme de déchirer le livre de téléphone dans la moitié ou déchirement de l'arbre en deux.
Je ne ai plus à se soucier toute cette moitié de l'arbre.
Et pourtant, curieusement en termes de la structure, cette chose ici que
commence par 33, qui se est un arbre de recherche binaire.
Je l'ai dit le mot récursive avant parce en effet ceci est une structure de données qui
par définition est récursive.
Vous pourriez avoir un arbre qui est présent grand, mais chacun de ses enfants
représente un arbre un peu plus petite.
Au lieu d'être grand-père ou grand-mère, maintenant il est juste maman
ou-- Je ne peux pas say-- pas maman ou papa, ce serait bizarre.
Au contraire, les deux enfants là-bas serait comme frère et sœur.
Une nouvelle génération de l'arbre généalogique.
Mais structurellement, il est la même idée.
Et il se trouve que je dois une fonction avec laquelle je peux chercher une recherche binaire
arbre.
Il est appelé recherche.
Je cherche N dans l'arbre flèche gauche sinon si N est supérieur à la valeur
que je suis actuellement à.
55 dans l'histoire il ya un instant.
Je dois une fonction appelée la recherche que je peux juste
N passer cela et rechercher de manière récursive le sous-arbre et juste retour
quelle que soit cette réponse.
Sinon je dois certains cas, de base finale ici.
>> Quel est le dernier cas?
Arbre est soit null.
La valeur soit je cherche est inférieur à ce qu'il ou supérieure à celle
ou égal à elle.
Et je pourrais dire égale égal, mais logiquement, il est
équivalent à simplement dire d'autre ici.
Tant il est vrai que je trouve quelque chose.
Il en est ainsi, espérons une exemple encore plus convaincante
que la fonction de sigma stupide nous avons fait quelques conférences dos,
où il était tout aussi facile à utiliser une boucle compter tous les chiffres de un
N. Ici, avec une structure de données qui est lui-même de façon récursive
définis et de manière récursive attirés, maintenant nous avoir la capacité de nous exprimer
dans le code qui lui-même est récursive.
Donc, cela est exactement le même code ici.
>> Alors que d'autres problèmes que nous pouvons résoudre?
Donc, un pas rapide loin de arbres pour un moment.
Ici est, disons, le drapeau allemand.
Et il ya clairement un motif à ce drapeau.
Et il ya beaucoup de drapeaux dans le monde qui
sont aussi simple que cela en termes de leurs couleurs et de motifs.
Mais supposons que cela est stocké en tant que .GIF, Ou d'un JPEG ou bitmap, ou une table de ping,
quel format de fichier graphique avec lequel vous êtes familier,
dont certains que nous sommes jouer avec dans PSET4.
Cela ne semble pas utile de stocker pixel noir, pixel noir, pixel noir,
dot, point, point, tout un tas de pixels noirs pour la première ligne de balayage,
ou une ligne, puis tout un tas de de même, puis un tas
de même, puis une tas ensemble de pixels rouges,
pixels rouges et les pixels rouges, puis tout un tas de pixels jaunes, jaune, non?
>> Il ya une telle inefficacité ici.
Comment feriez-vous intuitivement comprimer le drapeau allemand
si la mise en œuvre dans un fichier?
Comme quoi informations pouvons-nous pas peine stocker sur le disque afin
pour diminuer la taille de notre fichier à partir comme un mégaoctet à un kilo-octet, quelque chose
plus petit?
Dans laquelle se trouve la redondance ici pour être clair?
Que pourriez-vous faire?
Ouais?
Exactement.
Pourquoi ne pas plutôt que de se rappeler la couleur de chaque pixel sacrément
tout comme vous faites dans PSET4 avec le format de fichier bitmap,
pourquoi ne vous représentez pas seulement le colonne de gauche de pixels, par exemple
un tas de pixels noirs, un tas de rouge, et un tas de jaune,
et puis juste en quelque sorte l'encoder idée de répéter cette 100 fois
ou répéter cette 1000 fois?
Où est 100 ou 1000 juste un nombre entier, de sorte que vous
peut sortir avec un seul numéro au lieu de centaines ou de milliers
de pixels supplémentaires.
Et en effet, ce est comment nous pourrait comprimer le drapeau allemand.
Et
Maintenant, qu'en est-il le drapeau français?
Et un peu une sorte de exercice mental, quel drapeau
peut être comprimé plus sur le disque?
Le drapeau allemand ou les Français drapeau, si nous prenons cette approche?
Le drapeau allemand, parce qu'il ya plus de redondance horizontale.
Et par la conception, de nombreux fichiers graphiques formats ne fonctionnent en effet comme les lignes de balayage
horizontalement.
Ils pourraient travailler verticalement, juste l'humanité
il ya des années décidé que nous allons pensent généralement des choses rangée
par ligne à la place de la colonne par colonne.
Donc, en effet, si vous étiez à regarder le fichier
taille d'un drapeau allemand et un français drapeau, tant que la résolution est
de même, la même largeur et la hauteur, à celui-ci
ici va être plus grand, parce que vous avoir à vous répéter trois fois.
Vous devez spécifier bleu, répétez vous, blanc, répétez-vous, rouge,
vous répétez.
Vous ne pouvez pas aller tout le chemin vers la droite.
Et en passant, à faire désactiver la compression
est partout, si ceux-ci sont quatre trames d'une video-- vous
pourrait rappeler qu'un film ou vidéo est en général
comme 29 ou 30 images par seconde.
Il est comme un petit flip book où vous juste voir l'image, l'image, l'image, l'image,
l'image juste super rapide de sorte qu'il ressemble les acteurs sur l'écran sont en mouvement.
Voici un bourdon sur dessus d'un bouquet de fleurs.
Et si cela peut être une sorte de difficile de voir au premier coup d'œil,
la seule chose se déplaçant dans ce film est l'abeille.
>> Quel est muet sur le stockage vidéo non compressée?
Il est une sorte de déchets à stocker de la vidéo que quatre images presque identiques que
ne diffèrent que dans la mesure où lorsque l'abeille est.
Vous pouvez jeter plus de cette information
et rappelez-vous que, par exemple, la première image et la dernière image,
cadres clés Si vous avez jamais entendu le mot,
et juste stocker dans le milieu où l'abeille est.
Et vous ne devez pas stocker la totalité de la rose,
et le bleu, et de la valeurs vertes ainsi.
Donc cela pour dire seulement que la compression est partout.
Il est une technique que nous utilisons souvent ou tenir pour acquis ces jours.
>> Mais comment ne vous compressez texte?
Comment allez-vous comprimer texte?
Eh bien, chacun des personnages dans ASCII est un octet, ou huit bits.
Et cela est un peu idiot, non?
Parce que vous avez probablement de type A et E et I et O et U a beaucoup
le plus souvent comme W ou Q ou Z, en fonction de la langue dans laquelle
vous écrivez certainement.
Et alors pourquoi utilisons-nous huit bits pour chaque lettre,
y compris les moins lettres populaires, non?
Pourquoi ne pas utiliser moins de bits pour les lettres super populaire,
comme E, les choses que vous devinez d'abord dans Roue de la Fortune,
et utiliser plus de bits pour les lettres moins populaires?
Pourquoi?
Parce que nous allons juste utiliser moins fréquemment.
>> Eh bien, il se trouve qu'il ya eu les tentatives faites pour ce faire été.
Et si vous vous souvenez du grade l'école ou au lycée, le code Morse.
Morse a points et tirets qui peuvent être
transmis le long d'un fil comme des sons ou des signaux de quelque sorte.
Mais le code Morse est un super propre.
Il est une sorte de système binaire que vous avez des points ou des tirets.
Mais si vous voyez, par exemple, deux points.
Ou si vous pensez à l'opérateur qui va comme bip, bip, bip,
bip, frapper un peu de déclenchement qui transmet un signal,
si vous, le destinataire, reçoit deux points, quel message avez-vous reçu?
Complètement arbitraire.
>> JE?
JE?
Ou ce about-- ou moi?
Peut-être qu'il était juste deux droit de l'E?
Donc, il ya ce problème de décodabilité avec Morse
code, de sorte que, sauf si le personne vous envoyer le message
les pauses dans effectivement de sorte que vous pouvez trier des voir ou entendre les écarts entre les lettres,
il ne suffit pas simplement pour envoyer un flux de zéros et de uns,
ou points et de traits, parce qu'il ya ambiguïté.
E est un point unique, donc si vous voir deux points ou entendre deux points,
il est peut être deux de E ou peut-être il est l'un I.
Nous avons donc besoin d'un système qui est un peu plus intelligent que cela.
Ainsi, un homme du nom de Huffman ans Il ya venu avec exactement cela.
Donc, nous allons juste de prendre un coup d'oeil rapide
comment les arbres sont pertinentes à cet égard.
Supposons que ce soit un peu stupide message que vous souhaitez envoyer,
composé de seulement A, B, C et D de s E'S, mais il ya beaucoup de redondance ici.
Il est pas censé être l'anglais.
Il est pas crypté.
Il est juste un message stupide avec beaucoup de répétition.
Donc, si vous comptez réellement toutes les A'S, B, C de, D's, et E de, voici
la fréquence.
20% des lettres sont A'S, 45% des lettres
sont de E, et trois autres fréquences.
Nous avons compté là-haut la main et juste fait le calcul.
>> Donc, il se trouve que Huffman, il ya quelque temps,
réalisé que, vous savez ce qui, si je commence bâtiment
un arbre, ou une forêt d'arbres, si vous voulez, comme suit, je peux faire ce qui suit.
Je vais donner un noeud à chaque des lettres que je me soucie
et je vais stocker à l'intérieur de ce noeud
les fréquences en flottant valeur, ou vous pouvez utiliser un N, aussi,
mais nous allons simplement utiliser un flotteur ici.
Et l'algorithme qui il a proposé est que vous
prendre cette forêt de noeud unique arbres, arbres si super court,
et vous commencez à les relier à de nouveaux groupes, de nouveaux parents, si vous voulez.
Et vous faites cela en choisissant la deux plus petites fréquences à la fois.
Je pris donc 10% et 10%.
Je crée un nouveau nœud.
Et je l'appelle le nouveau nœud de 20%.
>> Quels sont les deux noeuds je combine ensuite?
Il est un peu ambiguë.
Donc, il ya certains cas de coin à envisager, mais de garder les choses assez,
Je vais choisir 20% - Je l'ignore maintenant les enfants.
Je vais choisir 20% et 15% et tracez deux nouveaux bords.
Et maintenant, qui deux noeuds puis-je combiner logiquement?
Ignorer tous les enfants, tous les petits-enfants, il suffit de regarder les racines
maintenant.
Quels sont les deux nœuds puis-je attacher ensemble?
Point de deux et 0,35.
Alors permettez-moi d'attirer deux nouveaux bords.
Et puis je ne ai qu'une gauche.
Alors, voici un arbre.
Et il a été tiré délibérément à regarder sorte de joli,
de remarquer que les bords ont également été marqué zéro et un.
Donc tous les bords gauche sont à zéro arbitrairement, mais constamment.
Tous les bons bords sont chers.
>> Et donc ce que Hoffman proposé est, si vous voulez représenter un B,
plutôt que de représenter le nombre 66 comme ASCII qui est entières huit bits,
vous savez quoi, magasin juste le modèle zéro, zéro, zéro,
zéro, parce que le chemin est de mon arbre, l'arbre de M. Huffman,
de la feuille à partir de la racine.
Si vous souhaitez enregistrer un E, en revanche, ne sont pas
envoyer huit bits qui représentent un E. Au lieu de cela, envoyez ce motif de bits?
One.
Et ce qui est bon à ce sujet est que E est la lettre la plus populaire,
et vous utilisez le le plus court code pour elle.
La prochaine plus populaire lettre ressemble à elle
était A. Et si le nombre de bits at-il proposer en utilisant pour cela?
Zéro, un.
>> Et parce qu'il est mis en œuvre comme cet arbre, pour l'instant
laissez-moi stipule par il ya aucune ambiguïté quant à Morse
code, parce que tous les lettres que vous vous souciez
sont à la fin de ces bords.
Voilà donc un seul application d'un arbre.
Cette est-- et je vais vague ma main à ce comment vous
pourrait mettre en œuvre ce que une structure C.
Nous avons juste besoin de combiner un symbole, comme un char,
et la fréquence à gauche et à droite.
Mais regardons deux derniers exemples que vous aurez
être assez familier avec après Quiz zéro problème réglé cinq.
>> Donc, il ya la structure de données connu comme une table de hachage.
Et une table de hachage est une sorte de refroidir en ce qu'il comporte des seaux.
Et suppose qu'il ya quatre seaux ici, seulement quatre espaces.
Voici un jeu de cartes, et est ici club, pelle, club, diamants, club,
diamants, clubs, diamants, clubs-- ce est donc le hasard.
Coeurs, hearts-- donc je suis bucketizing toutes les entrées ici.
Et un besoins de table de hachage de regarder votre entrée,
et puis le mettre dans un certain placer sur la base de ce que vous voyez.
Il est un algorithme.
Et je me sers d'un super- algorithme visuel simple.
La partie la plus difficile de ce qui était rappelant ce que les photos étaient.
Et puis il ya quatre choses totaux.
>> Maintenant, les piles ont été de plus en plus, ce qui est une conception délibérée chose ici.
Mais quoi d'autre pourrais-je faire?
Donc en fait nous avons ici un tas de vieux livres d'examen de l'école.
Supposons qu'un groupe de noms étudiants sont ici.
Voici une grande table de hachage.
Au lieu de quatre seaux, Je suis, disons 26.
Et nous ne voulons pas aller emprunter 26 choses de [l'extérieur? Annenberg?], De sorte
voici cinq qui représentent A à Z. Et si je
voir un étudiant dont le nom commence par A, Je vais à son questionnaire mis là.
Si quelqu'un commence par C, là-bas, A- effectivement, ne voulait pas le faire.
B va ici.
Donc, je dois A et B et C. Et voici maintenant un autre étudiant.
Mais si cette table de hachage est mis en oeuvre avec un réseau,
Je suis un peu foiré à ce point, non?
Je sorte de besoin de le mettre quelque part.
>> Donc, d'une manière que je peux résoudre ce problème est, tout à droite, un est occupé, B est occupé, C est occupé.
Je vais le mettre dans D. Ainsi, à Premièrement, je dois accès instantané aléatoire
à chacun des godets pour les étudiants.
Mais maintenant, il est une sorte de dévolue en quelque chose linéaire,
parce que si je veux chercher quelqu'un dont le nom commence par A, je vérifie ici.
Mais si tel est le pas A étudiant, je suis à la recherche,
Je dois sorte de commencer à vérifier les seaux, parce que ce que je faisais
était en quelque sorte linéairement sonder la structure de données.
Une façon stupide de dire il suffit de regarder pour la première ouverture disponibles,
et de mettre comme un plan B, pour ainsi dire, ou le plan D dans ce cas, la valeur
à cet endroit à la place.
Ceci est juste de sorte que si vous avez obtenu 26 endroits et pas d'étudiants
avec le nom Q ou Z, ou quelque chose comme que, au moins vous utilisez l'espace.
>> Mais nous avons déjà vu plus solutions intelligentes ici, non?
Que feriez-vous à la place si vous avez une collision?
Si deux personnes ont Un nom, ce serait
ont été plus intelligents ou plus solution intuitive que juste
Mettre un où D est censé être?
Pourquoi dois-je pas simplement aller dehors [? Annenberg?],
comme malloc, un autre nœud, le mettre ici, et ensuite mettre qu'un étudiant ici.
Alors que je dois essentiellement une sorte d'un tableau,
ou peut-être avec plus d'élégance que nous sommes commençons à voir une liste chaînée.
>> Et donc une table de hachage est une structure qui pourrait ressembler à cela,
mais plus intelligemment, vous quelque chose appelé chaînage séparé, dans lequel une table de hachage
est tout simplement un tableau, chacun des dont les éléments ne sont pas un certain nombre,
est lui-même une liste chaînée.
Alors que vous obtenez un accès ultra-rapide décider où votre valeur à hacher.
Tout comme avec l'exemple des cartes, Je pris des décisions super rapide.
Coeurs va ici, diamants va ici.
Même ici, A va ici, D va ici, B va ici.
Donc super rapides look-ups, et si vous arrive de courir dans un cas
collisions où vous avez, deux les personnes ayant le même nom, eh bien
vous venez de commencer les reliant.
Et peut-être vous les gardez triées par ordre alphabétique, peut-être vous ne le faites pas.
Mais au moins maintenant nous avons le dynamisme.
Donc, d'une part, nous avons super rapide constante de temps, et le type de temps linéaire
impliqués si ces listes chaînées commencer à obtenir un peu long.
>> Donc, ce genre de stupide, Il ya plaisanterie ans geek.
Au CS50 bidouille-o-thon, lorsque les élèves check-in,
certains TF ou CA chaque année pense qu'il est drôle à mettre en place
un signe de ce genre, où il vient signifie que si votre nom commence par un A,
aller dans cette voie.
Si votre nom commence avec un B, aller this-- OK,
il est drôle peut-être plus tard dans le semestre.
Mais il ya un autre façon de le faire, aussi.
Revenez à cela.
>> Donc, il ya cette structure.
Et ceci est notre dernière la structure pour aujourd'hui,
qui est quelque chose appelé un trie.
T-R-I-E, qui pour une raison est courte pour la récupération, mais il est appelé Trie.
Donc un trie est une autre intéressante amalgame de beaucoup de ces idées.
Il est un arbre, que nous avons vu auparavant.
Il est pas un arbre de recherche binaire.
Il est un arbre avec un certain nombre d'enfants, mais chacun des enfants dans un trie
est un tableau.
Un tableau de taille, disons, 26 ou peut-être 27 si vous voulez soutenir noms trait d'union
ou apostrophes dans les noms des personnes.
>> Et si cela est une structure de données.
Et si vous regardez de haut en bas, comme si vous
regarder le nœud supérieur là, M, est pointant à la chose la plus à gauche il,
qui est alors A, X, W, E, L, L. Ceci est seulement une structure de données qui arbitrairement
est mémoriser les noms des personnes.
Et Maxwell est stocké en suivant simplement un chemin de tableau en tableau en tableau.
Mais ce qui est étonnant sur un trie est que, si une liste chaînée et même
un tableau, le meilleur que nous ayons eu est temps linéaire ou logarithmique à la recherche du temps
quelqu'un.
Dans cette structure de données d'une trie, si ma structure de données a un nom dans ce
et je suis à la recherche pour Maxwell, je suis va le trouver assez rapidement.
Je viens de regarder pour M-A-X-W-E-L-L. Si cette structure de données, en revanche,
si N est un million, si il ya un millions de noms dans cette structure de données,
Maxwell va encore être détectable après seulement M-A-X-W-E-L-L
étapes.
Et étapes David-- D-A-V-I-D.
En d'autres termes, en construisant une structure de données qui est
obtenu l'ensemble de ces matrices, qui se soutenir l'accès aléatoire,
Je peux commencer à chercher jusqu'à autrui nom en utilisant une quantité de temps qui est
proportionnelle à pas le nombre des choses dans la structure de données,
comme un million de noms existants.
La quantité de temps qu'il me faut pour trouver M-A-X-W-E-L-L dans cette structure de données est
pas proportionnelle à la taille de la structure de données,
mais à la longueur du nom.
Et réaliste le noms Nous sommes regardant
ne vont jamais être fou longtemps.
Peut-être quelqu'un a un caractère 10 nom, nom de 20 caractères.
Il est certainement finie, non?
Il est un être humain sur Terre qui a le nom le plus long possible,
mais ce nom est une constante longueur de valeur, non?
Il ne varie pas dans tous les sens.
Donc, dans ce sens, nous avons atteint une structure de données
qui est constante de temps look-up.
Il prend un certain nombre de mesures en fonction de la longueur de l'entrée,
mais pas le nombre de nom dans la structure de données.
Donc, si nous doublons le nombre de noms l'année prochaine d'un milliard à deux milliards,
constatation Maxwell va prendre exactement le même nombre de sept étapes
pour le retrouver.
Et si nous semblons avoir atteint notre saint Graal de la durée de fonctionnement.
>> Alors quelques annonces rapides.
Quiz zéro est à venir.
Plus de détails sur ce que sur le site Web de cours au cours des prochains jours.
Lundis lecture-- il est un jour férié ici à Harvard lundi.
Il est pas à New Haven, nous sommes donc en prenant la classe
à New Haven pour conférence le lundi.
Tout sera filmé et retransmis en direct comme d'habitude,
mais finissons aujourd'hui avec un deuxième clip 30
appelés "pensées profondes" par Daven Farnham, qui
a été inspiré l'an dernier le samedi "Pensées profondes" de Night Live
par Jack Handy, qui devrait maintenant donner un sens.
>> FILM: Et maintenant, "Deep Pensées "de Daven Farnham.
Table de hachage.
>> ENCEINTE 1: Très bien, qui est pour l'instant.
Nous vous verrons la semaine prochaine.
>> DOUG: Pour le voir en action.
Donc, nous allons jeter un oeil à ce droit maintenant.
Donc, ici, nous avons un tableau non triés.
>> IAN: Doug, pouvez-vous aller de l'avant et de redémarrage cela pour seulement une seconde, s'il vous plaît.
Tout droit, caméras tournent, donc l'action chaque fois que vous êtes prêt, Doug, OK?
DOUG: Très bien, alors ce que nous avons ici est un tableau non triés.
Et je l'ai colorié tous les éléments rouge pour indiquer qu'il est, en fait,
non triés.
Donc, rappelons que la première chose que nous faisons est que nous trions la moitié gauche du tableau.
Ensuite, nous trions le droit moitié de la matrice.
Et ya-da, da-Ya, ya-da, nous fusionnons ensemble.
Et nous avons un tableau complètement triée.
Voilà donc comment fonctionne le tri par fusion.
>> IAN: Whoa, whoa, whoa, couper, couper, couper, couper.
Doug, vous ne pouvez pas simplement Ya-da, ya-da, Ya-da, votre chemin à travers le tri par fusion.
>> DOUG: Je viens de faire.
C'est bien.
Nous sommes bon pour aller.
Gardons laminage.
De toute façon,
>> IAN: Vous devez expliquer plus pleinement que cela.
Voilà tout simplement pas assez.
DOUG: Ian, nous ne faisons pas besoin de revenir à un.
C'est bien.
Donc de toute façon, si nous continuons avec merge-- Ian, nous sommes dans le milieu du tournage.
>> IAN: Je sais.
Et nous ne pouvons pas simplement Ya-da, ya-da, Ya-da, à travers l'ensemble du processus.
Vous devez expliquer comment le deux côtés se fusionnés.
>> DOUG: Mais nous avons déjà expliqué comment les deux sides--
>> IAN: Vous venez montré elle toute une gamme de fusion.
DOUG: ils savent le processus.
Ils vont bien.
Nous avons dépassé dix fois.
>> IAN: Vous venez sauté droit sur elle.
Nous allons revenir à un, vous tu ne peux pas Ya-da, da ya-dessus.
Tout droit, le dos à un.
>> DOUG: Je dois retourner à travers toutes les diapositives?
Mon Dieu.
Il est comme la sixième fois, Ian.
C'est bien.
>> IAN: Très bien.
Tu es prêt?
Génial.
Action.