СПІКЕР 1: Добра, так што гэта CS50 Гэта канец пятай тыдні. І нагадаем, што ў мінулы раз мы пачаў шукаць у дадзеных аматар структуры, якія пачалі вырашаць праблемы, якія пачалі ўводзіць новыя праблемы, але ключом да гэтага быў свайго роду разьбы, што мы пачаў рабіць ад вузла да вузла. Так што гэта, вядома, аднакратна звязаны спіс. І односвязанны, Я маю на ўвазе ёсць толькі адзін нітка паміж кожным з гэтых вузлоў. Аказваецца, можна зрабіць аматар рэчы, як двойчы звязаныя спісы у выніку чаго ў вас ёсць стрэлка адбываецца ў абодвух напрамках, што можа дапамагчы з некаторымі эфектыўнасці. Але гэта вырашыць праблему? Якія праблемы гэта вырашыць так? Чаму мы клапоцімся ў панядзелак? Чаму, у тэорыі, так і мы клапоцімся ў панядзелак? Што ён робіць? 

АЎДЫТОРЫЯ: Мы можам дынамічна змяніць яе памер. 

СПІКЕР 1: Такім чынам, мы можам дынамічна змяніць яе памер. Малайцы вас абодвух. Такім чынам, вы можаце дынамічна змяняць памер гэтага Структура дадзеных, у той час як масіў, водгук, вы павінны ведаць апрыёры, колькі месца вы хочаце і калі вам трэба крыху больш прастору, ты быццам не пашанцавала. Вы павінны стварыць зусім новы масіў. Вы павінны рухацца усе вашы дадзеныя аднаго да іншага, у рэшце рэшт вызваліць стары масіў калі вы можаце, а затым працягнуць. Якія толькі адчувае сябе вельмі дорага і вельмі неэфектыўна, і гэта сапраўды можа быць. Але гэта яшчэ не ўсё добра. Мы плацім цану, што было адным з больш відавочных коштаў мы плаціць з дапамогай звязанага спісу? 

АЎДЫТОРЫЯ: Мы павінны выкарыстоўваць падвойнае прастору для кожнага з іх. СПІКЕР 1: Так, так што мы павінны па меншай меры, у два разы больш прасторы. На самай справе, я зразумеў, што гэта з малюнка нават трохі ўводзіць у зман, таму што на CS50 IDE ў шмат сучасных кампутары, паказальнік або адрас на самай справе не чатыры байта. Гэта вельмі часта гэтыя дзён восем байт, якія азначае самы ніжні прастакутнікі там у рэальнасці з'яўляюцца свайго роду два разы вялікі, як тое, што я намаляваў, што азначае, што вы выкарыстоўваеце ў тры разы шмат месца, як мы маглі б у адваротным выпадку. Цяпер у той жа час, мы яшчэ гаворым байт, праўда? Мы не гаворым абавязкова мегабайтах або гігабайтах, калі гэтых структур дадзеных не атрымаць вялікі. 

І таму сёння мы пачынаем разглядаць як мы маглі б даследаваць дадзеныя больш эфектыўна, калі ў факт, што дадзеныя становіцца больш. Але давайце паспрабуем кананізаваць Першыя аперацыі што вы можаце зрабіць на іх віды структур дадзеных. Так нешта накшталт звязана Спіс у цэлым падтрымлівае Аперацыі падабаецца выдаліць, ўставіць, і пошук. І што я маю на ўвазе, што? Гэта проста азначае, што звычайна калі людзі выкарыстоўваюць звязаны спіс, яны ці хто-то яшчэ рэалізаваны функцыі, такія як выдаленне, устаўка, і пошук, так што вы можаце на самай справе нешта зрабіць карысна са структурай дадзеных. Такім чынам, давайце зірнем на тое, як мы маглі б рэалізаваць некаторы код для звязанага спісу наступным чынам. 

Так што гэта толькі некаторыя З-код, нават не поўная праграма што я сапраўды хутка збудаваў. Гэта не онлайн ў размеркаванні Код, таму што ён не будзе рэальна працаваць. Але звярніце ўвагу, Я толькі з каментаром сказаў, кропка кропка кропка, ёсць нешта там, кропка кропка кропка, што-то там. І давайце проста паглядзім на тое, што сакавітыя часткі. Так што на трэцяй лініі, Нагадаем, што гэта цяпер Мы прапанавалі абвясціць вузел апошні Час, адзін з тых прастакутных аб'ектаў. Ён мае Int, што мы назавем N, але мы маглі б назваць гэта што-небудзь, а затым структура вузла зорка называецца побач. І толькі, каб быць ясным, што ў другім лінія, на шостым радку, што гэта такое? Што ён робіць для нас? Таму што, вядома, выглядае больш загадкавымі, чым нашы звычайныя зменныя. 

АЎДЫТОРЫЯ: Гэта прымушае яго рухацца па адным. 

СПІКЕР 1: прымушае яго рухацца па адным. І калі быць больш дакладным, ён будзе захоўваць адрас вузла, які прызначаецца, каб быць семантычна побач з ім, праўда? Так што не збіраецца абавязкова рухацца нічога. Гэта проста будзе захоўваць значэнне, якое будзе адрас нейкага іншага вузла, і вось чаму мы сказалі структура вузел зорка, зорка, які пазначае паказальнік або адрас. ОК, так што зараз калі выказаць здагадку, што мы маем гэта N даступныя для нас, і давайце Выкажам здагадку, што хто-то яшчэ ўстаўляецца цэлую кучу цэлых лікаў у звязаным спісе. І, што звязана спіс паказвае нейкі момант пераменная называецца спіс, што гэта прайшоў тут у якасці параметру, як я магу ісці аб лініі 14 ажыццяўленні пошуку? Іншымі словамі, калі я рэалізую Функцыя, мэта якога ў жыцці гэта прыняць Int і затым пачатак звязанага спісу, што паказальнік на звязаны спіс. Як першыя, хто я думаю, Дэвід быў наш валанцёр у панядзелак, ён, паказваючы на ўся звязаны спіс, Гэта як калі б мы перадаем Дэвід, як наш аргумент тут. Як мы можам ісці аб праходжанні гэты спіс? Што ж, аказваецца, што, хоць паказальнікі з'яўляюцца адносна новымі ў цяперашні час для нас, мы можам зрабіць гэта адносна прама. 

Я збіраюся ісці наперад і абвясціць часовую зменную, што па пагадненні толькі збіраецца каб назваць паказальнік, або PTR, але вы маглі б назваць гэта ўсё, што вы хочаце. І я збіраюся ініцыялізацыі гэта ў пачатку спісу. Такім чынам, вы можаце б думаю гэта а мне настаўніка днях, выгляд, паказваючы на ​​кагосьці сярод нашых людзей у якасці добраахвотнікаў. Так што я часовую зменную, што гэта проста паказваючы на ​​тое ж самае што наш супадзенні імя Праца на грамадскіх пачатках Давід паказваў. Цяпер у той час як паказальнік ня нулявы, таму што водгук што нулявая некаторыя асаблівае значэнне вартавога размяжоўвае канец спісу, так што пакуль я не паказваючы на зямля, як наш апошні валанцёр было, давайце ісці наперад і выканайце наступныя дзеянні. Калі pointer-- і цяпер я як бы хачу рабіць тое, што мы зрабілі з вучнем structure-- калі паказальнік кропка побач equals-- хутчэй, калі паказальнік кропка N роўны роўная пераменная N, то Аргумент, які быў прыняты ў, то я хачу, каб ісці наперад і сказаць, вярнуцца праўда. Я знайшоў нумар N ўнутры адзін з вузлоў майго звязанага спісу. Але больш за кропка не працуе ў дадзеным кантэксце, таму што паказальнік, PTR, гэта сапраўды паказальнік, адрас, мы на самай справе можам цудоўна выкарыстоўваць нарэшце кавалак сінтаксісу што выгляд робіць інтуітыўнае пачуццё, а на самай справе выкарыстоўваць стрэлку тут, што азначае, ідуць ад што зварот да цэлага там ст. Так што гэта вельмі падобна на дух аператара кропка, а таму, што паказальнік не з'яўляецца паказальнікам і сам па сабе не фактычны структура, мы проста выкарыстоўваць стрэлку. 

Так што, калі бягучы вузел, што Я, часовая пераменная, я, паказваючы на ня N, тое, што я хачу зрабіць? Ну, з маім добраахвотніках што ў нас тут на днях, калі мой першы чалавек не той, які я хачу, і, магчыма, другі чалавек не што я хачу, і трэці, я трэба трымаць фізічнага перамяшчэння. Як як я крок праз спіс? Калі мы былі масіў, вам толькі што зрабіў, як я плюс плюс. Але ў дадзеным выпадку, досыць зрабіць паказальнік, атрымлівае, паказальнік, побач. Іншымі словамі, наступнае поле гэта, як і ўсе левай рукі што нашы добраахвотнікі ў панядзелак выкарыстоўвалі, каб паказаць на нейкай іншай вузел. Тыя былі іх бліжэйшыя суседзі. 

Так што, калі я хачу, каб прайсці праз гэты спіс, Я не магу проста зрабіць я плюс плюс больш, Я замест гэтага сказаць Я, паказальнік, будзе роўным незалежна ад наступнага поля, Наступнае поле, наступнае поле, пасля ўсіх гэтых левай рукі што ў нас на сцэне, паказваючы у некаторых наступных значэнняў. І калі я праз што ўся ітэрацыя, І, нарэшце, я ўдарыў пусты, не маючы знайшоў яшчэ N, я проста вярнуцца ілжывым. Такім чынам, яшчэ раз, усё, што мы робім тут, у адпаведнасці з карціны хвіліну назад, пачынае, паказваючы на пачатку спісу меркавана. І тады я правяраю, гэта значэнне Я шукаю роўна дзевяці? Калі гэта так, я вяртаюся праўда, і я зрабіць. Калі няма, то я абнавіць маю руку, АКА паказальнік, каб паказаць на месцы на наступны стрэлы, і тое месца ў наступным Эрроу, і ў наступным. Я проста ішоў праз гэты масіў. 

Такім чынам, яшчэ раз, хто клапоціцца? Падабаецца тое, што гэта інгрэдыент для? Ну, памятаеце, што мы ўвялі паняцце стэка, які гэта ўвесці абстрактны дадзеныя, паколькі гэта не з'яўляецца З, што, гэта не CS50 рэч, гэта абстрактная ідэя, гэта ідэя кладка рэчаў на верхняй частцы адзін з адным , Якія могуць быць рэалізаваны ў пучкі рознымі спосабамі. І адзін са спосабаў мы прапанавалі была з масіў, або са звязаным спісам. І атрымліваецца, што кананічна, А Стэк падтрымлівае, па меншай меры дзве аперацыі. І Buzz словы штуршок, каб націснуць нешта ў стэк, як новы латок ў сталовая, ці поп, гэта азначае, каб выдаліць верхні латок з стэка ў сталовай зала, а затым, магчыма, некаторыя іншыя аперацыі, а таксама. Так як мы маглі б вызначыць структуру што мы зараз выкліку стэк? 

Ну, у нас ёсць усё неабходнае ўмова Сінтаксіс ў нашым распараджэнні ў С. я кажу, даць мне вызначэнне тыпу ў на структуру ўнутры чаркі, Я хачу сказаць, гэта масіў, у А цэлая куча лічбаў, а затым памер. Такім чынам, іншымі словамі, калі я хачу ажыццявіць гэта ў кодзе, дазвольце мне пайсці і проста выгляд маляваць тое, што гэта кажа. Такім чынам, гэта кажа, дайце мне Структура, што ёсць масіў, і я не ведаю, што магутнасць, гэта па-відаць некаторая канстанта, што я вызначаюцца ў іншым месцы, і гэта нармальна. Але выкажам здагадку, гэта ўсяго толькі адзін, два, тры, чатыры, пяць. Так магутнасць 5. Гэты элемент ўнутры майго Структура будзе называцца лік. А потым мне патрэбен па-відаць, іншай зменнай называецца памер, які першапачаткова я збіраюся агаворваць усталёўваецца на нуль. Калі няма нічога стэк, памер роўны нулю, і гэта значэння смецця ў лічбах. Я паняцця не маю, што там проста няма. 

Так што, калі я хачу, каб падштурхнуць то ў стэк, Мяркую, я выклікаць функцыю штуршок, і Я кажу націснуць 50, як і лік 50, дзе вы маглі б прапанаваць Я малюю яго ў гэтым масіве? Там у пяць розных магчымых адказаў. Дзе вы хочаце, каб падштурхнуць лік 50? Калі мэта тут, зноў жа, называем Функцыя штуршок, праходзяць у якасці аргументу 50, дзе я паклаў яго? Пяць possible-- 20% шанец гадаць правільна. Да? 

АЎДЫТОРЫЯ: Далёкі права. 

СПІКЕР 1: Далёкі права. Існуе ў цяперашні час 25% шанец гадаць правільна. Так што будзе на самой справе будзе ў парадку. Паводле пагаднення, я скажу з масівам, мы, як правіла, пачынаюць з левай, але мы, безумоўна, можа пачаць з правай. Такім чынам, спойлер тут будзе я верагодна, збіраецца прыцягнуць яго злева, Як і ў звычайным масіве дзе Я пачаць рухацца злева направа. Але калі вы можаце перавярнуць арыфметычнае, выдатна. Гэта проста не звычайны. ОК, мне трэба, каб зрабіць адзін больш змяненняў, хоць. Цяпер, калі я штурхнуў нешта стэк, што далей? 

Добра, у мяне ёсць, каб павялічыць памер. Такім чынам, дазвольце мне ісці наперад і проста абнавіць гэта, які быў роўны нулю. І замест таго, у цяперашні час, я іду пакласці ў кошту аднаго. А цяпер выкажам здагадку, я націскаю іншую Колькасць у стэк, як 51. Ну, я павінен зрабіць яшчэ адзін змена, якое да памеру двух. А потым думаю, я націскаю яшчэ адзін Колькасць у стэк, як 61, Цяпер мне трэба, каб абнавіць яшчэ адзін памер час і атрымаць значэнне 3 у якасці памеру. І цяпер, я называю поп-музыкі. Цяпер поп, па пагадненні, не прымаць аргумент. Са стэкам, уся кропка метафары латок з'яўляецца тое, што вы не па сваім меркаванні пайсці атрымаць гэты латок, усё можна зрабіць поп верхні адзін з стэк, толькі таму, што. Гэта тое, што гэтая структура дадзеных робіць. 

Такім чынам, гэтай логіцы, калі я кажуць поп, тое, што прыходзіць ад? Так 61. Так што на самай справе кампутар збіраемся рабіць у памяці? Што мой код трэба зрабіць? Што вы маглі б прапанаваць мы мяняем на экране? Што павінна змяніцца? На жаль? Так мы пазбавімся ад 61. Так што я магу дакладна зрабіць. І я магу пазбавіцца ад 61. І тады тое, што іншыя змяненне павінна адбыцца? Памер, верагодна, мае вярнуцца да двух. І так, што ўсё ў парадку. Але пачакайце хвіліну, памер Хвіліну таму было тры. Давайце проста зрабіць хуткую праверку наяўнасці свядомасці. Як мы ведаем, што мы хацеў, каб пазбавіцца ад 61? Таму што мы з'яўляцца. І таму ў мяне ёсць гэты другі памер уласнасці. 

Пачакай, я успамінаючы другога тыдня калі мы пачалі казаць пра масівы, дзе гэта месца нулявы, гэта было месца адно, гэта было месца два, гэта размяшчэнне тры, чатыры, гэта выглядае як ўзаемасувязь паміж памерам і элемент, які я хачу, каб выдаліць з масіва, здаецца, проста што? Памер мінус адзін. І вось як, як людзі мы ведаем, 61 на першым месцы. Як гэта кампутар будзе ведаць? Калі ваш код, дзе вы, верагодна хачу зрабіць памер мінус адзін, так трох мінус адзін роўна двум, і што азначае, што мы хочам, каб пазбавіцца ад 61. І тады мы сапраўды можам абнавіць памер так, каб памер у цяперашні час ідзе ад трох да двух. І толькі, каб быць педантычным, я збіраюся выказаць здагадку, што я зрабіў, праўда? Вы інтуітыўна прапанаваў правільна я павінен пазбавіцца ад 61. Але не я накшталт накшталт пазбавіліся ад 61? Я забыўся эфектыўна што гэта на самай справе ёсць. І ўспомніце PSET4, калі вы чыталі артыкул аб судова-медыцынскай экспертызы, то ў фармаце PDF што ў нас, вы, хлопцы чытаць, ці вы будзе чытаць на гэтым тыдні PSET4. Нагадаем, што гэта на самай справе дарэчныя для ўся ідэя кампутарнай экспертызы. Што кампутар наогул робіць гэта ён проста забывае, дзе нешта, але гэта не пайшлі і, як паспрабаваць падрапаць яго ці пераазначэнне гэтыя біты з нулёў і адзінак або некаторы іншы выпадковым чынам калі вы самі не робяць гэта свядома. Так ваша інтуіцыя была Добра, давайце пазбавіцца ад 61. Але на самой справе, мы не павінны турбавацца. Нам проста трэба забываць, што гэта там, змяніўшы наш памер. 

Зараз ёсць праблема з гэтым стэкам. Калі я штурхаць рэчы стэк, што Відавочна, адбудзецца За некалькі момантаў часу? Мы збіраемся запусціць з космасу. І што нам рабіць? Мы накшталт нітах. Гэтая рэалізацыя не дазваляе нам памер масіва, таму што з дапамогай гэты сінтаксіс, калі вы ўспомніце другога тыдня, калі вы абвясцілі памер масіва, мы не бачылі механізм яшчэ дзе Вы можаце змяніць памер масіва. І на самай справе З не маюць гэтую функцыю. Калі вы кажаце, дайце мне пяць Nths, называюць іх лік, гэта ўсё, што вы збіраецеся атрымаць. Такім чынам, мы цяпер рабіць, як панядзелак, ёсць здольнасць выказваць рашэнне хоць, мы проста трэба наладзіць вызначэнне нашай стэка каб ня быць некаторых жорстка масіў, а проста захоўваць адрасы. 

Цяпер, чаму гэта? Цяпер мы проста павінны быць камфортна з той факт, што, калі працуе мой праграмы, Я, верагодна, збіраецца павінны спытаць чалавека, колькі нумароў вы хочаце захаваць? Такім чынам, уваход павінен аднекуль. Але як толькі я ведаю, што лік, то я магу толькі выкарыстоўваць тое, што працаваць, каб даць мне кавалак памяці? Я магу выкарыстоўваць Таноса. І я магу сказаць, любую колькасць байт я хачу вярнуцца на гэтыя Nths. І ўсё, што трэба захоўваць у лічбах Пераменная тут ўнутры гэтай структуры павінна быць што? Што на самой справе адбываецца ў Лічбы ў гэтым выпадку? Так, гэта паказальнік на першы байт гэтага кавалка памяці, або, больш канкрэтна, адрас з першых з гэтых байт. Не мае значэння, калі гэта адзін байт або байт, млрд Мне проста трэба, каб клапаціцца аб першай. Таму што тое, што Таноса гарантыі і мае аперацыйнай сістэмы гарантый, з'яўляецца тое, што кавалак памяці I атрымаць, ён збіраецца быць сумежнымі. Там не будзе прабелаў. Так што, калі я папрасіў 50 байт або 1000 байт, яны ўсё будзе спіна да спіны да спіны. І так доўга, як я памятаю, як вялікі, як шмат я папрасіў, усе мне трэба ведаць першы такі адрас. 

Так што цяпер у нас ёсць магчымасць у кодзе. Хоць і ён збіраецца ўзяць нас больш часу, каб напісаць гэтую гульню, мы маглі зараз пераразмеркаваць гэтую памяць проста захоўваць розныя адрасы ёсць калі мы хочам, каб больш або нават менш кавалак памяці. Дык вось, каб кампраміс. Цяпер мы атрымліваем дынаміку. У нас яшчэ ёсць contiguousness я сцвярджаючы. Таму Таноса дасць нам бесперапынны кавалак памяці. Але гэта будзе боль у шыя для нас, праграміст, на самай справе код да. Гэта проста больш працы. Мы павінны код падобна таму, што я быў стукаць з усяго імгненне таму. Вельмі выканальна, але гэта дадае складанасці. І так раз распрацоўшчык, праграміст Час яшчэ адзін рэсурс што мы маглі б трэба марнаваць некаторы час, каб атрымаць новыя магчымасці. І тады, вядома, ёсць чэргі. Мы не будзем спыняцца на гэтым адным вельмі падрабязна. Але гэта вельмі падобна па духу. Я мог бы рэалізаваць чаргу, і яго адпаведныя аперацыі, Ставіць ці з чаргі, як дадаць або выдаліць, гэта проста аматар спосаб сказаць гэта, Ставіць ці з чаргі, як след. Я магу толькі даць сабе-структуру што зноў ёсць масіў шэрагу, у што зноў мае памер, але чаму цяпер мне трэба адсочваць пярэдняй чарзе? Я не ведаю, трэба пярэдняя майго стэка. Ну, калі я зноў для queue-- давайце проста цяжка яго код як якія маюць, як пяць цэлыя лікі ў тут патэнцыйна. Такім чынам, гэта нуль, адзін, два, тры, чатыры. Гэта будзе званыя зноў нумары. І гэта будзе называцца памер. 

Чаму гэта не дастаткова мець толькі памер? Ну, давайце штурхаць гэтыя ж лічбы на. Так што я pushed-- я ў чаргу, або штурхнуў. Цяпер я ў чаргу 50, а затым 51, а затым 61, і кропка кропка кропка. Дык вось паставіць у чаргу. Я ў чарзе 50, то 51, то 61. І, што выглядае ідэнтычна у Стэк да гэтага часу, акрамя мне трэба зрабіць адно змяненне. Мне трэба, каб абнавіць гэты памер, так што я іду ад нуля да адзінкі да двух-трох Цяпер. Як з чаргі? Што адбываецца з DEQUEUE? Хто павінен прыйсці з гэтага спісу ў першую чаргу калі гэта лінія на Apple Store? Так 50. Так што гэта свайго роду складаней ў гэты раз. У той час як апошні раз гэта было супер проста, каб проста рабіць памер мінус адзін, Я да канца майго масіва эфектыўна дзе лічбы, гэта здымае 61. Але я не хачу, каб выдаліць 61. Я хачу ўзяць 50, якія быў там у 05:00 выбудоўвацца для Новы iPhone або яшчэ шмат чаго. І так, каб пазбавіцца ад 50, я не можаце проста зрабіць гэта, ці не так? Я магу выкрасліць 50. Але мы толькі што сказалі, мы не павінны быць настолькі анальны каб выдрапаць або схаваць дадзеныя. Мы можам проста забыцца, дзе яна ёсць. 

Але калі я магу змяніць мой памер цяпер два, гэта досыць інфармацыі каб ведаць, што адбываецца ў маёй чарзе? Не зусім. Як мой памер у два, але дзе ж чарзе пачынаюць, асабліва калі я да гэтага часу тыя ж нумары ў памяці. 50, 51, 61. Таму мне трэба памятаць, Цяпер, калі фронт. І такім чынам, я прапанаваў да там, мы толькі што называецца N-й фронт, чый першапачатковы Значэнне павінна быць што? Нуль, толькі пачатак спісу. Але цяпер у дадатак да памяншаючы памер, мы проста павялічваем фронт. Цяпер вось іншая праблема. Таму, як толькі я ўвесь час. Выкажам здагадку, што гэты лік як 121, 124, а затым, чорт вазьмі, Я з космасу. Але пачакайце хвіліну, я не з'яўляюся. Такім чынам, на дадзены момант у гісторыі, Выкажам здагадку, што памер аднаго, двух, тры, чатыры, так што выкажам здагадку, што памер чатыры, пярэдняя адна, так 51 на фронце. Я хачу паставіць яшчэ адзін нумар тут, але, чорт вазьмі, я з космасу. Але я не вельмі, ці не так? Дзе я магу паставіць некаторыя дадатковая кошт, як 171? Так, я мог толькі збольшага вярнуцца туды, праўда? А потым закрэсліць 50, або проста перапісаць яго з 171. І калі вам цікава, чаму нашы нумары атрымаў так выпадкова, яны звычайна прынята кампутар навука курсы ў Гарвардзе пасля CS50. Але гэта быў добры аптымізацыя, таму што цяпер я не марнаваць прастору. Я да гэтага часу павінны памятаць, наколькі вялікая гэтая рэч агульная. Гэта пяць за ўсё. Таму што я не хачу, каб пачаць перазапіс 51. Так што цяпер я па-ранейшаму з космасу, гэтак жа праблема, што і раней. Але вы можаце ўбачыць, як у цяперашні час у кодзе, вы, верагодна, трэба напісаць трохі больш Складанасць, каб гэта адбылося. І на самай справе, тое, што аператар у З, верагодна, дазваляе Вы чароўным зрабіць гэта круглявасць? Ды аператар па модулю, знак адсотка. Так што крута пра чэргі, хоць мы захаваць малюнак масівы як гэтыя, як прамых, калі вы выгляд думаю пра гэта, як выгібу вакол, як кола, то проста інтуітыўна выгляд працы разумова Я думаю, што крыху чысцей. Вы ўсё роўна прыйдзецца ажыццяўляць што ментальная мадэль у кодзе. Так што не так ужо цяжка, у канчатковым рахунку, рэалізацыі, але мы па-ранейшаму губляюць размер-- хутчэй, Магчымасць змяняць памер, калі мы не зробім гэта. 

Мы павінны пазбавіцца ад масіва, мы замяніць яго з аднаго паказальніка, а затым дзе-то ў маім кодзе я атрымаў патэлефануеце, якія функцыі на самай справе стварыць масіў званыя лічбы? Маллок, або іншыя падобныя Функцыя, дакладна. Любыя пытанні па стэкаў або чэргаў. Да? Добры пытанне. Што б вы модулю выкарыстоўваць тут. Так як правіла, пры выкарыстанні мод, вы маглі б зрабіць гэта з памерам Уся структура дадзеных. Так нешта накшталт пяці або ёмістасць, калі гэта пастаянная, верагодна удзел. Але толькі рабіць па модулю пяць верагодна, не з'яўляецца дастатковым, таму што мы павінны ведаць, рабіць мы абгарнуць вакол тут або тут або тут. Такім чынам, вы, верагодна, таксама захоча прыцягнуць памер рэчы або пярэдняя пераменная, а таксама. Так што гэта проста гэта адносна простае арыфметычнае выраз, але па модулю будзе ключавым элементам. 

Так кароткі фільм, калі вы будзеце. Анімацыя, што некаторыя Людзі ў іншым універсітэце сабраць, што мы прыстасаваныя для гэтай дыскусіі. Яна ўключае ў сябе Джэк навучання Факты пра чэргаў і статыстыкі. 

ФІЛЬМ: Даўным-даўно, быў хлопец па імені Джэк. Калі справа дайшла да прыняцця сябрамі, Джэк не маюць спрыту. Так Джэк пайшоў пагаварыць з Найбольш папулярны хлопец ведаў. Ён пайшоў да Лу і спытала, што мне рабіць? Лу ўбачыў, што яго сябар быў сапраўды засмучаны. Ну, ён пачаў, толькі паглядзіце, як вы апранутыя. Ці няма ў вас якія-небудзь вопратку з другога выгляд? Так, сказаў Джэк. Я ўпэўнены, што рабіць. Прыходзьце ў мой дом і Я пакажу іх вам. Такім чынам, яны адправіліся ў Джэка. І Джэк паказаў Лу акно дзе ён захоўваў усе свае кашулі, і штаны, і шкарпэткі. Лу сказаў, я бачу, у вас ёсць усе вашыя адзення ў кучу. Чаму б вам не насіць некаторыя іншыя раз у некаторы час? 

Джэк сказаў, добра, калі я выдаліць вопратку і шкарпэткі, Я мыць іх і пакласці ім далёка ў поле. Затым наступае наступны раніцай, і да я скачу. Я іду ў поле і атрымаць мая адзенне з верхняй. Лу хутка зразумеў, праблема з Джэкам. Ён працягваў адзенне, CD, і кнігі ў стэку. Калі ён пацягнуўся за то чытаць ці насіць, ён выбраць верхнюю кнігу або ніжняе бялізну. Потым, калі ён быў зроблены, ён будзе пакласці яго назад. Вярнуцца яна будзе ісці на вяршыні стэка. Я ведаю, што рашэнне, сказаў пераможны Гучна. Вы павінны навучыцца пачаць выкарыстоўваць чарзе. Лу ўзяў вопратку Джэка і павесіў у шафу. І калі ён спустошыў скрынка, ён проста кінуў яе. 

Тады ён сказаў, цяпер Джэк, у канцы дзень, пакласці вопратку злева калі вы кладзе іх. Тады заўтра раніцай, калі вам см сонцам, атрымаць вопратку на права, з канца радка. Хіба вы не бачыце? сказаў Лу. Гэта будзе так прыемна. Вы будзеце насіць усё адразу перш чым вы носіце нешта ў два разы. І з усім у чэргах у шафе і шэльфа, Джэк пачаў адчуваць досыць упэўнены ў сабе. Усё дзякуючы Лу і яго выдатны чарзе. СПІКЕР 1: Добра, гэта цудоўна. Так што было на самай справе адбываецца на пад капотам цяпер? Што мы маем паказальнікі, што ў нас ёсць Таноса, што ў нас ёсць магчымасць стварыць кавалкі памяці для сябе дынамічна. Так што гэта карціна, якую мы убачыў толькі на днях. Мы сапраўды не спыняцца на ім, але гэтая карціна мае ўжо на пад капот ўжо некалькі тыдняў. І так гэта ўяўляе, проста прастакутнік, які мы намалявалі, памяці кампутара. І, магчыма, ваш кампутар або CS50 ID, мае гігабайт аператыўнай памяці або памяці ці два гігабайта ці чатыры. Гэта сапраўды не мае значэння. Ваша аперацыйная сістэма Вокны ці Mac OS або Linux, па сутнасці дазваляе вашай праграмы думаць, што ён мае доступ да ўсёй памяці кампутара, нават калі вы маглі б быць запушчаны некалькі праграм адразу. Такім чынам, у рэчаіснасці, што на самой справе не працуе. Але гэта свайго роду ілюзія улічваючы ўсе вашы праграмы. Так што, калі ў вас ёсць два гігабайтамі аператыўнай памяці, гэта як кампутар можа думаць пра гэта. 

Цяпер па супадзенні, адзін з іх рэчы, адзін з гэтых сегментаў памяці, называецца стэк. І на самай справе ў любы час да гэтага часу ў напісанні кода што вы назвалі Функцыя, напрыклад, магістралі. Нагадаем, што ў любы час я маю Намаляваныя памяці кампутара, Я заўсёды прыцягваюць роду палова прамавугольніка тут і не турбаваць казаць пра тое, што гэта вышэй. Таму што, калі галоўны называецца, я сцвярджаю, што вы атрымаеце гэта кавалачак памяці што ідзе сюды. І калі асноўная функцыя называецца як своп, а своп ідзе тут. І аказваецца, што гэта дзе ён у канчатковым выніку. На тое, што называецца стэкам ўнутры памяці кампутара. Цяпер у канцы дня, гэта проста звяртаецца. Гэта як нулявым байт, байт адным, байт 2 млрд. Але калі вы думаеце пра гэта як гэта прастакутны аб'ект, усё, што мы робім кожны Час мы называем функцыя отводка новы кавалачак памяці. Мы даем гэтую функцыю кавалачак яго ўласнай памяці, каб працаваць з. 

І зараз ўспомніць, што гэта важна. Таму што, калі ў нас ёсць нешта накшталт абмену і дзве лакальныя зменныя, такія як А і В і мы мяняем гэтыя значэння з аднаго і двух да двух і адной, нагадаем што калі падпампоўкі вяртаецца, Гэта як калі б гэтага кавалачка з памяці толькі што. У рэчаіснасці, яна па-ранейшаму ёсць крыміналістычнага. І нешта яшчэ на самай справе ёсць. Але канцэптуальна, гэта, як хоць гэта цалкам зніклі. І так асноўнай не ведаю ні аб працы што было зроблена ў гэтай функцыі падпампоўкі, калі гэта не на самай справе прайшло ў тых Аргументы па паказальніку або па спасылцы. Цяпер, фундаментальнае рашэнне да гэтай праблемы з своп Праходзіць рэчы ў па адрасе. Але, аказваецца, таксама што ўжо на вышэй той частцы прамавугольніка ўвесь гэты час пакуль ёсць больш памяці там. І калі вы дынамічна вылучыць памяць, няхай гэта будзе ўнутры GetString, які мы рабілі для вас у CS50 бібліятэка, або калі вы, хлопцы, патэлефанаваць і спытаць Таноса аперацыйная сістэма кавалак памяці, ён не прыходзіць з стэка. Ён пастаўляецца з іншага месца ў памяці кампутара што называецца кучай. І гэта нічым не адрозніваецца. Гэта тое ж самае АЗП. Гэта ж памяць. Гэта проста АЗП гэта да там замест тут. 

І так што ж гэта значыць? Ну, калі ваш кампутар мае канчатковае колькасць памяці і стэк расце ўверх, так казаць, і куча, па у гэтым стрэлкі, расце ўніз. Іншымі словамі, кожны выкліку Таноса, Вы надаецца кавалачак памяці зверху, то, магчыма, трохі ніжэй, то трохі ніжэй, кожны раз, калі вы тэлефануеце Таноса, куча, яго выкарыстанне, з'яўляецца свайго роду расце, расце бліжэй і бліжэй да чаго? Стэк. Так што гэта, здаецца, як добрая ідэя? Я маю на ўвазе, дзе гэта не зусім ясна што яшчэ можна зрабіць, калі толькі вы ёсць канчатковае колькасць памяці. Але гэта, безумоўна, дрэнна. Гэтыя два стрэлы на Інтэнсіўны курс для аднаго. 

І атрымліваецца, што дрэнны хлопец, людзі, якія асабліва добра з праграмаваннем, і спрабуе ўзламаць кампутары, могуць выкарыстоўваць гэтую рэальнасць. На самай справе, давайце разгледзім трохі фрагмент. Такім чынам, гэта з'яўляецца прыкладам вы можаце прачытаць пра больш падрабязна ў Вікіпедыі. Мы пакажу вам на Артыкул калі цікава. Але ёсць напад ў цэлым вядомы як перапаўненне буфера, што існуе да тых часоў, як людзі мелі магчымасць маніпуляваць памяці кампутара, асабліва на C. Так што гэта вельмі адвольная праграма, але давайце чытаць знізу ўверх. Галоўная ў ARGC сімвал зоркі ARGV. Так што гэта праграма, якая прымае Аргументы каманднага радка. І ўсё ж галоўная, мабыць, выклік функцыя, назавем яго для прастаты F. І гэта праходзіць у чым? ARGV аднаго. Так яна пераходзіць у F ўсе слова тое, што карыстальнік увёў у радку пасля таго, Назва праграмы наогул. Гэтак жа, як Цэзар або Vigenere, які Вы маглі б успомніць, робіць з ARGV. 

Так што F? F падае ў радку ў якасці адзінага аргументу, АКА паўкокс зорка, ж рэч, як радок. І гэта называецца як заўгодна бар у гэтым прыкладзе. І тады сімвал з 12 толькі з пункту гледжання непрафесіяналы, што сімвал з дужка 12 робіць для нас? Што ён робіць? Вылучэнне памяці, спецыяльна 12 байта для 12 знакаў. Дакладна. І тады апошняя радок, змяшаць і копія, вы, верагодна, не бачыў. Гэта радок копія Функцыя, мэта якога ў жыцці гэта скапіяваць яго другі аргумент у якасці першага аргументу, але толькі да Пэўную колькасць байтаў. Такім чынам, трэці аргумент кажа, колькі байт неабходна скапіяваць? Даўжыня панэлі, усе карыстач уводзіць ст. І ўтрыманьне бар, гэты радок, з'яўляюцца скапіяваныя ў памяць паказаў на кропцы С. 

Так што гэта, здаецца, свайго роду дурное, і гэта. Гэта надуманы прыклад, але гэта прадстаўнік класа вектараў атакі, спосаб нападу на праграму. Усё добра і выдатна, калі карыстальнік тыпы ў словы, што гэта 11 сімвалаў або менш, плюс зваротны слеш нуля. Што рабіць, калі карыстальнік ў больш чым 11 або 12 або 20 або 50 сімвалаў? Што гэтая праграма будзе рабіць? Патэнцыйна SEG віна. Гэта адбываецца слепа капіяваць усё ў бары да яго даўжыні, якая літаральна ўсё ў бары, у адрас паказаў на С. Але З толькі прэвентыўна даецца як 12 байт. Але няма дадатковай праверкі. Там, калі умовах гэта няма. Там няма праверкі памылак тут. 

І так, што гэтая праграма збіраюся зрабіць, гэта проста слепа скапіяваць адно да іншага. І таму, калі мы гэта зрабіць як карцінка, вось проста кавалачак прасторы памяці. Так заўважыць на дне, мы ёсць лакальная пераменная бар. Так, што паказальнік, які збіраецца store-- а гэтай лакальнай аргументу, што гэта збіраецеся захоўваць радок бар. І звярніце ўвагу на тое як раз вышэй, у стэку, таму што кожны раз вы просіце на памяць у стэку, яна ідзе трохі над ім наглядна, Звярніце ўвагу, што ў нас ёсць 12 байт там. Верхні левы адзін кранштэйн З нуля і ніжні правы адзін кранштэйн З 11. Вось толькі, як кампутары збіраецца закласці яго. Так што проста інтуітыўна, калі бар мае больш чым 12 знакаў у агульнай складанасці, у тым ліку зваротны слеш нуль, дзе знаходзіцца 12 або З 12 кранштэйн збіраецца ісці? Ці, хутчэй, дзе 12-й сімвал або 13 сімвалаў, соты персанаж збіраецца у канчатковым выніку на малюнку? Вышэй або ніжэй? 

Правільна, таму што, хоць сам стэк расце ўверх, як толькі вы пакласці рэчы ў гэта, яна па канструктыўных прычынах, ставіць памяць зверху данізу. Так што, калі ў вас ёсць больш, чым 12 байт, Вы збіраецеся пачаць перазапіс бар. Зараз гэта памылка, але гэта на самай справе не мае вялікага значэння. Але гэта вялікая справа, таму што ёсць больш рэчаў адбываецца ў памяці. Дык вось, як мы маглі б паклаў прывітанне, каб быць ясна. Калі я набраў у прывітанне ў камандным радку. Н-Е-Л-Л-О зваротны слеш нуль, заканчваецца ў гэтыя 12 байт, і мы супер бяспечна. Усё добра. Але калі я нешта тыпу больш, патэнцыйна гэта збіраецца поўзаць ў бар прасторы. Але яшчэ горш, аказваецца з усяго гэтага часу, хоць мы ніколі не казалі аб гэта, стэк выкарыстоўваецца для іншых рэчаў. Гэта не толькі лакальныя зменныя. 

З мовай вельмі нізкі ўзровень. І гэта свайго роду таемна выкарыстоўвае стэк таксама памятаць, калі Функцыя называецца тое, што адрас з'яўляецца папярэдняй функцыі, так што ён можа перайсці назад да гэтай функцыі. Таму, калі асноўныя выклікі памяняць, сярод рэчы ў стэк не толькі змяняе лакальныя зменныя, або яго аргументы, таксама таемна штурхнуў стэк, як прадстаўлена чырвоным лустачкай тут, гэта адрас галоўнай фізічна ў памяці кампутара, так што, калі своп будзе зроблена, кампутар ведае, што я павінен вярнуцца на галоўную і скончыць выкананне асноўнай функцыі. Так што гэта небяспечна зараз, таму што, калі карыстач уводзіць у добра больш чым прывітанне, такім чынам, што ўвод карыстальніка перавызначаем або перапісвае, што чырвоны раздзел, лагічна, калі кампутара проста хачу, каб слепа выказаць здагадку, што байт у гэтай чырвонай лустачку з'яўляюцца адрас, па якім ён павінен вярнуць, што, калі праціўнік досыць разумны, або пашанцавала паставіць паслядоўнасць байт там выглядае як адрас, але гэта адрас кода што ён ці яна хоча кампутар выканаць замест галоўнай? 

Іншымі словамі, калі тое, Карыстальнік друкуе ў камандным радку, гэта не толькі тое, бяскрыўдна, як прывітанне, але на самой справе гэта код, які эквівалентна выдаліць усе файлы гэтага карыстальніка? Або напішыце свой пароль мне? Або пачаць запіс іх націску клавіш, праўда? Існуе спосаб, давайце прадугледжваюць сёння, што яны маглі б увесці не толькі ў прывітанне свет ці іх назва, яны маглі істотна перайсці ў код, нулёў і тыя, што кампутар памылкі для кода і адрасы. Дык няхай і некалькі абстрактна, калі карыстач у досыць спаборнасці кода што мы будзем абагульняць тут А. А напад або праціўнікі. Так што дрэнныя рэчы. Мы не клапоцімся пра нумара або нулі або адзінкі сёння, напрыклад, што вы ў канчатковым выніку перазапісу, што чырвоны раздзел, заўважыць, што паслядоўнасць байт. Аб 835 З нуля восем нулёў. А цяпер, як артыкул Вікіпедыі тут прапанаваў, калі вы зараз на самай справе пачаць маркіроўка байты ў кампутары гадоў памяці, што артыкул Вікіпедыі прапаную, што, тое, што, калі адрас гэтай верхнім левым байта 80 З 0 3508. 

Іншымі словамі, калі дрэнны хлопец досыць разумны, з яго ці яе код на самай справе паставіць нумар тут, што адпавядае адрасе кода ён ці яна ўводзяць у кампутар, вы можа падмануць кампутар у робячы нічога. Выдаленне файлаў, электроннай пошты рэчы, нюхаць трафіку, літаральна нічога можа быць ўводзілі ў кампутар. І так перапаўненне буфера атака па сваёй сутнасці гэта проста глупства, па-дурному найважнейшая з масіва, не маюць яго мяжы правяраецца. І гэта тое, што гэта супер небяспечна і адначасова супер магутны у З, што мы сапраўды павінны доступ у любую кропку ў памяці. Гэта да нас, праграмістаў, хто піша зыходны код для праверкі даўжыні праклятую любога масівы, якія мы маніпулявання. Такім чынам, каб было ясна, што выпраўленне? Калі мы вярнуцца да гэтага Код, я не павінен проста змяніць даўжыню панэлі, тое, што яшчэ я павінен правяраць? Што яшчэ я павінен рабіць, каб прадухіліць гэта напад цалкам? Я не хачу, каб проста слепа сказаць што вы павінны скапіяваць столькі байт, а даўжыня панэлі. Я хачу сказаць, скапіруйце ў колькасць байт у радку да выдзеленая памяці, або 12 максімальна. Так што я патрэбны нейкі, калі ўмова што робіць праверыць даўжыню панэлі, але калі ён перавышае 12, мы проста жорсткі код 12 як максімальна магчымую адлегласць. У адваротным выпадку так званага буфера Перапаўненне напад можа адбыцца. У ніжняй часткі гэтых слайдаў, калі вам цікава даведацца больш фактычная арыгінальная артыкул калі вы хочаце, каб зірнуць. 

Але цяпер, сярод цэн заплаціў тут быў неэфектыўнасць. Так, каб было хутка нізкі ўзровень погляд на тое, што могуць узнікнуць праблемы ў цяперашні час, што мы мець доступ да памяці кампутара. Але іншая праблема, мы ўжо наткнуўся на панядзелак проста неэфектыўнасць з звязанага спісу. Мы вярнуліся да лінейнага часу. Мы больш не маюць бесперапынны спектр. Мы не маем адвольны доступ. Мы не можам выкарыстоўваць квадратны абазначэння кранштэйна. Мы літаральна павінны выкарыстоўваць той час як цыкл як адзін я напісаў некаторы час таму. Але ў панядзелак, мы сцвярджалі, што мы можам паўзці назад у царства эфектыўнасці дасягнення тое, што гэта лагарыфмічная можа быць, ці яшчэ лепш, можа быць, нават нешта, што гэта Так званы сталай часу. Так, як мы можам зрабіць гэта з дапамогай гэтых новых інструменты, гэтыя адрасы, гэтыя паказальнікі, і разьбы рэчы наш уласны? Ну, выкажам здагадку, што тут, гэта куча лікаў, якія мы хочам захаваць у Структура дадзеных і пошук эфектыўна. Мы можам абсалютна пераматаць тыдня два, кінуць іх у масіў, і шукаць іх з дапамогай бінарнага пошуку. Падзяляй і ўладар. І на самай справе вы напісалі бінарны пошук у PSET3, дзе вы рэалізавалі праграму знайсці. Але вы ведаеце, што. Там накшталт больш разумны спосаб зрабіць гэта. Гэта крыху больш, складаныя і, магчыма, дазваляе нам зразумець, чаму двайковая Пошук нашмат хутчэй. Па-першае, давайце пазнаёмімся паняцце дрэва. Які, хоць у рэальнасць дрэвы роду расці, як гэта, у свеце кампутар навука яны накшталт растуць ўніз як радаводу, дзе ў вас ёсць Вашы дзядулі і бабулі або прадзеды ці яшчэ шмат чаго ў верхняй, патрыярха і матриарх сям'і, толькі адзін так званы корань, вузел, ніжэй якія з'яўляюцца яе дзеці, ніжэй якога з'яўляюцца яго дзеці, ці яго нашчадкі ў цэлым. І хто вісіць ніжняя частка сям'і Дрэва, акрамя таго, што малодшы ў сям'і, Таксама можна проста ў агульным называецца лісце дрэва. 

Так што гэта проста куча слоў і азначэнняў што-то называецца дрэва ў кампутары навука, гэтак жа, як радаводу. Але ёсць больш мудрагелістыя увасаблення дрэў, адно з якіх называецца бінарнае дрэва пошуку. І вы можаце роду дражніць акрамя таго, што гэтая рэч робіць. Ну, гэта двайковы, у якім сэнсе? Дзе двайковы прыходзяць адсюль? На жаль? Гэта не столькі або. Гэта больш, што кожны з вузлоў мае не больш двух дзяцей, як мы бачым тут. Увогуле, у tree-- і Вашы бацькі і бабулі можа мець столькі дзяцей або ўнукі, як яны на самой справе хочуць, і так, напрыклад там у нас ёсць тры дзяцей з гэтай правам вузле, але ў бінарным дрэве, вузел мае нуль, адзін або двое дзяцей. Максімальна І гэта прыемна уласнасці, таму што, калі ён абмежаваны двума, мы збіраемся, каб мець магчымасць атрымаць крыху часопіса базы дзвюх Дзеянне адбываецца тут, у канчатковым рахунку. Такім чынам, мы маем нешта лагарыфмічная. Але пра гэта крыху пазней. Пошук дрэва азначае, што нумары размешчаны такім чынам, што левая дзіцяці значэнне больш кораня. І яго права дзіця больш, чым у корані. Іншымі словамі, калі вы бераце любы з вузлы, колы ў гэтай карціне, і глядзіць на яго левай Дзіця і яго правы дзіцяці, першае павінна быць менш, другая павінна быць больш, чым. Так здаровае праверыць 55. Гэта засталося дзіцяці 33. Гэта менш, чым. 55, яго права дзіця 77. Гэта больш, чым. І гэта рэкурсіўнае вызначэнне. Мы маглі б праверыць кожны з тых, вузлы і тая ж карціна будзе праводзіць. 

Так што прыемна ў бінарнае дрэва пошуку, гэта што адзін, мы можам рэалізаваць яго з структуры, як гэта. І хоць мы кідалі шмат структур, у вашым яны некалькі Цяпер, спадзяюся, інтуітыўна. Сінтаксіс яшчэ таямніцай напэўна, але змесціва вузла ў гэтым context--, і мы працягваем выкарыстоўваючы слова вузел, ці з'яўляецца гэта прастакутнік на экране або круга, гэта толькі некаторыя агульныя кантэйнер, У гэтым выпадку дрэва, як той, мы бачылі, мы павінны цэлае у кожным з вузлоў а потым мне трэба два паказальнікі, якія паказваюць на левым дзіцяці і правай дзіцяці, адпаведна. Дык вось, як мы маглі б ажыццявіць, што ў структуры. І як я мог бы рэалізаваць гэта ў кодзе? Ну, давайце хутка паглядзець на гэтым маленькім напрыклад. Гэта не працуе, але я скапіяваць і ўставіць гэтую структуру. І калі мая функцыя для бінарных Пошук дрэва называецца пошук, і гэта прымае два аргументу, цэлы лік N і паказальнік да вузла, так што паказальнік на дрэва або паказальнік на корань дрэва, як я магу ісці аб пошуку N? Ну, па-першае, таму, што я справу з паказальнікамі, Я збіраюся зрабіць праверку наяўнасці свядомасці. Калі дрэва роўна роўная нуля, з'яўляецца N ў гэтым дрэве ці не ў гэтым дрэве? Гэта не можа быць, ці не так? Калі я міма нуль, няма нічога. Я мог бы таксама проста слепа сказаць вярнуцца ілжывым. Калі вы не даюць мне нічога, я, вядома, не магу знайсці лік N. Так што яшчэ я мог бы праверыць цяпер? Я хачу сказаць, добра яшчэ, калі п менш, чым тое, што знаходзіцца ў вузле дрэва што я быў перададзены значэнне N. Іншымі словамі, калі лік Я шукаеце, N, менш, чым вузел што я гляджу на. І вузел Я шукаю у называецца дрэва, і ўспомніць з папярэдняга прыкладу каб дабрацца да значэння ў паказальнік, Я выкарыстоўваю абазначэння са стрэлкай. Так што, калі N менш, чым дрэва стрэлкі N, я хачу, каб канцэптуальна ідзіце налева. Як я выказваю пошуку засталося? Каб было ясна, калі гэта карціна ў пытанні, і я быў прыняты, што верхні стрэлка, які накіраваны ўніз. Гэта мая паказальнік дрэва. Я паказваю на корані дрэва. І я з нецярпеннем скажам, лік 44, адвольна. 44 менш або больш, чым 55, відавочна? Дык гэта менш, чым. І так гэта, калі ўмова распаўсюджваецца. Так канцэптуальна, тое, што я хачу, каб пошук у наступным, калі я шукаю 44? Да? 

Дакладна, я хачу пошук левую дзіцяці, або налева суб-дрэва гэтай карціны. І на самай справе, хай мяне праз карціна тут на імгненне, так як Я не магу падрапаць гэта. Калі я пачну тут у 55, і Я ведаю, што значэнне 44 Я шукаю, каб левая, гэта свайго роду з, як раздзіраючы тэлефонную кнігу ў палова або раздзіраючы дрэва напалову. Я больш не прыйдзецца клапаціцца аб ўвесь гэты палова дрэва. І ўсё ж, як ні дзіўна, у тэрмінах Структура, гэтая рэч тут, што пачынаецца з 33, што само па сабе гэта бінарнае дрэва пошуку. Я сказаў слова рэкурсіўны раней, таму што Сапраўды, гэта структура дадзеных, па вызначэнні з'яўляецца рэкурсіўнай. Вы, магчыма, дрэва, у гэтым вялікі, але кожны з яго дзяцей ўяўляе сабой дрэва проста трохі менш. Замест гэтага быць дзядулю ці бабуля, цяпер гэта проста мама или-- я не магу say-- ня мама ці тата, што было б дзіўна. Замест двое дзяцей там будзе як брат і брат. Новае пакаленне ў радаводу. Але структурна, гэта тая ж самая ідэя. А то атрымліваецца, у мяне ёсць функцыя з якой я магу шукаць бінарны пошук дрэва. Гэта называецца пошук. Я шукаю N ў дрэве злева стрэлкі астатняе, калі п больш, чым значэнне што я ў цяперашні час. 55 у гісторыі момант таму. У мяне ёсць функцыя пад назвай Пошук, што я магу проста прайсці N гэта і рэкурсіўны пошук суб-дрэва і проста вяртанне усё, што адказам. Інакш я атрымаў некаторыя выніковы базавы выпадак тут. 

Якая канчатковая справа? Дрэва альбо нулявым. Значэнне я альбо шукаю з'яўляецца менш, чым гэта ці больш, што або роўная ёй. І я магу сказаць, роўныя роўныя, але лагічна гэта эквівалентна проста кажу яшчэ тут. Так праўда, як я знайсці нешта. Так, мы спадзяемся гэта яшчэ больш пераканаўчым прыкладам чым дурной функцыі сігма Мы зрабілі некалькі лекцый таму, дзе гэта было так жа лёгка выкарыстоўваць цыкл падлічыць ўсе лічбы ад аднаго да N. Тут са структурай дадзеных што сама рэкурсіўна вызначаны і рэкурсіўна звяртаецца, зараз мы маюць магчымасць выказаць сябе, каб у кодзе, які сам па сабе з'яўляецца рэкурсіўнай. Так што гэта сапраўды такі жа код тут. 

Так што іншыя праблемы мы можам вырашыць? Такім чынам, хуткім крокам ад дрэвы на імгненне. Вось, скажам, нямецкі сцяг. І ёсць відавочна шаблон для гэтага сцяга. І ёсць шмат сцягі ў свеце, так проста, як гэта з пункту гледжання іх колеру і ўзоры. Але выкажам здагадку, што гэта захоўваецца як .GIF Ці JPEG, або растравы, або пінг, любы графічны фармат файла з якой вы знаёмыя, некаторыя з якіх мы гуляць з у PSET4. Гэта, здаецца, не варта захоўваць чорны піксель, чорны піксель, чорны піксель, кропка, кропка, кропка, цэлая куча чорныя пікселі для першага радка разгорткі, ці радок, то цэлая куча тое ж самае, то цэлая куча таго ж самага, а затым Увесь букет чырвоных пікселяў, чырвоны пікселяў, чырвоныя пікселі, то ў цэлым Букет з жоўтых кропак, жоўты, праўда? 

Там такая неэфектыўнасць тут. Як бы вы інтуітыўна сціскаць нямецкі сцяг калі яе рэалізацыі ў выглядзе файла? Падабаецца тое, што інфармацыя мы не можам турбаваць захоўвання на дыску для таго, каб паменшыць нашу памер файла з, як мегабайт у кілабайт, то менш? У чым заключаецца надмернасць тут, каб быць зразумела? Што вы маглі б зрабіць? Да? Дакладна. Чаму б не ўспомніць, чым колер кожнага пікселя цыраваць гэтак жа, як вы робіце ў PSET4 з Фармат графічнага файла, чаму б вам проста не ўяўляюць левая калонка пікселяў, напрыклад куча чорных пікселяў, куча чырвоны, і куча жоўты, а потым проста нейкім чынам кадзіраваць Ідэя паўтарыць гэты 100 разоў або паўтарыць гэта ў 1000 раз? Дзе 100 або 1000 з'яўляецца проста цэлы лік, так што вы можа сысці з рук толькі адзін нумар замест сотняў або тысяч дадатковых пікселяў. І на самай справе, вось як мы можа сціскаць нямецкі сцяг. І Цяпер тое, што пра французскім сцягам? І трохі свайго роду разумовае практыкаванне, што сцяг могуць быць сціснутыя больш на дыску? Нямецкі сцяг ці французскі Сцяг, калі мы возьмем такі падыход? Нямецкі сцяг, таму што ёсць больш гарызантальнага рэзервавання. І па дызайне, многія графічны файл Фарматы сапраўды працаваць, як сканавання ліній гарызанталі. Яны маглі б працаваць вертыкальна, проста чалавецтва вырашылі гадоў таму, што мы будзем як правіла, думаць пра рэчы, шэраг па радках, а не па слупках. Так, калі б вы былі паглядзець на файл памер нямецкім сцягам і французскай мовах Сцяг, пакуль дазвол тое ж самае, такой жа шырыні і вышыня, на гэты раз тут будзе больш, таму што вы прыйдзецца паўтарыць сябе тры разы. Вы павінны паказаць, паўтор сіні самастойна, белы, паўтарацца, чырвоны, паўтарацца. Вы не можаце проста пайсці усё шлях да правай. І, як у бок, каб зрабіць ачысціць сціск ўсюды, калі гэта чатыры кадра з video-- вы Нагадаю, што фільм або відэа, як правіла, як 29 або 30 кадраў у секунду. Гэта як маленькі фліп кнігі, дзе вас проста ўбачыць выявы, малюнак, малюнак, малюнак, Малюнак проста супер хутка, так што, падобна, акцёры на экране рухаюцца. Вось чмель на Верх букетам кветак. І хоць гэта можа быць выгляд цяжка зразумець, на першы погляд, адзінае рух у гэты фільм пчала. 

Што з'яўляецца нямым аб захоўванні відэа ў несціснутым? Гэта свайго роду адходаў для захоўвання відэа як чатыры амаль ідэнтычных малюнкаў, адрозніваюцца толькі пастолькі, паколькі, калі пчала. Вы можаце выкінуць найбольш гэтай інфармацыі і памятаць толькі, напрыклад, першы кадр і апошні кадр, ключавыя кадры, калі вы калі-небудзь чулі слова, і проста захоўваць у сярэдняга, дзе пчала. І вы не павінны захоўваць усе ружовым, і сіні, і зялёныя значэння, а таксама. Так што гэта толькі сказаць, што сціску ва ўсім свеце. Гэта тэхніка, якую мы часта выкарыстоўваюць або прымаць як належнае ў гэтыя дні. 

Але як вы сціснуць тэкст? Як вы ісці аб сціску тэксту? Ну, кожны з персанажаў Ascii адзін байт, ці восем біт. І гэта свайго роду нямы, ці не так? Таму што вы, верагодна, увядзіце A і Е, я і вываду і U шмат часцей, чым, як W або Q або Z, у залежнасці ад мовы, на якім Вы пішаце, вядома ,. І так, чаму мы з дапамогай восем бітаў для кожнага лісты, у тым ліку не менш папулярныя літары, праўда? Чаму б не выкарыстоўваць меншая колькасць біт для супер папулярныя літары, як Е, то, думаю, вы першы ў Кола Фартуны, і выкарыстоўваць больш бітаў для менш папулярныя літары? Чаму? Таму што мы толькі збіраемся выкарыстоўваць іх радзей. 

Ну, аказваецца, што там ёсць прадпрымаліся спробы зрабіць гэта. І калі вы памятаеце з класа школа або ВНУ, код Морзэ. Азбука Морзэ мае пункту і працяжнік, якія могуць быць перадаюцца па провадзе як гукі або сігналы нейкі. Але код Морзэ з'яўляецца супер чысты. Гэта свайго роду двайны сістэмы ў што ў вас ёсць кропкі або рысачкі. Але калі вы бачыце, напрыклад, дзве кропкі. Ці, калі вы думаеце, назад аператару хто ідзе, як гукавы сігнал, БІП, БІП, гукавы сігнал, патрапіўшы трохі курок што перадае сігнал, калі вы, атрымальнік атрымлівае два пункту, тое, што паведамленне вы атрымалі? Цалкам адвольна. 

Я? Я? Або тое, што about-- ці я? Можа быць, гэта было ўсяго толькі два прама Э? Так што гэтая праблема з декодируемости з Морзэ Код, у выніку чаго, калі толькі чалавек, які пасылае вам паведамленне на самай справе робіць паўзу, каб вы маглі сартаваць бачыць або чуць прабелы паміж літарамі, гэта не дастаткова проста адправіць паток нулёў і адзінак, або кропкі і працяжнік, таму што ёсць двухсэнсоўнасць. Е з'яўляецца адна кропка, так што калі вам ўбачыць дзве кропкі ці пачуць дзве кропкі, можа быць, гэта два E-небудзь ці, можа быць, гэта адзін І. Так што мы павінны сістэму, што гэта трохі разумнейшыя, чым гэта. Такім чынам, чалавек па імі Хафман гадоў таму прыдумаў менавіта гэта. Такім чынам, мы проста збіраемся ўзяць хуткі погляд на тое, як дрэвы дарэчныя для гэтага. Выкажам здагадку, што гэта які- дурному паведамленне вы хочаце адправіць, складаецца толькі з A, B, C у D's і Е х, але ёсць шмат надмернасці тут. Гэта не азначала, каб быць англійская. Гэта не шыфруецца. Гэта проста глупства паведамленне з вялікай колькасцю паўтораў. Так што, калі вы на самой справе адлічваць усе А-х, Б, З-х, D's, і E-х, вось частата. 20% з літар А-х, 45% з літар з'яўляюцца E, і тры іншыя частоты. Мы налічылі там ўручную і проста зрабіў матэматыку. 

Так што атрымліваецца, што Хафман, некаторы час таму, зразумеў, што, вы ведаеце, тое, што, калі я пачну будынак дрэва, або лес дрэў, калі хочаце, як след, я магу зрабіць наступнае. Я збіраюся даць вузел сябар з лістоў, якія я клапоцяцца пра і я збіраюся захоўваць ўнутры гэтага вузла частоты, як плавае кропкай значэнне, ці вы маглі б выкарыстоўваць яго п таксама але мы будзем выкарыстоўваць толькі паплавок тут. І алгарытм, які ён прапанаваў, што вы прыняць гэты лес адным вузле дрэвы, так супер кароткія дрэвы, і вы пачынаеце злучэння іх з новыя групы, новыя бацькі, калі вы будзеце. І гэта можна зрабіць, выбраўшы два маленькіх частоты адначасова. Так што я ўзяў 10% і 10%. Стварыць новы вузел. І я заклікаю новы вузел 20%. 

Якія два вузлы я камбінаваць далей? Гэта крыху неадназначным. Так ёсць некаторыя выпадкі, у кутнія разгледзець, але трымаць рэчы даволі, Я збіраюся выбраць 20% - Цяпер я ігнараваць дзяцей. Я збіраюся выбраць 20%, а 15% і намалюйце два новыя рэбры. А цяпер якія два вузла я лагічна аб'яднаць? Ігнараваць усе дзеці, усё ўнукі, проста паглядзіце на карані Цяпер. Якія два вузлы я звязаць разам? Другі пункт і 0,35. Такім чынам, дазвольце мне зрабіць два новых рэбраў. І потым, я толькі атрымаў адзін застаўся. Дык вось дрэва. І гэта была звернута наўмысна глядзець выгляд даволі, але заўважыў, што рэбры маюць Таксама былі пазначаныя нуля і адзін. Такім чынам, усе з левага краёў роўныя нулю адвольна, але паслядоўна. Усе правыя краю з'яўляюцца тыя. 

І так, што Хофман прапанаваў ёсць, калі вы хочаце, каб прадстаўляць B, а не ўяўляюць сабой колькасць, як 66 ASCII, які восем цэлыя біт, вы ведаеце, што толькі крама ўзор нуль, нуль, нуль, нуля, таму што гэта шлях ад майго дрэва, дрэва Хафман г, да ліста ад кораня. Калі вы хочаце захаваць Е, наадварот, не адправіць восем біт, якія ўяўляюць Е. Замест гэтага, адправіць які набор бітаў? Адзін. І, што прыемна пра гэта з'яўляецца што Е з'яўляецца самым папулярным ліст, і вы з дапамогай кароткі код для яго. Наступным найбольш папулярным Ліст выглядае яна быў А. І так, колькі біт ён прапануецца выкарыстоўваць для гэтага? Нуль, адзін. 

І таму, што ён рэалізаваны як гэта дрэва, у цяперашні час дазвольце мне прадугледжваюць ёсць няма неадназначнасці, як у Морзэ Код, таму што ўсе з Лісты вы клапоціцеся аб ў канцы гэтых краёў. Так гэта толькі адзін Прымяненне дрэва. Гэта is-- і я хваля мая рука на гэта, як вы можа ажыццявіць гэта ў C структуры. Мы проста павінны аб'яднаць сімвал, як гольца, і частата ў левы і правы. Але давайце паглядзім на два Канчатковыя прыклады, якія вы атрымаць добра знаёмыя з пасля Тэст нуля ў праблеме ўсталяваць пяць. 

Так што ёсць структура дадзеных вядомы як хэш-табліцу. І Хэш-табліца з'яўляецца своеасаблівай астыць на тым, што ён мае вядра. І хай там чатыры вядры тут усяго чатыры прабелы. Вось калода карт, і тут клуб, рыдлёўка, клуб, алмазы, клуб, брыльянты, алмазы клуб ,, clubs-- так што гэта выпадковая. Сэрца, hearts-- таму я bucketizing усе ўваходы тут. І А патрэбы хэш-табліцу зірнуць на свой ўваход, а затым пакласці яго ў пэўны размясціць аснове таго, што вы бачыце. Гэта алгарытм. І я быў з дапамогай супер просты візуальны алгарытм. Самая цяжкая частка з якіх была памятаючы, што фатаграфіі былі. А тут яшчэ ўсяго чатыры рэчы. 

Цяпер стэкі былі расце, што наўмыснае дызайн рэч тут. Але што яшчэ я мог бы зрабіць? Таму на самай справе тут мы маем куча старых кніг школы іспыт. Выкажам здагадку, што кучу студэнты імёны тут. Вось больш хэш-табліцы. Замест чатырох вёдраў, Я, скажам, 26. І мы не хочам ісці займаць 26 рэчы з па-за [? Анненберга?], Так што вось пяць, якія ўяўляюць А да Z. І калі я см студэнта, чыё імя пачынаецца з А, Я збіраюся паставіць яго ці яе віктарыны там. Калі хто-то пачынае з C, там, A-- самай справе, не хочуць, каб зрабіць гэта. У ідзе сюды. Так што я атрымаў А і В і С. А Цяпер вось яшчэ студэнт. Але калі гэта хэш-табліцы рэалізаваны з масівам, Я накшталт ўшрубоўваецца на дадзены момант, ці не так? Я накшталт павінны пакласці гэта недзе. 

Так адзін спосаб я магу вырашыць гэта, усё права, заняты, заняты У, З заняты. Я збіраюся паставіць яго ў D. Такім чынам, у Спачатку я ёсць выпадковае імгненны доступ да кожнага з каўшоў для студэнтаў. Але цяпер гэта накшталт перададзеныя ў нешта лінейных, таму што, калі я хачу, каб шукаць каго- чыё імя пачынаецца з А, я правяраю тут. Але калі гэта не А студэнт Я шукаю, Я накшталт павінны пачаць праверку вядра, таму што тое, што я зрабіў быў свайго роду лінейна даследаваць структуру дадзеных. Дурны спосаб сказаць проста паглядзець для першай даступнай адкрыцця, і паставіць у план Б, так бы мовіць, ці план распрацоўкі ў гэтым выпадку, значэнне у гэтым месцы замест гэтага. Гэта проста так, што калі вы атрымаў 26 месца і не студэнты з імем Q або Z, ці нешта накшталт што, па меншай меры, вы карыстаецеся прастору. 

Але мы ўжо бачылі больш разумныя рашэння тут, праўда? Што б вы зрабілі, замест калі ў вас ёсць сутыкненне? Калі два чалавекі маюць назву А, што б былі разумнейшыя або інтуітыўнае рашэнне, чым проста Памяшканне, дзе D, як мяркуецца, будзе? Чаму я не магу проста пайсці па-за [? Анненберга?], як Таноса, іншы вузел, паставіць яго тут, а затым пакласці, што студэнт тут. Так што я па сутнасці ёсць якая з масіва, ці, можа быць, больш элегантна, як мы пачынаем бачыць звязаны спіс. 

І так хэш-табліца структура што можа выглядаць гэтак жа, як гэта, але разумнейшыя, вы нешта называецца асобны ланцужкі, у выніку чаго хэш-табліцу даволі проста ўяўляе сабой масіў, кожны з элементы якога не з'яўляецца лікам, само па сабе з'яўляецца звязаны спіс. Так што вы атрымаеце супер хуткі доступ вырашыць, дзе ў Хэш вашу каштоўнасць для. Многае, як у прыкладзе карт, Я зрабіў супер хуткія рашэнні. Сэрца ідзе тут, алмазы ідзе тут. Тое ж самае тут, А тут ідзе, Д ідзе тут, У тут ідзе. Так супер хуткі погляд вокны, і калі Вы выпадкова запусціць у выпадку дзе вы атрымалі сутыкнення, два людзі з такім жа імем, ну а потым Вы проста пачаць, звязваючы іх разам. І, можа быць, вы трымаеце іх сартуюцца ў алфавітным парадку, можа быць, вы гэтага не робяць. Але па меншай меры зараз у нас ёсць дынамізм. Такім чынам, з аднаго боку, мы маем вельмі хутка пастаянная часу, і выгляд лінейнага часу ўдзел, калі гэтыя звязаныя спісы пачынаюць атрымліваць трохі доўга. 

Так што гэта свайго роду дурныя, выклікалым жарты гадоў таму. У CS50 секчы-а-марафон, калі студэнты праверыць у, некаторыя TF або Каліфорнія кожны год думае, што гэта смешна, мірыцца знак, як гэта, дзе гэта толькі азначае, што калі ваша імя пачынаецца з А, ісці па гэтым шляху. Калі пачынаецца ваша імя з У, перайсці this-- ОК, гэта смешна, можа быць, пазней у семестр. Але ёсць яшчэ адзін спосаб зрабіць гэта, таксама. Вярніся да гэтага. 

Так што гэтая структура. І гэта наша апошняя Структура на сённяшні дзень, што-то называецца Trie. Т-Р-І-Е, які чамусьці не хапае для пошуку, але гэта называецца Trie. Так Trie яшчэ адзін цікавы Амальгама шмат гэтых ідэй. Гэта дрэва, якое мы бачылі раней. Гэта не бінарнае дрэва пошуку. Гэта дрэва з любым колькасцю дзяцей, але кожны з дзяцей у сінтаксічнага дрэва з'яўляецца масівам. Масіў памерам, дапусцім, 26 ці, можа быць 27 калі вы хочаце, каб падтрымаць злучок імёны або апострафы ў імёнах людзей. 

І так гэта структуры дадзеных. І калі вы паглядзіце зверху ўніз, як калі б вас паглядзіце на верхні вузел там, М, паказваючы на ​​крайнюю левую рэчы там, які затым A, X, W, E, L, L. Гэта проста структура дадзеных, якая адвольна з'яўляецца захаванне імёнаў людзей. І Максвел захоўваецца толькі пасля гэта шлях масіва масіва на масіў. Але што дзіўна каля Trie з'яўляецца што, у той час як звязаны спіс, і нават масіў, лепшае, што мы калі-небудзь атрымлівалі гэта лінейнае час або лагарыфмічнай час шукаеце хто да. У гэтым структуры дадзеных сінтаксічнага дрэва, калі мой структура дадзеных мае адзін імя ў ім і Я шукаю Максвелла, я збіраюся знайсці яго даволі хутка. Я проста гляджу на М-А-Х-W-E-L-L. Калі Гэтая структура дадзеных, насупраць, Калі N з'яўляецца млн, калі ёсць мільён імёны ў гэтай структуры дадзеных, Максвел яшчэ будзе выявіць ўжо праз М-А-Х-Ш-Е-Л-Ь крокі. І David-- Д-А-У-Я-D крокі. Іншымі словамі, шляхам стварэння структура дадзеных, што гэта атрымаў усе гэтыя масіваў, кожны з якіх Самі падтрымліваць адвольны доступ, Я магу пачаць гледзячы народных назваць, выкарыстоўваючы колькасць часу, што'S прапарцыйная ня колькасці рэчаў у структуры дадзеных, як мільён існуючыя імёны. Колькасць часу, якое патрабуецца, каб знайсці мяне М-А-Х-Ш-Е-Л-Л ў гэтай структуры дадзеных з'яўляецца прапарцыйная ня Памер структуры дадзеных, але з даўжынёй імя. І рэалістычна Імёны мы гледзячы ніколі не будзе з розуму доўга. Можа быць, хтосьці мае 10 характар імя, імя персанажа 20. Гэта, вядома, вядома, не так? Існуе чалавека на Зямлі, які мае максімальна магчымы імя, але гэта імя з'яўляецца канстантай значэнне даўжыні, праўда? Гэта не змяняецца ў любым сэнсе. Такім чынам, у гэтым выпадку, мы дасягнуты структурай дадзеных што сталая часу погляд ўверх. Гэта зойме некалькі крокаў у залежнасці ад даўжыні ўваходу, але не лічбу імя ў структуры дадзеных. Так што, калі мы падвоіў колькасць імёнаў ў наступным годзе з мільярда да двух мільярдаў, выснову Максвелла збіраецца ўзяць сапраўды такі ж колькасць сем крокаў каб знайсці яго. І такім чынам, мы, здаецца, дасягнулі наш святы Грааль час працы. 

Такім чынам, пара хуткіх аб'яваў. Віктарына нуль прыдумляць. Больш падрабязна пра тое, што на вэб-сайце Курсу на працягу бліжэйшых некалькіх дзён. Панядзелак lecture-- Гэта свята тут у Гарвардзе ў панядзелак. Гэта не ў Нью-Хейвене, такім чынам, мы бярэм клас ў Нью-Хейвен для лекцыі ў панядзелак. Усё будзе зняты і транслявацца ў прамым эфіры, як звычайна, але давайце ў канчатковым сёння з другім заціскам 30 званыя "глыбокія думкі" па Daven Фарным, які быў натхнёны ў мінулым годзе ў суботу "Думкі" Deep Night Live ў Джэк хэнд, які Зараз варта разабрацца. 

ФІЛЬМ: А зараз, "Глыбокая Думкі "па Daven Фарным. Хэш-табліцы. 

СПІКЕР 1: Добра, што яна ў цяперашні час. Мы будзем бачыць Вас на наступным тыдні. 

Даг: Для таго каб убачыць яго ў дзеянні. Такім чынам, давайце зірнем на гэта прама цяпер. Дык вось, у нас ёсць малокомплектных масіў. 

УПА: Дуг, вы можаце ісці наперад і перазапуск гэта ўсяго толькі за адну секунду, калі ласка. Добра, камеры працуюць, так што дзеянні кожны раз, калі вы будзеце гатовыя, Дуг, ОК? Даг: Добра, так што мы ёсць тут малокомплектных масіў. І я ўсё каляровыя элементы чырвоным колерам, што, па сутнасці, малокомплектных. Так нагадаць, што першае, што мы робім гэта мы сартуем левую палову масіва. Затым мы сартуем права палова масіва. І я-так, я-так, я-так, мы іх зліваюцца. І ў нас ёсць цалкам адсартаваны масіў. Дык вось, як аб'яднаць роду прац. 

УПА: Гэй, гэй, гэй, выразаць, выразаць, выразаць, выразаць. Дуг, ты не можаш проста я-так, я-так, я-так, ваш шлях праз сартавання зліццём. 

Даг: Я толькі што зрабіў. Гэта выдатна. Мы добра ісці. Давайце проста трымаць пракаткі. Так ці інакш, 

УПА: Вы павінны растлумачыць гэта больш поўна, чым гэта. Вось толькі не хапае. Даг: Ян, мы не трэба вярнуцца да аднаго. Гэта выдатна. Так ці інакш, калі мы будзем працягваць з merge-- Ян, мы знаходзімся ў сярэдзіне здымак. 

УПА: Я ведаю. І мы не можам проста я-так, я-так, я-так, праз увесь працэс. Вы павінны растлумачыць, як Боку зліваюцца разам. 

Даг: Але мы ўжо патлумачыў, як два sides-- 

УПА: Вы толькі што паказалі іх масіў зліцця. Даг: Яны ведаюць працэс. Яны ў парадку. Мы пайшлі на яго ў дзесяць разоў. 

УПА: Вы толькі што прапусціў прама над ёй. Мы вяртаемся да аднаго, вы вы не можаце я-так, я-так над ім. Добра, да аднаго. 

Даг: Я павінен вярнуцца праз усе слайды? Божа мой. Гэта як у шосты раз, Ian. Гэта выдатна. 

УПА: Добра. Вы гатовыя? Выдатна. Дзеянне.