[Musiikkia] PROFESSORI: Selvä. Tämä on CS50 ja tämä on viikon lopussa kolme. Joten olemme täällä tänään, eikä Sanders Teatteri, sen sijaan Weidner kirjasto. Jonka sisällä on studio tunnetaan Hauser Studio, tai sanokaamme Studio H, tai on me say-- jos olet nauttinut että vitsi, se on todella maasta luokkatoveri, Mark, verkossa, joka ehdotti niin paljon Twitterin kautta. Nyt mitä viileä noin täällä studiossa on että olen ympäröi Vihreiden seinät, green screen tai chromakey, niin sanoakseni, mikä tarkoittaa, että CS50: n tuotanto joukkue, tietämättä minulle nyt voisi olla laskemisesta minua eniten kaikkialla maailmassa, parempaan tai huonompaan. Nyt mitä on edessä, Harjoitus kaksi on teidän käsissänne Tällä viikolla mutta Harjoitus kolme tulevalla viikolla, teidät haastetaan kanssa ns peli 15, vanhan puolueen puolesta, että saatat muistaa saaneen kuin lapsi, joka on koko joukko numeroita, jotka voivat liukua ylös, alas, vasemmalle ja oikealle, ja siellä on yksi aukko sisällä palapeli, johon voit voi todella liukua ne palapelin palaset. Lopulta saat tämän palapeli joissakin semi satunnaisessa järjestyksessä, ja tavoitteena on lajitella, ylhäältä alas, vasemmalta oikealle, yhdestä koko matkan läpi 15. Valitettavasti täytäntöönpano sinulla on käsillä tulee olemaan ohjelmisto pohjainen, ei fyysisesti. Olet todella täytyy kirjoittaa koodia, jotka opiskelija tai käyttäjä voi pelata peliä 15. Ja itse asiassa hakkeri painos peli 15, sinun on haaste toteuttaa, ei vain pelaaminen tämän vanhan koulun peli, vaan ratkaiseminen siitä, täytäntöönpanon jumala tilassa niin sanoakseni, että todella ratkaisee palapeli ihmisen, tarjoamalla heille vihje, jälkeen vihje, kun vihje. Niin siitä lisää ensi viikolla. Mutta se, mitä on edessä. Nyt muistaa, että aiemmin tällä viikolla meillä oli jännitysnäytelmä, jos haluatte, jolloin paras teemme lajittelu viisas oli ylärajana Big O n potenssiin. Toisin sanoen, kuplalajittelu, valinta lajitella, lisäyslajittelun, ne kaikki, kun taas eri niiden täytäntöönpanossa, siirretty osaksi n potenssiin käynnissä aika hyvin pahimmassa tapauksessa. Ja me yleensä olettaa, että hyvin pahimmassa tapauksessa lajitteluun on yksi että tuloa ovat täysin taaksepäin. Ja todellakin, se kesti aivan muutaman askeleen toteuttaa jokainen näistä algoritmeja. Nyt aivan lopussa luokan Recall, vertasimme kuplalajittelu vastaan ​​valinta lajitella vastaan ​​yksi muu että kutsuimme yhdistää lajitella tuolloin, ja ehdotan, että se ottaa etuna oppitunti viikossa nolla, hajota ja hallitse. Ja jotenkin saavuttaa jonkinlaista logaritminen käyntiaika lopulta, sijasta jotain se on puhtaasti asteen. Ja se ei ole aivan logaritminen, se on hieman enemmän. Mutta jos muistatte luokasta, se oli paljon, paljon nopeammin. Katsotaanpa katsomaan mihin jäimme. Kuplalajittelu vs. valinta lajitella vs. Yhdistämisen lajitella. Nyt he kaikki käynnissä, vuonna Teoriassa samaan aikaan. CPU on käynnissä samalla nopeudella. Mutta voit tuntea kuinka tylsää tämä on hyvin nopeasti tulossa, ja kuinka nopeasti, kun pistää hiukan viikon nolla algoritmit, voimme nopeuttaa asioita. Joten merkki lajitella näyttää hämmästyttävän. Miten voimme hyödyntää sitä, jotta lajitella numeroita nopeammin. No katsotaanpa muistelen ainesosaa että me oli takaisin viikolla nolla, että etsivät joku puhelinluettelosta, ja muistuttaa, että pseudokoodilla että ehdotimme, jonka kautta voimme löytää joku kuten Mike Smith, näytti vähän jotain tällaista. Nyt katsomaan erityisesti rivillä 7 ja 8, ja 10 ja 11, joka aiheuttaa että silmukka, jolloin pidimme menee takaisin linja 3 uudestaan, ja uudestaan, ja uudelleen. Mutta käy ilmi, että voimme katsella tämä algoritmi, täällä pseudokoodilla, hieman kokonaisvaltaisemmin. Itse asiassa, mitä etsin klo täällä ruudulla, on algoritmi etsii Mike Smith joukossa joitakin joukko sivuja. Ja todellakin, voisimme yksinkertaistaa tämä algoritmi ne rivit 7 ja 8, ja 10 ja 11 vain sanoa, jonka olen esitetään tässä keltaisella. Toisin sanoen, jos Mike Smith on aiemmin kirja, meidän ei tarvitse määrittää vaiheessa askeleelta nyt miten edetä löytää hänet. Meillä ei tarvitse määritellä palata linja 3, Miksi emme vain sen sijaan, sanoa yleisemmin, etsi Mike vasen puoli kirjan. Toisaalta, jos Mike on todella myöhemmin kirjan, miksi emme vain lainata lainaus haku Mike oikeassa puoliskossa kirjan. Toisin sanoen, miksi emme vain tavallaan punt itsellemme sanomalla, etsi Mike tässä osajoukko kirjan, ja jättää sen nykyisiä algoritmi kertoa meille miten etsiä Mike että vasen puoli kirjan. Toisin sanoen, meidän algoritmi toimii onko se puhelinluettelo tämän paksuus, tämän paksuus, tai paksuus lainkaan. Joten voimme rekursiivisesti määritellä tämä algoritmi. Toisin sanoen, on näyttö täällä, on algoritmi etsimiseen Mike Smith keskuudessa sivut puhelinluettelosta. Joten rivi 7 ja 10, katsotaanpa vain sanoa juuri sitä. Ja käytän tätä termiä hetki sitten, ja todellakin, rekursio on muotisana nyt, ja se on tämän prosessin tehdä jotain syklistä jotenkin koodia käyttämällä että sinulla jo on, ja kutsuen sitä uudelleen, ja uudestaan, ja uudestaan. Nyt se tulee olemaan tärkeä että me jotenkin pohja pois, ja älä tee sitä äärettömän pitkä. Muuten aiomme on todellakin päättymättömään silmukkaan. Mutta katsotaan jos voimme lainata tätä ajatusta rekursiivisen, tehdä jotain uudelleen ja uudestaan ​​ja uudestaan, ratkaista lajittelu ongelma kautta yhdistämisen lajitella, kaikki tehokkaammin. Joten annan sinulle yhdistää lajitella. Katsotaanpa katsomaan. Joten tässä on pseudokoodilla, kanssa jotka voisimme toteuttaa lajittelu, Käyttämällä tätä algoritmia kutsutaan yhdistämisen lajitella. Ja se on yksinkertaisesti tämä. Syötteellä n alkion, Toisin sanoen, jos olet annettuja n elementtejä ja numeroita ja kirjaimia tai mikä tulo on, jos olet antanut n elementtiä, jos n on pienempi kuin 2, palaa. Oikea? Koska jos n on pienempi kuin 2, että tarkoittaa, että minun luettelo elementtien on joko kokoa 0 tai 1, ja sekä näissä triviaaleja tapauksissa luettelo on jo järjestetty. Jos ei ole luettelossa, se on järjestetty. Ja jos on lista pituus 1, se on tietenkin järjestetty. Joten algoritmi tarvitsee vain todella jotain mielenkiintoista, jos meillä on kaksi tai useampia elementtejä meille annettu. Joten katsokaamme taika sitten. Else järjestellä vasemmalla puolella elementtejä, sitten lajitella oikealla puolella elementtejä, sitten yhdistää lajiteltu puolikkaat. Ja mikä on tavallaan mielen taivutus täällä, on että en ole oikeastaan näyttävät määrännyt mitään ihan vielä, eikö? Kaikki Olen sanonut on, annetaan luettelo n elementtiä, lajitella vasen puoli, sitten oikea puoli, sitten yhdistää lajiteltu puolikkaat, mutta missä on todellinen salainen kastike? Missä algoritmi? No näyttää siltä, ​​että nämä kaksi riviä ensimmäinen, eräänlainen vasen puoli elementtejä, ja tavallaan oikea puoli elementtejä, ovat rekursiokutsua, niin sanoakseni. Onhan tässä vaiheessa, minulla on algoritmi, jolla voidaan lajitella koko joukko tekijöitä? Kyllä. Se on täällä. Se on täällä ruudulla, ja joten voin käyttää, että samoja vaiheita lajitella vasen puoli, kuin voin oikea puoli. Ja todellakin, uudestaan, ja uudestaan. Joten tavalla tai toisella, ja me pian nähdä tämän, taika yhdistämisen sort on upotettu että hyvin lopullisessa linja, yhdistämällä lajitellut puoliskot. Ja joka tuntuu melko intuitiivinen. Otat kaksi puoliskoa, ja te, jotenkin, yhdistää ne yhteen, ja näemme tämän konkreettisesti hetki. Mutta tämä on täydellinen algoritmi. Ja nyt nähdä tarkalleen miksi. No olettaa, että meille annetaan nämä samat kahdeksan elementtejä tässä ruudulla, yksi kautta kahdeksan, mutta ne ovat näennäisen satunnaisessa järjestyksessä. Ja tavoite käsillä on lajitella nämä elementit. No miten voin mennä noin tekee sen avulla, jälleen, yhdistää lajitella, kuten per tämä pseudokoodina? Ja vielä, ingrain tämä mielesi, vain hetken. Ensimmäinen tapaus on melko triviaali, jos se on vähemmän kuin 2, vain palata, ei ole tehtävää. Joten oikeastaan ​​siellä on vain kolme toimet todella pitää mielessä. Jälleen ja jälleen, olen menossa haluavat olla lajitella vasen puoli, lajitella oikea puoli, ja sitten kun niiden kaksi puolikasta lajitellaan, Haluan yhdistää ne yhteen yhdeksi lajiteltu lista. Niin pitää tämä mielessä. Joten tässä alkuperäisen luettelon. Katsotaanpa käsittelemään tätä array, kun aloimme viikolla kaksi, joka on yhtenäinen alue muistia. Tässä tapauksessa, joka sisältää kahdeksan numeroita, takaisin takaisin takaisin. Ja lähdetään nyt sovelletaan yhdistämisen lajitella. Joten Haluan ensin lajitella vasen puoli tämän luettelon, ja nyt, siksi, keskittyvät 4, 8, 6, ja 2. Nyt miten voin mennä noin lajittelun luettelo koko 4? No minun täytyy nyt harkita lajittelu vasemmalla vasemmalla puolella. Jälleen, nyt kelata vain hetken. Jos pseudokoodi on tämä, ja olen antanut kahdeksan elementtejä, 8 on ilmeisesti suurempi kuin tai yhtä suuri kuin 2. Joten ensimmäinen tapaus ei koske. Joten lajitella kahdeksan elementtejä, haluan ensin lajitella vasemmalla puolella elementtejä, sitten lajitella oikea puoli, sitten yhdistää kaksi lajitellut puolikkaat, kukin koko 4. OK. Mutta jos olet juuri kertonut minulle, lajitella vasen puoli, joka on nyt on koko 4, miten voin lajitella vasen puoli? No jos minulla on tuloon neljä elementtiä, Haluan ensin lajitella vasemmalle kaksi, sitten oikea kaksi, ja sitten yhdistää ne yhteen. Niin uudelleen, se tulee hieman of mielen taivutus peli täällä, koska te, tavallaan, on muistaa missä olet tarina, mutta loppujen lopuksi, antanut mitään useita tekijöitä, ensin haluat lajitella vasen puoli, sitten oikea puoli, sitten yhdistää ne yhteen. Aloitetaan juuri siihen. Tässä panos kahdeksan elementtejä. Nyt me tarkastelemme vasen puoli täällä. Miten lajitella neljä elementtiä? No ensin lajitella vasemmalle puolen. Nyt miten voin lajitella vasen puoli? No Olen saanut kaksi elementtiä. Joten järjestää kaksi elementtiä. 2 on suurempi tai vastaa 2, tietenkin. Niin että ensimmäinen tapaus ei koske. Joten minulla on nyt lajitella vasemmalle puolet näistä kahdesta elementistä. Vasen puoli, tietenkin, on vain 4. Joten miten voin lajitella luettelon yhden elementin? No nyt, että erityistä perustapaus ylös, niin sanotusti, sovelletaan. 1 on pienempi kuin 2, ja minun luettelo on todellakin koko 1. Joten en juuri palata. En tee mitään. Ja todellakin, katso mitä olen tehty, 4 on jo järjestetty. Kuten olen jo osittain onnistunut tässä. Nyt näyttää typerää vaatia, mutta se on totta. 4 on luettelo koko 1. Se on jo järjestetty. Se vasen puoli. Nyt minä lajitella oikea puoli. Minun panos on yksi elementti, 8 Samoin jo järjestetty. Tyhmä, liian, mutta jälleen, tämä perusperiaate aikoo jotta voimme nyt rakentaa päälle tämän onnistuneesti. 4 lajiteltu, 8 lajitellaan, nyt mikä oli viimeinen askel? Niin kolmas ja viimeinen vaihe, mikä tahansa kerran olet lajittelun lista, muistaa, oli yhdistää kaksi puolikasta, vasemmalle ja oikealle. Joten juuri siihen. Minun vasen puoli on tietenkin, 4. Minun oikea puoli on 8. Joten tehdään tämä. Ensinnäkin aion jakaa jotkut lisämuistia, että minä täällä edustan, koska vain toissijainen array, joka on iso mahtuakseen tähän. Mutta voit kuvitella jatkamisesta että suorakulmion koko pituudeltaan, jos tarvitsemme lisää myöhemmin. Miten otan 4 ja 8, ja yhdistää nämä kaksi luetteloa koko 1 yhdessä? Tässäkin melko yksinkertainen. 4 tulee ensin, sitten tulee 8. Koska jos haluan lajitella vasen puoli, sitten oikea puoli, ja sitten yhdistää nämä kaksi puolikasta yhdessä, lajiteltu järjestyksessä, 4 tulee ensin, sitten tulee 8. Joten näytämme edistyy, vaikka vaikka en ole tehnyt mitään varsinaista työtä. Mutta muista missä olemme tarina. Olemme alunperin kesti kahdeksan elementtejä. Olemme järjestetty vasen puoli, joka on 4. Sitten lajitellaan vasen puoli vasemman puolen, mikä oli 2. Ja tässä sitä mennään. Olemme tehneet tämän askeleen. Joten jos olemme lajiteltu vasen puoli 2, nyt meillä on lajitella oikea puoli 2. Joten oikea puoli 2 on nämä kaksi arvoa täällä, 6 ja 2. Joten nyt ottaa panos koko 2, ja lajitella vasen puoli, ja sitten oikea puoli, ja sitten yhdistää ne yhteen. No miten voin lajitella luettelon koko 1, joka sisältää vain numero 6? Olen jo tehnyt. Että luettelo koko 1 lajitellaan. Miten lajitella toinen luettelo koko 1, niin sanottu oikea puoli. No sekin on jo järjestetty. Numero 2 on yksin. Joten nyt minulla on kaksi puoliskoa, vasemmalle ja oikea, minun täytyy yhdistää ne yhteen. Annan itselleni ylimääräistä tilaa. Ja laittaa 2 siellä, sitten 6 siellä, mikä lajittelu että luettelo, vasen ja oikea, ja yhdistämällä se yhteen, lopulta. Joten olen hieman paremmassa kunnossa. En ole tehnyt, koska selvästi 4, 8, 2, 6 ei ole lopullinen tilaus, että haluan. Mutta Minulla on nyt kaksi luetteloa koko 2, että ovat molemmat vastaavasti on lajiteltu. Joten nyt jos taaksepäin sielusi silmä, mistä se jättää meidät? Aloitin kahdeksan elementtejä, niin minä supistetaan se alas vasemmalla puolella 4, sitten vasen puoli 2, ja sitten oikea puoli 2, Lopetin, siis, lajittelu vasen puolet 2, ja oikea puoli 2, niin mitä kolmas ja viimeinen vaihe tässä? Minun täytyy yhdistää yhdessä kaksi luetteloa koko 2. Joten mene eteenpäin. Ja ruudulla täällä, antaa minulle lisämuistia, vaikka teknisesti, huomaa, että olen sai koko joukko tyhjä tila ylös siellä. Jos haluan olla erityisen tehokkaasti tilaa viisas, Voisin vain alkaa liikkuvat osat edestakaisin, ylhäällä ja alhaalla. Mutta vain visuaalinen selkeys, Aion laittaa se alas alla, pitää asiat mukava ja puhdas. Joten minulla kaksi luetteloa koko 2. Ensimmäinen luettelo on 4 ja 8. Toisessa luettelossa on 2 ja 6. Katsotaanpa yhdistää ne yhdessä lajiteltu järjestyksessä. 2, tietenkin, tulee ensin, sitten 4, sitten 6, sitten 8. Ja nyt me näyttävät saada jonnekin mielenkiintoinen. Nyt olen lajiteltu puolet luetella, ja sattumalta, se on kaikki parilliset numerot, mutta että on todellakin vain sattumaa. Ja nyt on lajiteltu vasen puoli, että se on 2, 4, 6, ja 8. Mikään ei ole epäkunnossa. Joka tuntuu edistystä. Nyt tuntuu kuin olisin puhuneet ikuisesti nyt, niin mitä jää nähtäväksi, jos tämä algoritmi on todellakin tehokkaampi. Mutta olemme menossa läpi se erittäin järjestelmällisesti. Tietokone, tietenkin, tekisi sen niin. Missä siis olemme? Aloitimme kahdeksan elementtejä. Olen lajiteltu vasemmalla puolella 4. Näytän tehdä sen kanssa. Joten nyt seuraava askel on lajitella oikea puoli 4. Ja tämä osa voimme mennä läpi hieman enemmän nopeasti, vaikka olet Tervetuloa kelata tai pysäyttää, vain ajatella sen läpi omaan tahtiin, mutta mitä meillä nyt on tilaisuus tehdä täsmälleen samaa algoritmia neljään eri numeroille. Joten mene eteenpäin, ja keskitytään oikea puoli, jotka olemme täällä. Vasen puoli on, että oikea puoli, ja nyt vasen puoli vasemman puolet oikea puoli, ja miten lajitella luettelon koko 1, joka sisälsi vain numero 1? Se on jo tehty. Miten teen sama lista koon 1, joka sisältää vain 7? Se on jo tehty. Vaihe kolme tähän puoli sitten on yhdistää nämä kaksi tekijää uuteen luettelo koko 2, 1 ja 7. Eivät näytä tehneen kaikki että paljon mielenkiintoista työtä. Katsotaan, mitä tapahtuu seuraavaksi. Olen juuri järjestetty vasemmalla puolella oikea puoli minun alkuperäinen panos. Nyt lajitella oikealla puoli, joka sisältää 5 ja 3. Katsotaanpa jälleen katsoa vasemmalle puoli, lajiteltu, oikea puoli, lajiteltu, ja yhdistää nämä kaksi yhdessä, johonkin lisätilaa, 3 tulee ensin, sitten tulee 5. Ja nyt olemme lajiteltu vasemmalla puolella oikea puoli alkuperäisen ongelman, ja oikea puoli oikea puoli alkuperäisen ongelman. Mikä on kolmas ja viimeinen vaihe? Hyvin yhdistää nämä kaksi puolikasta yhteen. Joten haluan saada itselleni lisätilaa, mutta, jälleen, minä saattaa käyttää, että vapaata tilaa ylös. Mutta aiomme pitää se yksinkertainen visuaalisesti. Saanen sulautuvat nyt 1, ja sitten 3, ja sitten 5, ja sitten 7. Mikä jättää minua nyt oikeus puolet alkuperäisestä ongelmasta joka on täydellisesti lajitellaan. Niin mitä jää jäljelle? Tunnen pitää sanoa samat asiat uudestaan, ja uudestaan, mutta se kuvastaa Se, että käytämme rekursion. Prosessi käyttää algoritmi uudestaan, ja uudestaan, pienempiin osajoukot alkuperäiseen ongelmaan. Joten minulla on nyt vasemmalle lajiteltu puolet alkuperäisestä ongelmasta. Minulla on oikeus lajitellut puoli alkuperäisen ongelman. Mikä on kolmas ja viimeinen vaihe? Voi, se on sulautuvat. Joten tehdä. Katsotaanpa jakaa joitakin uusia muisti, mutta luoja, me voisi laittaa sen minne nyt. Meillä on niin paljon tilaa meille, mutta me pitää se yksinkertainen. Sijaan menee takaisin ja esiin ja alkuperäistä muistia, Haluan vain tehdä se visuaalisesti täällä alla, loppuun asti sulautuvien vasen puoli ja oikea puoli. Joten yhdistämällä, mitä minun pitää tehdä? Haluan ottaa elementtejä järjestyksessä. Joten etsit vasen puoli, Näen ensimmäinen numero on 2. Katson oikea puoli, Näen ensimmäinen numero on 1, niin ilmeisesti joka numero Haluanko nyppiä pois, ja laittaa ensimmäinen minun lopullisen luettelon? Tietenkin, 1. Nyt haluan kysyä saman kysymyksen. Vasemmalla puolella, olen silti saanut numero 2. Oikealla puoliskolla, Minulla numero 3. Kumpi minä haluan valita? Tietenkin, numero 2 ja nyt huomaa ehdokkaat 4 vasemmalla, 3 oikealla. Katsotaanpa, tietenkin, valitse 3. Nyt ehdokkaat ovat 4 vasemmalla, 5 oikealla. Me tietenkin valita 4. 6 vasemmalla, 5 oikealla. Me tietenkin valita 5. 6 vasemmalla, 7 oikealla. Valitsemme 6, ja sitten me valita 7, ja sitten päätämme 8. Voila. Joten valtava määrä sanoja myöhemmin, me ovat lajiteltu tämä lista kahdeksan toiminnallisuutta listaan ​​yhden kautta kahdeksan, joka on kasvaa jokaisessa vaiheessa, mutta kuinka paljon aikaa ja teki se vie meidät siihen. No Olen tarkoituksella laid asioita kuvallisesti täällä, jotta voimme tavallaan nähdä tai arvostaa divisioona valloittavat että on tapahtunut. Todellakin jos muistella vanavedessä, Olen jättänyt kaikki nämä pisteviivoilla paikallaan haltijoille, voit, sellainen, katso, päinvastaisessa järjestyksessä, jos sellainen muistella historia nyt, minun alkuperäinen lista on, tietenkin, koon 8. Ja sitten aikaisemmin, olin käsittelevät kaksi luetteloa koko 4, ja sitten neljä luettelot koko 2, ja sitten kahdeksan luettelot koko 1. Mitä tämä, sellainen, muistuttaa teitä? Hyvin, itse asiassa, mitä tahansa algoritmit olemme Katsoin toistaiseksi jossa jakaa, ja jakaa, ja jakaa, pitää ottaa asioita uudelleen, ja jälleen, johtaa tämä yleinen ajatus. Ja niin siellä on jotain logaritminen tekeillä. Ja se ei ole aivan loki n, mutta siellä on logaritminen komponentti mitä olemme juuri tehneet. Nyt pohtia, miten se todella on. Joten log n, taas oli suuri käyntiaika, kun teimme jotain binäärihakupuu, kuten me nyt kutsumme sitä, hajota ja hallitse strategia jonka kautta löysimme Mike Smith. Nyt teknisesti. Se on log pohja 2 n, jopa vaikka useimmissa matematiikka luokissa, 10 on yleensä pohja että oletat. Mutta tietotekniikan tutkijoita lähes aina ajatella ja puhutaan pohja 2, joten me yleensä vain sanoa loki n, sen sijaan, että tukin pohjaan 2 n, mutta ne ovat täsmälleen yksi ja Sama maailmassa tietokone tiede, ja syrjään, on jatkuva tekijä Ero näiden kahden välillä, joten se on kiistanalainen joka tapauksessa, enemmän muodollista syistä. Mutta nyt, mitä me välitämme Tietoja on tässä esimerkissä. Joten ei osoittaa esimerkkiä, mutta Ainakin käyttää esimerkiksi numeroita käsillä järki tarkistaa, jos haluatte. Joten aiemmin kaava oli log pohja 2 n, mutta mikä on n tässä asiassa. Minulla oli n alkuperäinen numeroita tai 8 Alkuperäisen numero erityisesti. Nyt se on ollut hieman vaikka, mutta olen melko Varmista, että log pohja 2 arvo 8 on 3, ja todellakin, mitä kiva siitä on että 3 on juuri monta kertaa että voit jakaa lista pituuden 8 uudestaan, ja uudestaan, ja uudelleen, kunnes olet jäänyt luettelot vain koko 1. Oikea? 8 menee 4, menee 2, menee 1, ja se on heijastava nimenomaan kyseisen kuva meillä oli vain hetki sitten. Niin vähän järki tarkistaa, missä logaritmi on todella mukana. Joten nyt, mitä muuta on mukana tässä? n. Niin huomaa, että jokainen kerta kun jakaa luettelon, vaikkakin käänteisessä järjestyksessä historiassa täällä, olin vielä tekemässä n asioita. Että sulautuvan vaihe edellytti, että Kosketan jokainen numeroita, jotta työnnä se sen sopivaan paikkaan. Joten vaikka korkeus tämän kaavio on koko lokin n n tai 3, Erityisesti, toisin sanoen, Tein kolme divisioonaa täällä. Kuinka paljon työtä minä tein vaakasuunnassa pitkin tämä kaavio joka kerta? No, tein n vaiheet työtä, koska jos olen sai neljä elementit ja neljä elementtiä, ja minun täytyy yhdistää ne yhteen. Minun täytyy mennä läpi nämä neljä ja nämä neljä, lopulta yhdistää ne takaisin kahdeksan elementtejä. Jos päinvastoin Minulla kahdeksan sormea tänne, jota en ole, ja kahdeksan fingers-- sorry--, jos olen sai neljä sormea ​​tänne, jota en, neljä sormea tänne, jota en, niin se sama Esimerkiksi kuten ennenkin, jos en on kahdeksan sormea ​​vaikka yhteensä, jota voin, sellainen, do. Voin tarkalleen tehdä täällä, Sitten voin varmasti yhdistää kaikki nämä luettelot on koko 1 yhdessä. Mutta en todellakaan tarvitse katsoa kunkin alkion tasan kerran. Joten korkeus tämä prosessi on loki n, leveys tämän prosessin, niin sanoakseni, on n, niin mitä me näytämme on, lopulta, on ajoaika koko n kertaa log n. Toisin sanoen, jaoimme lista, log n kertaa, mutta joka kerta teimme että meillä oli koskettaa jokainen elementtien jotta yhdistää ne kaikki yhdessä, jotka oli n kappaletta askel, joten meillä on n kertaa log n, tai tietojenkäsittelytieteessä sanoisi, asymptoottisesti, joka olisi iso sana kuvaamaan ylempään sidottu aika, meillä on käynnissä iso O log n aikaa, niin sanoakseni. Nyt tämä on merkittävä, koska muistaa, mitä käynnissä ajat olivat kupla lajitella, ja valinta lajitella, ja lisäyslajittelun, ja jopa muutamia muita olemassa, n potenssiin oli kun olimme. Ja voit, tavallaan, katso täällä. Jos n potenssiin on selvästi n kertaa n, mutta täällä meillä on n kertaa log n, ja tiedämme jo viikko nolla, että log n, logaritminen, on parempi kuin jotain lineaarinen. Onhan muistaa kuva kanssa punainen ja keltainen ja vihreät viivat että me kiinnitti, vihreä logaritminen linja oli paljon pienempi. Ja siksi, paljon paremmin ja nopeammin kuin suora keltainen ja punainen linjat, n kertaa log n on todellakin parempi kuin n kertaa n, tai n neliö. Joten meillä näyttää tunnistettu algoritmi yhdistämisen lajitella, joka toimii paljon lyhyemmän ajan, ja todellakin, siksi, aiemmin tällä viikolla, kun näimme että kilpailun välillä kupla lajitella, valinta lajitella, ja yhdistää lajitella, yhdistäminen lajitella todella, todella voitti. Ja todellakin, emme edes odota varten kuplalajittelu ja valinta lajitella saada valmiiksi. Nyt ottaa yksi muu syöttö tässä, mistä hieman muodollinen näkökulmasta, vain tapauksessa tämä resonoi paremmin kuin tämän korkeamman tason keskustelu. Joten tässä on algoritmi uudelleen. Katsotaanpa kysyä itseltämme, mitä käyntiaika on tämän algoritmit eri vaiheet? Katsotaanpa se jaetaan ensimmäiseen tapaus ja toisessa tapauksessa. IF ja muu IF tapauksessa, Jos N on pienempi kuin 2, palaa. Tuntuu vakio aikaa. Se on, tavallaan, kuten kahdessa vaiheessa, Jos n on pienempi kuin 2, palaa sitten. Mutta kuten sanoi maanantaina, vakio aikaa, tai Big O 1, voi olla kahdessa vaiheessa, kolme vaiheet, jopa 1000 askelta. Tärkeintä on, että se on jatkuva useita vaiheita. Joten keltainen korostettu pseudokoodina täällä toimii, me kutsumme sitä, vakio aikaa. Joten enemmän virallisesti, ja aiomme to-- tämä on se, missä määrin me virallistaa tämän oikeuden now-- T n, ajoaika ongelma joka vie n somethings syötteenä Yhtä suuri O yhden, Jos n on pienempi kuin 2. Joten on edellytyksenä, että. Joten olla selkeä, jos n on pienempi kuin 2, meillä on hyvin lyhyt lista, sitten ajoaika, T, n, missä n on 1 tai 0, tässä hyvin erityinen tapaus, se vain tulee olemaan vakio aikaa. Se tulee ottaa yksi vaihe, kaksi vaihetta riippumatta. Se on kiinteä useita vaiheita. Niin mehukas osa on varmasti vuonna Toisessa tapauksessa vuonna pseudokoodina. ELSE tapaus. Lajittele vasemmalla puolella elementtejä, lajitella oikea puolet elementtejä, yhdistää lajiteltu puolikkaat. Kuinka kauan kukin näistä askeleensa? No, jos käynnissä aika lajitella n elementtiä on, kutsukaamme sitä hyvin yleisesti, T, n, sitten lajittelu vasen puolet elementit on, tavallaan, kuin sanoisi, T n jaettuna 2, ja samoin lajittelu oikea puoli elementtejä on, sellainen, kuin sanoisi, T n jaettu 2, ja sitten yhdistämällä lajiteltu puolikkaat. No jos minulla joitakin alkioiden lukumäärä täällä, kuten neljä, ja jotkut numero elementtejä täällä, kuten neljä, ja minun täytyy yhdistää kuhunkin neljään vuonna, ja jokainen näistä neljä, yksi toisensa jälkeen siten, että lopulta minulla on kahdeksan elementtejä. Tuntuu, että on iso o n vaiheet? Jos Minulla n sormien ja kukin ne on tarkoitus sisällyttää paikalleen, se on kuin toinen n vaiheet. Joten todellakin formulaically, Voimme ilmaista tämän, vaikkakin hieman pelottavan aluksi silmäyksellä, mutta se on jotain että kaappaa juuri tätä logiikkaa. Juokseva aika, T, n, jos n on suurempi tai yhtä suuri kuin 2. Tässä tapauksessa, MUUTEN tapauksessa on T n jaettuna 2, sekä T N jaettuna 2, plus Big O n, jotkut lineaarinen useita vaiheita, ehkä täsmälleen n, ehkä 2 kertaa n, mutta se on karkeasti, jotta n. Niin että myös, miten voimme ilmaista tämä formulaically. Nyt et tiedä tätä, ellei olet tallentanut sen mielessäsi, tai etsiä se takana oppikirja, joka saattaa olla hieman huijata arkki lopussa, mutta tämä on todellakin menossa antaa meille iso O n log n, koska toistumisen että näette täällä ruudulla, jos todella teki sen ulos, kanssa ääretön määrä esimerkkejä, tai teit sen formulaically, olisit nähdä, että tämä, koska tämä kaava itsessään on rekursiivinen, jossa t n yli jotain oikealla, ja t N yli vasemmalla, tämä voi todella ilmaistava, lopulta, niin suuri irti n log n. Jos ei vakuuttunut, että on hieno nyt, vain ottaa uskossa, että se on todellakin, mitä se toistuminen johtaa, mutta tämä on vain hieman enemmän matemaattinen lähestymistapa näköinen klo ajoaika yhdistämisen sort perustuvat sen pseudokoodilla yksin. Nyt kestää vähän hengähdystauon kaiken tämän, ja katsomaan tiettyjä entinen senaattori, joka saattaa näyttää hieman tuttu, joka istui Googlen Eric Schmidt, jokin aika sitten, haastatteluun lavalla, edessä koko joukko ihmiset, puhuvat lopulta noin aihe, joka on aika nyt tuttu. Katsotaanpa katsomaan. Eric Schmidt: Nyt senaattori, olet täällä Googlessa, ja haluan ajatella puheenjohtajuudesta työhaastattelu. Nyt on vaikea saada työtä presidenttinä. Presidentti Obama: Oikea. Eric Schmidt: Ja olet aikoo tehdä [kuulumattomiin] nyt. On myös vaikea saada työtä Google. Presidentti Obama: Oikea. Eric Schmidt: Meillä on kysymyksiä, ja pyydämme ehdokkaita kysymyksiä, ja tämä yksi on Larry Schwimmer. Presidentti Obama: OK. Eric Schmidt: Mitä? Te ajatella olen tosissasi? Se on täällä. Mikä on tehokkain tapa lajitella miljoona 32 bittisiä kokonaislukuja? Presidentti Obama: Well-- Eric Schmidt: Joskus ehkä olen pahoillani, maybe-- Presidentti Obama: Ei, ei, ei, ei, ei, minä think-- Eric Schmidt: Se ei ole it-- Presidentti Obama: I ajatella, mielestäni kupla lajitella olisi väärä tapa edetä. Eric Schmidt: Tule. Jotka kertoivat hänelle tämän? OK. En tietojenkäsittelytieteen on-- Presidentti Obama: Olemme saimme vakoojia siellä. PROFESSORI: Selvä. Jätetään taaksemme nyt teoreettinen maailma algoritmien vuonna asymptoottinen analyysi sen, ja palata joitakin aiheita viikosta nolla ja yksi, ja alku poistaa joitakin apupyörät, jos haluatte. Niin että te todella ymmärtää lopulta maasta ylös, mitä meneillään alla huppu, kun kirjoittaa, kääntää, ja suorittaa ohjelmia. Recall erityisesti, että tämä oli ensimmäinen C-ohjelma me katsoimme, Canonical, yksinkertainen ohjelma tapaisena suhteellisesti jolloin se tulostaa, Hello World. Ja muistaa, että minä sanoin, prosessi että lähdekoodi menee läpi on juuri tämä. Otat lähdekoodia, siirtää se läpi kääntäjä, kuten kalahtaa, ja ulos tulee kohdekoodin, että voisi näyttää tältä, nollia ja ykkösiä että tietokoneen prosessoria, keskeinen käsittely-yksikön tai aivoissa, lopulta ymmärtää. On käynyt ilmi, että se on vähän yksinkertaistamista, että olemme nyt kanta kiusanhenki toisistaan ymmärtää, mitä on todella ollut meneillään alla huppu aina käyttää Sointi, tai yleisemmin, aina kun teet ohjelmaa, käyttämällä Tee ja CF 50 IDE. Erityisesti tavaraa kuten tämä on ensin luotu, kun ensin kääntää ohjelma. Toisin sanoen, kun ota lähdekoodi ja kääntää se, mikä on ensimmäinen on ulostulevien kalahtaa on jotain tunnetaan kokoonpano koodi. Ja itse asiassa se näyttää täsmälleen samalta kuin tämä. Juoksin komento komentoriviltä aikaisemmin. Kalahtaa viiva pääoma s hello.c, ja tämä loi tiedosto minulle kutsutaan hello.s, jonka sisällä olivat täsmälleen näitä pitoisuuksia, ja hieman enemmän yläpuolella ja hieman alle, mutta olen koonnut juiciest tietoa täältä ruudulla. Ja jos katsot tarkkaan, näet ainakin muutamia tuttuja avainsanoja. Olemme tärkein ylhäällä. Olemme printf alas keskellä. Ja meillä on myös Hello World kenoviiva n lainausmerkkeihin alhaalla. Ja kaikki muu täällä on hyvin alhainen ohjeet että tietokoneen prosessoria ymmärtää. CPU ohjeet, jotka liikkuvat muisti ympäri, jonka painon jouset muistista, ja lopulta, tulostaa asiat näytöltä. Nyt mitä tapahtuu vaikka jälkeen tämä kokoonpano koodi luodaan? Lopulta teet, todellakin, silti tuottaa kohdekoodilla. Mutta toimenpiteet, jotka ovat todella jatkunut alla huppu näyttää hieman enemmän kuin tämä. Lähdekoodi tulee kokoonpano koodi, joka sitten tulee kohdekoodin, ja operatiiviset sanat tässä on että, kun käännät lähdekoodin, ulos tulee kokoonpano koodi, ja sitten kun Kokoa kokoonpano koodi, ulos tulee kohdekoodilla. Nyt kalahtaa on erittäin hienostunut, kuten paljon kerääjiä, ja se tekee kaikki nämä vaiheet yhdessä, ja se ei välttämättä ulostulo välivaiheen tiedostoja, jotka voit jopa nähdä. Se vain kokoaa asioita, joka on yleinen termi, joka kuvaa tätä koko prosessia. Mutta jos todella haluat olla erityisesti siellä paljon enemmän tekeillä myös siellä. Mutta katsotaanpa myös katsovat nyt, että jopa että super yksinkertainen ohjelma, hello.c, kutsutaan toimintoa. Se kutsutaan printf. Mutta en kirjoita printf, todellakin, mukana C, niin sanoakseni. Se on toiminto muistaa, joka on ilmoitettu standardin io.h, joka on header-tiedosto, joka on aihe me oikeastaan sukeltaa perusteellisemmin ennen pitkää. Mutta otsikkotiedosto on tyypillisesti mukana koodilla tiedoston, lähdekooditiedostoa, joten paljon kuin on olemassa standardi io.h. Joskus sitten, joku, tai jonkun, myös kirjoitti tiedosto nimeltä standardi io.c, vuonna jonka todellinen määritelmät, tai toteutukset printf, ja rypäleterttuja muita toimintoja, todella kirjoitettu. Niin sillä, jos me harkita täällä vasemmalla, hello.c, että kun koottu, antaa meille hello.s, vaikka Kalahtaa ei vaivaudu säästö paikka voimme nähdä sen, ja että assembly saa kootaan hello.o, joka on todellakin oletusnimi annetaan aina käännät lähde koodi kohdekoodi, mutta eivät aivan valmis suorittamaan sitä vielä, koska toinen vaihe pitää tapahtua, ja on on tapahtunut muutaman viime viikkoa, ehkä tietämättään sinua. Erityisesti jonnekin vuonna CS50 IDE, ja tämä, Myös, on vähän yksinkertaistava hetkeksi, siellä on, tai oli upon a time, tiedosto nimeltä standardi io.c, että joku käännetty standardi io.s tai vastaava, että joku sitten koottu standardiin io.o, tai se kääntyy ulos hieman erilainen tiedosto muodossa, joka voi olla erilainen tiedostopääte kokonaan, mutta teoriassa ja käsitteellisesti, täsmälleen nämä toimenpiteet täytyi tapahtua jossain muodossa. Joka on sanoa, että nyt kun olen kirjallisesti ohjelma, hello.c, että vain sanoo, Hello World, ja olen käyttäen jonkun toisen koodi kuten printf, joka oli aikoinaan päällä aika, tiedostossa nimeltä standardi io.c, sitten jotenkin minun on otettava minun kohdekoodi, minun nollia ja ykkösiä, ja että henkilön esine koodi tai nollia ja ykkösiä, ja jotenkin yhdistää ne yksi lopullinen tiedosto, nimeltään Hei, että on kaikki nollia ja niistä minun päätehtävä, ja kaikki nollia ja ne, printf. Ja todellakin, että viime prosessi on nimeltään, liität kohdekoodilla. Jonka lähtö on suoritettava tiedosto. Joten tasapuolisuuden on päivän päätteeksi, ei mitään on muuttunut viikolla yksi, kun aloitti kokoamiseen ohjelmia. Itse asiassa tämä kaikki on ollut tapahtuu alla huppu, mutta nyt olemme asemassa jossa voimme todella tease lisäksi nämä eri vaiheet. Ja itse asiassa lopussa päivä, olemme yhä jää nollia ja ykkösiä, joka on todella suuri segue nyt Toinen ominaisuus C, että olemme ole tarvinnut hyödyntää todennäköisesti Tähän mennessä tunnetaan bittioperaatioiden. Toisin sanoen, toistaiseksi, milloin olemme Puhuttiin tietojen C tai muuttujiin C, meillä on ollut asioita, kuten merkkiä ja kellukkeet ja laajennukset ja pitkät ja kaksinkertaistuu ja vastaavat, mutta kaikki nämä ovat vähintään kahdeksan bittiä. Emme ole koskaan vielä ole voinut manipuloida yksittäisiä bittejä, vaikka yksittäisen vähän, me tietää, voi edustaa 0 ja 1. Nyt näyttää siltä, ​​että C, sinua voi päästä käsiksi yksittäisiä bittejä, jos tiedät syntaksin, jolla saada niitä. Joten katsomaan klo bittioperaatioiden. Joten Kuvassa on muutamia symboleja, olemme, tavallaan, tavallaan, ennen nähty. Näen et-merkki, pystysuora baari, ja jotkut muut samoin, ja muistuttavat, että et-merkki et-merkki on jotain olemme nähneet aiemmin. Looginen AND-operaattori, jossa sinulla on kaksi niistä yhdessä tai looginen TAI operaattori, jossa on kaksi pystypalkkia. Bittioperaatioiden, joka käymme katso toimivat bittiä erikseen, vain käyttää yksi et-merkki, yksi pystysuora palkki, sirkumfleksi symboli tulee seuraavaksi, pieni tilde, ja sitten vasemmalle kannatin vasen kannatin, tai oikea kannatin oikea kiinnike. Kukin näistä on eri merkitykset. Itse asiassa, nyt katsomaan. Mennään vanhan koulun tänään, ja käyttö kosketusnäyttö menneiden, tunnetaan valkoinen levy. Ja tämä valkoinen lauta aikoo antaa meille ilmaista joitakin melko yksinkertaisia ​​symboleita, tai pikemminkin joitakin melko yksinkertaisia ​​kaavoja, että voimme lopulta vipuvaikutus, jotta pääsyn yksittäisiä bittiä C-ohjelma. Toisin sanoen, tehdään tämä. Katsotaanpa ensin puhua varten hetki et-merkki, joka on peiton ja Operaattori. Toisin sanoen, tämä on operaattori, jonka avulla minulle on vasen muuttuja tyypillisesti, ja oikea muuttuja, tai yksittäinen arvo, että jos me ja ne yhteen, antaa minulle lopputulokseen. Joten mitä minä tarkoitan? Jos ohjelma, sinulla on muuttuva että tallentaa yhden näistä arvoista, tai katsotaanpa pitää asiat yksinkertaisina, ja vain kirjoittaa nollia ja ykkösiä erikseen, tässä miten -merkki operaattori toimii. 0 Ampersand 0 tulee yhtä 0. Nyt Miksi? Se on hyvin samankaltainen Boolen operaattoreilla, että olemme keskustelleet tähän asti. Jos luulet onhan 0 on väärä, 0 on väärä, väärä ja vääriä on, kuten olemme keskustelleet loogisesti, myös väärä. Jotta saamme 0 myös täällä. Jos otat 0 ampersand 1, hyvin, että myös tulee olemaan 0, koska tämä vasen ilmaisun olevan totta tai 1, sen pitäisi olla totta ja totta. Mutta tässä meillä on väärä ja totta, tai 0 ja 1. Nyt uudelleen, jos meillä on 1 ampersand 0, sekin tulee olemaan 0, ja jos meillä on 1 et-merkki 1, Lopuksi meillä on 1 bit. Eli toisin sanoen, me emme tee mitään mielenkiintoista tämän operaattorin vain vielä, tämä Ampersand operaattori. Se peiton ja Operaattori. Mutta nämä ovat ainekset jonka kautta voimme tehdä mielenkiintoisia asioita, kuten tulemme pian nähdä. Nyt katsokaamme vain yhden pystyviiva tänne oikealla. Jos minulla on 0 vähän ja minä TAI se, bittivastineen OR operaattori, toinen 0 bit, joka tulee antamaan minulle 0. Jos otan 0 vähän ja OR sen 1 vähän, niin aion saada 1. Ja itse asiassa, vain selkeys, anna minun mennä takaisin, niin että minun pystypalkki ei erehtynyt 1: n. Saanen uusia koko minun 1 on hieman enemmän selvästi, jotta voimme ensi nähdä, jos en on 1 tai 0, joka tulee olemaan 1, ja jos minulla on 1 tai 1 että, Myös tulee olemaan 1. Voit siis nähdä loogisesti että TAI operaattori käyttäytyy hyvin eri tavalla. Tämä antaa minulle 0 tai 0 antaa minulle 0, mutta joka toinen yhdistelmä antaa minulle 1. Niin kauan kuin minulla on yksi 1 kaava, tulos tulee olemaan 1. Toisin JA operaattori, et-merkki, vain jos minulla on kaksi 1: n yhtälö, voin itse saada 1 ulos. Nyt on olemassa muutamia muita toimijat samoin. Yksi niistä on hieman enemmän mukana. Joten anna minun mennä eteenpäin ja poistaa tämä vapauttaa levytilaa. Ja lähdetään katsomaan caret symboli, vain hetken. Tämä on tyypillisesti merkki voit kirjoittaa näppäimistön SHIFT ja sitten yksi numerot huipulla oman US näppäimistö. Joten tämä on yksinomainen OR operaattori, eksklusiivinen TAI. Joten me vain näimme tai toiminnanharjoittaja. Tämä on eksklusiivinen OR operaattori. Mitä oikeastaan ​​eroa? No katsotaanpa katsokaa kaava, ja käyttää tätä ainesosina lopulta. 0 XOR 0. Aion sanoa on aina 0. Se määritelmä XOR. 0 XOR 1 tulee olemaan 1. 1 XOR 0 tulee olemaan 1, ja 1 XOR 1 tulee olemaan? Väärässä? Tai oikea? Minä en tiedä. 0. Nyt mitä on tekeillä? No ajattele Nimi tämän operaattorin. Eksklusiivinen OR, jotta nimi, ehdottaa, vastaus on vain olemaan 1 jos tulot ovat yksin, yksinomaan eri. Joten tässä tulot ovat sama, joten tuotos on 0. Tässä tulot ovat sama, joten tuotos on 0. Tässä ovat lähdöt ovat erilaisia, ne ovat yksin, ja niin lähtö on 1. Joten se on hyvin samankaltainen Ja se on hyvin samankaltainen, tai pikemminkin se on hyvin samankaltainen TAI, mutta vain yksinomainen tavalla. Tämä ei ole enää 1, koska meillä on kaksi 1 n, ja ei yksinomaan, vain yksi niistä. Selvä. Entä muut? No tilde puolestaan ​​on todella mukava ja yksinkertainen, onneksi. Ja tämä on unary operaattorin, joka tarkoittaa se on sovellettu ainoastaan ​​yhteen tulo, yksi operandi, niin sanoakseni. Ei vasemmalle ja oikealle. Toisin sanoen, jos otat tilde of 0, vastaus on päinvastainen. Ja jos otat tilde 1, vastaus tulee olemaan päinvastainen. Joten tilde operaattori on tapa tyhjäksi hieman, tai käännetään verran 0-1 tai 1-0. Ja että jättää meidät vihdoin vain kaksi viimeistä toimijoiden, ns vasemmalla muutos, ja ns oikealla shift operaattori. Katsotaanpa katsomaan miten nämä työssä. Vasemmalle siirtyminen operaattori, kirjallinen kaksi kulmakiinnikkeet niin, toimii seuraavasti. Jos minun panos, tai minun operandi, vasemmalle shift operaattori on yksinkertaisesti 1. Ja minä sitten kertoa tietokoneen vasen shift että 1, sanovat seitsemän paikkoja, tulos on kuin olisin ottaa tämän 1, ja siirrä se seitsemän paikkoja yli vasemmalle, ja oletuksena, aiomme olettaa, että tilaa oikealle aiotaan nollilla. Toisin sanoen, 1 vasen muutos 7 on menossa antaa minulle, että 1, jonka jälkeen 1, 2, 3, 4, 5, 6, 7 nollia. Joten tavallaan, sen avulla voit ottaa pieni määrä kuten 1, ja selvästi on paljon paljon, paljon suurempi tällä tavalla, mutta me todella tulee nähdä viisaampi lähestymistapoja se sen sijaan, samoin, Selvä. Se on siinä viikolla kolme. Tulemme näkemään ensi kerralla. Tämä oli CS50. [Musiikkia] SPEAKER 1: Hän oli välipala baari syöminen kuuma tuhertaa jäätelöannos. Hänellä oli se koko hänen kasvonsa. Hän on päällään, että suklaa kuten parta SPEAKER 2: Mitä sinä teet? SPEAKER 3: Hmmm? Mitä? SPEAKER 2: Oletko juuri double dip? Voit kaksinkertainen kastetaan siru. SPEAKER 3: Anteeksi. SPEAKER 2: Sinä kastettu siru, sinä otti purra, ja te kastetaan uudelleen. SPEAKER 3: SPEAKER 2: Niin, että kuin laittaisi koko suu aivan dip. Seuraavan kerran otat siru, vain kasta se kerran, ja lopettaa sen. SPEAKER 3: Tiedätkö mitä, Dan? Voit pulahtaa tavalla haluat pulahtaa. Minä dip tapa, että haluan notkahdus.