[Powered by Google Translate] [Oddíl 3 - Další Komfortní]
[Rob Bowden - Harvard University]
>> [To je CS50. - CS50.TV]
>> Takže první otázka je podivně zní.
GDB umožňuje "ladit" program, ale konkrétně, co to nechat udělat?
Budu odpovědět, že jeden, a já nevím, co to přesně očekává,
takže hádám, že je to něco v duchu to umožňuje krok za krokem
projít programu, pracovat s ním, změna proměnných, dělat všechny tyto věci -
v podstatě kompletně ovládat provádění programu
a zkontrolujte, zda na dané části realizace programu.
Takže tyto funkce vám umožní ladit věci.
Dobře.
Proč binární hledání vyžaduje, aby pole být seřazeny?
Kdo chce odpovědět, že?
[Student] Vzhledem k tomu, že nefunguje, pokud to není seřazena. Jo >>. [Smích]
Pokud to není seřazena, pak je to možné rozdělit na dvě poloviny
a vím, že všechno, co na levé straně je menší a všechno vpravo
je větší, než je střední hodnota.
Tak to musí být seřazeny.
Dobře.
Proč je bublina třídit O n na druhou?
Má někdo nejprve chtít dát velmi rychle na vysoké úrovni přehled o tom, co bublina druh je?
[Student] Ty v podstatě projít každý prvek a dáte zjistit několik prvních prvků.
Pokud jsou z místa, kde jste je swap, pak zkontrolovat několik dalších prvků, a tak dále.
Když se dostanete na konec, pak víte, že největší prvek je umístěn na konci,
takže budete ignorovat, že jeden pak pokračovat dál přes,
a pokaždé, když budete muset zkontrolovat jeden méně prvek, dokud neprovedete žádné změny. Jo >>.
Je to tzv. bubble sort, protože pokud otočíte pole na jeho straně, takže je to nahoru a dolů, vertikální,
pak velké hodnoty klesne na dno a nízké hodnoty vůle bublina až na vrchol.
To je, jak to dostalo jeho jméno.
A jo, stačí projít.
Pořád jde přes pole, vyměňovat větší hodnotu
aby se největší hodnoty na dno.
>> Proč je to O n na druhou?
Za prvé, někdo chce říct, proč je to O n na druhou?
[Student] Protože pro každý běh jde n krát.
Můžete být jisti, že jste si vzal Nejsilnějším prvkem celou cestu dolů,
pak se budete muset zopakovat, že tak mnoho prvků. Jo >>.
Takže mějte na paměti to, co velké O znamená a jaké velké Omega znamená.
Velký O je jako horní mez na to, jak pomalu to může skutečně spustit.
Takže tím, že říká, že je to O n. čtverečkovaný, to není O n jinak by být schopen spustit
v lineárním čase, ale je to O z n kostičky
protože to je ohraničeno O n kostičky.
Pokud je to ohraničeno O n čtvercový, pak je to ohraničeno i n kostičky.
Takže je n na druhou, a v absolutním nejhorším případě nelze lépe než n čtvercový,
což je důvod, proč je O z n na druhou.
Takže vidět mírný matematiku na to, jak vyjde ven, aby se n na druhou,
pokud budeme mít pět věcí v našem seznamu, poprvé, kolik swapy bychom mohli potenciálně třeba, aby se
aby se to? Pojďme vlastně jen -
Kolik swapy budeme muset udělat v prvním běhu bublin řadit přes pole?
[Student] n - 1. Jo >>.
>> Pokud jsou 5 prvků, budeme muset provést n - 1.
Pak na druhém kolik swapy budeme muset udělat?
[Student] n - 2. Jo >>.
A třetí bude n - 3, a pak pro pohodlí budu psát poslední dva
jak pak budeme potřebovat, aby se 2 swapy a 1 swap.
Myslím, že poslední člověk může nebo nemusí ve skutečnosti se muselo stát.
Je to výměna? Nevím.
Takže se jedná o celkové množství swapů nebo alespoň srovnání budete muset udělat.
I když nechcete vyměnit, budete ještě potřebovat k porovnání hodnot.
Tak jsou n - 1 srovnání v prvním projetí pole.
Pokud uspořádání těchto věcí, pojďme vlastně dělat to šest věcí, takže to vyrovnat pěkně,
a pak budu dělat 3, 2, 1.
Takže jen přeskupit tyto částky, chceme vidět, kolik srovnání děláme
v celém algoritmu.
Takže pokud vám přinášíme ty chlapy tady,
pak jsme stále jen součet však mnoho srovnání existovaly.
Ale pokud sečteme tyto a sečteme tyto a sečteme tyto,
je to stále stejný problém. Právě jsme shrnout tyto konkrétní skupiny.
>> Takže teď se budeme sčítat 3 n. Není to jen 3 n.
Je to vždycky bude n / 2 n.
Takže tu máme náhodou 6.
Pokud jsme měli 10 věcí, pak bychom mohli udělat tuto sdružení pro 5 různých párů věcí
a skončit s n + n + n + n + n.
Takže jste vždy dostane n / 2 n je, a tak to budeme zapisovat to k n na druhou / 2.
A tak i když je to faktor poloviny, který se stane dál
vzhledem k tomu, že po každé iteraci přes pole porovnáme 1 méně
tak to je, jak se dostaneme přes 2, ale to je ještě n na druhou.
My se nestaráme o konstantní faktor o polovinu.
Takže hodně velké věci O takhle spoléhá jen na druhu dělat tento druh matematiky,
dělat aritmetické součty a geometrické řady další věci,
ale většina z nich v tomto kurzu jsou docela jasné.
Dobře.
Proč je vložení třídit Omega n? Co omega znamená?
[Dva studenti mluví najednou - nesrozumitelné] >> Jo.
Omega si můžete myslet, jak dolní mez.
>> Takže bez ohledu na to, jak efektivní váš vložení sort je algoritmus,
bez ohledu na seznamu, který je předán do, vždy musí porovnat alespoň n věci
nebo to má pro iteraci n věcí.
Proč je to?
[Student] Protože pokud je seznam již řazeno, pak přes první iteraci
můžete pouze zaručit, že úplně první element je nejméně,
a druhá iterace lze pouze zaručit první dva jsou
protože nevíte, že zbytek seznamu seřazeny. Jo >>.
Pokud předáte ve zcela seřazený seznam, přinejmenším budete muset jít přes všechny prvky
vidět, že nemusí nic být se pohyboval.
Takže procházející přes seznam a řekl oh, je to už jsou seřazena,
to je nemožné, abyste věděli, že to jsou seřazena dokud zjistit každý prvek
aby se zjistilo, zda jsou v seřazeném pořadí.
Tak dolní mez vložení řadit je Omega n.
Co je nejhorší doba chodu druhu korespondence,
Nejhorší případ je velké O znovu?
Takže v nejhorším případě, jak se sloučení sort běží?
[Student] N log n. Jo >>.
Nejrychlejší obecné třídění algoritmy jsou n log n. Můžete to udělat lépe.
>> Existují speciální případy, a pokud budeme mít čas dnes - ale asi won't -
jsme mohli vidět ten, který dělá lépe než n log n.
Ale v obecném případě, nemůžete udělat lépe, než n log n.
A sloučit druh se stane, že ten, co byste měli vědět o tomto kurzu, který je n log n.
A tak budeme skutečně provádí, že dnes.
A konečně, v ne více než tři věty, jak se výběr řazení práci?
Má někdo bude chtít odpovědět, a já počítat své věty
protože pokud půjdete přes 3 -
Pamatuje si někdo, výběr druhu?
Výběr řazení je obvykle docela snadné si pamatovat jen z názvu.
Stačí iterovat přes pole, najít, co největší hodnota nebo nejmenší -
bez ohledu na pořadí, které jste třídění palců
Takže řekněme, že jsme třídění od nejmenší k největší.
Můžete iterovat přes pole, hledá bez ohledu na minimální prvek,
vyberte ji, a pak už jen vyměnit to, co je na prvním místě.
A pak na druhém průchodu přes pole, podívejte se na minimální prvek znovu,
vyberte ji a poté si vyměňovat s tím, co je na druhé pozici.
Takže jsme jen sběr a výběr minimální hodnoty
a vložením do přední části pole, dokud se třídí.
Otázky týkající se, že?
>> Ty nevyhnutelně objevují ve formách, které musíte vyplnit, když jste podání PSet.
Ti jsou v podstatě odpovědi na ty.
Dobře, takže teď kódování problémy.
Už jsem rozeslal přes e-mail - Bylo někdo nedostal tento e-mail? Dobře.
Už jsem rozeslal přes e-mail na místo, které jsme bude používat,
a pokud kliknete na mé jméno - takže myslím, že budu na dně
z důvodu zpětné r - ale pokud kliknete na mé jméno uvidíte 2 revize.
Revize 1 se bude už jsem zkopírovat a vložit kód do prostorů
pro hledání věc, kterou budete muset provádět.
A Revize 2 bude druh věcí, které provádíme po tom.
Takže můžete kliknout na mé revize 1 a pracovat odtamtud.
A nyní chceme zavést binární vyhledávání.
>> Má někdo chtěl jen dát pseudokódu na vysoké úrovni vysvětlení
z toho, co budeme muset udělat pro vyhledávání? Jo.
[Student] Stačí vzít střed pole a uvidíme, jestli to, co jste hledali
je menší než nebo více.
A pokud je to méně, jdete do poloviny, která je méně,
a pokud je to víc, můžete jít do poloviny, která je více a vy to zopakovat, dokud stačí si jednu věc.
[Bowden] Jo.
Všimněte si, že naše čísla pole je již řazeno,
a tak to znamená, že můžeme využít, že jsme mohli nejprve zkontrolujte,
jo, já jsem hledal číslo 50.
Takže můžu jít do středu.
Střední je těžké definovat, kdy je to ještě řada věcí,
ale řekněme, že budeme vždy zkrátit na středu.
Takže tu máme 8 věcí, takže prostřední bude 16.
Hledám 50, takže 50 je větší než 16 let.
Takže teď můžu v podstatě léčit své pole jako těchto prvků.
Mohu vyhodit vše od 16 přes.
Teď je moje pole je právě tato 4 prvky, a opakuji.
Takže chci najít střed znovu, což bude 42.
42 je menší než 50, takže můžu hodit daleko tyto dva prvky.
To je můj zbývající pole.
Jdu najít střed znovu.
Myslím, že 50 byl špatný příklad, protože jsem byl vždycky zahodil věci na levé straně,
ale ve stejné míře, když jsem hledal něco
a je to méně, než prvek jsem v současné době při pohledu na,
pak budu vyhazovat všechno vpravo.
Takže teď musíme zavést, že.
Všimněte si, že musíme projít ve velikosti.
Můžeme také není nutné hard-kódu velikosti.
Takže pokud se zbavíme toho # define -
Dobře.
Jak mohu krásně zjistit, co velikost čísel pole je v současné době?
>> Kolik prvků je v číslech poli?
[Studentských] Čísla, držáky,. Délka?
[Bowden] To neexistuje v C.
Potřebujete. Délka.
Pole nemají vlastnosti, takže není délka vlastnost polí
že bude jen aby vám jak dlouho to stane se.
[Student] Viz kolik paměti má, a rozdělit podle toho, jak moc - >> Jo.
Takže, jak můžeme vidět, kolik paměti má? >> [Student] sizeof. Jo >>, sizeof.
Sizeof je operátor, který to bude vrátit velikost čísla pole.
A to bude ale mnoho celá čísla tam jsou časy, velikost celé číslo
protože to je to, kolik paměti je to vlastně nástupu do.
Takže pokud chci, aby řadu věcí v poli,
pak budu chtít rozdělit podle velikosti na celé číslo.
Dobře. Takže mi umožňuje předat ve velikosti zde.
Proč musím předat do velikosti vůbec?
Proč nemůžu prostě dělat tady int size = sizeof (sena) / sizeof (int)?
Proč to nefunguje?
[Student] Není to globální proměnná.
[Bowden] Haystack existuje a my jsme kolem v číslech jako kupce sena,
a tohle je předzvěst toho, co přijde. Jo.
[Student] Haystack je jen odkaz na to, tak to by se vrátit, jak velký tento odkaz je.
Jo.
Pochybuji, v přednášce, když jste viděli hromadu skutečnosti ještě, že jo?
Právě jsme mluvili o tom.
Takže stack je místo, kde všechny vaše proměnné se bude uložen.
>> Každá paměť, která je přidělena pro lokální proměnné se děje v zásobníku,
a každá funkce má svůj vlastní prostor na zásobníku, vlastní zásobník rám je to, co se jmenuje.
Takže hlavní má svůj stack frame a uvnitř ní bude existovat tento čísla pole,
a to bude o velikosti sizeof (čísla).
Bude to mít velikost čísel rozdělených podle velikosti prvků,
ale že všechny životy v zásobníku rámci hlavní je.
Když zavoláme hledání, hledání má svůj vlastní zásobník rám,
vlastní prostor pro ukládání všech svých lokálních proměnných.
Ale tyto argumenty - takže sena není kopie celého tohoto pole.
Nechceme předat v celé pole jako kopie do vyhledávání.
Je to jen předá odkaz na této matice.
Takže hledání lze přístup k těmto číslům prostřednictvím tohoto odkazu.
Je to stále přístup k věci, které žijí uvnitř zásobníku rámu hlavních je,
ale v podstatě, když se dostaneme do ukazatelů, které by mělo být brzy,
To je to, co ukazovátka.
Ukazatele jsou jen odkazy na věci, a můžete použít odkazy na přístup k věci
které jsou v zásobníku jiných věcí "rámů.
Takže i když čísla je místní hlavní, stále ještě můžeme přistupovat prostřednictvím tohoto ukazatele.
Ale protože je to jen ukazatel a je to jen odkaz,
sizeof (haystack) vrátí pouze velikost odkazu samotného.
To nevrátí velikost věc je to ukazuje.
To nevrátí skutečnou velikost čísel.
A tak to nebude fungovat, jak chceme, aby to.
>> Otázky týkající se, že?
Ukazatele budou pryč do významně více krvavý podrobněji v týdnech přijít.
A to je důvod, proč mnoho věcí, které vidíte, většina vyhledávacích věcí nebo třídit věci,
oni téměř všichni budeme muset vzít skutečné velikosti pole,
protože v C, nemáme ponětí, co velikost pole je.
Musíte ručně přenést dovnitř
A nelze ručně předat v celém poli, protože jsi jen procházet v odkazu
a to může dostat do velikosti v odkazu.
Dobře.
Takže teď chceme realizovat to, co bylo vysvětleno dříve.
Můžete pracovat na něm za minutu,
a nemusíte se bát všechno perfektně 100% funkční.
Stačí napsat do poloviční pseudokódu pro to, jak si myslíte, že by to mělo fungovat.
Dobře.
Není třeba být zcela hotový s to ještě.
Ale někdo cítí dobře s tím, co mají tak daleko,
jako něco, co můžeme pracovat společně?
Má někdo chtěl dobrovolně? Nebo jsem se náhodně vybírat.
Nemusí to být přímo v každém ohledu, ale něco, co můžeme měnit do funkčního stavu.
[Student] Jasně. Dobře >>.
Takže můžete ušetřit na revizi kliknutím na malou ikonu Uložit.
Jste Ramya, že jo? >> [Student] Jo. >> [Bowden] Dobře.
Takže teď můžu zobrazit revizi a každý může vytáhnout revizi.
A máme tady - Dobře.
Tak Ramya šel s rekurzivní řešení, které je rozhodně platné řešení.
Existují dva způsoby, jak můžete udělat tento problém.
Můžete to udělat iteračně nebo rekurzivně.
Většina problémy mi, že může být provedeno rekurzivně může být rovněž provedeno opakované.
Tak tady jsme udělali to rekurzivně.
>> Má někdo chcete definovat, co to znamená, aby se funkce rekurzivní?
[Student] Pokud máte funkci volat sebe
a pak volat sebe, dokud to vyjde s pravdou a pravda. Jo >>.
Rekurzivní funkce je jen funkce, která volá sama sebe.
K dispozici jsou tři velké věci, které rekurzivní funkce musí mít.
První z nich je samozřejmě, že volá sama sebe.
Druhým je base-case.
Takže v určitém okamžiku funkce musí přestat volat sám,
a to je to, co referenční případ je pro.
Tak tady víme, že bychom měli přestat, měli bychom se v našem hledání
je-li start rovná konec - a půjdeme nad tím, co to znamená.
Ale nakonec, poslední věc, která je důležitá pro rekurzivní funkce:
funkce musí nějak přiblížit základní věc.
Stejně jako když jste ve skutečnosti aktualizace nic, když uděláte druhý rekurzivní volání,
pokud jste doslova volá funkci znovu se stejnými argumenty
a žádné globální proměnné změnily nebo tak něco,
budete nikdy nedosáhne základní věc, v tomto případě to je špatné.
Bude to nekonečná rekurze a přetečení zásobníku.
Ale tady vidíme, že aktualizace se děje, protože jsme aktualizaci kdo + konec / 2,
jsme aktualizaci konec argumentu tady, jsme aktualizaci počáteční tvrzení zde.
Takže ve všech rekurzivní volání jsme aktualizaci něco. Dobře.
Chcete chodit nám prostřednictvím řešení? Jistě >>.
Já používám SearchHelp tak, že pokaždé, když jsem tuto funkci volání
Mám start, kde jsem hledal v poli a konec
, kde jsem pohledu na pole.
>> Na každém kroku, kde je to říká, že je to střední element, který je začátek + konec / 2,
je, že rovná tomu, co jsme hledali?
A pokud je, pak jsme ho našli, a já myslím, že je předán do úrovně rekurze.
A pokud to není pravda, pak jsme zkontrolovat, zda střední hodnota pole je příliš velká,
v takovém případě se díváme na levé polovině pole tím, že jde od začátku do střední indexu.
A jinak děláme Konec poloviny.
[Bowden] Dobře.
To zní dobře.
Dobře, takže pár věcí, a skutečně, je to velmi vysoké úrovni, co
že budete nikdy vědět tohoto kurzu, ale je to pravda.
Rekurzivní funkce, vždy uslyšíte, že jsou špatné řešení
protože když rekurzivně říkáš příliš mnohokrát, získáte přetečení zásobníku
protože, jak jsem již řekl dříve, každá funkce má svůj vlastní zásobník rám.
Takže každý hovor z rekurzivní funkce má svůj vlastní zásobník rám.
Takže pokud uděláte 1.000 rekurzivní volání, získáte 1.000 zásobník snímků,
a rychle se vést k nutnosti příliš mnoho stack rámy a věci se rozbijí.
Takže to je důvod, proč rekurzivní funkce jsou obecně špatné.
Ale tam je pěkný podmnožina rekurzivních funkcí tzv. tail-rekurzivní funkce,
a to se stane, že je příkladem jedné, kde v případě, že kompilátor vnímá tento
a to by mělo, myslím, že - v Clang předáte ho-O2 flag
pak si všimnete je to ocas rekurzivní a dělat věci dobře.
>> To bude používat stejné fronty rám znovu a znovu pro každou rekurzivní volání.
A tak, protože jste pomocí stejného zásobníku rám, nemusíte se obávat
kdy zásobník přetékání, a současně, jak si řekl,
kde jakmile se vrátíte pravda, pak to musí vrátit do všech těchto zásobníku rámů
a 10. výzva k SearchHelp musí vrátit do 9., se musí vrátit do 8..
Takže není třeba se stane, když funkce ocas rekurzivní.
A tak to, co dělá tato funkce ocas rekurzivní je upozornění, že pro dané výzvy k searchHelp
rekurzivní volání, že to dělat, je to, co se vrací.
Takže v první výzvě k SearchHelp, jsme buď okamžitě vrátí false,
okamžitě vrátit true, nebo budeme dělat rekurzivní volání SearchHelp
kde to, co se vracíme, je to, co, že hovor se vrací.
A my jsme nemohli dělat to, pokud jsme udělali něco jako int x = SearchHelp, return x * 2,
jen nějaký náhodný změna.
>> Takže teď to rekurzivní volání, toto int x = SearchHelp rekurzivní volání,
je již ocas rekurzivní, protože to vlastně nemá muset vrátit
zpět na předchozí zásobníku rámu tak, že předchozí volání funkce
pak může něco udělat s návratovou hodnotou.
Takže to není ocas rekurzivní, ale to, co jsme měli předtím, je pěkně ocas rekurzivní. Jo.
[Student] Pokud není druhá základna případ zkontrolovat první
protože by mohlo nastat situace, kdy při předat argument
jste start = konec, ale oni jsou jehly hodnotu.
Otázka nemůže narazíme na případ, kdy je konec jehly hodnota
nebo start = konec, přiměřeně, start = konec
a vy jste ve skutečnosti kontrolovat, že konkrétní hodnoty ještě,
pak začít + konec / 2 je jen tak mít stejnou hodnotu.
Ale my už se vrátil false, a nikdy jsme vlastně četl hodnotu.
Takže přinejmenším v prvním hovoru, pokud je velikost 0, pak chceme vrátit false.
Ale pokud velikost je 1, pak začátek nebude stejné konce,
a budeme alespoň zkontrolovat jeden prvek.
Ale myslím, že máte pravdu v tom, že můžeme skončit v případě, kdy začít + konec / 2,
Začátek nakonec je stejný jako začátek + konec / 2,
ale nikdy jsme vlastně četl tento prvek.
>> Takže když jsme nejprve zkontrolovat, je střední prvek hodnotu, kterou hledáte,
pak můžeme okamžitě vrátit true.
Else, pokud jsou stejné, pak je tu nemá smysl pokračovat
protože jsme jen tak aktualizaci na případ, kdy jsme na jedné prvku pole.
Pokud tento jediný prvek není ten, kterého hledáme,
pak je vše v pořádku. Jo.
[Student] věc je, že od té doby velikost je ve skutečnosti větší než počet prvků v poli,
tam je už offset - >> Tak bude velikost -
[Student] říci, zda pole je velikost 0, pak SearchHelp skutečně kontrolovat Haystack 0.
na první výzvu.
Pole má velikost 0, takže 0 je - >> Jo.
Je tu další věc, která - to by mohlo být dobré. Pojďme přemýšlet.
Takže pokud pole měl 10 článků a prostřední budeme kontrolovat, je index 5,
takže jsme kontrolu 5, a řekněme, že hodnota je menší.
Takže jsme házet všechno pryč od 5 kupředu.
Takže začít + end / 2 bude náš nový konec,
tak jo, to vždycky zůstat i po skončení tohoto pole.
Pokud je to případ, kdy to bylo sudé nebo liché, pak bychom zjistili, zda, řekněme, 4,
ale my jsme pořád vyhazujete -
Tak jo, konec je vždy bude za skutečného konce pole.
Takže prvků jsme se zaměřením na, konec je vždy bude jeden po tom.
A pokud se někdy začátek stejný konec, my jsme v poli velikosti 0.
>> Druhá věc, kterou jsem myslel je, že jsme aktualizaci start se začít + konec / 2,
tak to je pravda, že mám potíže s, kde začít + konec / 2
je element jsme kontrolu.
Řekněme, že jsme měli 10-prvek pole. Cokoliv.
Takže začít + end / 2 bude něco jako je tento,
a pokud to není hodnota, že chceme aktualizovat.
Hodnota je větší, takže chceme se podívat na této poloviny pole.
Tak jak jsme aktualizaci začátek, jsme aktualizaci start nyní tento prvek.
Ale to se může stále fungovat, nebo přinejmenším, můžete tak učinit začátek + konec / 2 + 1.
[Student] Nemusíte být začít + konec [neslyšitelné] >> Jo.
Jsme již zkoumali tento prvek a vím, že to není ten, kterého hledáme.
Takže nepotřebujeme aktualizovat start je tento prvek.
Můžeme jen přeskočit a aktualizovat začít být tento prvek.
A je tam někdy případ, řekněme, že to bylo konec,
takže pak kdo by to, kdo + konec / 2 by to,
kdo + konec - Jo, myslím, že to může skončit v nekonečné rekurze.
Řekněme, že je to jen pole o velikosti 2 nebo pole o velikosti 1. Myslím, že to bude fungovat.
Takže v současné době, start je tento prvek a konec je 1 mimo něj.
Takže prvek, který budeme kontrolovat, je to jedno,
a pak, když jsme aktualizaci začátek, jsme aktualizaci start být 0 + 1/2,
který se bude do konce nás zpět s počáteční že tento prvek.
>> Takže jsme kontrolu stejný prvek znovu a znovu.
Tak tohle je případ, kdy každá rekurzivní volání, musí být skutečně aktualizovat něco.
Takže musíme udělat začátek + konec / 2 + 1, jinak je tu případ
kde jsme ve skutečnosti aktualizace začátek.
Všichni vidí, že?
Dobře.
Má někdo nějaké dotazy týkající se tohoto roztoku nebo jakékoli další komentáře?
Dobře. Má někdo iterativní řešení, které můžeme všichni podívat na?
Jsme to všichni rekurzivně?
Nebo také myslím, že pokud jste si otevřeli její, pak byste měli mít přepsat svůj předchozí.
Má to automaticky ukládat? Nejsem pozitivní.
Má někdo se opakující?
Můžeme projít ní společně, ne-li.
Tato myšlenka je bude stejné.
Iterační řešení.
Budeme chtít, aby v podstatě dělat stejnou myšlenku
tam, kde chceme sledovat nového konce pole a nový začátek pole
a to, že znovu a znovu.
A jestli to, co jsme sledování jako na začátku a na konci vždy protínají,
pak jsme nenašli, a můžeme se vrátit false.
Tak jak to mám udělat, že? Každý, kdo má návrhy nebo kód pro mě vytáhnout?
[Student] Do smyčky while. Jo >>.
Budeš chtít udělat smyčku.
>> Měli jste kód, který jsem mohl vytáhnout, nebo co jsi chtěl navrhnout?
[Student] Myslím, že ano. >> Dobře. To dělá věci jednodušší. Jaké bylo vaše jméno?
[Student] Lucas.
Revize 1. Dobře.
Nejnižší je to, co jsme nazvali začít dříve.
Up není to, co jsme nazvali konec před.
Ve skutečnosti, konec je nyní v matici. Je to prvek, bychom měli zvážit.
Takže nízká je 0 až je velikost pole - 1,
a teď jsme smyčky, a my se kontrola -
Myslím, že můžete chodit přes něj.
Jaký byl váš myšlení přes to? Procházka nás prostřednictvím kódu.
[Student] Jasně. Podívejte se na haystack hodnotu ve středu a porovnat jej s jehlou.
Takže pokud je to větší než vaše jehly, pak budete chtít - oh, vlastně, že by měla být zpětně.
Budeš chtít vyhodit pravou polovinu, a tak jo, to by mělo být tak.
[Bowden] Tak by to mělo být méně? Je to to, co jsi řekl? >> [Student] Jo.
[Bowden] Dobře. Méně.
Takže pokud to, co se díváme na menší, než to, co chceme,
tak jo, chceme vyhodit levou polovinu,
což znamená, že se aktualizace vše Uvažujeme
Pohybem nízko na pravé straně pole.
To vypadá dobře.
Myslím, že to má stejný problém, který jsme si řekli na předchozí,
, kde v případě nízké je 0, a až je 1, potom nízký + až / 2 bude nastaven tak, aby se totéž znovu.
>> A i když to není tento případ, je ještě účinnější, přinejmenším
jen vyhodit prvek jsme právě podíval na kterém víme, že je v pořádku.
Tak nízká + nahoru / 2 + 1 - >> [Student] To by mělo být naopak.
[Bowden] Nebo by to mělo být - 1 a druhý by měl být + 1.
[Student] A by měl být dvojí rovnítko. >> [Bowden] Jo.
[Student] Jo.
Dobře.
A konečně, nyní, když máme tuto + 1-1 věc,
je to - to nemusí být - je to vůbec možné, nízká skončit s hodnotou vyšší než nahoru?
Myslím, že jediný způsob, jak se může stát - je to možné? >> [Student] Nevím.
Ale pokud to bude zkrácen a pak dostane minus 1 a potom - >> Jo.
[Student] To by možná si zpackal.
Myslím, že by to mělo být dobré jen proto, že
pro to, aby skončil nižší, budou muset být se rovnat, myslím.
Ale pokud jsou stejné, pak bychom udělali while začít s
a my jsme se vrátili hodnotu. Takže myslím, že jsme v pohodě teď.
Povšimněte si, že i když je tento problém již rekurzivní,
stejný druh myšlenek platí, kde můžeme vidět, jak to tak snadno propůjčuje
k rekurzivní řešení tím, že jsme jen aktualizuje indexy znovu a znovu,
děláme problém menší a menší, my se soustředíme na podmnožinu pole.
[Student] Při nízké je 0, a až je 1, by se oba 0 + 1/2, což by na 0,
a pak jeden by + 1, jeden by být - 1.
[Student] Kde jsme kontrolu rovnosti?
Jako v případě, že prostřední je vlastně jehla?
Nejsme v současné době dělá, že? Oh!
Pokud to -
Ano. Nemůžeme jen tak udělat test sem, protože řekněme, že první středu -
[Student] Je to vlastně jako nevyhazujte vázané.
Takže pokud máte vyhodit vázaná, budete muset zkontrolovat první nebo cokoliv.
Ah. Jo. >> [Student] Jo.
Takže teď jsme zahodil ten jsme v současné době se podíval na,
což znamená, že nyní musíme také mít
if (haystack [(low + up) / 2] == jehly), pak můžeme vrátit true.
A jestli jsem dal jinam, nebo jen v případě, to znamená doslova totéž
protože by se vrátili pravda.
Tak jsem si dal else if, ale to nevadí.
>> Takže ještě pokud to, jinak to, a to je běžná věc dělám
, kde i když je to v případě, kdy je vše dobré zde,
jako nízká, může být nikdy vyšší než nahoru, to nestojí za úvaha o tom, zda je to pravda.
Takže se může také říkat při nízké je menší než nebo roven
nebo při nízké je menší než
takže v případě, že jsou stále stejné, nebo nízká stane ujít,
pak můžeme vymanit z této smyčky.
Otázky, obavy, názory?
Dobře. To vypadá dobře.
Teď chceme udělat jakousi.
Pokud půjdeme do mé druhé revizi, vidíme tytéž čísla,
ale nyní jsou již v seřazeném pořadí.
A my chceme zavést jakousi pomocí jakýkoli algoritmus v O n log n.
Takže, které algoritmus si myslíte, že bychom měli zavést tady? >> [Student] Merge sort.
[Bowden] Jo. Sloučit sort je O (n log n), takže to je to, co budeme dělat.
A problém bude dost podobně,
kde se snadno půjčuje sebe k rekurzivní řešení.
Můžeme také přijít s iterativní řešení, pokud chceme,
ale rekurze bude jednodušší tady a měli bychom dělat rekurzi.
Myslím, že budeme procházet řadit sloučení první,
ačkoli tam je krásné video o řadit sloučení již. [Smích]
Takže sloučit druh existuje - Jsem plýtvání tolik této práce.
Oh, je tu jen jeden vlevo.
Tak sloučení.
Ó, 1, 3, 5.
Dobře.
Merge má dva samostatné pole.
Individuálně tyto dvě pole jsou oba seřazeny.
Takže toto pole, 1, 3, 5, seřazeny. Toto pole, 0, 2, 4, seřazeny.
Co teď sloučení měli udělat, je spojit je do jediného pole, která je sama seřazeny.
Takže chceme pole o velikosti 6, která se bude mít tyto prvky uvnitř něj
v seřazeném pořadí.
>> A tak můžeme využít k tomu, že tyto dva pole jsou seřazeny
k tomu v lineárním čase,
lineární čas význam v případě, že je velikost pole x, a to je velikost y,
pak celkový algoritmus by měl být O (x + y). Dobře.
Tak návrhy.
[Student] Mohli bychom začít zleva?
Takže budete dal 0 dolů a pak 1 a pak zde jste na 2.
Takže je to něco jako, že máte kartu, která se pohybuje doprava. >> [Bowden] Jo.
Pro oba z těchto polí, pokud se soustředit jen na krajním prvku.
Vzhledem k tomu, jak pole jsou seřazeny, víme, že tyto 2 prvky
jsou nejmenší prvky obou poli.
To znamená, že 1 z těchto 2 prvků musí být nejmenší prvek v naší sloučené pole.
To jen tak se stane, že nejmenší je jedno na pravé této doby.
Tak jsme se 0, vložte jej na levé straně, protože 0 je menší než 1,
takže si 0, vložte ji do naší první pozice, a pak jsme je aktualizuje
aby nyní soustředit na první prvek.
A teď jsme se opakovat.
Takže teď jsme tyto 2 a 1. 1 je menší, takže vložíme 1.
My aktualizovat tento ukazatel aby ukazoval na toho chlapa.
Nyní jsme to znovu, tak 2. To bude aktualizovat, porovnání těchto 2, 3.
Tato aktualizace, pak 4 a 5.
Tak to je sloučení.
>> Mělo by být naprosto jasné, že je lineární čas, protože jsme prostě jít přes každý prvek jednou.
A to je největší krok k realizaci sloučení řazení to dělá.
A to není tak těžké.
A pár věcí dělat starosti, je řekněme jsme sloučení 1, 2, 3, 4, 5, 6.
V tomto případě jsme skončili ve scénáři, kde tento člověk bude menší,
pak aktualizovat tento ukazatel, tohle bude menší, je aktualizuje,
tohle je menší, a teď budete muset uznat
když jste skutečně spustit z prvků, které mají v porovnání s.
Protože jsme již používali tento celého pole,
vše v tomto poli je nyní právě vložené do zde.
Takže pokud se někdy dostanete do bodu, kdy je jeden z našich polí zcela sloučeny již,
pak jen vzít všechny prvky druhé pole a vložit do konce pole.
Takže můžeme jen vložit 4, 5, 6. Dobře.
To je jedna věc, dávat si pozor na.
Prováděcí který by měl být krok 1.
Sloučit řadit pak na základě toho, že je to 2 kroky, 2 hloupé kroky.
Pojďme dát toto pole.
Takže sloučit druh, krok 1 je rekurzivně rozdělit pole na poloviny.
Takže rozdělit toto pole na poloviny.
V současné době máme 4, 15, 16, 50 a 8, 23, 42, 108.
A teď jsme to znovu a rozdělili jsme je do poloviny.
Já si jen to na této straně.
Takže 4, 15 a 16, 50.
Rádi bychom dělat stejnou věc znovu tady.
A teď jsme se rozdělili do poloviny znovu.
A máme 4, 15, 16, 50.
Tak to je náš základní scénář.
Jakmile pole jsou velikosti 1, pak přestat s rozdělením do poloviny.
>> Co teď budeme dělat s tím?
Jsme skončit to bude také rozdělit do 8, 23, 42, a 108.
Takže teď, že jsme v tomto bodě, nyní kroku dvě řadit sloučení je jen sloučení dvojice seznamů.
Takže chceme sloučit tyto. Právě jsme zavolat sloučení.
Víme, že sloučení se vrátit tyto v seřazeném pořadí.
4, 15.
Nyní chceme sloučit tyto, a že vrátí seznam s těmi v seřazeném pořadí,
16, 50..
Spojíme ty - Nemůžu psát - 8, 23 a 42, 108.
Takže máme sloučené dvojice jednou.
Teď už jen sloučit znovu.
Všimněte si, že každý z těchto seznamů je seřazena v sobě,
a pak můžeme jen sloučit tyto seznamy získat seznam velikosti 4, který je seřazena
a spojit tyto dva seznamy získat seznam velikosti 4, která je seřazena.
A konečně, můžeme sloučit tyto dva seznamy velikosti 4, aby si jeden seznam velikosti 8, která je seřazena.
Takže vidět, že je to celkově n log n, už jsme viděli, že sloučení je lineární,
takže když máme co do činění s sloučením tato, takže stejně jako celkové náklady na sloučení
těchto dvou seznamů je jen 2, protože -
Nebo dobře, je to O n, ale n je zde jen tyto 2 prvky, takže je to 2.
A tyto 2 bude 2 a tyto 2 bude 2 a tyto 2 bude 2,
takže přes všechny splývá, které musíme udělat, jsme se nakonec dělat n.
Jako 2 + 2 + 2 + 2 je 8, což je n,
takže náklady na sloučení v této sadě je n.
A pak to samé tady.
Budeme sloučení těchto 2, pak tyto 2, a osobně to sloučení bude trvat čtyři operace,
to sloučení bude trvat čtyři operace, ale opět, mezi všemi z nich,
jsme se nakonec slučování n celkem věci, a tak tento krok trvá n.
A tak každá úroveň má n prvků je sloučeny.
>> A kolik úrovní je tam?
Na každé úrovni, naše pole roste podle velikosti 2.
Zde naše pole jsou velikosti 1, zde jsou velikosti 2, zde jsou velikosti 4,
a konečně, jsou velikosti 8.
Takže, protože to je zdvojení, tam se bude celkem log n z těchto úrovní.
Takže s log n úrovní, každá jednotlivá úroveň přičemž n celkem operace,
dostaneme log n n algoritmus.
Otázky?
Lidé již dosáhla pokroku v tom, jak to provést co?
Je někdo již ve stavu, kdy jsem si jen vytáhnout svůj kód?
Můžu dát chvilku.
Tenhle bude delší.
Vřele doporučuji opakovat -
Nemusíte dělat rekurzi pro sloučení
protože dělat rekurzi pro sloučení, budete muset projít spoustu různých velikostí.
Můžete, ale je to otravné.
Ale rekurze pro řadit sám o sobě je docela snadné.
Stačí zavolat doslova jakousi na levé polovině, sort na pravé polovině. Dobře.
Každý, kdo má něco, co jsem si vytáhnout vzhůru?
Jinak já dám minutku.
Dobře.
Každý, kdo má něco, co můžeme pracovat s?
Jinak budeme jen s tímto pracujete a potom rozbalte odtamtud.
>> Každý, kdo má víc než to, že jsem si vytáhnout?
[Student] Jo. Můžete vytáhnout moje. >> Dobře.
Ano!
[Student] Byla tam spousta podmínek. >> Oh, střílet. Můžeš -
[Student] Musím zachránit ji. Jo >>.
Tak jsme udělali to sloučení odděleně.
Oh, ale to není tak špatné.
Dobře.
Takže druh je sám o sobě jen volání mergeSortHelp.
Vysvětlete nám, co mergeSortHelp dělá.
[Student] MergeSortHelp docela hodně dělá dva hlavní kroky,
který je vyřešit každou polovinu pole a pak sloučit oba.
[Bowden] Dobře, tak mi za sekundu.
Myslím, že to - >> [Student] musím -
Jo. Jsem něco chybí.
V sloučení, jsem si uvědomil, že musím vytvořit nové pole
protože jsem nemohl udělat to na místě. Ano >>. Nemůžete. Opravit.
[Student] Tak jsem vytvořit nové pole.
Zapomněl na konci se ponoří znovu změnit.
Dobře. Potřebujeme nové pole.
V řadit slučovací, je to téměř vždy pravda.
Část nákladů na lepší algoritmu časově
je téměř vždy museli použít trochu více paměti.
Tak tady, bez ohledu na to, jak to děláš sloučit druh,
budete nevyhnutelně potřebovat nějaké extra paměť.
On nebo ona vytvořila nové pole.
A pak řekneš na konci jsme stačí zkopírovat nové pole do původního pole.
[Student] Myslím, že ano, jo.
Nevím, jestli to funguje, pokud jde o počítání odkazu nebo cokoliv jiného -
Jo, bude to fungovat. >> [Student] Dobře.
Bylo pro vás zkuste to? >> [Student] Ne, ještě ne. Dobře >>.
Zkuste ji spustit, a pak budu mluvit o tom na chvíli.
[Student] Musím mít všechny funkční prototypy a všechno, že jo?
Funkční prototypy. Oh, myslíš jako - Ano.
Seřadit volá mergeSortHelp.
>> Tak, aby pro řazení volat mergeSortHelp, musí mergeSortHelp buď byly definovány
před řadit nebo si jen potřebujete prototyp. Stačí jen zkopírovat a vložit, že.
A podobně, mergeSortHelp volá sloučení,
ale merge není dosud definováno, takže se můžeme jen nechat mergeSortHelp vědět
že to, co sloučení bude vypadat, a tím to hasne.
Tak mergeSortHelp.
Máme problém, tady, kde nemáme základní věc.
MergeSortHelp je rekurzivní, takže každý rekurzivní funkce
bude potřebovat nějaký základní věci vědět, kdy přestat rekurzivně volat sám.
Co je náš základní scénář bude tady? Jo.
[Student] Pokud je velikost 1? >> [Bowden] Ano.
Tak jako jsme viděli tady, zastavili jsme se rozdělení pole
Jakmile jsme se dostali do polí velikosti 1, což nevyhnutelně jsou seřazeny sami.
Takže pokud velikost odpovídá 1, víme, že pole je již řazeno,
takže můžeme jen vrátit.
>> Všimněte si, že je neplatné, a tak jsme se nevrací nic konkrétního, jen jsme se vrátit.
Dobře. Tak to je náš základní scénář.
Myslím, že náš základní scénář by také mohla být, kdybychom se náhodou sloučení pole o velikosti 0,
jsme asi chtějí zastavit na nějakém místě,
takže stačí říci velikosti menší než 2 nebo nižší než nebo rovna 1
tak, že to bude fungovat za každé pole se.
Dobře.
Tak to je náš základní scénář.
Teď už chcete chodit nás přes sloučení?
Co všechny tyto případy znamenají?
Až tady, my jsme jen dělá stejnou myšlenku, -
[Student] musím být kolem velikosti se všemi hovory mergeSortHelp.
Přidal jsem velikost jako další primární a není to tam, jako je velikost / 2.
[Bowden] Oh, velikost / 2, velikost / 2. >> [Student] Jo, a také ve výše uvedeném funkci.
[Bowden] Tady? >> [Student] Jen velikost. >> [Bowden] Oh. Velikost, velikost? >> [Student] Jo.
[Bowden] Dobře.
Nechte mě přemýšlet o vteřinu.
Líbí narazíme na problém?
Jsme vždy zacházet levici jako 0. >> [Student] č.
To je špatně taky. Promiňte. Mělo by to být začátek. Jo.
[Bowden] Dobře. Líbí se mi, že lépe.
A konec. Dobře.
Takže teď chceš projít nám prostřednictvím sloučení? >> [Student] Dobře.
Jen jsem procházel tohoto nového pole, které jsem vytvořil.
Jeho velikost je velikost části pole, které chceme třídit
a snaží se najít prvek, který bych měl dát v novém pole kroku.
Takže k tomu, že v první jsem ověřit, jestli je levá polovina pole i nadále mít žádné další prvky,
a pokud tomu tak není, pak jít dolů k tomuto jinému stavu, který právě říká, že
v pořádku, musí být v pravém poli, a dáme, že v současné indexu newArray.
>> A pak jinak, já jsem ověřit, jestli je pravá strana pole je také skončil,
v takovém případě jsem dal v levé.
To by mohlo být skutečně nutné. Nejsem si jistý.
Ale stejně, další dva kontrola, kterou z těch dvou se menší doleva nebo doprava.
A také v každém případě, já navýšením podle toho, co zástupný I zvyšovat.
[Bowden] Dobře.
To vypadá dobře.
Má někdo nějaké připomínky nebo obavy nebo otázky?
Takže čtyři případy, které musíme přivést věci do pouhého bytí - nebo to vypadá jako pět -
ale musíme zvážit, zda doleva pole je vyčerpat co musíme sloučit,
zda právo pole je vyčerpat co musíme sloučit -
Jsem ukázal na nic.
Takže ať levé pole došla věci nebo právo pole došel věcí.
To jsou dva případy.
Potřebujeme také triviální případ, zda levice, co je menší než správnou věc.
Pak chceme zvolit levé věc.
To jsou případy.
Tak tohle měl pravdu, tak je to.
Array vlevo. Je to 1, 2, 3. Dobře. Tak jo, to jsou čtyři věci, které jsme mohli chtít dělat.
A nebudeme jít přes iterační řešení.
Nedoporučoval bych -
Sloučení druh je příklad funkce, která je jak to ocas rekurzivní,
to není snadné, aby se to tail rekurzivní,
ale také to není snadné, aby se to iterativní.
To je velmi snadné.
Tato implementace druhu korespondence,
sloučení, bez ohledu na to, co děláte, budete stavět sloučení.
>> Takže sloučit druh postaven na vrcholu sloučení rekurzivně je právě tato tři řádky.
Iterativně, je to více nepříjemné a těžké přemýšlet o.
Ale všimněte si, že to není ocas rekurzivní, protože mergeSortHelp - když to sama říká -
stále musí dělat věci po tomto rekurzivních volání vrátí.
Takže to stack frame musí nadále existovat i po volání této.
A pak, když budete volat, musí stack frame nadále existovat
protože i po tomto hovoru, stále potřebujeme sloučit.
A to je triviální, aby se tento ocas rekurzivní.
Otázky?
Dobrá.
Takže návrat k řazení - oh, jsou dvě věci, které chci ukázat. Dobře.
Vraťme se zpět k druhu, uděláme to rychle.
Nebo hledejte. Řadit? Seřadit. Jo.
Vraťme se zpět do začátků druhu.
Chceme vytvořit algoritmus, který třídí pole pomocí libovolného algoritmu
v O n.
Tak, jak je to možné? Má někdo nějaký druh -
Jsem naznačil dříve u -
Pokud se chystáme zlepšení z n log n na O n,
jsme zlepšili naše algoritmus časově,
což znamená, že to, co budeme muset udělat, aby se na to?
[Student] Space. Jo >>. Budeme používat více prostoru.
A to i jen více prostoru, je to exponenciálně více prostoru.
Takže si myslím, tento typ algoritmu je pseudo něco, pseudo polynomů -
pseudo - Nemůžu si vzpomenout. Pseudo něco.
Ale je to proto, že musíme použít tolik prostoru
že toho lze dosáhnout, ale není reálné.
>> A jak můžeme dosáhnout?
Toho můžeme dosáhnout, pokud se zaručí, že určitá element v poli
pod určitou velikost.
Takže řekněme, že velikost je 200,
jakýkoliv prvek v poli je nižší než velikost 200.
A to je skutečně velmi realistický.
Můžete velmi snadno mít pole, které víte, že vše, co v něm
bude menší než nějaké číslo.
Jako když mám nějaký naprosto masivní vektor, nebo tak něco
ale víte, všechno bude mezi 0 a 5,
pak to bude výrazně rychlejší udělat.
A vázané na některý z prvků je 5,
tak tento odhad, že je to, jak moc paměti budete používat.
Takže vázaný je 200.
Teoreticky je vždy vázaný od celé číslo může být až 4000000000,
ale to je nereálné, protože pak bychom používat místo
na pořadí 4000000000. Tak to je nereálné.
Ale tady budeme říkat naše vázaný je 200.
Trik dělat to v O n je uděláme další pole s názvem počty velikosti VÁZÁNI.
Takže vlastně, to je zkratka pro - Já vlastně nevím, jestli zvonění to dělá.
Ale v GCC na přinejmenším - Jsem za předpokladu, že zvonění to dělá taky -
to bude jen inicializaci celého pole, aby se 0s.
Takže pokud nechci dělat, pak bych mohl samostatně udělat for (int i = 0;
i <BOUND; i + +) a počítá [i] = 0;
Takže teď je vše inicializována na 0.
I iteraci své pole,
a to, co dělám, je počítám počet každého - Pojďme sem.
Máme 4, 15, 16, 50, 8, 23, 42, 108.
Co Počítám je počet výskytů každého z těchto prvků.
Pojďme skutečně přidat pár dalších tady s některými opakování.
Takže hodnota, kterou máme, je hodnota, která bude pole [i].
Takže val by mohl být 4 nebo 8 nebo cokoliv jiného.
A teď jsem počítat, kolik z této hodnoty jsem viděl,
takže se počítá [val] + +;
Po to provést, počítá se bude vypadat jako 0001.
Pojďme udělat počítá [val] - ŘÍDIT + 1.
>> Teď to je jen odpovídat za to, že jsme počínaje 0.
Takže pokud 200 bude naše největší číslo,
pak 0-200 je 201 věcí.
Takže se počítá, bude to vypadat, jako 00001, protože máme jeden 4.
Pak budeme mít 0001, kde budeme mít 1 v 8. indexu počtu.
Budeme mít 2 v 23. indexu počtu.
Budeme mít 2 v indexu 42. počtu.
Takže můžeme použít počet.
Takže num_of_item = počítá [i].
A pokud num_of_item je 2, to znamená, že chceme vložit 2 z počtu i
do našeho tříděném poli.
Takže musíme sledovat, jak daleko jsme se do pole.
Takže index = 0.
Array - budu jen psát.
Počty -
array [index + +] = i;
Je to to, co chci? Myslím, že je to to, co chci.
Ano, to vypadá dobře. Dobře.
Takže si všichni pochopili, co je cílem mé počítá pole je?
To počítá počet výskytů každého z těchto čísel.
Pak jsem iterace, která se počítá pole,
a tá pozice v poli se počítá
je počet i to, že by se měl objevit v mém tříděném poli.
To je důvod, proč se počty 4 bude 1
a počty 8 bude 1, počty 23 bude 2.
Tak to je, kolik z nich chci vložit do mého tříděném poli.
Pak jsem to.
Jsem vložení num_of_item i to do mého tříděném poli.
>> Otázky?
A tak opět, je to lineární čas, protože jsme se právě iterace přes to jednou,
ale je to také lineární v tom, co toto číslo se stane být,
a tak to silně závisí na tom, co je vázán.
S vázaný na 200, to není tak špatné.
Pokud váš vázaný bude 10.000, pak je to trochu horší,
ale pokud vaše spojený se bude 4000000000, to je naprosto nereálné
a toto pole bude muset být velikosti 4 miliardy korun, což je nereálné.
Tak to je to. Otázky?
[Neslyšitelné Student odpověď] >> Dobře.
Uvědomil jsem si, jednu věc, když jsme šli přes.
Myslím, že problém byl v Lucasovi a pravděpodobně jeden každý jsme viděli.
Úplně jsem zapomněla.
Jediné, co jsem chtěl vyjádřit, je, že když máte co do činění s věcmi, jako je indexů,
nikdy opravdu vidět, když píšete pro smyčce,
ale technicky, když máte co do činění s těmito indexy,
měli byste skoro vždy řešit s celých čísel bez znaménka.
Důvodem pro to je, když máte co do činění s podepsanými celá čísla,
takže pokud máte 2 podepsané celá čísla a přidejte je spolu
a oni skončí příliš velké, pak vy skončíte s záporné číslo.
Takže to je to, co integer overflow je.
>> Pokud mohu přidat 2000000000 a 1000000000, jsem skončit s negativním 1000000000.
To je, jak celá čísla pracovat na počítačích.
Takže problém s použitím -
To je v pořádku s výjimkou případů nízká stane být 2 miliardy až se stane na 1 mld. Kč,
pak bude negativní 1 miliarda a pak budeme dělit, že 2
a skončit s negativním 500000000.
Tak tohle je jen problém, pokud se stalo, že se hledá přes pole
miliard věcí.
Ale pokud low + až se stane přetečení, pak je to problém.
Jakmile jsme, aby byly nesignováno, pak 2 miliard eur 1000000000 je 3 mld. Kč.
3000000000 děleno 2 je 1,5 mld. Kč.
Takže jakmile to unsigned, všechno je perfektní.
A tak to také problém, když jste psaní pro smyčky,
a vlastně, to asi dělá to automaticky.
To bude vlastně jen křičet na vás.
Takže pokud toto číslo je příliš velký, aby se během jediné celé číslo, ale to by se vešly do celé číslo bez znaménka,
bude křičet na tebe, tak to je důvod, proč jste nikdy narazit na problém.
Můžete vidět, že index je nikdy nebude negativní,
a tak, když jste iterace přes pole,
můžete téměř vždy říci, unsigned int i, ale nemáte opravdu muset.
Věci jdou do práce skoro stejně dobře.
Dobře. [Šeptá] Jaký je čas?
Poslední věc, kterou jsem chtěl ukázat - a já to prostě udělat to opravdu rychle.
Víš, jak jsme # define, takže můžeme # define MAX jako 5 nebo tak něco?
Pojďme to udělat MAX. # Define vázán jako 200. To je to, co jsme dělali před.
To definuje konstantu, která je jen tak zkopírovat a vložit
všude tam, kde se stalo psát VÁZÁNI.
>> Takže můžeme skutečně udělat více s # definuje.
Můžeme # define funkce.
Jsou to opravdu funguje, ale budeme jim říkat funkce.
Příkladem by mohl být něco jako MAX (x, y) je definována jako (x <y y:? X). Dobře.
Takže byste měli zvyknout na syntaxi ternární operátor,
ale je x menší než y? Návrat y, jinak vrátí x.
Takže můžete vidět, můžete tuto samostatnou funkci,
a funkce může být jako bool MAX trvá 2 argumenty, vrátit.
To je jeden z nejčastějších z nich vidím udělal takhle. Říkáme jim makra.
To je makro.
To je jen syntaxe pro něj.
Můžete napsat makro dělat, co chcete.
Ty často vidět makra pro ladění printfs a tak.
Takže typu printf, existují speciální konstanty v C jako podtržení LINE podtržítko,
2 podtrhuje LINE podtržítko,
a tam je také myslím, že 2 podtržítka FUNC. To by mohlo být ono. Něco takového.
Tyto věci budou nahrazeny s názvem funkce
nebo číslo linky, které jste na.
Často, můžete napsat ladění printfs, že tady dole jsem mohl pak jen napsat
DEBUG a vytiskne se číslo řádku a funkce, které jsem náhodou být v
že došlo, že DEBUG prohlášení.
A můžete také vytisknout jiné věci.
Takže jedna věc, kterou by měl dávat pozor, je, jestli jsem náhodou # define DOUBLE_MAX
něco jako 2 * y a 2 * x.
Takže z jakéhokoliv důvodu, jste náhodou k tomu, že hodně.
Tak, aby to makro.
To je skutečně zlomené.
Nazval bych to tím, že dělá něco jako DOUBLE_MAX (3, 6).
Takže to, co by měla být vrácena?
[Student] 12.
Ano, měla 12 být vráceny, a 12 je vrácena.
3 bude nahrazeno za x, dostane 6 nahrazuje pro y, a vracíme se 2 * 6, která je 12.
Teď co tohle? Co by se mělo vrátit?
[Student] 14. V ideálním případě >>, 14.
Problém je, že jak hash definuje práci, pamatujte, že je to doslovný kopírování a vkládání
ze dne skoro všechno, takže to, co to bude vykládat jako
je 3 méně než 1 plus 6, 2 krát 1 plus 6, 2 krát 3.
>> Takže z tohoto důvodu téměř vždy zabalit vše v závorkách.
Jakákoli proměnná téměř vždy zabalit v závorkách.
Existují případy, kdy nemáte k, jako já vím, že nemám potřebu k tomu, že zde
protože méně, než je do značné míry vždy jen chodit do práce,
i když to nemusí být dokonce pravda.
Pokud je něco směšné jako DOUBLE_MAX (1 == 2),
pak, že se to být nahrazen s 3 méně než 1 rovná rovná 2,
a tak pak to bude dělat 3 méně než 1, to, že rovné 2,
což je to, co chceme.
Tak, aby se zabránilo operátor přednost problémy,
vždy zabalte v závorkách.
Dobře. A to je to, 5:30.
Máte-li jakékoli dotazy týkající se PSet, dejte nám vědět.
To by měla být zábava, a hacker vydání je také mnohem realističtější
než hackerské vydání v loňském roce, tak doufáme, že spousta z vás to zkusit.
V loňském roce to byl velmi zdrcující.
>> [CS50.TV]