DAVID MALAN: W porządku. Jesteśmy z powrotem. Tak więc w tym segmencie na temat programowania, co Myślałam, że robimy to mieszanka rzeczy. Jeden z nich, zrobić trochę czegoś hands-on, aczkolwiek przy użyciu bardziej zabawny programowanie environment-- taki, który jest poglądowe od dokładnie te rodzaje pomysłów rozmawialiśmy o, ale trochę bardziej formalnie. Dwa, spojrzeć na niektóre sposoby bardziej techniczne że programista faktycznie rozwiąże Problemy takie jak problem poszukiwania że przyjrzeliśmy się przed i również bardziej fundamentalnie ciekawy problem sortowania. 

Po prostu zakłada się od uzyskania go że książka telefoniczna została posortowana, ale że sam jest w rzeczywistości rodzajem Trudno problem z wielu różnych sposobów go rozwiązać. Więc użyjemy je jako klasa problemów Przedstawiciel rzeczy może być rozwiązany w ogóle. A potem pogadamy o dość szczegółowo, co nazywane są dane structures-- bardziej wyszukane sposoby jak połączonych listach i tabele mieszania i drzewa, które programista faktycznie obsłudze i zazwyczaj używają na tablicy malować obraz tego, co on lub ona przewiduje dla realizacji niektóre kawałek oprogramowania. 

Więc zróbmy rąk na części pierwsze. Więc po prostu dostać w swoje ręce brudne ze związkiem środowisko zwane scratch.mit.edu. Jest to narzędzie, którego używamy w naszym licencjackich klasy. Mimo, że jest ono przeznaczone od wieków 12 i do góry używamy go w górę część tego całkiem sporo ponieważ jest to miłe, zabawa Graficzny sposób uczenia trochę coś o programowaniu. Więc głowa do tego adresu URL, gdzie powinien zobaczyć stronę zupełnie jak ta, i iść do przodu, a następnie kliknij Dołącz do podstaw w prawym górnym rogu i wybrać nazwę użytkownika i hasło i ostatecznie dostać się account-- scratch.mit.edu. Myślałam, że to wykorzystać jako Pierwsza okazja, aby pokazać to. Pytanie wpadł podczas przerwy o tym, co kod faktycznie wygląda. I rozmawialiśmy przerwę o C, w szczególności do: szczególniej Niższy poziom w starym języku. A ja po prostu nie szybkie wyszukiwarki Google, aby znaleźć kod C dla wyszukiwania binarnego, że algorytm wykorzystywany do wyszukiwania tę książkę telefoniczną wcześniej. Ten szczególny przykład oczywiście nie szukaj książkę telefoniczną. To po prostu przeszukuje całą masę Liczby w pamięci komputera. Ale jeśli chcesz po prostu wizualnym poczucie tego, co rzeczywiste programowania Język wygląda, wygląda trochę coś takiego. Więc to jest około 20-plus, 30 lub tak wierszy kodu, ale rozmowa mamy mieli na przerwie o tym, jak to było w rzeczywistości dostaje przekształcił zer i jedynek a jeśli nie można po prostu wrócić, że przetwarzać i przejść z zer i jedynek powrót do kodu. 

Niestety, proces jest tak przekształcające że o wiele łatwiej powiedzieć niż zrobić. I poszedł do przodu i rzeczywiście okazało ten program, Binary Search, do zer i jedynek w drodze Program zwany kompilator, że zdarzy się, że tutaj, w prawo na moim Macu. A jeśli spojrzeć na ekran tutaj, koncentrując się w szczególności na tych sześciu środkowych kolumn tylko, zobaczysz tylko zer i jedynek. A ci są zer i jedynek, które skomponowania dokładnie ten program wyszukiwania. 

I tak każda porcja pięciu bitów, każdy bajt zer i jedynek tutaj reprezentują jakąś instrukcję Zazwyczaj wewnątrz komputera. I rzeczywiście, jeśli słyszałeś marketing slogan "Intel inside" - które, Oczywiście, oznacza to po prostu mieć Intel CPU lub mózgu wewnątrz komputera. A co to znaczy być CPU że masz zestaw instrukcji, że tak powiem. 

Każdy procesor na świecie, wielu im wykonany przez firmę Intel w tych dniach, rozumie skończonym liczba instrukcji. A te instrukcje są tak niskie jak dodać te dwie liczby, pomnożyć te dwie liczby, przenieść ten kawałek danych stąd tu w pamięci, z wyjątkiem tego Informacje stąd tu w pamięci, i tak forth-- tak bardzo niskiego poziomu, dane prawie elektroniczne. Ale z tych matematycznych operacje w połączeniu z tym, co mówiliśmy wcześniej, reprezentacja danych jak zer i jedynek, można budować wszystko że komputer może zrobić dzisiaj, czy to tekstowe, graficzne, muzyczne, lub w przeciwnym wypadku. 

Więc to jest bardzo łatwo dostać zagubiony w chwastów szybko. I nie ma wiele składniowych wyzwania przy czym jeśli się najprostsze, najgłupsza literówek żadnego programu będzie działać w ogóle. I tak, zamiast przy użyciu język jak C rano, Myślałem, że byłoby więcej zabawy faktycznie zrobić coś bardziej wizualne, które zaś przeznaczony dla dzieci jest rzeczywiście doskonały manifestacją o rzeczywistej programowania language-- właśnie dzieje wykorzystywać zdjęcia zamiast tekstu do reprezentowania tych pomysłów. 

Więc kiedy rzeczywiście mieć Konto na scratch.mit.edu, kliknij przycisk Utwórz W lewej górnej części strony. I powinieneś zobaczyć jak środowisko jeden mam zamiar zobaczyć na ekranie tutaj. A my spędzić trochę Trochę czasu grając tutaj. Zobaczmy, czy nie możemy wszystkim rozwiązać niektóre Problemy ze sobą w następujący sposób. 

Więc to, co zobaczysz w obrębie tego environment-- i faktycznie po prostu pozwolić mi wstrzymać. Czy ktoś tu nie ma? Nie tutaj? OK. Więc pozwól mi zwrócić uwagę na kilka Właściwości tego środowiska. 

Więc w lewym górnym rogu ekranu, mamy mają etap Scratch jest, że tak powiem. Scratch jest nie tylko nazwa tego języka programowania; jest to również nazwa kota, który widać tam domyślnie w kolorze pomarańczowym. On jest na scenie, więc tak jak opisałem żółw wcześniej jako bycie w prostokątna biała środowiska pokładzie. Tego kota świat ogranicza się do końca do tego prostokąta up there górze. 

W międzyczasie, po prawej hand side tutaj, to tylko obszar skrypty, A tabula rasa, jeśli będzie. To gdzie będziemy pisać Nasze programy za chwilę. A cegiełki, że będziemy użyć do napisania tego program-- zagadkę sztuk, jeśli są will-- te właśnie tu, w środku, i są skategoryzowane przez funkcjonalność. Tak więc, na przykład, mam zamiar iść do przodu i wykazują co najmniej jedną z nich. Mam zamiar iść do przodu, a następnie kliknij kategoria sterowania maksymalnie górze. 

Więc to są kategorie up górze. Idę kliknij kategorię sterowania. Raczej będę kliknij Events kategorii, pierwszy na prowadzenie w góry. A jeśli chcesz podążać nawet jak to zrobić, jesteś bardzo mile widziane. Idę kliknąć i przeciągnąć tę Pierwszy z nich, "gdy zielona flaga kliknięciu". A potem mam zamiar upuść go po prostu z grubsza na szczycie moich pustych łupki. 

I co jest miłe o Scratch jest to, że ten kawałek układanki, kiedy zblokowane z drugiej układanki sztuk, zrobi dosłownie co te kawałki układanki powiedzieć robić. Tak więc, na przykład, Scratch ma rację Teraz w środku jego świata. Mam zamiar iść do przodu i wybrać Teraz, powiedzmy, w kategorii Motion, jeśli chcesz wykonać same-- kategorię Motion. A teraz muszę zauważyć całość pęczek puzzli tutaj że kolejny rodzaj robić to, co mówią. I zamierzam iść do przodu i przeciągnąć upuść bloku Przesuń w prawo tutaj. 

I zauważ, że tak szybko, jak można dostać blisko dna "zieloną flagą kliknął przycisk ", zawiadomienie Jak pojawi się biała linia, jakby to prawie magnetyczne, chce tam iść. Wystarczy puścić, a to przystawki razem i kształty będą pasować. I teraz można chyba prawie odgadnąć, gdzie jedziemy z tym. 

Jeśli spojrzeć na etapie Scratch tu i patrzeć na wierzchu, zobaczysz czerwone światło, znak stopu i zieloną flagę. I zamierzam iść do przodu i oglądać moje screen-- na chwilę, jeśli można. Idę kliknij Zielona flaga teraz, i przeniósł się co wydaje się być 10 kroków lub 10 pikseli, 10 kropki na ekranie. 

A więc nie tak ekscytujące, ale pozwól mi zaproponować nawet nie uczy tego, po prostu przy użyciu własnego własnego intuition-- let ja proponuję, aby dowiedzieć się, w jaki sposób dokonać Scratch spacer tuż przy scenie. Czy mu ustąpić po prawej stronie ekran, aż po prawej stronie. Podam chwilę lub tak, aby walczyć z tym. Czasami warto spojrzeć w innych kategoriach bloków. W porządku. Więc po prostu zakręcić, gdy mamy zielona flaga kliknięciu tutaj i przejść 10 kroków jest tylko instrukcja, za każdym razem kliknij zieloną flagę, co się dzieje? Dobrze, że mój program jest uruchomiony. Więc może to zrobić może 10 razy ręcznie ale czuje się trochę nieco hackish, że tak powiem, przy czym ja naprawdę nie jestem rozwiązywania problemu. Próbuję tylko raz i znowu i znowu i znowu aż rodzaju przypadek osiągnąć dyrektywę że chciał osiągnąć wcześniej. 

Ale wiemy z pseudokod wcześniej, że nie ma Pojęcie to w programowaniu pętli, robić coś znowu i znowu. I tak widziałem, że grono Ciebie sięgnął po kawałek układanki, co? Powtarzaj aż. Więc możemy coś zrobić jak powtarzać aż. I co pan powtórzyć, aż dokładnie? 

OK. I pozwól mi iść z takim, który jest nieco prostsze przez chwilę. Pozwólcie mi iść do przodu i to zrobić. Należy zauważyć, że, jak można mieć odkryto pod kontrolą, nie jest to powtórzenie bloku, który nie wygląda na to, że jest duży. Niewiele pokoju między tymi dwoma żółtymi liniami. Ale jak niektórzy z was mogą mieć Zauważyłem, jeśli przeciągnij i upuść, zauważyć, jak to rośnie do wypełnienia kształtu. 

I można nawet dopchać więcej. To będzie po prostu stale rosnąć, jeśli przeciągnij i unoszą się nad nim. A ja nie wiem, co jest Najlepszym tutaj, więc pozwól mnie przynajmniej powtórzyć pięć razy, na instancji, a następnie wrócić na scenę i kliknij zieloną flagę. A teraz zauważyć, że nie jest całkiem tam. 

Teraz niektórzy z was proponowany jako Victoria po prostu nie, powtórz 10 razy. I to na ogół robi zabrać go przez całą drogę, ale nie tam być bardziej wytrzymałe sposób niż zastanawianie się arbitralnie jak wiele ruchów zrobić? Co może być lepszego bloku niż powtórzyć 10 razy być? 

Tak, więc dlaczego nie zrobić czegoś na zawsze? A teraz pozwól mi przenieść ten kawałek układanki Wewnątrz i pozbyć się tego. Zauważmy teraz nieważne gdzie Scratch rozpoczyna się, idzie do brzegu. I na szczęście MIT, który sprawia, że ​​nowa, po prostu upewnia się, że nigdy znika całkowicie. Zawsze można chwycić ogonem. 

I tak intuicyjnie, dlaczego on ruszać? Co tu się dzieje? Wydaje się, że zatrzymał się, ale Następnie, jeśli mogę odebrać i przeciągnij Trzyma chcąc iść tam. Dlaczego? Zaprawdę, komputer jest dosłownie zrobi to, czego powiedzieć to zrobić. Więc jeśli to powiedziano wcześniej, wykonaj następujące rzeczy zawsze, przenieść 10 kroków, to się nie poddawać się i odchodzą dopóki nie uderzył w czerwony znak stopu i zatrzymać program w ogóle. 

Więc nawet jeśli nie to zrobić, jak mogłem dokonać Scratch szybciej po ekranie? Więcej kroków, prawda? Więc zamiast robić 10 na raz, dlaczego nie iść dalej i zmienić go to-- co byś propose-- 50? Więc teraz mam zamiar kliknąć zielony flaga i rzeczywiście idzie bardzo szybko. 

I to, oczywiście, jest po prostu przejawem animacji. Czym jest animacja? To jest po prostu pokazujące ludzkich a cała masa zdjęć wciąż naprawdę, naprawdę szybko. I tak, jeśli mamy tylko mówię żeby przenieść więcej kroków, jesteśmy tylko o efekt być Zmiana gdzie on jest na ekranie bardziej gwałtownie na jednostkę czasu. 

Teraz kolejnym wyzwaniem, które zaproponowałem było mieć go odbijają się od krawędzi. I nie wiedząc, co logiczna sztuk exist-- bo to jest w porządku jeśli nie dostać się do etap challenge-- co chcesz zrobić intuicyjnie? Jak mielibyśmy mu odbijać i dalej, pomiędzy lewym i prawym? 

Tak. Więc musimy jakąś stanu, i Wydaje się, że warunkowe, tak aby niejako w kategorii sterowania. Które z tych bloków mamy prawdopodobnie chcesz? Tak, może ", jeśli potem." Tak więc zauważyć, że wśród żółtych blokach Mamy tu, nie jest to "jeśli" czy ta "if, else" bloku, który będzie pozwalają nam podjąć decyzję, aby to zrobić czy to zrobić. I można je nawet gniazdo zrobić wiele rzeczy. Albo jeśli nie odeszłaś tu jeszcze idź do kategorii Sensing and-- zobaczmy, czy to tutaj. 

Więc co może być pomocne bloku tutaj wykryć, czy jest on poza sceną? Tak, zauważyć, że niektóre z tych bloków Możliwa jest parametryzacja, że ​​tak powiem. Mogą one być dostosowane rodzaju nie w przeciwieństwie do HTML wczoraj z atrybutami gdzie te atrybuty rodzaju dostosować zachowanie etykiety. Podobnie tutaj, mogę pobrać ten dotknięcia bloku i zmiana i zadać sobie pytanie, ty dotykania myszy wskaźnik jak kursora czy może dotykać krawędzi? 

Więc pozwól mi iść i to zrobić. Mam zamiar pomniejszyć przez chwilę. Pozwól mi pobrać ten kawałek układanki tutaj, to ten kawałek układanki, a ja zamierzam jumble im się przez chwilę. Mam zamiar przenieść tego, zmienić na dotykania krawędzi, a ja jadę do ruchu to zrobić. Więc oto kilka składników. Myślę, że mam wszystko, co chcę. 

Czy ktoś chciał zaproponować jak ja Może można podłączyć je od góry do dołu W celu rozwiązania tego problemu konieczności Scratch ruch od prawej do lewej do prawej, aby od lewej do prawej strony do lewej, z których każda Czas po prostu odbijając się od ściany? Co chcę robić? Który blok należy podłączyć do "Kiedy zielona flaga kliknięciu pierwszy"? 

OK, więc zacznijmy z "zawsze". To, co dzieje się wewnątrz następny? Ktoś inny. OK, przesuń kroki. W porządku. Więc co? Więc wtedy, gdy. I zauważył, mimo to wygląda wciśnięte razem mocno, będzie to tylko rosnąć, aby wypełnić. To po prostu wskoczyć gdzie chcę go. 

I co mogę umieścić między if a potem? Prawdopodobnie ", jeśli dotyka krawędzi". A informacja, ponownie, jest zbyt duży za to, ale będzie rosnąć do wypełnienia. A następnie skręcić o 15 stopni? Ile stopni? Tak, więc 180 będzie wirować mnie dookoła. Zobaczmy więc, czy mam takie prawo. Pozwól mi pomniejszyć. 

Pozwól mi przeciągnij Scratch górę. Więc trochę zniekształcone teraz, ale to jest w porządku. Jak mogę przywrócić go łatwo? Zamierzam trochę oszukiwać. Więc dodaję kolejny Blok, żeby była jasność. Chcę, żeby wskazywać 90 stopni w prawo domyślnie więc jestem po prostu będzie mu powiedzieć aby to zrobić programowo. I jedziemy. Wydaje się to zrobić. To trochę dziwne, bo on chodzenie do góry nogami. Nazwijmy to błąd. To pomyłka. Błąd to błąd w programie, a błąd logiczny, że ja, człowiek, wykonana. Dlaczego on idzie do góry nogami? Czy MIT zepsuć czy ja? 

Tak, to znaczy, że nie jest MIT wina. Dali mi kawałek układanki który mówi włączyć jakąś liczbę stopni. A na sugestię Wiktorii, Jestem obracając się o 180 stopni, która jest właściwym intuicji. Lecz On obrócił się o 180 stopni dosłownie oznacza obrót o 180 stopni, a to nie jest tak naprawdę co chcę, widocznie. Bo przynajmniej on jest w to dwuwymiarowy świat, tak naprawdę się dzieje zwrotnym odwrócić go do góry nogami. 

Pewnie chcą wykorzystać to, co blok Zamiast tego, na podstawie tego co tu widzisz? Jak możemy rozwiązać ten problem? Tak, więc możemy wskazać w przeciwnym kierunku. I rzeczywiście, nawet to Nie będzie za mało, ponieważ możemy tylko ciężka kod wskazując na lewo lub w prawo. 

Wiesz, co możemy zrobić? Wygląda na to mamy Blok o wygodę. Gdybym powiększyć, patrz coś, czego się tu podoba? Wygląda więc na to MIT posiada abstrakcji zbudowany tutaj. Blok ten wydaje się być równoważne do których inne bloki, w liczbie mnogiej? 

To jeden blok wydaje się być równoważne do tej całej trójki bloków że mamy tutaj. Tak więc okazuje się, mogę uprościć moje Program pozbywając się tego wszystkiego i po prostu umieścić to tutaj. A teraz jest jeszcze trochę buggy, i to jest w porządku teraz. Zostawimy to będzie. Ale mój program jest jeszcze prostsze, a to również byłaby reprezentatywna stanowi cel sam w programming-- to najlepiej zrobić swój kod jako proste, a możliwie jak najbardziej zwartych a jednocześnie jest tak odczytu, jak to możliwe. Nie chcemy, aby było tak zwięzłe że jest to trudne do zrozumienia. 

Należy jednak zauważyć, że zastąpiliśmy trzy bloki z jednym, i to prawdopodobnie jest dobrą rzeczą. Mam wydobywane dala pojęcie sprawdzenia, czy jesteś na granicy z jednego bloku. Teraz możemy bawić się z tego w rzeczywistości. To nie dodaje tyle wartości intelektualnej, lecz wartość zabawy. Mam zamiar iść do przodu i złapać ten dźwięk tutaj. Więc pozwól mi iść do przodu, a niech mnie zatrzymać program na chwilę. Zamierzam nagrać następujące, umożliwiając dostęp do mojego mikrofonu. 

No to ruszamy. Ała. Spróbujmy jeszcze raz. No to ruszamy. OK, nagrałem coś złego. No to ruszamy. Ała. Ała. W porządku. Teraz muszę się pozbyć tego. W porządku. 

Więc teraz mam zapis tylko "Ouch". Więc teraz mam zamiar iść naprzód i nazywają to "au". Mam zamiar wrócić do moich skryptów, a teraz Ogłoszenie jest ten blok, który się nazywa odtwarzać dźwięk "meow" lub odtwarzania dźwięku "au". Mam zamiar przeciągnąć tego, a gdzie należy umieścić to dla efektu komicznego? Tak, więc teraz to niby buggy, bo teraz to block-- zauważyć jak to ", jeśli na krawędzi, bounce "to rodzaj samowystarczalny. trzeba więc, aby to naprawić. Pozwólcie mi iść do przodu i to zrobić. Pozwól mi pozbyć się tego i wrócić do naszego pierwotnego, bardziej celowe funkcjonalności. Tak ", jeśli dotyka krawędzi, a następnie" Chcę obrócić, zgodnie z propozycją Victoria, 180 stopni. I chcę grać dźwięk "au" istnieje? 

Tak, zauważy to na zewnątrz że żółty blok. Więc to też byłoby bug, ale zauważyłem go. Więc mam zamiar przeciągnąć go tutaj i nota teraz jest wewnątrz "if". Tak więc "jeśli" jest tego rodzaju podobnego arm-like blot że tylko będzie robić to, co znajduje się w jej wnętrzu. Więc teraz, jeśli pomniejszyć przy ryzyko annoying-- 

Komputer: Ała, au, au. 

DAVID MALAN: I po prostu iść na zawsze. Teraz wystarczy, aby przyspieszyć rzeczy tu, pozwól mi iść do przodu i otworzyć, niech say-- mnie puścić do niektórych z własnej rzeczy z klasą. I pozwól mi otworzyć się, powiedzmy, w tym jeden wykonany przez jednego z naszych towarzyszy dydaktycznych kilka lat temu. Więc niektórzy z was mogą przypomnieć Ta gra z przeszłości, i to jest rzeczywiście niezwykłe. Mimo, że zrobiliśmy Najprostsze programy w tej chwili, rozważmy, co to w rzeczywistości wygląda. Pozwól mi uderzyć luz. 

Tak więc w tej grze, mamy żaba, i za pomocą strzałek keys-- on ma większe kroki niż remember-- Mam kontrolę nad tym żaby. A celem jest przedostać się zajęty Droga bez w samochodach. I niech see-- jeśli pójdę się tutaj, trzeba czekać na dziennik, aby zmieniać. To czuje się jak robaka. Jest to rodzaj błędu. W porządku. Jestem na to tutaj, tam, a następnie zachować dzieje, aż do uzyskania wszystkich żaby do lily pads. Teraz to może wyglądać bardziej skomplikowane ale spróbujmy przełamać to w dół psychicznie oraz ustnie do swoich bloków składowych. Więc to chyba logiczne kawałek, który jeszcze nie widział ale to reaguje na naciśnięcia klawiszy, rzeczy uderzę na klawiaturze. 

Więc nie ma chyba jakiś Blok, który mówi, jeśli klucz równa się, zrób coś z Scratch-- Może przenieść go 10 kroków w ten sposób. Jeśli naciśnięty zostanie przycisk DOWN, przenieść 10 kroków w ten sposób, albo lewy klawisz, przenieść 10 kroków w ten sposób, że 10 kroków. Ja wyraźnie odwrócił kota w żabę. Tak to tylko w przypadku gdy Kostium, ponieważ rozmowy Scratch it-- my tylko importowany obraz żaby. 

Ale co jeszcze się dzieje? Jakie inne linie kodu, jakie inne kawałki układanki zrobił Blake, nasze nauczanie towarzysz, zastosować w tym programie, jak widać? Co czyni wszystko move-- co programowania wybudować? 

Ruch, sure-- więc przesunąć blok, na pewno. A co to takiego bloku Przesuń wewnątrz, najprawdopodobniej? Tak, coś w rodzaju pętli, może zawsze blokować, może powtórzyć block-- powtarzać aż do bloku. A to, co czyni i dzienniki lilia poduszki i wszystko inne posunięcie w przód i w tył. To właśnie dzieje się w nieskończoność. 

Dlaczego niektóre z samochodów porusza się szybciej niż inni? Czym różni się o tych programach? Tak, prawdopodobnie niektóre z nich biorą więcej stopni na raz, a niektóre z nich mniej etapów naraz. I efekt wizualny Jest szybka kontra powolny. 

Jak myślisz, co się stało? Gdy dostałem żaba na drodze po drugiej stronie ulicy i rzeki na lily pad, coś Warto zauważyć stało. Co stało się tak szybko, jak to zrobiłem? Zatrzymało się. To żaba zatrzymany i Dostałem drugą żabę. Więc co konstrukt musi być wykorzystywane tam, co funkcja? 

Tak, więc jest jakaś "If" uzależnić się tam, too. I okazuje out-- nie widzieliśmy this-- ale nie ma tam innych bloków, które Można powiedzieć, jeśli dotykają Inną rzeczą, na ekranie jeśli dotyka lily pad ", a następnie". I wtedy właśnie, kiedy aby pojawić się druga żaba. Dlatego, mimo że ta gra jest z pewnością bardzo stary, choć na pierwszy rzut oka jest tak wiele dzieje on-- i Blake Nie to wzbudzać w ciągu dwóch minut, prawdopodobnie zabrał mu kilka godzin, aby stworzyć tę grę na podstawie jego pamięci lub filmy Od wersji przeszłości za nim. Ale wszystkie te małe rzeczy dzieje się na ekranie w izolacji sprowadzają się do nich bardzo prosta constructs-- ruchy lub oświadczenia jak omówiliśmy, pętle i warunki i to wszystko. Istnieje kilka innych bardziej wyszukane funkcje. Niektóre z nich są czysto estetyczne i akustyczne, jak dźwięki po prostu grał. Jednak dla większości, mają w tym języku, scratch, wszystkie podstawowe cegiełki to ty mieć w C, Java, JavaScript, PHP, Ruby, Python, i wielu innych językach. Wszelkie pytania dotyczące zera? W porządku. Nie będziemy więc zanurkować głębiej do zera, jeśli jesteś mile widziany w ten weekend, zwłaszcza jeśli masz dzieci lub siostrzenice i siostrzeńcy i takie, aby wprowadzić je do zera. To rzeczywiście cudownie zabawny środowiska z, a jego autorzy twierdzą, bardzo wysokie sufity. Nawet mimo tego, że zaczęło się od bardzo szczegółowe niskopoziomowe, można naprawdę sporo z tym, co jest być może demonstracja dokładnie to. 

Ale bądźmy teraz przejść do nieco bardziej wyszukane problemy, jeśli chcesz, znany jako "poszukiwanie", a "Sortowania", bardziej ogólnie. Mieliśmy to książka telefoniczna earlier-- tutaj drugi tylko dla discussion-- że byliśmy w stanie wyszukiwać bardziej skutecznie, ponieważ znaczącej założeniu. I żeby była jasność, co Założenie było takie, że co przy przeszukiwaniu tej książce telefonicznej? Mike Smith był w książka telefoniczna, choć byłaby w stanie obsłużyć scenariusz bez niego tam, jeśli tylko zatrzyma się przedwcześnie. Książka jest alfabetyczna. I to jest bardzo hojny Założenie, ponieważ Oznacza someone-- jestem miły cięcia narożnik, jak ja się szybciej, ponieważ ktoś inny tego nie zrobił dużo ciężkiej pracy dla mnie. 

Ale co wtedy, gdy telefon Książka została nieposortowane? Może Verizon dostaje leniwy, po prostu wyrzucił Nazwy i numery każdego z nas tam może w kolejności, w jakiej przystąpił do usług telefonicznych. A ile czasu zajmie mi znaleźć kogoś takiego jak Mike Smith? 1000 strona telefonu book-- ilu strony muszę przejrzeć? 

Wszyscy. Jesteś rodzaju pecha. Dosłownie trzeba patrzeć na każde Strona, jeśli jest tylko książka telefoniczna losowo klasyfikowane. Możesz mieć szczęście i znaleźć Mike na pierwszej stronie, bo Był to pierwszy Klient zamówić usługę telefoniczną. Ale mógł być ostatni, też. 

Więc losowego nie jest dobre. Więc załóżmy, że mamy do sortowania książka telefoniczna lub ogólnych danych sortowania że mamy dano. Jak możemy to zrobić? 

Dobrze, niech po prostu spróbować prosty przykład tutaj. Pozwólcie mi iść do przodu i wrzucić Kilka liczb na planszy. Załóżmy, że mamy numery są powiedzmy, cztery, dwa, jeden i trzy. I, Ben uporządkować te numery dla nas. 

Ok dobrze. Jak to zrobiłeś? W porządku. Więc zacząć od najmniejszych Wartość i najwyższa, i to jest bardzo dobra intuicja. I uświadomić sobie, że ludzie są faktycznie dość dobry w rozwiązywaniu problemów w ten sposób, co najmniej gdy dane jest stosunkowo mała. Jak tylko zaczniesz mieć setki numerów, tysiące numerów, miliony numerów Ben pewnie nie mógł go dość, że szybko, przy założeniu, że luki w liczbach. Dość łatwo policzyć do miliona inaczej, po prostu czasochłonne. 

Więc algorytm brzmi jak Ben wykorzystane dopiero teraz było poszukiwanie najmniejszej liczby. Więc mimo, że ludzie mogą podjąć w wielu informacji wizualnej, komputer jest rzeczywiście trochę bardziej ograniczone. Komputer może tylko spojrzeć na jeden bajt na raz a może cztery bajty przy time-- w tych dniach może 8 bajtów przy time-- ale bardzo mała liczba Liczba bajtów w danym czasie. 

Tak więc biorąc pod uwagę, że naprawdę mamy cztery oddzielne wartości here-- i można myśleć o Ben jako posiadające Przesłony na gdyby komputer takie że nie widzi niczego innego niż jeden numer przy time-- więc generalnie zakłada, podobnie jak w Angielski, będziemy czytać od prawej do lewej. Więc pierwsza liczba Ben pewnie wyglądał co było czterech, a następnie bardzo szybko sobie sprawę, że jest to dość duży number-- pozwól mi szukać dalej. 

Nie ma dwóch. Poczekaj chwilę. Nimi jest mniejsza niż cztery. Idę do zapamiętania. Dwa to obecnie najmniejszy. Teraz jedno-, że nawet lepiej. To jeszcze mniejszy. Idę zapomnieć o dwóch i po prostu pamiętam teraz. 

A mógł przestać patrzeć? Cóż, mógł na podstawie na tej informacji, ale lepiej wyszukiwanie reszta listy. Bo co, jeśli zera było w liście? Co zrobić, jeśli negatywny było w liście? Wie tylko, że jego odpowiedź jest poprawna, jeśli jest on wyczerpujący Sprawdziłem całą listę. Więc patrzymy na resztę tego. Three--, że to strata czasu. Masz pecha, ale byłem nadal poprawne, aby to zrobić. I tak teraz on przypuszczalnie wybrany najmniejszy numer i po prostu umieścić go na początku listy, jak będę tu robić. Teraz to, co robiłeś w przyszłym, choć nie myśleli o nim prawie do tego stopnia? Powtórz ten proces, więc pewnego rodzaju pętli. Jest znanym pomysłem. Więc tutaj jest cztery. To obecnie najmniejszy. To kandydat. Nigdy więcej. Teraz widziałem dwa. To kolejna najmniejszy element. Three-- to nie jest mniejsza, więc Teraz Ben może wyrwać dwa. 

A teraz powtórzyć proces i Oczywiście trzy zostaje wyciągnięta dalej. Powtórz ten proces. Cztery zostanie wyciągnięta. A teraz jesteśmy na liczbach, więc lista musi być sortowane. 

I rzeczywiście, jest to formalny algorytm. Informatyk będzie Nazywamy to "wybór rodzaju" idea bycia Sortowanie listy iteratively-- ponownie i znowu wybierając najmniejsza liczba. I co jest ładne o to to jest po prostu tak cholernie intuicyjne. To takie proste. I można powtórzyć ten sam Operacja ponownie. To proste. 

W tym przypadku była szybka, ale Jak długo trzeba rzeczywiście wziąć? Zróbmy to wydawać i czuję się trochę bardziej uciążliwe. Tak jeden, dwa, trzy, cztery, pięć sześć siedem, osiem, dziewięć, 10, 11, 12, 13, 14, 15, 16-- dowolną liczbą. Chciałem tylko bardziej ten Czas niż tylko czterech. Więc jeśli mam całość pęczek liczb now-- go nawet nie ma znaczenia co are-- LET'S myśleć o tym, co to Algorytm jest bardzo podobne. 

Załóżmy, że istnieją jakieś numery. Ponownie, nie ma znaczenia, co są, ale są przypadkowe. Ja zastosowaniu algorytmu Bena. Muszę wybrać najmniejszą liczbę. Co ja robię? I mam zamiar fizycznie zrób to ten czas działania to. Szuka, szuka, szuka, szuka, szuka. Tylko do czasu mogę Zakończenie puszki listy Zdaję sobie sprawę, najmniejsza liczba była dwa i tym razem. Jeden nie jest na liście. Więc odłożyć dwa. 

Co mam teraz zrobić? Szuka, szuka, szuka, szuka. Teraz znalazłem numer siedem, ponieważ nie ma luki w tych numbers-- ale po prostu arbitralne. W porządku. Więc teraz mogę odłożyć siedem. Patrząc patrząc, patrząc. 

Teraz jestem zakładając Oczywiście, że Ben nie mają dodatkowy RAM, dodatkowe pamięć, ponieważ, oczywiście, Patrzę na ten sam numer. Z pewnością mógłbym pamiętał Wszystkie z tych numerów i to absolutnie prawdziwe. Ale jeśli Ben pamięta wszystko numerów widział, że nie ma rzeczywiście wykonane istotnego postępu bo już ma Możliwość wyszukiwania za pośrednictwem numerów na płycie. Pamiętając wszystkie z Liczby nie pomoże, bo może jeszcze jak komputer tylko patrzeć, jakie powiedział jeden numer na czas. Więc nie ma swego rodzaju oszustwo tam, że można wykorzystać. 

Tak więc w rzeczywistości, tak jak ja utrzymać przeszukiwania listy Dosłownie trzeba po prostu wracamy tam iz powrotem przez to, wyrywanie następna najmniejsza liczba. I jak można wywnioskować rodzaj z moich głupich ruchów, to po prostu staje się bardzo nużące bardzo szybko, i wydaje mi się, że będzie z powrotem i powrotem, tam iz powrotem, całkiem sporo. Teraz aby być uczciwym, nie muszę iść aż tak dobrze, niech see-- aby być uczciwym, Nie trzeba chodzić dość jak wiele kroków za każdym razem. Ponieważ, oczywiście, jak wybieranie numerów z listy, Pozostała lista jest coraz krótszy. 

A więc pomyślmy o ile kroków jestem naprawdę traipsing za każdym razem. W pierwszej sytuacji mieliśmy 16 numerów, i tak maximally-- niech po prostu zrobić to za discussion-- Musiałem patrzeć przez 16 Numery znaleźć najmniejszy. Ale kiedy wyrwana najmniejsza liczba, jak długo był pozostałą listę, oczywiście? Tylko 15. Więc ile numerów zrobił Ben czy mam do zapoznania się za drugim razem? 15, po prostu iść i znaleźć najmniejszy. Ale teraz, oczywiście, lista jest, Także mniejsze niż to było wcześniej. Tak jak wiele kroków ja trzeba wziąć następnym razem? 14 i 13, a potem 12, a także kropki, kropka, kropka, dopóki pozostaje mi tylko jedno. Więc teraz informatyk będzie zapytać, dobrze, co robi, że wszyscy równi? To faktycznie równa konkretne numer, który mogliśmy pewnością zrobić arytmetycznie, ale chcemy rozmawiać o wydajności algorytmów trochę bardziej formulaically, niezależne od tego jak długo lista jest. 

I tak wiesz, co? Jest to 16, ale tak jak powiedziałem wcześniej, niech po prostu zadzwonić do rozmiaru problemu n, gdzie n jest pewną liczbę. Może to jest 16, może to trzy, może to milion. Nie wiem Nie obchodzi mnie to. Co naprawdę chcę to formuła, że ​​mogę użyć do porównania tego algorytmu w stosunku do innych algorytmów że ktoś może twierdzić, są lepsze lub gorsze. 

Tak więc okazuje się, a tylko ja wiem to z podstawówki, że to faktycznie działa się tak samo coś takiego jak n na n plus jeden na dwóch. I to dzieje się równać, z Oczywiście, n oraz n kwadratu nad nimi. Więc gdybym chciał formułę dla ilu krokach zajmowali się patrząc na wszystko od raz po raz te numery i znowu, i znowu, powiedziałbym, to n do kwadratu oraz n nad nimi. Ale wiesz co? To po prostu wygląda niechlujnie. Po prostu naprawdę chcą ogólne poczucie rzeczy. A może pamiętacie z liceum, że istnieje jest pojęcie najwyższego terminu zamówienia. Który z tych terminów, n kwadratu, z N, albo połowę, ma największy wpływ na przestrzeni czasu? Im większe n dostaje, co Spośród nich większość spraw? 

Innymi słowy, jeśli podłączę na milion, n do kwadratu będzie najprawdopodobniej współczynnik wyróżniającym, bo milion razy Sam jest dużo większy niż plus jeden dodatkowy milion. Więc wiesz co? To jest taki cholernie duża Numer jeśli kwadrat numer. To naprawdę nie ma znaczenia. Jesteśmy po prostu będzie krzyż, który się i zapomnieć o nim. I tak informatykiem powiedzieliby że skuteczność tego algorytmu jest rzędu n squared-- Mam na myśli naprawdę zbliżenia. To jest rodzaj grubsza n do kwadratu. W miarę upływu czasu, tym większa i większe n dostaje, ten jest dobrym szacunkiem za to, co efektywności lub braku skuteczności tego algorytmu w rzeczywistości. I czerpać to, oczywiście, od rzeczywiście robi matematyki. Ale teraz jestem po prostu macha moje ręce, bo po prostu chcą ogólny sens tego algorytmu. 

Tak więc stosując tę ​​samą logikę, w międzyczasie, rozważmy inny algorytm już spojrzał at-- przeszukiwanie liniowe. Gdy szukałem dla book-- telefonu Nie sortowania go, szukając przez book-- telefonu nam powtarzał, że to 1000 kroków lub 500 kroków. Ale załóżmy, że uogólnienia. Jeśli istnieje n stron w książka telefoniczna, jaka jest czas pracy lub Sprawność przeszukiwanie liniowe? To na zlecenie ile kroków do znalezienia Mike Smith stosując przeszukiwanie liniowe, The Pierwszy algorytm lub nawet drugi? 

W najgorszym przypadku, Mike na końcu książki. Więc jeśli książka telefoniczna ma 1000 stron, mówiliśmy po raz ostatni, w najgorszym przypadku, może minąć mniej więcej jak wiele stron, aby znaleźć Mike? Podobnie jak 1000. Jest to górna granica. Jest to najgorszy z możliwych sytuacji. Ale znowu, jesteśmy odejście z numerów, takich jak 1000 teraz. To jest po prostu brak. 

Więc co jest logiczny wniosek? Znalezienie Mike w telefonie Książka, która zawiera strony n może podjąć, w najgorszym przypadku, ile kroków na zlecenie n? I rzeczywiście komputer Naukowiec powie że czas uruchomiona albo wydajności lub efektywności lub nieefektywność, algorytmu podobnego poszukiwanie linear jest rzędu n. I możemy zastosować te same Logika przekraczania coś a ja po prostu nie do sekundy Algorytm mieliśmy z książki telefonicznej, gdzie udaliśmy dwóch stron na raz. 

Więc 1000 strona książka telefoniczna może zabierze nas strona 500 obrotów, plus jeden jeśli zawrócić trochę. Więc jeśli książka telefoniczna zawiera strony N, ale robimy dwie strony na raz, to mniej więcej co? N na dwie części, tak, aby jak n nad nimi. Ale zrobiłem dochodzić Chwilę temu, że n nad two-- że niby takie same, jak tylko n. To tylko czynnik stały, informatycy powie. Skupmy się tylko na zmienne, really-- Największe zmienne w równaniu. 

szukaj więc liniowa, czy odbywa się jedną Strona naraz lub dwie strony na raz, jest rodzajem zasadniczo taka sama. To wciąż rzędu n. Ale twierdził wcześniej z moim obrazie że trzeci algorytm nie liniowy. To nie była prosta. To było to, że linia krzywa, a Formuła nie algebraiczne było to, co? Log n- więc logarytm przy podstawie dwa n. I nie musimy iść do zbyt dużo szczegółów na logarytmów dziś ale większość informatycy nie chciał nawet powiedzieć, jaka jest podstawa. Bo to wszystko jest po prostu stałe czynniki, by tak rzec, zaledwie nieznaczne różnice liczbowe. I tak będzie to bardzo często sposób szczególnie formalnego komputera Naukowcy na pokładzie lub programiści na tablicy argumentując, które faktycznie Algorytm będą używać albo co sprawność z ich algorytm jest. 

I nie jest koniecznie coś omówić w jakikolwiek sposób bardzo szczegółowy, ale dobry programista to ktoś który posiada solidną, formalne tło. On jest w stanie rozmawiać jesteś w tego rodzaju sposób i rzeczywiście zrobić argumenty jakościowe jak dlaczego jeden lub algorytm jeden kawałek oprogramowania jest lepsze w pewnym stopniu do drugiej. Bo z pewnością może wystarczy uruchomić program, jedna osoba i policzyć liczbę sekund trzeba, aby uporządkować kilka liczb, i można uruchomić niektórych Program Inne osoby i policzyć liczbę sekund trwa. Ale jest to bardziej ogólny sposób, że można wykorzystać do analizy algorytmów, jeśli chcesz, tylko na papier lub tylko werbalnie. Nawet nie uruchamiając go bez nawet nie próbuje wejść przykładowych można po prostu rozumieć przez nią. I tak z zatrudnieniem dewelopera lub jeśli mając mu lub jej rodzaju twierdzą ciebie dlaczego ich algorytm ich sekret Sos do wyszukiwania miliardy stron WWW dla Twojej firma jest lepsza, to są rodzaje argumentów one powinny najlepiej być w stanie dokonać. Albo przynajmniej są takie rzeczy które pojawiały się w dyskusji na przynajmniej w bardzo formalnej dyskusji. W porządku. Więc Ben zaproponował coś nazywa wybór sortowania. Ale mam zamiar zaproponować, że nie ma inne sposoby na zrobienie tego, too. Co mi się nie bardzo lubię o algorytmie Bena jest to, że szedł, albo po mnie chodzić tam iz powrotem tam iz powrotem iz powrotem. Co będzie, jeśli zamiast tego było zrobić coś w tych liczbach tutaj i ja się po prostu do czynienia z każdym Numer z kolei jak ja dał je? 

Innymi słowy, oto moja lista numerów. Czterech, jeden, trzy, dwa. A ja zamierzam wykonać następujące czynności. Mam zamiar wstawić numery której należą raczej niż wybierając je jeden na raz. Innymi słowy, tu jest numer cztery. 

Oto moja lista oryginału. I mam zamiar utrzymać zasadniczo nowa lista tutaj. Więc to jest stara lista. Jest nowa lista. Widzę numer cztery pierwsze. Moja nowa lista jest początkowo pusta, tak to jest trywialnie sprawa że cztery obecnie dobierane listę. Po prostu biorę numer mam podane, a ja wprowadzenie go w mojej nowej listy. 

Czy to nowa lista posortowana? Tak. To głupie, bo jest tylko jeden elementem, ale to absolutnie sortowane. Nic się nie na miejscu. To ciekawe, ten algorytm, kiedy przejść do następnego kroku. 

Teraz mam jeden. Tak jeden, oczywiście, należy u początku lub na końcu tej nowej liście? Początek. Więc muszę popracować teraz. Byłem przy niektórych Swobody z moim markerem po prostu rysunek rzeczy gdzie chcę je, ale to naprawdę nie jest dokładna w komputerze. Komputer, jak wiemy, ma RAM lub Random Access Memory, i to jest jeden bajt i kolejny bajt, a drugi bajt. A jeśli masz gigabajt RAM, masz miliard bajtów, ale są fizycznie w jednym miejscu. Nie można po prostu przenieść rzeczy wokół rysując go na pokładzie gdziekolwiek chcesz. Więc jeśli moja nowa lista ma Cztery miejsca w pamięci, niestety jest cztery już w niewłaściwym miejscu. 

Tak, aby wstawić numer jeden Nie można po prostu wyciągnąć go tutaj. To miejsce pamięci nie istnieje. To byłoby oszustwo, i byłem oszustwo obrazowo na kilka minut tutaj. Tak naprawdę, jeśli chcę, aby umieścić je tutaj, Mam tymczasowo skopiować cztery a następnie umieścić jeden tam. 

To dobrze, to jest prawidłowe, to technicznie możliwe, ale uświadomić sobie, że to dodatkowa praca. Nie wystarczy umieścić numer na swoim miejscu. Po raz pierwszy musiał przesunąć numer, a następnie umieścić go w miejscu, więc rodzaj podwoiła mój ilości pracy. Miejcie to na uwadze. 

Ale jestem teraz zrobić z tym elementem. Teraz chcę, aby pobrać numer trzy. Jeżeli, oczywiście, to należy? Pomiędzy. Nie mogę się już oszukać i po prostu umieścić go tam, bo znowu tej pamięci w lokalizacjach fizycznych. Więc muszę skopiować cztery i umieścić trzy tutaj. Nic takiego. To tylko jeden dodatkowy krok again-- czuje się bardzo tanie. 

Ale teraz przejść do dwóch. Dwa oczywiście należy tutaj. Teraz można rozpocząć, aby zobaczyć, jak praca może piętrzyć. I co teraz mam zrobić? Tak, muszę przenieść cztery, Mam następnie skopiować trzy, i teraz mogę wstawić dwa. A z tym jest haczyk Algorytm, co ciekawe, jest to, że załóżmy, że mamy bardziej ekstremalne przypadku, gdy jest to powiedzmy, osiem, siedem, sześć, pięć, cztery, trzy, dwa, jeden. Jest to w wielu kontekstach najgorszy scenariusz, bo absolutnie znakomite rzeczy jest dosłownie tyłu. 

To naprawdę nie ma wpływa algorytm Bena, bo w wyborze Bena sort ma zamiar utrzymać tam iz powrotem przez liście. A ponieważ był zawsze szuka całej listy pozostały, to nie ma znaczenia gdzie elementy. Ale w tym przypadku z moim wkładania approach-- spróbujmy. 

Tak jeden, dwa, trzy, cztery, pięć, sześć, siedem, osiem. Jeden dwa trzy cztery, pięć, sześć, siedem, osiem. Mam zamiar wziąć osiem, i gdzie mogę umieścić go? Cóż, na początku mojej listy, ponieważ ta nowa lista jest sortowana. A ja je skreślić. 

Gdzie mam umieścić siedem? Cholernie go. Trzeba tam pojechać, więc Muszę zrobić jakieś kopiowanie. A teraz siedem idzie tutaj. Teraz przechodzimy do sześciu. Teraz jeszcze więcej pracy. 

Osiem musi udać się tutaj. Siedem musi udać się tutaj. Teraz sześć może udać się tutaj. Teraz weź pięć. Teraz osiem musi odejść tu siedem musi iść tutaj, sześć ma iść tutaj, i teraz pięć i powtórzyć. I jestem prawie przesuwając go stale. 

Tak na końcu tego algorithm-- we''ll nazwać wstawiania sort-- rzeczywistości ma dużo pracy, też. To jest po prostu inna rodzaj pracy niż Ben. Prace Bena miał mnie dzieje tam iz powrotem przez cały czas, wybierając następna najmniejsza Element ponownie. Więc było to bardzo wizualne rodzaj pracy. 

Ten drugi algorytm, który jest wciąż correct-- będzie dostać pracę done-- po prostu zmienia się ilość pracy. Wygląda na to, że jesteś na początku oszczędności, bo jesteś po prostu czynienia z każdym elementem z góry bez chodzenia wszystkim droga przez liście, jak Ben. Jednak problemem jest to, w szczególności w tych szalone przypadki, w których to wszystko wstecz, jesteś po prostu rodzaj odroczenie ciężką pracę aż trzeba naprawić swoje błędy. 

A więc jeśli można to sobie wyobrazić osiem i siedem i sześć i pięć a następnie cztery i trzy i dwa przesuwając się przez liście, my właśnie zmienił rodzaj pracy robimy. Zamiast robić to u początku mojego iteracji Robię go u koniec każdej iteracji. Tak więc okazuje się, że ten algorytm, Także ogólnie nazywane Sortowanie przez wstawianie, Jest również na zlecenie n do kwadratu. To rzeczywiście nie jest lepsza, nie lepiej w ogóle. 

Jednakże, istnieje Trzecie podejście Chciałbym zachęcić nas do zastanowienia się, która jest następująca. Więc przypuszczam moją listę, dla uproszczenia znowu wynosi cztery, trzy, two-- tylko cztery numery. Ben miał dobrą intuicję, dobra intuicja ludzka wcześniej, przez którą stała cała listy eventually-- Sortowanie przez wstawianie. I namówił nas wzdłuż. Ale rozważmy Najprostszym sposobem, aby naprawić tę listę. 

Ta lista nie jest posortowana. Czemu? W języku angielskim, dlaczego nie faktycznie sortowane. Co to znaczy nie być sortowane? 

Student: To nie jest sekwencyjnym. 

DAVID MALAN: Nie sekwencyjnym. Daj mi przykład. 

Student: Umieść je w kolejności. 

DAVID MALAN: OK. Daj mi bardziej konkretny przykład. 

Student: porządku rosnącym. DAVID MALAN: Nie porządku rosnącym. Być bardziej precyzyjne. Nie wiem, co masz na myśli rosnąco. Co jest nie tak? 

Student: Najmniejszy z Liczby nie znajduje się w pierwszej pozycji. 

DAVID MALAN: Najmniejsza liczba użytkownika nie w pierwszym polu. Bądź bardziej dokładny. Zaczynam łapać dalej. Liczymy, ale co jest w porządku tutaj? 

Student: numeryczna sekwencja. DAVID MALAN: numeryczna sekwencja. rodzaj każdego człowieka, jakim jest utrzymanie to here-- bardzo wysoki poziom. Wystarczy dosłownie mi powiedzieć, co jest źle jak pięć-letniego sił. 

Student: plus jeden. 

DAVID MALAN: Co to jest? 

Student: plus jeden. 

DAVID MALAN: Co masz na myśli plus jeden? Daj mi inny pięć lat. Co się stało, mamo? Co się stało, tato? Co masz na myśli to nie jest klasyfikowane? 

Student: To nie jest właściwe miejsce. 

DAVID MALAN: Co Nie we właściwym miejscu? 

Student: Cztery. DAVID MALAN: OK, dobra. Więc cztery nie jest tam, gdzie powinien być. W szczególności, czy to prawda? Cztery i pierwszy dwa numery rozumiem. Czy to jest poprawne? Nie, oni są w porządku, prawda? W rzeczywistości, że teraz o komputera też. Może to być może patrzeć tylko na jednym, być może dwie rzeczy na once-- a właściwie tylko jedno w czasie, ale może przynajmniej spojrzeć na jednej rzeczy, to Następną rzeczą, tuż obok niego. 

Więc to są w porządku? Oczywiście nie. Więc wiesz co? Dlaczego nie bierzemy dziecko Kroki rozwiązywania tego problemu zamiast robić te fantazję algorytmy, takie jak Ben, gdzie on rodzaj mocowania go przelotowego listy zamiast robić to, co zrobiłem, gdzie I właśnie niby naprawić go jak idziemy? Miejmy tylko dosłownie rozbić Pojęcie order-- porządku numerycznym, nazwać cokolwiek want-- do tych porównań parami. 

Cztery i jeden. Czy to prawidłowa kolejność? Warto więc naprawić. Jeden i cztery, a następnie musimy po prostu skopiować to. Dobra, dobra. Poprawiłem jeden i cztery. Trzy i dwa? Nie. Niech moje słowa pasuje palce. Cztery i trzy? 

To nie jest w porządku, więc mam zamiar zrobić jeden, trzy, cztery, dwa. Ok dobrze. Teraz cztery i dwa? Musimy rozwiązać ten problem, too. Tak jeden, trzy, dwie, cztery. Więc to jest klasyfikowane? No, ale to jest bliżej sortowane? 

To jest dlatego, że ten ustalony pomyłka, naprawiliśmy ten błąd, i naprawiliśmy ten błąd. Więc zapewne stały trzy błędy. Jeszcze nie naprawdę wyglądają sortowane, ale jest obiektywnie bliżej brakowanych ponieważ stałe niektóre z tych błędów. 

I co teraz mam zrobić? I niby osiągnął koniec listy. I wydawało się, że ustalona wszystkie błędy, ale nie. Ponieważ w tym przypadku, niektóre numery mogło pęcherzykami bliżej do innych numerów nadal są poza kolejnością. Więc zróbmy to jeszcze raz, i będę po prostu zrobić to w miejscu tym razem. Jeden i trzy? W porządku. Trzy i dwa? Oczywiście nie, więc zmieńmy to. Tak więc dwa, trzy. Trzy i cztery? A teraz po prostu być Szczególnie pedantyczne tutaj. Jest klasyfikowane? Wy, ludzie wiedzą, że jest posortowana. 

powinienem spróbować ponownie. Więc Olivia proponuje spróbować ponownie. Czemu? Ponieważ komputer nie ma luksus naszych ludzkich oczu po prostu spoglądając back-- OK, skończę. Jak ustalić, czy komputer że lista jest teraz posortowana? Mechanicznie. 

muszę przejść przez po raz kolejny, i tylko wówczas, gdy nie rób / znaleźliśmy żadnych błędów mogę następnie zawrzeć jak komputer, yep, jesteśmy dobrze iść. Tak więc pierwszy i drugi, i dwa trzy, trzy i cztery. Teraz mogę powiedzieć, że to definitywnie sortowane, bo wprowadzono żadnych zmian. Teraz byłoby to błąd i po prostu głupie, gdybym, komputer, zadawane te same pytania raz oczekiwać różnych odpowiedzi. nie powinno się zdarzyć. 

A więc teraz lista jest sortowana. Niestety, czasu prowadzenia algorytm ten jest również n do kwadratu. Czemu? Ponieważ masz numery n, aw najgorszym przypadku trzeba przenieść numery n n razy, bo trzeba iść dalej Powrót do sprawdzenia i ewentualnie naprawić te numery. I możemy zrobić więcej analiza formalna, too. 

Więc to wszystko powiedzieć podjęliśmy trzy różne sposoby, jeden z nich natychmiast intuicyjne przy bat z Benem do mojego proponowane umieszczenie porządek do tego gdzie rodzaj zapominać las na pierwotnie drzew. Ale jeśli zrobić krok do tyłu, voila, mamy ustalone pojęcie sortowania. Tak to jest, śmiem twierdzić, niższy poziom może niż niektóre z tych innych algorytmy, ale spójrzmy prawdzie sprawdzić, czy nie możemy wizualizować ich drodze tego. 

Więc to jest jakiś ładny Oprogramowanie, że ktoś napisał użyciu kolorowych pasków to zamiar wykonać następujące czynności za nas. Każdy z tych prętów stanowi liczbę. Wyższy pasek, tym większa liczba, mniejszy bar, Im mniejsza liczba. Więc idealnie chcemy piękny piramidę gdzie zaczyna się mały i robi się duży, a to oznaczałoby, że Te paski są klasyfikowane. Więc mam zamiar iść do przodu i wyboru, na przykład algorytm Bena first-- wyboru sortowania. 

I zauważyć, co robi. Sposób, w jaki wybrałeś do wizualizację tego algorytmu jest to, że podobnie jak ja chodząc mojej liście, Ten program idzie poprzez liście numerów podkreślając w różowym każdego Numer że to patrzy. A co wydarzy się teraz? 

Najmniejsza liczba, która I albo Ben znalazł się nagle zostaje przeniesiona do początku listy. I zauważ zrobili eksmisji numer, który był tam, i to jest całkowicie w porządku. I nie dostać się do tego poziomu szczegółowości. Ale musimy umieścić liczba gdzieś więc po prostu przeniósł go do open spot, który został utworzony. Więc mam zamiar przyspieszyć ten w górę, ponieważ w przeciwnym wypadku Szybko staje się bardzo uciążliwe. Animacja speed-- tam idziemy. Więc teraz sama zasada Byłem stosowania, ale może zacząć czuć się algorytm, jeśli woli lub zobaczyć trochę jaśniej. I to algorytm daje efekt Wybór następnego najmniejszy element, więc masz zamiar zacząć zobaczyć to na ziemi się po lewej stronie. I na każdej iteracji, jak ja Proponuje, robi się trochę mniej pracy. To nie musi przejść całą drogę z powrotem do lewego końca listy, dlatego, że już zna te są klasyfikowane. Więc to rodzaj czuje się jak to jest przyspieszenie, choć każdy krok jest biorąc taką samą ilość czasu. Jest po prostu mniej etapów pozostałe. I teraz można poczuć rodzaju Algorytm oczyszczenie koniec, a nawet teraz jest posortowana. 

Więc Sortowanie przez wstawianie jest wszystko zrobione. Muszę ponownie losowy tablicy. A może po prostu zauważyć, że utrzymać go losowanie, a my przybliżenie To samo podejście, Sortowanie przez wstawianie. Pozwól mi go spowolnić tutaj. Zacznijmy że ponad. Zatrzymaj się. 

Pomińmy cztery. No to jedziemy. Losowy, one tablicę. I tu go-- Sortowanie przez wstawianie. Grać. Zauważ, że ma do czynienia ze sobą Element napotka od razu, jeśli jednak przynależy złe miejsce zawiadomienie wszystkie prace, które ma się wydarzyć. Musimy zachować przesunięcie więcej i więcej elementów, aby zrobić miejsce dla jednej chcemy wprowadzić w życie. 

Dlatego skupiamy się na lewy koniec tylko listy. Zauważ, że nawet nie spojrzał at-- my nie podkreślono w różowej niczym w prawo. Jesteśmy po prostu do czynienia z problemy jak idziemy, ale my tworzymy dużo pracować dla siebie miejscu. A więc jeśli to przyspieszyć Teraz, aby przejść do końca, ma inny klimat do niego rzeczywiście. To jest po prostu skupienie się na lewym końcu, ale robi trochę więcej pracy jako needed-- rodzaj wygładzania rzeczy powyżej, naprawie, ale ostatecznie do czynienia z każdy element pojedynczo aż dojdziemy dobrze the--, mamy Wszyscy wiemy, jak to się skończy, więc jest to trochę rozczarowująca może. 

Ale lista w end-- spoiler-- ma być sortowana. Więc spójrzmy na jeden ostatni. Nie możemy teraz przejść dalej. Prawie jesteśmy na miejscu. Dwa iść, jeden iść. I voila. Doskonały. 

Więc teraz zróbmy jeden ostatni, ponowne losowanie z bubble rodzaju. I tutaj odnotować, szczególnie jeśli go zwolnić w dół, ten nie zachowuje swooping wskroś. Należy jednak zauważyć, że po prostu sprawia, parami comparisons-- rodzaju lokalnych rozwiązań. Ale jak tylko dostać się do Koniec listy w kolorze różowym, co się ma zdarzyć się ponownie? Tak, to będzie musiał zacząć od nowa, bo tylko stałe parami błędy. A to może jeszcze ujawnił innych. A więc jeśli to przyspieszyć, będziesz zobaczyć, że, podobnie jak sama nazwa wskazuje, mniejsze elements-- lub raczej większe elements-- zaczynają bulgotać do góry, jeśli będzie. A mniejsze elementy są zaczynają bańki do lewej. I rzeczywiście, to jest rodzaj efekt wizualny, jak również. I tak będzie to skończyć wykończenia w podobny sposób także. 

Nie musimy mieszkać w tym konkretnym jeden. Pozwól mi otworzyć to teraz też. Istnieje kilka innych algorytmów sortowania na świecie, spośród których kilka są ujęte tutaj. A zwłaszcza dla uczniów, którzy nie są niekoniecznie wizualne czy matematyczne, jak przedtem, możemy tak samo postępują audially jeśli skojarzyć dźwięk z tym. I tylko dla zabawy, tu jest Kilka różnych algorytmów, a jeden z nich, w szczególności, że jesteś odnotuje nazywa się "scalania sortowania." 

Właściwie jest to zasadniczy lepszy algorytm, takie, które łączą się porządek, jeden z te, które sami zobaczycie, Kolejność nie jest n do kwadratu. To na zlecenie n razy logarytmicznej n, która jest faktycznie mniejsza, a zatem szybciej niż tych pozostałych trzech. I tam jest kilka innych głupie te, które zobaczymy. 

Więc jedziemy z jakimś dźwiękiem. To Sortowanie przez wstawianie, więc ponownie to jest po prostu do czynienia z elementami jak przychodzą. Jest to sortowanie bąbelkowe, dlatego biorąc pod uwagę ich par na raz. I znowu największe elementy pęcherzyków są do góry. 

Następna w kolejce wyboru sortowania. Ben jest algorytmem, w którym znowu się wybierając iteracyjnie następny najmniejszy element. I znowu, teraz naprawdę można usłyszeć, że to przyspieszenie, ale tylko w takim zakresie, jak to robi się coraz mniej pracować w każdej iteracji. Jest to szybszy, scalanie sortowanie, który jest sortowaniu skupiska liczbach razem, a następnie ich łączenie. Więc look-- lewy połowa jest już posortowana. 

Teraz to sortowaniu prawą połowę, a Teraz to się je połączyć w jeden. To jest coś, co nazywa "Gnom porządek". I można zobaczyć, że rodzaj to tam iz powrotem, ustalające pracy trochę tu i tam, zanim przystąpi do nowej pracy. I to wszystko. Jest jeszcze inny porządek, który jest naprawdę tylko do celów naukowych, nazywa się "głupi porządek", który trwa Twoje dane, sortuje je losowo, a następnie sprawdza, czy jest posortowana. A jeśli nie jest, to ponownie sortuje się losowo, sprawdza, czy to sortowane, a jeśli nie powtarza. I teoretycznie probabilistycznie to zakończy, ale po całkiem sporo czasu. To nie jest najbardziej efektywne algorytmy. Więc wszelkie pytania dotyczące tych Poszczególne algorytmy lub cokolwiek związane też tam? 

No cóż, teraz odciąć co wszyscy linie te są takie, że byłem rysunek i co ja zakładając komputer może to zrobić pod maską. Uważam, że wszystkie te numery Trzymam drawing-- muszą się gdzie przechowywane w pamięci. Będziemy pozbyć się tego faceta, teraz też. 

Więc kawałek pamięci w computer-- więc RAM DIMM czego szukaliśmy wczoraj, podwójny inline memory module-- wygląda następująco. I każdy z tych małych czarnych żetonów pewna liczba bajtów, zwykle. A potem złote szpilki są jak przewody łączące go do komputera, a zielona deska krzemu jest po prostu co trzyma wszystko razem. Więc co to tak naprawdę znaczy? Gdybym rodzaju wyciągnąć ten sam obraz, Załóżmy dla uproszczenia że ten DIMM, podwójny wbudowany moduł pamięci, jest jeden gigabajt pamięci RAM, jeden gigabajt Pamięć, która jest, jak wiele bajtów całkowita? Jeden gigabajt to ile bajtów? Więcej niż to. 1124 jest kilo, 1000. Mega jest miliony. Giga jest miliard. 

Ja kłamie? Możemy nawet czytać etykiety? To jest rzeczywiście 128 gigabajtów, więc jest to bardziej. Ale będziemy udawać, że to Jest tylko jeden gigabajt. To znaczy, nie ma miliard bajtów pamięci dostępnej do mnie lub 8 miliardów bitów, ale będziemy mówić w bajtach teraz posuwa się naprzód. 

Więc co to znaczy, to jest jeden bajt, to kolejny bajt Jest to kolejny bajt a jeśli bardzo chcieliśmy za szczególne musielibyśmy narysować mld małe kwadraty. Ale co to znaczy? Dobrze, niech mi tylko powiększyć w na tym zdjęciu. Jeśli mam coś, co wygląda jak to teraz, to cztery bajty. 

A więc mogłem umieścić tu cztery cyfry. Jeden dwa trzy cztery. Albo może umieścić cztery litery lub symbole. "Hej!" może pójść tam, ponieważ każda z liter omówiliśmy wcześniej, może być reprezentowany z ośmiu bitów lub ASCII lub bajt. Więc innymi słowy, można umieścić rzeczy w środku 8 mld tego jednego kija pamięci. Teraz co to znaczy, aby to odwrócić z powrotem do tyłu w pamięci w taki sposób? To jest to, co programista nazwałbym to "tablicę". W programie komputerowym, nie sądzę o sprzęcie bazowych, per se. Wystarczy myśleć o sobie jako posiadające Dostęp do miliard bajtów sumie i można cokolwiek chcesz z nim. Ale dla wygody to ogólnie przydatne aby utrzymać prawo pamięci obok siebie w taki sposób. Więc gdybym powiększyć this-- dlatego, że nie jesteśmy na pewno będzie narysować mld małe squares-- załóżmy, że ta płyta reprezentuje że kij pamięci teraz. A ja po prostu wyciągnąć tyle, ile moja Znacznik kończy się dając mnie tutaj. Więc teraz mamy kij pamięci na pokładzie który ma jeden, dwa, trzy, cztery, pięć, sześciu, jeden, dwa, trzy, cztery, pięć, sześć, seven-- więc 42 bajtów Pamięć w całości na ekranie. Dziękuję Ci. Tak, tak moja arytmetyczne w prawo. So 42 bajtów pamięci tutaj. Więc co to właściwie znaczy? Dobrze, programista komputerowy faktycznie na ogół myśleć o tej pamięci jako adresowalnych. Innymi słowy, każdy z nich miejsca w pamięci, w sprzęcie, ma unikalny adres. 

To nie jest tak skomplikowane jak One Brattle Square, Cambridge, Mass., 02138. Zamiast tego, to tylko liczba. Liczba bajtów jest zero, to jest Jeden z nich, to jest dwie, to jest trzy i jest 41. Poczekaj chwilę. Myślałem, że powiedziałem 42 przed chwilą. Zacząłem odliczanie od zera, tak, że rzeczywiście poprawne. Teraz nie mamy rzeczywiście wyciągnąć go w postaci siatki, a jeśli zwrócić go w postaci siatki Myślę, że w rzeczywistości rzeczy się nieco mylące. Co programista będzie, w swoim własnym umyśle, generalnie myślę o tym Pamięć tak jest jak taśmy, jak kawałek taśmy maskującej że właśnie trwa i trwa wiecznie lub dopóki nie zabraknie pamięci. Więc bardziej popularnym sposobem rysowania i po prostu myśleć o pamięci jest to, że jest to bajt zero, jeden, dwa, trzy, a następnie kropka, kropka, kropka. I masz 42 bajtów sumie takie, nawet choć fizycznie to może faktycznie być czymś więcej jak ten. 

Więc jeśli teraz myśleć o Pamięć jak ten, podobnie jak taśmy, to co programista ponownie nazwałbym tablicę pamięci. A jeśli chcesz faktycznie przechowywać Coś w pamięci komputera, generalnie należy przechowywać rzeczy back-to-back to back-to-back. Tak więc już mówić o liczbach. A kiedy chciał rozwiązywać problemy jak cztery, jeden, trzy, dwie, chociaż właśnie rysunek jedynie cztery cyfry, jeden, trzy, dwa na płycie, komputer będzie naprawdę mają tę konfigurację w pamięci. 

A co byłoby obok dwa w pamięci komputera? Cóż, nie ma odpowiedzi na to. Naprawdę nie wiem. I tak długo, jak Komputer nie jest potrzebny, nie musisz się martwić, co będzie dalej do numerów to nie zależy. A kiedy powiedziałem wcześniej, że komputer może wyglądać tylko jeden adres na raz Jest to rodzaj dlaczego. 

Nie inaczej rekordu Player i głowica odczytująca tylko jest w stanie spojrzeć na pewne rowek w fizycznym rekordu starej szkoły jednocześnie, w podobny Czy komputer dzięki jego procesora i jego Intel zestaw instrukcji, wśród których instrukcji jest odczytywany z pamięci lub zapisać memory-- komputer może tylko patrzeć w jednym miejscu przy time-- Czasami ich kombinacji, ale tak naprawdę tylko jedno miejsce w danym czasie. Więc kiedy robiliśmy te różne algorytmy, Nie jestem tylko piśmie w vacuum-- czterech, jeden, trzy, dwa. Liczby te faktycznie należą gdzie fizycznej pamięci. Więc nie są malutkie tranzystory lub jakiś elektroniki pod Okap przechowywania tych wartości. 

A w sumie, ile bitów udział już teraz, żeby była jasność? Więc to jest cztery bajty lub teraz jest to 32 bity całkowite. Więc nie są w rzeczywistości i 32 zer te tworzące te cztery rzeczy. Jest jeszcze tutaj, ale znowu nie dbam o to. 

Więc teraz niech zadać kolejny Pytanie używana jest pamięć, dlatego, że na koniec dnia w wariancji. Bez względu na to, co możemy zrobić z komputer, na koniec dnia sprzęt jest nadal samo pod wyciągiem. Jak bym się zapisać słowo tutaj? Cóż, słowo w komputerze jak "Hej!" będą przechowywane właśnie w taki sposób. A jeśli chcieliśmy dłużej Słowo, można po prostu nadpisać i powiedzieć coś jak "cześć" i sklep, który tutaj. 

I tak i tu, to contiguousness jest rzeczywiście korzystne, ponieważ komputer może po prostu czytać od prawej do lewej. Ale tu jest pytanie. W związku z tym słowo h-pl-l-l-o, Wykrzyknik, jak może komputer wie, gdzie Słowo zaczyna się i gdzie kończy się słowo? W kontekście liczb Jak działa komputer wiedzieć, jak długo sekwencja Liczby są lub gdzie zaczyna? Cóż, okazuje out-- i nie będziemy się zbytnio na tym poziomie detail-- komputery przenieść rzeczy wokół w pamięci dosłownie za pomocą tych adresów. Więc w komputerze, jeśli jesteś pisanie kodu do przechowywania rzeczy jak słowa, co masz naprawdę robi pisze Wyrażenia, które pamiętają gdzie w Pamięć komputera są te słowa. Więc pozwól mi bardzo, bardzo prosty przykład. 

Mam zamiar iść do przodu i otworzyć prosty program tekstowy, i mam zamiar stworzyć plik o nazwie hello.c. Większość tych informacji możemy Nie będę wchodził w najdrobniejszych szczegółach, ale mam zamiar napisać Program w tym samym języku, C. Jest to o wiele bardziej zastraszające, Uważam, niż Scratch, ale to jest bardzo podobne w duchu. W rzeczywistości, te kręcone braces-- można rodzaju myśleć o tym, co właśnie zrobił jak ten. 

Zróbmy to, faktycznie. Po kliknięciu zielona flaga, rób następująco. Chcę wydrukować "cześć". Więc teraz jest pseudokod. Jestem rodzaju rozmycia linii. W C, ten język mówię o, ta linia wydruku komentarzy faktycznie staje się "printf" z niektóre nawiasy i średnik. 

Ale to jest dokładnie ten sam pomysł. I to bardzo łatwy w obsłudze "Kiedy zielona flaga kliknięciu" staje znacznie bardziej ezoteryczne "int main nieważne." I to naprawdę nie ma odwzorowania, więc jestem po prostu się do tego zignorować. Ale nawiasy klamrowe są jak wygięte kawałki układanki lubią to. 

Więc może trochę zgadywać. Nawet jeśli nigdy wcześniej zaprogramowane wcześniej, co robi ten program chyba zrobić? Prawdopodobnie drukuje komentarzy z wykrzyknikiem. 

Warto więc spróbować. Zamierzam ją uratować. I to jest znowu bardzo stare środowisko szkolne. Nie mogę klikać, nie mogę przeciągać. Mam wpisywać komendy. Więc chcę uruchomić mój program, więc Mogę to zrobić, jak hello.c. To plik wpadłem. Ale czekaj, jestem brakuje krok. Co mówimy, jest to konieczne krok na języku jak C? Właśnie pisane źródła Kod, ale co mi potrzebne? Tak, muszę kompilator. Więc na moim Macu tutaj, mam Program nazywa się GCC, kompilatora GNU C, która pozwala mi robić this-- kolej mój kod źródłowy pod będziemy nazywać, kod maszynowy. 

I widzę, że znowu, takie jak te są zer i jedynek Właśnie utworzone z mojego kodu źródłowego, wszystkich zer i jedynek. A jeśli chcę uruchomić Mój program-- zdarza nazywać a.out dla historyczne reasons-- "cześć". Mogę go uruchomić ponownie. Witam Witam Witam. I wydaje się działać. 

Ale to oznacza, gdzieś w moim Pamięć komputera są słowa h-pl-l-l-o, Wykrzyknik. I okazuje się, tak na marginesie, co komputer typowo zrobić tak, że wie, gdzie wszystko zaczyna i end-- to zamiar umieścić specjalny symbol tutaj. I Konwencji jest umieszczenie liczbę zero na końcu słowa aby wiedzieć, gdzie jest faktycznie kończy się, więc, że nie trzymaj drukując coraz znaków niż faktycznie zamierzają. 

Ale tutaj, na wynos, nawet choć jest to dość ezoteryczne, jest to, że ostatecznie stosunkowo prosta. Ty dano rodzaju taśmy, puste Powierzchnia, na której można pisać listy. Po prostu musisz mieć specjalny symbol, jak arbitralnie liczbę zero, aby umieścić na koniec Twoje słowa tak, że komputer wie och, muszę zatrzymać drukowanie po Widzę wykrzyknik. Ponieważ Następną rzeczą jest Jest to wartość ASCII zera, lub jako znak null ktoś by to nazwać. Ale jest to rodzaj problemu tutaj, i niech powróci do numerów na chwilę. Załóżmy, że mam w rzeczywistości, tablicę liczb, i załóżmy, że Program Piszę to jak książka dla nauczyciela klasy i nauczycieli w klasie. A ten program pozwala mu wpisać w wyniki swoich uczniów na quizów. I załóżmy, że student dostaje 100 na swoim pierwszym quizie, może jak 80 na następny, a potem 75, następnie 90 na czwartym quiz. 

Więc w tym momencie w historii, matryca ma rozmiar cztery. Nie ma absolutnie więcej pamięci w komputer, ale tablica, by tak rzec, ma wielkość czterech. Przypuśćmy teraz, że nauczyciel chce przypisać piąty quizu do klasy. Cóż, jedna z rzeczy, czy ona ma zamiar zrobić Teraz jest przechowywać dodatkową wartość tutaj. Ale jeśli tablicy nauczyciel ma stworzone w tym programie nie ma rozmiaru dla, jednego problemu z tablicy jest nie można po prostu dodajemy do pamięci. Bo co, jeśli inna część Program posiada słowo "hej" właśnie tam? 

Innymi słowy, moja pamięć może być wykorzystane do niczego w programie. A jeśli z góry Wpisałem się, hej, Chcę wejście czterech punktów konkursowe Może idą tutaj i tutaj. A jeśli nagle zmienić zdanie później i że chcę piąty quizu Wynik, nie można po prostu umieścić go w dowolnym miejscu, bo co, jeśli to Pamięć jest używany czegoś else-- innego programu lub inna cechą programu że używasz? Więc trzeba myśleć z wyprzedzeniem jak chcesz przechowywać swoje dane, bo teraz już malowane Sam do cyfrowej rogu. 

Więc może zamiast nauczycielem powiedzieć, pisząc program do przechowywania jego lub jej klas, wiesz co? Mam zamiar poprosić, pisząc swój program, że chce zero, jeden, dwa, trzy, cztery, pięć, sześć, osiem klas łącznie. Tak jeden, dwa, trzy, cztery, pięć, sześć, siedem, osiem. Nauczyciel może nieco ponad przydzielić Pamięć przy pisaniu swojego programu i powiedzieć, wiesz co? Nigdy nie będę przypisać więcej niż osiem quizów w semestrze. To jest po prostu szalony. Nigdy nie przydziela tego. Więc w ten sposób, że on lub ona ma elastyczność w punktacji sklepu studenckich, jak 75, 90, a może i jedno dodatkowe, gdzie student dostał dodatkowy kredyt, 105. 

Ale jeśli nie nauczyciel wykorzystuje te trzy przestrzenie, jest intuicyjny wynos tutaj. On lub ona jest tylko marnowanie miejsca. Tak więc, innymi słowy, jest to wspólny kompromis w programowaniu gdzie można albo przydzielić dokładnie tyle pamięci, ile chcesz, Plusem jest to, z czego bardzo jesteś efficient-- jesteś nie jest marnotrawstwem w żadnym stopniu ale minusem których to co, jeśli zmienisz zdanie, gdy za pomocą programu, który chcesz zapisać więcej danych niż pierwotnie przeznaczone. 

Może więc rozwiązanie jest zatem pisać swoje programy w taki sposób, że używają więcej pamięci niż faktycznie potrzeba. W ten sposób nie będziemy do przedostania się do tego problemu, ale masz być marnotrawstwem. A im więcej pamięci program używa jak mówiliśmy wczoraj, tym mniej Pamięć to dostępne dla innych programów, tym szybciej komputer może zwolnić w dół ze względu na pamięć wirtualną. A więc idealnym rozwiązaniem może być to, co? 

Under-przydzielania wydaje złe. Nadmierne Alokacja wydaje złe. Więc co może być lepszym rozwiązaniem? Realokacji. Bądź bardziej dynamiczna. Nie zmuszaj się do wyboru priori, na początku, co chcesz. A już na pewno nie w ciągu przyznać, abyście nie marnotrawstwo. 

I tak, aby osiągnąć ten cel, trzeba rzucić tę strukturę danych, by tak rzec, z dala. A więc to, co programista zazwyczaj wykorzystywać jest coś nie jest nazywany Tablica ale połączonej listy. Innymi słowy, on lub ona będzie zacząć myśleć o ich pamięci jako swego rodzaju kształt, że może zwrócić się w następujący sposób. Jeśli chcesz zapisać jedną liczbę w program-- więc września Dałem moich uczniów quiz; chcę przechowywanie pierwszy quiz uczniów, i dostali 100 na it-- I Zamierzam zapytać mojego komputera, w drodze programu Mam napisano na jednym fragmencie pamięci. I mam zamiar przechowywać Numer 100 w nim, i to wszystko. 

Potem kilka tygodni później kiedy się moją drugą quizu, i nadszedł czas, aby wpisać w tym 90% jadę zwrócić się do komputera, hej, komputer, Mogę mieć inny fragment pamięci? To będzie dać mi tego pusty fragment pamięci. Mam zamiar umieścić w liczbie 90, ale w moim programie jakoś other-- i nie będziemy martwić składnia this-- muszę jakoś połączyć te rzeczy razem. A ja je razem z łańcucha wygląda jak strzała tutaj. 

Trzeci quizu, który pojawia się, Idę powiedzieć, hej, komputer, daj mi jeszcze kawałek pamięci. I zamierzam odłożyć cokolwiek to było, jak 75, i mam do tego łańcucha teraz razem jakoś. Czwarty quizu przychodzi, a może to pod koniec semestru. I w tym momencie mojego programu Może być używana jest pamięć wszędzie, na całym fizycznie. I tak po prostu dla zabawy, jestem zamiar wyciągnąć to dalej quiz-- zapomniałem co to było; ja że być może 80 lub something-- sposób tutaj. 

Ale to dobrze, bo obrazowo Zamierzam wyciągnąć tę linię. Innymi słowy, w rzeczywistości w sprzęcie komputera, pierwszy wynik może kończy się tutaj, ponieważ jest to zaraz na początku semestru. Kolejny może skończyć się tutaj bo trochę czasu minęło a program ciągle działa. Następny wynik, który był 75, może być tutaj. I ostatni wynik może być 80, co jest tutaj. 

Tak więc w rzeczywistości, fizycznie, to może być co pamięci komputera wygląda. Ale nie jest to psychicznym użyteczne Paradygmat dla programisty komputerowego. Dlaczego warto dbać gdzie cholery dane są kończąc? Chcesz tylko do przechowywania danych. 

Jest to coś w rodzaju naszej dyskusji wcześniej rysowania sześcian. Dlaczego cię to obchodzi, co kąt jest sześcianu i jak trzeba skręcić, żeby go wyciągnąć? Chcesz tylko kostkę. Podobnie Tutaj po prostu chcą książki gatunku. Po prostu chcę myśleć o to jako lista numerów. Kogo to obchodzi, jak to jest realizowane sprzętowo? 

Więc teraz abstrakcji Ten obraz jest tutaj. Jest to związane listy, a programista byłoby to nazwać, ile masz Lista oczywiście liczb. Ale to związane obrazowo poprzez te strzałkami i wszystkie te strzały are-- spodu kaptur, jeśli jesteś ciekaw, Przypomnijmy, że nasza fizyczna sprzęt ma Adresy zero, jeden, dwa, trzy, cztery. Wszystkie te strzały są to jak mapa lub kierunki, gdzie jeśli 90 is-- teraz Muszę policzyć. 

Zero, jeden, dwa, trzy, cztery, pięć, sześć, siedem lat. Wygląda na to, że 90 jest pamięć numeru adresu siedem. Wszystkie te strzały są to jak mały skrawek papieru która daje wskazówki do Program, który mówi, zgodnie z mapą aby dostać się do miejsca siódmego. I nie znajdziesz Drugi wynik quizu studenta. Tymczasem 75-- gdybym dalej, to jest siedem, osiem, dziewięć, 10, 11, 12, 13, 14, 15. 

Ta druga strzałka po prostu reprezentuje mapa do lokalizacji pamięci 15. Ale znowu, programista zazwyczaj robi Nie dbają o takim poziomie szczegółowości. I w większości każdym programowaniu dziś język, programista nawet nie wiem, gdzie w pamięci Liczby te są w rzeczywistości. Wszystko on lub ona musi dbać o to, które są w pewien sposób ze sobą powiązane w strukturze danych, takich jak to. 

Ale okazuje się, nie dostać się zbyt techniczne. Ale tylko dlatego, że może być może sobie pozwolić na tę dyskusję tutaj załóżmy, że mamy ponownie Ten problem tutaj tablicy. Zobaczmy, czy żałujemy tutaj. To 100, 90, 75 i 80. 

Pozwolę sobie pokrótce dokonać tego twierdzenia. Jest to tablica, a kolejny znamienną cechą tablicy jest to, że wszystkie dane są z powrotem do plecami do siebie w memory-- dosłownie jeden bajt lub może cztery bajty, część stała liczba bajtów dalej. W połączonej listy, które możemy wyciągnąć jak ten, który pod maską wie, gdzie te rzeczy jest? To nawet nie musi płynąć w ten sposób. Niektóre dane mogą być z powrotem do lewej na górze. Nawet nie wiem. 

I tak z tablicą, masz Funkcja zwana losowego dostępu. A co oznacza swobodnym dostępie że komputer może przeskoczyć od razu do dowolnego miejsca w tablicy. Czemu? Ponieważ komputer wie że pierwsze położenie jest zero, jeden, dwa, trzy. 

A więc jeśli chcesz jechać z ten element do następnego elementu, dosłownie, w Umysł komputera, wystarczy dodać jeden. Jeśli chcesz, aby przejść do trzeciego elementu, wystarczy dodać jedno- następnego elementu, po prostu dodać. Jednakże, w tej wersji historii, przypuśćmy komputer jest obecnie poszukuje na lub do czynienia z numerem 100. W jaki sposób można dostać się do następnego klasy w książce klasy? 

Trzeba wziąć siedem Kroki, które jest arbitralne. Aby dostać się do następnego, trzeba podjąć kolejne osiem kroków, aby dostać się do 15. Innymi słowy, nie jest stały odstęp między liczbami, i tak to właśnie bierze komputer jeszcze raz o to chodzi. Komputer musi szukać przez pamięć w celu znaleźć to, czego szukasz. 

Więc podczas gdy tablica wydaje się być structure-- szybka danych, bo ciebie dosłownie można po prostu zrobić prostą arytmetykę i dotrzeć tam, gdzie chcesz, dodając jeden, dla instance-- połączonej listy, poświęcić tej funkcji. Nie można po prostu przejść od pierwszego z drugiej do trzeciej, czwartej. Trzeba śledzić mapę. Trzeba podjąć kolejne kroki aby dostać się do tych wartości, które wydaje się być dodanie kosztów. Więc płacimy cenę, ale to, co było Cechą, która Dan szukał tutaj? Co połączonej listy widocznie pozwalają nam robić, co było pochodzenie ta szczególna historia? 

Dokładnie. Dynamiczny rozmiar do niego. Możemy dodać do tej listy. Możemy nawet kurczą listę, więc że jesteśmy tylko przy tak dużej ilości pamięci tak właściwie chcemy i tak Nigdy nie jesteś zbyt przydzielania. 

Teraz wystarczy, aby być naprawdę nit-wybredna, istnieje ukrytych kosztów. Więc nie należy po prostu pozwolił mi przekonać Ci, że jest to przekonujące kompromis. Jest jeszcze jeden ukryty koszt tutaj. Korzyść, być jasne, jest to, że możemy uzyskać dynamikę. Jeśli chcę kolejny element, mogę po prostu wyciągnąć go i umieścić numer tam. A potem mogę go połączyć z obrazem tutaj natomiast tutaj znowu, jeśli mam malowane sobie w kącie, czy coś innego nie jest już używane pamięć tu jestem pecha. Mam pomalowane się w rogu. 

Ale to, co jest ukryte kosztuje na tym obrazku? To nie tylko ilość czas, który potrzebny aby przejść stąd tu, czyli siedem kroków, a następnie osiem kroków, których jest więcej niż jeden. Co znajduje się w innym ukryte koszty? Nie tylko czas. Dodatkowe informacje o firmie konieczne do osiągnięcia tego obrazu. 

Tak, to mapa, te małe skrawki papier, jak utrzymać opisując je jako. Są arrows-- te nie są wolne. Computer-- wiesz co komputer ma. Ma zer i jedynek. Jeśli chcesz do reprezentowania strzałkę lub grupę map lub numer, trzeba trochę pamięci. Więc drugiej cenie zapłacić za połączonej listy, wspólny informatyka zasobów, jest także przestrzenią. 

I rzeczywiście, tak, tak często, wśród kompromisów w projektowaniu inżynierii oprogramowania System jest czas i space-- Są dwie swoich składników, dwa swoich najbardziej kosztownych składników. To kosztuje mnie więcej czasu bo mam do tej mapy, ale to też kosztuje mnie więcej miejsca bo muszę utrzymać tę mapę wokół. Więc jest nadzieja, ponieważ mamy rodzaj omówione powyżej wczoraj i dziś, jest to, że korzyści będą przeważać nad kosztami. 

Ale nie ma tu oczywiste rozwiązanie. Może to better-- a la szybkie i brudne, jak Kareem zaproponował earlier-- rzucać pamięć na problem. Wystarczy kupić więcej pamięci, mniej myśleć Trudno o rozwiązaniu problemu, i rozwiązać go w prostszy sposób. I rzeczywiście wcześniej, kiedy rozmawialiśmy o kompromisach, nie było przestrzeń komputer i czas. To był czas, deweloper, który Jeszcze innym źródłem. 

Więc jeszcze raz, to jest to balansowanie próbując zdecydować, które z tych rzeczy jesteś skłonny wydać? Jaki jest najtańszy? Co daje lepsze rezultaty? Tak? 

W rzeczy samej. W tym przypadku, jeśli jesteś reprezentujące liczby w maps-- nazywane są one w wielu językach "Wskaźniki" lub "adresy" - jest to dwa razy więcej miejsca. To nie musi być tak źle, jak w przypadku podwójnego teraz jesteśmy po prostu przechowywania numerów. Załóżmy, że byliśmy przechowywania rekordów pacjenta w hospital-- więc nazwy Pierson jest, numery telefonów, numery ubezpieczenia społecznego, lekarz historia. To pole może być wiele, znacznie większy, w którym to przypadku malutkie wskaźnik, adres następny element-- to nie jest wielka sprawa. To taka grzywka kosztuje to nie ma znaczenia. Ale w tym przypadku, tak, to podwojenie. Dobre pytanie. 

Porozmawiajmy o czasie trochę bardziej konkretnie. Jaki jest czas pracy poszukiwania tej listy? Załóżmy, że chcę, aby szukać przez wszystkie stopnie uczniów, a tam stopni n W tej strukturze danych. Tutaj też możemy pożyczać słownictwo wcześniej. Ta liniowa struktura danych. 

Big O n to, co jest wymagane, aby uzyskać na końcu tej struktury danych whereas-- i nie widzieliśmy Ten before-- tablica daje co nazywa stałą czasową, co oznacza, krok lub dwa stopnie lub 10 steps-- nie ma znaczenia. Jest to stała liczba. To nie ma nic wspólnego z rozmiar tablicy. A powodem tego, ponownie jest losowego dostępu. Komputer może po prostu od razu przeskoczyć do innej lokalizacji, ponieważ są one wszystkie takie same odległość od wszystkiego innego. Nie ma zaangażowany myślenie. W porządku. Więc jeśli mogę, daj mi spróbować malować dwa ostatnie zdjęcia. Bardzo często jeden znany jako tabeli mieszania. Więc motywować tę dyskusję, pozwól mi myśleć o tym, jak to zrobić. 

Tak jak o tym? Załóżmy, że problem chcemy rozwiązać teraz wdraża w dictionary-- więc cała masa angielskich słów lub cokolwiek. A celem jest, aby móc odpowiedzieć Kwestie postaci jest to słowo? Więc chcesz wdrożyć sprawdzania pisowni, tuż jak fizyczny słowniku że można spojrzeć na rzeczy. Załóżmy, że było to zrobić z tablicy. Mógłbym to zrobić. 

I załóżmy, że słowa są jabłka banan i kantalupa. I nie mogę myśleć o owocach które zaczynają się d, więc jesteśmy po prostu będziemy mieć trzy owoce. Więc to jest tablicą, a my jesteśmy przechowywania wszystkich tych słów w tym słowniku jako tablicę. Pytanie jest więc, jak inaczej można przechowywać te informacje? 

Cóż, jestem tutaj rodzaj oszukiwania, ponieważ każda z tych liter w słowie jest naprawdę indywidualna bajtów. Więc jeśli naprawdę chciałem być nit-wybredna, powinienem naprawdę być podzielenie się do tego znacznie mniejsze kawałki pamięci, i mogliśmy zrobić dokładnie to. Ale mamy zamiar uruchomić w ten sam problem, jak wcześniej. Co jeśli, jak Merriam Webster i Oxford Czy każdy rok-- dodają słowa do dictionary-- nie robimy niekoniecznie chcą się malować na rogu z tablicy? 

Zamiast więc, może mądrzejsi podejście jest umieszczenie jabłek we własnym węzłem lub pudełku, jak powiedzielibyśmy, banan i to tutaj mamy kantalupa. A my ciąg te rzeczy razem. Więc to jest tablica, a jest to związane lista. Jeśli nie można dość zobaczyć, to po prostu mówi "tablica", a to mówi "listy". 

Mamy więc takie same Dokładne kwestie jak poprzednio, przy czym mamy teraz Dynamizm w naszej połączonej listy. Ale mamy dość powolny słownika. Załóżmy, że chcę sprawdzić słowo. Może to zająć mi Big O n kroków, ponieważ słowo może się, aż na koniec lista, podobnie jak kantalupa. I okazuje się, że w programowaniu, sortowanie świętego Graala danych struktury, jest czymś który daje stałe Czas jakby tablicy ale wciąż daje dynamikę. 

Tak więc możemy mieć najlepsze z obu światów? I rzeczywiście, jest coś nazywany tabeli mieszania który pozwala dokładnie zrobić , Które choć w przybliżeniu. Tabela mieszania jest hodowcy Struktura danych, które Można pomyśleć, jak kombinacja array-- a ja zamierzam go wyciągnąć jak this-- i połączonych listach że będę rysować jak ten tutaj. 

A droga ta sprawa działa, jest następujący. Jeśli now-- ten hash table-- Jest to moja trzecia struktura danych, i chcę się zapisać słowa tego, nie wiem chcę po prostu zapisać wszystkie z słowa z powrotem do tyłu z powrotem do tyłu. Chcę wykorzystać niektóre kawałek informacji o słowach, które pozwolą mi ją tam, gdzie jest to szybciej. 

Tak więc biorąc pod uwagę słowa jabłko banan i kantalupa, Celowo wybraliśmy te słowa. Czemu? Jaki jest rodzaj gruntu różni się o trzy? Co jest oczywiste? Zaczynają z różnymi literami. 

Więc wiesz co? Zamiast umieścić wszystkie moje słowa to samo wiaderko, że tak powiem, jak w jednej wielkiej listy, to dlaczego nie zrobić Ja przynajmniej spróbować optymalizacji i uczynić moje listy 26/01 tak długo. Ciekawa optymalizacja może być, dlaczego nie Ja-- podczas wstawiania słowa do tej struktury danych do pamięci komputera, dlatego Nie mogę umieścić tutaj wszystkie "a" słowa, Wszystkie słowa 'B' Tutaj, i wszystkie słowa, 'C' Tutaj? Tak to kończy się wprowadzenie jabłko tutaj, banan tu kantalupa tutaj i tak dalej. 

A jeśli mam dodatkowe Słowo like-- co innego? Jabłko, banan, gruszka. Każdy myśli o smaku owocowym zaczynający się a, b lub c? Blueberry-- doskonały. To skończy się tutaj. A więc wydaje się, że minimalnie lepszym rozwiązaniem, bo teraz jeśli chcę aby szukać jabłko, ja first-- I nie tylko nurkowanie w moim struktury danych. Nie nurkować w pamięci mojego komputera. Po raz pierwszy spojrzeć na pierwszej literze. 

I to właśnie z komputera Naukowiec powie. Ty hash do swojej struktury danych. Wziąć swój wkład, który w sprawa ta jest słowem jak jabłko. Analizując je, patrząc na pierwsza litera w tym przypadku, sposób mieszania go. Hashing to ogólne określenie, zgodnie z którą wziąć coś jako wejście i produkować jakieś wyjście. A wyjście na tym, że Sprawa jest lokalizacja chcesz szukać, pierwszy Położenie drugie położenie, trzecią. Więc wejście jest jabłko, wyjście jest w pierwszej kolejności. Wejście jest banan, The Wyjście powinno być sekundy. Wejście jest kantalupa, wyjście powinno być trzecią. Wejście jest borówka, The Wyjście powinno być ponownie sekund. I to właśnie pozwala przejąć Skróty dzięki swojej pamięci w celu uzyskania słów lub dane bardziej efektywnie. 

Teraz ten skraca nasz czas potencjalnie nawet jako jeden z 26, bo jeśli zakładamy, że mieć tyle "a" słowa jak "z" słowa jak "Q" słów, które nie jest tak naprawdę realistic-- masz zamiar mieć pochylenie całej niektóre litery alphabet-- ale byłoby to przyrostowe Podejście to nie pozwala można dostać się do słów znacznie szybciej. A w rzeczywistości, wyrafinowany programu, Googles świata, Facebooks z world-- oni użyć tabeli mieszania dla wielu różnych celów. Ale nie byłby tak naiwny, po prostu spojrzeć na pierwszą literę w jabłko lub banana lub gruszkowe lub kantalupa, bo jak widać nich Listy można jeszcze dostać długo. 

I tak może to być jeszcze porządek z linear-- tak jakby powolny, jak z Big O n które omówiono wcześniej. Więc co naprawdę dobry tabeli mieszania będzie do-- będzie miał znacznie większy wachlarz. I będzie używać znacznie bardziej wyrafinowana funkcja skrótu, tak, że nie tylko wygląda na "a". Może to wygląda na "a-p-p-l-e", a jakoś konwertuje te pięć liter w miejscu, w którym Apple powinno być przechowywane. Jesteśmy po prostu naiwnie pomocą litery "A" sam, bo to ładne i proste. 

Ale tabeli mieszania w koniec, można myśleć jako kombinację tablicą, z których każda ma połączonej listy, które najlepiej powinien być jak najkrótszy. I nie jest to oczywiste rozwiązanie. W rzeczywistości, wiele dostrojeniu co dzieje się pod maską, gdy Realizując te rodzaje wyrafinowane struktury danych jest to, co jest właściwe długość tablicy? Jaka jest funkcja hash prawda? Jak przechowywać rzeczy w pamięci? 

Ale sobie sprawę, jak szybko tego rodzaju dyskusji eskalacja, czy tak daleko, że jest to rodzaj z nad głową w tym miejscu, które jest w porządku. Ale zaczęliśmy, wycofanie z prawdziwie coś na niskim poziomie i elektronicznego. I tak to znowu jest to Tematem abstrakcji, gdzie po uruchomieniu do podjęcia przez przyznane, OK, mam it-- tam Pamięć fizyczna, OK, rozumiem, każdy Fizyczna lokalizacja ma adres, OK, rozumiem, mogę reprezentować te adresy jak arrows-- można bardzo szybko zaczynają mieć Bardziej zaawansowane rozmowy, które w końcu wydaje się, że pozwala nam do rozwiązywania problemów, takich jak wyszukiwanie i sortowania bardziej efektywnie. I mieć pewność, too-- bo myślę, że to jest najgłębszym zaszliśmy do niektórych z tych tematów CS proper-- my ve sporządzono w dniu i połowę w tym wskazać, co można zrobić, zwykle w ciągu przebieg ośmiu tygodni w semestrze. 

Wszelkie pytania na temat tych? Nie? W porządku. Cóż, dlaczego nie możemy wstrzymać tam, zacząć obiad kilka minut wcześniej, wznowić w ciągu około godziny? I będę utrzymywał nieco z pytaniami. Potem będę musiał przejść potrwać kilka połączeń, jeśli to jest OK. Będę włączyć jakąś muzykę w międzyczasie ale obiad powinien być tuż za rogiem.