>> LUIDSPREKER 1: Oke, dus we zijn terug.
Welkom op CS50.
Dit is het einde van week zeven.
Zo herinneren dat vorige keer, we begonnen bekeken iets meer verfijnde
datastructuren.
Omdat tot nu toe, al hadden we echt tot onze beschikking was dit, een array.
>> Maar voordat we gooi de array als niet zo interessant, dat het inderdaad
eigenlijk, wat zijn sommige van de pluspunten van deze eenvoudige gegevens
structuur tot nu toe?
Wat is er goed aan?
Voor zover wij hebben gezien?
Wat heb je?
Niets.
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Wat is dat?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Vaste grootte.
OK, dus waarom is vaste grootte wel goed?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: OK, dus het is efficiënt in de zin dat je kunt toewijzen van een
vaste hoeveelheid ruimte, die hopelijk juist zoveel
ruimte als je wilt.
Zodat absoluut een plus kan.
>> Wat is een ander up kant van een array?
Yeah?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Alle - sorry?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Alle vakken in het geheugen of naast elkaar.
En dat is nuttig - waarom?
Dat is helemaal waar.
Maar hoe kunnen we die waarheid te benutten?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Precies, we kunnen bijhouden waar alles is gewoon door te weten
een adres, namelijk het adres van de eerste byte van dat stuk van het geheugen.
Of in het geval van de tekenreeks het adres van de eerste
char in die string.
En van daar, vinden we het einde van de string.
We kunnen het tweede element, het vinden derde element, enzovoort.
>> En zo de mooie manier van het beschrijven van die kenmerk is dat arrays geven ons
random access.
Gewoon door het gebruik van de vierkante haak notatie en een nummer, kunt u naar
een specifiek element in de array in constante tijd, big O
van een, zo te zeggen.
>> Maar er is al een aantal nadelen.
Wat een array niet heel gemakkelijk te doen?
Wat is er niet goed in?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Wat is dat?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Uitbreiding in omvang.
Dus de nadelen van de array precies het tegenovergestelde van wat de
Pluspunten zijn.
Dus een van de minpunten is dat het een vaste grootte.
Dus je kunt niet echt groeien.
U kunt een groter stuk van herverdelen geheugen, en verplaats de oude elementen
in de nieuwe matrix.
En dan gratis de oude array, voor Bijvoorbeeld door malloc of soortgelijk
functie genaamd realloc, die bijstuurt in het geheugen.
>> Realloc, als een terzijde, probeert u geheugen dat is naast de array
die je al hebt.
Maar het kan dingen verplaatsen rond geheel.
Maar in het kort, dat is duur, toch?
Want als je een stuk van het geheugen van deze grootte, maar je echt wilt een
van deze omvang, en u wilt behouden de oorspronkelijke elementen, je hebt
ruwweg een lineaire tijd kopieerproces die moet gebeuren vanaf
oude scala aan nieuwe.
En de realiteit vraagt ​​het besturingssysteem systeem weer en
opnieuw voor grote delen van het geheugen kan beginnen kost je wat tijd ook.
Dus het is zowel een zegen als een vloek in verhullen dat deze arrays
zijn van vaste grootte.
Maar als we introduceren in plaats daarvan iets als dit, waar we wel een gekoppelde
lijst, krijgen we een paar positieve kanten en een paar nadelen hier ook.
>> Dus een gelinkte lijst is gewoon een data constructie bestaande uit C structs in deze
geval, waarbij een structuur, recall, is gewoon een houder voor een of meer specifieke
typen variabelen.
In dit geval, wat doen de data types lijken binnenkant van de structuur dat
laatste keer dat we wel een knoop?
Elk van deze rechthoeken is een knooppunt.
En elk van de kleinere rechthoeken erin een gegevenstype.
Welke soorten hebben wij zeggen ze waren op maandag?
Yeah?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Een variabele en een pointer, of namelijk om int voor n,
en een pointer op de bodem.
Deze beide toevallig 32 bits, bij minst op een computer als deze CS50
Apparaat, en dus zijn ze even groot getekend.
>> Dus waar met behulp van de aanwijzer hoewel voor blijkbaar?
Waarom voeg deze pijl nu wanneer arrays waren zo mooi en schoon en eenvoudig?
Wat is de wijzer doet voor ons in elk van deze knooppunten?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Precies.
Het vertelt je waar de volgende is.
Dus ik soort van gebruik van de analogie van met behulp van een draad om een ​​soort van
rijg deze knooppunten samen.
En dat is precies wat we doen met pointers omdat elk van deze
delen van het geheugen al dan niet aaneengesloten, rug aan rug aan rug
binnenkant van RAM, want elke keer dat u bellen malloc zeggen, geef mij genoeg
bytes voor een nieuw knooppunt, het misschien hier zijn of het zou hier te zijn.
Het zou hier te zijn.
Je weet het gewoon niet.
>> Maar het gebruik van pointers in de adressen van die knopen, kunt u steek ze
samen op een manier die lijkt visueel als een lijst, zelfs als deze dingen zijn
allemaal verspreid door je een of je twee of uw vier gigabyte aan RAM-geheugen
binnenkant van uw eigen computer.
>> Dus het nadeel, dan, een gekoppelde lijst is wat?
Wat is een prijs die we blijkbaar betalen?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Meer ruimte, toch?
We hebben, in dit geval, een verdubbeling van het bedrag dat van de ruimte omdat we weg
van 32 bits voor elk knooppunt voor elk int, dus nu 64 bits omdat we moeten
houden rond een pointer ook.
Je krijgt meer efficiency als uw struct is groter dan deze eenvoudige zaak.
Als je eigenlijk een student binnen waarvan een paar strings voor
naam en het huis, misschien een ID-nummer, misschien nog enkele andere gebieden helemaal.
>> Dus als je een groot genoeg structuur, dan misschien de kosten van de aanwijzer
niet zo'n big deal.
Dit is een beetje een hoek geval in dat we zijn het opslaan van een dergelijke eenvoudige primitieve
binnenzijde van de gekoppelde lijst.
Maar hetzelfde is.
Je bent zeker meer uitgeven geheugen, maar je krijgt
flexibiliteit.
Want nu als ik wil een element toe te voegen aan het begin van deze lijst,
Ik moet een nieuw knooppunt toe te wijzen.
En ik moet gewoon werken die pijlen of andere manier door gewoon bewegen
sommige wijzers rond.
>> Als ik iets wil invoegen in de midden van de lijst, heb ik niet te
duwen iedereen opzij zoals we deden in weken 'verleden met onze vrijwilligers die
vertegenwoordigde een array.
Ik kan gewoon toewijzen van een nieuw knooppunt en wijs gewoon de pijlen in
verschillende richtingen omdat het niet hebben feitelijke blijven
geheugen een echte lijn zoals ik heb getekend het hier op het scherm.
>> En dan tot slot, als je wilt invoegen iets aan het einde van de lijst is
nog eenvoudiger.
Dit is een soort van willekeurige notatie, maar 34 van de pointer, neem een ​​gok.
Wat is de waarde van de pointer meest waarschijnlijk getekend beetje als een oude
school-antenne daar?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Het is waarschijnlijk nul.
En inderdaad, dat is een auteur weergave van null.
En het is null omdat je absoluut moeten weten wanneer het einde van een gekoppelde
lijst is, opdat je volgende te houden en volgen en het volgen van deze pijlen
om wat vuilnis waarde.
Dus null zal betekenen dat er geen meer knooppunten rechts van het getal 34,
in dit geval.
>> Dus stellen wij voor dat we kunnen implementeren dit knooppunt in de code.
En we hebben dit soort gezien van syntax voor.
Typedef gewoon definieert een nieuw type voor ons, geeft ons een synoniem als
koord was voor char *.
In dit geval gaat het om ons te geven verkorte schrijfwijze zodat struct knooppunt
kan in plaats daarvan alleen geschreven worden als knooppunt, dat is veel schoner.
Het is een stuk minder verbose.
>> Binnenkant van een knooppunt is blijkbaar een int riep n, en dan is een struct knoop *
wat betekent dat precies wat we wilden de pijlen te betekenen, een pointer naar een andere
knoop van exact hetzelfde gegevenstype.
En ik stel voor dat we konden implementeren van een zoekfunctie zoals deze, die op
het eerste gezicht lijkt een beetje complex.
Maar laten we het zien in de context.
>> Laat me over te gaan naar het toestel hier.
Laat ik het openen van een bestand met de naam lijst nul dot h.
En dat alleen bevat de definitie wij zag net een moment geleden voor deze data
soort heet een knooppunt.
Dus hebben we dat in een punt h bestand gezet.
>> En als een terzijde, hoewel dit programma dat u gaat zien is
niet zo ingewikkeld, het is inderdaad conventie bij het schrijven van een programma om
zet dingen zoals data types, te trekken constanten soms, binnenkant van uw
header-bestand en niet noodzakelijk in Uw C-bestand, zeker als je
programma's te krijgen groter en groter, zodat je weet waar te kijken voor zowel
documentatie in sommige gevallen, of voor de basics zoals deze, de
definitie van een soort.
>> Als ik het nu open lijst nul dot c, merken een paar dingen.
Het omvat een paar header files, de meeste waarvan wij eerder hebben gezien.
Het omvat een eigen header file.
>> En als een terzijde, waarom dat is dubbel citaten hier, in tegenstelling tot de hoek
beugels op de lijn die Ik heb daar gemarkeerd?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Ja, dus het is een lokaal bestand.
Dus als het een lokaal bestand van je eigen hier op lijn 15, bijvoorbeeld, gebruikt u
de dubbele aanhalingstekens in plaats van de haakjes.
>> Nu is dit soort van interessant.
Merk op dat ik een globale heb verklaard variabele in dit programma op lijn 18
eerste genoemd, waarbij het idee is dit naar een pointer naar de eerst
knoop in mijn gelinkte lijst, en ik heb geïnitialiseerd op null, want ik heb
geen werkelijke toegewezen nodes nog net.
>> Dus dit betekent, pictorially, wat we zag daarnet in de foto als
dat aanwijzer op de ver linkerhand.
Dus nu, dat de wijzer heeft geen pijl.
Het is in plaats daarvan gewoon nul.
Maar het vertegenwoordigt wat zijn de adres van de eerste werkelijke
knooppunt in deze lijst.
Dus ik heb uitgevoerd is het een mondiaal omdat, zoals u zult zien, dit alles
programma niet in het leven is te implementeren een gekoppelde lijst voor mij.
>> Nu heb ik een paar prototypes hier.
Ik besloot om functies zoals implementeren deletie, insertie, zoeken, en
traversal -
de laatste alleen maar lopen over de lijst, het afdrukken van haar elementen.
En nu hier is mijn main routine.
En wij zullen niet te veel tijd besteden aan deze aangezien dit soort van, hopelijk
oude hoed van nu.
>> Ik ga het volgende doen, terwijl de gebruiker werkt.
Zo een, ik ga om te printen uit dit menu.
En ik heb het zo geformatteerd netjes als ik kon.
Als types de gebruiker in een, dat betekent ze iets willen verwijderen.
Als types de gebruiker in twee, dat betekent ze iets willen invoegen.
Enzovoort.
Ik ga dan prompt dan voor een opdracht.
En dan ga ik getInt gebruiken.
>> Dus dit is een heel eenvoudige menuing interface waar je alleen maar te typen
een aantal mapping een van deze opdrachten.
En nu heb ik een mooie schone schakelaar verklaring dat gaat schakelen
wat de gebruiker intikt:
En als ze getypt een, ik zal roepen verwijderen en breken.
Als ze twee getypt, ik zal bel invoegen en breken.
>> En nu merkt dat ik heb elke gezet deze op dezelfde lijn.
Dit is slechts een stilistische beslissing.
Typisch dat we iets gezien als dit.
Maar ik heb net besloten, eerlijk gezegd, mijn programma leek meer leesbaar omdat
het was slechts vier gevallen gewoon een lijst is als volgt.
Helemaal legitiem gebruik van stijl.
En ik ga doen dit zolang de gebruiker heeft geen nul getypt, die ik
besloten zal betekenen dat ze willen stoppen.
>> Dus let nu op wat ik ben hier gaan doen.
Ik ga naar de lijst blijkbaar bevrijden.
Maar meer op dat in slechts een moment.
Laten we eerst dit programma uit te voeren.
Dus laat me een grotere terminal venster, dot slash lijst 0.
Ik ga om te gaan en invoegen typen twee, een aantal net 50, en nu
zie je de lijst is nu 50.
En mijn tekst gewoon gebladerd een beetje.
Dus nu let op de lijst bevat het nummer 50.
>> Laten we een andere insert door het nemen van twee.
Laten we het nummer in als een.
Lijst nu een, gevolgd door 50.
Dus dit is gewoon een tekstuele representatie van de lijst.
En laten we voegen nog een nummer als het nummer 42, die hopelijk is
gaan om te eindigen in het midden, omdat dit programma in het bijzonder sorteert het
elementen zoals plaatst ze.
Dus daar hebben we het.
Super eenvoudig programma dat kan absoluut gebruik hebben gemaakt van een array, maar ik
toevallig worden met behulp van een gelinkte lijst gewoon zo kan ik dynamisch
groeien en krimpen.
>> Dus laten we eens een kijkje te zoeken, als ik run command drie, ik wil zoeken
voor bijvoorbeeld het getal 43.
En niets was blijkbaar gevonden, want ik kreeg geen antwoord.
Dus laten we dit opnieuw doen.
Zoeken.
Laten we zoeken naar 50, of liever zoeken voor 42, wat een leuke heeft
weinig subtiele betekenis.
En ik vond de zin van het leven daar.
Nummer 42, als je niet weet de verwijzing, Google het.
Oke.
Dus wat heeft dit programma voor mij gedaan?
Het is gewoon me toegestaan ​​om daarmee te voegen ver en zoeken naar elementen.
>> Laten we snel vooruit, dan, om die functie hebben we een blik geworpen op
op maandag als een teaser.
Dus deze functie, beweren ik, zoekt naar een element in de lijst door eerst
men, dat de gebruiker en dan bellen GetInt tot een daadwerkelijke int krijgen
dat u wilt zoeken.
>> Merkt dan dit.
Ik ga een tijdelijke variabele maken in lijn 188 genaamd wijzer -
PTR -
zou hebben genoemd niets.
En het is een pointer naar een knooppunt omdat ik zei knooppunt * er.
En ik ben te initialiseren om gelijk te zijn eerst zodat ik daadwerkelijk heb mijn
vinger als het ware op het eerste element van de lijst.
Dus als mijn rechterhand hier is PTR ik ben wijzend op het zelfde ding dat eerst
wijst op.
>> Dus nu terug in de code, wat gebeurt er -
Dit is een veel voorkomende paradigma toen itereren meer dan een structuur als een
gelinkte lijst.
Ik ga het volgende doen terwijl pointer is niet gelijk aan So null terwijl
mijn vinger is niet wijst op een null waarde, als aanwijzer n gelijk is aan n.
Eerst zullen we merken dat n is wat de gebruiker ingetypt per GetInts noemen hier.
>> En aanwijzer n betekent wat?
Nou als we terug gaan naar de foto hier, als ik een vinger wijzen naar
dat eerste knooppunt bevat negen, pijl betekent in wezen naar die
knooppunt en pak de waarde op locatie n, in dit geval, het gegevensveld genoemd n.
>> Als een terzijde - en we zagen dit een paar van weken geleden, toen iemand vroeg -
Deze syntax is nieuw, maar het doet niet geef ons krachten die we
nog niet had.
Wat was deze zin gelijk aan het gebruik puntnotatie en ster een paar
van weken geleden, toen we terug gepeld deze laag een beetje te vroeg?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Precies, het was ster, en toen was het ster dot n, met
haakjes hier, die eruit ziet, eerlijk gezegd, ik denk dat veel
meer cryptisch te lezen.
Maar ster pointer, zoals altijd, middelen gaan daar.
En als je eenmaal daar bent, welke gegevens veld wilt u toegang?
Nou je het puntnotatie gebruiken om toegang te een structs data veld, en ik
specifiek willen n.
>> Eerlijk gezegd, ik zou dit pleiten is gewoon moeilijker te lezen.
Het is moeilijker te onthouden waar niet de haakjes te gaan, het
ster en dat allemaal.
Dus de wereld is besloten een aantal syntactische suiker, zo te zeggen.
Gewoon een sexy manier om te zeggen, dit is gelijk, en
misschien meer intuïtief.
Als wijzer is inderdaad een pointer, de pijl notatie middelen gaan daar en vinden
het veld in dit geval heet n.
>> Dus als ik vind het, let op wat ik doe.
Ik heb gewoon uitprinten, ik vond procent i, het aansluiten van de waarde voor die int.
Ik roep slapen voor een seconde gewoon naar soort van de pauze dingen op het scherm om
geven de gebruiker een tweede te absorberen wat er net gebeurd.
En dan breken ik.
Anders, wat moet ik doen?
Ik wijzer update naar gelijke aanwijzer pijl naast.
>> Dus gewoon om duidelijk te zijn, betekent dit gaan er, met behulp van mijn oude school notatie.
Dus dit betekent gewoon naar wat je bent goed op, dat in de zeer
eerste geval is ben ik wijzend op de structuur met negen erin.
Dus ik heb er gegaan.
En dan is de dot-notatie betekent, krijgen de waarde bij de volgende.
>> Maar de waarde, ook al is getekend als een smalle, is maar een getal.
Het is een numeriek adres.
Dus deze ene regel code, of geschreven als dit, de meer cryptische
manier, of als dit, de iets meer intuïtieve manier, betekent gewoon bewegen mijn hand
vanaf het eerste knooppunt naar het volgende, en dan de volgende, en vervolgens de
volgende, enzovoort.
>> Dus zullen we niet stilstaan ​​bij de andere implementaties van invoegen en verwijderen
en traversal, de eerste twee van die vrij betrokken.
En ik denk dat het heel makkelijk te krijgen verloren bij het doen van het mondeling.
Maar wat we hier kunnen doen is proberen te bepalen hoe
best dit visueel doen.
Want ik stel voor dat als we willen elementen invoegen in dit
bestaande lijst, die heeft vijf elementen -
9, 17, 22, 26 en 33 -
als ik zou gaan om dit te implementeren in code, ik moet nadenken over hoe om te gaan
over dit te doen.
>> En ik stel het nemen van kleine stapjes waarbij, in dit geval bedoel ik, wat zijn
de mogelijke scenario's die we kunnen ondervinden in het algemeen?
Bij de uitvoering van inzetstuk voor een gekoppelde lijst, dit gewoon toevallig een
specifiek voorbeeld van grootte vijf.
Nou als je een nummer wilt invoegen, willen zeggen dat de nummer een, en
behoud gesorteerde volgorde, waarbij uiteraard wel de nummer een moeten
gaan in dit specifieke voorbeeld?
Net als in het begin.
>> Maar wat interessant is dat als je er een wilt invoegen in dit
lijst, welke speciale wijzer nodig heeft te blijkbaar worden bijgewerkt?
Eerste.
Dus ik zou zeggen, dit is het eerste geval dat wij zou willen overwegen, een
scenario met het invoegen op het begin van de lijst.
>> Laten we plukken uit misschien een zo makkelijk of zelfs eenvoudiger geval, relatief gezien.
Stel dat ik wil het invoegen nummer 35 in gesorteerde volgorde.
Het behoort uiteraard daar.
Dus wat wijzer uiteraard gaat moeten worden bijgewerkt in dat scenario?
34's pointer steeds niet null maar het adres van de struct
met het nummer 35.
Dus dat is het geval twee.
Dus al, ik ben een soort quantizing hoeveel werk ik moet doen hier.
>> En tenslotte de hand liggende middelste zaak inderdaad, in het midden, als ik wil
Steek zoiets als zeggen 23, dat gaat tussen 23 en 26, maar
nu dingen een beetje meer betrokken omdat wat
pointers moeten worden veranderd?
Zo 22 moet uiteraard worden veranderd omdat hij niet kan wijzen naar 26 meer.
Hij moet naar het nieuwe knooppunt Ik moet wijzen door te bellen naar
malloc of een equivalent.
>> Maar dan moet ik ook aan dat nieuwe knooppunt, 23 in dit geval, om haar pointer hebben
wijzend op wie?
26.
En er komt wel een volgorde van bewerkingen hier.
Want als ik dit doe dwaas, en ik bijvoorbeeld beginnen bij het begin van
de lijst en mijn doel is om in te voegen 23.
En ik check, behoort het Hier, in de buurt van negen?
Nee.
Het maakt hier deel van uitmaken, naast de 17?
Nee.
Doet het hier hoort naast de 22?
Ja.
>> Nu, als ik hier ben dom, en niet denken dat dit door, ik zou
toewijzen mijn nieuwe knooppunt voor 23.
Ik zou de aanwijzer van werken het knooppunt genaamd 22, wijzend
het op het nieuwe knooppunt.
En wat heb ik te updaten wijzer van de nieuwe node te zijn?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Precies.
Wijzend op 26.
Maar dammit als ik niet al updaten 22's pointer punt op deze man, en
nu heb ik weeskinderen, de rest van de lijst, om zo te zeggen.
Dus volgorde van bewerkingen hier zal belangrijk.
>> Om dit te doen zou ik stelen, zeggen zes vrijwilligers.
En laten we kijken of we dit kunnen doen visueel in plaats van code-wise.
En we hebben een aantal mooie spanning ballen voor u vandaag.
OK, hoe over een, twee, in de weer - op het einde daar.
drie, vier, jullie allebei jongens op het einde.
En vijf, zes.
Tuurlijk.
Vijf en zes.
Oke en we zullen komen om jullie de volgende keer.
Oke, kom op maximaal.
>> Oke, omdat je hier eerst, zou je graag de ene onhandig
in Google Glass hier?
Oke, ja, OK, Glas, opnemen van een video.
OK, je bent goed om te gaan.
>> Oke, dus als jullie kunnen komen over Hier, heb ik van tevoren voorbereid
sommige nummers.
Oke, kom eens hier.
En waarom heb je niet een beetje gaan verder op die manier.
En laten we eens kijken, wat is uw naam, met de Google Glass?
>> STUDENT: Ben.
>> LUIDSPREKER 1: Ben?
OK, Ben, je zult eerst zijn, letterlijk.
Dus we gaan naar je sturen aan het einde van de etappe.
Oke, en uw naam?
>> STUDENT: Jason.
>> LUIDSPREKER 1: Jason, OK zul je zijn nummer negen.
Dus als je wilt Ben die weg te volgen.
>> STUDENT: Jill.
>> LUIDSPREKER 1: Jill, je gaat worden 17, dat als ik dit meer had gedaan
intelligent, zou ik begon aan het andere uiteinde.
Je gaat die kant op.
22.
En jij bent?
>> STUDENT: Mary.
>> LUIDSPREKER 1: Maria, zult u 22.
En uw naam is?
>> STUDENT: Chris.
>> LUIDSPREKER 1: Chris, zult u 26.
En dan tot slot.
>> STUDENT: Diana.
>> LUIDSPREKER 1: Diana, zult u 34.
Dus kom je over meer dan hier.
>> Oke, dus perfectioneren naargelang bestellen reeds.
En laten we verder gaan en doen dit zodat we kunnen echt -
Ben je gewoon een soort van kijken uit in niets daar.
OK, dus laten we verder gaan en verbeelden dit met armen, net als ik was, precies,
wat er gaande is.
Dus ga je gang en geef jezelf een voet of twee tussen uzelf.
En ga je gang en wijzen met een hand te wie je ook moeten wijzen op
gebaseerd.
En als je null bent gewoon wijzen recht naar beneden naar de vloer.
OK, so good.
>> Dus nu hebben we een gelinkte lijst, en laat mij stel dat ik de rol van spelen
PTR, dus ik zal niet de moeite de voortzetting van deze rond.
En dan - iemand dom conventie - U kunt dit alles wat je wilt noemen -
voorganger wijzer, pred wijzer -
het is gewoon de bijnaam we gaven onze voorbeeldcode aan mijn linkerhand.
De andere kant dat gaat worden houden bijhouden van wie is wie in de
volgende scenario.
>> Dus stel, eerste, ik wil eraf rukken dat eerste voorbeeld van het plaatsen, zeg
20, in de lijst.
Dus ik ga iemand nodig hebben belichamen het nummer 20 voor ons.
Dus ik moet malloc iemand uit het publiek.
Kom maar naar boven.
Wat is je naam?
>> STUDENT: Brian.
>> LUIDSPREKER 1: Brian, oke, dus je stelt het knooppunt met 20 zijn.
Oke, kom eens hier.
En natuurlijk voorkomend doet Brian behoort?
Dus, in het midden - eigenlijk, wacht een minuut.
We doen dit in de juiste volgorde.
We maken dit een stuk moeilijker dan het moet zijn op het eerste.
OK, we gaan vrij Brian en realloc Brian als vijf.
>> OK, dus nu willen we voegen Brian als vijf.
Dus kom eens hier naast Ben voor slechts een moment.
En je kunt waarschijnlijk vertellen waar dit verhaal gaat.
Maar laten we goed nadenken over de volgorde van de bewerkingen.
En het is juist deze visuele dat gaat line-up
met die voorbeeldcode.
Dus hier heb ik PTR wijst in eerste instantie Ben niet, per se, maar op welk
waarde hij bevat, die in dit geval is - hoe heet je ook alweer?
>> STUDENT: Jason.
>> LUIDSPREKER 1: Jason, dus zowel Ben en ik zijn wijzend op Jason op dit moment.
Dus nu heb ik om te bepalen, waar komt Brian behoort?
Dus het enige wat ik heb toegang tot nu is zijn n data-item.
Dus ik ga om te controleren, is Brian minder dan Jason?
Het antwoord is waar.
>> Dus wat nu moet gebeuren, in de juiste volgorde?
Ik moet bijwerken hoeveel pointers in totaal in dit verhaal?
Waar mijn hand is nog steeds wijzend op Jason, en je hand - als je wilt
leg je hand als, soort van, ik weet het niet, een vraagteken.
OK, goed.
>> Oke, dus je hebt een paar kandidaten.
Ofwel Ben of I of Brian of Jason of iedereen, die
pointers moeten veranderen?
Hoeveel in totaal?
>> OK, dus twee.
Mijn wijzer maakt eigenlijk niet meer uit want ik ben gewoon tijdelijk.
Dus het is deze twee jongens, vermoedelijk, zowel Ben en Brian.
Dus laat ik stel voor dat we een update Ben, want hij is de eerste.
Het eerste element van deze lijst gaat nu zijn Brian.
Dus Ben punt bij Brian.
OK, wat nu?
>> Wie krijgt wees naar wie?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: OK dus Brian heeft te wijzen op Jason.
Maar ik heb verloren spoor van die pointer?
Weet ik waar Jason is?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: ik doe, want ik ben de tijdelijke pointer.
En vermoedelijk, heb ik niet veranderd te wijzen op het nieuwe knooppunt.
Dus we kunnen gewoon Brian punt bij wie ik wijzend op.
En we zijn klaar.
Dus geval een, insertie in de het begin van de lijst.
Er waren twee belangrijke stappen.
Een, moeten we Ben updaten, en vervolgens moeten we ook Brian updaten.
En dan heb ik geen zorgen te maken gesjouw door de rest van de
lijst, omdat we al vond zijn locatie, want hij behoorde tot de
links van het eerste element.
>> Oke, dus vrij eenvoudig.
In feite, voelt alsof we zijn er bijna waardoor ook deze ingewikkelde.
Dus laten we nu plukken uit het einde van de lijst, en zie waar
de complexiteit begint.
Dus als nu, ik alloc uit het publiek.
Iedereen wil spelen 55?
Oke, zag ik voor het eerst je hand.
Kom maar naar boven.
Yeah.
Wat is je naam?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Habata.
OK, kom op omhoog.
Je zult het nummer 55 zijn.
Zodat je, natuurlijk, behoren aan het einde van de lijst.
Dus laten we herhalen de simulatie met mij zijnde de PTR voor slechts een moment.
Dus ik ben eerst naar het punt op wat Ben is wijzend op.
We zijn beiden nu op Brian wijzen.
Dus 55 is niet minder dan vijf.
Dus ik ga mezelf updaten door wijzend naar Brian's volgende pointer, die
Nu is natuurlijk Jason.
55 is niet minder dan negen, dus Ik ga PTR updaten.
Ik ga PTR updaten Ik ga PTR updaten.
En ik ga - hmm, wat is je naam ook alweer?
>> STUDENT: Diana.
>> LUIDSPREKER 1: Diana wijst, natuurlijk, op nul met haar linkerhand.
Dus waar komt Habata eigenlijk duidelijk te horen?
Naar links, hier.
Dus hoe weet ik om haar hier te zetten Ik denk dat ik het verpest.
Want wat is PTR kunst dit moment in de tijd?
Null.
Dus ook al, visueel, kunnen we uiteraard al deze te zien
jongens hier op het podium.
Ik heb niet bijgehouden van de vorige persoon in de lijst.
Ik heb geen een vinger wijzen, in dit geval, het nodenummer 34.
>> Dus laten we daadwerkelijk beginnen dit over.
Dus nu heb ik eigenlijk niet nodig een tweede lokale variabele.
En dit is wat je ziet in de werkelijke monster C-code, waar als ik ga,
toen ik updaten mijn rechterhand te wijzen Jason, waardoor Brian achterlatend, I
beter beginnen met mijn linkerhand te werken waar ik was, zodat als ik ga
door deze lijst -
meer onhandig dan ik van plan was nu hier visueel -
Ik ga naar de einde van de lijst.
>> Deze hand is nog steeds nul, die vrij is nutteloos, behalve aangeven
Ik ben duidelijk aan het einde van de lijst, maar nu heb ik tenminste dit
voorganger wijzer hier wijzen, zodat nu wat handen en wat pointers nodig
worden bijgewerkt?
Wiens hand wil je opnieuw te configureren eerste?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: OK, dus Diana's.
Waar wil je naar punt Linker pointer Diana's bij?
Bij 55, vermoedelijk, zodat we daar hebben gestoken.
En waar moet 55 pointer gaan?
Naar beneden, wat neerkomt op null.
En mijn handen, op dit moment, niet doen uit want ze waren gewoon
tijdelijke variabelen.
Dus nu zijn we klaar.
>> Dus de extra complexiteit daar - en het is niet zo moeilijk te implementeren,
maar we moeten een secundaire variabele te maken ervoor dat voordat ik naar mijn rechter
kant heb ik de waarde van mijn linker updaten de hand, pred wijzer in dit geval, dus
dat ik een achterstand pointer bij te houden van waar ik was te houden.
Nu als een terzijde, als je dit denkt door, dit voelt alsof het een
beetje vervelend te moeten houden Volg dit linkerhand.
>> Wat zou een andere oplossing dit probleem geweest?
Als je echt om de gegevens opnieuw te ontwerpen structuur we praten
door middel van dit moment?
Als dit gewoon een soort van voelt een beetje vervelend te moeten, willen, twee wijzers
het doornemen van de lijst, wie anders zou hebben, in een ideale wereld, gehandhaafd
informatie die we nodig hebben?
Yeah?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Precies.
Rechts dus er is eigenlijk een interessante kiem van een idee.
En dit idee van een eerdere pointer, wijzend naar het vorige element.
Wat als ik gewoon belichaamd dat binnenkant van de lijst zelf?
En het gaat om moeilijk te visualiseren zijn dit zonder al het papier
vallen op de vloer.
Maar stel dat deze jongens zowel gebruikt hun handen hebben een eerdere
wijzer, en een volgende pointer, waardoor uitvoering van wat wij een dubbel zullen noemen
gelinkte lijst.
Dat me zou toestaan ​​om een ​​soort van terugspoelen, veel gemakkelijker zonder mij, de
programmeur, hoeven houden bijhouden handmatig -
echt handmatig -
van waar ik eerder was geweest in de lijst.
Dus zullen we niet doen.
We zullen het simpel te houden, want dat is gaat komen op een prijs, twee keer zo
veel ruimte voor de pointers, als je wilt een tweede.
Maar dat is inderdaad een gemeenschappelijke gegevensstructuur bekend als
dubbel gelinkte lijst.
>> Laten we het laatste voorbeeld hier en zet deze jongens uit hun ellende.
Dus malloc 20.
Kom maar uit het gangpad daar.
Oke, wat is uw naam?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Sorry?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Demeron?
OK kom op omhoog.
Je moet 20.
Je natuurlijk gaat behoort tussen de 17 en 22.
Dus laat ik leer mijn les.
Ik ga om wijzer te beginnen wijzend op Brian.
En ik ga mijn linkerhand hebben alleen update naar Brian als ik naar
Jason, controle doet 20 minder dan negen?
Nee.
Is 20 minder dan 17?
Nee.
Is 20 minder dan 22?
Ja.
Dus wat pointers of handen moeten veranderen waar ze nu richten?
>> Dus we kunnen 17 doen wijzend op 20.
Dus dat is prima.
Waar willen we naar punt de aanwijzer nu?
At 22.
En we weten waar 22 is, nogmaals dank naar mijn tijdelijke pointer.
Dus we zijn OK daar.
Omdat deze tijdelijke opslag Ik heb spoor hield van waar iedereen is.
En nu kunt u visueel gaan in waar u behoort, en nu moeten we 1, 2, 3,
4, 5, 6, 7, 8, 9 stress ballen, en een applaus voor
deze jongens, als we dat konden.
Mooi gedaan.
>> [Applaus]
>> LUIDSPREKER 1: Oke.
En je kan de stukken houden papier als aandenken.
>> Oke, dus, geloof me het is een stuk gemakkelijker te lopen door die met
de mens dan het is met de werkelijke code.
Maar wat je zult in slechts een moment te vinden Nu, is dat hetzelfde - oh, dank je.
Dank u -
is dat je zult zien dat dezelfde gegevens structuur, een gelinkte lijst, kan eigenlijk
gebruikt als bouwsteen nog geavanceerde data-structuren.
>> En beseffen ook het thema hier is dat we hebben absoluut meer geïntroduceerd
complexiteit in de uitvoering van dit algoritme.
Inbrengen, en als we gingen er doorheen, verwijderen en zoeken, is een beetje
ingewikkelder dan het was een array.
Maar we krijgen een aantal dynamiek.
We krijgen een adaptief datastructuur.
>> Maar nogmaals, we betalen een prijs van het hebben van een aantal extra problemen, zowel
uitvoering ervan.
En we zijn opgegeven willekeurige toegang.
En om eerlijk te zijn, er is geen enkele mooie schoon dia ik je kan geven dat
zegt hier is de reden waarom een ​​gelinkte lijst is beter dan een array.
En laat het daarbij.
Omdat het thema terugkerende nu, zelfs meer dus in de komende weken, is
dat er niet per se een juist antwoord.
>> Daarom hebben we de afzonderlijke as van ontwerp voor probleem sets.
Het zal erg contextgevoelig of u deze gegevens gebruiken
of dat een structuur, en het zal afhankelijk van wat voor u in termen
van middelen en complexiteit.
>> Maar laat me voorstellen dat de ideale data structuur, de heilige graal, zou zijn
iets dat constante tijd, ongeacht hoeveel spul is
erin, zou het niet geweldig zijn als er een gegevensstructuur geretourneerd antwoorden
constante tijd.
Ja.
Dit woord is in uw enorme woordenboek.
Of nee, dit woord niet.
Of een dergelijk probleem.
Nou laten we eens kijken of we kunnen niet in ieder geval neem een ​​stap in de richting die.
>> Laat ik een nieuwe datastructuur te stellen dat kan worden gebruikt voor verschillende dingen,
in dit geval wel een hash table.
En dus zijn we eigenlijk terug naar blik in een matrix, in dit geval en
enigszins arbitrair, ik heb dit getekend hash table als een array met een soort van
tweedimensionale matrix -
of liever het is hier afgebeeld als een twee dimensionale array - maar dit is slechts
een array van maat 26, zodanig dat als we roepen de array, tafel beugel
nul de rechthoek aan de top.
Tafel beugel 25 is de rechthoek onderaan.
En dit is hoe ik een data zou kunnen trekken structuur waarin ik wil opslaan
mensen namen.
>> Dus bijvoorbeeld, en ik zal niet tekenen de hele zaak hier op de overhead, als ik
had deze array, die ik nu ga bel een hash table, en dit is weer
locatie nul.
Dit hier is locatie een, enzovoort.
Ik beweer dat ik wil deze gegevens gebruiken structuur, ter wille van de discussie,
om namen van mensen slaan, Alice en Bob en Charlie en andere dergelijke namen.
Dus denk aan dit nu als het begin van, zeg, een woordenboek
met veel woorden.
Ze toevallig namen zijn in ons voorbeeld hier.
En dit is maar al te germane, misschien, om uitvoering van een spellingscontrole, zoals we
misschien voor problemen stellen zes.
>> Dus als we hebben een scala aan totale grootte 26 zodat dit het 25e locatie
aan de onderkant, en ik beweer dat Alice is het eerste woord in het woordenboek van
namen die ik wil invoegen in RAM, in deze datastructuur, waar zijn
instincten vertellen dat Alice's naam moet gaan in deze serie?
>> We hebben 26 opties.
Waar we haar willen zetten?
We willen haar in beugel nul, toch?
Een voor Alice, laten we noemen dat nul.
En B zal een, en C zullen twee.
Dus we gaan schrijven Naam hier Alice's.
Als we dan plaatst Bob, zijn naam zal hier gaan.
Charlie zal hier gaan.
Enzovoort omlaag door Deze gegevensstructuur.
>> Dit is een prachtige datastructuur.
Waarom?
Tja, wat is de looptijd van de invoegen van de naam van een mens in deze
datastructuur op dit moment?
Gezien het feit dat deze tabel wordt geïmplementeerd, echt, als een array.
Nou het is een constante tijd.
Het is orde van een.
Waarom?
>> Nou hoe bepaal je waar Alice hoort?
Je kijkt naar de letter van haar naam?
De eerste.
En je kunt er komen, als het een string, door alleen maar naar touwtje
bracket nul.
Dus de nulde karakter van de string.
Dat is makkelijk.
We deden dat in de crypto opdracht weken geleden.
En dan als je eenmaal weet dat Alice's letter is hoofdletter A, kunnen we aftrekken
off 65 of hoofdletter A zelf, dat geeft ons nul.
Dus we weten nu dat Alice behoort op locatie nul.
>> En krijgt een pointer naar deze gegevens structuur, van een soort, hoe lang duurt
het me te vinden locatie nul in een array?
Slechts een stap, rechts Het is een constante tijd vanwege het RAM we
voorstel was een kenmerk van een array.
Dus in het kort, het uitzoeken wat de index naam van Alice's is, dat, in
dit geval is A, of laten we gewoon op te lossen dat tot nul, waarbij B en C is een
twee, uitzoeken dat uit is constante tijd.
Ik heb alleen maar te kijken naar haar eerste brief, uitzoeken waar nul is een
array is ook constante tijd.
Dus technisch is dat als twee stappen nu.
Maar dat is nog steeds constant.
Dus we noemen dat grote O van een, dus we hebben ingebracht Alice in deze tabel in
constante tijd.
>> Maar natuurlijk, ik ben wezen naïeve hier, toch?
Wat als er een Aaron in de klas?
Of Alicia?
Of enige andere namen die beginnen met A. Waar gaan we heen te zetten
die persoon, toch?
Ik bedoel, op dit moment is er slechts drie mensen op de tafel, dus we misschien
moet Aaron zetten op locatie nul een twee drie.
>> Rechts, kon ik hier zetten A.
Maar dan, als we proberen om David te voegen in deze lijst, waar gaat David heen?
Nu ons systeem begint te breken neer, toch?
Want nu David eindigt hier Als Aaron is eigenlijk hier.
En dus nu dit hele idee van een schone datastructuur die ons geeft
constante tijd inserties is niet meer constante tijd, want ik moet
controleren, oh, verdomme, iemand is al op locatie Alice's.
>> Laat ik sonde de rest van deze gegevens structuur, op zoek naar een plek om te zetten
iemand als Aarons naam.
En dus ook dat begint aan lineaire tijd duren.
Bovendien, als je nu wilt het vinden Aaron in deze datastructuur, en u
controleren, en Aarons naam is niet hier.
Idealiter zou je gewoon zeggen Aaron's niet in de gegevensstructuur.
Maar als je beginnen met het maken ruimte voor Aaron waar er moet een D zijn
of een E, u, slechtste geval moeten controleren geheel gegevensstructuur, in
welk geval het delegeert in iets lineair in de grootte van de tabel.
>> Dus oke, ik zal dit oplossen.
Het probleem is hier dat ik had 26 elementen in de array.
Laat ik het te veranderen.
Whoops.
Laat ik het zo wijzigen dat in plaats van het zijn maat 26 in totaal, let op de bodem
index gaat veranderen naar n minus 1.
Als 26 is duidelijk te klein voor de mens ' namen, omdat er duizenden
namen van de wereld, laten we gewoon te maken in 100 of 1000 of 10.000.
Laten we wijzen veel meer ruimte.
>> Nou dat niet noodzakelijkerwijs afnemen de kans dat we twee hebben
mensen met namen die beginnen met A, en dus, je gaat proberen om A te zetten
namen op locatie nul nog steeds.
Ze zijn nog steeds te botsen, die betekent dat we nog steeds een oplossing te brengen moet
Alice en Aäron en Alicia en andere namen die beginnen met A elders.
Maar hoeveel van een probleem is dit?
Wat is de kans dat u hebben botsingen in een data
structuur als deze?
>> Nou, laat ik - we komen terug om hier die vraag.
En kijken hoe we zouden kunnen eerst oplossen.
Laat ik trek dit voorstel hier.
Wat we zojuist beschreven is een algoritme, een heuristische genoemd lineaire
indringende waarbij, als je probeerde in te voegen iets wat hier in deze data
structuur, die een hash tabel wordt genoemd, en er is geen ruimte daar, je
echt sonde de datastructuur controleren, is deze beschikbaar?
Is deze beschikbaar is deze beschikbaar?
Is deze beschikbaar?
En toen het eindelijk is, je plaatst de noemen die je oorspronkelijk bedoeld
elders op die locatie.
Maar in het ergste geval, de enige plek zou de onderkant van de gegevens worden
structuur, het einde van de array.
>> Dus lineaire sonderen, in het ergste geval, delegeert in een lineaire algoritme waar
Aaron, als hij toevallig laatst moet worden ingevoegd in deze datastructuur, hij zou kunnen
botsen met deze eerste plaats, maar dan uiteindelijk door pech helemaal aan het eind.
Dus dit is geen constante tijd heilige graal voor ons.
Deze benadering van het plaatsen van elementen in een gegevensstructuur, een hash
tafel lijkt niet constant tijd althans niet in het algemene geval.
Het kan delegeren in iets lineair.
>> Dus wat als we botsingen op te lossen enigszins anders?
Dus hier is een meer verfijnde benaderen om wat er nog
riep een hash table.
En door hash, als een terzijde, wat Ik bedoel is de index die
Ik verwees naar eerder.
Om hash iets kan zijn gezien als een werkwoord.
>> Dus als je hash Alice is een naam, een hash-functie, om zo te zeggen,
moet een aantal keren.
In dit geval is nul als zij behoort bij locatie nul, een of zij behoort bij
locatie een, enzovoort.
Dus mijn hash-functie tot nu toe is super simpel, alleen kijken naar de
eerste letter van iemands naam.
Maar een hash-functie neemt als ingang een stukje van de gegevens, een
touwtje, een int, wat dan ook.
En hij spuugt meestal een nummer.
En dat aantal is waar die gegevens element behoort tot een gegevensstructuur
hier bekend als een hash table.
>> Dus gewoon intuïtief, dit is een iets andere context.
Dit is eigenlijk verwijst naar een voorbeeld waarbij verjaardagen, waar
er misschien wel 31 dagen van de maand.
Maar wat heeft deze persoon beslist om doen in geval van een aanrijding?
Context nu zijn, niet een botsing van namen, maar een botsing van verjaardagen,
Als twee mensen hebben dezelfde verjaardag op 2 oktober, bijvoorbeeld.
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Ja, dus hier hebben we de hefboomwerking van gelinkte lijsten.
Dus het ziet er een beetje anders dan trokken we het eerder.
Maar we lijken moeten een array aan de linkerkant.
Dat is een index, voor geen specifieke reden.
Maar het is nog steeds een array.
Het is een array van pointers.
En elk van die elementen, elk van deze kringen of slashes - de schuine streep
vertegenwoordigen null - elk van deze pointers is blijkbaar wijzen
wat datastructuur?
Een gekoppelde lijst.
>> Dus nu hebben we de mogelijkheid om harde code in ons programma
de grootte van de tabel.
In dit geval, we weten dat er nooit meer dan 31 dagen in een maand.
Zo hard coderen van een waarde als 31 wordt redelijk in die context.
In de context van namen, harde codering 26 is het niet onredelijk dat de mensen
alleen namen beginnen met bijvoorbeeld het alfabet met A tot en met Z.
>> We kunnen ze allemaal proppen in die gegevens structuur zo lang, als we een
botsing, wij niet de namen hier zetten, We denken in plaats van deze cellen
niet als strings zichzelf, maar verwijzingen naar bijvoorbeeld Alice.
En dan Alice kan een andere pointer hebben een andere naam ab
A. En Bob gaat hier eigenlijk voorbij.
>> En als er een andere naam beginnend met B, komt hij hierheen.
En zodat elk van de elementen van deze tafel twee, als we ontwierp deze een
beetje meer slim -
kom op -
als we ontwierp dit een beetje meer slim, wordt nu een adaptieve data
structuur, waar er geen harde limiet op hoeveel elementen u kunt invoegen
erin want als je hebt een botsing, dat is prima.
Gewoon doorgaan en voeg deze toe aan wat we zagen een beetje geleden was
bekend als een gelinkte lijst.
>> Nou laten we pauze voor slechts een moment.
Wat is de waarschijnlijkheid van een botsing in de eerste plaats?
Goed, misschien ben ik dan denk, misschien Ik ben meer dan engineering van dit probleem,
want weet je wat?
Ja, ik kan komen met willekeurige voorbeelden uit de top van mijn hoofd als
Allison en Aaron, maar in werkelijkheid, aangezien een gelijkmatige verdeling van
ingangen, dat is wat random inserties in een gegevensstructuur, wat is eigenlijk
de waarschijnlijkheid van een botsing?
Wel blijkt, het is eigenlijk super hoog.
Laat me generaliseren dit probleem als deze.
>> Dus in een ruimte van n CS50 studenten, wat is de kans dat ten minste
twee studenten in de kamer hebben dezelfde verjaardag?
Dus er is wat. een paar hund -
200, 300 mensen hier en een aantal honderd mensen thuis vandaag.
Dus als je wilde om ons af te vragen wat er de waarschijnlijkheid van twee mensen
in deze kamer met dezelfde verjaardag, kunnen we dit uitzoeken.
En ik beweer eigenlijk zijn er twee mensen met dezelfde verjaardag.
>> Bijvoorbeeld, heeft iemand hebben vandaag jarig?
Gisteren?
Morgen?
Oke, dus het voelt alsof ik ga moeten deze 363 of zo meer te doen
keer om daadwerkelijk uit te Als we hebben wel een botsing.
Of we kunnen doen dit wiskundig eerder dan tediously
dit te doen.
En stelt de volgende.
>> Dus ik stel voor dat we konden modelleren van de waarschijnlijkheid van twee mensen die de
dezelfde dag jarig als de kans van 1 verminderd de kans dat niemand
op dezelfde dag jarig.
Dus om dit te krijgen, en dit is slechts het mooie manier van schrijven van dit, voor de
eerste persoon in de kamer, hij of zij kan een van de mogelijke hebben
verjaardagen veronderstelling 365 dagen in het jaar, met excuses aan personen met
de 29 februari verjaardag.
>> Dus de eerste persoon in deze kamer is vrij aan een aantal verjaardagen hebben
uit de 365 mogelijkheden zodat we doen dat 365 gedeeld door 365,
die een.
De volgende persoon in de kamer, als het doel is een botsing, kan alleen
zijn of haar verjaardag op hoe verschillende dagen mogelijk?
364.
Dus de tweede term in deze uitdrukking is wezen doet dat wiskunde voor ons
door het aftrekken off een mogelijke dag.
En dan de volgende dag, de volgende dag, de volgende dag naar het totale aantal
van de mensen in de zaal.
>> En als we dan overwegen, wat is dan de kans dat niet van iedereen hebben
unieke verjaardagen, maar nogmaals 1 minus dat, wat we krijgen is een uitdrukking
dat kan zeer grillig zo uitzien.
Maar het is nog interessanter om te kijken naar visueel.
Dit is een grafiek waarbij op de x-as het aantal mensen in de kamer, de
aantal verjaardagen.
Op de Y-as is de kans van een botsing, twee mensen
die op dezelfde dag jarig.
>> En de afhaalmaaltijd van deze curve is dat zodra je naar wilt 40
studenten, je van plan bent op een kans 90% combinatorically twee
mensen of meer hebben op dezelfde dag jarig.
En als je eenmaal aan 58 mensen het willen bijna 100% van een kans beide
mensen in de kamer gaat het hebben dezelfde dag jarig, ook al is er
365 of 366 mogelijk emmers en slechts 58 mensen in de kamer.
Net statistisch je bent waarschijnlijk krijgen botsingen, die in het kort
motiveert deze discussie.
Dat zelfs als we hier chique en beginnen met deze ketens, we zijn nog steeds
zullen botsingen hebben.
>> Zodat het de vraag, wat is de kosten van het doen van toevoegingen en schrappingen
in een datastructuur als deze?
Nou laat me voor te stellen -
en laat me terug te gaan naar het scherm over hier - als we n elementen in de
lijst, dus als we proberen in te voegen n elementen, en we hebben
hoeveel totaal emmers?
Laten we zeggen 31 in totaal emmers in het geval van verjaardagen.
Wat is de maximale lengte van een van deze ketens potentieel?
>> Als er weer is 31 mogelijk verjaardagen in een bepaalde maand.
En we zijn gewoon klonteren iedereen -
dat is eigenlijk een stom voorbeeld.
Laten we in plaats daarvan 26.
Dus als daadwerkelijk mensen wier namen beginnen met A tot Z, waardoor aan
ons 26 mogelijkheden.
En we zijn met behulp van een datastructuur als degene die we net zagen, waarbij we
een array van pointers, die elk wijst op een gelinkte lijst waar de
eerste lijst is iedereen de naam Alice.
De tweede lijst is elke met de naam beginnend met A, beginnend
met B, enzovoort.
>> Wat de waarschijnlijke duur van elk van deze lijsten als we aannemen een mooie schone
verdeling van de namen van A tot Z over de gehele datastructuur?
Er is n mensen in de datastructuur gedeeld door 26, als ze mooi
verspreid over het gehele gegevensstructuur.
Zodat de lengte van elk van deze ketens is n gedeeld door 26.
Maar in grote O notatie, wat is dat?
Wat is dat eigenlijk?
Dus het is eigenlijk gewoon n, toch?
Want we hebben in het verleden gezegd, dat ugh je delen door 26.
Ja, in werkelijkheid sneller.
Maar in theorie, het is niet fundamenteel alles sneller.
>> Zodat we niet lijken te zijn dat alles veel dichter bij deze heilige graal.
In feite is dit slechts lineaire tijd.
Heck, op dit punt, waarom doen we niet gewoon gebruik maken van een enorme gelinkte lijst?
Waarom gaan we niet gewoon gebruik maken van een enorme array om de namen van opgeslagen
iedereen in de kamer?
Nou, is er nog steeds iets meeslepend over een hash table?
Is er nog iets dwingende over een gegevensstructuur
dat ziet er zo uit?
Dit.
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Recht, en opnieuw is het maar een lineaire tijd algoritme en een
lineaire tijd datastructuur, waarom doe ik niet gewoon opslaan ieders naam in een grote
array of in een grote gelinkte lijst?
En stoppen met het maken van CS zo veel moeilijker dan het moet zijn?
Wat is meeslepend over dit, zelfs hoewel ik krabde het uit?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Inlagen zijn niet?
Duur meer.
Dus inserties potentieel kon nog zijn constante tijd, zelfs als uw gegevens
structuur ziet er zo uit, een array van pointers, die elk goed op
potentieel een gelinkte lijst.
Hoe kon je constant bereiken tijd inbrengen van namen?
Plak deze op de voorkant, toch?
>> Als we offeren een ontwerp doelpunt van eerder, waar we wilden houden
ieders naam, bijvoorbeeld, gesorteerd, of alle nummers op het podium gesorteerd,
Stel dat we een ongesorteerde gelinkte lijst.
Het kost ons slechts een of twee stappen, zoals in het geval van Ben en Brian
eerder een element voegen op het begin van de lijst.
Dus als we niet de zorg over het sorteren van alle van de namen die beginnen met A of alle
de namen die beginnen met B, kunnen we nog steeds bereiken constante tijd invoegen.
Nu het opzoeken van Alice of Bob of naam Meer in het algemeen is nog wat?
Het is groot O van n gedeeld door 26, in de ideale geval waar iedereen is gelijkmatig
verdeeld, waar er zo veel A's aangezien er Z, die waarschijnlijk
onrealistisch.
Maar dat is nog steeds lineair.
>> Maar hier komen we terug naar het punt van asymptotische notatie
theoretisch waar.
Maar in de echte wereld, als ik beweer dat mijn programma kan iets 26 keer doen
sneller dan de jouwe, waarvan het programma ga je liever met behulp van?
Jou of van mij, die is 26 keer sneller?
Realistisch, de persoon van wie is 26 keer sneller, zelfs als theoretisch
onze algoritmes draaien in dezelfde asymptotische looptijd.
>> Laat ik een ander voorstel oplossing voor het geheel.
En als dit niet blow your mind, we uit datastructuren.
Dit is het dus een Trie -
soort van een domme naam.
Het komt van opvragingen, en het woord gespeld trie, t-r-i-e, door
Natuurlijk retrieval klinkt als trie.
Maar dat is de geschiedenis van het woord Trie.
>> Dus een Trie is inderdaad een soort van boom, en het is ook een spel op dat woord.
En ook al kun je niet helemaal zien deze visualisatie, een trie een
boom structuur, zoals een stamboom met een voorouder aan de bovenkant en kavels
van de kleinkinderen en de achterkleinkinderen als bladeren op de bodem.
Maar elk knooppunt in een trie een array.
En het is in een array - en laten we vereenvoudig voor een moment - het is een
array, in dit geval, van maat 26, waar elk knooppunt opnieuw is een array van grootte
26, waarbij de nulde element dat matrix vertegenwoordigt A, en de laatste
element in elk van deze matrix vertegenwoordigt Z.
>> Dus stel ik voor, dan, dat deze gegevens structuur, bekend als trie, kan
ook gebruikt om woorden te slaan.
We zagen een moment geleden hoe we kunnen opslaan woorden, of in dit geval namen en we
zagen eerder hoe we getallen kunnen opslaan, maar als we ons richten op namen of strings
Hier, op wat is interessant.
Ik eis dat de naam Maxwell is binnenkant van deze gegevensstructuur.
Waar zie je Maxwell?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Aan de linkerkant.
Dus wat is interessant met deze gegevens structuur is eerder dan de winkel
snaar M-A-X-W-E-L-L backslash nul all aaneengesloten, wat je doen in plaats
volgt.
Als dit een Trie als datastructuur, waarvan elk knooppunten weer een matrix,
en u wilt opslaan Maxwell, moet u eerst index en dus de wortel van de knoop, zodat
te spreken, de bovenste knoop, op locatie M, rechts, dus
ruwweg in het midden.
En dan vanaf daar volgt u een pointer naar een onderliggende knooppunten, om zo te zeggen.
Dus in de stamboom zin, je volgen naar beneden.
En die u leiden naar een ander knooppunt aan de linkerkant, die
gewoon een andere array.
>> En dan als je wilt opslaan Maxwell, u de aanwijzer die aangeeft vinden
A, dat deze hier.
Dan ga je naar het volgende knooppunt.
En merk - dit is de reden waarom de foto's een beetje misleidend -
dit knooppunt kijken super klein.
Maar rechts van dit Y en Z. Het is gewoon de auteur heeft afgekapt de
foto, zodat u eigenlijk dingen zien.
Anders deze foto enorm groot zou zijn.
Dus nu index in locatie X, dan W, dan E, dan L, dan L. Wat is er dan
deze nieuwsgierigheid?
>> Nou, als we met behulp van dit soort nieuwe nemen over hoe je een string op te slaan in een
datastructuur, moet je nog steeds wezen afvinken in de data
structuur die een woord eindigt hier.
Met andere woorden, elk van deze knooppunten een of andere manier heeft om te onthouden dat wij
eigenlijk volgde al deze pointers en worden een beetje verlaten
broodkruim op de bodem hier van deze structuur M-A-X-W-E-L-L is aangegeven
inderdaad in deze datastructuur.
>> Dus we kunnen dit als volgt doen.
Elk van de knooppunten in het beeld dat we gewoon zaag heeft een, een array van maat 27.
En het is nu 27, want in p set zes, we eigenlijk geven u een apostrof,
dus kunnen we namen als O'Reilly hebben en anderen met een apostrof.
Maar hetzelfde idee.
Elk van deze elementen in de matrix wijst naar een struct
knooppunt, dus gewoon een knooppunt.
Dit is zo erg aan denken van onze gelinkte lijst.
>> En dan heb ik een Boole, die ik zal bel woord, dat is gewoon gaat worden
waar als een woord geëindigd is knoop in de boom.
Het vertegenwoordigt in feite de kleine driehoek zagen we een moment geleden.
Als een woord eindigt op dat knooppunt in de boom, zal dat woord veld waar te zijn,
die conceptueel is controle uit, of we trekken deze driehoek, ja er
is een woord hier.
>> Dus dit is een Trie.
En nu is de vraag, wat wordt de lopende tijd?
Is het grote O van n?
Is het iets anders?
Nou, als je namen hebt n in deze data structuur, Maxwell is slechts een van de
hen, wat is de looptijd van de het plaatsen of het vinden van Maxwell?
Wat is de looptijd invoegen van Maxwell?
Als er n andere namen reeds in de tabel?
Yeah?
>> STUDENT: [onverstaanbaar].
>> LUIDSPREKER 1: Ja, het is de lengte van de naam, toch?
Dus M-a-x-w-e-l-l, zodat het voelt alsof deze algoritme is big O van zeven.
Nu, natuurlijk, de naam variëren in lengte.
Misschien is het een korte naam.
Misschien is het een langere naam.
Maar wat is sleutel hier is dat Het is een constant getal.
En misschien is het niet echt constant, maar god, zo realistisch, in een
woordenboek, is er waarschijnlijk een bepaalde grens het aantal letters in een
naam van de persoon in een bepaald land.
>> En dus kunnen we ervan uitgaan dat waarde is een constante.
Ik weet niet wat het is.
Het is waarschijnlijk groter dan we denken dat het is.
Want er is altijd wel een hoekje geval met een gekke lange naam.
Dus laten we het noemen k, maar het is nog steeds een constante vermoedelijk, omdat elke
naam in de wereld, ten minste een bepaald land, is dat de lengte of
korter, dus het is constant.
Maar toen we zeiden iets is groot O van een constante waarde, wat is dat
echt gelijk aan?
Dat is echt hetzelfde zoals zeggend constante tijd.
>> Nu zijn we soort van vals spelen, toch?
We zijn soort hefboomwerking een theorie hier om te zeggen dat goed, volgorde van de k
eigenlijk gewoon bestellen van een, en het is een constante tijd.
Maar het is echt.
Omdat het belangrijk inzicht is dat Als we namen n al deze
datastructuur, en we insert Maxwell, is de hoeveelheid tijd die ons
Steek Maxwell bij alle getroffen door hoeveel andere mensen
zijn in de datastructuur?
Lijkt niet te zijn.
Als ik een miljard meer elementen van deze trie, en steek vervolgens Maxwell, wordt
hij helemaal aangetast?
Nee.
En dat is in tegenstelling tot alle van de dag gegevens structuren die we tot nu toe heb gezien, waar
de looptijd van je algoritme is volledig onafhankelijk van hoeveel
spul is of nog niet is dat gegevensstructuur.
>> En dus met dit biedt u nu een gelegenheid voor p set van zes, die zal
weer betrekken de uitvoering van uw eigen spellingcontrole, het lezen van de 150.000
woorden, de beste manier om te slaan dat niet noodzakelijkerwijs duidelijk.
En al heb ik streefde te vinden de heilige graal, doe ik niet
beweren dat een Trie is.
In feite, een hash table kan heel goed blijken veel efficiënter.
Maar dat zijn slechts -
dat is slechts een van de ontwerpbeslissingen je zal moeten maken.
>> Maar in het sluiten laten we eens 50 of zo seconden om een ​​blik op wat ons te nemen
vooruit volgende week en verder we de overgang uit deze command line
wereld als C-programma's om dingen web gebaseerd en talen zoals PHP en
JavaScript en het internet zelf, protocollen zoals HTTP, wat je hebt
vanzelfsprekend voor de jaren nu, en typte elkste
dag, misschien, of gezien.
En we beginnen te schillen terug de lagen van wat het internet.
En wat is de code die ligt ten grondslag aan de huidige instrumenten.
Dus 50 seconden van deze teaser hier.
Ik geef u Strijders van het Net.
>> [VIDEO AFSPELEN]
>> -Hij kwam met een boodschap.
Met een protocol dat al zijn eigen.
Hij kwam tot een wereld van wrede firewalls, onverschillig routers, en gevaren ver
erger dan de dood.
Hij is snel.
Hij is sterk.
Hij is TCPIP.
En hij heeft uw adres.
Krijgers van het Net.
>> [END VIDEO AFSPELEN]
>> LUIDSPREKER 1: Dat is hoe het internet Zij werken vanaf volgende week.