1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [Музыка, якая іграе] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID Малання: Гэта CS50. 5 00:00:14,010 --> 00:00:18,090 І гэта як пачатак і end-- як literally-- амаль да канца 6 00:00:18,090 --> 00:00:18,825 з шостым тыдні. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Я думаў, я б падзяліцца Трохі весялосці самай справе. 9 00:00:22,640 --> 00:00:25,370 Я выцягнуў гэты ад ўсталяваць дадзеныя мінулым семестра. 10 00:00:25,370 --> 00:00:29,710 Вы можаце ўспомніць, што мы просім вас на кожны р усталяванай формы, калі вы глядзелі онлайн 11 00:00:29,710 --> 00:00:31,580 або калі вы прысутнічалі асабіста. 12 00:00:31,580 --> 00:00:33,020 А вось дадзеныя. 13 00:00:33,020 --> 00:00:34,710 Так што сёння было вельмі шмат прадказальным. 14 00:00:34,710 --> 00:00:37,126 Але мы хацелі, каб выдаткаваць трохі часу з вамі, тым не менш. 15 00:00:37,126 --> 00:00:40,599 Хто-небудзь выказаць здагадку, чаму гэта Графік настолькі п'яны, уверх ўніз, уверх ўніз, 16 00:00:40,599 --> 00:00:41,265 так паслядоўна? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Што рабіць кожнаму з пікаў і жолабы ўяўляюць? 19 00:00:45,130 --> 00:00:46,005 >> АЎДЫТОРЫЯ: [неразборліва] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID Малання: Сапраўды. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 І яшчэ пацешна, не дай бог, мы праводзім адну лекцыю ў пятніцу 24 00:00:55,480 --> 00:00:58,960 ў пачатку семестра, гэта тое, што мы бачым здарыцца. 25 00:00:58,960 --> 00:01:03,430 Таму сёння, калі мы прымаем ў трохі больш пра структурах дадзеных. 26 00:01:03,430 --> 00:01:06,660 І, каб даць вам больш цвёрдага цела Ментальная мадэль для задач у пяць, 27 00:01:06,660 --> 00:01:07,450 які ў цяперашні час па-за. 28 00:01:07,450 --> 00:01:10,817 Арфаграфічныя памылкі, у якім мы будзем ўручыць вам тэкставы файл некаторыя 100000 29 00:01:10,817 --> 00:01:12,650 плюс ангельскія словы, і Вы будзеце мець, 30 00:01:12,650 --> 00:01:17,770 каб высветліць, як спрытна загружаць іх у памяць, у аператыўнай памяці, выкарыстоўваючы некаторыя дадзеныя 31 00:01:17,770 --> 00:01:19,330 Структура вашага выбару. 32 00:01:19,330 --> 00:01:22,470 >> Цяпер адна такая структура дадзеных можа быць, але, верагодна, не павінна быць, 33 00:01:22,470 --> 00:01:25,630 даволі спрошчана звязаны спіс, якія мы ўвялі ў мінулы раз. 34 00:01:25,630 --> 00:01:29,220 І звязаны спіс, па меншай меры, Адно з пераваг над масівам. 35 00:01:29,220 --> 00:01:32,096 Што адна перавага звязаны спіс, магчыма? 36 00:01:32,096 --> 00:01:32,950 >> АЎДЫТОРЫЯ: Устаўка. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Малання: Устаўка. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Што вы маеце на ўвазе? 40 00:01:35,196 --> 00:01:37,872 >> АЎДЫТОРЫЯ: Дзе заўгодна разам Спіс [неразборліва]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Малання: Добра. 42 00:01:38,770 --> 00:01:42,090 Такім чынам, вы можаце ўставіць элемент там, дзе гэта Вы хочаце ў сярэдзіне спісу 43 00:01:42,090 --> 00:01:45,490 без ператасаваць нічога, якія мы заключылі, у нашым сартавання 44 00:01:45,490 --> 00:01:47,630 дыскусіі, не абавязкова добра, 45 00:01:47,630 --> 00:01:51,200 таму што гэта займае час, каб сапраўды рухацца усе гэтыя чалавека налева або направа. 46 00:01:51,200 --> 00:01:55,540 І так са звязаным спісам, вы можаце проста вылучыць з Таноса, новы вузел, 47 00:01:55,540 --> 00:01:58,385 а затым абнавіць пару pointers-- два, тры аперацыі max-- 48 00:01:58,385 --> 00:02:01,480 і мы ў стане слот каго у любым месцы ў спісе. 49 00:02:01,480 --> 00:02:03,550 >> Што яшчэ было выгадна аб звязаным спісе? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Так? 52 00:02:05,659 --> 00:02:06,534 >> АЎДЫТОРЫЯ: [неразборліва] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID Малання: Выдатна. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Ідэальны. 57 00:02:11,090 --> 00:02:12,070 Гэта сапраўды дынамічным. 58 00:02:12,070 --> 00:02:15,100 І што вы не здзяйсняе, загадзя, да некаторай фіксаванага памеру 59 00:02:15,100 --> 00:02:18,750 ўчастак памяці, як вам прыйдзецца каб з масівам, уверх з якіх 60 00:02:18,750 --> 00:02:22,455 з'яўляецца тое, што вы можаце вылучыць вузлы толькі на Попыт, такім чынам, выкарыстоўваючы толькі столькі месца 61 00:02:22,455 --> 00:02:23,330 як вы на самой справе трэба. 62 00:02:23,330 --> 00:02:26,830 У адрозненне ад масіва, вы маглі б выпадкова вылучыць занадта мала. 63 00:02:26,830 --> 00:02:28,871 А потым ён проста будзе быць боль у шыі 64 00:02:28,871 --> 00:02:32,440 пераразмеркаваць новы большы масіў, капіяваць ўсё больш, вызваліць стары масіў, 65 00:02:32,440 --> 00:02:33,990 а затым перайсці аб вашым бізнэсе. 66 00:02:33,990 --> 00:02:37,479 Ці яшчэ горш, вы можаце вылучыць шлях больш памяці, чым вы на самой справе трэба, 67 00:02:37,479 --> 00:02:40,520 і такім чынам, вы будзеце мець вельмі маланаселенай масіў, так бы мовіць. 68 00:02:40,520 --> 00:02:44,350 >> Так звязаны спіс дае гэтыя Перавагі дынамізм і гнуткасць 69 00:02:44,350 --> 00:02:46,080 з ўстаўкі і выдаленні. 70 00:02:46,080 --> 00:02:48,000 Але, безумоўна, павінна быць цана, заплачаных. 71 00:02:48,000 --> 00:02:50,000 На самай справе, адна з тым, даследавалі на віктарыне нулявы 72 00:02:50,000 --> 00:02:52,430 было пару кампрамісаў мы бачылі да гэтага часу. 73 00:02:52,430 --> 00:02:56,161 Так што цана, заплачаных або Недахопам звязанага спісу? 74 00:02:56,161 --> 00:02:56,660 Так. 75 00:02:56,660 --> 00:02:57,560 >> АЎДЫТОРЫЯ: Няма адвольнага доступу. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Малання: Няма адвольнага доступу. 77 00:02:58,809 --> 00:02:59,540 Але каго гэта хвалюе? 78 00:02:59,540 --> 00:03:01,546 Адвольны доступ гучыць не пераканаўча. 79 00:03:01,546 --> 00:03:02,421 >> АЎДЫТОРЫЯ: [неразборліва] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Малання: Цалкам дакладна. 82 00:03:05,740 --> 00:03:07,580 Калі вы хочаце мець пэўная algorithm-- 83 00:03:07,580 --> 00:03:10,170 і дазвольце мне на самай справе прапануюць бінарны пошук, у прыватнасці, што 84 00:03:10,170 --> 00:03:12,600 з'яўляецца адным мы выкарыстоўвалі даволі bit-- калі ў вас няма выпадковага доступу, 85 00:03:12,600 --> 00:03:15,516 Вы не можаце зрабіць што простую арыфметыку знайсці як сярэдні элемент 86 00:03:15,516 --> 00:03:16,530 і скача прама да яго. 87 00:03:16,530 --> 00:03:20,239 Вы замест гэтага пачаць у першы элемент і лінейна пошук злева 88 00:03:20,239 --> 00:03:22,780 направа, калі вы хочаце знайсці сярэдні ці любы іншы элемент. 89 00:03:22,780 --> 00:03:24,410 >> АЎДЫТОРЫЯ: Гэта, верагодна, зойме больш памяці. 90 00:03:24,410 --> 00:03:25,040 >> DAVID Малання: зойме больш памяці. 91 00:03:25,040 --> 00:03:27,464 Дзе, што дадатковы Кошт які прыбывае з памяці? 92 00:03:27,464 --> 00:03:28,339 >> АЎДЫТОРЫЯ: [неразборліва] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Малання: Цалкам дакладна. 95 00:03:33,440 --> 00:03:35,679 У гэтым выпадку тут, у нас былі звязаны спіс для цэлых лікаў, 96 00:03:35,679 --> 00:03:37,470 і яшчэ мы падвойвае аб'ём памяці 97 00:03:37,470 --> 00:03:39,680 мы павінны таксама шляхам захоўвання гэтыя паказальнікі. 98 00:03:39,680 --> 00:03:42,090 Цяпер менш буйной здзелкі, як Вашы Структуры атрымаць больш 99 00:03:42,090 --> 00:03:45,320 і вы захоўваеце ня шэраг, але можа быць, студэнт ці нейкі іншы аб'ект. 100 00:03:45,320 --> 00:03:46,880 Але справа, вядома, застаецца. 101 00:03:46,880 --> 00:03:49,421 І так лік аперацый на звязаных спісах называліся 102 00:03:49,421 --> 00:03:50,570 былі вялікімі вываду N-- лінейнай. 103 00:03:50,570 --> 00:03:54,730 Такія рэчы, як ўстаўкі ці пошуку або выдаленне ў выпадку элемента 104 00:03:54,730 --> 00:03:57,720 апынуўся ў самым канцы Спіс няхай гэта будзе сартуюцца ці не. 105 00:03:57,720 --> 00:04:01,167 >> Часам можа павезці і ў так ніжнія межы гэтых аперацый 106 00:04:01,167 --> 00:04:04,250 таксама можа быць сталай часу, калі вы заўсёды глядзіць на першым элеменце, 107 00:04:04,250 --> 00:04:05,070 напрыклад. 108 00:04:05,070 --> 00:04:09,360 Але, у канчатковым рахунку, мы абяцалі для дасягнення Святой Грааль 109 00:04:09,360 --> 00:04:12,630 структур дадзеных, або некаторыя набліжэнне іх, 110 00:04:12,630 --> 00:04:14,290 шляхам сталай часу. 111 00:04:14,290 --> 00:04:17,579 Ці можам мы знайсці элементы або дадаваць элементы або выдаляць элементы з спісу? 112 00:04:17,579 --> 00:04:19,059 Мы ўбачым зусім хутка. 113 00:04:19,059 --> 00:04:21,100 І атрымліваецца, што адзін механізмаў мы 114 00:04:21,100 --> 00:04:23,464 збіраецца пачаць выкарыстоўваць сёння, Гадавое спажыванне ў р ўстаноўлена пяць, 115 00:04:23,464 --> 00:04:24,630 на самай справе даволі знаёмым. 116 00:04:24,630 --> 00:04:27,430 Напрыклад, калі гэта звязка экзаменацыйныя кніг, кожная з якіх 117 00:04:27,430 --> 00:04:29,660 мае студэнт спачатку імя і прозвішча на ёй, 118 00:04:29,660 --> 00:04:31,820 і я забраць іх з у канцы іспыту, 119 00:04:31,820 --> 00:04:33,746 і ўсе яны даволі шмат у выпадковым парадку, 120 00:04:33,746 --> 00:04:36,370 і мы хочам ісці аб сартаванні гэтыя экзамены, так што, як толькі ацэньваюцца 121 00:04:36,370 --> 00:04:38,661 гэта проста нашмат лягчэй і хутчэй здаць іх назад 122 00:04:38,661 --> 00:04:40,030 для студэнтаў па алфавіце. 123 00:04:40,030 --> 00:04:42,770 Што б вашыя інстынкты быць для кучы экзаменаў, як гэта? 124 00:04:42,770 --> 00:04:45,019 >> Ну, калі вы, як я, вы маглі б бачыць, што гэта м, 125 00:04:45,019 --> 00:04:48,505 так што я збіраюся роду паставіць гэта ў, калі гэта мой стол ці мой паверх, дзе 126 00:04:48,505 --> 00:04:50,650 Я распаўсюдзе рэчы out-- ці мой масіў really-- 127 00:04:50,650 --> 00:04:52,210 Я мог бы паставіць усё Ms там. 128 00:04:52,210 --> 00:04:52,710 О. 129 00:04:52,710 --> 00:04:55,020 Вось А. Такім чынам, я мог бы пакласці As тут. 130 00:04:55,020 --> 00:04:55,520 О. 131 00:04:55,520 --> 00:04:57,980 Вось яшчэ А. Я збіраюся пакласці, што тут. 132 00:04:57,980 --> 00:05:02,490 Вось З. Вось яшчэ М. І так Я мог бы пачаць рабіць палі, як гэта. 133 00:05:02,490 --> 00:05:06,620 І тады, магчыма, я б у далейшым і свайго роду вельмі nitpicky-лы роду 134 00:05:06,620 --> 00:05:07,710 асобныя палі. 135 00:05:07,710 --> 00:05:11,300 Але справа ў тым, я хацеў бы паглядзець на ўваходзе, што я рукамі 136 00:05:11,300 --> 00:05:14,016 і я хацеў бы зрабіць некаторыя разлічваецца Рашэнне заснавана на гэтым ўваходзе. 137 00:05:14,016 --> 00:05:15,640 Калі ён пачынаецца з, паклаў яго там. 138 00:05:15,640 --> 00:05:18,980 Калі ён пачынаецца з Z, паставіць яго на там, і ўсё паміж імі. 139 00:05:18,980 --> 00:05:22,730 >> Так што гэта тэхніка, гэта як правіла, вядомыя як hashing-- Н-A-S-Н- 140 00:05:22,730 --> 00:05:26,550 Звычайна гэта азначае, узяўшы ў якасці ўваход і з дапамогай гэтага уваход для разліку 141 00:05:26,550 --> 00:05:30,940 Значэнне, як правіла, колькасць, і што лік з'яўляецца індэксам ў захоўванні 142 00:05:30,940 --> 00:05:32,260 Кантэйнер, як масіў. 143 00:05:32,260 --> 00:05:35,490 Такім чынам, іншымі словамі, я мог бы Хэш функцыя, як і я, у маёй галаве, 144 00:05:35,490 --> 00:05:37,940 што, калі я бачу кагосьці гэта Назва, хто пачынае з А, 145 00:05:37,940 --> 00:05:40,190 Я збіраюся карту, што да нуля ў маёй галаве. 146 00:05:40,190 --> 00:05:44,160 І калі я бачу кагосьці, з Z, я збіраецца карту, што да 25 у мяне ў галаве 147 00:05:44,160 --> 00:05:46,220 а затым пакласці, што ў апошні найбольш куча. 148 00:05:46,220 --> 00:05:50,990 >> Зараз, калі вы думаеце пра не мой мозг але праграма C, якія нумары маглі 149 00:05:50,990 --> 00:05:53,170 Вы належыце на для дасягнення гэтай жа вынік? 150 00:05:53,170 --> 00:05:55,594 Іншымі словамі, калі вас меў ASCII сімвалаў A, 151 00:05:55,594 --> 00:05:57,510 як вы вызначаеце, што вядро пакласці яго ў? 152 00:05:57,510 --> 00:05:59,801 Вы, напэўна, не хочаце, каб пакласці яго ў вядро 65, які 153 00:05:59,801 --> 00:06:01,840 будзе, як там без паважнай прычыны. 154 00:06:01,840 --> 00:06:04,320 Дзе вы хочаце паставіць з пункту гледжання яго кошту ASCII? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Дзе вы хочаце зрабіць яго ASCII Значэнне прыдумаць разумнейшыя вядра 157 00:06:08,920 --> 00:06:09,480 паставіць яго ў? 158 00:06:09,480 --> 00:06:10,206 >> АЎДЫТОРЫЯ: Мінус А. 159 00:06:10,206 --> 00:06:10,956 >> DAVID Малання: Так. 160 00:06:10,956 --> 00:06:13,190 Так мінус-мінус спецыяльна 65, калі гэта 161 00:06:13,190 --> 00:06:18,240 Сталіца А. Або 98, калі гэта маленькая. 162 00:06:18,240 --> 00:06:21,300 І так, што дазволіць нам, вельмі проста і вельмі арыфметычна, 163 00:06:21,300 --> 00:06:23,260 пакласці што-то ў вядро, як, што. 164 00:06:23,260 --> 00:06:26,010 Вось і атрымліваецца, што мы на самай справе гэта таксама яшчэ з віктарыны. 165 00:06:26,010 --> 00:06:29,051 >> Такім чынам, вы, магчыма, памятаеце, вы кружыў ваш Назва выкладчыцкага стыпендыята на вокладцы. 166 00:06:29,051 --> 00:06:32,270 І імёны ТФ былі арганізаваны ў гэтых калонках па алфавіце, 167 00:06:32,270 --> 00:06:34,400 добра, верыць гэтаму ці не, калі ўсе 80 плюс з нас 168 00:06:34,400 --> 00:06:37,800 сабраліся ў той вечар у класе, Апошні крок у нашым працэсе атэстацыі 169 00:06:37,800 --> 00:06:41,830 з'яўляецца хэш віктарыны ў вялікі прастору падлогі ў [неразборліва] 170 00:06:41,830 --> 00:06:45,110 і закласці віктарыны усеагульныя з рабіць усё дакладна іх TF-х 171 00:06:45,110 --> 00:06:47,700 Імёны на вокладцы, таму што то гэта нашмат лягчэй для нас 172 00:06:47,700 --> 00:06:51,290 шукаць у гэтым з дапамогай лінейных пошук ці нейкі хітрасці 173 00:06:51,290 --> 00:06:54,050 для TF знайсці яго ці віктарыны ёй студэнтаў. 174 00:06:54,050 --> 00:06:56,060 >> Так гэтая ідэя хэшавання што вы ўбачыце гэта 175 00:06:56,060 --> 00:07:00,520 даволі магутны на самай справе даволі звычайным і вельмі інтуітыўна, 176 00:07:00,520 --> 00:07:03,000 так жа, як, магчыма, падзяліць і захоп быў нулявы тыдні. 177 00:07:03,000 --> 00:07:05,250 Я перанясемся ў Hackathon Пару гадоў таму. 178 00:07:05,250 --> 00:07:08,040 Гэта было Zamyla і пару Іншыя студэнты персанал віншавальныя 179 00:07:08,040 --> 00:07:09,030 як яны ўвайшлі. 180 00:07:09,030 --> 00:07:12,680 І ў нас быў цэлы букет складвання сталы там з бэйджы. 181 00:07:12,680 --> 00:07:15,380 І мы тэгі імёнаў арганізаваны з як як над там 182 00:07:15,380 --> 00:07:16,690 і Zs там. 183 00:07:16,690 --> 00:07:20,350 І таму адзін з ТФ вельмі разумна напісаў гэта як інструкцыі 184 00:07:20,350 --> 00:07:21,030 на працягу дня. 185 00:07:21,030 --> 00:07:24,480 І ў 12-й тыдню семестра гэтым усё мела сэнс, і ўсё 186 00:07:24,480 --> 00:07:25,310 ведаў, што рабіць. 187 00:07:25,310 --> 00:07:27,900 Але ў любы час вы маеце чаргу такім жа чынам, 188 00:07:27,900 --> 00:07:30,272 вы рэалізуеце ж паняцце хэш. 189 00:07:30,272 --> 00:07:31,730 Так што давайце фармалізаваць гэта няшмат. 190 00:07:31,730 --> 00:07:32,890 Вось гэта масіў. 191 00:07:32,890 --> 00:07:36,820 Гэта звяртаецца, каб быць трохі Шырокі проста адлюстраваць, візуальна, 192 00:07:36,820 --> 00:07:38,920 што мы маглі б паставіць струны у чымсьці накшталт гэтага. 193 00:07:38,920 --> 00:07:41,970 І гэты масіў відавочна памер 26 за ўсё. 194 00:07:41,970 --> 00:07:43,935 І справа называецца Табліца адвольна. 195 00:07:43,935 --> 00:07:48,930 Але гэта ўсяго толькі выкананне мастака таго, што можа быць хэш-табліцу. 196 00:07:48,930 --> 00:07:52,799 >> Так хэш-табліцу цяпер збіраецца быць вышэй, структура дадзеных ўзроўню. 197 00:07:52,799 --> 00:07:54,840 У канцы дня мы збіраемся, каб убачыць, што вас 198 00:07:54,840 --> 00:07:58,700 можа рэалізаваць хэш-табліцу, якая гэта так жа, як рэгістрацыя ў лініі 199 00:07:58,700 --> 00:08:02,059 на Hackathon так жа, як гэта Табліца выкарыстоўваецца для сартавання экзаменацыйныя кнігі. 200 00:08:02,059 --> 00:08:03,850 Але табліца хэш роду гэтым высокім узроўні 201 00:08:03,850 --> 00:08:08,250 Канцэпцыя, якая можа выкарыстоўваць масіў пад капот, каб рэалізаваць яго, 202 00:08:08,250 --> 00:08:11,890 ці гэта можа выкарыстоўваць спіс даўжыні, ці нават магчыма, некаторыя іншыя структуры дадзеных. 203 00:08:11,890 --> 00:08:15,590 А цяпер вось theme-- ўзяцце некаторыя з гэтых фундаментальных інгрэдыентаў 204 00:08:15,590 --> 00:08:18,310 як масіў і гэтага будынка блакаваць зараз са спісу даўжыні 205 00:08:18,310 --> 00:08:21,740 і, убачыўшы, што яшчэ мы можам пабудаваць па-над тых, як інгрэдыенты 206 00:08:21,740 --> 00:08:26,550 ў рэцэпце, што робіць усё больш і больш цікавыя і карысныя канчатковыя вынікі. 207 00:08:26,550 --> 00:08:28,680 >> Так з хэш-табліцы мы маглі б рэалізаваць яго 208 00:08:28,680 --> 00:08:32,540 ў памяці наглядна, як гэта, але як можа ён на самай справе быць закадзіраваны да? 209 00:08:32,540 --> 00:08:33,789 Ну, можа быць, як проста гэта. 210 00:08:33,789 --> 00:08:38,270 Калі ПАТЭНЦЫЯЛ загалоўнымі літарамі, гэта проста некаторыя constant-- напрыклад 26, 211 00:08:38,270 --> 00:08:42,030 для 26 літар alphabet-- Я мог бы назваць сваю табліцу зменных, 212 00:08:42,030 --> 00:08:45,630 і я мог бы сцвярджаць, што я збіраюся пакласці тэкставыя зоркі ў там, ці радкі. 213 00:08:45,630 --> 00:08:49,880 Так што гэта так проста, як гэта, калі вы хочаце рэалізаваць хэш-табліцу. 214 00:08:49,880 --> 00:08:51,490 І ўсё ж, гэта сапраўды проста масіў. 215 00:08:51,490 --> 00:08:53,198 Але, зноў жа, хэш Табліца зараз тое, што мы будзем 216 00:08:53,198 --> 00:08:57,470 называюць абстрактны тып дадзеных, гэта толькі роду канцэптуальнай слаёў зверху 217 00:08:57,470 --> 00:09:00,780 аб чым-то больш свецкага Цяпер хацелася масіў. 218 00:09:00,780 --> 00:09:02,960 >> Цяпер, як мы ідзем аб вырашэнні праблем? 219 00:09:02,960 --> 00:09:06,980 Ну, раней я была раскоша мець досыць месцы табліцы тут 220 00:09:06,980 --> 00:09:09,460 так што я мог бы паставіць віктарыны дзе заўгодна, я хацеў. 221 00:09:09,460 --> 00:09:10,620 Так, як можа ісці тут. 222 00:09:10,620 --> 00:09:12,100 Zs можа ісці тут. 223 00:09:12,100 --> 00:09:13,230 Г-жа можа ісці тут. 224 00:09:13,230 --> 00:09:14,740 А потым у мяне было некаторы дадатковае прастору. 225 00:09:14,740 --> 00:09:18,740 Але гэта нешта накшталт падману правы Зараз з-за гэтага стала, калі я сапраўды 226 00:09:18,740 --> 00:09:22,720 думаў пра гэта як масіў, проста будзе якога-небудзь фіксаванага памеру. 227 00:09:22,720 --> 00:09:25,380 >> Тэхнічна, калі я цягну да віктарыны іншага студэнта 228 00:09:25,380 --> 00:09:28,490 і ўбачыць, о, гэта чалавек-х Імя пачынаецца з А таксама, 229 00:09:28,490 --> 00:09:30,980 Я накшталт хачу паставіць яго там. 230 00:09:30,980 --> 00:09:34,740 Але як толькі я паклаў яго туды, калі гэтая табліца сапраўды ўяўляе сабой масіў, 231 00:09:34,740 --> 00:09:37,840 Я збіраюся быць пераазначэнне або выдаліўшы хто віктарына гэты студэнт з'яўляецца. 232 00:09:37,840 --> 00:09:38,340 Ці не так? 233 00:09:38,340 --> 00:09:41,972 Калі гэта масіў, толькі адна рэч можа перайсці ў кожнай з гэтых клетак або элементаў. 234 00:09:41,972 --> 00:09:43,680 І так я накшталт ёсць выбіраць. 235 00:09:43,680 --> 00:09:45,735 >> Цяпер раней я накшталт падманулі і зрабілі гэта, ці я 236 00:09:45,735 --> 00:09:47,526 толькі збольшага ўкладваюцца іх адно над адным. 237 00:09:47,526 --> 00:09:49,170 Але што не збіраецца ляцець у кодзе. 238 00:09:49,170 --> 00:09:52,260 Дык дзе я мог бы паставіць Другі студэнт, чыё імя 239 00:09:52,260 --> 00:09:54,964 гэта калі ўсё, што я меў гэта даступныя таблічнага прасторы? 240 00:09:54,964 --> 00:09:57,880 І я выкарыстаў тры слота і яго Падобна на тое, ёсць толькі некалькі іншых. 241 00:09:57,880 --> 00:09:58,959 Што вы маглі б зрабіць? 242 00:09:58,959 --> 00:09:59,834 АЎДЫТОРЫЯ: [неразборліва] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID Малання: Так. 245 00:10:01,315 --> 00:10:02,370 Можа быць, давайце проста трымаць яго проста. 246 00:10:02,370 --> 00:10:02,660 Ці не так? 247 00:10:02,660 --> 00:10:04,243 Гэта не ўкладаецца, дзе я хачу паставіць яго. 248 00:10:04,243 --> 00:10:07,450 Так што я збіраюся паставіць яго тэхнічна, дзе B пойдзе. 249 00:10:07,450 --> 00:10:09,932 Цяпер, вядома, я пачынаю маляваць сябе ў кут. 250 00:10:09,932 --> 00:10:11,890 Калі я дабяруся да студэнта чыё імя на самай справе B, 251 00:10:11,890 --> 00:10:14,840 Цяпер B збіраецца быць трохі ссунуўся наперад, як можа здарыцца, так, 252 00:10:14,840 --> 00:10:17,530 калі гэта B, цяпер ён павінен прайсці тут. 253 00:10:17,530 --> 00:10:20,180 >> І так гэта вельмі хутка можа стаць праблематычным, 254 00:10:20,180 --> 00:10:23,850 але гэта тэхніка, якая на самай справе згадваецца як лінейная зандзіравання, 255 00:10:23,850 --> 00:10:26,650 у якім вы проста ацаніць узровень сваіх Масіў быць ўздоўж лініі. 256 00:10:26,650 --> 00:10:29,680 І вы толькі збольшага зонд або правяраць кожны даступны элемент 257 00:10:29,680 --> 00:10:31,360 пошук вольнага месца. 258 00:10:31,360 --> 00:10:34,010 І як толькі вы знойдзеце адзін, вы змесціце яго ў там. 259 00:10:34,010 --> 00:10:38,390 >> Зараз, цана надаецца цяпер для гэтага рашэння з'яўляецца тое, што? 260 00:10:38,390 --> 00:10:41,300 У нас ёсць масіў фіксаванага памеру, і калі я ўстаўляю імёны 261 00:10:41,300 --> 00:10:44,059 у яе, па меншай меры, на пачатковым этапе, што час працы ўстаўкі 262 00:10:44,059 --> 00:10:46,350 для здачы студэнтаў віктарыны ў правільных вядра? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O чаго? 265 00:10:50,002 --> 00:10:51,147 >> АЎДЫТОРЫЯ: н. 266 00:10:51,147 --> 00:10:52,480 DAVID Малання: Я чуў, вялікі O п. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Гэта не так. 269 00:10:54,300 --> 00:10:56,490 Але мы будзем дражніць адзін ад аднаго чаму праз хвіліну. 270 00:10:56,490 --> 00:10:57,702 Што яшчэ гэта можа быць? 271 00:10:57,702 --> 00:10:58,755 >> АЎДЫТОРЫЯ: [неразборліва] 272 00:10:58,755 --> 00:11:00,380 DAVID Малання: І дазвольце мне зрабіць гэта візуальна. 273 00:11:00,380 --> 00:11:04,720 Так, напрыклад, гэта літара S. 274 00:11:04,720 --> 00:11:05,604 >> АЎДЫТОРЫЯ: Гэта адзін. 275 00:11:05,604 --> 00:11:06,520 DAVID Малання: Гэта адзін. 276 00:11:06,520 --> 00:11:06,710 Ці не так? 277 00:11:06,710 --> 00:11:08,950 Гэта масіў, які значыць, у нас ёсць адвольны доступ. 278 00:11:08,950 --> 00:11:11,790 І калі мы думаем, што гэта як нуль і гэта як 25, 279 00:11:11,790 --> 00:11:13,800 і мы разумеем, што, ой, вось мой ўклад S, 280 00:11:13,800 --> 00:11:16,350 Я магу, вядома, канвертаваць S, ASCII сімвалаў, 281 00:11:16,350 --> 00:11:18,540 на адпаведны нумар паміж нулём і 25 282 00:11:18,540 --> 00:11:20,910 , А затым неадкладна пакласці яго дзе яна належыць. 283 00:11:20,910 --> 00:11:26,120 >> Але, вядома, як толькі я дабяруся да Другі чалавек, які клічуць А ці У або З 284 00:11:26,120 --> 00:11:29,300 у рэшце рэшт, калі я выкарыстаў лінейны зандзіравання ў якасці майго рашэння, 285 00:11:29,300 --> 00:11:31,360 час працы ўстаўкі ў горшым выпадку 286 00:11:31,360 --> 00:11:33,120 на самай справе адбываецца, каб ператворыцца ў чым? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 І я чую яго тут Правільна рана. 289 00:11:36,045 --> 00:11:36,920 АЎДЫТОРЫЯ: [неразборліва] 290 00:11:36,920 --> 00:11:41,620 DAVID Малання: Дык гэта н сапраўды калі-то ў вас ёсць дастаткова вялікі набор дадзеных. 291 00:11:41,620 --> 00:11:44,410 Так, з аднаго боку, калі ваш масіў досыць вялікі 292 00:11:44,410 --> 00:11:48,287 і вашы дадзеныя досыць рэдкія, вы атрымаць гэтую прыгожую пастаяннае час. 293 00:11:48,287 --> 00:11:50,620 Але як толькі вы пачынаеце усё больш і больш элементаў, 294 00:11:50,620 --> 00:11:53,200 і толькі статыстычна Вы атрымліваеце больш людзей з літарай 295 00:11:53,200 --> 00:11:56,030 Як іх імя або ліст B, гэта можа патэнцыйна 296 00:11:56,030 --> 00:11:57,900 пераходзіць у што-то больш лінейнымі. 297 00:11:57,900 --> 00:11:59,640 Так што не зусім ідэальна. 298 00:11:59,640 --> 00:12:00,690 Так мы маглі зрабіць лепш? 299 00:12:00,690 --> 00:12:03,210 >> Ну, тое, што было нашым Рашэнне раней, калі мы 300 00:12:03,210 --> 00:12:06,820 хочуць мець большы дынамізм, чым нешта накшталт масіва дазволена? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 АЎДЫТОРЫЯ: [неразборліва] 303 00:12:08,960 --> 00:12:10,030 DAVID Малання: Што мы ўводзім? 304 00:12:10,030 --> 00:12:10,530 Так. 305 00:12:10,530 --> 00:12:11,430 Так звязаны спіс. 306 00:12:11,430 --> 00:12:14,430 Ну, давайце паглядзім, што звязана Спіс можа зрабіць для нас, а не. 307 00:12:14,430 --> 00:12:17,630 Ну, дазвольце мне прапанаваць, што мы маляваць карціну наступным чынам. 308 00:12:17,630 --> 00:12:19,620 Зараз гэта ўжо іншая карцінка з прыкладу 309 00:12:19,620 --> 00:12:24,750 з другога тэкст, на самай справе, што на самай справе, выкарыстоўваючы масіў памерам 31. 310 00:12:24,750 --> 00:12:28,220 І гэты аўтар проста вырашыў хэш радкі 311 00:12:28,220 --> 00:12:32,430 не на аснове імёнаў гэтай асобы, але на аснове іх даты нараджэння. 312 00:12:32,430 --> 00:12:35,680 Незалежна ад месяца, яны лічылі, калі вы нарадзіліся з першага месяца 313 00:12:35,680 --> 00:12:39,580 або 31-е чысло месяца, аўтар будзе хэш на аснове гэтага значэння, 314 00:12:39,580 --> 00:12:44,154 з тым, каб распаўсюдзіць імёны з трохі больш, чым проста 26 плямы могуць дазволіць. 315 00:12:44,154 --> 00:12:47,320 І, магчыма, гэта крыху больш раўнамернае чым ісці з літар алфавіту, 316 00:12:47,320 --> 00:12:50,236 таму што, вядома, ёсць, верагодна, Чым больш людзей у свеце з імёнамі 317 00:12:50,236 --> 00:12:54,020 што пачатак з чым, вядома, некаторыя іншыя літары алфавіту. 318 00:12:54,020 --> 00:12:56,380 Так, можа быць, гэта крыху больш раўнамернае, мяркуючы 319 00:12:56,380 --> 00:12:58,640 Раўнамернае размеркаванне немаўлятаў праз месяц. 320 00:12:58,640 --> 00:12:59,990 >> Але, вядома, гэта ўсё яшчэ недасканалыя. 321 00:12:59,990 --> 00:13:00,370 Ці не так? 322 00:13:00,370 --> 00:13:01,370 Мы з калізіі. 323 00:13:01,370 --> 00:13:04,680 Некалькі чалавек у гэта Структура даных па-ранейшаму 324 00:13:04,680 --> 00:13:08,432 які мае тую ж дату нараджэння, па меншай меры Вы, незалежна ад месяца. 325 00:13:08,432 --> 00:13:09,640 Але тое, што аўтар зрабіў? 326 00:13:09,640 --> 00:13:13,427 Ну, падобна, што мы маем масіў на левай баку, праведзенай вертыкальна, 327 00:13:13,427 --> 00:13:15,010 але вось толькі выкананне мастака. 328 00:13:15,010 --> 00:13:18,009 Гэта не мае значэння, у якім кірунку вам звярнуць масіў, гэта ўсё ж такі масіў. 329 00:13:18,009 --> 00:13:20,225 Што гэта масіў, відаць? 330 00:13:20,225 --> 00:13:21,500 >> АЎДЫТОРЫЯ: звязаны спіс. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Малання: Так. 332 00:13:21,650 --> 00:13:23,490 Падобна на тое, што гэта Масіў звязанага спісу. 333 00:13:23,490 --> 00:13:26,490 Такім чынам, яшчэ раз, на гэты момант роду выкарыстання гэтых структур дадзеных зараз 334 00:13:26,490 --> 00:13:28,550 ў якасці інгрэдыентаў ў больш цікавыя рашэнні, 335 00:13:28,550 --> 00:13:30,862 Вы можаце абсалютна ўзяць фундаментальная, як масіў, 336 00:13:30,862 --> 00:13:33,320 а затым ўзяць што-то больш Цікава, як звязаны спіс 337 00:13:33,320 --> 00:13:36,660 і нават аб'яднаць іх у яшчэ больш цікавым структура дадзеных. 338 00:13:36,660 --> 00:13:39,630 І на самай справе, гэта таксама будзе назваць хэш-табліцу, 339 00:13:39,630 --> 00:13:42,610 у выніку чаго масіў сапраўды хэш-табліца, 340 00:13:42,610 --> 00:13:45,600 але, што хэш-табліца мае ланцуга, так бы мовіць, 341 00:13:45,600 --> 00:13:50,220 што можа расці або памяншацца на аснове Колькасць элементаў вы хочаце ўставіць. 342 00:13:50,220 --> 00:13:52,990 >> Цяпер, адпаведна, што час працы ў цяперашні час? 343 00:13:52,990 --> 00:13:58,030 Калі я хачу, каб ўставіць каго- чый дзень нараджэння 31 кастрычнік 344 00:13:58,030 --> 00:13:59,040 дзе ён або яна? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Добра. 347 00:14:01,030 --> 00:14:02,819 У самым нізе, дзе ён кажа 31. 348 00:14:02,819 --> 00:14:03,610 І гэта выдатна. 349 00:14:03,610 --> 00:14:05,060 Гэта было пастаяннае час. 350 00:14:05,060 --> 00:14:08,760 Але што, калі мы знаходзім кагосьці іншага чый дзень нараджэння, давайце паглядзім, 351 00:14:08,760 --> 00:14:10,950 Кастрычнік, Лістапад 31 снежня? 352 00:14:10,950 --> 00:14:12,790 Дзе ён збіраецца ісці? 353 00:14:12,790 --> 00:14:13,290 Тое ж самае. 354 00:14:13,290 --> 00:14:13,970 Двухступеністая ж. 355 00:14:13,970 --> 00:14:15,303 Гэта пастаянная, хоць не так? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Добра. 358 00:14:16,860 --> 00:14:17,840 На дадзены момант ён з'яўляецца. 359 00:14:17,840 --> 00:14:20,570 Але ў агульным выпадку, чым больш людзей мы дадаем, 360 00:14:20,570 --> 00:14:23,790 імавернасна, мы збіраемся каб атрымаць больш і больш сутыкненняў. 361 00:14:23,790 --> 00:14:26,820 >> Цяпер гэта крыху лепш, таму што тэхнічна 362 00:14:26,820 --> 00:14:34,580 Цяпер мае ланцуга можа быць у у горшым выпадку, як доўга? 363 00:14:34,580 --> 00:14:38,890 Калі я ўстаўляю рускі народ у гэта больш складаная структура дадзеных, рускі народ, 364 00:14:38,890 --> 00:14:41,080 у горшым выпадку гэта будзе н. 365 00:14:41,080 --> 00:14:41,815 Чаму? 366 00:14:41,815 --> 00:14:43,332 >> АЎДЫТОРЫЯ: Таму што, калі ўсё мае той жа дзень нараджэння, 367 00:14:43,332 --> 00:14:44,545 яны збіраюцца быць адна лінія. 368 00:14:44,545 --> 00:14:45,420 DAVID Малання: Выдатна. 369 00:14:45,420 --> 00:14:47,480 Гэта можа быць трохі надуманы, але сапраўды, у горшым выпадку, 370 00:14:47,480 --> 00:14:50,117 калі кожны чалавек мае той жа дзень нараджэння, улічваючы ўваходы ў вас ёсць, 371 00:14:50,117 --> 00:14:51,950 Вы будзеце мець, масава доўгі ланцужок. 372 00:14:51,950 --> 00:14:54,241 І так, вы маглі б назваць гэта хэш-табліцу, але на самой справе гэта 373 00:14:54,241 --> 00:14:56,810 проста масіўны звязаны спіс з ў цэлым шмат невыкарыстоўваемай прасторы. 374 00:14:56,810 --> 00:15:00,460 Але ў цэлым, калі лічыць, што па меншай меры, дні нараджэння uniform-- 375 00:15:00,460 --> 00:15:01,750 і гэта, верагодна, не. 376 00:15:01,750 --> 00:15:02,587 Я раблю гэта. 377 00:15:02,587 --> 00:15:04,420 Але калі выказаць здагадку, для дзеля абмеркавання 378 00:15:04,420 --> 00:15:07,717 што яны, то ў тэорыі, калі Гэта вертыкальнае прадстаўленне 379 00:15:07,717 --> 00:15:11,050 з масіва, а затым, спадзяюся, вы збіраецца атрымаць ланцугоў, якія з'яўляюцца, вы ведаеце, 380 00:15:11,050 --> 00:15:15,880 прыкладна такой жа даўжыні, дзе кожны з гэта ўяўляе сабой дзень месяца. 381 00:15:15,880 --> 00:15:19,930 >> Цяпер, калі ёсць 31 дзён у месяц, што азначае мой час працы сапраўды 382 00:15:19,930 --> 00:15:25,230 вялікі вываду п над 31, якія адчувае сябе лепш, чым лінейны. 383 00:15:25,230 --> 00:15:27,950 Але тое, што было адным з нашых Абавязацельствы пару тыдняў 384 00:15:27,950 --> 00:15:31,145 таму, калі ён прыйшоў да выказвання час працы алгарытму? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Проста толькі паглядзіце на высокім тэрмін замовы. 387 00:15:35,190 --> 00:15:35,690 Ці не так? 388 00:15:35,690 --> 00:15:37,400 31, безумоўна, карысна. 389 00:15:37,400 --> 00:15:39,610 Але гэта па-ранейшаму вялікі O п. 390 00:15:39,610 --> 00:15:41,730 Але адна з тым, з праблем ўсталяваць пяць 391 00:15:41,730 --> 00:15:43,950 будзе ў прызнаць, што абсалютна, 392 00:15:43,950 --> 00:15:47,320 асімптатычна, тэарэтычна Гэтая структура дадзеных 393 00:15:47,320 --> 00:15:50,470 няма лепш, чым проста адзін масіўны звязаны спіс. 394 00:15:50,470 --> 00:15:53,550 І на самай справе, у горшым выпадку, гэта Хэш-табліцы можа ператворыцца ў што. 395 00:15:53,550 --> 00:15:57,620 >> Але ў рэальным свеце, з намі людзі што ўласных кампутарах Mac або ПК або што 396 00:15:57,620 --> 00:16:01,240 і працуеце рэальны свет Праграмнае забеспячэнне на рэальных дадзеных, 397 00:16:01,240 --> 00:16:03,260 які алгарытм вы збіраецеся аддаеце перавагу? 398 00:16:03,260 --> 00:16:09,180 Той, які прымае канчатковыя крокі або той, які бярэ н дзеліцца на 31 крокаў 399 00:16:09,180 --> 00:16:12,900 знайсці нейкі фрагмент дадзеных або шукаць некаторую інфармацыю? 400 00:16:12,900 --> 00:16:16,580 Я маю на ўвазе, абсалютна тыя 31 марак Розніца ў рэальным свеце. 401 00:16:16,580 --> 00:16:18,540 Гэта ў 31 разоў хутчэй. 402 00:16:18,540 --> 00:16:20,880 І мы, людзі, вядома, спадабаецца, што. 403 00:16:20,880 --> 00:16:23,004 >> Так разумею, дыхатамію там паміж фактычна 404 00:16:23,004 --> 00:16:25,920 казаць пра тое, тэарэтычна і асімптатычна якія вызначана 405 00:16:25,920 --> 00:16:28,760 мае значэнне, як мы бачылі, але ў рэальным свеце, 406 00:16:28,760 --> 00:16:32,930 калі вы клапоціцеся аб проста зрабіць чалавек шчаслівы па агульных уваходам, 407 00:16:32,930 --> 00:16:36,010 Вы маглі б вельмі добра хочуць прымаць Справа ў тым, што, так, гэта лінейная, 408 00:16:36,010 --> 00:16:38,360 але гэта ў 31 разоў хутчэй чым лінейная можа быць. 409 00:16:38,360 --> 00:16:41,610 А яшчэ лепш, мы не проста павінны зрабіць што-то адвольнае, як дата нараджэння, 410 00:16:41,610 --> 00:16:44,030 мы маглі б выдаткаваць трохі Чым больш часу і розум 411 00:16:44,030 --> 00:16:47,140 і думаю пра тое, што мы маглі б зрабіць, імя чалавека і, можа быць, 412 00:16:47,140 --> 00:16:50,130 іх дата нараджэння аб'яднаць тых, інгрэдыенты, каб высветліць што-то 413 00:16:50,130 --> 00:16:52,720 што гэта сапраўды больш, раўнамернае і менш п'яны, 414 00:16:52,720 --> 00:16:56,250 так бы мовіць, чым гэтай карціне У цяперашні час мяркуе, што гэта магло б быць. 415 00:16:56,250 --> 00:16:57,750 Як мы маглі рэалізаваць гэта ў кодзе? 416 00:16:57,750 --> 00:17:00,280 Ну, дазвольце мне прапанаваць, што мы проста пазычыць сінтаксіс мы 417 00:17:00,280 --> 00:17:01,799 выкарыстоўваць пару разоў да гэтага часу. 418 00:17:01,799 --> 00:17:03,590 І я збіраюся вызначыць Вузел, які зноў 419 00:17:03,590 --> 00:17:06,812 гэта агульны тэрмін для толькі некаторыя Кантэйнер па якой структуры дадзеных. 420 00:17:06,812 --> 00:17:09,020 Я збіраюся прапанаваць, каб радок будзе там. 421 00:17:09,020 --> 00:17:11,369 Але мы збіраемся пачаць прымаць тыя, навучанне колаў ад цяпер. 422 00:17:11,369 --> 00:17:13,230 >> Няма больш CS50 бібліятэка сапраўды, калі вы не хочаце 423 00:17:13,230 --> 00:17:15,230 выкарыстоўваць яго для вашага фінале Праект, які выдатны, 424 00:17:15,230 --> 00:17:18,569 але зараз мы збіраемся адступаць заслону і кажуць, што гэта ўсяго толькі сімвал зоркі. 425 00:17:18,569 --> 00:17:22,069 Так словы там будзе імя чалавека ў пытанні. 426 00:17:22,069 --> 00:17:25,079 І зараз у мяне ёсць сувязь Тут да наступнага вузлу 427 00:17:25,079 --> 00:17:28,170 так, што яны ўяўляюць кожны з вузлоў 428 00:17:28,170 --> 00:17:30,950 ў ланцугі, патэнцыйна, з звязанага спісу. 429 00:17:30,950 --> 00:17:34,090 >> А цяпер, як я заяўляю, саму табліцу? 430 00:17:34,090 --> 00:17:36,660 Як аб'явіць усю гэтую структуру? 431 00:17:36,660 --> 00:17:40,960 Ну, на самай справе, гэтак жа, як я выкарыстаў паказальнік каб толькі першы элемент спісу 432 00:17:40,960 --> 00:17:44,510 да, так жа я магу толькі сказаць, Мне проста трэба кучу паказальнікаў 433 00:17:44,510 --> 00:17:46,270 ажыццявіць увесь гэты хэш-табліцу. 434 00:17:46,270 --> 00:17:49,484 Я збіраюся ёсць масіў называецца табліца для хэш-табліцы. 435 00:17:49,484 --> 00:17:50,900 Гэта збіраецца быць ёмістасці памеру. 436 00:17:50,900 --> 00:17:52,525 Вось колькі элементаў можа змясціцца ў яго. 437 00:17:52,525 --> 00:17:56,180 І кожны з гэтых элементаў у гэтым Масіў будзе вузел зорка. 438 00:17:56,180 --> 00:17:56,810 Чаму? 439 00:17:56,810 --> 00:18:00,160 Ну, за гэтую карціну, тое, што я рэалізацыі хэш-табліцу ў якасці 440 00:18:00,160 --> 00:18:04,330 эфектыўна ў пачатак усяго гэта масіў, які мы намалявалі вертыкальна, 441 00:18:04,330 --> 00:18:06,820 кожны з якіх квадратаў ўяўляе сабой паказальнік. 442 00:18:06,820 --> 00:18:09,170 Гэта тыя, якія маюць касую рысу праз іх проста нулявым. 443 00:18:09,170 --> 00:18:11,410 І тыя, якія маюць Стрэлкі, якія ідуць справа 444 00:18:11,410 --> 00:18:16,140 фактычныя паказальнікі на фактычныя вузлоў, Ergo пачатак звязанага спісу. 445 00:18:16,140 --> 00:18:19,050 >> Дык вось, тое, як мы маглі б рэалізацыі хэш-табліцу, што 446 00:18:19,050 --> 00:18:21,580 рэалізуе асобны ланцужкі. 447 00:18:21,580 --> 00:18:22,840 Цяпер мы можам зрабіць лепш? 448 00:18:22,840 --> 00:18:25,632 Добра, я абяцаў у мінулы раз, што мы маглі б дамагчыся сталага часу. 449 00:18:25,632 --> 00:18:27,381 І я як бы даў вам пастаянная часу тут, 450 00:18:27,381 --> 00:18:29,850 але тады не сказаў на самай справе Пастаянная часу, таму што гэта ўсё ж такі 451 00:18:29,850 --> 00:18:31,890 залежыць ад агульнага Колькасць элементаў 452 00:18:31,890 --> 00:18:34,500 Вы ўводу ў Структура дадзеных. 453 00:18:34,500 --> 00:18:35,980 Але выкажам здагадку, што мы зрабілі гэта. 454 00:18:35,980 --> 00:18:39,550 Дазвольце мне вярнуцца да экрана тут. 455 00:18:39,550 --> 00:18:44,520 Дазвольце мне таксама праецыраваць гэта тут, відавочна, экран, і выкажам здагадку, што я зрабіў гэта. 456 00:18:44,520 --> 00:18:49,300 Выкажам здагадку, што я хацеў, каб ўставіць імя Daven ў ў маёй структуры дадзеных. 457 00:18:49,300 --> 00:18:52,100 >> Таму я хачу, каб ўставіць радок Daven ў структуры дадзеных. 458 00:18:52,100 --> 00:18:54,370 Што рабіць, калі я не выкарыстоўваю хэш-табліцы, але я выкарыстоўваю 459 00:18:54,370 --> 00:18:56,980 што-тое, што больш дрэвападобная як радаводу, дзе 460 00:18:56,980 --> 00:18:59,670 ў вас ёсць корань у Верхняя і затым вузлы і лісце 461 00:18:59,670 --> 00:19:01,440 што ісці ўніз і вонкі. 462 00:19:01,440 --> 00:19:04,450 Выкажам здагадку, тое, што я хочаце ўставіць Daven-х 463 00:19:04,450 --> 00:19:06,430 у тое, што ў цяперашні час пусты спіс. 464 00:19:06,430 --> 00:19:09,780 Я збіраюся зрабіць наступнае: я збіраецца стварыць вузел у гэтай сям'і 465 00:19:09,780 --> 00:19:15,170 дрэвападобная структура дадзеных, якая выглядае трохі як гэта, кожны з якіх 466 00:19:15,170 --> 00:19:19,640 прастакутнікі ўжо, скажам, а пакуль 26 элементаў у ім. 467 00:19:19,640 --> 00:19:21,650 І кожны з клетак у гэтым масіве будзе 468 00:19:21,650 --> 00:19:23,470 прадстаўляць літару алфавіту. 469 00:19:23,470 --> 00:19:28,190 >> У прыватнасці, я збіраюся лячыць гэта, то В, то С, затым D, 470 00:19:28,190 --> 00:19:29,310 гэты тут. 471 00:19:29,310 --> 00:19:32,940 Дык гэта будзе эфектыўна ўяўляюць літару D. 472 00:19:32,940 --> 00:19:36,040 Але, каб ўставіць ўсе Daven-х назваць мне трэба зрабіць трохі больш. 473 00:19:36,040 --> 00:19:37,840 Так што я спачатку буду хэш, так бы мовіць. 474 00:19:37,840 --> 00:19:41,049 Я збіраюся паглядзець на першую літару у Daven, які, відавочна, з'яўляецца D, 475 00:19:41,049 --> 00:19:42,840 і я збіраюся вылучыць вузел, які выглядае 476 00:19:42,840 --> 00:19:45,570 як this-- вялікі прастакутнік вялікі дастаткова, каб адпавядаць ўвесь алфавіт. 477 00:19:45,570 --> 00:19:47,140 >> Цяпер D робіцца. 478 00:19:47,140 --> 00:19:49,720 Цяпер А. Д-А-В-Е-Н і з'яўляецца мэтай. 479 00:19:49,720 --> 00:19:51,220 Так што цяпер я збіраюся зрабіць гэта. 480 00:19:51,220 --> 00:19:54,027 Як толькі я пачаў D апавяшчэнне няма паказальніка там. 481 00:19:54,027 --> 00:19:56,860 Гэта каштоўнасці смецця на дадзены момант, ці я мог бы ініцыялізаваць яго да нуля. 482 00:19:56,860 --> 00:19:59,630 Але дазвольце мне працягваць ісці з гэтая ідэя пабудовы дрэва. 483 00:19:59,630 --> 00:20:04,260 Дазвольце мне вылучыць яшчэ адзін з іх вузлы, якія мае 26 элементаў у ім. 484 00:20:04,260 --> 00:20:05,150 >> І ведаеце што? 485 00:20:05,150 --> 00:20:09,130 Калі гэта ўсяго толькі вузел у памяці, што Я стварыў з Таноса, выкарыстоўваючы-структуру 486 00:20:09,130 --> 00:20:11,240 як мы хутка ўбачым, Я збіраюся зрабіць this-- 487 00:20:11,240 --> 00:20:14,450 Я збіраюся намаляваць стрэлку ад рэч, якая прадстаўлена D ўніз 488 00:20:14,450 --> 00:20:15,860 у гэтым новым вузле. 489 00:20:15,860 --> 00:20:19,240 А цяпер, па-першае побач Ліст на імя Daven ў, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- я збіраюся ісці наперад і зрабіць яшчэ адзін вузел, як гэта, 491 00:20:24,150 --> 00:20:30,150 у выніку чаго, у V элементы тут, якія мы будзем маляваць для instance-- воклічамі. 492 00:20:30,150 --> 00:20:31,020 Мы не будзем маляваць там. 493 00:20:31,020 --> 00:20:31,936 Гэта збіраецца ісці сюды. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Тады мы ідзем да лічаць, што гэта В. 496 00:20:35,712 --> 00:20:44,920 А потым сюды мы збіраемся індэкса у параўнанні з V у тое, што мы будзем разглядаць E. 497 00:20:44,920 --> 00:20:50,100 А потым адсюль мы збіраемся пайсці мець адзін з гэтых вузлоў тут. 498 00:20:50,100 --> 00:20:52,930 І цяпер у нас ёсць пытанне, каб адказаць. 499 00:20:52,930 --> 00:20:57,840 Мне трэба неяк паказаць, што мы ў канцы радка Daven. 500 00:20:57,840 --> 00:20:59,490 Так што я мог проста пакінуць яго пустым. 501 00:20:59,490 --> 00:21:02,670 >> Але што рабіць, калі ў нас ёсць Daven-х Прозвішча, імя таксама, што 502 00:21:02,670 --> 00:21:04,280 гэта, як мы ўжо казалі, Дэвенпорт? 503 00:21:04,280 --> 00:21:06,970 Так што, калі Daven з'яўляецца фактычна падрадок, 504 00:21:06,970 --> 00:21:08,960 прэфіксам значна больш доўгай радкі? 505 00:21:08,960 --> 00:21:11,450 Мы не можам проста пастаянна сказаць нічога не адбываецца 506 00:21:11,450 --> 00:21:14,410 туды, таму што мы маглі ніколі не ўставіць слова, як Давенпорт 507 00:21:14,410 --> 00:21:15,840 ў гэтай структуры дадзеных 508 00:21:15,840 --> 00:21:19,560 >> Так што мы можам зрабіць, а не з'яўляецца лячэння кожнага з гэтых элементаў 509 00:21:19,560 --> 00:21:22,170 як можа быць, маючы два элементы ўнутры іх. 510 00:21:22,170 --> 00:21:24,810 Адным з іх з'яўляецца паказальнікам, на самай справе, як я рабіў. 511 00:21:24,810 --> 00:21:27,100 Такім чынам, кожны з гэтых скрынь гэта не проста адна клетка. 512 00:21:27,100 --> 00:21:29,855 Але што рабіць, калі верхняя одно-- ніжні-х 513 00:21:29,855 --> 00:21:32,230 будзе нулявым, таму што няма Дэвенпорт толькі пакуль. 514 00:21:32,230 --> 00:21:34,197 Што рабіць, калі верхні гэта нейкая асаблівая каштоўнасць? 515 00:21:34,197 --> 00:21:36,530 І гэта будзе трохі цяжка зрабіць гэта гэты памер. 516 00:21:36,530 --> 00:21:38,130 Але мяркую, што гэта проста птушка. 517 00:21:38,130 --> 00:21:38,920 Праверце. 518 00:21:38,920 --> 00:21:44,230 Д-А-В-Е-Н ўяўляе сабой радок У гэтай структуры дадзеных. 519 00:21:44,230 --> 00:21:48,350 >> Між тым, калі б я меў больш месца тут, што я мог зрабіць P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 і я мог бы паставіць праверку ў вузле што ёсць літара Т ў самым канцы. 521 00:21:52,650 --> 00:21:55,460 Так што гэта масава Комплекс выгляд структуры дадзеных. 522 00:21:55,460 --> 00:21:57,210 І мой почырк вядома, не дапаможа. 523 00:21:57,210 --> 00:22:00,043 Але калі б я хацеў, каб ўставіць што-то яшчэ, падумайце, што мы будзем рабіць. 524 00:22:00,043 --> 00:22:03,370 Калі б мы хацелі паставіць Давіда ў, мы прытрымлівацца той жа логіцы, D-A-V, 525 00:22:03,370 --> 00:22:08,802 але цяпер я хацеў бы адзначыць у наступным Элемент не ад Е, але ад I да D. 526 00:22:08,802 --> 00:22:10,760 Так што гэта будзе больш вузлоў у гэтым дрэве. 527 00:22:10,760 --> 00:22:12,325 Мы збіраемся мець выкліку Таноса больш. 528 00:22:12,325 --> 00:22:14,700 Але я не хачу, каб зрабіць поўны беспарадак малюнка. 529 00:22:14,700 --> 00:22:17,710 Такім чынам, давайце замест гэтага глядзець у адным які быў папярэдне сфармуляваны 530 00:22:17,710 --> 00:22:21,810 як гэта з не кропка, кропка, кропкі, але толькі скарочаныя масівы. 531 00:22:21,810 --> 00:22:23,950 Але кожны з вузлоў ў гэтым дрэве тут 532 00:22:23,950 --> 00:22:26,700 уяўляе той жа thing-- Масіў Прамень памеру 26. 533 00:22:26,700 --> 00:22:28,860 >> Ці, калі мы хочам быць сапраўды правільнае зараз, што 534 00:22:28,860 --> 00:22:30,790 калі хто-то імя, як апостраф, давайце 535 00:22:30,790 --> 00:22:35,560 Выкажам здагадку, што кожны вузел мае фактычна як 27 індэксаў ў гэтым, а не толькі 26. 536 00:22:35,560 --> 00:22:42,020 Так што гэта зараз будзе дадзеных Структура называецца trie-- T-R-I-Е. 537 00:22:42,020 --> 00:22:46,120 Trie, які, як мяркуецца, гістарычна разумны імя для дрэва 538 00:22:46,120 --> 00:22:49,040 які аптымізаваны для пошук, які вядома ж, 539 00:22:49,040 --> 00:22:50,870 пішацца з I-Е так гэта Trie. 540 00:22:50,870 --> 00:22:52,710 Але гэта гісторыя сінтаксічнага дрэва. 541 00:22:52,710 --> 00:22:55,860 >> Так Trie гэта дрэвападобная дадзеных Структура як радаводу 542 00:22:55,860 --> 00:22:57,510 што ў канчатковым рахунку вядзе сябе так. 543 00:22:57,510 --> 00:23:00,890 А вось яшчэ адзін прыклад цэлая куча імёнаў іншых людзей. 544 00:23:00,890 --> 00:23:03,540 Але пытанне цяпер пад рукой тое, што ёсць 545 00:23:03,540 --> 00:23:08,070 мы атрымалі шляхам увядзення магчыма больш складанай структурай дадзеных, і адзін, 546 00:23:08,070 --> 00:23:09,870 шчыра кажучы, што выкарыстоўвае шмат памяці. 547 00:23:09,870 --> 00:23:11,703 >> Таму што нават пры тым, што, на дадзены момант, я толькі 548 00:23:11,703 --> 00:23:15,050 з дапамогай паказальніка Д і І V і Es і Ns, 549 00:23:15,050 --> 00:23:16,700 Я марнаваць чартоўску шмат памяці. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Але дзе я праводжу адзін рэсурс, Я, як правіла, нічога атрымаць таму іншы. 552 00:23:22,660 --> 00:23:26,020 Так што, калі я марную больш месца, што, верагодна, надзея? 553 00:23:26,020 --> 00:23:27,407 Гэта я марную менш чым? 554 00:23:27,407 --> 00:23:28,240 АЎДЫТОРЫЯ: Менш часу. 555 00:23:28,240 --> 00:23:28,990 DAVID Малання: Час. 556 00:23:28,990 --> 00:23:30,320 Цяпер, чаму гэта можа быць? 557 00:23:30,320 --> 00:23:33,880 Ну, тое, што з'яўляецца ўстаўка час, з пункту гледжання вялікі O цяпер, 558 00:23:33,880 --> 00:23:37,660 імя, як Daven або Дэвенпорт або Дэвід? 559 00:23:37,660 --> 00:23:39,340 Ну, Daven было пяць крокаў. 560 00:23:39,340 --> 00:23:42,350 Дэвенпорт будзе дзевяць крокаў, так што было б некалькі крокаў. 561 00:23:42,350 --> 00:23:44,250 Дэвід будзе пяць крокаў, а таксама. 562 00:23:44,250 --> 00:23:47,230 Так што тыя, канкрэтныя нумары, але, безумоўна, ёсць 563 00:23:47,230 --> 00:23:49,550 верхняя мяжа Даўжыня чыё-то імя. 564 00:23:49,550 --> 00:23:52,240 І сапраўды, у задачы наборы пяці спецыфікацыі, 565 00:23:52,240 --> 00:23:54,050 мы збіраемся прапанаваць што гэта нешта 566 00:23:54,050 --> 00:23:55,470 гэта 40-некаторыя з лішнім персанажаў. 567 00:23:55,470 --> 00:23:58,180 >> Рэальна, ніхто не мае бясконца доўгае імя, 568 00:23:58,180 --> 00:24:01,542 які павінен сказаць, што даўжыня назваць або даўжыня радка мы маглі б 569 00:24:01,542 --> 00:24:03,750 ёсць пэўная стан Структура, магчыма, што? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Гэта пастаянная. 572 00:24:06,250 --> 00:24:06,430 Ці не так? 573 00:24:06,430 --> 00:24:09,310 Гэта можа быць вялікі пастаяннай, як 40-тое, але гэта канстанта. 574 00:24:09,310 --> 00:24:13,752 І гэта не мае ніякага залежнасць ад таго, колькі іншыя назвы з'яўляюцца ў гэтай структуры дадзеных. 575 00:24:13,752 --> 00:24:15,460 Іншымі словамі, калі I хацеў зараз ўставіць 576 00:24:15,460 --> 00:24:20,540 Колтон або Габрыэль або Роб або Zamyla або Элісан або Белинда або любыя іншыя імёны 577 00:24:20,540 --> 00:24:23,940 ад персаналу ў гэтых дадзеных Структура, з'яўляецца час працы 578 00:24:23,940 --> 00:24:26,750 ўстаўкі і іншыя назвы будзе наогул ўплыў 579 00:24:26,750 --> 00:24:30,220 па тым, як і многія іншыя элементы з'яўляюцца ў структуры дадзеных, ужо? 580 00:24:30,220 --> 00:24:31,040 Гэта не так. 581 00:24:31,040 --> 00:24:31,540 Ці не так? 582 00:24:31,540 --> 00:24:36,150 Таму што мы эфектыўна выкарыстоўваць гэта шматслаёвая хэш-табліцы. 583 00:24:36,150 --> 00:24:38,280 І час працы любы з гэтых аперацый 584 00:24:38,280 --> 00:24:41,510 залежыць не ад колькасці элементы, якія ў структуры дадзеных 585 00:24:41,510 --> 00:24:43,090 або што ў канчатковым выніку адбываецца каб быць у структуры дадзеных, 586 00:24:43,090 --> 00:24:44,714 але па даўжыні, што канкрэтна? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Радок быць устаўлены, які робіць 589 00:24:49,200 --> 00:24:52,580 гэта асімптатычна пастаянным time-- вялікі O аднаго. 590 00:24:52,580 --> 00:24:54,720 І, шчыра кажучы, проста ў рэальны свет, гэта 591 00:24:54,720 --> 00:24:58,380 азначае ўстаўкі назву Daven бярэ як пяць крокаў, або Дэвенпорт дзевяць 592 00:24:58,380 --> 00:25:00,100 крокі, або Дэвід пяць крокаў. 593 00:25:00,100 --> 00:25:03,071 Гэта па-чартоўску маленькія раз хадавыя. 594 00:25:03,071 --> 00:25:05,320 І, сапраўды, гэта вельмі добрая рэч, асабліва калі 595 00:25:05,320 --> 00:25:08,126 гэта не залежыць ад агульнай Колькасць элементаў у там. 596 00:25:08,126 --> 00:25:10,500 Так як мы можам гэта рэалізаваць Такая структура ў кодзе? 597 00:25:10,500 --> 00:25:12,900 Гэта крыху больш, Комплекс, але ўсё-такі гэта 598 00:25:12,900 --> 00:25:15,050 толькі ўжыванне асноўныя будаўнічыя блокі. 599 00:25:15,050 --> 00:25:17,830 Я збіраюся перагледзець нам вузел наступным чынам: 600 00:25:17,830 --> 00:25:21,100 Ьоо называецца word-- і гэта можна было б назваць што-небудзь. 601 00:25:21,100 --> 00:25:23,970 Але Ьоо ўяўляе тое, што я звярнуў як галачкай. 602 00:25:23,970 --> 00:25:24,490 Так. 603 00:25:24,490 --> 00:25:26,720 Гэта канец радка У гэтай структуры дадзеных. 604 00:25:26,720 --> 00:25:30,702 >> І, вядома, вузел зорка там мае на ўвазе дзяцей. 605 00:25:30,702 --> 00:25:32,410 І, на самай справе, гэтак жа, як генеалагічнае дрэва, вы 606 00:25:32,410 --> 00:25:34,370 разгледзіць вузлы што вісяць ад 607 00:25:34,370 --> 00:25:36,920 з ніжняй частцы якой-небудзь з бацькоў Элемент быць дзеці. 608 00:25:36,920 --> 00:25:40,510 І таму дзеці збіраецца быць масівам 27, 27 адзін 609 00:25:40,510 --> 00:25:41,680 проста быць для апострафа. 610 00:25:41,680 --> 00:25:43,390 Мы збіраемся, каб разабрацца Асаблівы выпадак гэтага. 611 00:25:43,390 --> 00:25:45,400 Такім чынам, вы можаце мець пэўны Імёны ўдзельнікаў апострафы. 612 00:25:45,400 --> 00:25:47,399 Можа быць, нават злучок павінны ісці туды, але вы будзеце 613 00:25:47,399 --> 00:25:50,330 см у р наборы 5 мы толькі сыходу аб лістах і апострафы. 614 00:25:50,330 --> 00:25:52,990 >> А потым, як вы ўяўляеце сама структура дадзеных? 615 00:25:52,990 --> 00:25:56,454 Як вы ўяўляеце корань гэтага сінтаксічнага дрэва, так бы мовіць? 616 00:25:56,454 --> 00:25:59,620 Ну, сапраўды гэтак жа як з звязанага спісу, вы патрэбен паказальнік на першы элемент. 617 00:25:59,620 --> 00:26:04,270 З сінтаксічнага дрэва трэба проста адзін паказальнік на корань гэтага сінтаксічнага дрэва. 618 00:26:04,270 --> 00:26:07,290 І адтуль вы можаце хэш Ваш шлях ўніз ўсё глыбей і глыбей 619 00:26:07,290 --> 00:26:10,460 для кожнага іншага вузла ў структуры. 620 00:26:10,460 --> 00:26:13,440 Так проста з гэтай слоікам мы ўяўляем, што-структуру. 621 00:26:13,440 --> 00:26:15,877 >> Цяпер Meanwhile-- О, пытанне. 622 00:26:15,877 --> 00:26:17,220 >> АЎДЫТОРЫЯ: Што Ьоо слова? 623 00:26:17,220 --> 00:26:20,490 >> DAVID Малання: Bool слова проста гэта C ўвасабленне 624 00:26:20,490 --> 00:26:22,920 з таго, што я апісаў у гэтым полі тут, калі 625 00:26:22,920 --> 00:26:26,000 Я пачаў падзелу кожнай з элементы масіва на дзве часткі. 626 00:26:26,000 --> 00:26:27,600 Адным з іх з'яўляецца паказальнікам на наступны вузел. 627 00:26:27,600 --> 00:26:30,280 Іншы павінен быць нешта накшталт сцяжка 628 00:26:30,280 --> 00:26:33,770 сказаць так, ёсць Слова Daven што тут сканчаецца, 629 00:26:33,770 --> 00:26:35,610 таму што мы не хочам, на дадзены момант, Дэйв. 630 00:26:35,610 --> 00:26:39,320 >> Нават пры тым, што Дэйв будзе законным слова, што ён не ў сінтаксічнага дрэва 631 00:26:39,320 --> 00:26:39,830 яшчэ. 632 00:26:39,830 --> 00:26:40,950 І D няма ні слова. 633 00:26:40,950 --> 00:26:42,770 І D-гэта не тое слова або імя. 634 00:26:42,770 --> 00:26:45,020 Так галачкай паказвае толькі адзін раз вас 635 00:26:45,020 --> 00:26:48,190 ўдарыў гэты вузел папярэдняя шлях персанажаў 636 00:26:48,190 --> 00:26:50,700 на самай справе гэта радок, як вы ўставілі. 637 00:26:50,700 --> 00:26:53,660 Так што ўсё Ьоо там робіць для нас. 638 00:26:53,660 --> 00:26:55,500 >> Любыя іншыя пытанні аб спробах? 639 00:26:55,500 --> 00:26:56,215 Так. 640 00:26:56,215 --> 00:26:58,035 >> АЎДЫТОРЫЯ: Што такое перакрыцце? 641 00:26:58,035 --> 00:26:59,945 Што рабіць, калі ў вас ёсць Дэйва і Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID Малання: Выдатна. 643 00:27:00,820 --> 00:27:02,580 Што рабіць, калі ў вас ёсць Дэйва і Daven? 644 00:27:02,580 --> 00:27:06,240 Так што, калі мы ўстаўляем, кажуць мянушку, для David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 На самай справе гэта супер проста. 647 00:27:08,700 --> 00:27:10,325 Такім чынам, мы толькі збіраемся распачаць чатыры кроку. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 Д-А-В-Е. І тое, што мне трэба зрабіць, як толькі я стукнуў, што чацвёрты вузел? 650 00:27:15,847 --> 00:27:16,680 Проста збіраюся праверыць. 651 00:27:16,680 --> 00:27:18,000 Мы ўжо добра ісці. 652 00:27:18,000 --> 00:27:18,840 Гатова. 653 00:27:18,840 --> 00:27:19,750 Чатыры кроку. 654 00:27:19,750 --> 00:27:21,590 Пастаяннае час асімптатычна. 655 00:27:21,590 --> 00:27:26,300 І зараз мы паказалі, што абодва Dave і Daven з'яўляюцца радкамі ў структуры. 656 00:27:26,300 --> 00:27:27,710 Так не праблема. 657 00:27:27,710 --> 00:27:30,200 І звярніце ўвагу, як прысутнасць з Daven не зрабіць гэта 658 00:27:30,200 --> 00:27:34,750 ўзяць больш часу або менш Час для Дэйва, і наадварот. 659 00:27:34,750 --> 00:27:36,000 >> Так што яшчэ мы можам цяпер зрабіць? 660 00:27:36,000 --> 00:27:40,680 Мы выкарысталі гэтую метафару да латкоў, які ўяўляе нешта. 661 00:27:40,680 --> 00:27:43,380 Але аказваецца, што чарка латкоў на самай справе 662 00:27:43,380 --> 00:27:47,187 дэманстратыўнае іншага абстрактнага дадзеных type-- больш высокую структуру дадзеных ўзроўню 663 00:27:47,187 --> 00:27:49,770 што ў канцы дня гэта проста як масіў або звязаны спіс 664 00:27:49,770 --> 00:27:50,970 ці нешта больш прыземленым. 665 00:27:50,970 --> 00:27:53,270 Але гэта больш цікава канцэптуальнае паняцце. 666 00:27:53,270 --> 00:27:56,440 Стэк, як гэта Латкі тут у Мазер, 667 00:27:56,440 --> 00:27:58,750 як правіла, называюць проста that-- стэк. 668 00:27:58,750 --> 00:28:02,540 >> І ў гэтым тыпе структуры дадзеных ў вас ёсць два operations-- 669 00:28:02,540 --> 00:28:05,880 ў вас ёсць адзін пад назвай штуршок для дадаючы што-то ў стэк, 670 00:28:05,880 --> 00:28:08,320 як пакласці яшчэ адзін латок Вярнуўшыся на вяршыні стэка. 671 00:28:08,320 --> 00:28:11,350 І тады поп, які азначае, што вы ўзяць верхні оф латка. 672 00:28:11,350 --> 00:28:16,210 Але тое, што ключ аб стэка з'яўляецца тое, што ён атрымаў гэтую цікавую характарыстыку. 673 00:28:16,210 --> 00:28:19,560 Як сталовай персаналу перастаўляючы латкі для наступнага прыёму ежы, 674 00:28:19,560 --> 00:28:21,380 што будзе праўда пра тое, як студэнты 675 00:28:21,380 --> 00:28:22,856 ўзаемадзейнічаць з гэтай структурай дадзеных? 676 00:28:22,856 --> 00:28:24,480 АЎДЫТОРЫЯ: Яны збіраюцца поп прэч. 677 00:28:24,480 --> 00:28:26,550 DAVID Малання: Яны збіраюцца поп прэч, мы спадзяемся на вяршыню. 678 00:28:26,550 --> 00:28:28,910 У адваротным выпадку гэта проста нейкая дурная каб прайсці ўвесь шлях да дна. 679 00:28:28,910 --> 00:28:29,070 Ці не так? 680 00:28:29,070 --> 00:28:31,620 Структура дадзеных на самай справе не дазваляюць Вы, каб захапіць ніжнюю латок, па меншай меры 681 00:28:31,620 --> 00:28:32,520 лёгка. 682 00:28:32,520 --> 00:28:35,040 Так што гэта цікава Ўласцівасць да стэку 683 00:28:35,040 --> 00:28:39,730 што апошні элемент у гэта будзе першым з. 684 00:28:39,730 --> 00:28:43,400 І кампутарныя навукоўцы называюць гэта LIFO-- апошнім прыйшоў, першым выйшаў. 685 00:28:43,400 --> 00:28:45,540 І гэта на самай справе ёсць цікавыя прыкладання. 686 00:28:45,540 --> 00:28:50,090 Гэта не абавязкова так відавочна, як некаторыя і іншыя, але ён можа, вядома, быць карысным, 687 00:28:50,090 --> 00:28:54,040 і яно можа, на самай справе, быць рэалізаваны праз пару-рознаму. 688 00:28:54,040 --> 00:28:58,550 >> Так што, і на самой справе, хай мне не ныраць у тым, што. 689 00:28:58,550 --> 00:28:59,860 Давайце зробім гэта замест гэтага. 690 00:28:59,860 --> 00:29:03,700 Давайце паглядзім на той, які амаль Тая ж ідэя, але гэта крыху больш справядлівым. 691 00:29:03,700 --> 00:29:04,200 Ці не так? 692 00:29:04,200 --> 00:29:07,560 Калі вы адзін з гэтых хлопчыкаў вентылятараў або дзяўчынкі, што сапраўды любіць прадукты кампаніі Apple 693 00:29:07,560 --> 00:29:10,130 і вы прачнуліся у 3:00 выбудоўвацца ў нейкую краму 694 00:29:10,130 --> 00:29:14,150 каб атрымаць самую апошнюю iPhone, вы магчыма, у чарзе, як гэта. 695 00:29:14,150 --> 00:29:15,800 >> Цяпер чарга вельмі свядома назваў. 696 00:29:15,800 --> 00:29:18,190 Гэта лінія, таму што ёсць некаторыя справядлівасць да яго. 697 00:29:18,190 --> 00:29:18,690 Ці не так? 698 00:29:18,690 --> 00:29:21,690 Было б выгляд смактаў калі ў вас ёсць атрымаў там першы ў Apple Store 699 00:29:21,690 --> 00:29:25,700 але вы эфектыўна ніжні Латок, таму што супрацоўнікі Apple, затым 700 00:29:25,700 --> 00:29:28,189 поп апошні чалавек, які на самай справе трапіў у лінію. 701 00:29:28,189 --> 00:29:31,230 Так стэкаў і чэргаў, хоць функцыянальна яны накшталт ў same-- 702 00:29:31,230 --> 00:29:33,105 гэта проста гэтая калекцыя рэсурсаў, што гэта 703 00:29:33,105 --> 00:29:36,210 будзе расці і shrink-- там Гэты аспект справядлівасці да яго, 704 00:29:36,210 --> 00:29:39,634 па меншай меры, у рэальным свеце, дзе аперацыі вы трэніруецеся 705 00:29:39,634 --> 00:29:40,800 прынцыпова адрозніваюцца. 706 00:29:40,800 --> 00:29:43,360 Stack-- чарзе rather--, як кажуць, 707 00:29:43,360 --> 00:29:45,320 дзве аперацыі: чэргі н і чэргаў d. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Ці вы можаце патэлефанаваць ім любую колькасць рэчаў. 710 00:29:48,090 --> 00:29:50,770 Але вы проста хочаце, каб захапіць паняцце, што чалавек дадання 711 00:29:50,770 --> 00:29:53,230 і, у канчатковым рахунку адзін аднімання. 712 00:29:53,230 --> 00:29:58,840 >> Зараз пад капотам, як стэк і чарга можа быць рэалізаваны як? 713 00:29:58,840 --> 00:30:01,390 Мы не будзем удавацца ў кодзе гэта таму, што чым вышэй узровень 714 00:30:01,390 --> 00:30:03,387 Ідэя з'яўляецца свайго роду больш відавочным. 715 00:30:03,387 --> 00:30:04,470 Я маю на ўвазе, што ты гэта робяць людзі? 716 00:30:04,470 --> 00:30:07,030 Калі я першы чалавек у кампаніі Apple Шануйце і гэта ўваходныя дзверы, 717 00:30:07,030 --> 00:30:08,130 Вы ведаеце, што я збіраюся стаяць тут. 718 00:30:08,130 --> 00:30:09,750 І наступны чалавек збіраюся стаяць тут. 719 00:30:09,750 --> 00:30:11,500 І наступны чалавек збіраюся стаяць тут. 720 00:30:11,500 --> 00:30:13,792 Так што структура дадзеных паддаецца чарзе? 721 00:30:13,792 --> 00:30:14,542 >> АЎДЫТОРЫЯ: Чарга. 722 00:30:14,542 --> 00:30:15,667 DAVID Малання: Ну, чэргі. 723 00:30:15,667 --> 00:30:16,390 Вядома. 724 00:30:16,390 --> 00:30:16,920 Што яшчэ? 725 00:30:16,920 --> 00:30:17,600 >> АЎДЫТОРЫЯ: звязаны спіс. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Малання: звязаны спіс можна рэалізаваць. 727 00:30:18,990 --> 00:30:22,500 І звязаны спіс добра, таму што тады яна можа расці калі заўгодна доўга, у адрозненне 728 00:30:22,500 --> 00:30:24,880 да таго, некаторы фіксаваны лік людзей у краме. 729 00:30:24,880 --> 00:30:27,030 Але, можа быць, фіксаваны лік месцаў з'яўляецца законным. 730 00:30:27,030 --> 00:30:30,350 Таму што, калі ў іх толькі ёсць, як 20 IPhones ў першы дзень, можа быць, 731 00:30:30,350 --> 00:30:33,930 яны павінны толькі масіў памеру 20 каб прадставіць гэтую чаргу, якая 732 00:30:33,930 --> 00:30:37,070 толькі сказаць зараз, як толькі мы пачынаем казаць аб гэтых высокіх задач на ўзроўні, 733 00:30:37,070 --> 00:30:38,890 Вы можаце рэалізаваць яго у любым ліку шляхоў. 734 00:30:38,890 --> 00:30:42,030 І там, напэўна, толькі збіраюся быць кампраміс у прасторы і часе 735 00:30:42,030 --> 00:30:43,950 ці проста ва ўласным складанасці кода. 736 00:30:43,950 --> 00:30:45,380 >> А як наконт стэка? 737 00:30:45,380 --> 00:30:48,190 Ну, стэк, мы бачылі занадта можа быць проста гэтыя латкі. 738 00:30:48,190 --> 00:30:50,007 І вы маглі б рэалізаваць гэты масіў. 739 00:30:50,007 --> 00:30:53,090 Але ў нейкі момант, калі вы карыстаецеся масіў, што адбудзецца з латкоў 740 00:30:53,090 --> 00:30:54,173 Вы спрабуеце здушыць? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Добра. 743 00:30:55,670 --> 00:30:57,490 Вы толькі збіраецеся быць у стане пайсці так высока. 744 00:30:57,490 --> 00:31:00,156 І я думаю, што ў Mather яны фактычна ўбудавальныя ў гэтую адтуліну. 745 00:31:00,156 --> 00:31:01,950 Так на самой справе, гэта амаль як Mather выкарыстоўвае 746 00:31:01,950 --> 00:31:03,783 масіў фіксаванага памеру, таму што вы можаце толькі 747 00:31:03,783 --> 00:31:08,302 падыходзяць так шмат латкоў у гэтым адкрыцці ў сцяна ўнізе калені людзей. 748 00:31:08,302 --> 00:31:10,010 І так, што можа быць кажуць, масіў, 749 00:31:10,010 --> 00:31:14,300 але мы, безумоўна, можа рэалізаваць, што ў больш агульным з звязанага спісу. 750 00:31:14,300 --> 00:31:16,390 >> Ну, тое, што пра іншую структуры дадзеных? 751 00:31:16,390 --> 00:31:18,760 Дазвольце мне падцягнуць адзін іншы візуальны тут. 752 00:31:18,760 --> 00:31:24,710 Нешта накшталт, як пра гэта адзін тут? 753 00:31:24,710 --> 00:31:28,920 Чаму гэта можа быць карысна мець не што-то фантазіі, як сінтаксічнага дрэва, якое 754 00:31:28,920 --> 00:31:32,370 мы бачылі б гэтыя вельмі шырокія вузлы, кожны з якіх знаходзіцца ў масіве? 755 00:31:32,370 --> 00:31:35,740 Але што, калі мы робім нешта больш проста, як стары школьны радаводу, 756 00:31:35,740 --> 00:31:38,110 кожны з якіх вузлы тут толькі захаванні нумары. 757 00:31:38,110 --> 00:31:42,180 Замест імя ці нашчадка проста захаванні нумары накшталт гэтага. 758 00:31:42,180 --> 00:31:45,250 >> Ну, жаргон мы выкарыстоўваем у структуры дадзеных з'яўляецца абедзве спробы 759 00:31:45,250 --> 00:31:49,510 і дрэвы, дзе Trie, зноў жа, толькі адзін, вузлы якога з'яўляюцца масівы, 760 00:31:49,510 --> 00:31:51,680 яшчэ, што вы маглі б выкарыстоўваць з пачатковай школы 761 00:31:51,680 --> 00:31:53,860 калі вы зрабілі сям'ю tree-- лісце і корань 762 00:31:53,860 --> 00:31:57,250 з дрэва і дзяцей бацька і іх браты і сёстры. 763 00:31:57,250 --> 00:32:03,670 І мы маглі б рэалізаваць дрэва, Напрыклад, як проста, як гэта. 764 00:32:03,670 --> 00:32:07,420 Дрэва, калі ён у выглядзе вузла, адзін з гэтыя колы, што мае шэраг, 765 00:32:07,420 --> 00:32:09,947 гэта не будзе мець адзін паказальнік, а два. 766 00:32:09,947 --> 00:32:11,780 І як толькі вы дадаеце Другі паказальнік, вы 767 00:32:11,780 --> 00:32:13,905 можа на самай справе цяпер зрабіць выгляд двухмернага дадзеных 768 00:32:13,905 --> 00:32:14,780 структуры ў памяці. 769 00:32:14,780 --> 00:32:16,660 Многае, як двухмерных Масіў, вы можаце 770 00:32:16,660 --> 00:32:18,904 ёсць выгляд двухмерных звязаныя спісы, але тыя, 771 00:32:18,904 --> 00:32:20,820 што вынікаюць ўзоры дзе няма ніякіх цыклаў. 772 00:32:20,820 --> 00:32:24,487 Гэта сапраўды дрэва з адным прабацька шлях сюды, а затым 773 00:32:24,487 --> 00:32:27,320 некаторыя бацькі і дзеці, і унукі і праўнукі. 774 00:32:27,320 --> 00:32:28,370 і гэтак далей. 775 00:32:28,370 --> 00:32:32,390 >> Але тое, што сапраўды ахайна пра гэта таксама, проста каб падражніць вас з трохі кода, 776 00:32:32,390 --> 00:32:35,370 Нагадаем Рэкурсія ад некаторы час таму, у выніку чаго 777 00:32:35,370 --> 00:32:38,220 Вы пішаце функцыю, якая называе сябе. 778 00:32:38,220 --> 00:32:41,140 Гэта прыгожая магчымасць ажыццявіць тое, 779 00:32:41,140 --> 00:32:42,920 як рэкурсіі, таму што лічу гэта. 780 00:32:42,920 --> 00:32:43,860 >> Гэта дрэва. 781 00:32:43,860 --> 00:32:48,040 І я быў трохі анальны з тым, як Я паклаў цэлыя лікі на вуліцу. 782 00:32:48,040 --> 00:32:51,020 Настолькі, што яна мае спецыяльны name-- дрэва двайковага пошуку. 783 00:32:51,020 --> 00:32:53,460 Цяпер мы чулі пра двайковы пошук, але вы можаце 784 00:32:53,460 --> 00:32:55,180 працаваць у зваротным напрамку ад імя Гэтая рэч? 785 00:32:55,180 --> 00:32:59,280 Што такое шаблон, як я ўстаўляецца цэлыя лікі ў гэтым дрэве? 786 00:32:59,280 --> 00:33:00,696 Гэта не адвольная. 787 00:33:00,696 --> 00:33:01,570 Там нейкая карціна. 788 00:33:01,570 --> 00:33:02,090 Так. 789 00:33:02,090 --> 00:33:03,370 >> АЎДЫТОРЫЯ: Невялікія тыя, што злева. 790 00:33:03,370 --> 00:33:03,690 >> DAVID Малання: Так. 791 00:33:03,690 --> 00:33:05,062 Меншыя з іх злева. 792 00:33:05,062 --> 00:33:06,270 Вялікія з іх па праве. 793 00:33:06,270 --> 00:33:12,940 Такі, што сапраўднае зацвярджэнне з'яўляецца бацька перавышае яго левай дзіцяці, 794 00:33:12,940 --> 00:33:14,850 але менш, чым яго правай дзіцяці. 795 00:33:14,850 --> 00:33:17,750 І што ў адзіночку нават рэкурсіўны слоўнае вызначэнне 796 00:33:17,750 --> 00:33:20,500 таму што вы можаце ўжыць, што Тая ж самая логіка для кожнага вузла 797 00:33:20,500 --> 00:33:23,080 І гэта толькі радыюсе па-за, базавы варыянт, калі вам 798 00:33:23,080 --> 00:33:25,740 будзе, калі вы націснеце адну з лісце, так бы мовіць, 799 00:33:25,740 --> 00:33:28,580 дзе адпачынак не мае дзяцей далей. 800 00:33:28,580 --> 00:33:30,614 >> Зараз, як вы маглі б знайсці нумар 44? 801 00:33:30,614 --> 00:33:32,280 Вы б пачаць у корані і сказаць, хм. 802 00:33:32,280 --> 00:33:35,690 55 ня 44 Так што я хачу пайсці правільна ці я хачу пайсці налева? 803 00:33:35,690 --> 00:33:37,190 Ну, відавочна, вы хочаце пайсці налева. 804 00:33:37,190 --> 00:33:40,060 І так гэта проста, як тэлефон Прыклад кніга ў бінарнага пошуку 805 00:33:40,060 --> 00:33:41,099 ў цэлым. 806 00:33:41,099 --> 00:33:43,390 Але мы яго рэалізацыі Зараз трохі больш дынамічна 807 00:33:43,390 --> 00:33:45,339 чым масіў можа дазволіць. 808 00:33:45,339 --> 00:33:48,130 І на самай справе, калі вы хочаце паглядзець на код, на першы погляд, што. 809 00:33:48,130 --> 00:33:49,671 Падобна на тое, цэлай кучай ліній. 810 00:33:49,671 --> 00:33:51,220 Але гэта прыгожа проста. 811 00:33:51,220 --> 00:33:54,490 Калі вы хочаце рэалізаваць функцыю называецца пошук, мэта якога ў жыцці 812 00:33:54,490 --> 00:33:57,290 з'яўляецца пошук значэння як п, цэлы лік, 813 00:33:57,290 --> 00:34:01,756 і вы прайшлі ў адной pointer-- паказальнік на вузел каранёў, 814 00:34:01,756 --> 00:34:04,380 хутчэй, з гэтага дрэва, з якога Вы можаце атрымаць доступ ўсё астатняе, 815 00:34:04,380 --> 00:34:08,850 звярніце ўвагу, як прама Вы можаце рэалізаваць логіку. 816 00:34:08,850 --> 00:34:10,880 Калі дрэва з'яўляецца пустым, Відавочна, што гэта не ёсць. 817 00:34:10,880 --> 00:34:11,880 Давайце проста вярнуцца ілжывым. 818 00:34:11,880 --> 00:34:12,000 Ці не так? 819 00:34:12,000 --> 00:34:14,040 Калі вы не перадаць яму нічога, там нічога няма. 820 00:34:14,040 --> 00:34:17,900 >> У адваротным выпадку, калі п менш Дрэва стрэлкі N-- цяпер стрэлка н, 821 00:34:17,900 --> 00:34:20,670 Нагадаем, мы ўвялі супер коратка на днях, 822 00:34:20,670 --> 00:34:25,100 і гэта проста азначае, дэ-спасылку на ўказальнік і паглядзець на месцы, якое называецца н. 823 00:34:25,100 --> 00:34:27,690 Дык гэта значыць, пайсці туды і паглядзець на полі пад назвай п. 824 00:34:27,690 --> 00:34:33,810 Так што, калі п, значэнне вы далі, менш чым значэнне ў цэлы лік дрэў, 825 00:34:33,810 --> 00:34:35,449 дзе вы хочаце пайсці? 826 00:34:35,449 --> 00:34:36,389 Налева. 827 00:34:36,389 --> 00:34:37,780 >> Так заўважыць Рэкурсія. 828 00:34:37,780 --> 00:34:39,860 Я returning-- не дакладна. 829 00:34:39,860 --> 00:34:40,989 Не хлусня. 830 00:34:40,989 --> 00:34:45,670 Я вяртаюся незалежна адказ ад званка ў сябе, праходзячы 831 00:34:45,670 --> 00:34:50,100 п зноў, які з'яўляецца залішнім, але тое, што крыху адрозніваецца цяпер? 832 00:34:50,100 --> 00:34:51,989 Як я раблю праблему менш? 833 00:34:51,989 --> 00:34:54,920 Я перадаю ў якасці другога Аргумент, ня корань дрэва, 834 00:34:54,920 --> 00:34:59,616 але левая дзіця ў гэтым выпадку. 835 00:34:59,616 --> 00:35:00,990 Так я перадаю ў левым дзіцяці. 836 00:35:00,990 --> 00:35:04,720 >> Між тым, калі п больш, чым вузел У цяперашні час я, гледзячы на, 837 00:35:04,720 --> 00:35:06,690 Я пошук правы бок. 838 00:35:06,690 --> 00:35:10,880 У адваротным выпадку, калі дрэва не з'яўляецца нулявым, і калі элемент не налева 839 00:35:10,880 --> 00:35:13,240 і гэта не права, што дзіўна справа? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Мы фактычна выявілі вузел у Пытанне, а так мы вяртаемся дакладна. 842 00:35:18,440 --> 00:35:21,490 >> Так мы толькі падрапалі паверхню Цяпер некаторыя з гэтых структур дадзеных. 843 00:35:21,490 --> 00:35:24,370 У праблема ўсталяваць пяць вы будзеце даследаваць гэтыя яшчэ далей, 844 00:35:24,370 --> 00:35:27,250 і вам будзе прадастаўлена ваш дызайн Выбар, як ісці аб гэтым. 845 00:35:27,250 --> 00:35:30,250 Тое, што я хацеў бы завяршыць на гэта проста другі тізер 30 846 00:35:30,250 --> 00:35:32,080 пра тое, што чакае на наступным тыдні, і за яго межамі. 847 00:35:32,080 --> 00:35:35,390 >> Як мы begin-- шчасце вы маглі б think-- наш пераход павольна 848 00:35:35,390 --> 00:35:38,680 са свету C і ніжэй Дэталі рэалізацыі ўзроўню, 849 00:35:38,680 --> 00:35:42,090 ў свеце, у якім мы можам узяць для разумеюцца, што хто-то нарэшце- 850 00:35:42,090 --> 00:35:44,010 рэалізаваны гэтыя дадзеныя збудаванні для нас, 851 00:35:44,010 --> 00:35:47,570 і мы пачнем разумець, Рэальны свет азначае рэалізацыі 852 00:35:47,570 --> 00:35:50,560 праграмы вэб-аснове і сайты ў больш агульным 853 00:35:50,560 --> 00:35:52,910 а таксама вельмі бяспекі Наступствы, якія мы толькі 854 00:35:52,910 --> 00:35:54,850 пачалі драпаць паверхню. 855 00:35:54,850 --> 00:35:57,320 Вось што нас чакае у бліжэйшыя дні. 856 00:35:57,320 --> 00:36:00,480 >> [ВИДЕОВОСПРОИЗВЕДЕНИЕ] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Ён Прыйшоў з паведамленнем, з пратаколам усё сваё. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Ён прыйшоў у свет жорсткі брандмаўэр, незаботливым маршрутызатары, 861 00:36:30,894 --> 00:36:33,368 і небяспекі значна горш, чым смерць. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Ён хутка. 864 00:36:36,236 --> 00:36:37,980 Ён моцны. 865 00:36:37,980 --> 00:36:42,830 Ён TCP / IP, і ў яго ёсць свой адрас. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 «Воіны Сеткі". 868 00:36:48,074 --> 00:36:49,660 [END ВИДЕОВОСПРОИЗВЕДЕНИЕ] 869 00:36:49,660 --> 00:36:50,910 DAVID Малання: Coming наступным тыдні. 870 00:36:50,910 --> 00:36:51,880 Мы будзем бачыць вас тады. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [ВИДЕОВОСПРОИЗВЕДЕНИЕ] 873 00:36:56,060 --> 00:36:59,240 -А Зараз, "Глыбокія думкі" па Daven Фарнэме. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 Дэвід заўсёды пачынаецца лекцыі з "Добра". 876 00:37:05,820 --> 00:37:08,750 Чаму не "Вось рашэнне на гэтым тыдні праблемы набору " 877 00:37:08,750 --> 00:37:12,180 або "Мы даем ўсе вы?" 878 00:37:12,180 --> 00:37:13,380 [Смяецца] 879 00:37:13,380 --> 00:37:15,530 [END ВИДЕОВОСПРОИЗВЕДЕНИЕ]