>> SPEAKER 1: Dobře, takže jsme zpátky.
Vítejte na CS50.
To je konec týdne sedm.
Takže připomenout, že minule jsme začali při pohledu na něco propracovanější
datové struktury.
Vzhledem k tomu, až do teď, jsme měli opravdu máme k dispozici to bylo, pole.
>> Ale dříve, než jsme se zbavit pole tak, že vše zajímavé, což opravdu to
ve skutečnosti je, jaké jsou některé z klady tohoto jednoduchého dat
struktura tak daleko?
Co je to dobrý?
Zatím, jak jsme viděli?
Co to máš?
Nic.
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Co je to?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Pevná velikost.
OK, tak proč je pevnou velikost dobrý i když?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: OK, takže je to efektivní pocit, že můžete přidělovat
pevná částka z vesmíru, což snad je přesně tolik, kolik
prostor tak, jak chcete.
Takže to může být naprosto plus.
>> Co jiného se strana pole?
Jo?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: All - Cože?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Všechny boxy v paměti nebo vedle sebe.
A to je užitečné - proč?
To je docela pravda.
Ale jak můžeme využít, že pravdu?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Přesně tak, můžeme sledovat kde je vše jen na základě znalosti
jednu adresu, a to na adresu první byte tohoto bloku paměti.
Nebo v případě, že řetězec, adresa první
char v tomto řetězci.
A odtud můžeme nalézt konec řetězce.
Najdeme zde Druhý prvek, Třetí část, a tak dále.
>> A tak fantastický způsob, jak to popsat je, že pole nám
náhodný přístup.
Jen pomocí hranatou závorkou zápis a číslo, můžete přeskočit na
specifický prvek v poli v konstantním čase, velké O
jednoho, abych tak řekl.
>> Ale tam bylo nějaké stinné stránky.
Co pole neudělal velmi snadno?
Co je to vůbec dobré?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Co je to?
>> STUDENT: [neslyšitelné].
>> Reproduktor 1: Rozšíření ve velikosti.
Takže stinné pole jsou přesně opak toho, co
upsides jsou.
Takže jedna z nevýhod je že je to pevnou velikost.
Takže si můžete opravdu ji pěstovat.
Můžete přidělit větší kus paměť, a pak se přesunout staré prvky
do nového pole.
A pak bez stará pole, pro instance, pomocí malloc nebo podobný
funkce je volána realloc, které realokuje paměť.
>> Realloc, jako stranou, se snaží, aby vám paměť, která je vedle pole
že již máte.
Ale to by se věci pohnuly asi úplně.
Ale ve zkratce, je to drahé, ne?
Protože pokud máte kus paměti této velikosti, ale opravdu chci
této velikosti, a chcete zachovat zachovány původní prvky, budete muset
zhruba lineární čas Proces kopírování že je třeba, aby se stalo od
staré na nové pole.
A realita se ptá provozní systém znovu a znovu a
opět velké kusy paměti může začít stát nějaký čas stejně.
Takže je to požehnáním i prokletím v zastírat, že tato pole
jsou pevné délky.
Ale když si představíme něco místo takhle, kterou nazývá propojený
seznam, dostaneme několik upsides a několik stinné i zde.
>> Takže spojový seznam je prostě dat struktura tvořena structs C v tomto
případ, kdy struct, odvolání, je jen kontejner pro jeden nebo více specifických
typy proměnných.
V tomto případě, co si datové typy Zdá se, že uvnitř struct, který
naposledy jsme nazývaný uzel?
Každý z těchto obdélníků je uzel.
A každý z menších obdélníků uvnitř ní je datový typ.
Jaké typy si říkáme byli v pondělí?
Jo?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: variabilní a ukazatel nebo Přesněji řečeno, int, pro N,
a ukazatel v dolní části.
Oba ti stalo, že 32 bitů na alespoň na počítači, jako je tento CS50
Zařízení, a tak jsou tažené stejně ve velikosti.
>> Takže to, co používáte ukazatel když za zjevně?
Proč přidat na tuto šipku teď, když pole bylo tak pěkné a čisté a jednoduché?
Co dělá ukazatel pro nás v každé z těchto uzlů?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Přesně tak.
Je to řekne, kde další je.
Tak nějak jsem použít analogii pomocí vlákno nějak
nit těchto uzlů dohromady.
A to je přesně to, co děláme s ukazatele, protože každý z nich
kousky paměti může, ale nemusí být souvislé, zády k sobě k sobě
v paměti RAM, protože pokaždé, když se volání malloc řekl, dej mi dost
bajtů pro nový uzel, mohlo by to tu, nebo by to mohlo být.
Mohlo by to být tady.
Prostě nevím.
>> Ale s použitím ukazatele na adresy ty uzly, můžete steh je
společně tak, že vypadá vizuálně jako seznam, i když tyto věci jsou
vše rozprostřené v celém jednom nebo vaše dvě nebo čtyři gigabajty vaše RAM
uvnitř vašeho vlastního počítače.
>> Tak nevýhodou, pak, spojový seznam je co?
Co je to cena, kterou jsme zřejmě platit?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Více prostoru, ne?
My jsme v tomto případě, zdvojnásobil množství prostoru, protože jsme šli
z 32 bitů pro každý uzel, pro každou int, takže teď 64 bitů, protože musíme
držet kolem ukazatel stejně.
Získáte větší účinnost, pokud váš struct je větší než tato jednoduchá věc.
Pokud jste skutečně studenta uvnitř z nichž je několik stringů
jméno a dům, možná číslo, možná některých dalších oborů dohromady.
>> Takže pokud máte dostatečně velký struct, pak možná cena ukazatel je
není tak velký problém.
Toto je trochu rohové případu v tom, že jsme ukládání takový jednoduchý primitivní
uvnitř propojeného seznamu.
Ale jde o to samé.
Ty určitě trávit více paměť, ale vy jste stále
flexibilita.
Protože teď, když chci přidat prvek na začátku tohoto seznamu,
Musím přidělit nový uzel.
A já mám jen ty aktualizace šipky jaksi jen pohybující
několik rad kolem.
>> Pokud chci vložit něco do uprostřed seznamu, nemám na
tlačit všechny stranou, jako tomu bylo v minulost týdnů s našimi dobrovolníky, kteří
představovala pole.
Dovedu si vyhradit nový uzel a pak stačí poukázat na šipky v
různé směry, protože to není musí zůstat v aktuální
paměť pravda, linka, jako bych vypracovány je to tady na obrazovce.
>> A pak konečně, pokud chcete vložit něco na konec seznamu, je
ještě jednodušší.
To je trochu libovolného notaci, ale 34 je ukazatel, hádejte.
Jaká je hodnota jeho ukazatel nejvíce pravděpodobně vyvodit něco jako starý
Škola anténa tam?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Je to asi null.
A opravdu to je jedna autora zastoupení null.
A to je null, protože jste naprosto Potřebujete vědět, kde je konec spojového
seznam, jinak budete mít následující a sledování a po těchto šipek
do určité hodnoty odpadky.
Takže null bude znamenat, že neexistuje více uzlů napravo od čísla 34,
v tomto případě.
>> Takže navrhujeme, že můžeme realizovat tento uzel v kódu.
A my jsme viděli tento druh syntaxe před.
Typedef jen definuje nový typ nám, nám dává jako synonymum
string byl pro char *.
V tomto případě to bude, aby nám zkrácený zápis tak, že struct uzel
Místo toho můžete být jen zapsat jako uzel, který je mnohem čistší.
Je to mnohem méně upovídaný.
>> Uvnitř uzlu je zřejmě int tzv. n, a pak struct node *
což znamená, že přesně to, co jsme chtěli šipky znamená, ukazatel na další
uzel přesně stejného typu.
A já navrhuji, abychom mohli realizovat vyhledávací funkce jako je tento, který v
první pohled by se mohlo zdát trochu složitější.
Ale podívejme se, že v kontextu.
>> Nech mě jít přes spotřebiče tady.
Dovolte mi otevřít soubor s názvem Seznam nulový bod h.
A že obsahuje pouze definici my právě viděl před chvílí na tato data
typ nazývaný uzel.
Takže jsme dali, že do souboru dot hodin.
>> A jak je stranou, i když to program, který se chystáte vidět, je
není tak složité, je to ve skutečnosti Konvence při psaní programu
dát věci jako datové typy, táhnout konstanty někdy uvnitř vašeho
hlavičkový soubor a ne nutně v Váš soubor C, jistě, když si
Programy se větší a větší, takže víte, kde hledat a to jak pro
dokumentace v některých případech, nebo pro základy, jako je toto,
Definice některých typů.
>> Kdybych se tak otevírá seznam nulovou tečku c, všimněte si pár věcí.
Obsahuje několik hlavičkové soubory, většina které jsme ještě neviděli.
Obsahuje vlastní hlavičkový soubor.
>> A stranou, proč je to dvakrát cituje zde, na rozdíl od úhlu
držáky na trati, která Jsem zdůraznil, že?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Jo, tak to je místní soubor.
Takže jestli je to místní soubor z vašich vlastních zde na lince 15, například, můžete použít
uvozovky místo z šikmých závorkách.
>> Teď je to docela zajímavé.
Všimněte si, že jsem prohlásil, globální proměnnou v tomto programu na řádku 18
tzv. první, myšlenka je to bude ukazatel na první
uzel v mém propojeného seznamu, a já jsem inicializována, na hodnotu null, protože jsem
není přiděleno žádné skutečné uzly jen zatím.
>> Takže to znamená, obrazově, co jsme viděl před chvílí na obrázku jako
že ukazatel na daleko levé straně.
Takže teď, že ukazatel nemá šipku.
Je to místo je jen null.
Ale představuje to, co bude adresa první skutečný
uzel v tomto seznamu.
Tak jsem se provádění je globální protože, jak uvidíte, to vše
Program se v životě realizovat spojový seznam pro mě.
>> Teď mám několik prototypů zde.
Rozhodl jsem se implementovat funkce, jako je mazání, vkládání, vyhledávání a
průchod -
poslední být jen pěšky přes seznam, vytištění jeho prvky.
A teď je můj hlavní rutina.
A nebudeme trávit příliš mnoho času na to, protože to je něco, doufejme
starý klobouk nyní.
>> Chystám se udělat následující, zatímco uživatel spolupracuje.
Takže jedno, já jdu k tisku z tohoto menu.
A já jsem ho formátovat jako čistě, jak jsem mohl.
Pokud uživatel zadá v jednom, to znamená, že které chcete odstranit něco.
Pokud uživatel zadá ve dvou, to znamená, že které chcete vložit něco.
A tak dále.
Chystám se poté vás vyzve pak na příkaz.
A pak budu používat GetInt.
>> Tak to je opravdu jednoduché menuing interface, kde stačí zadat
číslo mapování na jeden z těchto příkazů.
A teď mám pěkný čistý vypínač prohlášení, že se to zapnout
co uživatel napsal palců
A když napsal jeden, já zavolejte odstranit a rozbít.
Pokud zadali dva, já zavolejte vložit a zlomit.
>> A teď Povšimněte si, že jsem dal každý z nich na stejném řádku.
Je to jen stylistické rozhodnutí.
Obvykle jsme viděli něco takhle.
Ale já jsem se rozhodl, upřímně řečeno, můj program Podíval čitelnější, protože
to bylo jen čtyři případy, na vypsalo to takhle.
Zcela legitimní použití stylu.
A já budu dělat to tak dlouho, dokud uživatel nezadali nulu, což jsem
rozhodl, bude znamenat, že chtějí s kouřením přestat.
>> Takže teď upozornění, co jsem dělat tady.
Chystám se uvolnit seznamu zdánlivě.
Ale o tom až za chvíli.
Pojďme si nejprve tento program spustit.
Takže mi dovolte větší terminál okna, tečka lomítko list 0.
Chystám se jít dopředu a vložit, psaní dva, jako je číslo 50, a nyní
uvidíte seznam je nyní 50.
A můj textu jen posouvat se trochu.
Takže teď všimnete seznam obsahuje číslo 50.
>> Pojďme udělat další vložku tím, že dva.
Pojďme zadejte číslo jako jeden.
List je nyní jeden, následuje 50.
Takže je to jen textová reprezentace seznamu.
A pojďme vložit ještě jedno číslo jako číslo 42, což je snad
chystá skončit ve středu, protože Tento program v jednotlivých druhů se
prvky, jak to vloží nimi.
Takže tady to máme.
Super jednoduchý program, který by absolutně použili celou řadu, ale já
stalo, že se pomocí propojeného seznamu jen tak mohu dynamicky
zvětšit a zmenšit ji.
>> Takže pojďme se podívat pro vyhledávání, když jsem spustit příkaz tři, Chci vyhledávat
pro, řekněme, číslem 43..
A nic se zřejmě našel, protože jsem se vrátil žádnou odpověď.
Tak jdeme na to znovu.
Hledat.
Pojďme hledání 50, nebo spíše hledání na 42, což je pěkný
Trochu jemnější význam.
A já jsem našel smysl života tam.
Číslo 42, pokud nevíte, reference, Google jej.
Dobrá.
Takže to, co tento program pro mě udělal?
Je to jen mi dovolil vložit tak daleko a hledání prvků.
>> Pojďme rychle vpřed, pak se že funkce se podíval na
v pondělí jako ukázku.
Takže tuto funkci, tvrdím, hledá element v seznamu jako první
jeden, upozornění uživatele a volání GetInt získat aktuální int
které chcete vyhledat.
>> Pak nevšiml.
Chystám se vytvořit dočasnou proměnnou v souladu s názvem 188 ukazatel -
PTR -
mohla zavolat tomu nic.
A je to ukazatel na uzel protože jsem řekl, že uzel *.
A já inicializace je rovná nejprve tak, že jsem skutečně mít svou
prstem, abych tak řekl, na velmi První prvek seznamu.
Takže pokud moje pravá ruka je zde PTR jsem ukazuje na stejnou věc, že ​​první
ukazuje na.
>> Takže teď zpátky v kódu, co se bude dít dál -
je to společný vzor, ​​když iterace přes struktury, jako
spojový seznam.
Chystám se udělat následující, zatímco ukazatel není rovno null Takže zatímco
můj prst neukazuje na nějaké null hodnota, pokud je ukazatel šipka n se rovná n.
Jsme si všimnete jako první, že n je to, co Uživatel napsal v přepočtu GetInts zavolat tady.
>> A ukazatel šipka n rozumí co?
No, pokud se vrátíme k obrázku zde když mám prst ukazující na
že první uzel obsahuje devět, Šipka v podstatě znamená, že jít do
uzel a chytit hodnotu při umístění n, V tomto případě jsou data pole s názvem n.
>> Jako stranou - a viděli jsme to ještě před pár týdny, když se někdo zeptal -
tato syntaxe je nový, ale to není nám síly, které jsme
už nemělo.
Co to bylo za výraz ekvivalentní k použití tečka zápis a hvězda pár
týdny, když jsme sloupnout tato vrstva trochu předčasně?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Přesně tak, je to hvězda, a pak je to hvězda tečka n, s
závorky zde, který vypadá, Upřímně řečeno, myslím, že spousta
více tajemné číst.
Ale hvězda ukazatel, jako vždy, znamená jít.
A jakmile jste tam, jaké údaje Pole chceš přístup?
No použít tečka notaci pro přístup struct datové pole, a já
konkrétně chcete n.
>> Upřímně řečeno, řekl bych to je prostě těžší číst.
Je to těžší si vzpomenout, kde se závorky jdou,
hvězda a to všechno.
Aby celý svět přijal některé syntaktické cukr, abych tak řekl.
Jen sexy způsob, jak říct, To je ekvivalentní, a
možná více intuitivní.
Je-li ukazatel je skutečně ukazatel, znamená notace šipky jít a najít
pole je v tomto případě tzv. n.
>> Takže pokud ji najdu, všimněte si, co dělám.
Prostě vytisknout, našel jsem procent ia zapojíte hodnotou pro daný int.
Nazval jsem spát po dobu jedné sekundy, jen aby druhu pauzy věcí na obrazovce
poskytují uživateli druhé absorbovat co se právě stalo.
A pak jsem se zlomit.
Jinak, co mám dělat?
Aktualizovat ukazatele rovna ukazatel šipku vedle.
>> Tak aby bylo jasno, to znamená jít tam přes můj old-school notace.
Takže to znamená jen jít do čehokoliv jste ukázal na, které velmi
Prvním případem je, že jsem ukázal na struct s devíti v něm.
Tak jsem šel tam.
A pak tečka notace znamená, získat hodnotu na další.
>> Ale hodnota, a to i když je čerpány jako úzký, jen číslo.
Je to číselná adresa.
Takže tento jeden řádek kódu, ať již napsal takhle víc složitější
způsobem, nebo jako je to, o něco více intuitivní způsob, prostě znamená pohnout rukou
z prvního uzlu na další, a pak další, a potom
další, a tak dále.
>> Takže nebudeme bydlet na straně druhé implementace vkládání a mazání
a průchod, z nichž první dva které jsou poměrně zapojit.
A myslím, že je to docela snadné se dostat ztratil, když dělá to ústně.
Ale to, co můžeme udělat, je zde pokusu o stanovení
nejlepší udělat to vizuálně.
Protože bych navrhoval, že pokud bychom Chci vložit prvky do tohoto
Stávající seznam, který má pět základních prvků -
9, 17, 22, 26, a 33 -
Kdybych měl jít k provedení tohoto v kód, musím zvážit, jak jít
asi dělá.
>> A já bych navrhnout, přičemž dítě kroky přičemž v tomto případě mám na mysli, jaké jsou
možných scénářů, které jsme setkat obecně?
Při provádění vložka pro propojenou seznam, to je náhodou
Konkrétním příkladem velikosti pět.
No, pokud chcete vložit číslo, rádi říkají, že číslo jedna, a
udržování seřazeny objednávky, kde samozřejmě dělá číslo jedna je třeba
jít v tomto konkrétním příkladu?
Stejně jako na začátku.
>> Ale co je zajímavé je, že Chcete-li vložit jeden do toho
seznam, co potřebuje speciální ukazatel aktualizovat zřejmě?
První.
Takže bych si dovolil tvrdit, toto je první případ že bychom mohli chtít, aby zvážila,
scénář zahrnující vkládání na na začátku seznamu.
>> Pojďme trhat off možná tak jednoduché, nebo dokonce jednodušší případ, relativně vzato.
Předpokládejme Chci vložit číslo 35 v seřazeném pořadí.
To samozřejmě patří tam.
Takže to, co ukazatel zřejmě bude musí být aktualizovány v tomto případě?
34 je ukazatel stále není null ale adresa struct
obsahující číslo 35.
Tak to je případ dvou.
Tak už jsem trochu kvantizace kolik práce musím udělat tady.
>> A konečně zřejmé, prostřední případ opravdu, ve středu, když chci
vložit něco jako, řekněme 23, která vede mezi 23 a 26, ale
nyní se věci trochu víc podílí protože to, co
ukazatele je třeba změnit?
22 tak samozřejmě je třeba změnit protože nemůže odkazovat na 26 už ne.
Že je třeba, aby odkazoval na nový uzel, který Budu se muset rozdělit na telefonním čísle
malloc nebo jiným ekvivalentním.
>> Ale pak jsem také potřebovat nový uzel, 23 V tomto případě, aby se její ukazatel
ukázal na koho?
26.
A tam to bude pořadí úkonů zde.
Protože když jsem to hloupě a já například od začátku roku
seznam, a mým cílem je, vložit 23.
A já jsem zkontrolovat, to patří Zde, v blízkosti devíti?
Ne.
Znamená to sem patří, vedle 17?
Ne.
Má to sem patří vedle 22?
Ano.
>> Teď, když jsem hloupý tady, a ne myslí si, až bych mohl
přidělit můj nový uzel pro 23 let.
Bych mohl aktualizovat ukazatel z uzel s názvem 22, směřující
že na nový uzel.
A pak to, co mám aktualizovat Nový uzel je ukazatel, že?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Přesně tak.
Ukázal na 26 let.
Ale dammit kdybych neměl již aktualizovat 22 je ukazatel ukazovat na toho chlapa, a
teď mám sirotky, zbytek seznamu, abych tak řekl.
Takže pořadí operací zde bude důležité.
>> K tomu jsem mohl ukrást, řekněme, šest dobrovolníků.
A uvidíme, jestli můžeme to udělat vizuálně namísto kódu ručiček.
A máme nějaké krásné stres míče pro vás dnes.
OK, jak se o jeden, dva, ve zpět - na konci tam.
tři, čtyři, oba kluci na konci.
A pět, šest.
Jistě.
Pět a šest.
Dobře a my se na vás příště.
Dobře, pojď nahoru.
>> Dobře, když už jsi tady poprvé, byste chtěli být tím, kdo nešikovně
ve skle Google tady?
Dobře, takže OK, sklo, videozáznam.
OK, máte dobré jít.
>> Dobře, takže pokud vy můžete přijít tady jsem předem připravené
některá čísla.
Dobře, pojď sem.
A proč nejdeš trochu dále tímto způsobem.
A podívejme se, jak se jmenuješ, se skleněným Google?
>> STUDENT: Ben.
>> SPEAKER 1: Ben?
OK, Bene, budete první, a to doslova.
Takže budeme posílat do konce období.
Dobře, a vaše jméno?
>> STUDENT: Jason.
>> SPEAKER 1: Jason, OK budete být číslo devět.
Takže pokud budete chtít sledovat Ben tímto způsobem.
>> STUDENT: Jill.
>> SPEAKER 1: Jill, budete mít 17, která, pokud bych to udělal více
inteligentně, musel bych začal na druhém konci.
Můžete jít tudy.
22.
A vy jste?
>> STUDENT: Mary.
>> SPEAKER 1: Mary, budete 22.
A vaše jméno?
>> STUDENT: Chris.
>> SPEAKER 1: Chris, budete 26.
A pak konečně.
>> STUDENT: Diana.
>> SPEAKER 1: Diana, budete 34.
Takže si pojď sem.
>> Dobře, takže perfektní řazeny objednat již.
A pojďme dál, a to takže můžeme opravdu -
Ben jsi jen trochu hledat ven nikde tam.
OK, takže pojďme dál, a líčí to použití zbraně, stejně jako já, přesně,
co se děje.
Takže jděte do toho a dát sami si noha nebo dva mezi sebou.
A jděte do toho a přitom s jednou rukou na ten, kdo byste měli směřovat na
na základě tohoto.
A pokud jste null jen bod přímo na podlahu.
OK, tak dobře.
>> Takže teď máme propojený seznam, a dovolte mi, abych navrhnout, že budu hrát roli
PTR, tak jsem se neobtěžoval provádění tohoto okolí.
A pak - někdo hloupý konvence - můžete volat to, co chcete -
předchůdce ukazatel, pred ukazatel -
je to jen přezdívka jsme dali v náš ukázkový kód k mé levé ruce.
Na druhé straně, která bude udržovat sledovat, kdo je kdo v
následující scénáře.
>> Takže předpokládám, nejprve chci utrhnout pryč , že první příklad vkládání, řekněme
20, do seznamu.
Takže budu potřebovat někoho, kdo by ztělesňují číslo 20 pro nás.
Tak jsem třeba někoho malloc z publika.
Pojď nahoru.
Jak se jmenujete?
>> STUDENT: Brian.
>> SPEAKER 1: Brian, v pořádku, takže musí být uzel obsahující 20.
Dobře, pojď sem.
A samozřejmě, pokud Brian se patří?
Tak, ve středu - ve skutečnosti, počkej.
Děláme to mimo pořadí.
Děláme to mnohem těžší než je třeba, aby se na prvním místě.
OK, jdeme na volný Brian a realloc Brian jak pět.
>> OK, tak teď chceme vložit Brian jak pět.
Tak pojď sem vedle Ben na chvíli.
A můžete říct, pravděpodobně kde tento příběh bude.
Ale pojďme pečlivě promyslet, pořadí úkonů.
A je to právě tato vizuální že se to seřadí
s tímto ukázkový kód.
Tak tady jsem PTR ukázal nejprve není na Bena, samo o sobě, ale bez ohledu na
cení, že obsahuje, což je v tomto případě je - jak se jmenuje?
>> STUDENT: Jason.
>> SPEAKER 1: Jason, tak jak Ben a já jsme ukázal na Jasona v tomto okamžiku.
Takže teď musím zjistit, kde se Brian patří?
Takže jediné, co mám přístup k Právě teď je jeho n datová položka.
Takže budu kontrolovat, je Brian méně než Jasona?
Odpověď je pravda.
>> Tak co teď musí stát, ve správném pořadí?
Musím aktualizovat, kolik ukazatelů celkem v tomto příběhu?
Kde je moje ruka stále ukazuje na Jason a vaše ruce - chcete-li
dát ruku jako, tak nějak jsem nevím, otazník.
OK, dobře.
>> Dobře, takže máte několik kandidátů.
Buď Ben nebo já nebo Brian nebo Jason nebo všichni ostatní, které
ukazatele je třeba změnit?
Kolik celkem?
>> OK, tak dva.
Můj ukazatel nezáleží už protože jsem jen dočasné.
Takže je to tihle dva, pravděpodobně, jak Ben a Brian.
Takže mi dovolte navrhnout, abychom aktualizace Ben, protože je to poprvé.
První prvek tohoto seznamu se nyní bude Brian.
Takže Ben bod na Briana.
OK, co teď?
>> Kdo dostane ukázal na koho?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: OK, takže Brian má ukázat na Jasona.
Ale už jsem ztratil přehled o tomto ukazatel?
Vím, kde je Jason?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: já, protože jsem dočasný ukazatel.
A pravděpodobně jsem se nezměnil ukázat na nový uzel.
Takže můžeme jednoduše Brian bod na toho, kdo mi ukázal na.
A jsme hotovi.
Tak jeden případ, ve vložení na začátku seznamu.
Tam byly dva hlavní kroky.
Za prvé, musíme aktualizovat Bena, a pak musíme rovněž aktualizovat Briana.
A pak nemám obtěžovat traipsing přes zbytek
seznam, protože jsme již našli jeho umístění, protože patřil k
vlevo od prvního prvku.
>> Dobře, takže docela jednoduché.
Ve skutečnosti, pocit, že jsme skoro takže to příliš složité.
Takže pojďme se utrhnout z konce seznamu, a zjistit, kde
složitost začíná.
Takže když teď jsem alloc z publika.
Každý, kdo chce hrát 55?
Tak jo, viděl jsem svou ruku jako první.
Pojď nahoru.
Jo.
Jak se jmenujete?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Habata.
OK, pojď nahoru.
Budete mít číslo 55.
Takže vy, samozřejmě, patří na konci seznamu.
Takže pojďme přehrát simulaci se mnou bytí PTR jen na chvíli.
Tak jsem poprvé bude ukazovat na bez ohledu na to Ben ukázal na.
Oba jsme ukazuje nyní na Briana.
Takže 55 je ne méně než pět.
Takže budu aktualizovat tím, že jsem ukázal na další ukazatel Brianovi, který
Nyní je samozřejmě Jasona.
55 je menší než devět, takže Chystám se aktualizovat PTR.
Chystám se aktualizovat PTR Budu aktualizovat PTR.
A já jdu - hmm, co je Vaše jméno znovu?
>> STUDENT: Diana.
>> SPEAKER 1: Diana ukazuje, samozřejmě, při nulovém s levou rukou.
Takže tam, kde se skutečně Habata patří jasně?
Na levé straně, zde.
Tak jak mám vědět, že ji zde Myslím, že jsem to podělal.
Protože to, co je umění PTR tento okamžik v čase?
Null.
Takže i když vizuálně, můžeme samozřejmě vidět všechny z nich
kluci tady na jevišti.
Já jsem to sledoval z předchozí osoba v seznamu.
Nemám prst ukazující ven, V tomto případě, uzel číslo 34.
>> Takže pojďme skutečně začít to znovu.
Takže teď vlastně nepotřebujete Druhý lokální proměnná.
A to je to, co uvidíte v Skutečný vzorek C kód, kde, jak jsem jít,
když jsem aktualizovat pravou ruku k bodu Jason, přičemž je nutno Brian zezadu, jsem
lepší začít používat levou ruku k aktualizovat, kde jsem byl, takže, jak jsem jít
pomocí tohoto seznamu -
více rozpačitě, než jsem chtěl teď tady vizuálně -
Chystám se dostat do konec seznamu.
>> Tato ruka je stále nulový, což je docela zbytečné, pouze ukazují
Jsem jednoznačně na konci seznamu, ale teď aspoň to mám
předchůdce ukazovatel tady, tak Co teď předává a jaké ukazatele musí
aktualizovat?
Čí ruka chceš překonfigurovat první?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: OK, tak Dianin.
Kam chcete nasměrovat Dianin levý ukazatel na?
Na 55, pravděpodobně, aby jsme tam vložit.
A kde by 55 ukazatel jít?
Dolů, což null.
A moje ruce, v tomto bodě, ne jedno, protože oni byli jen
dočasné proměnné.
Takže teď jsme hotovi.
>> Takže další složitosti tam - a že to není tak těžké zavést,
ale potřebujeme sekundární proměnnou, aby se jistý, že předtím, než jsem se pohnout právo
ruka, jsem aktualizovat hodnotu mé levici ruka, pred ukazatel v tomto případě, tak
že mám koncové ukazatele sledovat, kde jsem byl.
Nyní, jak stranou, pokud si myslíte tohle přes to pocit, že je to
Trochu nepříjemné mít na sledování tohoto levé ruky.
>> Co by jiné řešení tohoto problému byly?
Pokud jste se dostali k redesign data Struktura mluvíme
až teď?
Pokud je to jen trochu cítí trochu nepříjemné mít ráda, dva ukazatele
prochází seznam, kdo by mohl jinak se, v ideálním světě, udržovány
Informace, které potřebujete?
Jo?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Přesně tak.
Pravá takže je to vlastně zajímavý zárodek nápadu.
A tato myšlenka na předchozí ukazatel, ukazuje na předchozí prvek.
Co když jsem ztělesněný, že v seznamu sám?
A to bude těžké si představit, to bez všech papíru
pádu na zem.
Ale předpokládejme, že tito lidé používají jak jejich rukou mít předchozí
ukazatel, a další ukazatel, čímž realizuje to, co budeme říkat dvakrát
spojový seznam.
To by mi dovolte, abych nějak vzad mnohem snadněji, aniž by mě,
programátor, musela držet sledovat ručně -
skutečně ručně -
, kde jsem byl předtím v seznamu.
Takže nebudeme dělat.
Budeme držet to jednoduchý, protože to je přijde za cenu, což je dvakrát
mnoho prostoru pro ukazatele, chcete-li druhou.
Ale to je opravdu společný datové struktury známé jako
dvojnásobně spojový seznam.
>> Pojďme udělat poslední příklad zde a dal tihle kluci z jejich utrpení.
Tak malloc 20.
Pojď nahoru od uličky tam.
Dobře, Jak se jmenujete?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Je nám líto?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Demeron?
OK pojď nahoru.
Ty musí být 20.
Ty samozřejmě budou Patří mezi 17 a 22.
Takže dovolte mi učit mé lekci.
Chystám se začít ukazatel ukázal na Briana.
A já budu mít levou ruku aktualizovat pouze k Brianovi, jak jsem se přesunout na
Jason, kontrola dělá 20 méně než devět?
Ne.
Je o 20 méně než 17?
Ne.
Je o 20 méně než 22?
Ano.
Takže to, co ukazovátka nebo ruce je třeba změnit kde to ukazuje teď?
>> Takže, co můžeme udělat 17 ukazuje na 20 let.
Tak to je v pořádku.
Kde chceme upozornit ukazatel myši teď?
Ve 22.
A my víme, kde 22 je opět díky k mému dočasné ukazatele.
Tak to je v pořádku tam.
Takže kvůli této dočasné skladování Nechal jsem sledovat, kde se všichni.
A teď můžete jít do vizuálně, kde patříte, a teď potřebujeme 1, 2, 3,
4, 5, 6, 7, 8, 9 stres míče, a potlesk pro
tihle kluci, kdybychom mohli.
Dobrá práce.
>> [APPLAUSE]
>> SPEAKER 1: Dobře.
A můžete držet kusy papíru jako památku.
>> Dobře, takže, věřte mi, je to hodně jednodušší projít, aby se
lidé, než je tomu u skutečného kódu.
Ale to, co najdete za chvíli teď, je to stejné - ach, děkuji.
Děkuji -
je, že zjistíte, že stejné údaje struktura, spojový seznam, může ve skutečnosti
být použity jako stavební blok k ještě sofistikované datové struktury.
>> A uvědomit si taky téma zde je, že jsme absolutně představil více
složitost do provádění tohoto algoritmu.
Vložení, a když jsme šli přes to, výmaz a vyhledávání, je trochu
komplikovanější, než se byl s řadou.
Ale získat nějaké dynamiku.
Dostáváme adaptivní strukturu dat.
>> Ale opět platíme cenu, že některé další složitost, a to jak v
provádění.
A my jsme se vzdali náhodný přístup.
A abych byl upřímný, že to není nějaký pěkný čištění snímek můžu dát, že
říká, že je zde důvod, proč spojový seznam je lepší než pole.
A nechat to tak.
Protože téma znovu objevuje nyní, i více v nadcházejících týdnech, je
že to nemusí být nutně správná odpověď.
>> To je důvod, proč máme samostatnou osu designu pro základní problémové okruhy.
Bude to velmi kontextová zda chcete tato data použít
struktura nebo že jeden, a to bude závisí na to, co je pro vás z hlediska
zdrojů a složitosti.
>> Ale dovolte mi navrhnout, aby byla ideální údajů struktura, Svatý grál, bude
něco, co je konstantní čas bez ohledu na to, kolik věcí je
uvnitř, nebylo by úžasné, kdyby datová struktura se vrátil v odpovědi
konstantní čas.
Ano.
Toto slovo je v obrovské slovníku.
Nebo ne, to slovo není.
Nebo nějaký takový problém.
No uvidíme, jestli můžeme alespoň ne krok směrem k tomuto.
>> Dovolte mi navrhnout novou datovou strukturu, která mohou být použity pro různé věci,
v tomto případě nazývá hash tabulky.
A tak jsme vlastně zpět pohledem na poli, v tomto případě, a
trochu uměle, já jsem to vypracovány hash tabulky jako pole s druhem
dvourozměrné pole -
nebo spíše to zde zobrazen jako dva rozměrné pole - ale je to jen
pole o velikosti 26, tak, že pokud se zavolejte pole, stolní držák
nula je obdélník v horní části.
Stolní držák 25 je obdélník v dolní části.
A to je, jak bych mohl nakreslit dat struktura, ve které chci uložit
Jména lidí.
>> Tak například, a nebudu kreslit Celá věc tady na stropě, když jsem
měl toto pole, které jsem teď bude volání hash tabulky, a to je opět
umístění nula.
Tohle je místo jeden, a tak dále.
Tvrdím, že chci použít tato data struktura, v zájmu diskuse
Uložení jmen lidí, Alice a Bob a Charlie a další podobné názvy.
Takže myslíte, že o tom dnes stejně jako začátky , řekněme, ve slovníku
se spoustou slov.
Oni stalo, že se jména v našem příkladu zde.
A to je příliš germane, snad, aby provádí kontrolu pravopisu, jako my
Mohou to být problém nastavit šest.
>> Takže pokud máme řadu celkové velikosti 26 tak, že je to místo 25.
na dně, a tvrdím, že je Alice první slovo ve slovníku
Názvy, které chci vložit do paměti RAM, do tohoto datové struktury, kde jsou
instinkt říká, že Alice je Název by měl jít v tomto poli?
>> Máme 26 možností.
Pokud chceme ji?
Chceme ji v závorce nula, ne?
A pro Alici, řekněme, že nula.
A B bude jeden, a C budou dva.
Takže budeme psát Alicin jméno tady.
Pokud se poté vložte Bob, jeho název půjde zde.
Charlie naleznete zde.
A tak dále dolů Tato datová struktura.
>> Je to nádherná struktura dat.
Proč?
No to je doba chodu vložením lidského jméno do tohoto
struktura dat právě teď?
Vzhledem k tomu, že tato tabulka je implementována, opravdu jako pole.
No, je to konstantní čas.
To je cílem jednoho.
Proč?
>> Tak, jak si zjistit, kde Alice patří?
Když se podíváte na které písmeno jejího jména?
První.
A můžete se tam dostat, když je to řetězec, jen o pohledu na provázku
držák nula.
Takže nultý znak řetězce.
To je jednoduché.
To jsme udělali v crypto přiřazení týdny.
A pak ještě jednou víte, že Alice písmeno velké, můžeme odečíst
off 65 nebo kapitálu je sám, že nám dává nulu.
Takže nyní víme, že Alice patří v místě nulové.
>> A vzhledem k tomu ukazatel k těmto údajům struktura, nějakého druhu, jak dlouho trvá
to se mi najít místo nula v poli?
Jen jeden krok, že je to konstantní čas protože s libovolným přístupem se
Navrhovaný byl charakterizován pole.
Takže ve zkratce, zjišťuje, co index Alice je název, který je v
V tomto případě je, nebo ať to prostě řešit že k nule, kde B je jedna a C je
dva, zjišťuje, že z je konstantní čas.
Musím se podívat na její první dopis, přijít na to, kde je nula
Pole je také konstantní čas.
Takže technicky to jako dva kroky nyní.
Ale to je stále konstantní.
Takže říkáme, že velký O jedné, takže jsme vložena Alici do této tabulky v
konstantní čas.
>> Ale samozřejmě, já jsem byl naivní, ne?
Co když tam Aaron ve třídě?
Nebo Alicia?
Nebo jakékoliv jiné názvy začínající A. Kam jdeme dát
že člověk, ne?
Myslím, že právě teď je tu jen tři Lidé na stole, takže možná jsme
měli dát Aaron v místě nula jedna dva tři.
>> Jasně, mohl jsem tady.
Ale pak, když se snažíme vložit do Davida tento seznam, kde se David jít?
Nyní náš systém spustí vypínací dolů, ne?
Protože teď David skončí tady pokud Aaron je ve skutečnosti zde.
A tak se celá tahle představa, že čistá datová struktura, která nám dává
konstantním čase vložky již není konstantní čas, protože musím
zjistit, oh, sakra, někdo to již v místě Alice.
>> Dovolte mi, abych prozkoumat zbytek těchto údajů struktura, hledat místo dát
někdo jako jméno Aaron.
A tak to taky začíná aby se lineární čas.
Navíc, pokud se chcete vyhledat Aaron v této datové struktuře, a
zkontrolovat, a Áronova jméno tu není.
V ideálním případě by jste právě řekl Aronovi není v datové struktuře.
Ale pokud si začnete dělat prostor pro Aaron tam, kde by byly D
nebo E, ty, v nejhorším případě, je nutné zkontrolovat Celá struktura dat, ve
takovém případě přejde do něčeho lineární ve velikosti tabulky.
>> Takže v pořádku, já to opravit.
Problém je, že jsem měl 26 prvků v tomto poli.
Dovolte mi, abych ji změnit.
Jejda.
Dovolte mi, abych ho změnit tak, že místo bytí velikost 26 celkem, všimněte si na dno
index se změní na n mínus jedna.
Pokud 26 je zjevně příliš malá pro člověka " jména, protože tam jsou tisíce
jména na světě, prostě dělat na 100 nebo 1000 nebo 10000.
Řekněme přidělit mnohem více prostoru.
>> Dobře, že nemusí nutně snížit pravděpodobnost, že nebudeme mít dva
lidé s názvy začínající a tak jsi to zkusit dát
jména na umístění nulu stále.
Pořád bude srazí, což znamená, že stále potřebujeme řešení, aby
Alice a Árona a Alicia a další Jména začínající A jinde.
Ale jak velký problém to je?
Co je to pravděpodobnost, že si mají kolize v datovém
Struktura takhle?
>> No, dovolte mi, abych - vrátíme se na tuto otázku zde.
A podívejte se na to, jak bychom mohli řešit jako první.
Dovolte mi, abych vytáhnout tento návrh zde.
To, co jsme právě popsal, je algoritmus, heuristický tzv. lineární
snímání, kdy, pokud jste se pokusili vložit něco, co zde v těchto údajů
struktura, která se nazývá hash tabulky, a neexistuje žádný prostor tam,
skutečně zkoumat strukturu dat kontrola, je to k dispozici?
Je to k dispozici, je to k dispozici?
Je to k dispozici?
A když konečně je vložíte jméno, které jste původně zamýšlel
jinde v tomto místě.
Ale v nejhorším případě pouze bod může být velmi spodní údajů
struktura, velmi konec pole.
>> Takže lineární sondy, v nejhorším případě, přejde do lineární algoritmus, kde
Aaron, když se stane být vložen poslední v této datové struktuře, mohl by
kolidovat s tímto prvním místě, ale pak konec smůla v samém závěru.
Takže to není konstantní Doba svatý grál pro nás.
Tento přístup, vkládání prvků do datová struktura nazývá hash
tabulka se nezdá být konstantní čas alespoň ne v obecném případě.
To může přejít do něčeho lineární.
>> Takže co kdybychom vyřešit kolize poněkud jinak?
Tak tady je to složitější přiblížit to, co je ještě
tzv. hash tabulky.
A hash, jako stranou, co Mám na mysli, je index, který
Jsem se zmínil dříve.
Chcete-li něco hash může být myšlenka jako slovesa.
>> Takže pokud hash Alice je jméno, hašovací funkce, abych tak řekl,
by měla vrátit číslo.
V tomto případě je nula, pokud se patří na umístění nula, jedna, pokud se patří na
polohy na jedné, a tak dále.
Takže moje hashovací funkce bylo dosud Super jednoduché, jen při pohledu na
První písmeno v něčí jméno.
Ale hašovací funkce bere jako vstup některých údaj,
string, int, cokoliv.
A to vyplivne typicky číslo.
A to číslo je, že data, kdy element patří do datové struktury
známý zde jako tabulky hash.
>> Tak jen intuitivně, to je mírně odlišný kontext.
Toto vlastně odkazuje na příklad zahrnující narozeniny, kde
zde může být tolik, kolik 31 dnů v měsíci.
Ale co se to člověk rozhodnout, dělat v případě nehody?
Kontext teď být, ne kolizi jména, ale kolize narozenin,
když se dva lidé mají narozeniny ve stejný den na 2. října, například.
>> STUDENT: [neslyšitelné].
>> Reproduktor 1: Jo, tak tady máme využití propojených seznamů.
Takže to vypadá trochu jinak než jsme nakreslil dříve.
Ale zdá se, že na pole na levé straně.
To je jeden index, a to bez zvláštní důvod.
Ale je to pořád pole.
Je to pole ukazatelů.
A každý z těchto prvků, z nichž každý z Tyto kruhy nebo lomítka - slash
představuje null - každá z těchto ukazatele se zřejmě ukazuje na
co datová struktura?
Spojový seznam.
>> Takže teď máme schopnost pevný kód do našeho programu
velikost tabulky.
V tomto případě víme, že nikdy více než 31 dnů v měsíci.
Tak těžké kódování hodnoty, jako je 31 rozumné v tomto kontextu.
V souvislosti s názvy, pevný kódování 26 není od věci, že lidé to
pouze názvy začínají, například, abeceda zapojení do Z.
>> Můžeme se nacpat je všechny do těchto údajů struktura tak dlouho, jak když jsme si
kolize, nemáme dát jména zde, namísto toho, že z těchto buněk
ne jako řetězce samotné, ale ukazatele na, například, Alice.
A pak Alice může mít jiný ukazatel na jiný název začíná
A. A Bob se vlastně děje tady.
>> A pokud je tu další jméno začínající pomocí B, on skončí tady.
A tak každý z prvků tohoto stolní dva, když jsme navrhli tento
trochu víc chytře -
no -
když jsme navrhli to trochu víc chytře, se nyní stává adaptivní údajů
struktura, kde neexistuje žádný pevný limit na tom, kolik prvků můžete vložit
do ní, protože pokud máte kolize, to je v pořádku.
Jen do toho pusťte a připojit ji ke co jsme viděli trochu byl ještě před
známý jako propojeného seznamu.
>> Tak pojďme pauzu jen na chvíli.
Co je pravděpodobnost kolize na prvním místě?
Dobře, možná jsem přemýšlel nad, možná Jsem na inženýrské tento problém,
protože víte co?
Ano, mohu přijít s libovolnou Příklady z vrcholu mé hlavy, jako je
Allison a Aaron, ale ve skutečnosti, vzhledem k rovnoměrné rozložení
vstupy, to je nějaký náhodný vkládání do datové struktury, co je opravdu
pravděpodobnost kolize?
Tak se ukázalo, že je to vlastně Super vysoká.
Dovolte mi, abych zobecnit Problém je v tom, jak to.
>> Takže v místnosti n CS50 studenti, co je pravděpodobnost, že alespoň
dva studenti v místnosti mají narozeniny ve stejný den?
Takže to, co. několik Hund -
200, 300 lidí tady a několik set lidí doma dnes.
Takže pokud jste se chtěl zeptat sami sebe, co je pravděpodobnost dvou lidí
v této místnosti má narozeniny ve stejný den, můžeme přijít na to.
A tvrdím, ve skutečnosti existují dva lidé se stejným narozeniny.
>> Například, má někdo má dnes narozeniny?
Včera?
Zítra?
Dobře, takže to vypadá, budu muset udělat 363 nebo tak více
Časy skutečně zjistit, pokud máme kolizi.
Nebo bychom to mohli udělat matematicky spíše než zdlouhavě
jak to udělat.
A navrhuji následující.
>> Takže navrhuji, abychom mohli modelovat pravděpodobnost, že dvě osoby, které mají
narozeniny ve stejný den jako pravděpodobnost 1 minus pravděpodobnost nikdo s
stejně nejlepší.
Takže si to, a to je jen ozdobný způsob, jak psát to, pro
první osoba v pokoji, on nebo ona může mít jeden z možných
narozeniny za předpokladu, že 365 dnů v roce, s omluvou osobám s
29.února narozeniny.
>> Takže první člověk v této místnosti je zdarma mít libovolný počet narozeniny
ze 365 možností tak, že budeme to dělat 365 děleno 365,
což je jedna.
Další osoba v místnosti, v případě, že cílem je, aby se zabránilo kolizi, může jen
mají jeho životnímu jubileu, jak mnoho různých možných dní?
364.
Takže druhý termín v tomto výrazu je v podstatě tím, že matematiku pro nás
odečtením off jeden možný den.
A pak další den, další den, Následující den se na celkovém počtu
lidí v místnosti.
>> A když jsme pak zváží, co pak je pravděpodobnost, ne každý má
Unikátní narozenin, ale opět mínus 1 to, co dostaneme, je výrazem
které mohou velmi fancifully vypadat takto.
Ale je to mnohem zajímavější podívat se na vizuálně.
Toto je tabulka, kde na ose x je počet lidí v místnosti,
počet narozenin.
Na ose y je pravděpodobnost, kolize, dva lidé
mají narozeniny ve stejný den.
>> A stánek s jídlem z této křivky je že jakmile se dostanete do líbí 40
studenti, že jste se na 90% pravděpodobností combinatorically dvou
osoby nebo více, které mají narozeniny ve stejný den.
A jakmile se dostanete líbí 58 lidem, že je to téměř 100% šance dvou
lidé v místnosti se bude muset narozeniny ve stejný den, i když je
365 nebo 366 možných kbelíky a Pouze 58 lidí v místnosti.
Jen statisticky budete pravděpodobně se kolizím, což ve zkratce
motivuje tuto diskusi.
Že i když se dostaneme fantazie tady, a začít s těmito řetězy, jsme stále
bude mít kolize.
>> Tak to vyvolává otázku, co je Náklady dělá inserce a delece
do datové struktury, jako je tento?
Tak mi dovolte navrhnout, -
a nech mě jít zpět na obrazovku přes zde - pokud jsme n prvky
seznam, takže pokud se snažíme vložit n prvků, a máme
kolik celkem lopaty?
Řekněme, že celkem 31 věder v případě narozenin.
Jaká je maximální délka jednoho z těchto řetězců potenciálně?
>> Pokud opět tam 31 možné narozeniny v daném měsíci.
A my jsme jen hrudkující všechny -
ve skutečnosti, že je to hloupý příklad.
Jdem na 26 místo.
Takže pokud skutečně lidé, jejichž jména začít s A až Z, čímž
nás 26 možností.
A my jsme pomocí datové struktury, jako ten jsme právě viděli, čímž máme
pole ukazatelů, z nichž každá poukazuje na připojeném seznamu, kde se
První seznam je každý s názvem Alice.
Druhý seznam je každý s jméno začínající, počínaje
s B, a tak dále.
>> To, co je pravděpodobné, že délka každé z tyto seznamy když budeme předpokládat, pěkný čistý
Rozdělení jmen A až Z v celé datové struktury?
K dispozici je n lidí v datové struktuře děleno 26, pokud jsou dobře
rozprostřeny po celé datové struktury.
Takže délka každé z těchto řetězce je n děleno 26.
Ale ve velkém notace, co to je?
Co je to doopravdy?
Takže je to opravdu jen n, ne?
Protože jsme řekli v minulosti, že fuj vydělte 26.
Ano, ve skutečnosti je to rychlejší.
Ale teoreticky, to není zásadně všechno rychleji.
>> Tak jsme se nezdají být až tak moc blíže k tomuto svatého grálu.
V podstatě je to jen lineární dobu.
Sakra, na tomto místě, tak proč ne my stačí použít jeden obrovský spojový seznam?
Proč ne my stačí použít jeden velký Pole pro ukládání názvů
všichni v místnosti?
No, je tu ještě něco, co přesvědčivá tabulky hash?
Je tu ještě něco, co přesvědčivé o datové struktuře
to vypadá takhle?
Toto.
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Jasně, a znovu když je to jen lineární algoritmus, a
lineární čas datová struktura, proč ne já jen ukládat každého název velké
pole, nebo ve velkém propojeného seznamu?
A přestaň dělat UO tak mnohem těžší než je třeba, aby se?
Co je přesvědčivá, byť i když jsem škrábal ven?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Insertions nejsou?
Drahé už ne.
Takže vložky potenciálně mohli i nadále být konstantní čas, i když data
Struktura vypadá to, řadu ukazatele, z nichž každý ukazuje na
potenciálně spojové seznamy.
Jak byste mohli dosáhnout konstantní čas vložení jména?
Držet ji v přední části, ne?
>> Pokud bychom obětovat cíl návrhu od dříve, kde jsme chtěli udržet
každého název, například, třídění, nebo všechna čísla na scéně řazeny,
Předpokládejme, že máme netříděného spojový seznam.
To jen nás stojí jeden nebo dva kroky, jako v případě Bena a Brianem
dříve, vložit prvek na na začátku seznamu.
Takže pokud se nechcete starat o třídění všechny jmen začínajících nebo všechny
jména začínající na B, můžeme stále dosáhnout konstantní čas vložení.
Nyní vzhlédl Alice nebo Bob nebo jakýkoli název obecně je stále co?
Je to velký O n děleno 26, v ideální případ, kdy jsou všichni jednotně
distribuovány, kde je tolik, kolik je protože jsou to Z, což je pravděpodobně
nereálné.
Ale to je stále lineární.
>> Ale tady jsme se vrátit k bodu z asymptotické notace bytí
teoreticky pravda.
Ale v reálném světě, když tvrdí, že můj program něco udělat 26 krát
rychleji než ty, jejichž program, budete raději používáte?
S pozdravem a dolu, což je 26 krát rychlejší?
Realisticky, osoba, která je o 26 krát rychlejší, i když je to teoreticky
naše algoritmy spustit ve stejném asymptotická době jeho běhu.
>> Dovolte mi navrhnout jiný řešení vůbec.
A pokud to nebude foukat vaši mysl, jsme z datových struktur.
Tak to je trie -
druh hloupé jméno.
Pochází z rešerší, a slovo se píše trie, t-r-i-e, protože
Kurz vyhledávání zní jako trie.
Ale to je historie na slovo trie.
>> Takže trie je opravdu nějaký druh stromu, a je to také hra na dané slovo.
A i když nemůžete docela vidět s touto vizualizací, trie je
strom strukturován jako rodokmenu s jeden předek nahoře a mnoho
vnoučat a velkých vnoučata jako listy na dně.
Ale každý uzel trie je pole.
A to je v poli - a pojďme zjednodušovat na chvíli - je to
pole, v tomto případě o velikosti 26, kde každý uzel je opět pole o velikosti
26, kde je v tom, že nultý prvek pole představuje, a poslední
element v každé takové Pole představuje Z.
>> Takže navrhuji tedy, aby tato data struktury, známé jako trie, může být
použít i pro ukládání slova.
Viděli jsme před chvílí, jak bychom mohli uložit slova, nebo v tomto případě jména, a my
již viděli, jak můžeme uložit čísla, ale pokud se zaměříme na názvy nebo řetězce
Zde si všimněte, co je zajímavé.
Tvrdím, že název je Maxwell v této datové struktury.
Kde vidíte Maxwell?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Na levé straně.
Takže to, co je zajímavé, s těmito daty struktura je spíše než obchod se
řetězec M-A-X-W-E-L-L lomítko nula, všechny souvislý, co můžete udělat, místo toho
je následující.
Pokud se jedná o trie jako datové struktury, každý jehož uzlech je opět pole,
a chcete uložit Maxwell, musíte nejprve index, a tak v kořenovém uzlu, takže
mluvit, nejhořejší uzel, na umístění M, vpravo, tak
zhruba do středu.
A pak odtud, postupujte ukazatel na podřízené uzly, abych tak řekl.
Takže v rodokmenu smyslu, budete postupovat směrem dolů.
A, které vás dovedou do jiného uzlu Vlevo, který je
jen další pole.
>> A pak, pokud chcete uložit Maxwell, najdete ukazatel, který představuje
A, což je toto zde.
Pak můžete jít na další uzel.
A upozornění - to je důvod, proč je obraz trochu klame -
Tento uzel vypadat Super malý.
Ale na pravé straně je Y a Z. Je to jen autor zkrácen
obraz tak, že jste skutečně vidět věci.
Jinak tento obrázek by bylo velmi široké.
Takže teď si index do umístění X, pak W, pak E, pak L, pak L. Tak co je
to zvědavost?
>> No, pokud budeme používat tento druh nový se o tom, jak ukládat řetězec
datová struktura, stále musíte v podstatě zaškrtnout v datech
struktura, která slovo zde končí.
Jinými slovy, každý z těchto uzlů nějak musí pamatovat, že jsme
vlastně následoval všech těchto ukazatelů a odcházejí trochu
chléb drobky ve spodní části zde v této Struktura pro označení M-A-X-W-E-L-L
ve skutečnosti v této datové struktury.
>> Tak bychom mohli postupovat takto.
Každý z uzlů v obraze jsme jen Pila má jeden, pole o velikosti 27.
A to je v současné době 27, protože v p nastavit šest, budeme ve skutečnosti vám apostrof,
takže můžeme mít jména jako O'Reilly a jiní s apostrofy.
Ale stejný nápad.
Každý z těchto prvků v pole poukazuje na struct
uzel, tak jen uzel.
Tak to je velmi připomínající našeho propojeného seznamu.
>> A pak jsem si Boolean, který budu zavolejte slovo, které je jen bude
true, pokud slovo končí na to uzel ve stromu.
Je to skutečně představuje malý trojúhelník jsme viděli před chvílí.
Takže pokud slovo končí v tomto uzlu strom, bude to slovo pole je pravda,
který je koncepčně zaškrtnutím nebo jsme kreslíte tohoto trojúhelníku, ano, tam
je slovo zde.
>> Tak to je trie.
A teď je otázka, co je jeho doba chodu?
Je to velký O n?
Je to něco jiného?
No, pokud jste n názvy těchto údajů struktura, Maxwell je pouze jedním z
je, jaká je doba chodu vkládání nebo zjištění Maxwell?
Co je to doba chodu vložení Maxwell?
Pokud existuje n jiná jména již v tabulce?
Jo?
>> STUDENT: [neslyšitelné].
>> SPEAKER 1: Jo, je to délka jména, ne?
Tak M-a-x-w-e-l-l, takže to je takto algoritmus je velký O sedm.
Nyní, samozřejmě, název mají různou délku.
Možná je to krátký název.
Třeba je to delší jména.
Ale co je klíčové je to, že je to neustálý číslo.
A možná to opravdu není konstantní, Ale Bůh, když realisticky, v
slovník, je to asi nějaká hranice, Na počtem písmen ve
jméno osoby v dané zemi.
>> A tak můžeme předpokládat, že hodnota je konstantní.
Nevím, co to je.
Je to pravděpodobně větší než si myslíme, že je.
Protože tam je vždy nějaký roh pouzdro s crazy dlouhým názvem.
Takže řekněme, že k, ale je to stále konstantní pravděpodobně, protože každý
jméno ve světě, alespoň v Zejména země, je to, že délka nebo
kratší, takže je konstantní.
Ale když jsme řekli, že je něco velké O konstantní hodnoty, co je to
skutečně odpovídá?
To je opravdu to samé jak říká konstantní čas.
>> Teď jsme trochu podvádění, ne?
Jsme druh využití teorii, zde říci, že dobře, aby součinitele je
opravdu jen řádově jedné, a to je konstantní čas.
Ale ve skutečnosti je.
Vzhledem k tomu, Klíčovou myšlenkou je, že pokud jsme n jména již v tomto
datové struktury, a vložíme Maxwell, je množství času, které nás zavede do
vložit Maxwell vůbec postižené tím, kolik dalších lidí
jsou v datové struktuře?
Nezdá se, že být.
Kdybych měl miliardu více prvků této trie a vložte Maxwell, je
se vůbec týká?
Ne.
A to je na rozdíl od některého z denních dat struktury jsme viděli doposud, kdy
doba chodu algoritmu je zcela nezávisle na tom, jak moc
věc je nebo není již v této datové struktury.
>> A tak s tím poskytuje nyní je příležitost pro p sadu šesti, která bude
opět zahrnovat realizaci vlastní Kontrola pravopisu, čtení v 150000
slova, jak nejlépe uložit, že není nutně zřejmé.
A když jsem usiloval, aby si Svatý grál, vůbec se mi nelíbí
tvrdí, že je trie.
Ve skutečnosti může být hašovací tabulka velmi dobře ukáže být mnohem efektivnější.
Ale to jsou jen -
to je jen jedna z rozhodnutí o návrhu budete muset udělat.
>> Ale při uzavírání pojďme 50 nebo tak sekund se podívat na to, co je
před příští týden a my po přechodu z tohoto příkazového řádku
světě, pokud C programy k věcem web založené a jazyky jako PHP a
JavaScript a internet sám, protokoly jako HTTP, kterou jste
brát za samozřejmost let teď, a napsal většinu každý
den, možná, nebo vidět.
A začneme oloupejte vrstvy, co je internet.
A co je kód, který tvoří základ dnešní nástroje.
Takže 50 sekund tohoto ukázku zde.
Dám vám Bojovníci sítě.
>> [PŘEHRÁVÁNÍ]
>> -Přišel se zprávou.
S protokolem všichni jeho vlastní.
Přišel na svět krutých firewallů, bezcitný routery a nebezpečí daleko
horší než smrt.
Je rychlý.
Je silný.
Je TCPIP.
A má svou adresu.
Válečníci sítě.
>> [END PŘEHRÁVÁNÍ]
>> SPEAKER 1: To je, jak internet musí pracovat od příštího týdne.