DAVID MALAN: Baiklah. Kita kembali. Jadi, dalam segmen ini pengaturcaraan apa Saya fikir kita akan lakukan adalah campuran perkara. Satu, melakukan sedikit sesuatu yang tangan-on, walaupun menggunakan lebih suka bermain program environment-- satu yang demikian menggambarkan betul-betul jenis idea kita telah bercakap tentang, tetapi sedikit lebih secara rasmi. Kedua, melihat beberapa cara-cara yang lebih teknikal bahawa programmer sebenarnya akan menyelesaikan masalah seperti masalah mencari bahawa kita melihat sebelum dan juga lebih asas masalah yang menarik sorting. 

Kami hanya menganggap dari mendapatkan pergi bahawa buku telefon telah disusun, tetapi itu sahaja sebenarnya jenis yang masalah keras dengan pelbagai cara untuk menyelesaikannya. Oleh itu, kita akan menggunakan ini sebagai kelas masalah wakil perkara-perkara yang mungkin perlu diselesaikan secara umum. Dan kemudian kita akan bercakap mengenai dengan terperinci apa dipanggil data structures-- cara pelamun seperti senarai berkaitan dan jadual hash dan pokok-pokok yang programmer akan sebenarnya digunakan dan biasanya menggunakan pada papan putih untuk cat gambar apa yang dia bermatlamat untuk melaksanakan beberapa perisian. 

Jadi mari kita buat tangan-pada bahagian pertama. Jadi hanya mendapatkan tangan anda kotor dengan persekitaran dipanggil scratch.mit.edu. Ini adalah alat yang kita gunakan dalam kelas ijazah pertama kami. Walaupun ia direka untuk peringkat umur 12 dan ke atas, kita menggunakannya untuk sehingga sebahagian daripada yang agak sedikit kerana ia adalah yang baik, menyeronokkan cara grafik pengajian sesuatu yang sedikit tentang pengaturcaraan. Jadi menuju ke URL yang, di mana anda perlu melihat halaman yang agak seperti ini, dan pergi ke depan dan klik Sertai Scratch di sebelah kanan atas dan memilih nama pengguna dan kata laluan dan akhirnya mendapatkan diri anda yang scratch.mit.edu account--. Saya fikir saya akan menggunakan ini sebagai peluang pertama untuk menunjukkan ini. Soalan yang datang semasa rehat tentang apa kod sebenarnya kelihatan seperti. Dan kita bercakap semasa rehat mengenai C, khususnya-- terutamanya yang tahap yang lebih rendah dalam bahasa yang lebih tua. Dan saya hanya melakukan yang cepat Carian Google untuk mencari kod C untuk carian binari, algoritma yang kita digunakan untuk mencari buku telefon sebelum ini. Ini contoh tertentu, sudah tentu, tidak mencari buku telefon. Ia hanya mencari sejumlah besar nombor dalam ingatan komputer. Tetapi jika anda hanya ingin mendapatkan visual rasa apa pengaturcaraan sebenar bahasa kelihatan seperti, ia kelihatan sesuatu yang kecil seperti ini. Jadi ia adalah kira-kira 20-plus, 30 atau lebih baris kod, tetapi perbualan kita telah mempunyai lebih rehat adalah kira-kira bagaimana ini sebenarnya mendapat berubah menjadi sifar dan satu dan jika anda tidak boleh hanya kembali yang memproses dan pergi dari sifar dan satu belakang untuk kod. 

Malangnya, proses begitu transformatif bahawa ia adalah lebih mudah berkata daripada dilakukan. Saya pergi ke hadapan dan benar-benar bertukar program itu, Binary Search, ke sifar dan orang-orang yang melalui program dipanggil pengkompil bahawa saya berlaku kepada ada di kanan pada Mac saya. Dan jika anda melihat skrin di sini, memberi tumpuan khusus di Syarikat-pertengahan enam tiang sahaja, anda hanya akan melihat sifar dan satu. Dan mereka adalah sifar dan orang-orang yang mengarang tepat bahawa program pencarian. 

Dan sebagainya setiap sebahagian daripada lima bit, setiap bait sifar dan satu di sini, mewakili beberapa arahan biasanya dalam komputer. Dan sebenarnya, jika anda telah mendengar slogan pemasaran "Intel dalam" - iaitu, sudah tentu, hanya bermakna anda mempunyai yang Intel CPU atau otak dalam komputer. Dan apa yang bermakna untuk menjadi CPU adalah bahawa anda mempunyai set arahan, boleh dikatakan. 

Setiap CPU di dunia, banyak mereka dibuat oleh Intel hari ini, memahami yang terhad beberapa arahan. Dan orang-arahan adalah tahap begitu rendah sebagai menambah kedua-dua nombor bersama-sama, darabkan kedua-dua nombor bersama-sama, bergerak sekeping data dari sini ke sini dalam ingatan, menyimpan ini maklumat dari sini ke sini dalam ingatan, dan sebagainya forth-- begitu sangat, sangat peringkat rendah, butiran hampir elektronik. Tetapi dengan orang-orang matematik operasi ditambah dengan apa yang kita dibincangkan sebelum ini, perwakilan data sebagai sifar dan satu, boleh anda membina segala-galanya yang komputer boleh lakukan hari ini, sama ada ia teks, grafik, muzik, atau sebaliknya. 

Jadi ini adalah sangat mudah untuk mendapatkan hilang dalam rumpai daripada cepat. Dan ada banyak cabaran sintaksis di mana jika anda membuat yang paling mudah, bodoh daripada kesilapan menaip tiada program akan bekerja sekalipun. Dan sebagainya dan bukannya menggunakan bahasa seperti C pagi ini, Saya fikir ia akan menjadi lebih seronok untuk benar-benar melakukan sesuatu yang lebih visual, yang manakala yang direka untuk kanak-kanak sebenarnya manifestasi yang sempurna suatu program sebenar language-- hanya berlaku untuk menggunakan gambar bukan teks untuk mewakili idea-idea. 

Jadi apabila anda memang mempunyai akaun pada scratch.mit.edu, klik butang Buat di bahagian kiri laman web ini. Dan anda akan dapat melihat persekitaran seperti yang saya kira-kira untuk melihat pada skrin saya di sini. Dan kita akan menghabiskan hanya sedikit sedikit masa bermain di sini. Mari kita lihat jika kita tidak boleh semua menyelesaikan beberapa masalah bersama-sama dengan cara yang berikut. 

Jadi apa yang anda akan lihat di ini environment-- dan sebenarnya hanya membiarkan saya berhenti seketika. Adakah sesiapa yang tidak di sini? Bukan disini? OKEY. Jadi biarlah saya menunjukkan beberapa ciri-ciri persekitaran ini. 

Jadi pada sebelah kiri atas skrin, kita mempunyai peringkat awal, jadi untuk bercakap. Scratch adalah bukan sahaja nama bahasa pengaturcaraan ini; ia juga nama kucing yang anda lihat dengan lalai terdapat dalam oren. Dia berada di atas pentas, jadi sama seperti saya sebut penyu lebih awal sebagaimana yang berada dalam persekitaran papan putih segi empat tepat. Dunia ini kucing dikurung sepenuhnya dengan yang segi empat tepat sehingga atas sana. 

Sementara itu, di sebelah kanan sebelah sini, ia hanya kawasan skrip, yang sabak kosong jika anda akan. Ini adalah di mana kita akan menulis program kami dalam hanya seketika. Dan pembinaan usaha kita hendaklah gunakan untuk menulis ini program-- teka-teki keping, jika anda will-- adalah orang-orang di sini di tengah-tengah, dan mereka dikategorikan oleh fungsi. Jadi, sebagai contoh, saya akan pergi ke hadapan dan menunjukkan sekurang-kurangnya salah satu daripada. Saya akan pergi ke hadapan dan klik kategori Kawalan sehingga atas. 

Jadi ini adalah kategori sehingga atas. Saya akan klik kategori Kawalan. Sebaliknya, saya akan klik Events kategori, satu sehingga bahagian yang pertama. Dan jika anda ingin untuk ikut bersama-sama walaupun seperti yang kita lakukan ini, anda agak selamat datang ke. Saya akan klik dan tarik ini Yang pertama, "apabila bendera hijau diklik." Dan kemudian saya akan menjatuhkannya hanya secara kasar di bahagian atas papan tulis kosong saya. 

Dan apa yang baik tentang Scratch ialah sekeping teka-teki ini, apabila berinteraksi dengan teka-teki yang lain keping, akan melakukan secara literal apa yang orang-orang keping teka-teki patut dilakukan. Jadi, sebagai contoh, Scratch adalah betul kini di pertengahan dunianya. Saya akan pergi ke hadapan dan memilih sekarang, katakan, kategori Motion itu, jika anda ingin melakukan same-- kategori Motion. Dan kini melihat Saya mempunyai keseluruhannya sekumpulan kepingan teka-teki di sini bahawa, sekali lagi, jenis melakukan apa yang mereka katakan. Dan saya akan pergi ke hadapan dan tarik dan drop blok langkah yang betul di sini. 

Dan perhatikan bahawa sebaik sahaja anda berhampiran dengan bahagian bawah "bendera hijau klik "butang, notis bagaimana garisan putih muncul, seolah-olah ia hampir magnet, ia mahu pergi ke sana. Hanya melepaskan, dan ia akan snap bersama-sama dan bentuk akan sepadan. mungkin dan sekarang anda boleh hampir meneka di mana kita akan dengan ini. 

Jika anda lihat pada peringkat awal yang di sini dan melihat ke atas itu, anda akan melihat cahaya merah, berhenti tanda, dan bendera hijau. Dan saya akan pergi ke hadapan dan menonton screen-- saya hanya untuk seketika, jika anda boleh. Saya akan klik hijau bendera sekarang, dan beliau berpindah apa yang kelihatan sebagai 10 langkah atau 10 piksel, 10 titik, pada skrin. 

Dan sebagainya tidak yang menarik, tetapi biarlah saya mencadangkan tanpa mengajar ini, hanya menggunakan sendiri let intuition-- anda sendiri saya mencadangkan bahawa anda memikirkan bagaimana untuk membuat Scratch berjalan kaki kanan pentas. Adakah dia memberi laluan kepada sebelah kanan skrin, sepanjang jalan ke kanan. Biar saya memberi anda seketika atau supaya bertumbuk dengan itu. Anda mungkin mahu untuk melihat dengan pada kategori lain blok. Baiklah. Jadi, untuk mengulang, apabila kita mempunyai bendera hijau diklik di sini dan bergerak 10 langkah-langkah yang yang hanya arahan, setiap kali saya klik bendera hijau, apa yang berlaku? Well, yang menjalankan program saya. Jadi saya boleh melakukan ini mungkin 10 kali secara manual, tetapi ini berasa sedikit bit hackish, jadi untuk bercakap, di mana saya tidak benar-benar menyelesaikan masalah tersebut. Saya hanya mencuba sekali lagi dan lagi dan lagi dan lagi sehingga saya semacam sengaja mencapai arahan yang saya sasarkan untuk dicapai lebih awal. 

Tetapi kita tahu daripada kami pseudokod sebelum ini bahawa ada idea ini dalam pengaturcaraan gegelung, melakukan sesuatu lagi dan lagi. Oleh itu, saya melihat bahawa sekumpulan anda dihubungi untuk mendapatkan sekeping apa teka-teki? Ulangi sehingga. Oleh itu, kita boleh melakukan sesuatu seperti ulangi sehingga. Dan apa yang anda mengulangi sehingga betul-betul? 

OKEY. Dan biarlah saya pergi dengan satu yang agak lebih mudah untuk hanya seketika. Biar saya pergi ke hadapan dan melakukan ini. Perhatikan bahawa, kerana anda mungkin mempunyai ditemui di bawah kawalan, terdapat blok berulang ini, yang tidak kelihatan seperti ia yang besar. Ada tidak banyak ruang dalam antara kedua-dua garisan kuning. Tetapi sebagai sebahagian daripada anda mungkin mempunyai perasan, jika anda seret dan lepaskan, melihat bagaimana ia tumbuh untuk mengisi bentuk. 

Dan anda juga boleh mengasak lagi. Ia hanya akan terus berkembang jika anda menyeret dan berlegar di atasnya. Dan saya tidak tahu apa yang terbaik di sini, jadi mari saya sekurang-kurangnya mengulangi lima kali, untuk misalnya, dan kemudian kembali ke peringkat dan klik bendera hijau. Dan kini melihat ia tidak cukup di sana. 

Sekarang sebahagian dari kamu dicadangkan itu, mengikut Victoria hanya tidak, ulangi 10 kali. Dan yang biasanya tidak mendapatkan dia sepanjang jalan, tetapi tidak akan ada yang lebih mantap cara daripada sewenang-wenangnya memikirkan berapa banyak bergerak untuk membuat? Apa yang mungkin menjadi batu yang lebih baik daripada berulang 10 kali menjadi? 

Yeah, jadi mengapa tidak melakukan sesuatu yang selama-lamanya? Dan sekarang mari saya bergerak sekeping teka-teki ini dalam sana dan menghapuskan satu ini. Sekarang notis tidak kira di mana Scratch bermula, dia pergi ke tepi. Dan bersyukur kerana MIT, yang membuat Awal, hanya akan memastikan bahawa dia tidak pernah hilang sama sekali. Anda sentiasa boleh merebut ekornya. 

Dan hanya intuitif, mengapa dia terus bergerak? Apa yang sedang berlaku di sini? Dia seolah-olah telah berhenti, tetapi kemudian jika saya mengambil dan drag dia terus mahu pergi ke sana. Kenapa begitu? Sesungguhnya, komputer adalah benar-benar akan melakukan apa yang anda beritahu kepada lakukan. Jadi, jika anda memberitahu lebih awal melakukan berikut perkara selama-lamanya, bergerak 10 langkah, ia akan terus pergi dan pergi sehingga saya memukul tanda berhenti merah dan berhenti program ini sama sekali. 

Jadi, walaupun anda tidak melakukan ini, bagaimana boleh saya membuat Scratch langkah lebih cepat di skrin? Lebih langkah, bukan? Jadi, daripada melakukan 10 pada satu masa, mengapa tidak kita teruskan dan mengubahnya supaya- apa yang anda akan propose-- 50? Jadi sekarang saya akan klik hijau bendera, dan sesungguhnya, dia pergi dengan pantas. 

Dan ini, sudah tentu, adalah hanya manifestasi animasi. Apakah animasi? Ia hanya menunjukkan anda seorang manusia seluruh sekumpulan imej masih benar-benar, benar-benar, benar-benar cepat. Dan jadi jika kita hanya memberitahu beliau untuk bergerak lebih langkah-langkah, kami hanya mempunyai kesan yang sama adalah untuk perubahan di mana dia berada di atas skrin semua unit yang lebih cepat setiap masa. 

Sekarang cabaran seterusnya yang saya mencadangkan adalah untuk mempunyai dia melantun dari tepi. Dan tanpa mengetahui apa teka-teki keping exist-- kerana ia adalah baik jika anda tidak sampai ke peringkat challenge-- apa yang anda mahu lakukan intuitif? Bagaimana kita akan dia bangkit semula dan sebagainya, antara kiri dan kanan? 

Yeah. Oleh itu, kita perlu beberapa jenis keadaan, dan kami seolah-olah mempunyai conditional, jadi untuk berkata-kata, di bawah kategori Kawalan. Yang mana blok ini kita mungkin mahu? Ya, mungkin "jika, kemudian." Jadi notis bahawa di antara blok kuning kami ada di sini, ada ini "jika" atau ini "jika, lain" blok yang akan membolehkan kita untuk membuat keputusan untuk melakukan ini atau untuk berbuat demikian. walaupun dan anda dapat bersarang mereka untuk melakukan pelbagai perkara. Atau jika anda tidak pergi sini lagi, pergi ke depan untuk kategori Sensing yang dan- mari kita lihat jika ia di sini. 

Jadi apa blok mungkin dapat membantu di sini untuk mengesan jika dia pentas? Ya, perasan bahawa beberapa blok-blok boleh parametrized, jadi untuk bercakap. Mereka boleh bentuk disesuaikan, tidak tidak seperti HTML semalam dengan sifat-sifat, di mana mereka sifat-sifat jenis menyesuaikan tingkah laku tag. Begitu juga di sini, saya boleh merebut menyentuh ini blok dan perubahan dan bertanya soalan, yang anda menyentuh tetikus penunjuk seperti kursor atau yang anda menyentuh tepi? 

Jadi biarlah saya masuk dan melakukan ini. Saya akan zum keluar untuk seketika. Biar saya merebut sekeping teka-teki ini di sini, teka-teki sekeping ini, dan saya akan campurkannya mereka untuk hanya seketika. Saya akan bergerak ini, menukar ini ke tepi menyentuh, dan saya akan gerakan melakukan ini. Jadi di sini adalah beberapa bahan-bahan. Saya rasa saya telah mendapat segala-galanya yang saya mahu. 

Adakah seseorang suka untuk mencadangkan bagaimana saya boleh menyambung ini mungkin atas ke bawah untuk menyelesaikan masalah yang mempunyai Scratch langkah kanan ke kiri ke kanan untuk kiri ke kanan ke kiri, setiap masa hanya memantul dari dinding? Apa yang saya mahu lakukan? Blok yang perlu saya menyambung kepada "Bendera apabila hijau klik pertama"? 

OK, jadi mari kita mulakan dengan "selama-lamanya." Apa yang berlaku di dalam yang akan datang? Orang lain. OK, bergerak langkah. Baiklah. Kemudian apa? Sebab itu jika. Dan perhatikan, walaupun ia kelihatan diapit bersama-sama ketat, ia hanya akan berkembang untuk mengisi. Ia hanya akan melompat di mana saya mahu ia. 

Dan apa yang saya meletakkan antara jika dan ketika itu? Mungkin "jika menyentuh kelebihan." Dan notis, sekali lagi, ia terlalu besar untuk itu, tetapi ia akan berkembang untuk mengisi. Dan kemudian berpaling 15 darjah? Berapa banyak darjah? Ya, jadi 180 akan berputar saya sepanjang jalan di sekitar. Jadi mari kita lihat jika saya mendapat hak ini. Biar saya zum keluar. 

Biar saya seret Scratch up. Jadi dia sedikit diputarbelitkan sekarang, tetapi itulah denda. Bagaimana saya boleh menetapkan semula beliau dengan mudah? Saya akan menipu sedikit. Jadi, saya menambah satu lagi blok, hanya untuk menjadi jelas. Saya mahu dia menunjukkan 90 darjah ke kanan secara lalai, jadi saya hanya akan beritahu dia untuk berbuat demikian pengaturcaraan. Dan di sini kita pergi. Kita seolah-olah telah melakukannya. Ia sedikit pelik, kerana dia berjalan terbalik. Mari kita memanggil bahawa pepijat. Itulah kesilapan. bug A adalah satu kesilapan dalam program, yang ralat logik bahawa saya, manusia, yang dibuat. Mengapa dia akan terbalik? Adakah MIT skru sehingga atau tidak saya? 

Ya, maksud saya, ia bukan MIT kesalahan. Mereka memberikan saya sekeping teka-teki yang mengatakan menghidupkan beberapa beberapa darjah. Dan pada cadangan Victoria, Saya beralih 180 darjah, yang merupakan gerak hati yang betul. Tetapi beralih 180 darjah secara literal ertinya berpaling 180 darjah, dan itu tidak benar-benar apa yang saya mahu, nampaknya. Kerana sekurang-kurangnya dia dalam dunia ini dua dimensi, supaya perubahan yang sedang berlaku untuk flip dia terbalik. 

Saya mungkin mahu menggunakan apa blok sebaliknya, berdasarkan apa yang anda lihat di sini? Bagaimana kita boleh menetapkan ini? Ya, jadi kami akan menunjukkan ke arah yang bertentangan. Dan sebenarnya walaupun itulah tidak akan mencukupi, kerana kita hanya kod keras untuk menunjuk kiri atau kanan. 

Anda tahu apa yang boleh kita lakukan? Ia kelihatan seperti kita mempunyai blok mudah di sini. Jika saya zum masuk, lihat sesuatu yang kita suka di sini? Supaya ia kelihatan seperti MIT mempunyai abstraksi dibina di sini. Blok ini seolah-olah menjadi bersamaan yang blok lain, kata ganda? 

Ini satu blok seolah-olah menjadi bersamaan untuk ketiga-tiga mereka ini seluruh blok yang kita ada di sini. Jadi ternyata saya boleh memudahkan saya program dengan menyingkirkan semua itu dan hanya meletakkan ini di sini. Dan kini dia masih sedikit kereta, dan itulah denda buat masa sekarang. Kami akan meninggalkan yang berkenaan. Tetapi program saya adalah lebih mudah, dan ini juga, akan menjadi wakil satu gol dalam programming-- adalah untuk membuat pilihan kod anda sebagai mudah, padat yang mungkin, namun masih lagi sebagai boleh dibaca yang mungkin. Anda tidak mahu untuk membuat ia begitu ringkas bahawa ia sukar untuk difahami. 

Tetapi notis saya digantikan tiga blok dengan satu, dan itulah boleh dikatakan satu perkara yang baik. Saya telah disarikan jauh tanggapan memeriksa sama ada anda di pinggir dengan hanya satu blok. Sekarang kita boleh bersenang-senang dengan ini, sebenarnya. Ini tidak menambah begitu banyak nilai intelek tetapi nilai suka bermain. Saya akan pergi ke hadapan dan merebut bunyi ini di sini. Jadi biarlah saya pergi ke hadapan, dan biarlah saya menghentikan program untuk seketika. Saya akan merakam berikut, membenarkan akses kepada mikrofon saya. 

Di sini kita pergi. Aduh. Mari kita cuba ini lagi. Di sini kita pergi. OK, saya mencatatkan perkara yang salah. Di sini kita pergi. Aduh. Aduh. Baiklah. Sekarang saya perlu untuk menghilangkan itu. Baiklah. 

Jadi sekarang saya mempunyai rakaman hanya "ouch." Jadi sekarang saya akan pergi ke hadapan dan memanggil ini "ouch." Saya akan kembali untuk skrip saya, dan kini notis ada blok ini yang dinamakan memainkan bunyi "meow" atau memainkan bunyi "ouch." Saya akan tarik ini, dan di mana perlu saya meletakkan ini untuk kesan lucu? Yeah, jadi sekarang ia adalah jenis kereta, kerana sekarang ini block-- melihat bagaimana ini "jika di pinggir, melantun "adalah jenis yang serba lengkap. Jadi saya perlu untuk menetapkan ini. Biar saya pergi ke hadapan dan melakukan ini. Biar saya menghilangkan ini dan kembali kepada asal kita, lebih sengaja fungsi. Jadi "jika menyentuh tepi, kemudian" Saya hendak untuk menghidupkan, sebagai Victoria dicadangkan, 180 darjah. Dan saya mahu bermain bunyi "ouch" di sana? 

Yeah, notis itu di luar bahawa blok kuning. Jadi ini, juga, akan menjadi bug, tetapi saya dapati ia. Jadi, saya akan tarik di sini, dan notis kini ia di dalam "jika." Oleh itu, "jika" adalah seperti ini daripada seperti lengan seperti hapuskanlah yang hanya akan melakukan apa yang di dalamnya. Jadi sekarang jika saya zum keluar di risiko annoying-- 

KOMPUTER: Aduh, aduh, aduh. 

DAVID MALAN: Dan ia hanya akan berterusan selama-lamanya. Kini hanya untuk mempercepatkan perkara di sini, saya pergi ke hadapan dan membuka, mari kita iaitu- biarlah saya pergi ke beberapa barangan saya sendiri dari kelas. Dan biarlah saya membuka, katakan, ini satu yang dibuat oleh salah seorang felo pengajaran kami beberapa tahun yang lalu. Jadi sebahagian daripada anda mungkin ingat permainan ini dari tadi, dan ia sebenarnya luar biasa. Walaupun kita telah melakukan perkara yang paling mudah program sekarang, mari kita mempertimbangkan apa ini sebenarnya kelihatan seperti. Biar saya tekan bermain. 

Jadi, dalam permainan ini, kita mempunyai katak, dan menggunakan anak panah keys-- dia mengambil langkah-langkah yang lebih besar daripada yang saya remember-- Saya mempunyai kawalan ke atas katak ini. Dan matlamatnya adalah untuk mendapatkan di seluruh sibuk jalan tanpa berjalan ke kereta. Dan mari kita see-- jika saya pergi di sini, saya perlu menunggu log untuk menatal dengan. Ini berasa seperti pepijat. Ini adalah jenis pepijat. Baiklah. Saya pada ini di sini, sana, dan kemudian anda menyimpan usaha sehingga anda mendapatkan semua katak-katak pad lily. Sekarang ini mungkin kelihatan semua lebih kompleks, tetapi mari kita cuba untuk memecahkan ini turun mental dan secara lisan ke dalam blok komponen. Jadi ada mungkin teka-teki sekeping yang kita tidak pernah melihat lagi tetapi itu menjawab ketukan kekunci, kepada perkara-perkara saya memukul pada papan kekunci. 

Jadi ada mungkin beberapa jenis blok yang mengatakan, jika kunci sama sehingga, kemudian melakukan sesuatu dengan Scratch-- mungkin bergerak 10 langkah cara ini. Jika kunci ke bawah ditekan, bergerak 10 langkah cara ini, atau kekunci kiri, bergerak 10 langkah cara ini, 10 tidak perlu pergi itu. Saya jelas bertukar kucing menjadi katak. Jadi itu hanya di mana pakaian, panggilan Scratch it-- kita hanya diimport gambar katak. 

Tetapi apa lagi yang berlaku? Apa yang lain-lain talian kod, apa kepingan teka-teki yang lain lakukan Blake, rakan-rakan pengajaran kami, digunakan dalam program ini, nampaknya? Apa yang membuat segala-galanya move-- apa program bina? 

Gerakan, sure-- jadi menggerakkan blok, yang pasti. Dan apa yang blok langkah di dalam, kemungkinan besar? Ya, beberapa jenis gelung, mungkin selama-lamanya menyekat, mungkin berulang block-- ulangi sehingga blok. Dan itulah apa yang membuat log dan pad lily dan segala langkah lagi belakang dan sebagainya. Ia hanya berlaku tanpa henti. 

Mengapa beberapa kereta bergerak lebih cepat daripada yang lain? Apa yang berbeza tentang program-program? Ya, mungkin sebahagian daripada mereka mengambil lebih langkah dalam satu masa dan sebahagian daripada mereka kurang langkah dalam satu masa. Dan kesan visual cepat berbanding perlahan. 

Apa yang anda fikir berlaku? Apabila saya tiba katak saya sepanjang jalan di seberang jalan dan sungai ke pad lily, sesuatu perlu diberi perhatian yang berlaku. Apa yang berlaku dengan seberapa segera seperti yang saya lakukan itu? Ia berhenti. katak yang berhenti, dan Saya mendapat katak kedua. Jadi apa konstruk mesti digunakan di sana, apa ciri? 

Ya, jadi ada beberapa jenis "Jika" merapikan sana juga. Dan ternyata out-- kita tidak melihat this-- tetapi ada blok lain di sana yang boleh katakan, jika anda menyentuh perkara lain pada skrin, jika anda menyentuh pad lily, "kemudian." Dan kemudian itulah apabila kita membuat katak kedua muncul. Jadi, walaupun permainan ini adalah pasti sangat bertarikh, walaupun pada pandangan pertama terdapat begitu banyak berlaku Blake pada-- dan tidak cambuk ini dalam dua minit, ia mungkin mengambil beliau beberapa jam untuk menghasilkan permainan ini berdasarkan ingatan atau video beliau versi tadi itu daripadanya. Tetapi semua ini perkara-perkara kecil akan pada skrin secara berasingan mendidih ke ini sangat mudah pergerakan constructs-- atau penyata seperti yang kita telah dibincangkan, gelung dan syarat, dan itulah mengenainya. Ada beberapa ciri-ciri lain pelamun. Sesetengah daripada mereka adalah semata-mata estetik atau akustik, seperti bunyi Saya hanya bermain dengan. Tetapi bagi sebahagian besar, anda mempunyai dalam bahasa ini, Awal, semua asas pembinaan usaha anda ada dalam C, Java, JavaScript, PHP, Ruby, Python, dan apa-apa bilangan bahasa lain. Sebarang soalan mengenai calar? Baiklah. Oleh itu, kita tidak akan menyelam lebih dalam untuk Awal, walaupun sama-sama pada hujung minggu ini, terutamanya jika anda mempunyai anak-anak atau anak saudara perempuan dan anak saudara dan sebagainya, untuk memperkenalkan mereka kepada Scratch. Ia sebenarnya satu hebat suka bermain persekitaran dengan, sebagai penulis yang mengatakan, siling yang tinggi. Walaupun kami bermula dengan sangat butiran tahap rendah, anda benar-benar boleh lakukan agak sedikit dengan itu, dan ini mungkin demonstrasi perkara tersebut. 

Tetapi mari kita kini beralih kepada lebih banyak masalah canggih, jika anda akan, dikenali sebagai "mencari" dan "Menyusun," amnya. Kami mempunyai buku telefon ini earlier-- sini satu sama lain hanya untuk discussion-- yang kami dapat untuk mencari dengan lebih cekap kerana daripada andaian ketara. Dan hanya untuk menjadi jelas, apa andaian adalah saya membuat ketika mencari melalui buku telefon ini? Bahawa Mike Smith adalah buku telefon, walaupun saya akan dapat mengendalikan senario tanpa dia sana jika saya hanya berhenti awal. Buku ini adalah abjad. Dan itulah yang sangat murah hati andaian, kerana itu bermakna someone-- Saya jenis memotong sudut, seperti saya lebih cepat kerana seseorang lagi yang melakukan banyak kerja keras untuk saya. 

Tetapi bagaimana jika telefon buku telah terisih? Mungkin Verizon mendapat malas, hanya melemparkan nama dan nombor semua orang di sana mungkin dalam perintah itu di mana mereka mendaftar untuk perkhidmatan telefon. Dan berapa banyak masa yang diperlukan saya untuk mencari seseorang seperti Mike Smith? 1000 halaman telefon book-- berapa banyak laman saya perlu melihat melalui? 

Kesemuanya. Anda jenis daripada nasib. Anda benar-benar perlu melihat setiap halaman jika buku telefon hanya disusun secara rawak. Anda mungkin akan bernasib baik dan mencari Mike pada halaman yang pertama, kerana dia merupakan pelanggan pertama untuk memerintahkan perkhidmatan telefon. Tetapi dia mungkin telah lepas juga. 

Jadi susunan rawak tidak baik. Jadi rasa kita perlu menyusun buku telefon atau dalam data jenis umum yang kita telah diberikan. Bagaimana kita boleh berbuat demikian? 

Baiklah, biar saya hanya cuba contoh yang mudah di sini. Biar saya pergi ke hadapan dan membuat undian beberapa nombor di papan. Katakan nombor yang kita ada adalah, katakan, empat, dua, satu, dan tiga. Dan, Ben, menyusun nombor-nombor ini untuk kita. 

Ok baik. Bagaimana anda melakukannya? Baiklah. Jadi bermula dengan yang paling kecil nilai dan yang paling tinggi, dan itu benar-benar gerak hati yang baik. Dan menyedari bahawa kita yang manusia sebenarnya cukup baik pada penyelesaian masalah seperti ini, sekurang-kurangnya apabila data adalah agak kecil. Sebaik sahaja anda mula mempunyai beratus-ratus nombor, beribu-ribu nombor, berjuta-juta nombor, Ben mungkin tidak boleh melakukannya cukup yang cepat, dengan anggapan bahawa terdapat jurang dalam nombor. Agak mudah untuk mengira satu juta sebaliknya, memakan hanya masa. 

Jadi algoritma ia kedengaran seperti Ben digunakan tadi adalah carian untuk jumlah yang paling kecil. Jadi, walaupun kita manusia boleh mengambil dalam banyak maklumat visual, komputer sebenarnya sedikit lebih terhad. Komputer hanya boleh melihat satu bait pada satu masa atau mungkin empat bait di time-- yang hari ini mungkin 8 bytes di time-- yang tetapi jumlah yang sangat kecil daripada bait pada masa yang diberikan. 

Jadi memandangkan kita benar-benar mempunyai empat nilai berasingan sini-- dan anda boleh berfikir Ben sebagai mempunyai blinders pada-olah dia adalah komputer seperti bahawa ia tidak dapat melihat apa-apa selain daripada satu nombor di time-- yang supaya kita biasanya akan mengambil alih, seperti dalam Bahasa Inggeris, kami akan dibaca dari kanan ke kiri. Jadi nombor pertama Ben mungkin kelihatan di empat dan kemudian dengan cepat menyedari itu adalah satu yang cukup besar number-- biarlah saya terus mencari. 

Ada dua. Tunggu sebentar. Dua adalah lebih kecil daripada empat. Saya akan ingat. Dua kini yang paling kecil. Sekarang one-- itulah yang lebih baik. Itulah yang lebih kecil. Saya akan lupa kira-kira dua dan hanya ingat sekarang. 

Dan dia boleh berhenti mencari? Well, dia boleh berdasarkan maklumat ini, tetapi dia akan carian yang lebih baik yang lain dalam senarai itu. Kerana apa jika sifar berada dalam senarai? Bagaimana jika negatif satu berada dalam senarai? Dia hanya tahu bahawa jawapan beliau adalah betul jika dia mendalam diperiksakan keseluruhan senarai. Oleh itu, kita melihat seluruh ini. Three-- itu adalah satu pembaziran masa. Hanya tidak bernasib baik, tetapi saya masih betul untuk berbuat demikian. Dan sekarang dia mungkin memilih nombor yang paling kecil dan hanya meletakkan ia pada permulaan senarai, seperti yang saya akan lakukan di sini. Sekarang apa yang kamu buat selepas, walaupun anda tidak berfikir tentang hal itu hampir setakat ini? Ulangi proses ini, jadi beberapa jenis gelung. Ada idea biasa. Jadi di sini adalah empat. Itulah masa yang paling kecil. Itulah calon. Tidak lagi. Sekarang saya lihat dua. Itulah elemen seterusnya yang paling kecil. Three-- itu bukan kecil, jadi sekarang Ben boleh cabut kedua-dua. 

Dan sekarang kita mengulangi proses, dan sudah tentu tiga mendapat ditarik keluar depan. Mengulangi proses tersebut. Empat mendapat ditarik keluar. Dan sekarang kita berada di luar nombor, jadi senarai yang perlu diselesaikan. 

Dan sesungguhnya, ini adalah satu algoritma formal. Seorang saintis komputer akan memanggil ini "apapun pemilihan," idea itu jenis yang menyenaraikan iteratively-- lagi dan lagi dan lagi memilih nombor yang paling kecil. Dan apa yang baik tentang hal itu adalah ia hanya begitu darn intuitif. Ia amat mudah. Dan anda boleh mengulangi yang sama operasi lagi dan lagi. Ia mudah. 

Dalam kes ini ia laju, tetapi berapa lama masa yang benar-benar mengambil? Mari kita membuat ia kelihatan dan berasa sedikit lebih membosankan. Jadi satu, dua, tiga, empat, lima enam, tujuh, lapan, sembilan, 10, 11, 12, 13, 14, 15, 16-- nombor sewenang-wenangnya. Saya hanya mahu lebih ini masa daripada hanya empat. Jadi, jika saya telah mendapat keseluruhan sekumpulan nombor sekarang-- ia langsung tidak kira apa yang mereka ialah- ini membiarkan berfikir tentang apa yang ini algoritma benar-benar adalah seperti. 

Katakan terdapat nombor di sana. Sekali lagi, tidak kira apa mereka, tetapi ia secara rawak. Saya memohon algoritma Ben. Saya perlu untuk memilih nombor yang paling kecil. Apa yang saya buat? Dan saya akan secara fizikal melakukannya kali ini untuk bertindak keluar. Mencari, mencari, mencari, mencari, mencari. Hanya dengan masa yang saya dapat akhir senarai yang boleh Saya sedar yang paling kecil nombor adalah dua masa ini. Tidak ada di dalam senarai. Jadi saya meletakkan dua. 

Apa yang saya lakukan seterusnya? Mencari, mencari, mencari, mencari. Sekarang saya mendapati nombor tujuh, kerana ada jurang dalam numbers-- ini tetapi hanya sewenang-wenangnya. Baiklah. Jadi sekarang saya boleh meletakkan tujuh. Mencari Lelaki, mencari. 

Sekarang saya menganggap, sudah tentu, bahawa Ben tidak mempunyai RAM tambahan, tambahan memori, kerana, sudah tentu, Saya melihat nombor yang sama. Sesungguhnya saya boleh ingat semua orang-orang nombor, dan itu sememangnya benar. Tetapi jika Ben ingat semua nombor dia dilihat, dia tidak benar-benar membuat kemajuan asas kerana dia sudah mempunyai keupayaan untuk mencari melalui nombor di papan. Mengingati semua nombor tidak membantu, kerana dia masih boleh seperti komputer hanya melihat, kita telah berkata satu nombor, pada satu masa. Jadi tidak ada semacam cheat sana yang boleh anda manfaatkan. 

Jadi pada hakikatnya, seperti yang saya terus mencari senarai, Saya benar-benar perlu teruskannya belakang dan sebagainya melaluinya, mencabut keluar nombor seterusnya yang paling kecil. Dan seperti yang anda jenis boleh membuat kesimpulan daripada pergerakan bodoh saya, ini hanya mendapat sangat membosankan dengan cepat, dan saya seolah-olah akan kembali dan sebagainya, belakang dan sebagainya agak sedikit. Sekarang untuk berlaku adil, saya tidak perlu pergi cukup, baik, mari kita see-- untuk berlaku adil, Saya tidak perlu berjalan agak kerana banyak langkah setiap kali. Kerana, sudah tentu, kerana saya pilih nombor dari senarai, senarai baki semakin pendek. 

Dan jadi mari kita berfikir tentang jumlah langkah Saya sebenarnya traipsing melalui setiap masa. Dalam keadaan yang pertama kami mempunyai 16 nombor, dan sebagainya maximally-- mari kita melakukan ini untuk discussion-- yang Saya melihat melalui 16 nombor untuk mencari yang paling kecil. Tetapi apabila saya dipetik daripada jumlah yang paling kecil, bagaimana lama adalah senarai yang masih ada, sudah tentu? Hanya 15. Jadi berapa banyak nombor lakukan Ben atau saya mempunyai untuk melihat melalui kali kedua? 15, hanya untuk pergi dan mencari yang paling kecil. Tetapi sekarang, sudah tentu, senarai adalah, juga, lebih kecil berbanding sebelum ia. Jadi berapa banyak langkah-langkah yang tidak saya perlu mengambil masa yang akan datang? 14 dan kemudian 13 dan kemudian 12, ditambah dot, dot, dot, sehingga saya ditinggalkan dengan hanya satu. Jadi sekarang seorang saintis komputer akan bertanya, baik, apa adakah itu semua sama? Ia sebenarnya sama dengan beberapa konkrit jumlah itu kita boleh pasti melakukan arithmetically, tetapi kita mahu bercakap tentang kecekapan algoritma sedikit lebih formulaically, bebas daripada berapa lama senarai adalah. 

Dan supaya anda tahu apa? Ini adalah 16, tetapi seperti yang saya katakan sebelum ini, mari kita memanggil saiz masalah n, di mana n adalah nombor. Mungkin ia adalah 16, mungkin ia tiga, mungkin ia adalah satu juta. Saya tidak tahu. Saya tidak peduli. Apa yang saya inginkan adalah formula yang saya boleh gunakan untuk membandingkan algoritma ini terhadap algoritma lain bahawa seseorang mungkin menuntut adalah lebih baik atau lebih teruk lagi. 

Jadi ternyata, dan saya hanya tahu ini dari sekolah rendah, bahawa ini sebenarnya kerja-kerja kepada yang sama Perkara seperti n lebih n tambah satu lebih dua. Dan ini berlaku untuk sama, sudah Sudah tentu, n kuasa dua tambah n lebih dua. Jadi jika saya mahu formula berapa banyak langkah terlibat dalam melihat semua daripada nombor-nombor lagi dan lagi dan lagi dan lagi, saya akan berkata ia n kuasa dua tambah n lebih dua. Tetapi anda tahu apa? Ini hanya kelihatan tidak kemas. Saya hanya mahu pengertian umum perkara. Dan anda mungkin ingat dari sekolah tinggi yang terdapat adalah tanggapan jangka perintah tertinggi. Yang syarat-syarat ini, n kuasa dua, n, atau separuh, mempunyai kesan yang paling dari masa ke masa? N lebih besar mendapat, yang ini perkara-perkara yang paling? 

Dalam erti kata lain, jika saya pasang dalam sejuta, n kuasa dua akan menjadi yang paling mungkin faktor mendominasi, kerana satu juta kali itu sendiri adalah jauh lebih besar daripada tambah satu tambahan juta. Jadi, anda tahu apa? Ini adalah seperti darn besar nombor jika anda mengambil ancang-nombor. Ini tidak benar-benar perkara. Kami hanya akan silang yang keluar dan lupa mengenainya. Dan supaya seorang saintis komputer akan berkata bahawa kecekapan algoritma ini adalah atas perintah n squared-- Maksud saya benar-benar satu penghampiran. Ia umpama secara kasar n kuasa dua. Dari masa ke masa, yang lebih besar dan n lebih besar mendapat, ini adalah anggaran yang baik untuk apa yang kecekapan atau kekurangan kecekapan algoritma ini sebenarnya. Dan saya mendapatkan bahawa, sudah tentu, dari sebenarnya melakukan matematik. Tetapi sekarang saya hanya melambai tangan saya, kerana saya hanya mahu rasa umum algoritma ini. 

Jadi menggunakan logik yang sama, sementara itu, mari kita mempertimbangkan algoritma lain kita sudah kelihatan carian at-- linear. Apabila saya telah mencari untuk book-- telefon tidak mengasingkan ia, mencari melalui book-- telefon kita terus berkata bahawa ia adalah 1000 langkah-langkah, atau 500 langkah. Tetapi mari kita umum itu. Jika ada n muka surat dalam buku telefon, apa yang masa berjalan atau kecekapan carian linear? Ia adalah atas perintah berapa banyak langkah-langkah untuk mencari Mike Smith menggunakan carian linear, algoritma pertama, atau kedua? 

Dalam kes terburuk, Mike adalah pada akhir buku ini. Jadi, jika buku telefon mempunyai 1,000 muka surat, kita kata masa lalu, dalam kes paling teruk, ia mungkin mengambil masa kira-kira bagaimana banyak halaman untuk mencari Mike? Seperti 1000. Ia merupakan satu had atas. Ia adalah keadaan yang paling teruk mungkin. Tetapi sekali lagi, kita beralih dari nombor-nombor seperti 1000 sekarang. Ia hanya n. 

Jadi apa kesimpulan yang logik? Mencari Mike dalam telefon buku yang mempunyai halaman n mungkin mengambil masa, dalam kes yang teruk, jumlah langkah atas perintah n? Dan sesungguhnya komputer saintis akan berkata bahawa masa berjalan, atau prestasi atau kecekapan atau ketidakcekapan, daripada algoritma seperti carian linear adalah atas perintah n. Dan kita boleh memohon yang sama logik menyeberangi sesuatu daripada kerana saya hanya lakukan kepada kedua algoritma kami dengan buku telefon, mana kita pergi dua halaman pada satu masa. 

Jadi 1000 halaman buku telefon mungkin membawa kita 500 halaman bertukar, tambah satu jika kita menggandakan belakang sedikit. Jadi, jika buku telefon mempunyai halaman n, tetapi yang kita lakukan dua halaman pada satu masa, itulah kira-kira apa? N lebih dua, jadi itu seperti n lebih dua. Tetapi saya membuat tuntutan yang masa yang lalu bahawa n lebih two-- itu jenis yang sama dengan hanya n. Ia hanya satu faktor yang tetap, ahli sains komputer akan berkata. Mari kita hanya memberi tumpuan kepada pembolehubah, really-- pembolehubah terbesar dalam persamaan. 

carian supaya linear, sama ada dibuat satu halaman pada satu masa atau dua halaman pada satu masa, adalah jenis asas yang sama. Ia masih atas perintah n. Tetapi saya mendakwa dengan gambar saya sebelum ini bahawa algoritma ketiga tidak linear. Ia bukan satu garis lurus. Ia adalah bahawa garis melengkung, dan algebra formula ada apa? Log n-- supaya log asas dua n. Dan kita tidak perlu pergi ke terlalu lebih terperinci mengenai logaritma hari ini, tetapi kebanyakan ahli-ahli sains komputer tidak akan walaupun memberitahu anda apa yang asas adalah. Kerana itu semua hanya faktor-faktor yang berterusan, boleh dikatakan, hanya perbezaan angka sedikit. Dan sebagainya ini akan menjadi perkara biasa cara untuk komputer terutamanya formal ahli-ahli sains di papan atau pengaturcara di papan putih sebenarnya dengan alasan yang algoritma mereka akan menggunakan atau apa kecekapan algoritma mereka. 

Dan ini tidak semestinya sesuatu anda berbincang dalam mana-mana terperinci, tetapi programmer yang baik adalah seseorang yang mempunyai, latar belakang formal yang kukuh. Dia dapat bercakap dengan anda dalam jenis ini cara dan benar-benar membuat hujah-hujah kualitatif mengapa satu algoritma atau satu perisian adalah lebih baik dalam beberapa cara yang lain. Kerana anda boleh pasti hanya menjalankan program seseorang itu dan mengira bilangan saat yang diperlukan untuk menyelesaikan beberapa nombor, dan anda boleh menjalankan beberapa program orang lain dan mengira bilangan saat yang diperlukan. Tetapi ini adalah cara yang lebih umum yang anda boleh gunakan untuk menganalisis algoritma, jika anda akan, hanya pada kertas atau hanya secara lisan. Tanpa berjalan, tanpa walaupun cuba input sampel, anda hanya boleh sebab melaluinya. Dan sebagainya dengan menyewa pemaju atau jika mempunyai dia atau dia semacam berhujah kepada anda mengapa algoritma mereka, rahsia mereka sos untuk mencari berbilion halaman web untuk anda syarikat adalah lebih baik, ini adalah jenis hujah-hujah mereka ideal harus dapat dilupakan. Atau sekurang-kurangnya ini adalah jenis perkara yang akan datang dalam perbincangan, di kurangnya dalam perbincangan yang sangat formal. Baiklah. Jadi Ben dicadangkan sesuatu dipanggil jenis pemilihan. Tetapi saya akan mencadangkan bahawa ada cara-cara lain untuk berbuat demikian juga. Apa yang saya tidak benar-benar suka mengenai algoritma Ben adalah bahawa dia terus berjalan, atau setelah saya berjalan, belakang dan sebagainya dan belakang dan sebagainya dan belakang dan sebagainya. Bagaimana jika sebaliknya saya adalah untuk melakukan sesuatu seperti nombor-nombor ini di sini dan saya hanya berurusan dengan setiap nombor seterusnya kerana saya memberikannya? 

Dalam erti kata lain, di sini senarai saya nombor. Empat, satu, tiga, dua. Dan saya akan melakukan yang berikut. Saya akan memasukkan nombor di mana mereka berada dan bukan daripada memilihnya satu pada satu masa. Dalam erti kata lain, di sini adalah nombor empat. 

Berikut adalah senarai asal saya. Dan saya akan mengekalkan dasarnya senarai baru di sini. Jadi ini adalah senarai lama. Ini senarai baru. Saya melihat nombor empat pertama. senarai baru saya pada mulanya kosong, jadi ia adalah trivially kes bahawa empat kini aneka senarai. Saya hanya mengambil bilangan saya diberikan, dan saya meletakkan ia di dalam senarai baru saya. 

Adalah senarai baru ini disusun? Yeah. Ia bodoh kerana ada hanya satu elemen, tetapi ia benar-benar disusun. Tidak ada yang keluar dari tempat. Ia lebih menarik, algoritma ini, apabila saya bergerak ke langkah seterusnya. 

Sekarang saya mempunyai satu. Jadi satu, sudah tentu, tergolong di bermula atau akhir senarai baru ini? Permulaan. Jadi saya perlu membuat kerja-kerja sekarang. Saya telah mengambil beberapa kebebasan dengan penanda saya dengan hanya melukis perkara di mana saya mahu mereka, tetapi itu tidak benar-benar tepat dalam komputer. Komputer, seperti yang kita tahu, mempunyai RAM atau Random Access Memory, dan itulah salah satu bait dan bait lain dan bait lain. Dan jika anda mempunyai gigabit RAM, anda mempunyai bilion bait, tetapi ia secara fizikal di satu lokasi. Anda tidak boleh hanya bergerak barangan sekitar dengan melukis pada papan mana sahaja yang anda mahu. Jadi, jika senarai baru saya mempunyai empat lokasi dalam ingatan, malangnya empat adalah sudah di tempat yang salah. 

Jadi untuk memasukkan nombor satu Saya tidak boleh hanya menarik di sini. lokasi memori ini tidak wujud. Yang akan menipu, dan saya telah menipu bergambar untuk beberapa minit di sini. Jadi benar-benar, jika saya mahu meletakkan satu di sini, Saya mempunyai untuk menyalin sementara empat dan kemudian meletakkan satu di sana. 

Itu baik, itu betul, yang secara teknikal mungkin, tetapi sedar itulah kerja tambahan. Saya tidak hanya meletakkan nombor di tempat. Saya pertama terpaksa bergerak nombor, kemudian memasukkannya ke dalam tempat, jadi saya jenis dua kali ganda jumlah saya kerja. Jadi menyimpan bahawa dalam fikiran. 

Tetapi saya kini sudah selesai dengan elemen ini. Sekarang saya mahu merebut nombor tiga. Di mana, sudah tentu, ia tergolong? Di antara. Saya tidak boleh menipu lagi dan hanya meletakkan ia di sana, kerana, sekali lagi, ingatan ini adalah di lokasi fizikal. Jadi saya perlu menyalin empat dan meletakkan tiga di sini. Bukan masalah besar. Ia hanya satu langkah tambahan again-- berasa sangat murah. 

Tetapi sekarang saya beralih kepada kedua-dua. Kedua-dua, sudah tentu, tergolong di sini. Sekarang anda mula melihat bagaimana kerja yang boleh terkumpul. Sekarang apa yang saya perlu lakukan? Ya, saya perlu bergerak empat, Saya kemudian perlu menyalin tiga, dan sekarang saya boleh memasukkan kedua-dua. Dan menangkap dengan ini algoritma, yang menariknya, adalah bahawa rasa kita mempunyai lebih ekstrem kes di mana ia katakan lapan, tujuh, enam, lima, empat, tiga, dua, satu. Ini adalah, dalam banyak konteks, senario kes terburuk, kerana perkara yang darn literal ke belakang. 

Ia tidak benar-benar menjejaskan algoritma Ben, kerana dalam pemilihan Ben semacam dia akan menjaga pergi dan balik melalui senarai. Dan kerana dia sentiasa mencari melalui senarai baki keseluruhan, ia tidak penting di mana unsur-unsur adalah. Tetapi dalam kes ini dengan memasukkan saya approach-- mari kita cuba ini. 

Jadi satu, dua, tiga, empat, lima, enam, tujuh, lapan. Satu dua tiga empat, lima, enam, tujuh, lapan. Saya akan mengambil lapan, dan di mana saya meletakkan ia? Nah, pada awal senarai saya, kerana senarai baru ini disusun. Dan saya memotongnya. 

Di mana saya meletakkan tujuh? Celaka. Ia perlu untuk pergi ke sana, jadi Saya mempunyai untuk melakukan penyalinan. Dan kini tujuh pergi di sini. Sekarang saya beralih kepada enam. Sekarang ia lebih kerja. 

Lapan telah pergi di sini. Seven telah pergi di sini. Kini enam boleh pergi di sini. Sekarang saya merebut lima. Kini lapan telah pergi sini, tujuh telah pergi di sini, enam telah pergi di sini, dan kini lima dan berulang. Dan saya cukup banyak bergerak ia sentiasa. 

Jadi pada akhirnya, algorithm-- ini kita akan memanggilnya sisipan sort-- sebenarnya mempunyai banyak kerja juga. Ia hanya berbeza jenis kerja daripada Ben. kerja Ben telah saya akan belakang dan sebagainya sepanjang masa, memilih seterusnya terkecil elemen lagi dan lagi. Oleh itu, jenis ini sangat visual kerja. 

Ini algoritma lain, yang masih correct-- ia akan mendapatkan pekerjaan yang done-- hanya perubahan jumlah kerja. Ia kelihatan seperti pada mulanya anda berada menjimatkan, kerana anda hanya berurusan dengan setiap elemen depan tanpa berjalan semua jalan melalui senarai seperti Ben adalah. Tetapi masalahnya ialah, terutama dalam kes gila di mana itu semua ke belakang, anda hanya jenis menangguhkan kerja keras sehingga anda perlu untuk menetapkan kesilapan anda. 

Dan jadi jika anda boleh bayangkan ini lapan dan tujuh dan enam dan lima dan kemudian empat dan tiga dan dua bergerak dengan cara mereka melalui senarai, kita baru sahaja mengubah jenis kerja yang kami lakukan. Daripada melakukan ia di permulaan lelaran saya, Saya hanya melakukannya pada akhir setiap lelaran. Jadi ia ternyata bahawa algoritma ini, juga, umumnya dipanggil jenis kemasukan, juga atas perintah n kuasa dua. Ia sebenarnya tidak lebih baik, tidak lebih baik pada semua. 

Walau bagaimanapun, ada pendekatan ketiga Saya akan menggalakkan kita untuk mempertimbangkan, yang ini. Jadi andaikan senarai saya, untuk kesederhanaan sekali lagi, empat, satu, tiga, two-- hanya empat nombor. Ben mempunyai gerak hati yang baik, gerak hati manusia yang baik sebelum ini, yang mana kita tetap seluruh menyenaraikan eventually-- jenis sisipan. Saya dipujuk kita bersama-sama. Tetapi mari kita mempertimbangkan Cara yang paling mudah untuk menetapkan senarai ini. 

Senarai ini tidak diselesaikan. Mengapa? Dalam bahasa Inggeris, menjelaskan mengapa ia tidak benar-benar disusun. Apakah ertinya tidak diselesaikan? 

PELAJAR: Ia tidak berurutan. 

DAVID MALAN: Tidak berurutan. Berikan saya satu contoh. 

PELAJAR: Meletakkan mereka dalam perintah. 

DAVID MALAN: OK. Beri saya contoh yang lebih spesifik. 

PELAJAR: Menaik perintah. DAVID MALAN: Tidak menaik perintah. Lebih tepat. Saya tidak tahu apa yang anda maksudkan dengan naik. Apa yang tidak kena? 

PELAJAR: Yang paling kecil daripada nombor tidak dalam ruang pertama. 

DAVID MALAN: nombor terkecil yang tidak dalam ruang pertama. Menjadi lebih khusus. Saya mula menangkap. Kami mengira, tetapi apa yang di luar perintah di sini? 

PELAJAR: urutan berangka. DAVID MALAN: urutan berangka. jenis semua orang penyimpanan ia sini-- tahap yang sangat tinggi. Hanya literal beritahu saya apa yang salah seperti kekuatan yang berusia lima tahun. 

PELAJAR: Plus satu. 

DAVID MALAN: Apa itu? 

PELAJAR: Plus satu. 

DAVID MALAN: Apa yang kamu maksudkan satu plus? Berikan saya berbeza lima tahun berusia a. Apa salahnya, ibu? Apa salahnya, ayah? Apa yang kamu maksudkan ini tidak diselesaikan? 

PELAJAR: Ia bukan tempat yang betul. 

DAVID MALAN: Apa tidak di tempat yang betul? 

PELAJAR: Four. DAVID MALAN: OK, baik. Jadi empat tidak di mana ia sepatutnya. Khususnya, adalah hak ini? Empat dan satu, yang pertama dua nombor yang saya lihat. Adakah ini betul? Tidak, mereka berada di luar perintah, bukan? Malah, rasa sekarang mengenai komputer, terlalu. Ia hanya boleh melihat mungkin satu, mungkin dua perkara pada once-- dan benar-benar hanya satu perkara pada satu masa, tetapi ia boleh sekurang-kurangnya melihat satu perkara maka Perkara seterusnya yang betul di sebelahnya. 

Jadi adakah ini dalam rangka? Sudah tentu tidak. Jadi, anda tahu apa? Mengapa kita tidak mengambil bayi langkah-langkah untuk memperbaiki masalah ini daripada melakukan mewah ini algoritma seperti Ben, di mana dia semacam membetulkannya oleh menggelung melalui senarai daripada melakukan apa yang saya lakukan, di mana Saya hanya jenis tetap ia seperti yang kita pergi? Mari kita literal memecahkan tanggapan tertib berangka perintah-, memanggilnya apa sahaja yang anda want-- ke dalam ini perbandingan dari segi pasangan. 

Empat dan satu. Adakah ini susunan yang betul? Jadi mari kita menetapkan bahawa. Satu dan empat, dan kemudian kita hanya akan menyalin itu. Baiklah, baik. Saya tetap satu dan empat. Tiga dan dua? No. Biar kata-kata saya sepadan jari saya. Empat dan tiga? 

Ia bukan dalam perintah, jadi saya akan untuk melakukan satu, tiga, empat, dua. Ok baik. Sekarang empat dan dua? Kita perlu untuk menetapkan ini, juga. Jadi satu, tiga, dua, empat. Begitu juga ia disusun? Tiada, tetapi ia lebih dekat dengan disusun? 

Ia adalah, kerana kita tetap ini kesilapan, kita tetap kesilapan ini, dan Kami telah tetapkan satu kesilapan ini. Oleh itu, kita tetap tiga kesilapan boleh dikatakan. Masih tidak benar-benar melihat disusun, tetapi ia adalah objektif lebih dekat dengan disusun kerana kita tetap beberapa orang-orang kesilapan. 

Sekarang apa yang saya lakukan seterusnya? Saya jenis sampai ke penghujung senarai. Saya seolah-olah telah tetap semua kesilapan, tetapi tidak. Kerana dalam kes ini, beberapa nombor mungkin telah dipam lebih dekat kepada nombor lain yang masih keluar perintah. Jadi mari kita buat sekali lagi, dan saya akan hanya melakukannya di tempat masa ini. Satu dan tiga? Tidak mengapa. Tiga dan dua? Sudah tentu tidak, jadi mari kita mengubah itu. Jadi dua, tiga. Tiga dan empat? Dan sekarang mari kita hanya menjadi terutamanya bengah sini. Adakah ia disusun? Anda manusia tahu ia disusun. 

Saya harus cuba lagi. Jadi Olivia mencadangkan saya cuba lagi. Mengapa? Kerana komputer yang tidak mempunyai kemewahan mata manusia hanya mengerling back-- OK, aku selesai. Bagaimanakah komputer menentukan bahawa senarai itu kini disusun? Mekanikal. 

Saya perlu melalui sekali lagi, dan hanya jika saya tidak membuat / mencari apa-apa kesilapan yang boleh saya kemudian membuat kesimpulan seperti komputer, yep, kita baik pergi. Jadi, satu dan dua, dua dan tiga, tiga dan empat. Sekarang saya secara muktamad boleh mengatakan ini adalah disusun, kerana saya tidak membuat sebarang perubahan. Sekarang ia akan menjadi bug dan hanya bodoh jika saya, komputer, bertanya soalan-soalan yang sama sekali lagi mengharapkan jawapan yang berbeza. tidak sepatutnya berlaku. 

Dan sehingga kini senarai itu disusun. Malangnya, berlari masa algoritma ini juga n kuasa dua. Mengapa? Kerana anda mempunyai nombor n, dan dalam kes paling teruk anda perlu bergerak nombor n kali n kerana anda perlu terus pergi kembali untuk memeriksa dan berpotensi menetapkan nombor-nombor ini. Dan kita boleh melakukan yang lebih analisis formal, terlalu. 

Semua ini untuk mengatakan bahawa kita telah mengambil tiga pendekatan yang berbeza, satu daripada mereka segera intuitif off kelawar dari Ben untuk kemasukan yang dicadangkan saya jenis yang ini di mana anda jenis terlepas pandang hutan untuk pokok-pokok pada mulanya. Tetapi jika anda mengambil langkah ke belakang, Voilà, kami tetap tanggapan sorting. Jadi ini, berani mengatakan, tahap yang lebih rendah mungkin daripada beberapa orang-orang lain algoritma, tetapi mari kita lihat jika kita tidak boleh menggambarkan ini dengan cara ini. 

Jadi ini adalah beberapa nice perisian yang seseorang menulis menggunakan bar yang berwarna-warni itu akan melakukan yang berikut untuk kita. Setiap bar ini mewakili nombor. Taller bar, semakin besar jumlah itu, lebih kecil bar, lebih kecil bilangan. Begitu ideal kita mahu piramid nice di mana ia bermula kecil dan mendapat besar, dan yang akan bermakna bahawa Bar ini disusun. Jadi, saya akan pergi ke hadapan dan memilih, misalnya, algoritma Ben first-- apapun pemilihan. 

Dan perhatikan apa yang ia lakukan. Cara mereka telah memilih untuk menggambarkan algoritma ini adalah bahawa, sama seperti saya berjalan melalui senarai saya, program ini berjalan melalui senarai nama nombor, menonjolkan in pink setiap jumlah itu ia melihat. Dan apa yang akan berlaku sekarang? 

Bilangan terkecil yang I atau Ben mendapati tiba-tiba mendapat berpindah ke permulaan senarai. Dan notis yang mereka lakukan mengusir nombor yang berada di sana, dan yang betul-betul halus. Saya tidak masuk ke dalam tahap yang terperinci. Tetapi kita perlu meletakkan jumlah itu di suatu tempat, jadi kita bergerak kepada tempat terbuka yang telah dicipta. Jadi saya akan mempercepatkan ini sehingga, kerana jika tidak ia menjadi sangat membosankan dengan cepat. Animasi speed-- ada kita pergi. prinsip Jadi sekarang sama Saya telah memohon, tetapi anda boleh mula berasa algoritma, jika anda akan, atau melihat ia sedikit lebih jelas. Dan algoritma ini mempunyai kesan memilih elemen yang paling kecil akan datang, jadi anda akan mula melihatnya jalan sehingga di sebelah kiri. Dan pada setiap lelaran, seperti yang saya dicadangkan, ia bekerja yang kurang sedikit. Ia tidak perlu pergi sepanjang jalan kembali ke hujung kiri senarai, kerana ia sudah mengetahui orang-orang yang disusun. Jadi ia jenis berasa seperti ia mempercepatkan, walaupun setiap langkah adalah mengambil jumlah yang sama. Terdapat hanya lebih sedikit langkah yang seterusnya. Dan sekarang anda jenis boleh merasai algoritma membersihkan akhir itu, dan sesungguhnya kini ia disusun. 

Jadi jenis kemasukan semua dilakukan. Saya perlu semula Rawakkan-array. Dan perhatikan saya boleh hanya menjaga randomizing ia, dan kami akan mendapat anggaran pendekatan yang sama, jenis kemasukan. Biar saya memperlahankannya ke sini. Mari kita mulakan yang lebih. Berhenti. 

Mari kita skip empat. Di sana kami pergi. Rawakkan lokasi mereka. Dan di sini kita go-- jenis kemasukan. Play. Perhatikan bahawa ia berurusan dengan setiap unsur ia menghadapi merta, tetapi jika ia tergolong dalam tempat notis salah semua kerja yang telah berlaku. Kami perlu terus beralih lebih dan banyak lagi elemen untuk membuat bilik untuk apa yang kita mahu dimasukkan ke dalam tempat. 

Jadi, kita memberi tumpuan kepada hujung kiri senarai sahaja. Notis yang kami telah tidak kelihatan at-- kita telah tidak ditonjolkan dalam apa-apa merah jambu ke kanan. Kami hanya berurusan dengan masalah seperti yang kita pergi, tetapi kami mewujudkan banyak bekerja untuk diri kita sendiri masih. Dan jadi jika kita mempercepatkan ini sehingga sekarang untuk pergi ke siap, ia mempunyai rasa yang berbeza untuk itu sesungguhnya. Ia hanya memberi tumpuan kepada hujung kiri tetapi melakukan kerja lebih sedikit sebagai needed-- jenis perkara melicinkan lebih, menetapkan perkara-perkara, tetapi berurusan akhirnya dengan setiap unsur satu demi satu sehingga kita sampai ke hanya-- baik, kita semua tahu bagaimana ini akan berakhir, maka ia adalah satu underwhelming sedikit mungkin. 

Tetapi senarai dalam end-- yang spoiler-- akan diselesaikan. Jadi mari kita lihat di salah satu lepas. Kita tidak boleh hanya melangkau sekarang. Kita sudah hampir. Dua untuk pergi, satu pergi. Dan Voilà. Cemerlang. 

Jadi sekarang mari kita buat satu yang terakhir, semula randomizing dengan gelembung macam. Dan perhatikan di sini, terutamanya jika saya memperlahankannya ke bawah, ini tidak menyimpan swooping melalui. Tetapi notis ia hanya membuat berpasangan jenis comparisons-- penyelesaian tempatan. Tetapi sebaik sahaja kita dapat akhir senarai dalam merah jambu, apa yang akan perlu berlaku lagi? Ya, ia akan perlu mula semula, kerana ia hanya kesilapan dari segi pasangan tetap. Dan yang mungkin telah didedahkan lagi orang lain. Dan jadi jika anda mempercepatkan sehingga ini, anda akan melihat bahawa, banyak yang namanya, yang lebih kecil elements-- atau sebaliknya, yang elements-- lebih besar bermula gelembung sehingga ke atas, jika anda akan. Dan unsur-unsur yang lebih kecil mula gelembung ke kiri. Dan sesungguhnya, itulah jenis kesan visual juga. Dan sebagainya ini akan berakhir kemasan dengan cara yang hampir sama juga. 

Kami tidak mempunyai mereka kekal pada salah satu tertentu ini. Biar saya membuka ini sekarang juga. Ada beberapa algoritma sorting lain di dunia, beberapa yang direkodkan di sini. Dan terutama untuk pelajar yang tidak semestinya visual atau matematik, seperti yang kita lakukan sebelum ini, kita boleh juga melakukan ini audially jika kita kaitkan bunyi dengan ini. Dan hanya untuk keseronokan, di sini adalah Beberapa algoritma yang berbeza, dan salah seorang daripada mereka khususnya anda berada akan perasan dipanggil "merge." 

Ia sebenarnya adalah asasnya algoritma yang lebih baik, seperti yang bergabung jenis, salah satu daripada orang-orang yang anda kira-kira untuk melihat, bukan perintah n kuasa dua. Ia pada perintah itu n kali log daripada n, yang sebenarnya lebih kecil dan dengan itu lebih cepat daripada yang tiga lain. Dan ada pasangan lain orang-orang yang bodoh yang kita akan lihat. 

Jadi di sini kita pergi dengan beberapa bunyi. Ini adalah jenis kemasukan, jadi sekali lagi ia hanya berurusan dengan unsur-unsur kerana mereka datang. Ini adalah jenis gelembung, jadi ia menganggap mereka pasangan pada satu masa. Dan sekali lagi, unsur-unsur terbesar sedang menggelegak sehingga ke atas. 

Seterusnya apapun pemilihan. Ini adalah algoritma Ben, di mana lagi dia memilih iterative elemen seterusnya yang paling kecil. Dan sekali lagi, kini anda boleh benar-benar mendengar bahawa ia mempercepatkan tetapi hanya setakat kerana ia melakukan kurang dan kurang bekerja pada setiap lelaran. Ini adalah lebih cepat satu, bergabung apapun, yang menyusun kelompok nombor bersama-sama dan kemudian menggabungkan mereka. Jadi look-- kiri setengah sudah disusun. 

Kini ia menyusun separuh yang betul, dan kini ia akan menggabungkan mereka menjadi satu. Ini adalah sesuatu yang dinamakan "Gnome macam." Dan anda boleh jenis melihat bahawa ia akan belakang dan sebagainya, menetapkan kerja sedikit di sini dan di sana sebelum ia bertindak untuk kerja-kerja baru. Dan itu sahaja. Ada jenis lain, yang benar-benar hanya untuk tujuan akademik, dipanggil "jenis bodoh," yang mengambil data anda, menyusun ia secara rawak, dan kemudian memeriksa jika ia disusun. Dan jika tidak, ia semula menyusun ia secara rawak, memeriksa jika ia disusun, dan jika tidak mengulangi. Dan dalam teori, probabilistically ini akan melengkapkan, tetapi selepas agak sedikit masa. Ia bukan yang paling cekap algoritma. Jadi apa-apa soalan kepada orang-orang algoritma atau apa-apa tertentu berkaitan di sana juga? 

Nah, mari kita kini mengusik selain apa yang semua ayat-ayat ini adalah bahawa saya telah melukis dan apa yang saya menganggap komputer boleh lakukan di bawah hood. Saya berpendapat bahawa semua nombor-nombor Saya menyimpan drawing-- mereka perlu mendapatkan disimpan di suatu tempat dalam ingatan. Kami akan menghilangkan lelaki ini sekarang juga. 

Jadi sekeping memori dalam computer-- supaya RAM DIMM adalah apa yang kita dicari semalam, dua memori sebaris module-- kelihatan seperti ini. Dan masing-masing cip hitam sedikit adalah nombor bait, biasanya. Dan kemudian pin emas adalah seperti wayar yang menyambung ke komputer, dan lembaga silikon hijau adalah hanya apa yang membuat segala-galanya bersama-sama. Jadi apakah ini benar-benar bermakna? Jika saya jenis menarik gambar yang sama, mari kita andaikan untuk kesederhanaan yang DIMM ini, dua modul memori sebaris, adalah satu gigabait RAM, satu gigabit ingatan, yang berapa banyak bait jumlah? Satu gigabyte adalah berapa banyak bait? Lebih daripada itu. 1124 adalah kilo, 1000. Mega juta. Giga adalah satu bilion. 

Adakah saya berbohong? Bolehkah kita walaupun membaca label? Ini sebenarnya 128 gigabait, jadi ia lebih. Tetapi kita akan berpura-pura ini hanya salah satu gigabit. Ini bermakna ada satu bilion bait memori yang tersedia untuk saya atau 8 bilion bit, tetapi kita akan bercakap dari segi bait sekarang, bergerak ke hadapan. 

Jadi apa yang bermakna adalah ini adalah satu bait, ini adalah bait lain, ini adalah bait lain, dan jika kita benar-benar mahu untuk menjadi tertentu kita perlu menarik satu bilion dataran kecil. Tetapi apa maksudnya? Baiklah, biar saya hanya zum dalam pada gambar ini. Jika saya ada sesuatu yang kelihatan seperti ini sekarang, itu empat bait. 

Oleh itu, saya boleh meletakkan empat nombor tersebut di sini. Satu dua tiga empat. Atau saya boleh meletakkan empat huruf atau simbol. "Hey!" boleh pergi di sana, kerana setiap huruf, kita dibincangkan sebelum ini, boleh diwakili dengan lapan bit atau ASCII atau satu bait. Jadi dalam erti kata lain, anda boleh meletakkan 8 bilion perkara di dalam satu kayu ini memori. Sekarang apa yang ia bermaksud untuk meletakkan perkara-perkara kembali ke belakang untuk kembali dalam ingatan seperti ini? Ini adalah apa yang programmer akan panggil "array." Dalam program komputer, anda tidak fikir mengenai perkakasan asas, per se. Anda hanya memikirkan diri anda sebagai mempunyai akses kepada sejumlah bilion bait, dan anda boleh apa sahaja yang anda mahu dengan ia. Tetapi untuk kemudahan ia biasanya berguna untuk menjaga hak ingatan anda bersebelahan antara satu sama lain seperti ini. Jadi jika saya mengezum masuk pada this-- kerana kita pasti tidak akan untuk menarik satu bilion squares-- sedikit mari kita andaikan bahawa lembaga ini mewakili bahawa kayu memori sekarang. Dan saya hanya akan menarik seramai saya penanda berakhir memberikan saya di sini. Jadi sekarang kita mempunyai kayu memori pada papan itu mendapat satu, dua, tiga, empat, lima, enam, satu, dua, tiga, empat, lima, enam, seven-- jadi 42 bait memori pada jumlah skrin. Terima kasih. Ya, adakah aritmetik saya betul. Jadi 42 bait memori di sini. Jadi apakah ini sebenarnya bermakna? Nah, seorang pengaturcara komputer akan sebenarnya umumnya memikirkan memori ini sebagai addressable. Dalam erti kata lain, setiap satu daripada lokasi dalam ingatan, dalam perkakasan, mempunyai alamat yang unik. 

Ia bukan seperti yang kompleks seperti One Brattle Square, Cambridge, Mass., 02138. Sebaliknya, ia hanya nombor. Ini adalah bilangan bait sifar, ini adalah satu, ini adalah dua, ini adalah tiga, dan ini adalah 41. Tunggu sebentar. Saya fikir saya berkata 42 sebentar tadi. Saya mula mengira pada sifar, jadi itulah sebenarnya betul. Sekarang kita tidak mempunyai untuk benar-benar menarik ia sebagai grid, dan jika anda menarik ia sebagai grid Saya rasa perkara yang sebenarnya mendapatkan sedikit mengelirukan. Apa programmer akan, dalam fikiran mereka sendiri, umumnya berfikir ini memori yang sama seperti pita, seperti sekeping pita pelekat yang hanya berjalan dan terus selama-lamanya atau sehingga anda kehabisan memori. Jadi cara yang lebih biasa untuk menarik dan hanya berfikir tentang memori akan bahawa ini adalah bait sifar, satu, dua, tiga, dan kemudian dot, dot, dot. Dan anda mempunyai 42 bytes seperti jumlah, walaupun walaupun secara fizikal ia mungkin sebenarnya menjadi sesuatu yang lebih seperti ini. 

Jadi, jika anda sekarang memikirkan anda memori ini, seperti pita, ini adalah apa yang programmer lagi akan memanggil pelbagai ingatan. Dan apabila anda mahu untuk benar-benar menyimpan sesuatu dalam memori komputer, biasanya anda lakukan kedai perkara back-to-back untuk back-to-back. Oleh itu, kita telah bercakap tentang nombor. Dan apabila saya mahu menyelesaikan masalah seperti empat, satu, tiga, dua, walaupun saya hanya melukis hanya pada nombor empat, satu, tiga, dua di atas kapal, komputer akan benar-benar mempunyai persediaan ini dalam ingatan. 

Dan apa yang akan menjadi sebelah dua dalam ingatan komputer? Well, tidak ada jawapan untuk itu. Kami tidak tahu. Dan selagi komputer tidak memerlukannya, ia tidak perlu mengambil berat apa yang akan datang kepada nombor ia berat tentang. Dan apabila saya berkata sebelum ini bahawa komputer hanya boleh melihat satu alamat pada satu masa, ini adalah jenis mengapa. 

Tidak seperti rekod pemain dan kepala membaca hanya dapat melihat yang tertentu alur dalam rekod lama-sekolah fizikal pada satu masa, sama boleh komputer terima kasih untuk CPU dan yang Intel set arahan, antara yang arahan dibaca daripada ingatan atau simpan ke memory-- yang komputer hanya boleh melihat di satu lokasi di time-- yang kadang-kadang kombinasi, tetapi benar-benar hanya satu lokasi pada satu masa. Oleh itu, apabila kita telah melakukan ini pelbagai algoritma, Saya tidak hanya menulis dalam vacuum-- empat, satu, tiga, dua. Nombor-nombor tersebut sebenarnya milik suatu tempat fizikal dalam ingatan. Jadi, terdapat sedikit kecil transistor atau beberapa jenis elektronik di bawahnya hood menyimpan nilai-nilai ini. 

Dan secara keseluruhan, berapa banyak bit adalah terlibat sekarang, hanya untuk menjadi jelas? Jadi ini adalah empat bait, atau kini ia 32 bit jumlah. Jadi sebenarnya ada 32 sifar dan yang mengarang empat perkara. Terdapat juga lebih di sini, tetapi sekali lagi kita tidak peduli tentang itu. 

Jadi sekarang mari kita tanya lain soalan menggunakan memori, kerana bahawa pada akhir hari ini adalah dalam varians. Tidak kira apa yang kita lakukan dengan komputer, pada akhir hari perkakasan yang masih sama di bawah hood. Bagaimana saya akan menyimpan perkataan dalam sini? Well, kata dalam komputer seperti "Hey!" akan disimpan sama seperti ini. Dan jika anda mahu yang lebih lama perkataan, anda hanya boleh menulis ganti itu dan mengatakan sesuatu seperti "hello" dan kedai yang di sini. 

Dan sebagainya di sini, juga, contiguousness ini sebenarnya kelebihan, kerana komputer hanya boleh dibaca dari kanan ke kiri. Tetapi di sini adalah satu soalan. Dalam konteks perkataan ini, h-e-l-l-o, tanda seru, bagaimana mungkin komputer tahu di mana perkataan bermula dan di mana perkataan itu berakhir? Dalam konteks nombor, bagaimana komputer tahu berapa lama urutan nombor adalah atau di mana ia bermula? Nah, ternyata out-- dan kami tidak akan pergi terlalu banyak ke tahap ini detail-- komputer bergerak barangan sekitar dalam ingatan secara literal melalui alamat ini. Jadi dalam komputer, jika anda menulis kod untuk menyimpan perkara seperti kata-kata, apa yang anda benar-benar lakukan adalah menaip ungkapan-ungkapan yang ingat di mana dalam ingatan komputer kata-kata ini. Jadi biarlah saya melakukan yang sangat, contoh yang sangat mudah. 

Saya akan pergi ke hadapan dan membuka program teks yang mudah, dan saya akan membuat fail yang dipanggil hello.c. Kebanyakan maklumat ini kita tidak akan pergi ke dengan terperinci, tetapi saya akan menulis program dalam bahasa yang sama, C. Ini adalah jauh lebih menakutkan, Saya berpendapat, daripada calar, tetapi ia sangat sama dalam semangat. Malah, kerinting ini jenis braces-- anda boleh sudah memikirkan apa yang saya hanya melakukan seperti ini. 

Mari kita buat ini, sebenarnya. Apabila bendera hijau diklik, lakukan yang berikut. Saya hendak mencetak "hello." Jadi sekarang ini adalah kod pseudo. Saya jenis mengaburkan garis. Dalam C, bahasa ini Saya bercakap kira-kira, talian cetak ini hello sebenarnya menjadi "printf" dengan beberapa kurungan dan koma bertitik. 

Tetapi ia adalah idea yang sama. Dan ini sangat user-friendly "Apabila bendera hijau diklik" menjadi lebih sukar difahami "tidak sah utama int." yang Dan ini benar-benar tidak mempunyai pemetaan, jadi saya hanya akan mengabaikan itu. Tetapi pendakap kerinting adalah seperti kepingan teka-teki melengkung seperti ini. 

Jadi anda jenis boleh sudah meneka. Walaupun anda tidak pernah diprogramkan sebelum ini, apakah program ini mungkin lakukan? Mungkin mencetak hello dengan tanda seru. 

Jadi mari kita cuba. Saya akan menyimpannya. Dan ini, sekali lagi, yang sangat persekitaran sekolah lama. Saya tidak boleh klik, saya tidak boleh seret. Saya perlu menaip arahan. Jadi saya mahu menjalankan program saya, jadi Saya mungkin melakukan ini, seperti hello.c. Itulah fail saya berlari. Tetapi tunggu, saya hilang langkah. Apa yang kita katakan adalah sesuatu yang perlu langkah untuk bahasa seperti C? Saya baru sahaja ditulis sumber kod, tetapi apa yang saya perlukan? Ya, saya perlu pengkompil. Maka pada Mac saya di sini, saya mempunyai program dipanggil GCC, GNU C compiler, yang membolehkan saya untuk berpatah this-- kod sumber saya ke dalam, kami akan memanggilnya, kod mesin. 

Dan saya boleh melihat bahawa, sekali lagi, seperti berikut, ini adalah sifar dan orang-orang yang saya dicipta dari kod sumber saya, semua sifar dan satu. Dan jika saya mahu menjalankan saya program-- ia berlaku untuk dipanggil a.out untuk reasons-- sejarah "hello." Saya boleh berjalan lagi. Hello, hello, hello. Dan ia seolah-olah bekerja. 

Tetapi itu bermakna suatu tempat di saya memori komputer adalah kata-kata h-e-l-l-o, tanda seru. Dan ternyata, hanya sebagai diketepikan, apa yang komputer akan biasanya lakukan supaya ia tahu di mana perkara mula dan end-- ia akan meletakkan simbol khas di sini. Dan konvensyen adalah untuk meletakkan nombor sifar pada akhir perkataan supaya anda tahu di mana ia sebenarnya berakhir, supaya anda tidak menyimpan mencetak lebih banyak watak-watak daripada yang anda sebenarnya berniat. 

Tetapi bisa dibesarkan di sini, walaupun walaupun ini agak sukar difahami, adalah bahawa ia akhirnya agak mudah. Anda telah diberi jenis pita, kosong ruang di mana anda boleh menulis surat. Anda hanya perlu mempunyai simbol khas, seperti sewenang-wenangnya nombor sifar, untuk meletakkan pada akhir kata-kata anda supaya komputer tahu, oh, saya perlu berhenti percetakan selepas Saya melihat tanda seru. Oleh kerana perkara yang akan datang terdapat adalah nilai ASCII sifar, atau watak nol sebagai ada orang yang memanggilnya. Tetapi ada jenis masalah di sini, dan mari kita kembali semula kepada nombor untuk seketika. Katakan yang saya lakukan, sebenarnya, mempunyai pelbagai nombor, dan andaikan bahawa program saya menulis adalah seperti buku gred untuk guru dan kelas guru. Dan program ini membolehkan dia atau dia menaip dalam skor pelajar mereka pada kuiz. Dan andaikan bahawa pelajar mendapat 100 pada kuiz pertama mereka, mungkin seperti 80 pada yang akan datang, maka 75, maka 90 kuiz keempat. 

Jadi pada ketika ini dalam cerita, array adalah saiz empat. Ada memori benar-benar lebih dalam komputer, tetapi pelbagai, jadi untuk bercakap, adalah saiz empat. Katakan sekarang bahawa guru mahu untuk menetapkan kuiz kelima kelas. Nah, salah satu daripada perkara-perkara yang atau dia akan perlu lakukan kini menyimpan nilai tambahan di sini. Tetapi jika array guru mempunyai diwujudkan dalam program ini adalah saiz untuk, salah satu masalah dengan array adalah yang anda tidak boleh hanya terus menambah kepada ingatan. Kerana bagaimana jika satu lagi sebahagian daripada program mempunyai perkataan "hey" di sana? 

Dengan kata lain, ingatan saya boleh digunakan untuk apa-apa dalam program. Dan jika terlebih dahulu saya menaip dalam, hey, Saya hendak input empat markah kuiz, mereka mungkin pergi di sini dan di sini. Dan jika anda tiba-tiba berubah fikiran kemudian dan berkata saya mahu kuiz kelima skor, anda tidak boleh hanya meletakkan ia di mana sahaja yang anda mahu, kerana apa jika ini memori yang digunakan sesuatu else-- beberapa program lain atau beberapa ciri lain program bahawa anda berjalan? Jadi, anda perlu berfikir terlebih dahulu bagaimana anda mahu menyimpan data anda, kerana sekarang anda telah dicat diri anda ke dalam sudut digital. 

Jadi seorang guru mungkin sebaliknya mengatakan apabila menulis program untuk menyimpan nya gred, anda tahu apa? Saya akan meminta, semasa menulis program saya, yang saya mahu sifar, satu, dua, tiga, empat, lima, enam, lapan gred jumlah. Jadi satu, dua, tiga, empat, lima, enam, tujuh, lapan. guru boleh hanya lebih-memperuntukkan memori semasa menulis program masing-masing dan berkata, anda tahu apa? Saya tidak akan memberikan lebih daripada lapan kuiz dalam sesuatu semester. Itu hanya gila. Saya tidak akan memperuntukkan bahawa. Supaya dengan cara ini dia mempunyai fleksibiliti untuk skor kedai pelajar, seperti 75, 90, dan mungkin satu tambahan di mana pelajar mendapat kredit tambahan, 105. 

Tetapi jika guru tidak pernah menggunakan ketiga-tiga ruang, ada Fleet intuitif di sini. Dia hanya membazirkan ruang. Jadi dalam erti kata lain, ini tradeoff biasa dalam pengaturcaraan di mana anda boleh sama ada memperuntukkan memori tepat seberapa banyak yang anda mahu, terbalik yang adalah bahawa anda super efficient-- anda tidak membazir di all-- tetapi keburukan yang adalah apa yang jika anda menukar fikiran anda apabila menggunakan program yang anda mahu menyimpan lebih banyak data daripada anda asalnya bertujuan. 

Jadi mungkin penyelesaian adalah, maka, menulis program anda dalam apa-apa cara bahawa mereka menggunakan lebih banyak memori melebihi daripada keperluannya. Dengan cara ini anda tidak akan untuk menghadapi masalah itu, tetapi anda satu pembaziran. Dan memori yang lebih program anda menggunakan, seperti yang kita bincangkan semalam, kurang memori yang tersedia untuk program lain, lebih cepat komputer anda mungkin memperlahankan turun kerana ingatan maya. Dan supaya penyelesaian yang ideal mungkin apa? 

Under-Memperuntukkan kelihatan buruk. Lebih-Memperuntukkan kelihatan buruk. Jadi apa yang mungkin menjadi penyelesaian yang lebih baik? Pembahagian semula. Menjadi lebih dinamik. Jangan memaksa diri anda untuk memilih priori, pada awal, apa yang anda mahu. Dan sudah tentu tidak lebih-memperuntukkan, supaya kamu jangan membazir. 

Dan sebagainya untuk mencapai matlamat itu, kita perlu membuang struktur data ini, jadi untuk bercakap, jauh. Dan supaya apa yang programmer biasanya akan menggunakan adalah sesuatu yang tidak yang dikenali mudah tetapi senarai berpaut. Dalam erti kata lain, dia akan mula memikirkan ingatan mereka sebagai jenis yang bentuk yang mereka boleh menarik dengan cara yang berikut. Jika saya mahu menyimpan satu nombor dalam yang program-- jadi ia September, Saya telah diberikan pelajar saya kuiz; saya mahu untuk menyimpan kuiz pertama pelajar, dan mereka mendapat 100 pada saya it-- Aku akan meminta komputer saya, melalui program yang saya telah bertulis, untuk satu sebahagian memori. Dan saya akan untuk menyimpan nombor 100 di dalamnya, dan itu sahaja. 

Kemudian beberapa minggu kemudian apabila saya kuiz kedua saya, dan ia adalah masa untuk menaip dalam 90%, saya akan untuk meminta komputer, hey, komputer, boleh saya mempunyai satu lagi sebahagian memori? Ia akan memberi saya ini sebahagian kosong memori. Saya akan dimasukkan ke dalam jumlah 90, tetapi dalam program saya entah bagaimana atau other-- dan kami tidak akan bimbang tentang sintaks untuk this-- saya perlu entah bagaimana rantai perkara-perkara ini bersama-sama. Dan saya akan rantai mereka bersama-sama dengan apa yang kelihatan seperti anak panah di sini. 

Kuiz yang ketiga yang datang, Saya akan berkata, hey, komputer, memberi saya satu lagi sebahagian memori. Dan saya akan meletakkan apa pun ia, seperti 75, dan saya perlu rantaian ini bersama-sama sekarang entah bagaimana. kuiz Keempat datang bersama-sama, dan mungkin itulah ke arah akhir semester. Dan ketika itu program saya mungkin menggunakan memori di seluruh tempat, di seluruh fizikal. Dan sebagainya hanya untuk tendangan, Saya akan menarik ini sebagainya quiz-- saya terlupa apa yang ia adalah; Saya rasa mungkin 80 atau something-- cara di sini. 

Tetapi itu tidak mengapa, kerana bergambar Saya akan menarik garis ini. Dalam erti kata lain, pada hakikatnya, dalam perkakasan komputer anda, skor pertama mungkin berakhir di sini kerana ia di awal semester. Yang seterusnya mungkin berakhir di sini kerana sedikit masa telah berlalu dan program terus berjalan. Rata-rata yang akan datang, yang 75, mungkin di sini. Dan skor yang terakhir mungkin 80, yang di sini. 

Jadi pada hakikatnya, secara fizikal, ini mungkin apa memori komputer anda kelihatan seperti. Tetapi ini bukan mental berguna paradigma seorang pengaturcara komputer. Mengapa anda perlu mengambil berat di mana palang pintu data anda berakhir? Anda hanya mahu untuk menyimpan data. 

Ini adalah jenis seperti perbincangan kita awal lukisan kiub. Mengapa kamu peduli apa sudut adalah kiub dan bagaimana anda perlu untuk menghidupkan untuk menarik ia? Anda hanya mahu kiub. Begitu juga di sini, anda hanya mahu buku gred. Anda hanya mahu memikirkan ini sebagai senarai nombor. Siapa yang peduli bagaimana ia dilaksanakan dalam perkakasan? 

Jadi abstraksi sekarang adalah gambar ini di sini. Ini adalah senarai dikaitkan, kerana programmer akan memanggilnya, setakat yang anda mempunyai senarai, jelas nombor. Tetapi ia dikaitkan bergambar melalui anak panah ini, dan semua anak panah ini ialah- bawah hood, jika anda ingin tahu, ingat bahawa perkakasan fizikal kita mempunyai alamat sifar, satu, dua, tiga, empat. Semua anak panah ini adalah seperti peta atau arahan, di mana jika 90 is-- sekarang Saya mendapat untuk mengira. 

Sifar, satu, dua, tiga, empat, lima, enam, tujuh. Ia kelihatan seperti 90 adalah di memori nombor alamat tujuh. Semua anak panah ini adalah seperti sekerap sedikit kertas yang yang memberi arahan kepada program yang mengatakan ikut peta ini untuk sampai ke lokasi tujuh. Dan di sana anda akan mencari yang skor kuiz kedua pelajar. Sementara itu, 75-- jika saya terus ini, ini adalah tujuh, lapan, sembilan, 10, 11, 12, 13, 14, 15. 

Ini anak panah lain hanya mewakili Peta ke lokasi memori 15. Tetapi sekali lagi, pengaturcara umumnya tidak tidak mengambil berat tentang tahap ini lanjut. Dan dalam kebanyakan setiap program bahasa hari ini, pengaturcara tidak akan tahu di mana dalam ingatan nombor-nombor ini sebenarnya. Semua dia mempunyai untuk mengambil berat tentang adalah bahawa mereka entah bagaimana dikaitkan bersama-sama dalam struktur data seperti ini. 

Tetapi ternyata tidak untuk mendapatkan terlalu teknikal. Tetapi hanya kerana kita boleh mungkin mampu untuk mempunyai perbincangan ini di sini, katalah kita semula isu ini di sini array. Mari kita lihat jika kita kesal kerana pergi di sini. Ini adalah 100, 90, 75, dan 80. 

Biar saya secara ringkas membuat tuntutan ini. Ini adalah pelbagai, dan sekali lagi, ciri-ciri penting array adalah bahawa semua data anda kembali ke kembali ke belakang dalam memory-- literal satu bait atau mungkin empat bait, beberapa nombor tetap bait jauh. Dalam senarai berpaut, yang kita mungkin menarik seperti ini, di bawah hood yang tahu di mana barangan itu? Ia juga tidak perlu mengalir seperti ini. Antara data boleh menjadi kembali ke sebelah kiri di sana. Anda tidak tahu. 

Dan sebagainya dengan array, anda mempunyai ciri dikenali sebagai capaian rawak. Dan apa cara akses rawak adalah bahawa komputer boleh melompat serta-merta kepada mana-mana lokasi dalam array. Mengapa? Kerana komputer itu tahu lokasi itu yang pertama adalah sifar, satu, dua, dan tiga. 

Dan jadi jika anda mahu pergi dari elemen ini kepada elemen seterusnya, anda secara literal, dalam fikiran komputer, hanya menambah satu. Jika anda ingin pergi ke elemen yang ketiga, hanya menambah one-- elemen seterusnya, hanya menambah satu. Walau bagaimanapun, dalam versi ini cerita, rasa komputer kini sedang pada atau berurusan dengan nombor 100. Bagaimana anda mendapatkan ke depan gred dalam buku gred? 

Anda perlu mengambil masa tujuh langkah-langkah, yang sewenang-wenangnya. Untuk sampai ke satu depan, anda perlu untuk mengambil masa lapan langkah-langkah lain untuk sampai ke 15. Dalam erti kata lain, ia bukan satu jurang yang berterusan antara nombor, dan sebagainya ia hanya mengambil komputer lebih banyak masa titik. Komputer mempunyai untuk mencari melalui memori untuk untuk mencari apa yang anda cari. 

Jadi manakala array cenderung menjadi data yang cepat structure-- kerana anda boleh benar-benar hanya melakukan aritmetik mudah dan mendapatkan di mana anda mahu dengan menambah satu, untuk instance-- senarai berpaut, kausembelih ciri asal. Anda tidak boleh hanya pergi dari pertama untuk kedua ketiga keempat. Anda perlu mengikuti peta. Anda perlu mengambil langkah-langkah yang lebih untuk sampai ke nilai-nilai, yang seolah-olah menjadi menambah kos. Jadi, kita membayar harga yang, tetapi apa yang ciri yang Dan telah memohon di sini? Apakah senarai berpaut nampaknya membolehkan kita untuk melakukan, yang merupakan asal-usul cerita tertentu ini? 

Tepat sekali. A saiz dinamik kepadanya. Kita boleh menambah kepada senarai ini. Kami juga boleh mengecutkan senarai, jadi bahawa kita hanya menggunakan memori sebanyak seperti yang kita benar-benar mahu dan sebagainya kami tidak pernah lebih-Memperuntukkan. 

Kini hanya menjadi benar-benar nit-cerewet, ada kos tersembunyi. Jadi, anda tidak boleh hanya beritahu saya meyakinkan anda bahawa ini adalah tradeoff menarik. Ada kos tersembunyi lain di sini. Manfaat ini, jelas, ialah kita mendapatkan dinamik. Jika saya mahu elemen lain, saya boleh hanya menarik dan meletakkan nombor di sana. Dan kemudian saya boleh menghubungkannya dengan gambar di sini, sedangkan di sini, sekali lagi, jika saya telah dicat diri saya ke satu sudut, jika sesuatu yang lain telah menggunakan memori di sini, saya daripada nasib. Saya telah dicat diri saya ke sudut. 

Tetapi apa yang tersembunyi kos dalam gambar ini? Ia bukan hanya jumlah yang masa yang diperlukan untuk pergi dari sini ke sini, iaitu tujuh langkah, kemudian lapan langkah-langkah, yang lebih daripada satu. Apa yang lain kos tersembunyi? Bukan sahaja masa. Maklumat tambahan boleh perlu untuk mencapai gambar ini. 

Ya, peta itu, mereka sisa sedikit kertas, kerana saya terus menggambarkan mereka sebagai. Ini arrows-- mereka tidak bebas. A computer-- anda tahu apa komputer mempunyai. Ia mempunyai sifar dan satu. Jika anda mahu untuk mewakili anak panah atau peta atau nombor, anda memerlukan ingatan. Jadi harga lain yang anda membayar untuk senarai berpaut, sains komputer biasa sumber, juga ruang. 

Dan sesungguhnya begitu, jadi biasa, antara melepas dalam mereka bentuk kejuruteraan perisian sistem adalah masa dan space-- adalah dua daripada bahan-bahan anda, dua bahan-bahan yang paling mahal anda. Ini menelan belanja saya lebih banyak masa kerana saya perlu mengikuti peta ini, tetapi ia juga menelan belanja saya lebih banyak ruang kerana saya perlu menjaga peta ini sekitar. Jadi harapan, kerana kita ada jenis dibincangkan lebih semalam dan hari ini, adalah bahawa faedah akan melebihi kos. 

Tetapi tidak ada penyelesaian yang jelas di sini. Mungkin ia adalah better-- cepat la dan kotor, sebagai Kareem dicadangkan earlier-- untuk membuang memori pada masalah ini. Hanya membeli lebih banyak memori, berfikir kurang keras tentang menyelesaikan masalah ini, dan menyelesaikannya dengan cara yang lebih mudah. Dan sesungguhnya sebelum ini, apabila kita bercakap tentang melepas, ia bukan ruang dalam komputer dan masa. Ia adalah masa pemaju, yang lagi sumber lain. 

Jadi sekali lagi, ia adalah tindakan penyeimbangan ini cuba untuk membuat keputusan yang mana perkara-perkara adakah anda bersedia untuk berbelanja? Yang adalah yang paling mahal? Yang menghasilkan keputusan yang lebih baik? Yeah? 

Sungguh benar. Dalam kes ini, jika anda mewakili nombor dalam maps-- yang ini dipanggil dalam pelbagai bahasa "Petunjuk" atau "alamat" - ia adalah dua ruang. Yang tidak semestinya seburuk berganda jika sekarang kita hanya menyimpan nombor. Katakan bahawa kita telah menyimpan rekod pesakit di hospital-- yang supaya nama Pierson, nombor telefon, nombor keselamatan sosial, doktor sejarah. Kotak ini mungkin banyak, lebih besar, di mana penunjuk kecil sedikit, alamat seterusnya element-- ia bukan satu masalah besar. Ia seperti pinggiran yang kos ia tidak mengapa. Tetapi dalam kes ini, ya, ia adalah dua kali ganda a. Soalan yang baik. 

Mari kita bercakap tentang masa yang sedikit dengan lebih kukuh. Apakah masa yang berjalan pencarian senarai ini? Katakan saya mahu mencari melalui semua gred pelajar, dan ada gred n dalam struktur data ini. Di sini juga, kita boleh meminjam perbendaharaan kata lebih awal. Ini adalah struktur data linear. 

O Big n adalah apa yang diperlukan untuk mendapatkan ke akhir struktur data ini, whereas-- dan kami tidak melihat ini sebelum itu array memberikan anda apa yang dipanggil masa yang berterusan, yang bermaksud satu langkah atau dua langkah atau 10 steps-- tidak mengapa. Ia adalah nombor yang tetap. Ia tidak ada kena mengena dengan saiz array. Dan sebab itu, sekali lagi, capaian rawak. Komputer hanya boleh segera melompat ke lokasi lain, kerana mereka semua yang sama jarak dari segala-galanya. Tidak ada pemikiran yang terlibat. Baiklah. Jadi, jika saya boleh, saya cuba untuk cat dua gambar akhir. A satu yang biasa dikenali sebagai jadual hash. Jadi untuk memberi motivasi kepada perbincangan ini, biarlah saya berfikir tentang bagaimana untuk melakukan ini. 

Jadi bagaimana pula ini? Katakan bahawa masalah ini kita mahu menyelesaikan sekarang sedang melaksanakan dalam dictionary-- yang supaya sejumlah besar perkataan Inggeris atau apa sahaja. Dan matlamatnya adalah untuk dapat menjawab soalan bentuk ini ialah perkataan? Jadi, anda mahu untuk melaksanakan penyemak ejaan, hanya seperti kamus fizikal bahawa anda boleh melihat perkara dalam. Katakan saya adalah untuk melakukan ini dengan array. Saya boleh melakukan ini. 

Dan andaikan perkataan epal dan pisang dan tembikai. Dan saya tidak boleh berfikir buah-buahan yang bermula dengan d, jadi kami hanya akan mempunyai tiga buah-buahan. Jadi ini adalah pelbagai, dan kami menyimpan semua kata-kata ini dalam kamus ini sebagai array. Persoalannya, maka, adalah bagaimana lagi anda boleh menyimpan maklumat ini? 

Well, Saya jenis menipu di sini, kerana setiap huruf-huruf dalam perkataan adalah benar-benar satu bait individu. Jadi jika saya benar-benar mahu menjadi nit-cerewet, saya perlu benar-benar dapat membahagikan ini ke dalam banyak ketulan yang lebih kecil memori, dan kita boleh melakukan perkara tersebut. Tetapi kita akan menghadapi masalah yang sama seperti sebelum ini. Bagaimana jika, sebagai Merriam Webster atau Oxford juga setiap year-- mereka menambah kata-kata kepada dictionary-- kita tidak semestinya mahu cat diri kita ke penjuru dengan array? 

Jadi, mungkin pendekatan yang lebih bijak adalah untuk meletakkan epal dalam nod sendiri atau kotak, seperti yang kita katakan, pisang, dan maka di sini kita ada tembikai. Dan kita rentetan perkara-perkara ini bersama-sama. Jadi ini adalah array, dan ini adalah senarai yang dipautkan. Jika anda tidak boleh agak lihat, ia hanya berkata "array," dan ini mengatakan "senarai." 

Oleh itu, kita mempunyai yang sama isu-isu sebenar seperti sebelum ini, di mana kita kini mempunyai dinamik dalam senarai dikaitkan kami. Tetapi kita mempunyai kamus yang agak perlahan. Katakan Saya hendak mencari perkataan. Ia mungkin mengambil masa saya O besar n langkah-langkah, kerana perkataan yang mungkin menjadi sepanjang jalan pada akhir senarai, seperti tembikai. Dan ternyata bahawa dalam pengaturcaraan, jenis daripada kaedah berpotensi suci data struktur, adalah sesuatu yang memberikan anda berterusan masa seperti array tetapi yang masih memberikan anda dinamik. 

Jadi boleh kita mempunyai yang terbaik daripada kedua-dua dunia? Dan sesungguhnya, ada sesuatu dipanggil jadual hash yang membolehkan anda untuk melakukan perkara yang, walaupun kira-kira. Satu jadual hash adalah pelamun struktur data yang kita boleh berfikir sebagai kombinasi array-- yang dan saya akan menarik ia seperti this-- dan senarai berkaitan bahawa saya akan menarik seperti ini di sini. 

Dan cara perkara ini kerja-kerja adalah seperti berikut. Jika ini sekarang-- hash table-- adalah struktur data ketiga saya, dan saya mahu menyimpan kata-kata dalam hal ini, saya tidak mahu hanya menyimpan semua fakta yang kembali ke belakang untuk kembali ke belakang. Saya mahu memanfaatkan beberapa sekeping maklumat mengenai kata-kata yang akan membiarkan saya mendapatkannya di mana ia lebih cepat. 

Jadi memandangkan epal kata-kata dan pisang dan tembikai, Saya sengaja memilih kata-kata. Mengapa? Apakah jenis asasnya berbeza tentang tiga? Apa yang jelas? Mereka bermula dengan huruf yang berbeza. 

Jadi, anda tahu apa? Bukannya meletakkan segala perkataan-Ku di baldi yang sama, jadi untuk bercakap, seperti dalam satu senarai yang besar, mengapa tidak melakukannya Saya sekurang-kurangnya cuba pengoptimuman dan membuat senarai saya 1/26 lama. A pengoptimuman menarik mungkin mengapa tidak Saya-- apabila memasukkan perkataan ke dalam struktur data ini, ke dalam ingatan komputer, mengapa saya tidak meletakkan semua 'a' perkataan di sini, segala perkataan 'b' di sini, dan semua perkataan 'c' di sini? Jadi ini berakhir meletakkan epal di sini, pisang sini, tembikai sini, dan sebagainya. 

Dan jika saya mempunyai tambahan perkataan like-- apa yang lain? Apple, pisang, pir. Sesiapa memikirkan buah yang bermula dengan a, b, atau c? sempurna Blueberry--. Yang akan berakhir di sini. Dan dengan itu kita seolah-olah mempunyai sedikit penyelesaian yang lebih baik, kerana sekarang jika saya mahu untuk mencari epal, saya first-- Saya tidak hanya menyelam ke dalam struktur data saya. Saya tidak menyelam ke dalam memori komputer saya. Saya mula-mula melihat surat pertama. 

Dan ini adalah apa yang komputer saintis akan berkata. Anda hash ke dalam struktur data anda. Anda mengambil input anda, yang kes ini adalah satu perkataan seperti epal. Anda menganalisisnya, melihat huruf pertama dalam kes ini, dengan itu hashing ia. Hashing adalah di mana istilah umum anda mengambil sesuatu sebagai input dan anda menghasilkan beberapa output. Dan output dalam yang kes adalah lokasi yang anda ingin cari, yang pertama lokasi, lokasi kedua, ketiga. Jadi input adalah epal, keluaran adalah pertama. input adalah pisang, yang output harus kedua. input adalah tembikai, output harus ketiga. input adalah blueberry, yang output perlu lagi menjadi kedua. Dan itulah yang membantu anda mengambil pintasan melalui ingatan anda untuk mendapatkan kata-kata atau data yang lebih berkesan. 

Sekarang ini menjimatkan masa kita berpotensi sebanyak satu daripada 26, kerana jika anda menganggap bahawa anda mempunyai banyak "a" perkataan sebagai "z" perkataan yang perkataan "q", yang tidak benar-benar realistic-- anda akan mempunyai condong seluruh surat tertentu alphabet-- yang tetapi ini akan menjadi tambahan pendekatan yang tidak membenarkan anda untuk mendapatkan kata-kata lebih cepat. Dan pada hakikatnya, yang canggih program, Googles dunia, yang Facebooks daripada world-- mereka akan menggunakan jadual hash untuk banyak tujuan yang berlainan. Tetapi mereka tidak akan menjadi begitu naif untuk hanya melihat huruf pertama dalam epal atau pisang atau pir atau tembikai, kerana seperti yang anda lihat ini senarai masih boleh lama. 

Dan hal ini masih ada semacam daripada linear-- jadi semacam perlahan, seperti dengan o besar n yang kita dibincangkan sebelum ini. Jadi apa jadual hash yang baik yang sebenar akan do-- ia akan mempunyai pelbagai yang lebih besar. Dan ia akan menggunakan lebih fungsi hashing canggih, supaya ia tidak hanya melihat "a." Mungkin ia kelihatan pada "a-p-p-l-e" dan entah bagaimana menukarkan mereka lima huruf ke lokasi di mana epal perlu disimpan. Kami hanya naif menggunakan huruf 'a' sahaja, kerana ia adalah baik dan mudah. 

Tetapi jadual hash, dalam Akhirnya, anda boleh berfikir sebagai gabungan pelbagai, setiap yang mempunyai senarai berpaut yang ideal perlu sebagai pendek yang mungkin. Dan ini bukanlah satu penyelesaian yang jelas. Malah, banyak penalaan halus yang berlaku di bawah hood apabila melaksanakan ini jenis struktur data yang canggih adalah apa yang kanan panjang array? Apakah fungsi hash yang betul? Bagaimana anda menyimpan perkara-perkara dalam ingatan? 

Tetapi sedar berapa cepat seperti ini perbincangan meningkat, sama ada setakat ini bahawa ia adalah jenis lebih kepala seseorang pada ketika ini, yang adalah baik. Tetapi kami mula, ingat, dengan benar-benar sesuatu peringkat rendah dan elektronik. Dan hal ini sekali lagi adalah ini tema abstraksi, di mana sebaik sahaja anda mula untuk mengambil untuk diberikan, OK, saya telah mendapat it-- ada memori fizikal, OK, faham, setiap lokasi fizikal mempunyai alamat, OK, saya mendapat ia, saya boleh mewakili alamat tersebut sebagai arrows-- anda boleh dengan cepat mula mempunyai perbualan yang lebih canggih yang pada akhirnya seolah-olah akan membolehkan kita untuk menyelesaikan masalah seperti mencari dan menyusun dengan lebih berkesan. Dan yakinlah, too-- kerana saya rasa ini adalah yang paling dalam kami telah pergi ke beberapa ini topik CS proper-- kami telah dilakukan dalam sehari dan setengah di ini menunjukkan apa yang anda biasanya boleh melakukan lebih perjalanan lapan minggu dalam sesuatu semester. 

Sebarang pertanyaan mengenai ini? Tidak? Baiklah. Nah, mengapa tidak kita berhenti seketika di sana, mula makan tengah hari beberapa minit awal, disambung semula pada hanya kira-kira satu jam? Dan saya akan berlama-lama untuk sedikit dengan soalan. Kemudian saya akan perlu pergi mengambil panggilan pasangan jika itu OK. Saya akan menghidupkan muzik beberapa dalam masa yang sama, tetapi makan tengah hari harus sekitar sudut.