DAVID Маланки: Добре. Ми повернулись. Так що в цьому сегменті з програмування, що Я думав, що ми робимо це поєднання речей. По-перше, зробити трохи про щось руки-на, хоча і з використанням більш грайливий програмування environment-- той, який є показовим з саме ті види ідей ми говоримо про те, але трохи більш формально. По-друге, подивіться на деякі з тим більше технічні способи що програміст буде насправді вирішити Проблеми, як в пошуках проблеми що ми розглянули до і також більш фундаментально цікава проблема сортування. 

Ми тільки припустив, що з самого початку йти що ця телефонна книга сортували, але це само по собі насправді добрий з складна проблема з багатьма різними способами щоб вирішити цю проблему. Таким чином, ми будемо використовувати їх як клас задач представник речей, може бути вирішена в цілому. І тоді ми будемо говорити про в деяких деталях, що називаються дані structures-- химерні способи, як пов'язані списки і хеш-таблиці і дерева, програміст буде насправді використовувати і як правило, використовують на дошці малювати картина того, що він або вона передбачає для реалізації деякі частини програмного забезпечення. 

Так що давайте робити практичний частини першої. Так що просто отримати ваші руки брудні з навколишнє середовище називається scratch.mit.edu. Це інструмент, який ми використовуємо в нашому університетському класі. Незважаючи на те, що він призначений для осіб до 12 років і старше, ми використовуємо його для вгору частина цього зовсім небагато так як це приємно, весело Графічний спосіб навчання дещо про програмуванні. Так голова до цього URL, де ви повинні побачити сторінку зовсім так, і йти вперед і натисніть Приєднуйтесь до подряпин в верхньому правому куті і виберіть ім'я користувача та пароль і в кінцевому підсумку отримати собі account-- scratch.mit.edu. Я думав, що використовувати це як можливість вперше показати це. Питання підійшов під час перерви про те, що код насправді виглядає. І ми говорили під час перерви о С, зокрема particular-- нижчий рівень в більш старому мові. І я просто зробив швидкий Google пошук, щоб знайти код C для двійкового пошуку, алгоритм, який ми використовується для пошуку цієї телефонної книги раніше. Цей конкретний приклад, звичайно ж, не шукає телефонну книгу. Він просто шукає цілу купу Числа в пам'яті комп'ютера. Але якщо ви хочете, щоб просто отримати візуальне відчуття того, що фактичне програмування мова виглядає, це виглядає трохи щось на зразок цього. Так що мова йде про 20-плюс, 30 або близько того рядків коду, але розмова ми мали більш перерви був про те, як це насправді отримує трансформувалося в нулів і одиниць і якщо ви не можете просто повернутися, що обробляти і йдуть від нулів і одиниць назад в код. 

На жаль, процес настільки преосвітній що це набагато легше сказати, ніж зробити. Я пішов вперед і насправді виявилося що програма, бінарний пошук, в нулі і одиниці у формі приєднання Програма під назвою компілятор, що я трапляється, є тут прямо на моєму Mac. І якщо ви подивитеся на екран тут, звернувши особливу увагу на цих середніх шести колон тільки, ви побачите тільки нулі і одиниці. І ті нулі і одиниці, які скласти саме цю програму пошуку. 

І так кожен шматок п'ять бітів, кожен байт нулів і одиниць тут, становлять певну інструкцію як правило, всередині комп'ютера. І справді, якщо ви чули рекламний слоган "Intel всередині" - це, звичайно, просто означає, що у вас є Intel CPU або мозок всередині комп'ютера. І що це значить бути процесор що у вас є набір інструкцій, так би мовити. 

Кожен процесор в світі, багато з вони зроблені Intel в ці дні, розуміє кінцеве кількість інструкцій. І ці інструкції настільки низький рівень , Як додати ці два числа разом, перемножити ці два числа разом, перемістити цю частину даних тут щоб тут, в пам'яті, зберегти цей інформація звідси тут, в пам'яті, і так forth-- дуже, дуже низького рівня, майже електронні деталі. Але з тими, математична операції в поєднанні з тим, що ми обговорювали раніше, представлення даних як нулі і одиниці, можуть Ви сформуєте все що комп'ютер може зробити сьогодні, будь то це текстове, графічне, музичне, або іншим чином. 

Так що це дуже легко отримати втратили в бур'янів швидко. І є багато синтаксичні проблеми причому, якщо ви зробите найпростіший, дурне помилок ніхто з програми буде працювати взагалі. І тому замість того, щоб використовувати мова, як C цього ранку, Я думав, що це було б більше задоволення насправді робити щось більше, візуальне сприйняття, в той час як призначені для дітей насправді є досконалим проявом фактичного програмування language-- якраз трапляється використовувати зображення замість тексту щоб представити ці ідеї. 

Тому, як тільки ви насправді мати рахунок на scratch.mit.edu, натисніть кнопку Створити в лівому верхньому куті сайту. І ви повинні побачити навколишнє середовище як один я збираюся бачити на моєму екрані тут. І ми витратимо трохи небагато часу, граючи тут. Давайте подивимося, якщо ми не можемо все вирішити деякі проблеми разом наступним чином. 

Так що ви побачите в цьому environment-- і насправді просто дайте мені паузу. Хто-небудь не тут? Не тут? ДОБРЕ. Отже, дозвольте мені відзначити кілька Характеристики цього середовища. 

Таким чином, у верхньому лівому куті екрану, ми є стадія чистого аркуша, так би мовити. Подряпини не тільки ім'я цієї мови програмування; це також ім'я кота, ви бачите, за замовчуванням там в помаранчевий колір. Він знаходиться на сцені, так так само, як я описав черепаха раніше як в прямокутна біла дошка довкілля. Світ цієї кішки обмежується виключно на цей прямокутник нагорі там. 

У той же час, справа права частина тут, це тільки область скрипти, чистого аркуша, якщо ви будете. Саме тут ми будемо писати наші програми в мить. І будівельні блоки, які ми використовувати, щоб написати це program-- головоломки штук, якщо ви will-- є ті, прямо тут, в центрі, і вони класифікуються по функціональності. Так, наприклад, я збираюся йти вперед і продемонструвати, по крайней мере, один з них. Я збираюся йти вперед і натисніть категорія управління нагорі. 

Так що ці категорії до вершини. Я збираюся натиснути категорію управління. Швидше за все, я буду натискати на події категорія, найперший нагорі. І якщо ви хочете слідувати навіть як ми робимо це, ви дуже ласкаво просимо. Я збираюся натиснути і перетягнути цей Перший з них, "коли зелений прапор клацнув". А потім я збираюся кинути його просто приблизно у верхній частині моїх порожніх сланці. 

І що приємно про порожньому місці є те, що цей шматок головоломки, коли взаємопов'язаний з іншого головоломки штук, збирається зробити буквально що ці шматочки головоломки кажуть робити. Так, наприклад, Подряпини прав Зараз в середині свого світу. Я збираюся йти вперед і вибрати Тепер, скажімо, категорія руху, якщо ви хочете зробити same-- категорії руху. А тепер зверніть увагу у мене є цілий купа головоломки тут що, знову ж таки, робити вигляд, що вони говорять. І я збираюся йти вперед і перетягнути впустити блок рухатися прямо тут. 

І зверніть увагу, що, як тільки ви отримаєте близько до нижньої частини "зелений прапор натиснув "кнопку, повідомлення як з'являється біла лінія, як ніби це майже магнітні, він хоче поїхати туди. Просто відпустити, і він буде вистачати разом і форми будуть збігатися. І тепер ви можете, можливо, майже вгадати, де ми збираємося з цим. 

Якщо ви подивіться на сцену Скретч тут і дивитися у верхній частині його, ви побачите червоне світло, знак зупинки, і зелений прапор. І я збираюся йти вперед і дивитися мої screen-- на мить, якби ви могли. Я збираюся натиснути зелений прапор прямо зараз, і він переїхав, що, як видається, 10 кроків або 10 пікселів, 10 точок, на екрані. 

І так не так цікаво, але дозвольте мені запропонувати навіть не вчив цьому, просто використовуючи свій власний intuition-- нехай я пропоную вам з'ясувати, як зробити Подряпини прогулянку прямо зі сцени. Чи були йому зробити шлях для правого боку екран, весь шлях направо. Дозвольте мені дати вам момент або так, щоб боротися з цим. Ви можете захотіти поглянути на інші категорії блоків. Добре. Так що просто резюмувати, коли ми маємо зелений прапор натиснувши тут і рухатися 10 кроків є тільки інструкція, кожен раз, коли я натисніть зелений прапор, що відбувається? Ну, це працює моя програма. Так що я міг би зробити це може бути в 10 разів вручну, але це відчуває себе трохи трохи хаком, так би мовити, в результаті чого я насправді не вирішення проблеми. Я просто намагаюся знову і знову і знову і знову поки я начебто випадково досягти директиви що я мав намір досягти раніше. 

Але ми знаємо з нашого псевдокод раніше, що є це поняття в програмуванні зациклення, робити щось знову і знову. І ось я побачив, що зв'язка з вас потягнувся за те, що шматок головоломки? Повторюйте до тих пір. Таким чином, ми могли б зробити щось як повторювати до. І не те, що ви повторити, поки точно? 

ДОБРЕ. І дозвольте мені піти з той, який кілька найпростіше на мить. Дозвольте мені йти вперед і робити це. Зверніть увагу на те, що, як ви, можливо, виявив під контролем, Тобто цей повтор блок, який не виглядає, як ніби це що великий. Там не так багато місця в між цими двома жовтими лініями. Але так як деякі з вас, можливо, помітили, якщо ви перетягнути, зверніть увагу, як він росте, щоб заповнити форму. 

І ви можете навіть втиснути більше. Це буде просто продовжувати рости, якщо перетягуванні і парити над ним. І я не знаю, що це найкраще тут, так що давайте мені принаймні повторити п'ять разів, для екземпляр, а потім повернутися на сцену і натисніть на зелений прапор. А тепер зверніть увагу, що це не зовсім там. 

Зараз деякі з вас запропонували в якості Вікторія просто, повторіть 10 разів. І що взагалі робить отримати його весь шлях, Але хіба не було б більш надійним спосіб, ніж довільно з'ясувати, скільки ходів зробити? Що може бути краще блок ніж повторити 10 разів бути? 

Так, так чому б не зробити щось назавжди? А тепер дозвольте мені перенести цей шматок головоломки всередині там, і позбутися від цього. Тепер зверніть увагу незалежно від того, де Царапина починається, він йде до краю. І на щастя MIT, який робить нуля, просто не гарантує, що він ніколи повністю зникає. Ви завжди можете схопити його за хвіст. 

І точно так само інтуїтивно, Чому він продовжує рухатися? Що ж тут відбувається? Він, здається, зупинилося, але а потім, якщо я піднімаю і перетягнути він продовжує хотіти йти туди. Чому так? Дійсно, комп'ютер буквально збирається робити те, що ви скажете їй зробити. Так що, якщо ви сказали це раніше зробити наступна річ назавжди, рухатися 10 кроків, це буде продовжувати йти і йти поки я не вдарив червоний знак стоп і зупинити програму в цілому. 

Так що навіть якщо ви цього не зробили зробити це, як я міг зробити Подряпини рухатися швидше по екрану? Інші кроки, чи не так? Таким чином, замість того, щоб робити 10 в той час, чому б нам не йти вперед і змінити його, метою яких що б ви propose-- 50? Так що тепер я збираюся натиснути зелений прапор, і насправді, він йде дуже швидко. 

І це, звичайно ж, це просто прояв анімації. Що таке анімація? Це просто показує вам людини A ціла купа нерухомих зображень насправді, насправді, дуже швидко. І тому, якщо ми просто розповідаю йому рухатися більше кроків, ми просто маючи ефект бути зміна, де він знаходиться на екрані все більш швидко за одиницю часу. 

Тепер наступний виклик, який я запропонував повинен був мати його відскакують від краю. І не знаючи, що головоломки штук exist--, тому що це нормально якщо ви не дістатися до етап challenge--, що ви хочете зробити інтуїтивно? Як би ми його відскочити назад і вперед, між лівим і правим? 

Так. Так що нам потрібно якийсь стану, і ми як видається, мають умовними, так кажуть, під категорію управління. Який з цих блоків ми, ймовірно, хочете? Так, можливо, "якщо, то". Так помітити, що серед жовтих блоків ми маємо тут, є це "якщо" або це ", якщо ще" блок, який буде дозволяють нам прийняти рішення, щоб зробити це або зробити це. І ви навіть можете їх гніздо зробити кілька речей. Або, якщо ви не пройшли ще тут, йти вперед до категорії Sensing і-- давайте подивимося, якщо він тут. 

Так що блок може бути корисним тут щоб виявити, якщо він зі сцени? Так, зверніть увагу, що деякі з цих блоків можуть бути параметризовані, якщо можна так висловитися. Вони можуть бути налаштовані роду, а не На відміну від HTML вчора з атрибутами, де ці атрибути роду налаштувати поведінку тега. Точно так же тут, я можу захопити цей зворушливий блок і змінити і задати питання, ви торкаючись мишею покажчик, як курсор або ви доторкнувшись до краю? 

Отже, дозвольте мені піти і зробити це. Я збираюся зменшити на мить. Дозвольте мені захопити цей шматок головоломки тут, це шматок головоломки це, і я збираюся перемішувати вони на мить. Я буду рухатися в цьому, змінити це зворушливою край, і я збираюся зробити це рух. Так ось деякі інгредієнти. Я думаю, що у мене є все, що захочу. 

хтось хотів би запропонувати, як я може з'єднати їх, може бути, зверху вниз для того, щоб вирішити проблему наявності Подряпина рух справа наліво направо зліва направо, наліво, кожен Час як раз відбиваючись від стіни? Що я хочу зробити? Який блок я повинен підключитися до "Коли зелений прапор клацнув перший"? 

ОК, так що давайте почнемо з «назавжди». Те, що відбувається всередині далі? Хтось інший. OK, рухатися кроки. Добре. Тоді що? Так то якщо. І зверніть увагу, навіть якщо це виглядає затиснутою разом щільно, він просто буде рости, щоб заповнити. Це буде просто стрибати в тому, де я хочу. 

І що ж я ставлю між ІФ та тоді? Можливо ", якщо ви торкаєтеся край». І зауважте, знову ж таки, це занадто великий для неї, але вона буде рости, щоб заповнити. А потім повернути на 15 градусів? Скільки градусів? Так, так що 180 буде обертатися мене все навпаки. Отже, давайте подивимося, якщо я отримав це право. Дозвольте мені зменшити зображення. 

Дозвольте мені перетягнути нашкребти. Таким чином, він трохи спотворюється Зараз, але це нормально. Як я можу скинути його легко? Я збираюся трохи обдурити. Таким чином, я додав ще один блок, просто щоб бути ясним. Я хочу, щоб він вказує на 90 градусів вправо за замовчуванням, так що я просто хочу, щоб сказати йому, зробити це програмно. А ось і ми. Ми, здається, зробили це. Це трохи дивно, тому що він йде з ніг на голову. Давайте назвемо, що помилка. Це помилка. Виправлена ​​помилка, помилка в програмі, а логічна помилка, що я, людина, зробив. Чому він збирається з ніг на голову? Виявилася MIT загвинтити або я? 

Так, я маю на увазі, це не в MIT несправність. Вони дали мені шматок головоломки що говорить повернути деяку кількість градусів. І за пропозицією Вікторії, Я перетворююся на 180 градусів, який є правильним інтуїція. Але поворот на 180 градусів в буквальному сенсі означає поворот на 180 градусів, і це насправді не що я хочу, мабуть. Тому що, по крайней мере, він в це двовимірна світ, так що поворот дійсно відбувається щоб перевернути його з ніг на голову. 

Я, ймовірно, хочете, щоб використовувати те, що блок замість того, щоб, грунтуючись на те, що ви бачите тут? Як ми можемо це виправити? Так, таким чином, ми могли б вказати в протилежному напрямку. І насправді навіть це не буде достатньо, тому що ми можемо тільки жорсткий код щоб вказувати вліво або вправо. 

Ви знаєте, що ми можемо зробити? Схоже, що у нас є зручний блок тут. Якщо я наближати см то, що ми, як тут? Так це виглядає, як MIT має абстракція побудована тут. Цей блок представляється еквівалентним до яких інші блоки, множина? 

Цей блок представляється еквівалентним до всієї цієї трійці блоків що ми маємо тут. Так виходить, що я можу спростити свою Програма, позбувшись від усього цього і просто поставити це тут. А тепер він ще трохи глючить, і це нормально зараз. Ми залишимо це буде. Але моя програма навіть простіше, і це теж, буде представник голи в programming-- це в ідеалі зробити свій код, просто, як можна більш компактним, в той же час, як читаним, наскільки це можливо. Ви не хочете, щоб зробити це так лаконічний що це важко зрозуміти. 

Але зверніть увагу, я замінив три блоки з одним, і це, можливо, хороша річ. Я абстрагуються поняття знали що Ви на краю за допомогою тільки одного блоку. Тепер ми можемо отримувати задоволення з цим, насправді. Це не додає стільки інтелектуальні цінності, але грайлива значення. Я збираюся йти вперед і захопити цей звук тут. Отже, дозвольте мені йти вперед, і нехай мене зупинити програму на мить. Я збираюся записати наступне, забезпечуючи доступ до мого мікрофона. 

Ось і ми. Уч. Давайте спробуємо це знову. Ось і ми. ОК, я записав неправильні речі. Ось і ми. Уч. Уч. Добре. Тепер мені потрібно, щоб позбутися від цього. Добре. 

Так що тепер у мене є Запис тільки "Ой". Так що тепер я збираюся піти вперед і називаємо це "Уч." Я збираюся повернутися для моїх сценаріїв, і тепер повідомлення є цей блок, який називається грати звук "мяу" або відтворювати звук "Уч." Я збираюся тягнути це, і де я повинен поставити це на комічний ефект? Так, так що тепер це свого роду глючить, тому що тепер це block-- зверніть увагу, як це ", якщо на краю, відскоку "є свого роду самодостатнім. Тому мені потрібно, щоб виправити це. Дозвольте мені йти вперед і робити це. Дозвольте мені позбутися від цього і повернутися до нашого початкового, більш навмисним функціональність. Так що "якщо ви торкаєтеся край, а потім" Я хочу повернути, як це було запропоновано Вікторія, На 180 градусів. І я хочу, щоб грати звук "Уч" є? 

Так, зверніть увагу, що це за межами що жовтий блок. Так що це теж було б помилка, але я помітив це. Так що я збираюся тягнути його сюди, і зауважте, тепер це всередині «якщо». Так що "якщо" це свого роду однойменних руки, як блоттинга що тільки збирається робити те, що всередині нього. Так що тепер, якщо я віддалити в ризик annoying-- 

КОМП'ЮТЕР: Ой, ой, ой. 

DAVID Маланки: І буде просто тривати вічно. Тепер просто прискорити речі тут, дозвольте мені йти вперед і відкрити, давайте say-- відпустити мене в якийсь мого власного матеріалу від класу. І дозвольте мені відкрити, скажімо, це один зроблений одним з наших навчальних товаришів пару років назад. Так що деякі з вас можуть згадати ця гра від минулих років, і це насправді чудово. Незважаючи на те, що ми зробили Найпростішим програм прямо зараз, давайте розглянемо, що це насправді виглядає. Дозвольте мені вдарив грати. 

Так що в цій грі, у нас є жаби, і за допомогою стрілки keys-- він приймає великі кроки, ніж я remember-- У мене є контроль над цією жаби. І мета полягає в тому, щоб отримати через зайнятий Дорога без запуску в автомобілях. І давайте see--, якщо я йду тут, я доведеться чекати, поки журнал для прокрутки по. Це відчуває, як помилка. Це свого роду помилка. Добре. Я на це тут, там, а потім ви тримаєте йти, поки не отримаєте всі жаби в латаття. Тепер це може виглядати все більш складними, але давайте спробуємо розбити це вниз подумки і усно на складові блоки. Так що, ймовірно, головоломка частина, яку ми ще не бачили але це реагує на натискання клавіш, до речей, я вдарив по клавіатурі. 

Так що там, напевно, якась блок, який говорить, якщо ключ дорівнює вгору, потім зробити щось з Scratch-- можливо перемістити його 10 кроків таким чином. Якщо вниз клавіша натиснута, рухатися 10 кроків таким чином, або ліва клавіша, рухатися 10 кроків Таким чином, 10 кроків, які. Я чітко повернув кішку в жабу. Так ось саме там, де костюм, як чернетка дзвінки it-- ми тільки що імпортували картину жаби. 

Але що ще відбувається? Які інші рядки коду, що інші головоломки зробив Блейк, наше вчення співробітник, використовувати в цій програмі, очевидно? Що робить все move-- то, що програмування побудувати? 

Motion, sure-- так перемістити блок, напевно. І те, що цей крок блок всередині, швидше за все? Так, якийсь цикл, може бути, назавжди заблокувати, можливе повторення block-- повторювати до блоку. І ось що робить журнали і латаття і все інше рух взад і вперед. Це просто відбувається нескінченно. 

Чому деякі з автомобілів рухатися швидше, ніж інші? Що відрізняє цих програм? Так, ймовірно, деякі з них приймають більше кроків відразу і деякі з них менше кроків відразу. І візуальний ефект дуже швидко в порівнянні з повільним. 

Як ви думаєте, що трапилося? Коли я отримав мою жабу весь шлях через дорогу і річку на лілії майданчик, щось Примітно, відбулося. Те, що сталося, як тільки я зробив це? Вона зупинилася. Ця жаба зупинилася, і Я отримав другу жабу. Так що конструкція повинна бути використовується там, яка функція? 

Так, так що є якась "Якщо" стан там, теж. І виходить out-- ми не побачили this-- але є й інші блоки там Можна сказати, якщо ви торкаєтеся Інша справа, на екрані, якщо ви торкаючись до латаття ", а потім". І тоді, коли ми зробити другий жаби з'являються. Так що, хоча ця гра, безумовно, дуже застаріли, хоча на перший погляд є так багато відбувається on-- і Блейк НЕ шмагати це в дві хвилини, він, ймовірно, взяв його кілька годин, щоб створити цю гру заснований на його пам'яті або відео версії вчорашнього дня про нього. Але всі ці дрібниці відбувається на екрані в ізоляції зводяться до них дуже просто constructs-- руху або заяви як ми вже обговорювали, петлі та умови, і саме про це. Там в кілька інших особливостей любитель. Деякі з них є чисто естетичні або акустичні, як звуки я просто грав. Але здебільшого, ви є в цій мові, на порожньому місці, всі фундаментальні будівельні блоки, які вам є в C, Java, JavaScript, PHP, Ruby, Python, і будь-яку кількість інших мов. Будь-які питання на порожньому місці? Добре. Тому ми не будемо занурюватися глибше подряпати, хоча ви завжди можете в ці вихідні, особливо якщо у вас є діти або племінниці і племінники і такі, познайомити їх з нуля. Це насправді дивно грайливий середа з, як кажуть його автори, дуже високі стелі. Незважаючи на те, що ми почали з дуже низькорівневих деталей, ви дійсно можете зробити зовсім небагато з ним, і це, мабуть, демонстрація саме це. 

Але давайте тепер перейти до деяких більш складні проблеми, якщо ви будете, відомий як "пошук" і "Сортування" в більш загальному плані. У нас була ця телефонна книга earlier-- тут ще один раз для discussion-- що ми змогли знайти більш ефективно, тому що значного припущення. І просто бути зрозуміло, що Передбачалося, що робить я при пошуку через цю телефонну книгу? Це Майк Сміт був в телефонна книга, хоча я матиме можливість обробляти сценарій без нього там, якщо я просто зупинився передчасно. Книга в алфавітному порядку. І це дуже щедрий припущення, тому що означає someone-- Я начебто різання кут, як я швидше, тому що хтось ще зробив багато важкої роботи для мене. 

Але що, якщо телефон Книга була несортоване? Може бути, Verizon став ледачим, просто кинув імена та номери кожного в там може бути, в тому порядку, в якому вони підписався на телефон служби. А скільки часу займає мене щоб знайти кого-то на кшталт Майка Сміта? 1000 сторінок телефон book-- скільки сторінки я повинен переглянути? 

Усі. Ти ніби не пощастило. Ви буквально повинні дивитися на кожен сторінка, якщо телефонна книга просто випадковим чином упорядковано. Ви можете отримати пощастило і знайти Mike на самій першій сторінці, тому що він був першим замовником замовити послугу по телефону. Але він, можливо, був останнім, теж. 

Так у випадковому порядку не добре. Тому припустимо, що ми повинні сортувати Телефонна книга або в загальних даних сортування що ми дали. Як ми можемо зробити це? 

Що ж, дозвольте мені спробувати простий приклад тут. Дозвольте мені йти вперед і кинути Кілька номерів на дошці. Нехай числа у нас є є, скажімо, чотири, два, один і три. І, Бен, сортувати ці цифри для нас. 

ОК добре. Як ти це зробив? Добре. Так що почніть з найменшим значення і високий, і це дійсно хороша інтуїція. І розуміємо, що ми люди насправді досить добре на рішення проблем як це, по крайней мере, коли дані відносно мала. Як тільки ви починаєте мати сотні чисел, тисячі чисел, мільйони чисел, Бен, ймовірно, не міг зробити це досить швидко, що, якщо припустити, що існують прогалини в цифрах. Досить легко підрахувати до мільйона в іншому випадку просто забирає багато часу. 

Таким чином, алгоритм це звучить як Бен використовується тільки зараз був пошук найменшого числа. Так що, хоча ми, люди можуть прийняти у великій кількості інформації візуально, комп'ютер насправді трохи більш обмеженим. Комп'ютер може тільки дивитися на один байт в той час, або, може бути чотири байти за time-- в ці дні, може бути 8 байт за time-- але дуже невелике число байтів в даний момент часу. 

Тому, з огляду на, що ми дійсно маємо чотири окремі значення here-- і ви можете думати про Бен як має шори, якби він був комп'ютер типу що він не може бачити нічого іншого ніж один номер в каталозі time-- тому ми зазвичай будемо вважати, як і в Англійська, ми будемо читати справа наліво. Таким чином, перший номер Бен, ймовірно, виглядав на було чотири роки, а потім дуже швидко зрозумів, що це досить великий number-- дозвольте мені продовжувати пошуки. 

Там два. Почекай хвилинку. Два менше чотирьох. Я буду пам'ятати. Два в даний час є найменшим. Тепер одно-- це ще краще. Це навіть менше. Я збираюся забути про двох і просто згадати його зараз. 

І він міг перестати дивитися? Ну, він міг на основі на цій інформації, але він краще б пошук інша частина списку. Тому що, якщо нуль були в списку? Що робити, якщо негативний були в списку? Він знає тільки, що його відповідь є правильним, якщо він вичерпно перевірив весь список. Таким чином, ми дивимося на решті частини цього. Three--, що це марна трата часу. Не пощастило, але я був до сих пір правильно зробити це. І ось тепер він, ймовірно, вибирається найменше число і просто покласти його на початку зі списку, як я буду тут робити. Тепер те, що ви робили далі, незважаючи на те, Ви не думали про це майже до такої міри? Повторіть цей процес, тому якийсь цикл. Там знайома ідея. Так ось чотири. Це в даний час найменший. Це кандидат. Чи не більше. Тепер я бачив два. Це наступний найменший елемент. Three--, що не менш, так Тепер Бен може виривати два. 

І тепер ми повторюємо процес, а звичайно три отримує витяг наступний. Повторіть процес. Чотири отримує витяг. А тепер ми з чисел, так що список повинен бути відсортований. 

І справді, це формальний алгоритм. Комп'ютер вчений буде називаємо це "вибір роду" ідея в тому, сортувати по список iteratively-- знову і знову і знову вибір найменше число. І що приємно про нього це просто так чертовски інтуїтивним. Це так просто. І ви можете повторити те ж саме операція знову і знову. Це просто. 

У цьому випадку це було швидко, але як довго це насправді взяти? Давайте зробимо це, здається, і відчувати себе трохи більш виснажливим. Так що один, два, три, чотири, п'ять, шість ,, сім, вісім, дев'ять, 10, 11, 12, 13, 14, 15, 16-- довільне число. Я просто хотів більше цього Час, ніж просто чотири. Так що, якщо у мене є ціле зв'язка чисел now-- його навіть не має значення що вони are-- давайте думати про те, що це Алгоритм дуже схожий. 

Припустимо, що існують числа там. Знову ж, не має значення, що вони є, але вони випадковим чином. Я застосовую алгоритм Бен. Мені потрібно, щоб вибрати найменше число. Що мені робити? І я збираюся фізично зробити це на цей раз, щоб діяти його. Дивлячись, дивлячись, дивлячись, дивлячись, дивлячись. Тільки на той час я отримую кінець списку може Я розумію, що найменший число було два на цей раз. Один не в списку. Так що я поклав два. 

Що робити далі? Дивлячись, дивлячись, дивлячись, дивлячись. Тепер я знайшов номер сім, тому що є прогалини в цих numbers-- а просто довільно. Добре. Так що тепер я можу покласти вниз сім. Дивлячись дивлячись, дивлячись. 

Тепер я припускаю, з Звичайно ж, що Бен НЕ мають додаткову оперативну пам'ять, додаткові пам'ять, тому що, звичайно ж, Я дивлюся на той же номер. Звичайно, я міг би пам'ятати, всі ці цифри, і це абсолютно вірно. Але якщо Бен пам'ятає все з номера, які він бачив, він насправді не зробив фундаментальний прогрес тому що у нього вже є можливість пошуку за номерами на дошці. Згадуючи все з номера не допомагає, тому що він все ще може як комп'ютер тільки дивитися, ми вже говорили, один номер зараз. Так що немає ніякого роду читів там, що ви можете використовувати. 

Так що насправді, як я продовжувати пошук в списку, Я буквально повинен просто продовжувати йти взад і вперед через неї, вищипування Наступного найменше число. І, як ви можете частково зробити висновок від моїх дурних рухів, це просто стає дуже утомливо дуже швидко, і я, здається, йде назад і вперед, взад і вперед, зовсім небагато. Тепер, щоб бути справедливим, я не повинен йти зовсім як, ну, давайте see-- бути справедливим, Я не доведеться ходити досить стільки кроків, кожен раз. Тому що, звичайно ж, як я вибрати зі списку, залишився список стає все коротшим. 

Так що давайте думати про скільки кроків я насправді тащась через кожен раз. У першій ситуації у нас було 16 номерів, і так maximally-- давайте просто зробити це для discussion-- Я повинен був дивитися через 16 років номера, щоб знайти найменший. Але як тільки я вибрали найменше число, як довгий час був залишився список, звичайно? Тільки 15. Так скільки чисел зробив Бен або у мене є погортати вдруге навколо? 15, просто піти і знайти найменший. Але тепер, звичайно, список, теж менше, ніж це було раніше. Так скільки кроків зробив я повинні взяти на себе в наступний раз? 14, а потім 13, а потім 12, плюс точка, точка, точка, поки я не залишиться тільки один. Так що тепер комп'ютерний вчений буде запитаєте, ну, що ж, що всі рівні? Це насправді так само деякі конкретні число, яке ми могли б, звичайно, робити арифметично, але ми хочемо поговорити про ефективність алгоритмів трохи більше formulaically, не залежить від того, як довго цей список. 

І ви знаєте, що? Це 16, але як я вже сказав раніше, давайте просто назвати розмір проблеми п, де п деяке число. Може бути, це 16, може бути, це три, може бути, це мільйон. Не знаю. Я не дбаю. Те, що я дійсно хочу, формула, я можу використовувати для порівняння цей алгоритм проти інших алгоритмів що хтось може претендувати краще або гірше. 

Так що виходить, і я тільки знаю, що це з початкової школи, що це насправді працює, до того ж річ, як п по п плюс один більше двох. І це відбувається в рівних умовах, Звичайно ж, п квадрат плюс п над ними. Так що, якщо я хотів формулу На скільки кроків були залучені в дивлячись на всі про знову і знову ці цифри і знову і знову, я б сказав, це п квадрат плюс п над ними. Але ви знаєте, що? Це просто виглядає неакуратно. Я просто дуже хочу Загальний сенс речей. І ви можете згадати з середньої школи, що там є поняття терміна вищого порядку. Який з цих термінів, п квадрат, російська, або половину, має найбільший вплив з плином часу? Чим більше п отримує, що з цих питань найбільше? 

Іншими словами, якщо я підключу на мільйон, п квадрат буде, швидше за все, домінуючим фактором, тому що в мільйон разів сама по собі набагато більше ніж плюс один додатковий мільйон. Таким чином, ви знаєте, що? Це така велика штопання номер, якщо ви квадратури номер. Це не має ніякого значення. Ми просто хрест, , І забути про це. І тому вчений сказав би що ефективність цього алгоритму складає близько п squared-- Я маю на увазі дійсно наближення. Це свого роду грубо п в квадраті. З плином часу, тим більше і більше п отримує, це є гарною оцінкою для того, що ефективність або відсутність ефективності цього алгоритму насправді. І я отримати, що, звичайно ж, від фактично робить математику. Але тепер я просто махав мої руки, тому що я просто хочете загальний зміст цього алгоритму. 

Таким чином, використовуючи ту ж логіку, тим часом, давайте розглянемо інший алгоритм ми вже розглянули at-- лінійний пошук. Коли я шукав для телефону book-- НЕ сортувати її, пошук через телефонну book-- ми продовжували говорити, що це було 1000 кроків або 500 кроків. Але давайте узагальнимо це. Якщо є п сторінок телефонна книга, що біжучий час або ефективність лінійного пошуку? Це на порядок скільки кроків, щоб знайти Майк Сміт, використовуючи лінійний пошук, то Перший алгоритм, або навіть другий? 

У гіршому випадку, Майк знаходиться в кінці книги. Так що, якщо телефонна книга має 1000 сторінок, ми говорили минулого разу, в найгіршому випадку, це може зайняти приблизно як багато сторінок, щоб знайти Майк? Як і 1000. Це верхня межа. Це найгірший з можливих ситуацій. Але знову ж таки, ми віддаляючись з числа, як 1000 зараз. Це просто п. 

Так що ж логічний висновок? Знаходження Майк в телефоні Книга, яка має п сторінок може знадобитися, в найгіршому випадку, скільки кроків по порядку п? І справді комп'ютер вчений сказав би що час роботи, або продуктивність або ефективність або неефективність алгоритму як лінійний пошук по порядку п. І ми можемо застосувати той же логіка перетину щось як я тільки що зробив на другий Алгоритм ми мали з телефонною книгою, куди ми пішли дві сторінки одночасно. 

Так щоб 1000 сторінка Телефонна книга може взяти нас 500 сторінок поворотів, плюс один якщо ми загнути небагато. Так що, якщо телефонна книга має п сторінок, але ми робимо дві сторінки в той час, це приблизно те, що? N більш ніж два, так що як п над ними. Але я зробив вимагати хвилину тому, що п над two-- це свого роду такий же, як тільки п. Це просто постійний множник, комп'ютерні вчені сказали б. Давайте акцентувати увагу тільки на змінні, really-- найбільші змінні в рівнянні. 

Таким чином, лінійний пошук, то чи зробив один сторінки в той час, або дві сторінки в той час, є свого роду принципово те ж саме. Це як і раніше порядку п. Але я стверджував з моїм зображенням раніше що третій алгоритм ні лінійний. Це була не пряма лінія. Це було те, що вигнуті лінії, і алгебраїчна формула була що? Журнал так увійти N-, підстава два п. І ми не повинні вдаватися в багато деталей на логарифмів сьогодні, але більшість комп'ютерних учених не буде навіть сказати вам, що база. Тому що це все просто постійними факторами, так би мовити, тільки незначні числові відмінності. І ось це було б дуже поширеним явищем спосіб особливо формального комп'ютера науковці на дошці або програмісти білої дошки насправді стверджуючи, який Алгоритм вони будуть використовувати або те, що коефіцієнт корисної дії з їх алгоритм. 

І це не обов'язково щось ви будете обговорювати в будь-якому деталях, але хороший програміст хтось який має солідний, формальний фон. Він в змозі говорити Ви в цьому виді шляху і насправді зробити якісні аргументи, чому один алгоритм або одна частина програмного забезпечення перевершує в якійсь мірі до іншого. Тому що ви могли б, звичайно, просто запустити програму одну людину і підрахувати кількість секунд потрібно, щоб сортувати деякі цифри, і ви можете запустити деякі програма іншу людину і підрахувати кількість секунд потрібно. Але це більш загальний спосіб, який ви можете використовувати для аналізу алгоритмів, якщо ви будете, як раз на папір або просто в усній формі. Навіть не запустити його без навіть пробувати входи вибірки, ви можете просто міркувати через нього. І так з наймом розробник або якщо маючи його або її роду стверджують, вам чому їх алгоритм, їх секрет соус для пошуку мільярди веб-сторінок для компанія краще, ці є види аргументів, які вони в ідеалі повинні бути в змозі зробити. Або, принаймні, це види речей що б прийти в дискусії на хоча б в дуже формальної дискусії. Добре. Так що Бен запропонував щось називається вибір роду. Але я збираюся запропонувати, що є інші способи зробити це, теж. Те, що я не дуже подобається про алгоритм Бен в тому, що він продовжував йти, або то, як я йду, туди-сюди і взад і вперед і назад і вперед. Що робити, якщо замість того, щоб я мав зробити щось на зразок цих чисел тут і я повинен був просто мати справу з кожним номер, в свою чергу, як я дав йому? 

Іншими словами, тут мій список номерів. Чотири, один, три, два. І я збираюся зробити наступне. Я збираюся вставити цифри де вони належать швидше ніж вибираючи їх по одному за раз. Іншими словами, ось номер чотири. 

Ось мій початковий список. І я буду підтримувати по суті, новий список тут. Так що це старий список. Це новий список. Я бачу номер чотири в першу чергу. Мій новий список спочатку порожній, тому тривіальним випадок що чотири тепер сортували список. Я просто приймаючи число я дав, і я ставлю його в своєму новому списку. 

розсортовані цей новий список? Так. Це нерозумно, тому що є тільки один елемент, але це абсолютно відсортований. Там немає нічого, недоречні. Це цікавіше, цей алгоритм, коли я переходжу до наступного кроку. 

Тепер у мене є один. Так що, звичайно ж, належить на початок або кінець цього нового списку? Початок. Так що я повинен зробити деякі роботи в даний час. Я приймаю деякі вольності з моїм маркером на просто малюнок речей де я хочу їх, але це не зовсім точним в комп'ютері. Комп'ютер, як ми знаємо, має Оперативна пам'ять, або Random Access Memory, і це один байт і інший байт і ще один байт. І якщо у вас є гігабайти RAM, у вас є мільярд байтів, але вони фізично в одному місці. Ви не можете просто переміщати речі навколо намалювавши її на дошці де ви хочете. Так що, якщо мій новий список має чотири місця в пам'яті, на жаль, чотири є вже в неправильному місці. 

Таким чином, щоб вставити номер один Я не можу просто зробити це тут. Це місце пам'яті не існує. Це було б обман, і я був Зради зображально протягом декількох хвилин тут. Так насправді, якщо я хочу поставити один тут, Я повинен тимчасово скопіювати чотири а потім покласти один там. 

Це добре, це правильно, що це технічно можливо, але розумію, що це додаткова робота. Я не просто поставити номер на місці. Спочатку я повинен був рухатися номер, а потім покласти його на місці, так що я свого роду подвоїв свою обсяг роботи. Так що майте це на увазі. 

Але зараз я зробив з цим елементом. Тепер я хочу, щоб захопити номер три. Там, де, звичайно ж, воно належить? Між. Я не можу обдурити більше і просто поставити його там, тому що, знову ж таки, ця пам'ять в фізичних місцях. Так що я повинен скопіювати чотири і поставити три тут. Не велике діло. Це всього лише один додатковий крок again-- відчуває себе дуже недорого. 

Але тепер я переходжу до двох. Два, звичайно ж, належить тут. Тепер ви починаєте бачити, як робота може накопичуватися. Тепер те, що я повинен робити? Так, я повинен перемістити чотири, Потім я повинен скопіювати три, і тепер я можу вставити два. І улов з цим Алгоритм, досить цікаво, є те, що припустимо, у нас є більш екстремальний випадок, коли це, скажімо, вісім, сім, шість, п'ять, чотири, три, два, один. Це, у багатьох контекстах, в гіршому випадку, тому що штопати річ буквально в зворотному напрямку. 

Це дійсно не має впливає на алгоритм Бен, тому що в відборі Бен свого роду він збирається тримати ходить взад і вперед по списку. І тому, що він завжди шукав через весь список, неважливо де елементи. Але в цьому випадку з моєї вставки approach-- давайте спробуємо це. 

Так один, два, три, чотири, п'ять, шість, сім, вісім. Один два три чотири, п'ять, шість, сім, вісім. Я збираюся взяти вісім, і де я можу це сказати? Ну, на самому початку мого списку, тому що цей новий список відсортований. І я перетинаю його. 

Де я поставив сім? Палки. Він повинен йти туди, так Я повинен зробити деякі копіювання. А тепер сім йде тут. Тепер я переходжу до шести. Тепер стало ще більше роботи. 

Вісім повинен йти тут. Сім повинен йти сюди. Тепер шість може піти сюди. Тепер я захопити п'ять. Тепер вісім повинен йти тут, сім доводиться йти сюди, шість повинен йти тут, і Тепер п'ять і повторіть. І я досить багато переміщаючи його постійно. 

Таким чином, в кінці кінців, це algorithm-- ми будемо назвати його вставки sort-- насправді має багато роботи, теж. Це просто різні вид роботи, ніж Бен. Робота Бен змусив мене йти назад і вперед весь час, вибираючи наступний найменший елемент знову і знову. Так що це було дуже візуальний вигляд роботи. 

Цей інший алгоритм, який як і раніше correct-- він отримає роботу done-- просто змінює обсяг роботи. Схоже, що спочатку ви економії, тому що ви просто маємо справу з кожним елементом фронт без ходити все шлях через список, як Бен. Але проблема в тому, особливо в ці божевільні випадки, коли це все в зворотному напрямку, ви просто вид відкладаючи важку роботу поки ви не повинні виправити свої помилки. 

І так, якщо ви можете собі це вісім і сім і шість і п'ять а потім чотири і три і два переміщаючи їх шлях через список, ми тільки що змінили тип роботи, яку ми робимо. Замість того, щоб робити це на початок моєї ітерації, Я просто роблю це на кінець кожної ітерації. Так виходить, що цей алгоритм, теж, як правило, називається сортування вставкою, Також на порядок п квадрата. Це не насправді не краще, чи не краще взагалі. 

Проте, є і третій підхід Я хотів би закликати нас до розгляду, що це. Отже, нехай мій список, для простоти знову ж таки, чотири, один, три, two-- всього чотири номери. Бен мав хорошу інтуїцію, хороша людська інтуїція до того, за допомогою якого ми фіксували весь список eventually-- вставки сортування. Я умовив нас вперед. Але давайте розглянемо Найпростіший спосіб виправити цей список. 

Цей перелік не впорядкований. Чому? В англійській мові пояснити, чому це насправді не сортується. Що це значить не бути відсортовані? 

СТУДЕНТ: Це не послідовний. 

DAVID Маланки: Чи не послідовний. Дайте мені приклад. 

СТУДЕНТ: Помістіть їх в порядку. 

DAVID Маланки: OK. Дайте мені більш конкретний приклад. 

СТУДЕНТ порядку зростання. DAVID Маланки: Не в порядку зростання. Бути більш точним. Я не знаю, що ви маєте на увазі по зростанню. Що не так? 

СТУДЕНТ: Найменший з цифри не в першому просторі. 

DAVID Маланки: Найменший номера моделі не в першому просторі. Будьте більш конкретними. Я починаю ловити на. Ми розраховуємо, але що з ладу тут? 

СТУДЕНТ: числова послідовність. DAVID Маланки: числова послідовність. вид кожної людини утримування вона here-- дуже високий рівень. Просто буквально сказати мені, що не так, як п'ять-річної потужності. 

СТУДЕНТ: Плюс один. 

DAVID Маланки: Що це? 

СТУДЕНТ: Плюс один. 

DAVID Маланки: Що ви маєте на увазі плюс один? Дайте мені інший п'ять років. Що трапилося, мама? Що трапилося, тато? Що ви маєте на увазі це не впорядкований? 

СТУДЕНТ: Це не місце. 

DAVID Маланки: Що не в потрібному місці? 

СТУДЕНТ: Чотири. DAVID Маланки: Добре, добре. Так чотири не там, де вона повинна бути. Зокрема, це вірно? Чотири і один, перший два числа, які я бачу. Чи це правильно? Ні, вони не в порядку, чи не так? Насправді, думаю, що зараз про комп'ютер, теж. Він може дивитися тільки на одну, може бути, може бути, дві речі в once-- а насправді тільки одна річ, в той час, але він може принаймні, подивитися на одну річ, то Наступне, що прямо поруч з ним. 

Так само ці в порядку? Звичайно, ні. Таким чином, ви знаєте, що? Чому б нам не взяти дитину кроки усунути цю проблему замість того, щоб робити ці фантазії алгоритми, такі як Бен, де він начебто фіксуючи його пробігаємо за списком замість того, щоб робити те, що я зробив, де Я тільки частково встановив його, як ми йдемо? Давайте просто буквально зламати Поняття order-- числового порядку, назвати це все, що ви want-- в цих парних порівнянь. 

Чотири і один. Чи є це правильний порядок? Отже, давайте виправимо це. Один і чотири, а потім ми просто скопіювати це. Добре, добре. Я встановив один і чотири. Три і два? Немає. Нехай мої слова збігаються мої пальці. Чотири і три? 

Це не в порядку, так що я збираюся щоб зробити один, три, чотири, два. ОК добре. Тепер чотири і два? Нам потрібно, щоб виправити це, теж. Так один, три, два, чотири. Так це сортується? Ні, але це ближче до впорядкований? 

Це, тому що ми це виправив помилка, ми виправили цю помилку, і ми виправили цю помилку. Таким чином, ми зафіксували три помилки, можливо. Проте не виглядає відсортоване, але вона об'єктивно ближче до відсортоване тому що ми зафіксували деякі з цих помилок. 

Тепер те, що мені робити далі? Я частково досяг кінця списку. Я, здавалося, закріпилася всі помилки, але немає. Тому що в цьому випадку, деякі номери можливо, пузирилися ближче на інші номери, які як і раніше не в порядку. Так що давайте робити це знову, і я буду просто зробити це на місці цього разу. Один і три? Все добре. Три і два? Звичайно, немає, так що давайте змінити цю ситуацію. Так два, три. Три і чотири? А тепер давайте просто особливо педантичним тут. сортується це? Ви, люди знають, що це сортується. 

Я повинен спробувати ще раз. Так що Олівія пропонує мені спробувати ще раз. Чому? Оскільки комп'ютер не має розкіш наших людських очей просто глянувши back-- ОК, я зробив. Як комп'ютер визначає що список тепер відсортований? Механічно. 

Я повинен пройти через ще раз, і тільки тоді, коли я не роблять / знайти будь-які помилки, я можу потім зробити висновок, як комп'ютер, так, ми добре йти. Так один і два, два і три, три і чотири. Тепер я можу остаточно сказати, що це сортують, тому що я не зробив ніяких змін. Тепер це буде помилка і просто нерозумно, якщо я, комп'ютер, знову запитав ті ж питання чекаючи різні відповіді. Не повинно статися. 

І ось тепер список відсортований. На жаль, біг часу цей алгоритм також N в квадраті. Чому? Оскільки у вас є п числа, а в гіршому випадку ви повинні рухатися п чисел п раз, тому що ви повинні продовжувати йти тому, щоб перевірити і виправити потенційно ці цифри. І ми можемо зробити більше формальний аналіз теж. 

Так що це все, щоб сказати, що ми зробили три різних підходи, один з них відразу ж інтуїтивно від кажана від Ben до мого пропонованого включення сортувати до цього де ви начебто обійти увагою ліс за деревами на початковому етапі. Але тоді, якщо ви зробити крок назад, вуаля, ми виправили сортувальний поняття. Так що це, насмілюся сказати, нижчий рівень, можливо, ніж деякі з тих інших алгоритми, але давайте побачити, якщо ми не можемо уявити собі вони через це. 

Так що це якийсь хороший програмне забезпечення, яке хтось написав, використовуючи барвисті бари, що це збирається зробити наступне для нас. Кожен з цих стержнів є число. Taller стовпчик, тим більше число, менше бар, тим менше число. Так що в ідеалі ми хочемо хорошу піраміду де вона починається з малого і стає великою, і це буде означати, що ці бари упорядковано. Так що я збираюся йти вперед і вибирати, наприклад, алгоритм Бен first-- вибір сортування. 

І зауважте, що він робить. Те, як вони вибрали візуалізувати цей алгоритм в тому, що, так само, як я був ходити через мій список, ця програма йде через свій список номерів, виділяючи в рожевий колір кожного число, яке він дивиться. А що має статися прямо зараз? 

Найменше число, Я або Бен виявив раптом отримує переміщається в початок списку. І зверніть увагу, що вони зробили виселити номер, який був там, і це прекрасно. Я не потрапив в цей рівень деталізації. Але нам потрібно поставити що число десь, так що ми просто перемістив його до відкрите місце, яке було створено. Так що я збираюся прискорити цей процес вгору, тому що в іншому випадку він стає дуже виснажливим швидко. Анімація speed-- там ми йдемо. Так що тепер же принцип Я застосовувала, але ви може почати відчувати себе алгоритм, якщо ви буде, або побачити його трохи більш чітко. І цей алгоритм має ефект вибираючи наступний найменший елемент, так що ви збираєтеся розпочати він підніметься на лівій стороні. І на кожній ітерації, як я запропонував, він робить трохи менше роботи. Він не повинен пройти весь шлях назад до лівого кінця списку, тому що це вже знає тих, упорядковано. Так що це свого роду відчуває, як це прискорення, хоча кожен крок приймаючи таку ж кількість часу. Там в решту всього менше кроків. І тепер ви можете частково відчуваю Алгоритм очищення в кінці його, і справді тепер це сортується. 

Таким чином, сортування вставкою все це робиться. Мені потрібно повторно рандомізації масив. І зауважте, я можу просто тримати його рандомізації, і ми отримаємо наближення той же підхід, сортування вставкою. Дозвольте мені уповільнити його сюди. Давайте почнемо, що більш. СТОП. 

Давайте пропустити чотири. Там ми йдемо. Перемішайте їх масив. І тут ми go-- вставки роду. Грати. Зверніть увагу на те, що він має справу з кожним елемент він зустрічає відразу ж, але якщо вона належить неправильне місце повідомлення всі роботи, що має статися. Ми повинні продовжувати перехід більш і більше елементів, щоб звільнити місце для того, що ми хочемо, щоб поставити на місце. 

Таким чином, ми зосереджуємося на лівий кінець тільки список. Зауважте, що ми навіть не дивилися at-- ми не виділені рожевим кольором що-небудь направо. Ми просто маємо справу з проблеми, як ми йдемо, але ми створюємо багато працювати для себе досі. І тому, якщо ми прискорити цей процес Тепер, щоб перейти до завершення, вона має інше почуття до нього насправді. Це просто зосередитися на лівому кінці, але робити трохи більше роботи, як needed-- вид згладжують речей більше, фіксуючи речі, але справа в кінцевому рахунку, з кожен елемент по одному за раз поки ми не отримаємо добре the--, ми всі знають, як це збирається закінчитися, так що це трохи нищівної можливо. 

Але список в end-- spoiler-- збирається бути відсортовані. Отже, давайте розглянемо один останній. Ми не можемо просто пропустити цей. Ми майже там. Два йти, один йти. І вуаля. Відмінно. 

Так що тепер давайте зробимо одну останню, повторно рандомізації з бульбашкового сортування. І зауважте тут, особливо якщо я уповільнити його вниз, це тримати ширяє до кінця. Але зверніть увагу, це тільки робить парно comparisons-- роду локальних рішень. Але як тільки ми отримуємо кінець списку в рожевий, що доведеться статися знову? Так, це доведеться почати все спочатку, тому що це тільки Нерухомі попарні помилки. І це, можливо, виявили ще інші. І тому, якщо ви прискорити цей процес, ви будете бачимо, що, подібно до того як випливає з назви, тим менше elements-- або, вірніше, великі elements-- починають пузиритися до самого верху, якщо ви будете. А більш дрібні елементи починаючи пузиритися вниз вліво. І справді, це свого роду візуальний ефект, а також. І таким чином це буде в кінцевому підсумку обробка в дуже схожим чином, теж. 

Ми не повинні зупинятися у цій конкретній одному. Дозвольте мені відкрити це зараз, теж. Там в кілька інших алгоритмів сортування в світі, деякі з яких захоплюються тут. І спеціально для учнів, які не є обов'язково візуальне або математичне, як ми робили раніше, ми можемо також зробити це audially якщо асоціювати звук з цим. І просто для задоволення, ось кілька різних алгоритмів, і один з них, зокрема, ви помітить, називається "сортування злиттям." 

Це насправді принципово краще алгоритм, таким чином, що сортування злиттям, один з ті, з якими ви хочете бачити, не порядок п в квадраті. Це про порядок п раз Логарифм N, яка насправді менше, і, таким чином, швидше, ніж інші три. І є пара інший дурні ті, що ми будемо бачити. 

Так що тут ми йдемо з деяким звуком. Це сортування вставкою, так що знову це просто справа з елементами як вони приходять. Це свого роду міхур, так що вважаючи їх пари одночасно. І знову ж таки, найбільші елементи проривається до самого верху. 

Далі вибір сортування. Це алгоритм Бен, де знову він итеративно вибору Наступного найменший елемент. І знову ж таки, тепер ви можете дійсно почути, що це прискорення, але тільки в тій мірі, як це робить все менше і менше працювати на кожній ітерації. Це швидше, сортування злиттям, який сортує кластери чисел разом, а потім об'єднуючи їх. Так look-- лівий половина вже відсортовані. 

Тепер це сортування праву половину, і Тепер він збирається об'єднати їх в одне ціле. Це те, що називається "Гном роду." І ви можете частково бачити, що він ходить взад і вперед, фіксуючи роботу трохи тут і там, перш ніж він приступає до нової роботи. І це все. Там в інший вид, який дійсно тільки для академічних цілей, називається "дурним роду", який приймає Ваші дані, сортує його в випадковому порядку, а потім перевіряє, чи є вона сортується. І якщо це не так, то знову сортує його випадковим чином, перевіряє, чи є вона сортується, і якщо не повторюється. І в теорії, вероятностно це буде завершено, але після того, як зовсім небагато часу. Це не самий ефективність алгоритмів. Так що будь-які питання про тих, конкретні алгоритми або що-небудь пов'язаних там теж? 

Що ж, давайте тепер дражнять один від одного, що все ці лінії, які я малюю і те, що я припускаю, що комп'ютер може зробити під капотом. Я вважаю, що всі ці цифри Я тримаю drawing-- вони повинні отримати зберігається десь в пам'яті. Ми позбутися цього хлопця зараз теж. 

Таким чином, частина пам'яті в computer-- так RAM пам'яті складає то, що ми шукали вчора, подвійний вбудована пам'ять module-- виглядає наступним чином. І кожен з цих маленьких чорних фішок деяка кількість байтів, як правило. А потім золоті шпильки подібні дроти, які підключаються до комп'ютера, і зелена дошка кремнію просто що тримає все разом. Так що ж це насправді означає? Якщо я як би зробити такий же картину, давайте припустимо для простоти що цей модуль DIMM, подвійний вбудований модуль пам'яті, один гігабайт оперативної пам'яті, один гігабайт пам'ять, яка, скільки всього байт? Один гігабайт це скільки байт? Більше того. 1124 є кілограм 1000. Мега млн. Гіга це мільярд. 

Я лежу? Чи можемо ми навіть читати етикетку? Це насправді 128 гігабайти, так що це більше. Але ми будемо робити вигляд, це це тільки один гігабайт. Так що означає, що є мільярд байт пам'яті, доступної для мене або 8 мільярдів біт, але ми збираємося говорити в термінах байтів в даний час, рухатися вперед. 

Так що це значить, це один байт, це ще один байт, це ще один байт, і якщо ми дійсно хотіли щоб бути конкретним, ми б залучити мільярд маленьких квадратів. Але що це означає? Що ж, дозвольте мені просто збільшити в цій фотографії. Якщо у мене є щось, що виглядає як це зараз, це чотири байти. 

І таким чином я міг би поставити чотири числа тут. Один два три чотири. Або я міг би поставити чотири букви або символи. "Гей!" може піти прямо там, тому що кожна з букв, ми обговорювали раніше, може бути представлена з вісьмома бітами або ASCII або байт. Отже, іншими словами, ви можете поставив 8 мільярдів речі всередині цієї однієї палиці пам'яті. Тепер те, що це означає, щоб покласти речі назад щоб спина до спини в пам'яті, як це? Це те, що програміст могли б назвати "масив". У комп'ютерній програмі, ви не думаєте, про основні апаратних засобів, саме по собі. Ви просто думаєте про себе як такі, що доступ до цілому в мільярд байтів, і ви можете все, що ви хочете з ним. Але для зручності це взагалі корисно щоб зберегти своє право пам'яті поруч один з одним, як це. Так що якщо я збільшити на this-- тому що ми, звичайно, не збирається залучити мільярд маленьких squares-- давайте припустимо, що ця плата становить що палиця пам'яті в даний час. І я просто зробити так багато, як мій Маркер закінчується тим, що дав мені тут. Так що тепер у нас є палиця пам'яті на борту що є один, два, три, чотири, п'ять, шість, один, два, три, чотири, п'ять, шість, seven-- близько того 42 байта Пам'ять на загальній екрану. Дякую. Так, зробив мій арифметика правильно. Так 42 байт пам'яті тут. Так що ж це насправді означає? Ну, комп'ютерний програміст буде насправді, як правило думати про цю пам'яті як адресно. Іншими словами, кожен з них місця в пам'яті, в апаратних засобах, має унікальну адресу. 

Це не так складно, як один Brattle Площа, Кембридж, штат Массачусетс., 02138. Замість цього, це просто число. Це байт з номером нуль, це По-перше, це два, це три, і це 41. Почекай хвилинку. Я думав, що я сказав, 42 хвилину тому. Я почав відлік з нуля, так що це насправді правильно. Тепер ми не повинні фактично зробити його у вигляді сітки, і якщо ви малюєте його в вигляді сітки Я думаю, що речі насправді отримати трохи вводить в оману. Який програміст, в своєму власному розумі, як правило, думають про це пам'яті, як це так само, як стрічки, як шматок липкою стрічкою що просто йде далі і далі назавжди або поки не закінчаться пам'яті. Таким чином, більш поширеним способом привернути і думати тільки про пам'ять було б, що це байта нуль, один, два, три, а потім точка, точка, точка. І у вас є всього 42 таких байтів, навіть хоча фізично він може насправді бути чимось більшим, як це. 

Так що якщо ви зараз думаєте про вашу пам'яті, так як це, так само, як стрічки, це те, що програміст знову назвали б масив пам'яті. І коли ви дійсно хочете зберегти щось в пам'яті комп'ютера, Ви взагалі робите зберігання речей спина до спини спина до спини. Таким чином, ми говоримо про цифри. І коли я хотів, щоб вирішити проблеми як чотири, один, три, два, хоча я був просто малюнок тільки цифри чотири, один, три, два на борту, комп'ютер дійсно цю установку в пам'яті. 

А що було б поруч з два в пам'яті комп'ютера? Ну, немає ніякої відповіді на це. Ми дійсно не знаємо. І до тих пір поки комп'ютер не потрібен, він не повинен піклуватися, що буде далі до числам це дійсно піклується про. І коли я вже говорив раніше, що комп'ютер можна дивитися тільки за однією адресою в той час, це свого роду чому. 

Чи не на відміну від запису плеєр і голівки, що зчитує тільки будучи в стані дивитися на певний канавка в фізичної записи старої школи в той час, аналогічним чином може комп'ютер завдяки її центрального процесора і його комплект Intel інструкція, серед яких інструкції зчитується з пам'яті або зберегти memory-- комп'ютер може тільки дивитися в одному місці при time-- іноді їх поєднання, але насправді тільки в одному місці в той час. Тому, коли ми робимо ці різні алгоритми, Я не просто писати в vacuum-- чотири, один, три, два. Ці цифри насправді належать десь фізичної пам'яті. Так що є крихітне транзисторів або якийсь електроніки під капот зберігання цих значень. 

А в цілому, скільки біт участь прямо зараз, щоб бути ясно? Так що це чотири байти, або тепер це всього 32 біта. Так що є насправді 32 нулів і ті складові ці чотири речі. Там навіть більше тут, але знову ми не дбаємо про це. 

Так що тепер давайте поставимо інший Питання використання пам'яті, тому що це в кінці дня в дисперсії. Незалежно від того, що ми могли б зробити з комп'ютер, в кінці дня апаратні засоби і раніше те ж саме під капотом. Як би я зберігати слово тут? Ну, слово в комп'ютері, як "Гей!" буде зберігатися так само, як це. І якщо ви хотіли більше слово, ви можете просто перезаписати, що і сказати щось як "привіт" і магазин, який тут. 

І ось тут теж, це contiguousness насправді є перевагою, тому що комп'ютер може просто читати справа наліво. Але ось питання. В контексті цього слова, ч-е-л-л-о, знаку оклику, як, можливо, комп'ютер знає, де слово починається і де закінчується слово? У контексті чисел, як робить комп'ютер знаю, як довго послідовність номера або де вона починається? Що ж, виявляється out-- і ми не будемо надто багато в цей рівень detail-- комп'ютери переміщати речі навколо в пам'яті буквально через ці адреси. Таким чином, в комп'ютері, якщо ви написання коду для зберігання речей як і слова, що ви насправді робить друкує Вирази, які пам'ятають, де в пам'ять комп'ютера ці слова. Отже, дозвольте мені зробити дуже, дуже простий приклад. 

Я збираюся йти вперед і відкрити просту текстову програму, і я збираюся створити файл з ім'ям hello.c. Велика частина цієї інформації ми Не буду вдаватися в дуже докладно, але я збираюся написати Програма в тій же самій мові, C. Це набагато більш страшним, Я б сказав, що нуля, але це дуже схоже за духом. Насправді, ці фігурна braces-- ви можете вид думаю про те, що я тільки що зробив, як це. 

Давайте зробимо це, насправді. Коли зелений прапор клацнув, виконайте наступні дії. Я хочу, щоб роздрукувати "привіт". Так що тепер це псевдокод. Я частково розмиваючи кордону. У C, ця мова я говорю О, ця лінія друку привіт фактично стає "Printf" з деякі круглі дужки і крапка з комою. 

Але це точно така ж ідея. І це дуже зручно "Коли зелений прапор клацнув" стає набагато більш аркан "INT головний недійсним." І це насправді не має ніякого відображення, так що я буду просто ігнорувати це. Але фігурні дужки подібні вигнуті частини головоломки, як це. 

Так що ви можете вгадати вид. Навіть якщо ви ніколи не програмували раніше, що робить ця програма, ймовірно, робити? Можливо друкує привіт зі знаком оклику. 

Так давайте спробуємо це. Я збираюся зберегти його. І це, знову ж таки, дуже стара шкільна середу. Я не можу натиснути, я не можу перетягнути. Я повинен вводити команди. Тому я хочу, щоб запустити свою програму, так що Я міг би зробити це, як hello.c. Це файл я побіг. Але почекайте, я пропускаю крок. Що ми говоримо, є необхідною крок для мови як C? Я тільки що написав джерело код, але що мені потрібно зробити? Так, мені потрібен компілятор. Так що на моєму Mac тут, у мене є Програма під назвою GCC, GNU C компілятор, яка дозволяє мені робити this-- поворот мій вихідний код в, ми будемо називати його, машинний код. 

І я бачу, що, ще раз, як показано нижче, ці є нулі і одиниці я просто створений з мого вихідного коду, всі нулі і одиниці. І якщо я хочу працювати мій program-- це відбувається називатися a.out для історичні reasons-- "привіт". Я можу запустити його знову. Привіт привіт привіт. І це, здається, працює. 

Але це означає, що десь в моєму пам'ять комп'ютера слова ч-е-л-л-о, оклику. І виявляється, так само, як і в сторону, що таке комп'ютер, як правило, зробити так, що він знає, де речі починають і end-- це збирається поставити спеціальний символ тут. І конвенція повинна поставити номер нуль в кінці слова так що ви знаєте, де це насправді закінчується, так що ви Не примушуйте себе продовжувати друкувати більше і більше символів, ніж ви насправді мають наміру. 

Але тут їжа на будинок, навіть хоча це досить аркан, є те, що це в кінцевому рахунку відносно просто. Ви отримали вид стрічки, заготовки простір, на якому можна писати листи. Ви просто повинні мати спеціальний символ, як завгодно число нуль, щоб покласти в кінці ваші слова так, що комп'ютер знає, ой, я повинен відмовитися від друку після того, як Я бачу знак оклику. Тому що наступна річ там це значення ASCII нуля, або нульовий символ, як хтось назве його. Але є свого роду проблеми тут, і давайте повернутися числах на хвилину. Припустимо, що я, насправді, є масив чисел, і припустимо, що Програма Я пишу це як клас книга для вчителя і вчителів класі. І ця програма дозволяє йому або їй щоб набрати бали своїх учнів на вікторинах. І припустимо, що студент отримує 100 на їх першої вікторини, може бути, як 80 на наступний, то 75, а потім 90 на четвертій вікторини. 

Таким чином, в цей момент в історії, масив має розмір чотири. Там абсолютно більше пам'яті в комп'ютер, але масив, так би мовити, має розмір чотири. Припустимо тепер, що вчитель хоче призначити п'ятий тест на клас. Ну, одна з речей, які він або вона буде мати, щоб зробити тепер зберігати додаткову цінність тут. Але якщо масив вчитель має Створений в цій програмі має розмір для, одна з проблем з масивом є те, що Ви не можете просто продовжувати додавати до пам'яті. Тому що, якщо інша частина Програма має слово "гей" прямо там? 

Іншими словами, пам'ять може бути використовується для чогось в програмі. А якщо заздалегідь я надрукував, агов, Я хочу, щоб введення чотирьох балів вікторини, вони могли б піти тут і тут. І якщо ви раптом передумаєте пізніше і сказати, що я хочу п'ятий вікторини рахунок, ви не можете просто покласти його туди, куди ви хочете, тому що, якщо це пам'яті використовується для чогось else-- іншу програму або будь-якої іншої особливістю програми що ви працюєте? Таким чином, ви повинні думати заздалегідь як ви хочете зберігати ваші дані, тому що тепер ви пофарбовані себе в цифровий кут. 

Таким чином, замість того, щоб учитель міг би кажуть, при написанні програми зберігати його або її класів, ви знаєте, що? Я буду просити, при написанні моєї програми, що я хочу, нуль, один, два, три, чотири, п'ять, шість, вісім класів в цілому. Так один, два, три, чотири, п'ять, шість, сім, вісім. Викладач може просто неправомірно пропагувати пам'яті при написанні свою програму і сказати, ви знаєте, що? Я ніколи не буду призначати більш ніж через вісім вікторин протягом семестру. Це просто безумство. Я ніколи не буду виділяти це. Так що таким чином він або вона має гнучкість для зберігання студентських балів, як 75, 90, і, можливо, один додатковий, де студент отримав додатковий кредит, 105. 

Але якщо вчитель ніколи використовує ці три простору, є інтуїтивне винос тут. Він або вона просто витрачати простір. Отже, іншими словами, є цей загальний компроміс в програмуванні де ви можете або виділити рівно стільки пам'яті, скільки ви хочете, потенціал зростання якого є те, що ти супер efficient-- ви не бути марнотратним на all-- але нижня сторона якого є те, що якщо ви зміните свою думку, коли за допомогою програми, яку ви хочете зберегти більше даних, ніж спочатку передбачалося. 

Тому, можливо, це рішення, то, писати свої програми таким чином, що вони використовують більше пам'яті ніж вони насправді потрібно. Таким чином, ви не збираєтеся нарватися на цю проблему, але ви бути марнотратним. І чим більше пам'яті ваша програма використовує, як ми обговорювали вчора, тим менше пам'ять, яка доступна для інших програм, тим швидше ваш комп'ютер може уповільнити вниз через віртуальної пам'яті. І тому ідеальним рішенням може бути те, що? 

Під-виділяють здається поганим. Надмірна здається погано Виділення. Так що може бути кращим рішенням? Перерозподіл. Будьте більш динамічним. Чи не змушувати себе вибрати апріорі, на самому початку, що ви хочете. І, звичайно, не неправомірно пропагувати, щоб не бути марнотратним. 

І так, щоб досягти цієї мети, ми потрібно кинути цю структуру даних, так би мовити, геть. І так, що програміст як правило, використовують щось не називається масив, але пов'язаний список. Іншими словами, він або вона буде починають думати про свою пам'ять як є свого роду форму, що вони можна зробити наступним чином. Якщо я хочу, щоб зберегти номер в program-- тому вересня Я дав моїм студентам вікторини; я хочу для зберігання першої вікторини студентів, і вони отримали 100 на it-- I задам мій комп'ютер, шляхом програми я написано, для одного шматка пам'яті. І я буду зберігати номер 100 в ньому, і це все. 

Потім кілька тижнів потому коли я отримаю свій другий вікторини, і настав час, щоб набрати в тому, що 90%, я збираюся щоб запитати комп'ютер, агов, комп'ютер, може у мене є ще один шматок пам'яті? Це збирається дати мені це порожній шматок пам'яті. Я збираюся поставити в число 90, але в моїй програмі якось або other-- і ми не будемо турбуватися про Синтаксис this-- мені потрібно як-то ланцюг ці речі разом. І я прикувати їх разом з що виглядає як стріла тут. 

Третій тест, який приходить, Я збираюся сказати, агов, комп'ютер, дайте мені ще один шматок пам'яті. І я збираюся покласти вниз Як би там не було, як 75, і я повинен ланцюга цієї разом зараз якось. Четвертий вікторини приходить разом, і, можливо, що це ближче до кінця семестру. І до того моменту моя програма може бути з використанням пам'яті всюди, у всьому фізично. І ось якраз для стусанів, я збирається зробити це вперед quiz-- я забув, що це було; Я думаю, може бути, 80 або something-- шлях тут. 

Але це нормально, тому що зображально Я збираюся намалювати цю лінію. Іншими словами, в дійсності, в апаратному забезпеченні вашого комп'ютера, перший рахунок може в кінцевому підсумку тут, тому що це прямо на початку семестру. Наступним може в кінцевому підсумку тут бо трохи часу пройшло і програма продовжує працювати. Наступний показник, який був 75, може бути тут. І остання оцінка може бути 80, який знаходиться тут. 

Таким чином, в дійсності, фізично, це може бути яка пам'ять комп'ютера виглядає наступним чином. Але це не є корисним психічного парадигма для програміста. Чому ви повинні піклуватися, де клямка ваші дані в кінцевому підсумку? Ви просто хочете зберегти дані. 

Це ніби як нашій дискусії раніше малювання куба. Чому ви все одно, що кут куба і як потрібно повернути, щоб привернути його? Ви просто хочете куб. Точно так же тут, ви просто хочу, щоб клас книги. Ви просто хочете, щоб думати про це як список номерів. Хто дбає, як це реалізовані в апаратних засобах? 

Таким чином, абстракція в даний час ця картина тут. Це пов'язано список, як і програміст назвав би це, оскільки у вас є список, очевидно чисел. Але це пов'язано зображально за допомогою цих стрілок, і всі ці стрілки are-- під капот, якщо вам цікаво, Нагадаємо, що наше фізичне обладнання має адреси нуль, один, два, три, чотири. Всі ці стріли як карта або напрямки, де, якщо 90 is-- прямо зараз Я повинен розраховувати. 

Нуль, один, два, три, чотири, п'ять, шість, сім. Схоже, що 90 знаходиться згадку про адресу номер сім. Всі ці стріли є як маленький клаптик паперу який дає напрямках до програма, яка говорить, що слідувати цій карті щоб дістатися до місця сім. І там ви знайдете другий студентський вікторини рахунок. Тим часом, 75-- якщо я буду продовжувати це, це сім, вісім, дев'ять, 10, 11, 12, 13, 14, 15. 

Ця інша стрілка просто представляє карта пам'яті на місце 15. Але знову ж таки, як правило, програміст робить не дбають про цей рівень деталізації. І в більшості кожного програмування мова сьогодні, програміст навіть не буде знати, де в пам'яті ці цифри насправді. Все, що він або вона повинен піклуватися про те, що вони якимось чином пов'язані один з одним в структурі даних, як це. 

Але виявляється, не щоб отримати занадто технічний. Але тільки тому, що ми можемо, можливо, дозволити собі мати цю дискусію тут, Припустимо, що ми знову це питання тут масиву. Давайте подивимося, якщо ми збираємося тут шкодують. Це 100, 90, 75, і 80. 

Дозвольте мені коротко зробити цю заяву. Це масив, і знову, характерною ознакою яких масиву є те, що всі ваші дані назад спина до спини в memory-- буквально один байт або, може бути чотири байти, деяке фіксоване число байтів геть. У пов'язаному списку, який ми могли б зробити як це, під капотом, який знає де, що матеріал? Він навіть не потрібно чинити так. Деякі дані можуть бути назад вліво там. Ви навіть не знаєте. 

І так з масивом, у вас є особливість відома як випадкового доступу. А які кошти довільного доступу що комп'ютер може стрибати миттєво в будь-яке місце в масиві. Чому? Оскільки комп'ютер знає що перше місце розташування нуль, один, два, і три. 

І тому, якщо ви хочете, щоб перейти від цей елемент до наступного елементу, ви в буквальному сенсі, в розум комп'ютера, просто додайте один. Якщо ви хочете, щоб перейти до третього елементу, просто додайте одно-- наступний елемент, просто додайте. Проте, в цій версії історії, припустимо, комп'ютер в даний час шукає на або маємо справу з номером 100. Як ви отримуєте до наступного клас в класі книги? 

Ви повинні прийняти сім кроки, які довільно. Для того, щоб дістатися до наступного, ви повинні прийняти ще вісім кроків, щоб дістатися до 15. Іншими словами, це не постійний зазор між числами, і тому він просто бере Комп'ютер більше часу точка. Комп'ютер повинен шукати через пам'ять в порядку щоб знайти те, що ви шукаєте. 

Таким чином, в той час як масив має тенденцію бути швидко дані structure-- бо ви може буквально зробити просту арифметику і потрапити туди, куди ви хочете, додавши до нього один, для instance-- пов'язаний список, ви жертвуєте цю функцію. Ви не можете просто йти від першої на другий третій четвертий. Ви повинні слідувати карті. Ви повинні вжити додаткових заходів, щоб дістатися до тих значень, які Здавалося б, додавання вартості. Таким чином, ми платимо ціну, але те, що було особливість, що Ден шукав тут? Що робить пов'язаний список мабуть, дозволяють нам робити, який був походження ця конкретна історія? 

Абсолютно вірно. Динамічний розмір для нього. Ми можемо додати до цього списку. Ми можемо навіть скоротити список, так що ми тільки використовуючи стільки пам'яті як ми насправді хочемо і так ми ніколи не надмірно розподілу. 

Тепер просто, щоб бути дійсно NIT-розбірливі, є приховані витрати. Таким чином, ви не повинні просто дайте мені переконати ви, що це є переконливим компромісом. Там інша прихована вартість тут. Перевага, щоб бути ясно, є те, що ми отримуємо динамічність. Якщо я хочу ще один елемент, я можу просто намалювати його і поставити ряд там. І тоді я можу пов'язати його із зображенням тут, в той час як тут, знову ж таки, якщо я пофарбовані себе в кут, якщо щось ще вже використовує пам'ять тут, я не пощастило. Я намалював себе в кут. 

Але те, що прихований варто в цій картині? Це не просто сума часу, який потрібен йти звідси тут, який сім кроків, а потім вісім кроків, що більш ніж один. Що ще одна прихована вартість? Не тільки час. Додаткова інформація необхідно для досягнення цієї фотографії. 

Так, ця карта, ці маленькі клаптики паперу, як я продовжую описувати їх як. Ці arrows-- ті не є вільними. Computer-- ви знаєте, то, що комп'ютер має. Він має нулі і одиниці. Якщо ви хочете, щоб представляти стрілу або А карту або номер, вам потрібно кілька пам'яті. Так що з іншою ціною, яку ви платити за пов'язаного списку, загальна інформатика ресурс, також простір. 

І справді так, так часто, серед компроміси в розробці програмної інженерії системи час і space-- два з ваших інгредієнтів, два з ваших самих дорогих інгредієнтів. Це коштувало мені більше часу тому що я повинен слідувати цій карті, але це також варто мені більше місця тому що я повинен тримати цю карту навколо. Таким чином, надія, як ми свого роду обговорювався протягом вчорашнього дня і сьогодні, в тому, що вигоди переважать витрати. 

Але немає ніякого очевидного рішення тут. Може бути, це better-- а-ля швидкий і брудний, а Карім запропонував earlier-- кинути пам'ять на проблему. Просто купіть більше пам'яті, менше думати важко про вирішення проблеми, і вирішити її в більш простий спосіб. І дійсно раніше, коли ми говорили про компроміси, воно не було місця в комп'ютер і час. Це був час, розробник, який це ще один ресурс. 

Отже, ще раз, саме це урівноваження намагаючись вирішити, який з цих речей ви готові витратити? Який є найменш дорогим? Що дає кращі результати? Так? 

Справді. У цьому випадку, якщо ви представлення чисел в maps-- їх називають на багатьох мовах "Покажчики" або "адреси" - це подвійне простір. Це не повинно бути так погано, як подвійний, якщо Прямо зараз ми просто зберігання чисел. Припустимо, що ми зберігали записи пацієнта в hospital-- так називає Пірсона, номери телефонів, номера соціального страхування, доктор історія. Це поле може бути багато, набагато більше, і в цьому випадку крихітна покажчик, адреса наступна element-- це не має великого значення. Це така бахрома вартість не має значення. Але в цьому випадку, так, це подвоєння. Гарне питання. 

Давайте поговоримо про той час, а трохи конкретніше. Що час роботи пошуку цей список? Припустимо, що я хотів шукати через всі класи студентів, і є п класів в цій структурі даних. Тут, також, ми можемо запозичити словниковий запас раніше. Це лінійна структура даних. 

Big O п є те, що потрібно, щоб отримати до кінця цієї структури даних, whereas-- і ми не бачили це before-- масив дає вам що називається постійної часу, що означає, один крок або два кроки або 10 steps-- не має значення. Це фіксоване число. Вона не має нічого спільного з розмір масиву. І причина цього, знову ж таки, з довільним доступом. Комп'ютер може просто негайно перейти на інше місце, тому що вони все одно відстань від всього іншого. Там немає мислення бере участь. Добре. Так що, якщо я можу, я спробую намалювати два фінальних зображень. Дуже часто один відомий як хеш-таблицю. Таким чином, щоб мотивувати цю дискусію, дайте мені подумати про те, як це зробити. 

Так як щодо цього? Припустимо, що задача ми хочемо вирішити прямо зараз здійснює в dictionary-- так ціла купа англійських слів або будь-який інший. І мета полягає в тому, щоб бути в змозі відповісти питання формі це слово? Так що ви хочете реалізувати програма перевірки орфографії, просто як фізичний словник що ви можете подивитися речі в. Припустимо, я зробити це за допомогою масиву. Я міг би зробити це. 

І припустимо, що слова яблуко і банан і диня. І я не можу думати про фруктах які починаються з D, так що ми просто матиме три фруктів. Так що це масив, і ми зберігати всі ці слова в цьому словнику як масив. Питання, тоді, як ще Ви могли б зберігати цю інформацію? 

Ну, я свого роду обман тут, тому що кожна з цих букв в слові дійсно індивідуальний байт. Так що, якщо я дійсно хотів бути ніт-розбірливі, я повинен дійсно бути розділивши це вгору в набагато менші шматки пам'яті, і ми могли б зробити саме це. Але ми будемо працювати в та ж проблема, як і раніше. Що якщо, як Merriam Webster чи Оксфорд робить кожен год-- вони додають слова до dictionary-- ми не робимо обов'язково хочуть малювати себе в кут з масивом? 

Так що замість того, щоб, можливо, розумніші підхід це покласти яблуко в своєму власному вузлі або коробці, як би ми сказали, банан, і то тут ми маємо диню. І ми струна ці речі разом. Так що це масив, це пов'язаний список. Якщо ви не можете досить бачити, це просто каже "масив", і це говорить, що "список." 

Таким чином, ми маємо те ж саме точні питання, як і раніше, в результаті чого ми тепер маємо динамізм в нашому пов'язаному списку. Але у нас є досить повільний словник. Припустимо, я хочу, щоб шукати слово. Це може зайняти мені велику O п кроки, тому що слово може бути весь шлях в кінці список, як диня. І виходить, що в програмуванні, сортувати Грааля даних структури, щось що дає вам постійне час як масив але це як і раніше дає вам динамізм. 

Так що ми можемо мати краще з обох світів? І справді, є щось називається хеш-таблицю що дозволяє робити саме що, хоча і приблизно. Хеш-таблиця являє собою вправнішим Структура даних, які ми може думати, як поєднання array-- і я збираюся намалювати його як this-- і пов'язані списки що я буду малювати, як це тут. 

І то, як ця річ працює наступним чином. Якщо цей now-- хеш table-- моя третя структура даних, і я хочу, щоб зберегти Слова в цьому, я не хочу просто зберігати всі слова спина до спини, щоб спина до спини. Я хочу використовувати деякі частина інформації про слова, які дозволять мені отримати його там, де це швидше. 

Так що, з огляду на слова яблуко і банани і диня, Я навмисно вибрав ці слова. Чому? Щось принципово відрізняється про трьох? Що очевидно? Вони починаються з різних букв. 

Таким чином, ви знаєте, що? Замість того, щоб помістити всі мої слова в то ж відро, так би мовити, як в одному великому списку, чому не Я принаймні спробувати оптимізацію і зробити мої списки 1/26 до тих пір. переконливий оптимізація може бути, чому не Я-- при вставці слова в цю структуру даних, в пам'ять комп'ютера, чому я не віддав все 'а' слова тут, все 'Комерсант' слова тут, і все 'C' слова тут? Так що це в кінцевому підсумку покласти яблуко тут, банан тут, диню тут, і так далі. 

І якщо у мене є додатковий Слово like-- що інше? Яблуко, банан, груша. Будь думаю плода яка починається з А, В або С? Blueberry-- досконалим. Це буде в кінцевому підсумку тут. І тому ми, здається, є незначно краще рішення, тому що тепер, якщо я хочу шукати яблуко, я first-- Я не просто занурення в моїй структурі даних. Я не занурюйтесь в пам'ять мого комп'ютера. Я перший погляд на першу букву. 

І це те, що комп'ютер вчений сказав би. Ви хеш у вашій структурі даних. Ви берете свій внесок, який в цей випадок є слово, як яблуко. Ви аналізуєте його, дивлячись на перша буква в цьому випадку, тим самим хешування. Хеш є загальний термін, в результаті чого ви берете щось у якості вхідних даних і ви робите деякий висновок. І вихід в тому, випадок розташування Ви хочете знайти, перший місце, друге місце, третє місце. Таким чином, вхід яблуко, вихід першого. Вхід банан, Висновок повинен бути другим. Вхід диня, висновок повинен бути третім. Вхід чорниця, Висновок повинен знову бути другим. І це те, що допоможе вам прийняти ярлики через вашу пам'ять для того, щоб дістатися до слів або дані більш ефективно. 

Тепер це скорочує наш час потенційно по стільки, скільки один з 26, тому що якщо припустити, що ви мати стільки «а» слова, як "Z" слова, як "Q" слів, які насправді не realistic-- ви будете мати перекіс по деякі букви alphabet-- але це було б інкрементний Підхід, який дійсно дозволяє ви, щоб дістатися до слів набагато швидше. І справді, складний програма, то Googles світу, Facebooks з world-- вони будуть використовувати хеш-таблицю для багатьох різних цілей. Але вони не були б настільки наївний, щоб просто подивитися на першу букву в яблуко або банан або груша або диня, тому що, як ви можете бачити ці списки можуть отримати ще довго. 

І так що це ще може бути свого роду з linear-- так начебто повільно, як з великим O п що ми обговорювали раніше. Так що реальна хороша хеш-таблиця буде do-- він матиме набагато більший масив. І це буде використовувати набагато більше складні функції хешування, так що це не просто дивитися на «а». Може бути, він дивиться на "а-р-р-л-е" і якимось чином перетворює ці п'ять букв в тому місці, де яблуко має бути збережено. Ми просто по наївності, використовуючи букву 'A' поодинці, тому що це просто і красиво. 

Але хеш-таблицю, в кінець, ви можете думати у вигляді комбінації масив, кожен з яких має пов'язаний список, що в ідеалі має бути якомога коротшим. І це не є очевидним рішенням. Насправді, більша частина тонкої настройки що відбувається під капот, коли здійснення цих видів складні структури даних це те, що є правильним довжина масиву? Що таке правильний хеш-функція? Як ви зберігаєте речі в пам'яті? 

Але зрозуміти, наскільки швидко такого роду дискусії зростали, або до цих пір, що це свого роду з над головою в цей момент, який добре. Але ми почали, нагадаємо, з істинно щось низького рівня і електронні. І так це знову-таки це тема абстракції, де, як тільки ви почнете приймати для як належне, в порядку, у мене є it-- фізичної пам'яті, ОК, отримав його, кожен фізичне розташування має адресу, ОК, я отримав його, я можу уявити ці адреси як arrows-- Ви можете дуже швидко почати мати складніші розмови про те, в кінці кінців, здається, що дозволяє нам вирішувати проблеми, такі як пошук і сортування більш ефективно. І будьте впевнені, too-- тому що я думаю, що це є найглибшим ми пішли до деяких з цих тем CS proper-- ми зроблено в півтора дня на це вказати, що ви, можливо, як правило, роблять більш Протягом восьми тижнів протягом семестру. 

Будь-які питання по цим? Немає? Добре. Ну, чому б нам не зробити паузу там, почати обід на кілька хвилин раніше, резюме всього близько години? І я буду затримуватися трохи з питаннями. Тоді я буду повинен йти взяти пару дзвінків, якщо це нормально. Я включу музику в той же час, але обід повинен бути за кутом.