>> 1. Előadó: Rendben, tehát ez CS50 Ez a hét végén öt.
És emlékszem, hogy utoljára nekilátott a galambász adatok
struktúrák indult, hogy megoldja problémákat, hogy kezdte el bevezetni
új problémák, de a legfontosabb, hogy ezt az a fajta threading, hogy mi
kezdett hozzá csomópontok.
Szóval ez persze egyszeresen láncolt lista.
És egyszeres kapcsolódik, Úgy értem, nem csak egy
menet között minden egyes ilyen csomópontok.
Kiderült, amit tehetünk cifrább dolgok, mint kétszeresen láncolt listák
ahol van egy nyíl mindkét irányban, amely
segíthet bizonyos hatékonyságot.
De ez megoldotta a problémát?
Mi a gond viszont ezt megoldani?
Miért érdekel hétfőn?
Miért, elvileg, nem törődünk hétfőn?
Mit csinal?
>> Közönség: Mi lehet dinamikusan méretét.
>> 1. Előadó: OK, így tudjuk dinamikusan méretét.
Jól sikerült mind a ketten.
Szóval lehet dinamikusan átméretezni ezt adatszerkezet, mivel egy sor,
Emlékezzünk, tudnod kell a priori, hogy mennyi helyet szeretne
és ha kell még egy kis helyet, te ilyen szerencséje.
Létre kell hozni egy teljesen új tömb.
Meg kell mozgatni az összes az adatokat az egyik a másikra,
végül szabad a régi tömb ha tudsz, majd folytassa.
Ami csak úgy érzi, nagyon költséges és nagyon nem hatékony, és valóban az is.
De ez még nem minden jó.
Mi árat fizetnek, mi volt az egyik a nyilvánvaló árak is
fizetni egy láncolt lista?
>> Közönség: Meg kell használni dupla helyet mindegyik.
1. Előadó: Igen, így van szükségünk legalább kétszer annyi helyet.
Sőt, rájöttem, hogy ez kép még egy kicsit félrevezető,
mert a CS50 IDE a sok modern számítógépek, egy mutatót vagy címet
valójában nem négy bájt.
Nagyon gyakran ezek nap nyolc bájt, amely
: a legalsó téglalapok ott a valóságban
a fajta kétszer akkora, mint amit én kiállított,
ami azt jelenti, amit használ háromszor sok helyet, mint talán van más módon.
Most ugyanabban az időben, vagyunk Még mindig beszél bájt, ugye?
Mi nem feltétlenül beszél megabájt vagy gigabájt,
kivéve, ha ezek az adatok struktúrák kap nagy.
>> És így ma elkezdjük vizsgálni hogyan lehet felfedezni adatok
hatékonyabban, ha a Valójában az adatok nagyobb lesz.
De nézzük meg, hogy canonicalize A műveletek első
hogy meg tudod csinálni a következő típusú adatok struktúrákat.
Szóval olyasmi, mint egy kapcsolt lista általában támogatja
műveletek, mint a törlés, helyezze, és keresni.
És mit jelent az, hogy?
Ez csak azt jelenti, hogy általában, ha az emberek a láncolt lista,
ők vagy valaki más által végrehajtott funkciók, mint a törlés, betét,
és a keresés, így Ön valóban tenni valamit
hasznos az adatszerkezet.
Szóval vessünk egy gyors pillantást meg, hogyan lehet végrehajtani
Néhány kódot egy láncolt lista a következőképpen.
>> Szóval ez csak néhány a C kód, Nem is egy komplett program
hogy igazán gyorsan felkorbácsolta.
Ez nem online forgalmazás kódot, mert nem a ténylegesen megtett.
De észre Épp most egy megjegyzést mondta,
dot dot dot, van valami ott, pont pont pont, ott valami.
És nézzük csak nézd meg mi a szaftos részek.
Tehát a sorban három, Emlékeztetünk arra, hogy ez most
Javasoltuk nyilvánító csomópont utolsó ideje, az egyik ilyen téglalap alakú tárgyat.
Meg van egy int, hogy fogjuk hívni N, de nevezhetjük bárminek,
majd a struct csomópont csillagos nevezett következő.
És csak hogy tisztázzuk, hogy a második vonal, a soros hathengeres, mi ez?
Mit tesz nekünk?
Mert úgy néz ki több rejtélyes, mint a szokásos változók.
>> Közönség: Azt teszi, hogy mozogni több mint egy.
>> 1. Előadó: Azt teszi, hogy mozogni több mint egy.
És pontosabban, akkor tárolja a címét
A csomópont, amely azt jelentette, hogy szemantikailag mellette, igaz?
Szóval ez nem fog feltétlenül mozognak semmit.
Ez csak fog értéket tárolnak, amely
lesz a cím néhány más csomópont,
és ezért mondtunk struct node csillag, a csillag jelöli
egy mutató, vagy egy címet.
OK, így most, ha feltételezzük, hogy van Ebben az N elérhető számunkra, és nézzük
Feltételezem, hogy valaki másnak beilleszteni egy csomó egészek
egy láncolt lista.
És hogy kapcsolódik lista Rámutatott, hogy néhány ponton
változó nevű lista, amelyet telt itt, mint a paraméter,
hogyan megy a vonalon 14 végrehajtási keresés?
Más szóval, ha én végrehajtási függvény, amelynek célja az életben
az, hogy egy int, majd a elején egy láncolt lista,
hogy egy mutató a láncolt lista.
Mint az első, aki azt hiszem, David volt önkéntesünk hétfőn,
ő mutat Az egész láncolt lista,
olyan, mintha mi halad Dávid az érveink itt.
Hogyan érjük el áthaladó ez a lista?
Nos, kiderült, hogy bár mutatók viszonylag új most nekünk,
ezt meg tudjuk tenni, viszonylag egyenesen.
>> Megyek megy előre, és Kijelentem, ideiglenes változó,
egyezményesen csak megy hogy hívják mutató vagy PTR,
de lehet nevezni, amit akarsz.
És fogok alaphelyzetbe azt a kezdetét a lista.
Szóval lehet egyfajta gondolom, ennek a mint én a tanár a minap,
fajta mutatva valaki körében emberek önkéntesként.
Szóval egy átmeneti változó, ami Csak mutatva ugyanezt
hogy a véletlenül nevezték önkéntes Dávid is rámutatva.
Most, miközben mutató nem nulla, mert visszahívás
hogy null valamilyen különleges sentinel értéke A behatároló a lista végén,
így amíg nem vagyok mutatva földön, mint az utolsó önkéntes
volt, menjünk előre és tegye a következőket.
Ha pointer-- és most valahogy akarnak hogy amit tettünk a diák
structure-- ha a mutató melletti pont equals-- inkább, ha a mutató dot N egyenlő
egyenlő az n változó, a érv, hogy a már elfogadott,
akkor azt akarom, hogy menjen előre és azt mondják vissza igaz.
Találtam száma N belsejét egyik csomópont én láncolt lista.
De a dot már nem működik ebben az összefüggésben,
mert mutatót, PTR, van Valóban egy mutató, cím,
mi valójában is csodálatosan Használja végül egy darab szintaxis
ez a fajta gyártmányú ösztönösen érzi, és ténylegesen
Használja a nyíl itt, ami azt jelenti, megy ezt a címet az egész, ott.
Tehát ez nagyon hasonlít a szellem a dot-üzemeltető,
hanem azért, mert a mutató nem egy pointer és nem a tényleges struct magát,
csak használja a nyíl.
>> Tehát, ha az aktuális csomópont, hogy én, az ideiglenes változó, am mutatva
nem N, mit akarok csinálni?
Nos, az én emberi önkéntesek hogy mi volt itt a minap,
Ha az első emberi nem az általam szeretnénk, és talán a második ember nem
Az egyik azt akarom, és a harmadik, én kell tartani fizikai mozgatása.
Mint hogyan lépek a listában?
Amikor volt egy tömb, csak tettem, mintha én plus plus.
De ebben az esetben elegendő, ha nem mutató, kap, mutató, a következő.
Más szóval, a következő mező olyan, mint minden a bal kezében
hogy emberi önkéntesek hétfőn -a használta, hogy rámutasson néhány más csomóponton.
Ezek voltak azok a következő szomszédok.
>> Tehát, ha azt akarom, hogy menj végig a listán, Nem tudok csak tudom plus plus többé,
Azt kell, hogy mondjam helyett Azt, mutató, folyik
hogy egyenlő függetlenül a következő mező, A következő mező, a következő mező,
következő mindazoknak bal keze hogy mi volt a színpadon mutatóeszköz
Egyes későbbi értékeket.
És ha én átjutni hogy egész iterációnál
és végül, elütöttem null nem rendelkező megtalált N mégis, én csak vissza hamis.
Szóval megint minden, amit mi csinálunk itt, mint egy a kép egy perce
kezd mutatva a a lista elején feltehetően.
És akkor ellenőrizze, ez az érték Keresem egyenlő kilenc?
Ha igen, azt vissza igaz, és kész vagyok.
Ha nem, akkor frissítem a kezem, AKA mutatót, hogy pont
A következő nyíl helyét, és akkor a következő nyíl helyét,
és a következő.
Én egyszerűen csak séta ezt a tömböt.
>> Tehát újra, kit érdekel?
Mint mi ez az összetevő,?
Nos, emlékszem, hogy mi vezetett fogalmának egy halom, amely
egy absztrakt adattípus, amennyiben ez nem egy C dolog, hogy ez nem egy CS50 dolog,
ez egy elvont elképzelés, ez az ötlet egymásra dolgokat egymás tetejére
hogy lehet végrehajtani fürtök különböző módon.
És egy út javasoltuk volt egy tömb, vagy egy láncolt lista.
És kiderül, hogy kanonikusan, a verem támogatja legalább két művelet.
És a buzz szavak push, hogy nyomja valami a verembe,
mint egy új tálcát a étkezőben, vagy a pop,
ami azt jelenti, hogy távolítsa el a legfelső tálcát a verem az étkezőben
hall, majd talán néhány Más műveletek is.
Tehát hogyan tudnánk szerkezetét meghatározó hogy mi most hív egy köteg?
>> Nos, mindannyian a szükséges szintaxis a rendelkezésünkre a C. mondom,
adj egy típus meghatározása Egy struct belsejében egy köteg,
Azt fogom mondani egy tömb, egy csomó szám, majd méretét.
Más szóval, ha azt akarom, végrehajtani ezt a kódot,
hadd menjen, és csak ilyen felhívni, hogy ez mit mond.
Tehát ez azt mondja, hogy nekem egy szerkezet, van egy tömbben,
és én nem tudom, mi kapacitása, ez nyilván valami állandó, hogy én már
máshol definiált, és ez jó.
De tegyük fel, hogy csak egy, két, három, négy, öt.
Tehát kapacitása 5.
Ez az elem belső én struktúrát kell hívott számokat.
És akkor kell egy egyéb változó láthatóan
nevű méretű, hogy kezdetben megyek kikötni nullára inicializálunk.
Ha nincs semmi a verem, mérete nulla,
és ez szemét értékeket számokban.
Fogalmam sincs, hogy mi van benne, csak még.
>> Tehát ha azt szeretné, hogy álljon valamit a verembe,
hiszem, hívja a funkciót push, és Mondom tolja 50, mint a 50-,
ahol javasolna Én felhívni, hogy ebben a tömbben?
Van öt különböző lehetséges válaszok.
Hol szeretné, hogy álljon a szám 50?
Ha a cél itt, újra, hívja a funkciót push, át egy érvet
50, hová tegyem meg?
Öt possible-- 20% -os valószínűséggel találgatás helyesen.
Igen?
>> Közönség: szélsőjobb.
>> 1. Előadó: szélsőjobb.
Van most egy 25% esélye találgatás helyesen.
Tehát, hogy valójában minden rendben lesz.
Megegyezés alapján, azt mondom egy sor, mi lenne általában kezdeni a bal,
de minden bizonnyal kezdeni a megfelelő.
Tehát a spoiler itt lenne vagyok valószínűleg fog rajzolni a bal oldalon,
Csak úgy, mint egy normális tömb, ahol Én indulj balról jobbra.
De ha a flip számtani, finom.
Ez egyszerűen nem hagyományos.
OK, azt kell, hogy egy További változás mégis.
Most, hogy már tolta valamit a verembe, mi a következő lépés?
>> Rendben, azt kell növelni a méretét.
Szóval hadd menjen előre, és csak frissíteni ezt, ami nulla volt.
És ahelyett, hogy most, megyek hogy hozzanak értéke egy.
És most tegyük fel, megnyomom a másik szám a verembe, mint a 51.
Nos, azt kell, hogy még egy változás, amely legfeljebb akkora, kettő.
És akkor hiszem tolja még egy szám a verembe, mint 61,
most kell frissíteni a méret még egy ideje, és kap az érték 3, mint a méret.
És most tegyük fel, hívom a pop.
Most pop, megállapodás szerint, nem veszi érv.
A verem, az egész pont a tálca metafora
az, hogy nincs mérlegelési jogköre menni fog, hogy tálcán, minden, amit tehetünk
a pop a legfelső egyet a verem, csak azért, mert.
Ez az, amit ez az adat struktúrára.
>> Tehát, hogy a logika, ha mondjuk pop, mi jön ki?
Tehát 61.
Szóval mi tényleg a számítógép fog tenni a memóriában?
Mit jelent a kódot kell csinálni?
Mit javasolna megváltoztatjuk a képernyőn?
Mit kell változtatni?
Bocsánat?
Így megszabadulunk 61.
Szóval tudom biztosan csinálni.
És tudok megszabadulni a 61.
És akkor mi más változás kell történnie?
Méret valószínűleg visszamenni kettő.
És így ez rendben van.
De várj egy percet, méret Egy perccel ezelőtt volt, három.
Nézzük csak egy gyors józanság csekket.
Honnan tudjuk, hogy akart megszabadulni a 61?
Mert mi popping.
És így van ez a második ingatlan alapterülete.
>> Várj egy percet, én vagyok gondoltam vissza a héten két
amikor elkezdtünk beszélni tömbök, ahol ez volt helye nulla,
ez volt az egyik helyen, ez volt helye két, ez helyen három, négy,
úgy néz ki, mint a közötti kapcsolat méret
és az elem, hogy szeretnék eltávolítani A tömb tűnik, hogy csak legyen mit?
Méret mínusz egy.
És ez az, hogyan, mint az emberek Tudjuk 61 az első.
Hogy a számítógép fog tudni?
Amikor a kódot, ahol valószínűleg akarok mérete mínusz egy,
így három mínusz egy két, és hogy a azt jelenti, hogy szeretne megszabadulni a 61.
És akkor valóban frissítheti A méretet úgy, hogy mérete most
megy háromról csak két.
És csak azért, pedáns, megyek azt javasolni, hogy kész vagyok, ugye?
Akkor javasolt ösztönösen helyesen kéne megszabadulni 61.
De nincs Valahogy fajta ütött megszabadulni 61?
Már elfelejtkeznek hogy ez valóban létezik.
És hiszem, vissza PSET4, ha elolvastátok A cikket a kriminalisztika, a PDF-
hogy mi volt a srácok olvasni, vagy fogja olvasni ezen a héten PSET4.
Emlékezzünk vissza, hogy ez valójában valaminek megfelelő Az egész ötlet a számítógép kriminalisztika.
Mi a számítógép általában nem az, ez csak elfelejti, hol valami,
de ez nem megy, és hasonlók próbáljuk megkarcolni ki vagy felülírás
ezeket a biteket a nullák és egyesek vagy valamilyen más, véletlenszerű mintát
hacsak te magad erre tudatosan.
Tehát az intuíció volt Rendben, hogy megszabaduljunk a 61.
De a valóságban, nem kell bajlódnia.
Csak meg kell elfelejteni, hogy hogy ott van megváltoztatásával méretét.
>> Most van egy probléma ezzel verem.
Ha tovább nyomja a dolgokat a verembe, mi
Nyilvánvalóan fog történni mindössze néhány pillanat az időben?
Fogunk elfogy a hely.
És mit tegyünk?
Mi vagyunk a fajta csavarni.
Ez a megvalósítás nem hagyja nekünk átméretezni a tömb, mert segítségével
ezt a szintaxist, ha gondoljon vissza a heti két,
ha egyszer már kijelentette, A tömb méretét,
nem láttunk olyan mechanizmust még, ahol meg lehet változtatni a méret a tömb.
És valóban C nem ezt a funkciót.
Ha azt mondod, hogy nekem öt Nths, hívja őket számokat,
Ez minden, amit akarsz kapni.
Tehát mi most, mint a hétfő, van a képessége, hogy kifejezze a megoldás
Bár, már csak be kell csípés meghatározása a verem
hogy nem lehet néhány kódolt tömb, de csak tárolni egy címet.
>> Most miért van ez?
Most már csak azt kell kényelmes, Az a tény, hogy amikor a program fut,
Én valószínűleg fog Meg kell kérdeznem az emberi,
hány számot akarsz tárolni?
Tehát a bemenő kell jönnie valahonnan.
De ha már tudjuk, hogy szám, akkor én is csak
Használja milyen funkciót adni nekem egy darab memória?
Tudom használni malloc.
És elmondhatom, bármennyi bájt akarom vissza ezekre Nths.
És azt kell tárolni a számok változó itt belül ez a struktúra
kell, hogy mit?
Hogy valójában mi megy a szám ebben a forgatókönyvben?
Igen, egy mutatót az első byte, hogy darab memória,
vagy még pontosabban, a cím Az első ilyen bájt.
Nem számít, ha ez az egyik bájt vagy egy milliárd byte-,
Csak kell törődnünk az első.
Mert amit malloc garanciák és az operációs rendszer garantálja,
az, hogy a darab a memória I kap, akkor lesz egybefüggő.
Ott nem lesz hiányos.
Tehát, ha kértem 50 bájt vagy 1000 byte,
ezek mind lesz vissza háttal.
És mindaddig, amíg emlékszem, milyen nagy, milyen sokat kértem, csak annyit kell tudni,
az első ilyen címet.
>> Tehát most már képes a kódot.
Jóllehet, ez fog minket Több időm írni ezt fel,
tudnánk teremteni átcsoportosítása, hogy az emlékezet által Csak tárolása eltérő címre van
ha azt akarjuk, egy nagyobb, vagy akár egy kisebb darab memória.
Tehát itt egy kompromisszum.
Most, hogy a dinamizmus.
Még mindig van contiguousness Én azt állítva.
Mivel malloc ad nekünk egy folytonos darabkája memória.
De ez lesz a fájdalom A nyak számunkra, a programozó,
hogy ténylegesen kódot fel.
Ez csak több munkát.
Szükségünk van-kód hasonlít ahhoz, amit én dörömböl ki csak egy pillanattal ezelőtt.
Nagyon megvalósítható, de hozzáteszi, komplexitás.
És így fejlesztő időt, programozó ideje egy újabb erőforrás
hogy mi szüksége lehet tölteni egy kis időt, hogy új funkciókat.
És persze van egy sorban.
Nem fogunk menni ebbe egy a sok részlet.
De ez nagyon hasonlít a szellem.
Nem tudtam végrehajtani a sorba, és a megfelelő műveleteket,
Enqueue vagy dequeue, mint felvenni vagy eltávolítani, ez csak egy szakértő szóval ez,
Enqueue vagy dequeue, az alábbiak szerint.
Én is csak adok magamnak egy struct hogy ismét van egy szám tömb,
hogy ismét a mérete, De miért most kell
nyomon követni az első sorban?
Nem kell tudni Az első az én verem.
Hát, ha ismét egy queue-- nézzük csak kemény
kódolnod, mint amelyek, mint öt Egész számok itt potenciálisan.
Tehát ez nulla, egy, kettő, három, négy.
Ez lesz hívott számokat újra.
És ez lesz az úgynevezett mérete.
>> Miért nem elegendő hogy csak méretet?
Nos, nézzük nyomja ugyanezen számok.
Szóval pushed-- I enqueued, vagy tolt.
Most akkor sorba állítását 50, majd 51, majd 61, és pont pont pont.
Szóval ez Enqueue.
Én enqueued 50, majd 51, majd 61.
És hogy néz ki, hogy egy rakás eddig,
csak én szükség, hogy egy változás.
Azt, hogy frissíteni kell ezt a méretet, így megyek nulláról 1-2, hogy három most.
Hogyan dequeue?
Mi történik a dequeue?
Kinek kell lejönni először a listán ha ez a vonal az Apple Store?
Tehát 50.
Szóval ez a fajta trükkösebb ebben az időben.
Mivel utoljára ez szuper volt egyszerűen csak nem mérete mínusz egy,
Azt, hogy a végén az én tömb hatékonyan ahol a számok, hogy eltávolítja 61.
De nem akarom, hogy távolítsa el 61.
Azt akarom, hogy 50, akik ott volt 05:00
sorban a új iPhone vagy miegymás.
És így, hogy megszabaduljon a 50, I Nem csak ezt, ugye?
Én is kihúz 50.
De mi csak azt mondta, Nem kell, hogy így legyen anális
hogy kihúz vagy elrejtheti az adatokat.
Mi is csak elfelejteni, hol van.
>> De ha tudom megváltoztatni a mérete most Két, ez elegendő információ
tudni, hogy mi folyik az én sorban?
Nem igazán.
Mint a mérete két, hanem hol a sorban kezdődik,
különösen, ha még mindig van ugyanezek a számok a memóriában.
50, 51, 61.
Szóval kell emlékezni Most, amikor a front.
És ahogy javasoltam fel ott vagyunk, már csak úgynevezett
N-edik előtt, akinek az első értéket kellett volna, mi?
Zero, csak a lista elején.
De most amellett, hogy csökkentjük a méret, csak növeljük az első.
Most itt van egy másik probléma.
Tehát ha én folyamatosan megy.
Tegyük fel, ez az a szám, mint 121, 124, majd, a fenébe is,
Én vagyok a hely.
De várj egy percet, nem vagyok.
Tehát ezen a ponton a történet, tegyük fel, hogy a mérete egy, kettő,
három, négy, így feltételezzük, hogy a mérete négy, az első az egyik,
így 51 elöl.
Azt szeretnénk, hogy egy másik számot itt, de a fenébe is, én vagyok a hely.
De nem igazán vagyok, ugye?
Hol tudnék némi hozzáadott érték, mint a 171?
Igen, én is csak ilyen menj vissza oda, ugye?
Majd húzza át a 50, vagy Csak írja felül 171.
És ha kíváncsi vagy, miért a számok annyira véletlenszerű,
Ezek általánosan vett számítógép tudományos képzés, a Harvard után CS50.
De ez egy jó optimalizálás, mert most nem vagyok kiesik hely.
Még mindig kell emlékezni milyen nagy ez a dolog teljes.
Ez összesen öt.
Mert nem akarom, hogy felülírását kezdi 51.
Szóval most én vagyok még szabad terület, így ugyanaz a probléma, mint korábban.
De láthatod, hogy most a kódban, akkor valószínűleg
Meg kell írni egy kicsit komplexitás, hogy ez megtörténjen.
És valóban, mi üzemeltető C valószínűleg lehetővé teszi,
Ön varázslatosan ezt a körkörösség?
Ja moduló, A százalékos jel.
Szóval mi egyfajta hűvös egy sorban, még akkor is megtartjuk rajz tömbök
mivel ezek, mint egyenesek, ha fajta gondolni ezt a kanyargós
körül, mint egy kör, akkor csak ösztönösen azt a fajta működik mentálisan
Azt hiszem, egy kicsit tisztábban.
Azt még meg kell végrehajtani hogy a mentális modell kódot.
Szóval nem is olyan nehéz, végül, hogy végre,
de még mindig elveszítik a size-- inkább a képes átméretezni, kivéve, ha ezt tesszük.
>> Van, hogy megszabaduljon a tömb, akkor helyette egy egységes mutatót,
majd valahol a kódomat kaptam Egy hívják, amit úgy működnek, hogy valóban létre
A tömb hívott számokat?
Malloc, vagy valamilyen hasonló funkciót, pontosan.
Bármilyen kérdésre halom, vagy sorokat.
Igen?
Jó kérdés.
Mit modulo kíván használni itt.
Tehát általában akkor, ha a mod, akkor csináld
a méret a egész adatstruktúra.
Szóval valami ilyesmi öt vagy kapacitás, ha ez állandó, valószínűleg részt.
De csak ezzel modulo öt Valószínűleg nem elegendő,
mert tudnunk kell, hogy mi is kerületi itt vagy itt vagy itt.
Szóval akkor valószínűleg azt is akarnak bevonni
A méret a dolog, vagy az elülső változó is.
Tehát csak ez a viszonylag egyszerű aritmetikai kifejezés,
de modulo lenne a legfontosabb összetevő.
>> Tehát rövidfilm, ha lesz.
Egy animáció, hogy egyes hozzátartozók egy másik egyetemen
össze, hogy már adaptált ezt a vitát.
Ez magában foglalja a tanulás a Jack tényeket sorok és a statisztikák.
>> FILM: Once upon a time, volt egy srác nevű Jack.
Amikor eljött a barátkoznak, Jack nem egy trükk.
Szóval Jack elment, hogy beszéljen a Népszerű fickó, akit ismert.
Elment Lou, és megkérdezte, mit tegyek?
Lou látta, hogy a barátja tényleg szomorú.
Nos, ő kezdte, csak nézd, milyen úgy nézel ki.
Ne bármilyen ruhát egy másik pillantást?
Igen, mondta Jack.
Én biztos nem.
Gyere a házamba, és Majd én megmutatom nektek.
Így elmentek Jack.
És Jack megmutatta Lou mezőbe hol tartja minden ingek,
és a nadrágját, és a zokniját.
Lou, látom, hogy van az összes ruhát egy halom.
Miért nem viselnek néhány mások egyszer egy kicsit?
>> Jack azt mondta, jól, amikor én ruházatot eltávolítani és zokni,
Én mosom őket, és tedd őket a dobozba.
Aztán jön a következő Reggel, és akár azt hop.
Megyek a dobozt, és kap ruhámat a tetején.
Lou gyorsan rájött, A probléma Jack.
Folyton ruhát, CD-k, és könyvek a veremben.
Amikor elérte a valamit olvasni, vagy viselni,
Ő dönt, az első könyv, vagy fehérnemű.
Aztán amikor végzett, ő mondaná vissza.
Vissza menne, a tetején a verem.
Tudom, hogy a megoldás, mondta diadalmas Loud.
Meg kell tanulni, hogy kezdi el használni a sorban.
Lou vette Jack ruháit és lógott a szekrénybe.
És mikor kiürítették A doboz, ő csak dobta.
>> Aztán azt mondta, most már Jack, a végén A nap ruháit a bal
ha fel őket.
Akkor holnap reggel, amikor lásd a napsütés, hogy a ruhák
a jobb oldalon, a sor végére.
Hát nem látod? mondta Lou.
Ez lesz olyan szép.
Majd viselni mindent egyszerre Mielőtt viselni valamit kétszer.
És mindent sorba a szekrényében, és polc,
Jack kezdte érezni egészen biztos magában.
Minden köszönhetően Lou és ő csodálatos sorban.
1. Előadó: Rendben, ez imádnivaló.
Szóval mi már tényleg lesz A a motorháztető alatt most?
Hogy van mutatók, hogy van malloc,
hogy megvan a képessége, hogy hozzon létre darabokat a memória magunkat
dinamikusan.
Tehát ez egy kép, amit megpillantotta csak a minap.
Nem igazán él rajta, de ez a kép
már folyik alatta A motorháztető hete.
És így ez azt jelenti, csak egy téglalapot, amit rajzolt,
a számítógép memóriáját.
És talán a számítógép, illetve CS50 ID, egy gigabájt memória vagy RAM
vagy két gigabájt vagy négy.
Ez nem igazán számít.
Az operációs rendszer Windows vagy Mac OS vagy Linux,
lényegében lehetővé teszi a programot gondolni, hogy hozzá tud
hogy a teljes egészében a számítógép memóriájában,
még akkor is lehet, hogy fut több program egyszerre.
Így a valóságban, hogy nem igazán működik.
De ez a fajta illúzió fordítani az összes programot.
Tehát, ha két giga RAM, ez a az, hogy a számítógép lehet, hogy belegondolok.
>> Most véletlenül, az egyik ilyen dolgok, az egyik ilyen szegmensek memória,
nevezzük verem.
És valóban bármikor Eddig írásban kódot
hogy felhívta a funkciót, például a fő.
Emlékezzünk vissza, hogy minden alkalommal, amikor már húzott számítógép memóriája,
Én mindig felhívni a fajta felében egy téglalap itt
és nem zavarja, beszél mi van fent.
Mert amikor fő hívják, azt állítják, hogy ezt kapod szelet memória
hogy megy le itt.
És ha fő nevezett funkció mint a swap, illetve a swap megy itt.
És kiderül, hogy ez ahol ez kiöntött.
On egy úgynevezett verem belsejében a számítógép memóriáját.
Most a végén a nap, ez csak címek.
Ez olyan, mint byte nulla, byte hosszú, byte 2 milliárd.
De ha belegondolunk mivel ez téglalap alakú tárgyat,
Az összes csinálunk minden alkalommal hívunk funkció
rétegződés új szelet memória.
Adunk, hogy a funkció egy szelet saját memóriával dolgozni.
>> És emlékszem most, hogy ez fontos.
Mert ha van olyasmi, mint a swap
és két helyi változók, mint az A és B megváltoztatjuk ezeket az értékeket egy és két
két és egy, visszahívás hogy amikor a swap visszatér,
olyan, mintha ez a szelet A memória csak elmentek.
A valóságban ez még mindig ott forensically.
És valami még valóban ott.
De fogalmilag, ez olyan mintha ez teljesen eltűnt.
És így fő nem ismer a munka hogy azért került sor, hogy a swap,
kivéve, ha ez valóban telt azokban érvek mutató által vagy utalásokkal.
Most, az alapvető megoldás hogy ezt a problémát a swap-
Múlik a dolgokat a címet.
De kiderült, túl, mi óta tart fent az a része,
A téglalap egész idő alatt Még van több memóriát odafent.
És ha dinamikusan memóriát foglalni,
legyen szó belsejében getString, amely mi már ennek az Ön számára a CS50
könyvtár, vagy ha a fiúk hívja malloc és kérje
Az operációs rendszer egy darab memória, ez nem jön a veremből.
Jön egy másik helyre a számítógép memóriájában
hogy hívják a kupac.
És ez még nem minden más.
Ez ugyanaz a RAM.
Ez ugyanaz a memória.
Ez csak a RAM, ami akár ott, hanem itt lent.
>> És ez mit jelent?
Nos, ha a számítógép véges mennyiségű memória
és a verem nő fel, így beszélni, és a kupac szerint
hogy ezt a nyilat, növekszik le.
Más szavakkal, minden alkalommal, amikor hívást malloc,
te is kap egy szelet memória felülről,
akkor talán egy kicsit alacsonyabb, majd egy kicsit alacsonyabb, minden alkalommal, amikor hívást malloc,
A kupac, ez a használat, a fajta nő,
egyre közelebb és közelebb, mi?
A verem.
Így jelent ez úgy tűnik, mint egy jó ötlet?
Úgy értem, ahol ez nem igazán világos, mi mást tehet, ha csak
Van egy véges mennyiségű memóriát.
De ez biztosan rossz.
Ez a két nyíl a gyorstalpaló egymásért.
>> És kiderül, hogy a rosszfiú, emberek, akik különösen jó a programozás,
és akarja feltörni a számítógépeket, lehet kihasználni ezt a valóságot.
Tény, hogy nézzük meg egy kis részlet.
Szóval ez egy példa lehet olvasni mintegy részletesebben a Wikipedia.
Majd pont akkor a cikket, ha kíváncsi.
De van egy támadás általában néven puffer túlcsordulás, hogy
létezett ameddig emberekben volt képes manipulálni
számítógép memóriájában, különösen a C. Tehát ez egy nagyon önkényes programot,
de most olvasni alulról felfelé.
Fő be argC char csillagos argv.
Szóval ez egy program, mely parancssori paramétereket.
És a legfontosabb jelent látszólag hívás függvényében, nevezzük az egyszerűség kedvéért F.
És ez megy, mi?
Argv egy.
Így bejut F bármi a szó, hogy a felhasználói gépelt
A prompt után Szak neve egyáltalán.
Annyira, mint Caesar vagy Vigenère, amely talán felidézni csinál argv.
>> Tehát mi F?
F vesz egy húr mint a kizárólagos érvet,
AKA egy char csillag, ugyanazon dolog, mint egy húr.
És ezt hívják önkényesen Bár ebben a példában.
És akkor char c 12, Csak a laikus szempontból,
mi char c konzol 12 csinál nekünk?
Mi csinál?
Memórialefoglalás, konkrétan 12 byte 12 karakter.
Pontosan.
És akkor az utolsó sort, majd kevergetve másolatot, akkor már valószínűleg nem látta.
Ez egy szöveg másolata függvény, amelynek célja az életben
az, hogy másolja a második érv be az első érv,
de csak egy bizonyos számú bájt.
Így a harmadik érv azt mondja, hány bájtot kell másolni?
A hossza bár, amit a felhasználó beírt.
És a tartalmát bár, hogy a húr, amelyek
bemásolja a memóriában mutatott a C.
>> Szóval ez úgy tűnik, elég hülyén, és ez.
Ez egy kitalált példa, de ez képviselője
egy osztály a támadási, módon támadó egy programot.
Minden rendben van, és jó, ha a felhasználó típusok egy szó, ami 11 karakter
vagy kevesebb, plusz a backslash nulla.
Mi van, ha a felhasználó beírja a több mint 11 vagy 12 vagy 20 vagy 50 karakter?
Mi ez a program fog csinálni?
Potenciálisan seg hiba. Működik hogy vakon másolni mindent bar
a hosszával, amely a Szó szerint mindent bár,
a címet mutatott C. De C csak megelőző jellegű adják 12 bájt.
De nincs külön ellenőrizni.
Nincs ha a körülmények.
Nincs hibaellenőrzési itt.
>> És akkor mi ez a program eredménye, hogy vakon
másolni egy dolog, hogy a többi.
És így, ha felhívjuk ezt képként, itt
Csak egy szeletkét a memóriát.
Tehát észre az alján, mi Van egy helyi változó bárban.
Szóval ez a mutató, hogy fog store-- inkább az, hogy a helyi érv, hogy ez
fog tárolni a húr bárban.
És akkor észre csak fölötte egy verem,
mert minden alkalommal, amikor kérni A memória a veremben,
megy egy kicsit fölötte képileg,
észre, hogy megvan a 12 byte van.
A bal felső az egyik C konzol nulla és ki a jobb alsót C konzol 11.
Ez csak, hogy a számítógépek majd feküdt ki.
Tehát csak ösztönösen, ha bár több mint 12 karakter összesen, beleértve a
A backslash nulla, hol van a 12 vagy a C konzol 12 fog menni?
Vagy inkább, ahol a 12- karakter vagy a 13. karaktert,
A századik karaktert fog hogy a végén a képen?
Alatt vagy felett?
>> Jobb, mert bár A verem magát növekszik felfelé,
ha egyszer már fel cuccot , ez a dizájn miatt
helyezi a memória felülről lefelé.
Tehát, ha már van több mint 12 bájt, fogsz kezdeni, hogy felülírja bárban.
Most, hogy egy hiba, de ez Nem igazán nagy dolog.
De ez egy nagy dolog, mert van Több dolog történik a memóriában.
Tehát itt, hogy hogyan tudnánk tedd hello, hogy egyértelmű legyen.
Ha beírtam helló a billentyűket.
H-E-L-L-O backslash nulla, végül belül a 12 byte, és mi szuper biztonságos.
Minden rendben.
De ha én írja valamit hosszabb, esetleg ez
fog szivárogni a bárban helyet.
De ami még rosszabb, kiderül az összes ebben az időben,
még akkor is, soha nem beszéltünk ez a verem használják egyéb dolgokat.
Ez nem csak a helyi változókat.
>> C egy nagyon alacsony szintű nyelven.
És ez a fajta titokban használja a verem is
emlékezni, amikor egy funkciót nevezik, mi
A cím az előző funkciót, így ugrik vissza, hogy a funkció.
Tehát amikor a fő hívások cserélni között A dolgok a verembe
nem csak felcseréli a helyi változókat, vagy érveit, szintén titokban tolta
a verembe képviselt A piros szelet itt,
a címe fő fizikailag a számítógép memóriájában,
úgy, hogy amikor a swap történik, a számítógép tudja, hogy vissza kell mennie a fő
és befejezni a végrehajtó a fő funkciója.
Szóval ez veszélyes most, mert ha a felhasználó által is több mint hello,
úgy, hogy a felhasználó által megadott clobbers vagy felülírja, hogy piros pont,
logikusan, ha a számítógép csak fog vakon vállalnak
hogy a bájtok a piros szelet is a címet, amelyre ad vissza,
mi van, ha az ellenség elég okos ahhoz, vagy szerencsés, hogy egy bájtsorozatok
van, hogy néz ki, mint egy cím, de ez a címe kód
hogy ő akarja a számítógép hogy végre ahelyett fő?
>> Más szóval, ha az, amit az felhasználó beírja a parancssorba
nem csak valami ártalmatlan, mint a Hello,
de ez valójában kódot, ami egyenértékű törölni mindezt a felhasználó fájljai?
Vagy e-mailben a jelszót, hogy nekem?
Vagy indul naplózása billentyűleütéseket, ugye?
Van egy módja, hadd kikötik ma, hogy tudtak írja nemcsak helló
világ, vagy a nevüket, tudtak lényegében
át a kódot, és nullák is, hogy a számítógép
hibák mindkét kódot, és egy címet.
Így bár kissé absztrakt, ha a felhasználó beír elég ellenséges kódot
hogy mi lesz általánosítani itt A. A jelentése támadás vagy ellenfelek.
Tehát csak rossz dolgokat.
Nem érdekel a számát vagy a nullát vagy egyest
ma, mint, amit a végén felülírását, hogy piros pont,
észre, hogy bájtsorozatok.
O 835 C nulla nyolc nulla.
És most, ahogy a Wikipedia cikket itt azt javasolta, ha már tényleg kezd
címkézéshez bájtok számítógép memória, amit a Wikipedia cikket
javaslattevő, hogy mi van, ha a cím Az, hogy a bal felső bájt 80 C 0 3508.
>> Más szóval, ha a rosszfiú elég okos a saját kódját
hogy egyszerűen egy számmal, hogy itt megfelel a címet a kódot
ő injektált a számítógépbe, akkor
trükk a számítógép csinál semmit.
Eltávolítja a fájlokat, e-mailezés dolgokat, szippantás a forgalom,
Szó szerint bármi lehet fecskendeznek a számítógép.
És így a puffer túlcsordulás támadást középpontban
ez csak egy hülye, hülye nyomós tömb, hogy
Nem volt annak határait ellenőrizni.
És ez az, ami szuper veszélyes és ezzel egyidejűleg szuper erős
C-ben az, hogy valóban van hozzáférést biztosít bárhol a memóriában.
Rajtunk múlik, hogy velünk, a programozók, akik írni az eredeti kódot
hogy ellenőrizze a rohadt hosszú bármely tömbök, hogy mi manipulálni.
Tehát, hogy világos legyen, mi a fix?
Ha visszaállíthatja erre kódot, amit nem kellene csak
megváltoztatni a hossza bár, mit mást kéne megnézni?
Mit kell még csinálni, hogy ennek kivédésére teljesen?
Nem akarom, hogy csak vakon mondani hogy meg kell másolni annyi bájt
mint a hossza bar.
Azt akarom mondani, másolni, mint hány bájt, mint a bar
akár a kiosztott memória, vagy 12 maximálisan.
Szóval kell valami, ha állapota hogy nem ellenőrzi a hossza bár,
de ha az meghaladja a 12, csak kemény kódot 12, mint a lehető legnagyobb távolságot.
Ellenkező esetben az úgynevezett puffer túlcsordulás támadás megtörténhet.
Alján a tárgylemezeket, Ha kíváncsi vagy, hogy tovább
a tényleges eredeti cikk Ha azt szeretné, hogy vessen egy pillantást.
>> De most, többek között az árak fordítani volt hiányosságok.
Szóval ez volt a gyors alacsony nézd meg, mi
problémák merülhetnek fel most, hogy férhetnek hozzá számítógép memóriájában.
De egy másik probléma is Már megbotlott hétfőn
csak az eredménytelenség A láncolt lista.
Mi vissza a lineáris időt.
Már nincs egy összefüggő tömbben.
Nincs véletlen hozzáférésű.
Nem tudjuk használni szögletes zárójel jelöléssel.
Szó van, hogy egy while ciklus amilyet én írtam az imént.
De hétfőn azt állította, hogy tudjuk kúsznak vissza a birodalmába hatékonyság
elérése valamit, ami logaritmikus vagy talán eddigi legjobb,
talán még valamit, ami úgynevezett konstans idő.
Szóval hogyan lehet csinálni, hogy segítségével ezek az új szerszámok, ezeket a címeket, ezeket a mutatókat,
és threading dolgokat a saját?
Nos, tegyük fel, hogy Itt, ezek egy csomó
A számok, hogy szeretnénk tárolni egy adatok szerkezete és keresés hatékonyan.
Mi lehet teljesen visszatekerni a héten két, dobja ezeket egy tömbben,
és keresni őket bináris kereséssel.
Oszd meg és uralkodj.
És valóban írtál bináris keresés PSET3,
ahol végre a find programot.
De tudod, mit.
Van egyfajta többet okos módja ennek.
Ez egy kicsit kifinomult és ez talán
lehetővé teszi számunkra, hogy miért bináris Keresés annyira sokkal gyorsabb.
Először is, hadd vezessen be a fogalom a fán.
Mely, bár a valóság fák fajta
nőnek, mint ez, a világ számítógép a tudomány azt a fajta nő lefelé
mint egy családfát, ahol van, a nagyszülők vagy a dédszüleim
vagy miegymás tetején, a pátriárka és A családfő anya a család, csak egy
úgynevezett gyökér, csomópont, az alábbiakban amelyek a gyermekek,
alatt, amelyek a gyermekek, illetve leszármazottai általában.
És bárki lógott le az alján a család
fa, amellett, hogy a legfiatalabb a családban,
is csak legyen általánosan az úgynevezett levelek a fa.
>> Tehát ez csak egy csomó A szavak és kifejezések
valami úgynevezett fa számítógép a tudomány, mint egy családfát.
De van cifrább inkarnációja a fák, amelyek közül az egyik
az úgynevezett bináris kereső fa.
És akkor milyen kötekedik eltekintve mi ez a dolog nem.
Nos, ez a bináris milyen értelemben?
Amennyiben ez a bináris származik itt?
Bocsánat?
Ez nem is annyira sem vagy.
Ez több, hogy az egyes csomópontok nem rendelkezik Több mint két gyerek, mint látjuk itt.
Általában egy tree-- és a szülők és nagyszülők
Egyszerre annyi gyerek, vagy unoka, mert valójában akar,
és így például ott van három a gyerekek ki, hogy jobb csomópont,
de egy bináris fa, egy csomópont nulla, egy vagy két gyermek maximálisan.
És ez egy jó tulajdonság, mert ha ez a két kupakkal,
fogunk tudni egy kicsit napló bázis két
akció folyik itt végül.
Tehát van valami logaritmikus.
De még az, hogy egy pillanat alatt.
Keresés fa azt jelenti, hogy a számok elrendezve, hogy a bal oldali gyermek
érték nagyobb, mint a gyökér.
És a jobb fia nagyobb, mint a gyökér.
Más szóval, ha Ön bármely csomópontok, a körök ezt a képet,
és megnézi a bal gyermek és jobb fia,
az első legyen kisebb, mint, a második nagyobbnak kell lennie, mint.
Így a józanság ellenőrizheti 55.
Ez maradt gyermek 33.
Ez kevesebb, mint.
55, a jobb fia 77.
Ez nagyobb, mint.
És ez egy rekurzív definíció.
Mi lehetett ellenőrizni minden egyike azoknak csomópontok és ugyanazt a mintát tartana.
>> Szóval mi szép egy bináris kereső fa, az
hogy az egyik, akkor végrehajtja egy struct, mint ez.
És bár mi dobott Sok struktúrák a,
ők valamelyest intuitív most remélhetőleg.
A szintaxis mindig misztikus biztos, de a tartalmát egy csomópont ebben
context-- és mi folyamatosan szó használata a csomópont,
hogy ez egy téglalap a képernyőn, vagy egy kör,
ez csak néhány általános tároló, Ebben az esetben egy fa, mint az egyik
láttuk, szükségünk van egy egész szám az egyes csomópontok
és aztán kell két mutató mutató balra a gyermek és a megfelelő gyermek,
volt.
Szóval így talán végre, hogy egy struktúra.
És hogyan lehet azt megvalósítani, hogy a kódot?
Nos, vessünk egy gyors nézd meg ezt a kis példát.
Ez nem működőképes, de már vágólapra másolni, hogy a struktúra.
És ha én a funkció egy bináris keresési fa az úgynevezett kereső,
és ez a két paramétert, n egész és egy mutatót
A csomóponthoz, így egy mutatót a fán vagy egy mutatót a fa gyökerét,
hogyan megy körülbelül keresi N?
Nos, először is, mert én vagyok foglalkozó mutatók,
Azt fogom tenni a józanság csekket.
Ha fa egyenlők egyenlő null, N a fán vagy nem a fán?
Nem lehet, nem?
Ha én vagyok már null, nincs ott semmi.
Én akár azt is csak vakon mondják vissza hamis.
Ha adsz nekem semmi, én biztosan nem találtunk száma N. Szóval mi mást én
ellenőrizd most?
Azt fogom mondani jól mást, ha N kevesebb, mint amit az a facsomópont
hogy én már átadta N értéket.
Más szóval, ha a szám én keres, az N, kevesebb, mint a csomópont
hogy nézem.
És a csomópont keresem A nevezik fa,
és emlékszem az előző példában eljutni az értéket egy mutatót,
Én a nyíl jelöléssel.
Tehát, ha az N-nél kisebb fa nyíl N, azt akarom, hogy koncepcionálisan menni balra.
Hogyan kifejezetten keresi maradt?
Ahhoz, hogy tiszta, ha ez a kép a szóban forgó,
és én már át, hogy a legfelső nyíl, ami lefelé mutat.
Ez az én fa mutató.
Én mutatott a gyökér a fa.
És keresem mondjuk, száma 44, önkényesen.
44-nél kisebb, vagy nagyobb, mint 55 nyilvánvalóan?
Szóval ez kevesebb, mint.
És így ez, ha a feltétel.
Tehát elméletileg, mit akarok keresés jövő, ha keresem 44?
Igen?
>> Pontosan, szeretnék keresés a bal gyermek,
vagy a bal oldali részfa kép.
És valóban, hadd keresztül A képet itt lent
csak egy pillanatra, hiszen Nem tudom karcolja meg ezt.
Ha elkezdek itt a 55., és a Tudom, hogy az érték 44
Keresem az, hogy A bal, ez a fajta
hasonló tépte a telefonkönyvből fél- vagy könnyezés a fa felét.
Én már nem kell törődnünk ezt az egész fele a fa.
És mégis, kíváncsian szempontjából a szerkezete, ez a dolog itt, hogy
kezdődik a 33., hogy maga egy bináris kereső fa.
Azt mondta, a szó rekurzív előtt, mert Valóban ez egy adatstruktúrát, amely
definíció rekurzív.
Lehet, hogy egy fát, hogy ez nagy, de minden embernél a gyerekeknek
jelent egy fa, csak egy kicsit kisebb.
Ahelyett hogy a nagypapa vagy a nagymama, most már csak anya
or-- nem tudok say-- nem anya vagy apa, hogy furcsa lenne.
Ehelyett a két gyerek van lenne, mint testvére és a testvér.
Az új generációs családfáját.
De szerkezetileg, ez ugyanaz a gondolat.
És kiderül, van egy funkció amellyel tudok keresni egy bináris keresés
fa.
Úgy hívják keresést.
Én keresni N fa nyíl balra mást ha n értéke nagyobb, mint az érték
hogy én vagyok jelenleg.
55 A történet egy perce.
Van olyan függvény is kereső, amely tudok csak
át N ezt, és rekurzív keresés Az al-fát, és csak vissza
akármit is választ.
Mást kaptam néhány végső alapeset itt.
>> Mi a végső esetben?
Fa vagy null.
Az érték Engem sem keres kevesebb, mint ez, vagy nagyobb, mint a
vagy egyenlő vele.
És azt is mondhatnám egyenlő egyenlő, de logikusan ez
egyenértékű csak azt mondom, itt még.
Tehát igaz az, hogy hogyan találok valamit.
Így remélhetőleg ez egy még vonzóbb például
mint a hülye szigma funkció csináltunk egy pár előadásra vissza,
ahol éppen olyan könnyen használható a hurok számoljon el a számokat az egyik
N. Itt egy adatstruktúrát hogy maga rekurzív
meghatározott és rekurzív húzott, most megvan a képessége, hogy kifejezze magunkat
A kód, amely önmagában rekurzív.
Tehát ez pontosan ugyanazt a kódot itt.
>> Tehát mi más problémák tudjuk megoldani?
Tehát egy gyors lépésre fák csak egy pillanatra.
Itt van, mondjuk, a német zászló.
És ott egyértelműen a minta ez a zászló.
És van sok zászlók a világ, hogy
olyan egyszerű, mint ez szempontjából a színek és minták.
De tegyük fel, hogy ez tárolja a GIF, vagy JPEG, vagy bitmap, vagy egy ping,
egy grafikus fájlformátum amellyel még nem ismeri,
amelyek közül néhány vagyunk játszik a PSET4.
Ez nem tűnik érdemes tárolni fekete pixel, fekete pixel, fekete pixel,
dot, pont, pont, egy csomó fekete képpont az első soronkénti,
vagy sor, akkor egy csomó ugyanaz, akkor egy csomó
az azonos, majd egy csomó piros pixel,
piros pixel, piros pixel, majd egy egész csokor sárga képpont, sárga, ugye?
>> Van egy ilyen eredménytelenség itt.
Hogyan írnád intuitívan tömöríteni a német zászló
Ha azt végrehajtó fájlként?
Például mit információt nem tudunk zavarja tárolása a lemezen érdekében
csökkenti a fájl mérete, mint a egy megabyte egy kilobyte, valami
kisebb?
Ahol rejlik a redundancia Itt tisztázni kell?
Mit tehetett volna?
Igen?
Pontosan.
Miért nem inkább emlékezni a színe minden rohadt pixel
mint te csinálsz itt PSET4 A bitmap file formátum,
miért nem csak képviseli a bal szélső oszlopában pixel, például
Egy csomó fekete képpontok, egy csomó vörös, és egy csomó sárga,
és aztán csak valahogy kódolják ötlete ismételje ezt 100-szor
vagy ismételje meg ezt a 1000-szer?
Amennyiben 100 vagy 1000 van Csak egy egész szám, így
lehet megúszni csak egy számot helyett száz vagy több ezer
további pixel.
És valóban, mi így lehet tömöríteni a német zászlót.
És
Most mi a helyzet a francia zászló?
És egy kicsit valamiféle mentális gyakorlat, amely zászló
lehet tömörített több lemezen?
A német zászló, vagy a francia zászló, ha vesszük ezt a megközelítést?
A német zászló, mert van több vízszintes redundancia.
És a programok kialakítása, sok grafikus fájl formátumok valóban működik nevén képsorok
vízszintesen.
Tudtak dolgozni függőlegesen, csak az emberiség
úgy döntött évvel ezelőtt, hogy mi lesz általában gondolni a dolgokat sorban
által, hanem egymás oszlopról oszlopra.
Tehát valóban, ha volt hogy nézd meg a fájl
akkora, mint egy német és egy francia zászló zászló, mindaddig, amíg a felbontás
az azonos, azonos szélességű és a magasság, ez az egy
Itt lesz nagyobb, mert meg kell ismételni magát háromszor.
Meg kell adnia a kék, ismételje magad, fehér, ismételje meg magad, piros,
ismételje magát.
Nem lehet csak úgy megy minden Az utat a jobb oldalon.
És mint félre, hogy törölje a kompressziós
mindenütt jelen van, ha ezek négy kép egy video-- akkor
Lehet emlékeztetnek arra, hogy egy film vagy video általában
mint 29 vagy 30 képkocka másodpercenként.
Ez olyan, mint egy kis flip könyv, ahol csak lásd kép, kép, kép, képek,
A kép csak szuper gyors, így néz ki A szereplők a képernyőn mozog.
Itt egy poszméh a tetején egy csokor virágot.
És bár lehet, hogy egyfajta nehéz belátni, hogy az első pillantásra,
Az egyetlen dolog, mozgó ez a film a méhek.
>> Milyen buta tárolásával kapcsolatban videó tömörítés nélkül?
Elég egy hulladék tárolására videó négy, közel azonos képek
különböznek csak annyiban, amennyiben a méh.
Akkor dobja el a legtöbb Ezen információk
és emlékszem csak, például, Az első keret és az utolsó képkocka,
fő kereteket, ha már Hallottál már a szó,
és csak tárolja az közepén, ahol a méh.
És akkor nem kell tárolja az összes a rózsaszín,
és a kék, és a zöld értékeket is.
Tehát ez csak azt jelenti, hogy tömörítés mindenhol.
Ez egy technika, gyakran használja vagy magától értetődőnek ezekben a napokban.
>> De hogyan tömöríteni szöveget?
Hogyan megy körülbelül tömörítése szöveget?
Nos, mind a karakterek Az ASCII egy bájt, illetve nyolc bit.
És ez a fajta buta, ugye?
Mert akkor valószínűleg típusú és E I és O, U sokat
gyakrabban, mint, mint a W vagy Q vagy Z, attól függően, hogy milyen nyelven
írsz biztosan.
És így miért is használ nyolc bit minden levelet,
köztük a legkevésbé népszerű leveleket, ugye?
Miért nem használ kevesebb bitet A szuper népszerű betűk,
mint az E, a dolgok akkor hiszem, első Szerencsekerék,
és több bitet A kevésbé népszerű leveleket?
Miért?
Mert mi csak fog használja őket ritkábban.
>> Nos, kiderült, hogy ott van Történtek próbálkozások erre.
És ha visszahívja évfolyam iskolában vagy középiskolában, morze.
Morse kód pontok és gondolatjelek, hogy lehet
adódik át egy vezetéket, mint hangok vagy jelek néhány sort.
De morze egy szuper tiszta.
Elég egy bináris rendszer hogy van a pontok vagy gondolatjelek.
De ha úgy látja, hogy például két pont.
Vagy ha úgy gondolja, vissza a kezelő aki megy, mint sípszó sípszó, sípszó,
sípolás, ütő egy kicsit ravaszt hogy egy jelet,
ha a címzett, kap két pöttyök, milyen üzenetet kaptál?
Teljesen önkényes.
>> Én?
Én?
Vagy mi about-- vagy én?
Lehet, hogy csak két E jogát?
Szóval van ez a probléma A decodability Morse
kódot, amellyel kivéve, ha a küldője akkor az üzenet
valóban szünetel, így egyfajta lát vagy hall a rések között levelek,
ez nem elegendő csupán Levél egy patak nullák,
vagy pontok és vonalak, mert ott van a kétértelműség.
E egyetlen pont, így ha hogy két pont, vagy hallani két pont,
talán két E által vagy talán ez az egyik I.
Tehát szükségünk van egy olyan rendszer, amely egy kicsit okosabb annál.
Tehát egy ember nevű Huffman év ezelőtt jött össze pontosan ezt.
Szóval csak úgy hogy egy gyors pillantást
hogy milyen fák illenek ehhez.
Tegyük fel, hogy ez az egyes hülye üzenetet küldeni szeretné,
tagjai: csak A, B, C a D és az E-k, de van egy csomó redundancia itt.
Ez nem azt jelentette, hogy az angol.
Ez nem titkosított.
Ez csak egy hülye üzenetet sok az ismétlés.
Tehát, ha valóban számít ki az összes A., B., C-, D és E a, itt van
A frekvencia.
20% -a a betűk A., 45% -a a betűk
az E-k, és három másik frekvencián.
Mi számít ott kézzel és csak nem a matek.
>> Így kiderül, hogy a Huffman, néhány évvel ezelőtt,
rájött, hogy, tudod, mit, ha elkezdek épület
egy fa, vagy erdei fák, ha úgy tetszik, az alábbiak szerint, meg tudom csinálni a következő.
Megyek, hogy egy csomópont minden A betűk érdekel
és megyek tárolni belsejében a csomóponton
A frekvenciák lebegőpontos értéket, vagy ha lehet használni egy N is
de majd csak használ egy úszó van.
És az algoritmus, hogy azt javasolta, hogy meg
ezt erdő egyes csomópont fák, így szuper rövid fák,
és elkezd összekötő őket Új csoportok, új szülők, ha úgy tetszik.
És akkor ezt választotta a két legkisebb frekvencia egy időben.
Szóval vettem 10% és 10%.
Én hozzon létre egy új csomópontot.
És hívom az új csomópont 20%.
>> Melyik két csomópont egyszerre többféle jövő?
Ez egy kicsit félreérthető.
Szóval egy kis sarok ügyek fontolja meg, de a dolgokat elég,
Megyek választhat 20% - Én most figyelmen kívül hagyja a gyerekeket.
Megyek választhat 20% és 15% és felhívni két új élek.
És most, amely két csomópontot tudom logikailag összekapcsolják?
Figyelmen kívül hagyja a gyerekek, mind a unokái, csak nézd meg a gyökereket
Most.
Melyik két csomópont tudom köti össze?
Pont két és 0,35.
Szóval hadd hívjam két új élek.
És akkor már csak egy maradt.
Tehát itt egy fa.
És ez már kiállított szándékosan nézni milyen szép,
de észrevettem, hogy a széleken is is jelzett nulla és egy.
Tehát mind a bal szélétől nulla önkényesen, de következetesen.
Minden a megfelelő élek is.
>> És akkor mi van Hoffman javasolt, Ha azt szeretnénk, hogy képviselje a B,
ahelyett képviseli a szám 66, mint ASCII amely nyolc teljes bit,
tudod mit, csak boltba A minta nulla, nulla, nulla,
nulla, mert ez az út az én fa, Mr. Huffman fája,
A levél a gyökér.
Ha szeretnéd tárolni E ezzel szemben nem
Levél nyolc bit, hogy képviselje az E. Ehelyett küldeni, milyen mintát bitek?
Egy.
És mi a szép ez, hogy az E a legnépszerűbb írni,
valamint ha a legrövidebb kódot hozzá.
A következő legnépszerűbb levél néz ki, hogy
volt A. És így hány bitet mondott javaslatot használ ez?
Nulla, egy.
>> És mert ez végre mivel ez a fa, most
hadd kikötik van egyértelműen meg a Morse-
kódot, mert az összes betűk törődsz
vannak végén ezeket élek.
Szóval ez csak egy alkalmazása egy fa.
Ez is-- és én hullám kezem ebben hogyan
Lehet végrehajtani ezt a C szerkezetet.
Csak meg kell kombinálni egy szimbólum, mint egy char,
és a frekvencia balra és jobbra.
De nézzük meg a két utolsó példa, hogy akkor
kap elég ismerős után kvíz nulla probléma meg öt.
>> Tehát van az adatstruktúra néven hash tábla.
És egy hash tábla fajta király, mivel úgy rendelkezik vödrök.
És tegyük fel, van négy vödör itt van, csak négy üres helyeket.
Itt egy pakli kártyát, és itt van klub, ásó, klub, gyémánt, klub,
gyémánt, klub, gyémánt, clubs-- így ez a véletlen.
Szívek, hearts-- úgyhogy bucketizing az összes bemenet van.
És egy hash table-nek hogy nézd meg a bemeneti,
majd betette egy bizonyos helyezze az alapján, amit látsz.
Ez egy algoritmust.
És én is használtam egy szuper egyszerű vizuális algoritmus.
A legnehezebb része az volt, eszébe jutott, amit a képek voltak.
És akkor ott van négy teljes dolgokat.
>> Most a halom nőttek, ami egy tudatos tervezés dolog itt.
De mi mást tehetek?
Szóval tényleg itt van egy csomó régi iskolai vizsga könyveket.
Tegyük fel, hogy egy csomó hallgatók nevek itt.
Itt egy nagyobb hash tábla.
Négy helyett vödrök, Én, mondjuk 26.
És nem akartunk menni kölcsönkérni 26 dolgokat kívülről [? Annenberg?], Így
Itt van öt képviselő A-tól Z És ha én
hogy egy diák, akinek a neve kezdődik, Megyek tegye saját kvíz ott.
Ha valaki kezdődik C, ott, Egy-- valójában, nem akartam ezt tenni.
B megy át ide.
Így kaptam az A és B és C és Most itt egy másik diák.
De ha ez a hash tábla végre egy sor,
Én ilyen csavarni Ezen a ponton, igaz?
Valahogy meg kell tenni ennek valahol.
>> Tehát az egyik mód arra, hogy megoldja ezt, minden Jobbra egy forgalmas, B foglalt, C foglalt.
Megyek, hogy őt D. Tehát Először is, én véletlen azonnali hozzáférést
az egyes kanalak a diákok számára.
De most ez a fajta decentralizált valami lineáris,
mert ha akarok keresni valakit akinek a neve kezdődik, megnézem itt.
De ha ez nem az A hallgató keresem,
Valahogy el kell kezdeni ellenőrzése A vödrök, mert amit tettem
afféle lineárisan szonda adatok szerkezetét.
Egy hülye szóval csak nézz az első rendelkezésre álló nyitó,
és tedd egy B terv, hogy úgy mondjam, vagy terv D ebben az esetben az értéket
e helyett.
Ez csak úgy, hogy ha már Van 26 helyszínen, és nem a diákok
A név Q vagy Z, vagy valami ilyesmi hogy legalábbis, amit használ a teret.
>> De már látott több Okos megoldás itt van, ugye?
Mit tennél helyett ha van egy ütközés?
Ha két ember A megnevezés, mi lenne
már egy okosabb vagy több intuitív megoldás, mint
Elhelyezés egy D helyére kéne lennie?
Miért nem csak megy kívül [? Annenberg?],
mint a malloc, egy másik csomópont, tedd itt, és aztán, hogy egy diák itt.
Szóval, hogy én alapvetően van valamiféle tömb,
vagy talán elegánsabb, mint mi vagyunk kezdik látni a láncolt lista.
>> És így a hash tábla egy olyan szerkezet amelyek úgy néznek ki, mint ez,
de ügyesen, akkor egy úgynevezett Külön láncolás, ahol egy hash tábla
egészen egyszerűen egy tömb, egyenként melynek elemei nem szám,
maga a láncolt lista.
Úgy, hogy Önnek szuper gyors hozzáférést döntés, hogy hol hash meg értéket.
Hasonlóan a kártyák például Csináltam szuper gyors döntéseket.
Szívek megy itt, gyémánt megy itt.
Ugyanez itt, egy megy itt, D megy itt, a B megy itt.
Szóval szuper gyors pillantást-up, és ha akkor megtörténhet, hogy befut egy esetben
ahol van ütközés, két az emberek az azonos nevű, majd jól
csak elkezd őket összekapcsolni.
És talán nem tartjuk őket válogatni betűrendben, talán nem.
De legalább most már a dinamizmus.
Tehát az egyik oldalon ott van szupergyors konstans időt, és egyfajta lineáris idő
szó, ha ezek a láncolt listák kezdenek egy kicsit hosszú.
>> Tehát ez a fajta egy buta, geeky vicc évvel ezelőtt.
A CS50 hack-a-Thon, amikor a diákok ellenőrzi,
Néhány TF vagy CA évente hiszi, hogy vicces, hogy tegye fel
jele, mint ez, ahol csak azt jelenti, ha a neve kezdődik egy A,
erre kell menni.
Ha a neve kezdődik a B, menjen this-- OK,
ez vicces, talán később a félévben.
De van egy másik módja ennek is.
Gyere vissza, hogy a.
>> Szóval van ez a szerkezet.
És ez az utolsó struktúra ma,
amely egy úgynevezett Trie.
A T-R-I-E, amely valamilyen okból rövid visszakeresés, de ezt hívják Trie.
Tehát egy Trie egy másik érdekes amalgám sok ilyen ötletek.
Ez egy fa, amit eddig láttam.
Ez nem egy bináris kereső fa.
Ez egy fa, minden gyermekek száma, de minden a gyerekek egy Trie
egy tömb.
Egy sor mérete, mondjuk, 26 vagy talán 27 Ha szeretnéd támogatni kötőjeles neveket
vagy aposztróf az emberek neveit.
>> És így ez egy adatstruktúra.
És ha megnézzük felülről A végére, mint ha
Nézd meg a felső csomópont van, M, az rámutatva, hogy a bal szélső dolog van,
amelyet ezután A, X, W, E, L, L. Ez csak egy adatstruktúra, hogy önkényesen
a tároló emberek neveit.
És Maxwell tárolja csak a következő az utat a tömb tömb tömb.
De mi Elképesztő egy Trie van hogy míg a láncolt lista, és még
tömb, a legjobb, amit valaha kaptál van lineáris idő vagy logaritmikus ideje keres
valakit.
Ebben adatstruktúra egy Trie, ha én adatszerkezet egy név benne
és keresem Maxwell, én vagyok fog találni elég gyorsan.
Én csak keresni M-A-X-W-E-L-L. Ha ez az adat struktúra, ezzel szemben,
ha N egy millió, ha van egy millió nevek ezen adatok szerkezete,
Maxwell még lesz felderíthető után csak az M-A-X-W-E-L-L
lépéseket.
És David-- D-A-V-I-D lépésben.
Más szóval, az épület adatstruktúrát, ami
kapott összes ilyen tömbök, amelyek mindegyike magukat támogatják véletlenszerű hozzáférés,
Kezdhetem keresi fel az emberek nevet egy ideig, ez
arányos Nem száma a dolgok az adatok szerkezete,
mint egy millió nevekkel.
Az időt vesz igénybe, hogy megtaláljam M-A-X-W-E-L-L ezen adat struktúra
arányos nem a mérete az adatok szerkezete,
de, hogy a hossza a név.
És reálisan nevek keresünk fel
soha nem lesz őrült hosszú.
Lehet, hogy valaki egy 10 karakter Íme, 20 karakter neve.
Ez természetesen véges, nem igaz?
Van egy ember a Földön, aki a leghosszabb lehetséges nevet,
bár ez az elnevezés állandó érték hossza, ugye?
Ez nem változik semmi értelme.
Tehát ily módon, most már elérni egy adatstruktúra
hogy állandó idő look-up.
Ez nem fog egy több lépésből attól függően, hogy a hossza a bemenet,
de nem a több név az adatszerkezet.
Tehát, ha megduplázza a nevek száma jövőre egy milliárd kétmilliárd,
megállapítás Maxwell fog tartani pontosan ugyanannyi hét lépésben
hogy megtalálja őt.
És így úgy tűnik, hogy elérték a szent grál a futási idő.
>> Tehát néhány gyors bejelentések.
Kvíz nulla jön ki.
Több az, hogy a pályán honlapján Az elkövetkező pár nap.
A hétfői lecture-- ez egy ünnep Itt a Harvardon hétfőn.
Ez nem New Haven, így elvisszük az osztály
New Haven Tantermi hétfőn.
Minden forgatják és élőben, mint rendesen,
de most véget ma egy 30 másodperces klip
az úgynevezett "mély gondolatokat" által Daven Farnham, amely
ihlette tavaly a szombat Night Live "mély gondolatok"
Jack Handy, amely Most már semmi értelme.
>> FILM: És most, "Deep Gondolatok "a Daven Farnham.
Hash tábla.
>> 1. Előadó: Rendben, ennyi egyelőre.
Találkozunk a jövő héten.
>> DOUG: Hogy látni működés közben.
Szóval vessünk egy pillantást, hogy most.
Tehát itt, van egy rendezetlen tömb.
>> Ian: Doug, akkor megy előre, és indítsa újra ez csak egy második, kérem.
Rendben, kamera gördülő, így fellépés, amikor csak akarja, Doug, OK?
DOUG: Rendben, akkor mi vagyunk Van itt egy rendezetlen tömb.
És én már színes valamennyi elemét piros, jelezve, hogy ez, sőt,
szétválogatás nélkül.
Így emlékeztetni arra, hogy az első dolog, amit Mi vagyunk rendezni a bal fele a tömbben.
Aztán rendezni a jobb a fele a tömb.
És ya-da, da ya-, ya-da, mi egyesítése őket.
És van egy teljesen rendezett tömbben.
Szóval így egyesíti a fajta működik.
>> Ian: Hé, hé, hé, vág, vág, vág, vág.
Doug, akkor nem csak ya-da, da ya-, ya-da, végig merge sort.
>> DOUG: én csináltam.
Rendben van.
Mi még jól jöhet.
Nézzük csak tartsa gördülési.
Mindegy,
>> Ian: Meg kell magyarázni ez jobban, mint ezt.
Ez egyszerűen nem elég.
DOUG: Ian, mi nem kell, hogy menjen vissza az egyik.
Rendben van.
Mindegy, ha továbbra is a merge-- Ian, mi vagyunk a közepén forgatás.
>> Ian: Tudom.
És nem csak a ya-da, da ya-, ya-da, az egész folyamatot.
Meg kell magyarázni, hogy a két fél kap összefűzve.
>> DOUG: De már elmagyarázta, hogy a két sides--
>> Ian: épp most látható nekik egy merge tömb.
DOUG: Ismerik a folyamatot.
Jól vannak.
Mentünk rajta tízszer.
>> Ian: Csak kimarad jobb rajta.
Megyünk vissza az egyik, akkor nem tudsz ya-da, da ya-felette.
Rendben, vissza az egyik.
>> DOUG: mennem kell vissza végig a csúszda?
Istenem.
Ez olyan, mint a hatodik alkalommal, Ian.
Rendben van.
>> Ian: Rendben.
Készen állsz?
Nagy.
Akció.