1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [MUSIK BERMAIN] 3 00:00:03,340 --> 00:00:11,020 4 00:00:11,020 --> 00:00:14,010 >> DAVID MALAN: Ini adalah CS50. 5 00:00:14,010 --> 00:00:18,090 Dan ini adalah kedua-dua awal dan end-- seperti literally-- hampir akhirnya 6 00:00:18,090 --> 00:00:18,825 dari minggu ke enam. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Saya fikir saya akan berkongsi sedikit dari fakta yang menyenangkan. 9 00:00:22,640 --> 00:00:25,370 Saya telah ditarik ke atas ini dari data semester terakhir ini ditetapkan. 10 00:00:25,370 --> 00:00:29,710 Anda mungkin ingat bahawa kami meminta anda pada setiap p bentuk set jika anda telah melihat dalam talian 11 00:00:29,710 --> 00:00:31,580 atau jika anda telah menghadiri secara peribadi. 12 00:00:31,580 --> 00:00:33,020 Dan di sini adalah data. 13 00:00:33,020 --> 00:00:34,710 Jadi hari ini adalah sangat diramalkan. 14 00:00:34,710 --> 00:00:37,126 Tapi kami ingin menghabiskan sedikit waktu dengan Anda tetap. 15 00:00:37,126 --> 00:00:40,599 Apakah ada yang mau menduga mengapa ini grafik sangat bergerigi, naik turun, naik turun, 16 00:00:40,599 --> 00:00:41,265 secara konsisten? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Apa yang setiap satu daripada puncak dan palung mewakili? 19 00:00:45,130 --> 00:00:46,005 >> PENONTON: [didengar] 20 00:00:46,005 --> 00:00:47,002 21 00:00:47,002 --> 00:00:47,835 DAVID MALAN: Memang. 22 00:00:47,835 --> 00:00:50,900 23 00:00:50,900 --> 00:00:55,480 Dan yang lebih lucu, Allah melarang, kita memegang satu ceramah pada hari Jumaat 24 00:00:55,480 --> 00:00:58,960 pada awal semester, itulah yang kita lihat berlaku. 25 00:00:58,960 --> 00:01:03,430 Jadi hari ini, kita mengambil dalam sedikit lebih lanjut mengenai struktur data. 26 00:01:03,430 --> 00:01:06,660 Dan untuk memberikan anda lebih banyak dari yang kukuh model mental untuk masalah di lima, 27 00:01:06,660 --> 00:01:07,450 yang kini keluar. 28 00:01:07,450 --> 00:01:10,817 Salah ejaan, di mana, kita akan menyerahkan fail teks beberapa 100,000 29 00:01:10,817 --> 00:01:12,650 ditambah kata-kata bahasa Inggeris, dan Anda akan mempunyai 30 00:01:12,650 --> 00:01:17,770 untuk memikirkan bagaimana untuk cerdik beban mereka ke dalam memori, ke dalam RAM, menggunakan beberapa data 31 00:01:17,770 --> 00:01:19,330 struktur pilihan anda. 32 00:01:19,330 --> 00:01:22,470 >> Sekarang satu struktur data tersebut boleh berkenaan, tetapi mungkin tidak boleh, 33 00:01:22,470 --> 00:01:25,630 senarai yang agak mudah dikaitkan, yang kami memperkenalkan masa lalu. 34 00:01:25,630 --> 00:01:29,220 Dan senarai yang dikaitkan mempunyai sekurang-kurangnya satu kelebihan berbanding array. 35 00:01:29,220 --> 00:01:32,096 Apa yang salah satu keuntungan dari senarai berpaut boleh dikatakan? 36 00:01:32,096 --> 00:01:32,950 >> PENONTON: Pemasukan. 37 00:01:32,950 --> 00:01:33,908 >> DAVID MALAN: Pemasukan. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Apa yang kamu maksudkan dengan itu? 40 00:01:35,196 --> 00:01:37,872 >> PENONTON: Di mana-mana bersama-sama senarai [terdengar]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID MALAN: Baik. 42 00:01:38,770 --> 00:01:42,090 Oleh itu, anda boleh memasukkan elemen di mana sahaja anda mahu di tengah-tengah senarai 43 00:01:42,090 --> 00:01:45,490 tanpa perlu shuffle apa-apa, mana kita membuat kesimpulan, dalam pengasingan kami 44 00:01:45,490 --> 00:01:47,630 perbincangan, bukan semestinya satu perkara yang baik, 45 00:01:47,630 --> 00:01:51,200 kerana ia mengambil masa untuk benar-benar bergerak semua jenis manusia yang kiri atau kanan. 46 00:01:51,200 --> 00:01:55,540 Dan sebagainya dengan senarai yang disambungkan, anda boleh hanya memperuntukkan dengan malloc, nod baru, 47 00:01:55,540 --> 00:01:58,385 dan kemudian mengemas beberapa pointers-- dua, tiga operasi max-- 48 00:01:58,385 --> 00:02:01,480 dan kita mampu untuk slot seseorang di mana-mana sahaja dalam senarai. 49 00:02:01,480 --> 00:02:03,550 >> Apa lagi yang berfaedah tentang senarai berpaut? 50 00:02:03,550 --> 00:02:04,980 51 00:02:04,980 --> 00:02:05,659 Ya? 52 00:02:05,659 --> 00:02:06,534 >> PENONTON: [didengar] 53 00:02:06,534 --> 00:02:07,538 54 00:02:07,538 --> 00:02:08,413 DAVID MALAN: Perfect. 55 00:02:08,413 --> 00:02:10,590 56 00:02:10,590 --> 00:02:11,090 Sempurna. 57 00:02:11,090 --> 00:02:12,070 Ia benar-benar dinamik. 58 00:02:12,070 --> 00:02:15,100 Dan bahawa anda tidak melakukan, terlebih dahulu, untuk beberapa ukuran yang tetap 59 00:02:15,100 --> 00:02:18,750 sebahagian memori, seperti anda akan mempunyai untuk dengan array, terbalik di mana 60 00:02:18,750 --> 00:02:22,455 adalah bahawa anda boleh memperuntukkan nod hanya pada permintaan itu dengan hanya menggunakan lebih banyak ruang 61 00:02:22,455 --> 00:02:23,330 kerana anda benar-benar perlu. 62 00:02:23,330 --> 00:02:26,830 Sebaliknya dengan array, anda mungkin sengaja memperuntukkan terlalu sedikit. 63 00:02:26,830 --> 00:02:28,871 Dan kemudian ia hanya akan menjadi sakit di leher 64 00:02:28,871 --> 00:02:32,440 mengagihkan semula lokasi baru yang lebih besar, menyalin semuanya berakhir, membebaskan array lama, 65 00:02:32,440 --> 00:02:33,990 dan kemudian bergerak perniagaan anda. 66 00:02:33,990 --> 00:02:37,479 Atau lebih teruk lagi, anda mungkin memperuntukkan cara memori lebih daripada yang anda benar-benar perlu, 67 00:02:37,479 --> 00:02:40,520 dan supaya anda akan mempunyai sangat pelbagai jarang penduduknya, boleh dikatakan. 68 00:02:40,520 --> 00:02:44,350 >> Jadi senarai berpaut memberi anda ini kelebihan dan memberi fleksibiliti 69 00:02:44,350 --> 00:02:46,080 dengan sisipan dan penghapusan kata. 70 00:02:46,080 --> 00:02:48,000 Tapi tentunya mesti ada harga yang harus dibayar. 71 00:02:48,000 --> 00:02:50,000 Malah, salah satu tema dijelajahi dengan kuiz sifar 72 00:02:50,000 --> 00:02:52,430 adalah beberapa trade-off kita telah melihat setakat ini. 73 00:02:52,430 --> 00:02:56,161 Jadi apa harga yang telah dibayar atau yang downside dari senarai berpaut? 74 00:02:56,161 --> 00:02:56,660 Yeah. 75 00:02:56,660 --> 00:02:57,560 >> PENONTON: Tiada akses rawak. 76 00:02:57,560 --> 00:02:58,809 >> DAVID MALAN: Tiada akses rawak. 77 00:02:58,809 --> 00:02:59,540 Tapi siapa yang peduli? 78 00:02:59,540 --> 00:03:01,546 Capaian rawak tidak bunyi yang menarik. 79 00:03:01,546 --> 00:03:02,421 >> PENONTON: [didengar] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID MALAN: Tepat sekali. 82 00:03:05,740 --> 00:03:07,580 Jika anda ingin mempunyai yang algorithm-- tertentu 83 00:03:07,580 --> 00:03:10,170 dan biarkan aku sebenarnya mencadangkan carian binari khususnya, yang 84 00:03:10,170 --> 00:03:12,600 adalah salah satu kami telah digunakan agak bit-- yang jika anda tidak mempunyai akses rawak, 85 00:03:12,600 --> 00:03:15,516 Anda tidak boleh melakukan itu aritmetik mudah mencari elemen seperti tengah 86 00:03:15,516 --> 00:03:16,530 dan melompat hak untuk itu. 87 00:03:16,530 --> 00:03:20,239 Anda malah harus bermula yang pertama elemen dan linear mencari dari kiri 88 00:03:20,239 --> 00:03:22,780 ke kanan jika anda mahu untuk mencari tengah atau sebarang unsur lain. 89 00:03:22,780 --> 00:03:24,410 >> PENONTON: Ia mungkin mengambil masa lebih banyak memori. 90 00:03:24,410 --> 00:03:25,040 >> DAVID MALAN: Membawa lebih banyak memori. 91 00:03:25,040 --> 00:03:27,464 Di mana ialah tambahan biaya yang berasal dari dalam ingatan? 92 00:03:27,464 --> 00:03:28,339 >> PENONTON: [didengar] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID MALAN: Tepat sekali. 95 00:03:33,440 --> 00:03:35,679 Dalam kes ini di sini, kami mempunyai daftar link untuk bilangan bulat, 96 00:03:35,679 --> 00:03:37,470 tetapi kita dua kali ganda jumlah memori 97 00:03:37,470 --> 00:03:39,680 kita perlu dengan juga menyimpan pointer ini. 98 00:03:39,680 --> 00:03:42,090 Sekarang kurang dari masalah besar seperti struct anda mendapatkan yang lebih besar 99 00:03:42,090 --> 00:03:45,320 dan anda menyimpan bukan angka tetapi mungkin seorang pelajar atau beberapa objek lain. 100 00:03:45,320 --> 00:03:46,880 Tapi yang pasti tetap. 101 00:03:46,880 --> 00:03:49,421 Dan sebagainya beberapa operasi pada daftar terkait dipanggil 102 00:03:49,421 --> 00:03:50,570 adalah O besar linear n--. 103 00:03:50,570 --> 00:03:54,730 Hal-hal seperti penyisipan atau carian atau penghapusan dalam hal unsur 104 00:03:54,730 --> 00:03:57,720 kebetulan berada di akhir sangat daftar apakah itu disusun atau tidak. 105 00:03:57,720 --> 00:04:01,167 >> Kadang-kadang anda mungkin beruntung dan di batas sehingga lebih rendah pada operasi ini 106 00:04:01,167 --> 00:04:04,250 juga mungkin masa yang berterusan jika anda selalu melihat elemen yang pertama, 107 00:04:04,250 --> 00:04:05,070 misalnya. 108 00:04:05,070 --> 00:04:09,360 Tetapi pada akhirnya, kita berjanji untuk mencapai kaedah berpotensi suci 109 00:04:09,360 --> 00:04:12,630 struktur data, atau beberapa daripadanya perkiraan, 110 00:04:12,630 --> 00:04:14,290 dengan cara masa yang sama. 111 00:04:14,290 --> 00:04:17,579 Bolehkah kita dapati unsur-unsur atau menambah unsur-unsur atau mengeluarkan unsur-unsur dari senarai? 112 00:04:17,579 --> 00:04:19,059 Kita akan lihat tidak lama lagi. 113 00:04:19,059 --> 00:04:21,100 Dan ternyata yang satu mekanisme kami 114 00:04:21,100 --> 00:04:23,464 akan mula menggunakan hari ini, penggunaan tahunan p meletakkan lima, 115 00:04:23,464 --> 00:04:24,630 sebenarnya cukup akrab. 116 00:04:24,630 --> 00:04:27,430 Sebagai contoh, jika ini adalah sekumpulan buku ujian, yang masing-masing 117 00:04:27,430 --> 00:04:29,660 mempunyai pelajar pertama nama dan nama akhir di atasnya, 118 00:04:29,660 --> 00:04:31,820 dan saya menjemput mereka dari pada akhir peperiksaan, 119 00:04:31,820 --> 00:04:33,746 dan mereka semua cukup banyak dalam susunan rawak, 120 00:04:33,746 --> 00:04:36,370 dan kami mahu pergi tentang menyortir ini ujian sehingga setelah dinilai 121 00:04:36,370 --> 00:04:38,661 ia hanya lebih mudah dan lebih cepat untuk menyerahkan mereka kembali 122 00:04:38,661 --> 00:04:40,030 kepada pelajar-pelajar mengikut abjad. 123 00:04:40,030 --> 00:04:42,770 Apa yang akan menjadi naluri anda untuk timbunan ujian seperti ini? 124 00:04:42,770 --> 00:04:45,019 >> Nah, jika anda seperti saya, anda mungkin akan melihat bahawa ini adalah m, 125 00:04:45,019 --> 00:04:48,505 jadi saya akan ke semacam meletakkan ini ke dalam, jika ini adalah meja saya atau lantai di mana 126 00:04:48,505 --> 00:04:50,650 Saya menyebarkan perkara out-- atau array saya really-- 127 00:04:50,650 --> 00:04:52,210 Saya mungkin meletakkan semua Cik di sana. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Berikut adalah gred A. Jadi saya mungkin meletakkan Seperti di sini. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Berikut adalah satu lagi A. Saya akan untuk meletakkan bahawa di sini. 132 00:04:57,980 --> 00:05:02,490 Berikut adalah Z. yang Di sini adalah satu lagi M. Dan sebagainya Saya mungkin mula membuat tumpukan seperti ini. 133 00:05:02,490 --> 00:05:06,620 Dan kemudian mungkin saya akan pergi nanti dan semacam sangat nitpicky-ly semacam 134 00:05:06,620 --> 00:05:07,710 buasir individu. 135 00:05:07,710 --> 00:05:11,300 Tapi yang penting saya akan melihat di input yang saya tangan 136 00:05:11,300 --> 00:05:14,016 dan saya akan membuat beberapa dikira keputusan berdasarkan input itu. 137 00:05:14,016 --> 00:05:15,640 Jika ia bermula dengan A, meletakkan ia di sana. 138 00:05:15,640 --> 00:05:18,980 Jika ia bermula dengan Z, meletakkannya di di sana, dan segala sesuatu di antara. 139 00:05:18,980 --> 00:05:22,730 >> Jadi ini adalah satu teknik yang umumnya dikenali sebagai hashing-- H-A-S-H-- 140 00:05:22,730 --> 00:05:26,550 yang secara umum berarti mengambil sebagai input dan menggunakan input itu untuk menghitung 141 00:05:26,550 --> 00:05:30,940 nilai, umumnya nombor, dan bahawa jumlah adalah indeks ke dalam simpanan yang 142 00:05:30,940 --> 00:05:32,260 bekas, seperti array. 143 00:05:32,260 --> 00:05:35,490 Jadi dengan kata lain, saya mungkin mempunyai fungsi hash, seperti yang saya lakukan dalam kepala saya, 144 00:05:35,490 --> 00:05:37,940 bahawa jika saya melihat seseorang yang nama yang bermula dengan A, 145 00:05:37,940 --> 00:05:40,190 Saya akan peta yang kepada sifar dalam kepala saya. 146 00:05:40,190 --> 00:05:44,160 Dan jika saya melihat seseorang dengan Z, saya akan peta yang ke 25 di kepala saya 147 00:05:44,160 --> 00:05:46,220 dan kemudian memasukkan ke dalam tumpukan terakhir paling. 148 00:05:46,220 --> 00:05:50,990 >> Sekarang, jika anda berfikir tentang tidak otak saya tetapi program C, apa nombor boleh 149 00:05:50,990 --> 00:05:53,170 anda bergantung kepada untuk mencapai keputusan yang sama? 150 00:05:53,170 --> 00:05:55,594 Dengan kata lain, jika anda mempunyai karakter ASCII A, 151 00:05:55,594 --> 00:05:57,510 bagaimana anda menentukan apa baldi untuk memasukkannya ke dalam? 152 00:05:57,510 --> 00:05:59,801 Anda mungkin tidak mahu memasukkannya ke dalam baldi 65, yang 153 00:05:59,801 --> 00:06:01,840 akan menjadi seperti di sana tanpa alasan yang baik. 154 00:06:01,840 --> 00:06:04,320 Di mana anda mahu meletakkan A dari segi nilai ASCII? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Di manakah anda mahu lakukan untuk ASCII nilai untuk datang dengan baldi yang lebih pintar 157 00:06:08,920 --> 00:06:09,480 untuk memasukkannya ke dalam? 158 00:06:09,480 --> 00:06:10,206 >> PENONTON: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID MALAN: Ya. 160 00:06:10,956 --> 00:06:13,190 Jadi tolak A atau tolak khususnya 65 jika ia 161 00:06:13,190 --> 00:06:18,240 A. modal Atau 98 jika itu adalah huruf kecil a. 162 00:06:18,240 --> 00:06:21,300 Dan sebagainya yang akan membolehkan kita untuk, sangat sederhana dan sangat deret hitung, 163 00:06:21,300 --> 00:06:23,260 memasukkan sesuatu ke dalam baldi seperti itu. 164 00:06:23,260 --> 00:06:26,010 Jadi ternyata kita sebenarnya ini juga walaupun dengan kuiz. 165 00:06:26,010 --> 00:06:29,051 >> Jadi, anda mungkin ingat anda dilingkari anda Nama mengajar rakan-rakan yang di sampulnya. 166 00:06:29,051 --> 00:06:32,270 Dan nama-nama yang TF telah dianjurkan ke dalam ruangan ini mengikut abjad, 167 00:06:32,270 --> 00:06:34,400 baik, percaya atau tidak, apabila semua 80 ditambah daripada kita 168 00:06:34,400 --> 00:06:37,800 bersama-sama malam yang lain untuk kelas, langkah terakhir dalam proses penilaian kami 169 00:06:37,800 --> 00:06:41,830 adalah untuk hash kuis menjadi besar ruang lantai di [terdengar] 170 00:06:41,830 --> 00:06:45,110 dan untuk meletakkan kuiz semua orang daripada betul-betul perintah TF mereka 171 00:06:45,110 --> 00:06:47,700 nama-nama di kulit, kerana maka ia lebih mudah untuk kita 172 00:06:47,700 --> 00:06:51,290 untuk mencari yang menggunakan linear mencari atau beberapa jenis kepintaran 173 00:06:51,290 --> 00:06:54,050 untuk TF untuk mencari atau kuiz penuntutnya. 174 00:06:54,050 --> 00:06:56,060 >> Jadi idea ini dari hashing yang anda akan lihat adalah 175 00:06:56,060 --> 00:07:00,520 cukup kuat sebenarnya cukup perkara biasa dan sangat intuitif, 176 00:07:00,520 --> 00:07:03,000 seperti mungkin membahagi dan menakluk adalah pada minggu sifar. 177 00:07:03,000 --> 00:07:05,250 Saya cepat ke depan untuk hackathon yang beberapa tahun yang lalu. 178 00:07:05,250 --> 00:07:08,040 Ini adalah Zamyla dan beberapa lain pelajar ucapan kakitangan 179 00:07:08,040 --> 00:07:09,030 kerana mereka masuk. 180 00:07:09,030 --> 00:07:12,680 Dan kami mempunyai sejumlah besar lipat meja ada dengan tag nama. 181 00:07:12,680 --> 00:07:15,380 Dan kami telah tag nama yang dianjurkan dengan seperti Seperti di sana 182 00:07:15,380 --> 00:07:16,690 dan Zs di sana. 183 00:07:16,690 --> 00:07:20,350 Dan jadi salah satu TF sangat cerdik menulis ini sebagai petunjuk 184 00:07:20,350 --> 00:07:21,030 untuk hari itu. 185 00:07:21,030 --> 00:07:24,480 Dan pada minggu ke-12 semester ini semua masuk akal dan semua orang 186 00:07:24,480 --> 00:07:25,310 tahu apa yang perlu dilakukan. 187 00:07:25,310 --> 00:07:27,900 Tapi bila-bila masa anda mempunyai antri dengan cara yang sama, 188 00:07:27,900 --> 00:07:30,272 Anda melaksanakan tanggapan yang sama hash. 189 00:07:30,272 --> 00:07:31,730 Jadi mari kita merumuskan ia sedikit. 190 00:07:31,730 --> 00:07:32,890 Berikut adalah array. 191 00:07:32,890 --> 00:07:36,820 Ia tertarik dengan sedikit lebar hanya untuk menggambarkan, secara visual, 192 00:07:36,820 --> 00:07:38,920 supaya kita meletakkan tali dalam hal seperti ini. 193 00:07:38,920 --> 00:07:41,970 Dan mudah ini jelas dari saiz 26 jumlah. 194 00:07:41,970 --> 00:07:43,935 Dan perkara yang disebut meja sewenang-wenangnya. 195 00:07:43,935 --> 00:07:48,930 Tapi ini hanya rendition artis apa jadual hash mungkin. 196 00:07:48,930 --> 00:07:52,799 >> Jadi jadual hash sekarang akan menjadi struktur data tahap yang lebih tinggi. 197 00:07:52,799 --> 00:07:54,840 Pada akhir hari kita akan melihat bahawa anda 198 00:07:54,840 --> 00:07:58,700 boleh melaksanakan jadual hash, yang jauh seperti talian check-in 199 00:07:58,700 --> 00:08:02,059 pada hackathon seperti ini meja digunakan untuk pengisihan buku peperiksaan. 200 00:08:02,059 --> 00:08:03,850 Tetapi jadual hash semacam tingkat tinggi 201 00:08:03,850 --> 00:08:08,250 konsep yang boleh menggunakan array di bawah tenda untuk melaksanakannya, 202 00:08:08,250 --> 00:08:11,890 atau bisa menggunakan senarai panjang, atau bahkan mungkin beberapa lain-lain struktur data. 203 00:08:11,890 --> 00:08:15,590 Dan sekarang itu pengambilan theme-- beberapa bahan-bahan asas 204 00:08:15,590 --> 00:08:18,310 seperti array dan bangunan ini menghalang sekarang daripada senarai panjang 205 00:08:18,310 --> 00:08:21,740 dan melihat apa lagi yang kita boleh membina di atas mereka, seperti bahan-bahan 206 00:08:21,740 --> 00:08:26,550 ke dalam resipi, membuat lebih banyak hasil akhir yang menarik dan berguna. 207 00:08:26,550 --> 00:08:28,680 >> Jadi dengan jadual hash kita mungkin melaksanakannya 208 00:08:28,680 --> 00:08:32,540 dalam memori bergambar seperti ini, tetapi bagaimana mungkin ia sebenarnya dikodkan sehingga? 209 00:08:32,540 --> 00:08:33,789 Yah, mungkin hanya sebagai adalah ini. 210 00:08:33,789 --> 00:08:38,270 Jika KEUPAYAAN dalam semua topi, hanya beberapa constant-- misalnya 26, 211 00:08:38,270 --> 00:08:42,030 untuk 26 huruf alphabet-- yang Saya sebut meja variabel saya, 212 00:08:42,030 --> 00:08:45,630 dan saya mungkin mendakwa bahawa saya akan meletakkan bintang arang di sana, atau tali. 213 00:08:45,630 --> 00:08:49,880 Jadi ia semudah ini jika anda ingin menerapkan jadual hash. 214 00:08:49,880 --> 00:08:51,490 Namun, ini adalah benar-benar hanya array. 215 00:08:51,490 --> 00:08:53,198 Tetapi sekali lagi, hash meja kini apa yang kita akan 216 00:08:53,198 --> 00:08:57,470 memanggil jenis data abstrak itu hanya semacam lapisan konseptual di atas 217 00:08:57,470 --> 00:09:00,780 sesuatu yang lebih biasa sekarang seperti array. 218 00:09:00,780 --> 00:09:02,960 >> Sekarang, bagaimana kita pergi mengenai menyelesaikan masalah? 219 00:09:02,960 --> 00:09:06,980 Nah, sebelum ini saya mempunyai mewah mempunyai ruang meja yang cukup di sini 220 00:09:06,980 --> 00:09:09,460 supaya saya dapat meletakkan kuiz mana-mana sahaja yang saya mahu. 221 00:09:09,460 --> 00:09:10,620 Jadi Seperti yang pergi di sini. 222 00:09:10,620 --> 00:09:12,100 Zs mungkin pergi di sini. 223 00:09:12,100 --> 00:09:13,230 Cik boleh pergi di sini. 224 00:09:13,230 --> 00:09:14,740 Dan kemudian saya mempunyai beberapa ruang tambahan. 225 00:09:14,740 --> 00:09:18,740 Tetapi ini adalah sedikit hak menipu sekarang kerana jadual ini, jika saya benar-benar 226 00:09:18,740 --> 00:09:22,720 menganggapnya sebagai array, hanya akan menjadi dari beberapa saiz tetap. 227 00:09:22,720 --> 00:09:25,380 >> Jadi secara teknikal, jika saya menarik sehingga kuiz lain pelajar 228 00:09:25,380 --> 00:09:28,490 dan melihat, oh, orang ini nama bermula dengan A juga, 229 00:09:28,490 --> 00:09:30,980 Aku agak mahu meletakkan ia di sana. 230 00:09:30,980 --> 00:09:34,740 Tetapi sebaik sahaja saya meletakkan di sana, jika jadual ini sememangnya merupakan array, 231 00:09:34,740 --> 00:09:37,840 Saya akan dapat mengatasi atau clobbering sesiapa kuiz ini adalah pelajar. 232 00:09:37,840 --> 00:09:38,340 Betul? 233 00:09:38,340 --> 00:09:41,972 Jika ini adalah array, hanya satu hal boleh pergi dalam setiap sel-sel atau elemen. 234 00:09:41,972 --> 00:09:43,680 Oleh itu, saya jenis mempunyai untuk memilih dan memilih. 235 00:09:43,680 --> 00:09:45,735 >> Sekarang sebelum saya jenis menipu dan melakukan ini atau saya 236 00:09:45,735 --> 00:09:47,526 hanya jenis disusun mereka di atas satu sama lain. 237 00:09:47,526 --> 00:09:49,170 Tetapi itu tidak akan terbang dalam kod. 238 00:09:49,170 --> 00:09:52,260 Jadi, di mana saya boleh meletakkan pelajar kedua yang namanya 239 00:09:52,260 --> 00:09:54,964 adalah A jika semua saya harus ialah ruang jadual yang sedia ada? 240 00:09:54,964 --> 00:09:57,880 Dan saya telah menggunakan tiga slot dan ia kelihatan seperti hanya ada beberapa orang lain. 241 00:09:57,880 --> 00:09:58,959 Apa yang anda boleh lakukan? 242 00:09:58,959 --> 00:09:59,834 PENONTON: [didengar] 243 00:09:59,834 --> 00:10:00,565 244 00:10:00,565 --> 00:10:01,315 DAVID MALAN: Ya. 245 00:10:01,315 --> 00:10:02,370 Mungkin mari kita tetap sederhana. 246 00:10:02,370 --> 00:10:02,660 Betul? 247 00:10:02,660 --> 00:10:04,243 Ia tidak sesuai di mana saya mahu meletakkannya. 248 00:10:04,243 --> 00:10:07,450 Jadi, saya akan meletakkan ia dari segi teknikal di mana B akan pergi. 249 00:10:07,450 --> 00:10:09,932 Sekarang, tentu saja, saya mula melukis diri saya ke sudut. 250 00:10:09,932 --> 00:10:11,890 Jika saya mendapat kepada pelajar yang mana nama sebenarnya B, 251 00:10:11,890 --> 00:10:14,840 sekarang B akan dipindahkan sedikit ke hadapan, sebagai mungkin berlaku, ya, 252 00:10:14,840 --> 00:10:17,530 jika ini adalah a, kini ia mempunyai pergi di sini. 253 00:10:17,530 --> 00:10:20,180 >> Dan jadi ini dengan cepat boleh menjadi bermasalah, 254 00:10:20,180 --> 00:10:23,850 tapi teknik yang benar-benar disebut sebagai linear menyelidik, 255 00:10:23,850 --> 00:10:26,650 di mana anda hanya menganggap anda array untuk menjadi sepanjang garis. 256 00:10:26,650 --> 00:10:29,680 Dan anda hanya jenis menyiasat atau memeriksa setiap elemen yang ada 257 00:10:29,680 --> 00:10:31,360 mencari tempat yang tersedia. 258 00:10:31,360 --> 00:10:34,010 Dan sebaik sahaja anda mencari satu, anda menjatuhkannya di sana. 259 00:10:34,010 --> 00:10:38,390 >> Sekarang, harga yang dibayar sekarang untuk penyelesaian ini adalah apa? 260 00:10:38,390 --> 00:10:41,300 Kami mempunyai pelbagai saiz tetap, dan apabila saya memasukkan nama 261 00:10:41,300 --> 00:10:44,059 ke dalamnya, sekurang-kurangnya pada peringkat awal, apa yang waktu berjalan penyisipan 262 00:10:44,059 --> 00:10:46,350 untuk menempatkan pelajar kuiz dalam baldi yang betul? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O dari apa? 265 00:10:50,002 --> 00:10:51,147 >> PENONTON: n. 266 00:10:51,147 --> 00:10:52,480 DAVID MALAN: Aku mendengar O besar n. 267 00:10:52,480 --> 00:10:53,530 268 00:10:53,530 --> 00:10:54,300 Tidak benar. 269 00:10:54,300 --> 00:10:56,490 Tapi kita akan mengusik selain mengapa hanya dalam beberapa saat. 270 00:10:56,490 --> 00:10:57,702 Apa lagi yang mungkin? 271 00:10:57,702 --> 00:10:58,755 >> PENONTON: [didengar] 272 00:10:58,755 --> 00:11:00,380 DAVID MALAN: Dan biarkan aku melakukannya secara visual. 273 00:11:00,380 --> 00:11:04,720 Jadi kira ini adalah surat yang S. 274 00:11:04,720 --> 00:11:05,604 >> PENONTON: Ia adalah salah. 275 00:11:05,604 --> 00:11:06,520 DAVID MALAN: Ini salah satu. 276 00:11:06,520 --> 00:11:06,710 Betul? 277 00:11:06,710 --> 00:11:08,950 Ini adalah sebuah array, yang bermakna kita mempunyai akses rawak. 278 00:11:08,950 --> 00:11:11,790 Dan jika kita berfikir tentang ini sebagai sifar dan kerana ini 25, 279 00:11:11,790 --> 00:11:13,800 dan kita sedar bahawa, oh, inilah input S saya, 280 00:11:13,800 --> 00:11:16,350 Saya pasti boleh menukar S, karakter ASCII, 281 00:11:16,350 --> 00:11:18,540 ke nombor yang sama antara sifar dan 25 282 00:11:18,540 --> 00:11:20,910 dan kemudian dengan serta-merta meletakkannya di tempatnya. 283 00:11:20,910 --> 00:11:26,120 >> Tapi tentu saja, sebaik sahaja saya sampai ke orang kedua yang memiliki nama adalah A atau B atau C 284 00:11:26,120 --> 00:11:29,300 akhirnya, jika saya telah menggunakan linear menyelesaikan sesuatu sebagai penyelesaian saya, 285 00:11:29,300 --> 00:11:31,360 masa yang berjalan dari sisipan dalam kes yang paling teruk 286 00:11:31,360 --> 00:11:33,120 sebenarnya akan berpindah ke apa? 287 00:11:33,120 --> 00:11:34,270 288 00:11:34,270 --> 00:11:36,045 Dan aku mendengarnya di sini betul awal. 289 00:11:36,045 --> 00:11:36,920 PENONTON: [didengar] 290 00:11:36,920 --> 00:11:41,620 DAVID MALAN: Jadi adalah n memang sekali anda mempunyai satu set data yang cukup besar. 291 00:11:41,620 --> 00:11:44,410 Jadi, dalam satu tangan, jika array cukup besar 292 00:11:44,410 --> 00:11:48,287 dan data anda jarang cukup, Anda mendapatkan waktu ini tetap indah. 293 00:11:48,287 --> 00:11:50,620 Tetapi sebaik sahaja anda mula mendapatkan lebih banyak dan lebih banyak elemen, 294 00:11:50,620 --> 00:11:53,200 dan hanya statistik anda mendapat lebih ramai orang dengan huruf 295 00:11:53,200 --> 00:11:56,030 A sebagai nama atau huruf B, ia boleh berpotensi 296 00:11:56,030 --> 00:11:57,900 berpindah ke sesuatu yang lebih linear. 297 00:11:57,900 --> 00:11:59,640 Jadi tidak cukup sempurna. 298 00:11:59,640 --> 00:12:00,690 Oleh itu, kita boleh melakukan yang lebih baik? 299 00:12:00,690 --> 00:12:03,210 >> Nah, apa yang kami penyelesaian sebelum apabila kita 300 00:12:03,210 --> 00:12:06,820 ingin mempunyai dinamisme lebih daripada sesuatu seperti array dibenarkan? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 PENONTON: [didengar] 303 00:12:08,960 --> 00:12:10,030 DAVID MALAN: Apa yang kami memperkenalkan? 304 00:12:10,030 --> 00:12:10,530 Yeah. 305 00:12:10,530 --> 00:12:11,430 Jadi senarai berpaut. 306 00:12:11,430 --> 00:12:14,430 Nah, mari kita lihat apa yang terkait senarai mungkin lakukan untuk kita sebagai gantinya. 307 00:12:14,430 --> 00:12:17,630 Baiklah, biar saya mencadangkan kita bahawa menarik gambar seperti berikut. 308 00:12:17,630 --> 00:12:19,620 Sekarang ini adalah berbeza gambar dari contoh 309 00:12:19,620 --> 00:12:24,750 daripada teks yang berbeza, sebenarnya, yang adalah benar-benar menggunakan pelbagai saiz 31. 310 00:12:24,750 --> 00:12:28,220 Dan penulis ini hanya memutuskan untuk hash tali 311 00:12:28,220 --> 00:12:32,430 tidak berdasarkan nama orang itu, tetapi berdasarkan tarikh lahir mereka. 312 00:12:32,430 --> 00:12:35,680 Tanpa mengira bulan, mereka membuat kesimpulan jika anda dilahirkan pada tanggal satu bulan yang 313 00:12:35,680 --> 00:12:39,580 atau 31 bulan, penulis akan hash berdasarkan nilai itu, 314 00:12:39,580 --> 00:12:44,154 untuk menyebarkan nama keluar sedikit lebih daripada 26 tempat-tempat mungkin mengizinkan. 315 00:12:44,154 --> 00:12:47,320 Dan mungkin itu seragam yang lebih sedikit daripada pergi dengan huruf abjad, 316 00:12:47,320 --> 00:12:50,236 kerana sudah tentu ada mungkin lebih ramai orang di dunia dengan nama-nama 317 00:12:50,236 --> 00:12:54,020 yang awal dengan A daripada pasti beberapa huruf lain abjad. 318 00:12:54,020 --> 00:12:56,380 Jadi mungkin ini adalah sedikit seragam lebih, dengan asumsi 319 00:12:56,380 --> 00:12:58,640 taburan seragam bayi di dalam sebulan. 320 00:12:58,640 --> 00:12:59,990 >> Tetapi, sudah tentu, ini masih tidak sempurna. 321 00:12:59,990 --> 00:13:00,370 Betul? 322 00:13:00,370 --> 00:13:01,370 Kami mengalami perlanggaran. 323 00:13:01,370 --> 00:13:04,680 Beberapa orang dalam struktur data masih 324 00:13:04,680 --> 00:13:08,432 mempunyai tarikh lahir yang sama sekurang-kurangnya anda tidak kira bulan. 325 00:13:08,432 --> 00:13:09,640 Tetapi apa yang telah penulis lakukan? 326 00:13:09,640 --> 00:13:13,427 Nah, ia kelihatan seperti kita mempunyai array di sebelah kiri ditarik menegak, 327 00:13:13,427 --> 00:13:15,010 tapi itu hanya persembahan artis. 328 00:13:15,010 --> 00:13:18,009 Tidak peduli ke arah mana anda menarik array, ia masih array. 329 00:13:18,009 --> 00:13:20,225 Apa ini pelbagai rupanya? 330 00:13:20,225 --> 00:13:21,500 >> PENONTON: Senarai Berkaitan. 331 00:13:21,500 --> 00:13:21,650 >> DAVID MALAN: Ya. 332 00:13:21,650 --> 00:13:23,490 Ia kelihatan seperti ini merupakan array linked list. 333 00:13:23,490 --> 00:13:26,490 Jadi sekali lagi, hingga saat ini semacam menggunakan struktur data sekarang 334 00:13:26,490 --> 00:13:28,550 sebagai bahan untuk lebih penyelesaian yang menarik, 335 00:13:28,550 --> 00:13:30,862 Anda benar-benar boleh mengambil asas, seperti array, 336 00:13:30,862 --> 00:13:33,320 dan kemudian mengambil sesuatu yang lebih menarik seperti senarai berpaut 337 00:13:33,320 --> 00:13:36,660 dan bahkan menggabungkan mereka ke dalam yang lebih struktur data yang lebih menarik. 338 00:13:36,660 --> 00:13:39,630 Dan sesungguhnya, ini juga akan dipanggil jadual hash, 339 00:13:39,630 --> 00:13:42,610 mana array adalah benar-benar jadual hash, 340 00:13:42,610 --> 00:13:45,600 tetapi jadual hash ini rantai, boleh dikatakan, 341 00:13:45,600 --> 00:13:50,220 yang boleh membesar atau mengecilkan berdasarkan beberapa elemen yang anda mahu masukkan. 342 00:13:50,220 --> 00:13:52,990 >> Sekarang, dengan itu, apa yang masa yang berjalan sekarang? 343 00:13:52,990 --> 00:13:58,030 Jika saya ingin memasukkan seseorang yang ulang tahun adalah 31 Oktober, 344 00:13:58,030 --> 00:13:59,040 di mana ia tidak pergi? 345 00:13:59,040 --> 00:14:00,530 346 00:14:00,530 --> 00:14:01,030 Baik. 347 00:14:01,030 --> 00:14:02,819 Di bahagian paling bawah di mana dikatakan 31. 348 00:14:02,819 --> 00:14:03,610 Dan itu sempurna. 349 00:14:03,610 --> 00:14:05,060 Itu adalah masa yang berterusan. 350 00:14:05,060 --> 00:14:08,760 Tapi bagaimana kalau kita mencari orang lain yang ulang tahun ini, mari kita lihat, 351 00:14:08,760 --> 00:14:10,950 Oktober, November, 31 Disember? 352 00:14:10,950 --> 00:14:12,790 Di mana yang dia akan pergi? 353 00:14:12,790 --> 00:14:13,290 Hal yang sama. 354 00:14:13,290 --> 00:14:13,970 Dua langkah walaupun. 355 00:14:13,970 --> 00:14:15,303 Itu yang berterusan walaupun bukan? 356 00:14:15,303 --> 00:14:16,360 357 00:14:16,360 --> 00:14:16,860 Baik. 358 00:14:16,860 --> 00:14:17,840 Pada masa ini ia adalah. 359 00:14:17,840 --> 00:14:20,570 Tetapi dalam kes umum, semakin banyak orang yang kita menambah, 360 00:14:20,570 --> 00:14:23,790 probabilistically, kita akan untuk mendapatkan lebih banyak dan lebih perlanggaran. 361 00:14:23,790 --> 00:14:26,820 >> Ini adalah sedikit lebih baik kerana dari segi teknikal 362 00:14:26,820 --> 00:14:34,580 sekarang rantai saya boleh berada di dalam kes terburuk berapa lama? 363 00:14:34,580 --> 00:14:38,890 Jika saya memasukkan n orang ke dalam ini lebih struktur data yang canggih, n orang, 364 00:14:38,890 --> 00:14:41,080 dalam kes yang paling teruk ia akan menjadi n. 365 00:14:41,080 --> 00:14:41,815 Mengapa? 366 00:14:41,815 --> 00:14:43,332 >> PENONTON: Kerana jika semua orang mempunyai hari jadi yang sama, 367 00:14:43,332 --> 00:14:44,545 mereka akan menjadi satu baris. 368 00:14:44,545 --> 00:14:45,420 DAVID MALAN: Perfect. 369 00:14:45,420 --> 00:14:47,480 Mungkin sedikit dibuat-buat, tetapi benar-benar dalam kes paling teruk, 370 00:14:47,480 --> 00:14:50,117 jika semua orang mempunyai hari jadi yang sama, diberi input yang anda miliki, 371 00:14:50,117 --> 00:14:51,950 Anda akan mempunyai rangkaian secara besar-besaran yang lama. 372 00:14:51,950 --> 00:14:54,241 Dan sebagainya, anda boleh menyebutnya hash table, tapi sebenarnya itu 373 00:14:54,241 --> 00:14:56,810 hanya daftar besar dikaitkan dengan banyak keseluruhan ruang kosong. 374 00:14:56,810 --> 00:15:00,460 Tetapi secara umum, jika kita menganggap bahawa sekurang-kurangnya hari lahir adalah uniform-- 375 00:15:00,460 --> 00:15:01,750 dan mungkin tidak. 376 00:15:01,750 --> 00:15:02,587 Saya sedang membuat hal itu. 377 00:15:02,587 --> 00:15:04,420 Tetapi jika kita mengambil alih, untuk kepentingan diskusi 378 00:15:04,420 --> 00:15:07,717 bahwa mereka, maka secara teori, jika ini adalah perwakilan menegak 379 00:15:07,717 --> 00:15:11,050 array, baik maka mudah-mudahan anda akan mendapatkan rantaian yang, anda tahu, 380 00:15:11,050 --> 00:15:15,880 kira-kira sama panjang di mana masing-masing ini merupakan hari bulan. 381 00:15:15,880 --> 00:15:19,930 >> Sekarang jika terdapat 31 hari dalam bulan ini, itu berarti masa saya berjalan benar-benar 382 00:15:19,930 --> 00:15:25,230 adalah O besar n lebih dari 31, yang merasa lebih baik daripada linear. 383 00:15:25,230 --> 00:15:27,950 Tetapi apa yang adalah salah satu daripada kami komitmen beberapa minggu 384 00:15:27,950 --> 00:15:31,145 yang lalu apabila ia datang untuk menyatakan masa yang berjalan dari algoritma? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Hanya hanya melihat perkataan perintah yang tinggi. 387 00:15:35,190 --> 00:15:35,690 Betul? 388 00:15:35,690 --> 00:15:37,400 31 adalah pasti membantu. 389 00:15:37,400 --> 00:15:39,610 Tapi ini masih O besar n. 390 00:15:39,610 --> 00:15:41,730 Tetapi salah satu tema dari permasalahan yang lima 391 00:15:41,730 --> 00:15:43,950 akan menjadi untuk mengakui bahawa benar-benar, 392 00:15:43,950 --> 00:15:47,320 asimtotik, secara teori struktur data ini 393 00:15:47,320 --> 00:15:50,470 tidak lebih baik daripada hanya satu senarai yang besar yang berkaitan. 394 00:15:50,470 --> 00:15:53,550 Dan memang, dalam kes paling teruk, ini jadual hash mungkin turun ke dalam. 395 00:15:53,550 --> 00:15:57,620 >> Tetapi dalam dunia nyata, dengan kita manusia bahwa Mac sendiri atau komputer peribadi atau apa sahaja 396 00:15:57,620 --> 00:16:01,240 dan menjalankan dunia nyata perisian data dari dunia nyata, 397 00:16:01,240 --> 00:16:03,260 yang algoritma yang anda akan lebih suka? 398 00:16:03,260 --> 00:16:09,180 Salah satu yang mengambil langkah-langkah akhir atau salah satu yang mengambil n dibahagikan dengan 31 langkah 399 00:16:09,180 --> 00:16:12,900 untuk mencari sedikit data atau untuk mencari beberapa maklumat? 400 00:16:12,900 --> 00:16:16,580 Maksud saya, benar-benar 31 jenama perbezaan dalam dunia sebenar. 401 00:16:16,580 --> 00:16:18,540 Ia adalah 31 kali lebih cepat. 402 00:16:18,540 --> 00:16:20,880 Dan kita manusia pasti akan menghargai itu. 403 00:16:20,880 --> 00:16:23,004 >> Jadi mewujudkan dikotomi ada antara benar-benar 404 00:16:23,004 --> 00:16:25,920 bercakap tentang hal-hal secara teori dan asimptot yang pasti 405 00:16:25,920 --> 00:16:28,760 mempunyai nilai seperti yang kita lihat, tapi dalam dunia sebenar, 406 00:16:28,760 --> 00:16:32,930 jika anda mengambil berat tentang hanya membuat bahagia manusia untuk input umum, 407 00:16:32,930 --> 00:16:36,010 Anda sangat baik mungkin mahu menerima hakikat bahawa, ya, ini adalah linear, 408 00:16:36,010 --> 00:16:38,360 tetapi ia 31 kali lebih cepat linear mungkin. 409 00:16:38,360 --> 00:16:41,610 Dan lebih baik lagi, kita tidak hanya perlu melakukan sesuatu sewenang-wenang seperti tarikh lahir yang, 410 00:16:41,610 --> 00:16:44,030 kita boleh menghabiskan sedikit lebih banyak masa dan kepandaian 411 00:16:44,030 --> 00:16:47,140 dan berfikir tentang apa yang kita boleh lakukan, diberi nama seseorang dan mungkin 412 00:16:47,140 --> 00:16:50,130 tarikh lahir mereka untuk menggabungkan bahan-bahan untuk mencari tahu sesuatu 413 00:16:50,130 --> 00:16:52,720 yang benar-benar lebih seragam dan kurang bergerigi, 414 00:16:52,720 --> 00:16:56,250 boleh dikatakan dari gambar ini kini menunjukkan ia mungkin. 415 00:16:56,250 --> 00:16:57,750 Bagaimana kita boleh melaksanakan ini dalam kod? 416 00:16:57,750 --> 00:17:00,280 Baiklah, biar saya mencadangkan kita bahawa hanya meminjam sintaks kami telah 417 00:17:00,280 --> 00:17:01,799 digunakan beberapa kali setakat ini. 418 00:17:01,799 --> 00:17:03,590 Dan saya akan mendefinisikan nod, yang sekali lagi 419 00:17:03,590 --> 00:17:06,812 adalah istilah generik untuk hanya beberapa bekas untuk beberapa struktur data. 420 00:17:06,812 --> 00:17:09,020 Saya akan mencadangkan supaya string akan di sana. 421 00:17:09,020 --> 00:17:11,369 Tetapi kita akan mula mengambil mereka latihan roda off sekarang. 422 00:17:11,369 --> 00:17:13,230 >> Tidak ada perpustakaan CS50 lebih benar-benar, melainkan jika anda mahu 423 00:17:13,230 --> 00:17:15,230 menggunakannya untuk akhir anda Projek ini, yang baik-baik saja, 424 00:17:15,230 --> 00:17:18,569 tetapi sekarang kita akan menarik kembali tirai dan berkata ia hanya satu bintang arang. 425 00:17:18,569 --> 00:17:22,069 Jadi perkataan ada akan menjadi nama orang yang bersangkutan. 426 00:17:22,069 --> 00:17:25,079 Dan sekarang saya mempunyai link di sini untuk nod seterusnya 427 00:17:25,079 --> 00:17:28,170 sehingga ini mewakili setiap satu daripada nod 428 00:17:28,170 --> 00:17:30,950 dalam rantai, berpotensi, senarai berpaut. 429 00:17:30,950 --> 00:17:34,090 >> Dan sekarang bagaimana saya menyatakan jadual hash itu sendiri? 430 00:17:34,090 --> 00:17:36,660 Bagaimana saya mengisytiharkan seluruh struktur ini? 431 00:17:36,660 --> 00:17:40,960 Nah, benar-benar, sama seperti saya menggunakan pointer hanya elemen pertama dari senarai 432 00:17:40,960 --> 00:17:44,510 sebelum ini, juga boleh saya katakan Aku hanya perlu sekelompok pointer 433 00:17:44,510 --> 00:17:46,270 untuk melaksanakan jadual ini hash keseluruhan. 434 00:17:46,270 --> 00:17:49,484 Saya akan mempunyai array dipanggil jadual untuk jadual hash. 435 00:17:49,484 --> 00:17:50,900 Ia akan menjadi kapasiti saiz. 436 00:17:50,900 --> 00:17:52,525 Itu berapa banyak elemen boleh muat di dalamnya. 437 00:17:52,525 --> 00:17:56,180 Dan masing-masing dari elemen-elemen dalam array akan menjadi bintang nod. 438 00:17:56,180 --> 00:17:56,810 Mengapa? 439 00:17:56,810 --> 00:18:00,160 Well, setiap gambar ini, apa yang saya melaksanakan jadual hash sebagai 440 00:18:00,160 --> 00:18:04,330 berkesan pada awalnya adalah hanya array ini yang kita gambarkan secara menegak, 441 00:18:04,330 --> 00:18:06,820 setiap kotak yang mewakili pointer. 442 00:18:06,820 --> 00:18:09,170 Itulah orang-orang yang mempunyai garis condong melalui mereka hanya null. 443 00:18:09,170 --> 00:18:11,410 Dan orang-orang yang mempunyai anak panah akan ke kanan 444 00:18:11,410 --> 00:18:16,140 adalah petunjuk yang sebenarnya untuk nod yang sebenarnya, ergo permulaan senarai berpaut. 445 00:18:16,140 --> 00:18:19,050 >> Jadi di sini, kemudian, adalah bagaimana kita mungkin melaksanakan jadual hash yang 446 00:18:19,050 --> 00:18:21,580 melaksanakan chaining berasingan. 447 00:18:21,580 --> 00:18:22,840 Sekarang kita boleh melakukan yang lebih baik? 448 00:18:22,840 --> 00:18:25,632 Baiklah saya berjanji Kali terakhir kita boleh mencapai masa yang sama. 449 00:18:25,632 --> 00:18:27,381 Dan aku agak memberikan anda masa tetap di sini, 450 00:18:27,381 --> 00:18:29,850 tetapi kemudian tidak berkata benar-benar masa tetap kerana ia masih 451 00:18:29,850 --> 00:18:31,890 bergantung kepada jumlah beberapa elemen 452 00:18:31,890 --> 00:18:34,500 anda memasukkan ke dalam struktur data. 453 00:18:34,500 --> 00:18:35,980 Tetapi sekiranya kita melakukan ini. 454 00:18:35,980 --> 00:18:39,550 Mari kita kembali ke layar di sini. 455 00:18:39,550 --> 00:18:44,520 Kini saya akan projek ini di sini, jelas skrin, dan kira saya melakukan ini. 456 00:18:44,520 --> 00:18:49,300 Penulis ingin memasukkan nama Daven di dalam struktur data saya. 457 00:18:49,300 --> 00:18:52,100 >> Jadi saya ingin memasukkan string Daven ke dalam struktur data. 458 00:18:52,100 --> 00:18:54,370 Bagaimana jika saya tidak menggunakan hash meja, tetapi saya menggunakan 459 00:18:54,370 --> 00:18:56,980 sesuatu yang lebih seperti pohon seperti pohon keluarga, di mana 460 00:18:56,980 --> 00:18:59,670 anda mempunyai beberapa akar di node atas dan kemudian dan daun 461 00:18:59,670 --> 00:19:01,440 yang pergi ke bawah dan ke luar. 462 00:19:01,440 --> 00:19:04,450 Katakan itu, saya yang ingin memasukkan ini Daven 463 00:19:04,450 --> 00:19:06,430 ke dalam apa yang saat ini senarai main kosong. 464 00:19:06,430 --> 00:19:09,780 Saya akan melakukan perkara-perkara berikut: Saya akan mewujudkan nod dalam keluarga ini 465 00:19:09,780 --> 00:19:15,170 seperti pohon struktur data yang kelihatan sedikit seperti ini, yang masing-masing 466 00:19:15,170 --> 00:19:19,640 persegi panjang telah, katakan, untuk saat 26 unsur-unsur di dalamnya. 467 00:19:19,640 --> 00:19:21,650 Dan setiap sel-sel dalam array ini akan 468 00:19:21,650 --> 00:19:23,470 untuk mewakili huruf abjad itu. 469 00:19:23,470 --> 00:19:28,190 >> Secara khusus, saya akan merawat ini adalah A, maka B, maka C, maka D, 470 00:19:28,190 --> 00:19:29,310 satu ini di sini. 471 00:19:29,310 --> 00:19:32,940 Jadi ini akan berkesan mewakili huruf D. 472 00:19:32,940 --> 00:19:36,040 Tetapi untuk memasukkan semua ini Daven nama saya lakukan sedikit lebih. 473 00:19:36,040 --> 00:19:37,840 Jadi, saya terlebih dahulu ke hash, jadi untuk bercakap. 474 00:19:37,840 --> 00:19:41,049 Saya akan melihat huruf pertama di Daven yang jelas D, 475 00:19:41,049 --> 00:19:42,840 dan saya akan memperuntukkan nod yang kelihatan 476 00:19:42,840 --> 00:19:45,570 seperti this-- sebuah segiempat tepat yang besar besar cukup agar sesuai dengan seluruh abjad. 477 00:19:45,570 --> 00:19:47,140 >> Sekarang D dilakukan. 478 00:19:47,140 --> 00:19:49,720 Kini A. D-A-V-E-N adalah tujuan. 479 00:19:49,720 --> 00:19:51,220 Jadi sekarang apa yang akan saya lakukan adalah ini. 480 00:19:51,220 --> 00:19:54,027 Sebaik sahaja saya mula notis D tidak ada penunjuk sana. 481 00:19:54,027 --> 00:19:56,860 Ia adalah nilai-nilai sampah pada masa ini, atau saya mungkin memulakan ke null. 482 00:19:56,860 --> 00:19:59,630 Tetapi saya terus berjalan dengan idea ini membina pokok. 483 00:19:59,630 --> 00:20:04,260 Biar saya mengalokasikan lagi salah satu daripada nod yang mempunyai 26 unsur-unsur di dalamnya. 484 00:20:04,260 --> 00:20:05,150 >> Dan anda tahu apa? 485 00:20:05,150 --> 00:20:09,130 Jika ini hanya nod dalam memori yang Saya buat dengan malloc, menggunakan struct 486 00:20:09,130 --> 00:20:11,240 seperti yang kita akan melihat, Saya akan melakukan this-- 487 00:20:11,240 --> 00:20:14,450 Aku akan menarik anak panah dari perkara yang diwakili D ke bawah 488 00:20:14,450 --> 00:20:15,860 untuk nod baru ini. 489 00:20:15,860 --> 00:20:19,240 Dan sekarang, pertama yang akan datang surat atas nama Daven ini, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- saya akan pergi ke depan dan menarik nod lain seperti ini, 491 00:20:24,150 --> 00:20:30,150 di mana, unsur-unsur V di sini, yang kami akan menarik untuk ups instance--. 492 00:20:30,150 --> 00:20:31,020 Kami tidak akan menarik di sana. 493 00:20:31,020 --> 00:20:31,936 Ia akan pergi di sini. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Kemudian kita akan menganggap hal ini menjadi V. 496 00:20:35,712 --> 00:20:44,920 Dan kemudian di sini kita akan indeks turun dari V menjadi apa yang kita akan mempertimbangkan E. 497 00:20:44,920 --> 00:20:50,100 Dan kemudian dari sini kita akan pergi mempunyai salah satu daripada nod ini di sini. 498 00:20:50,100 --> 00:20:52,930 Dan sekarang kita mempunyai soalan untuk menjawab. 499 00:20:52,930 --> 00:20:57,840 Saya perlu entah bagaimana menunjukkan bahawa kita berada di akhir string Daven itu. 500 00:20:57,840 --> 00:20:59,490 Jadi saya hanya boleh meninggalkan ia null. 501 00:20:59,490 --> 00:21:02,670 >> Tapi bagaimana kalau kita mempunyai ini Daven nama penuh juga, yang 502 00:21:02,670 --> 00:21:04,280 adalah, seperti yang kita katakan, Davenport? 503 00:21:04,280 --> 00:21:06,970 Jadi apa jika Daven adalah sebenarnya substring, 504 00:21:06,970 --> 00:21:08,960 awalan tali yang lebih lama? 505 00:21:08,960 --> 00:21:11,450 Kita tidak boleh hanya secara kekal mengatakan apa-apa yang sedang berlaku 506 00:21:11,450 --> 00:21:14,410 untuk pergi ke sana, kerana kita boleh pernah memasukkan kata seperti Davenport 507 00:21:14,410 --> 00:21:15,840 ke dalam Struktur data ini 508 00:21:15,840 --> 00:21:19,560 >> Jadi apa yang kita boleh lakukan sebagai gantinya adalah merawat setiap elemen-elemen ini 509 00:21:19,560 --> 00:21:22,170 sebagai mungkin mempunyai dua unsur-unsur dalam diri mereka. 510 00:21:22,170 --> 00:21:24,810 Salah satunya adalah pointer, memang, seperti yang saya telah lakukan. 511 00:21:24,810 --> 00:21:27,100 Jadi setiap kotak-kotak bukan hanya satu sel. 512 00:21:27,100 --> 00:21:29,855 Tetapi bagaimana jika atas satu-- satu bahagian bawah ini 513 00:21:29,855 --> 00:21:32,230 akan menjadi batal, karena tidak ada Davenport dulu. 514 00:21:32,230 --> 00:21:34,197 Bagaimana jika orang yang atas beberapa nilai khas? 515 00:21:34,197 --> 00:21:36,530 Dan ia akan menjadi sedikit keras untuk menarik itu ukuran ini. 516 00:21:36,530 --> 00:21:38,130 Tapi rasa itu hanya tanda semak. 517 00:21:38,130 --> 00:21:38,920 Semak. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N adalah rentetan dalam struktur data ini. 519 00:21:44,230 --> 00:21:48,350 >> Sementara itu, jika saya mempunyai lebih banyak ruang di sini, saya boleh melakukan P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 dan saya boleh meletakkan cek di nod yang mempunyai huruf T pada akhir sangat. 521 00:21:52,650 --> 00:21:55,460 Jadi ini adalah secara besar-besaran kompleks yang berpandangan struktur data. 522 00:21:55,460 --> 00:21:57,210 Dan tulisan tangan saya tentu tidak membantu. 523 00:21:57,210 --> 00:22:00,043 Tetapi jika saya ingin memasukkan sesuatu lain, pertimbangkan apa yang kita akan lakukan. 524 00:22:00,043 --> 00:22:03,370 Jika kita mahu meletakkan Daud dalam, kita suka mengikut logik yang sama, D-A-V, 525 00:22:03,370 --> 00:22:08,802 tapi sekarang saya akan menunjukkan di akhirat unsur bukan dari E, tetapi dari I hingga D. 526 00:22:08,802 --> 00:22:10,760 Jadi tidak akan menjadi lebih nod dalam pokok ini. 527 00:22:10,760 --> 00:22:12,325 Kita akan mempunyai panggilan malloc lanjut. 528 00:22:12,325 --> 00:22:14,700 Tetapi saya tidak mahu membuat keadaan huru-hara lengkap gambar ini. 529 00:22:14,700 --> 00:22:17,710 Jadi mari kita bukan melihat satu yang telah pra-dirumuskan 530 00:22:17,710 --> 00:22:21,810 seperti ini dengan tidak dot, dot, titik, tetapi array hanya singkatan. 531 00:22:21,810 --> 00:22:23,950 Tetapi setiap satu daripada nod dalam pokok ini di sini 532 00:22:23,950 --> 00:22:26,700 mewakili thing-- yang sama array Ray dari saiz 26. 533 00:22:26,700 --> 00:22:28,860 >> Atau jika kita mahu menjadi sekarang benar-benar betul, apa yang 534 00:22:28,860 --> 00:22:30,790 jika nama seseorang sebagai apostrofe, mari kita 535 00:22:30,790 --> 00:22:35,560 menganggap bahawa setiap nod sebenarnya mempunyai seperti 27 indeks di dalamnya, bukan sahaja 26. 536 00:22:35,560 --> 00:22:42,020 Jadi ini sekarang akan menjadi data yang struktur dipanggil trie-- T-R-saya-E. 537 00:22:42,020 --> 00:22:46,120 A indone, yang diduga sejarah nama pintar untuk pokok 538 00:22:46,120 --> 00:22:49,040 yang mengoptimumkan pengambilan, yang sudah tentu, 539 00:22:49,040 --> 00:22:50,870 dieja dengan I-E supaya ia indone. 540 00:22:50,870 --> 00:22:52,710 Tetapi itu adalah sejarah trie. 541 00:22:52,710 --> 00:22:55,860 >> Jadi indone adalah data seperti pohon ini struktur seperti pohon keluarga 542 00:22:55,860 --> 00:22:57,510 yang pada akhirnya berkelakuan seperti itu. 543 00:22:57,510 --> 00:23:00,890 Dan di sini adalah hanya satu lagi contoh sejumlah besar nama-nama orang lain. 544 00:23:00,890 --> 00:23:03,540 Tapi pertanyaannya sekarang di tangan adalah apa yang 545 00:23:03,540 --> 00:23:08,070 kami memperoleh dengan memperkenalkan dikatakan lebih struktur data yang rumit, dan satu, 546 00:23:08,070 --> 00:23:09,870 terus terang, yang menggunakan banyak memori. 547 00:23:09,870 --> 00:23:11,703 >> Kerana walaupun, pada masa ini, saya hanya 548 00:23:11,703 --> 00:23:15,050 menggunakan penunjuk D dan A dan V dan Es dan Ns, 549 00:23:15,050 --> 00:23:16,700 Saya membuang palang pintu dari banyak memori. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Tetapi di mana saya menghabiskan satu sumber, Saya cenderung untuk mendapatkan kembali yang lain. 552 00:23:22,660 --> 00:23:26,020 Jadi jika saya menghabiskan lebih banyak ruang, apa yang mungkin harapan? 553 00:23:26,020 --> 00:23:27,407 Bahawa saya menghabiskan kurang apa? 554 00:23:27,407 --> 00:23:28,240 PENONTON: Kurang masa. 555 00:23:28,240 --> 00:23:28,990 DAVID MALAN: Masa. 556 00:23:28,990 --> 00:23:30,320 Sekarang mengapa yang mungkin? 557 00:23:30,320 --> 00:23:33,880 Nah, apa yang pemasukan masa, dari segi O besar sekarang, 558 00:23:33,880 --> 00:23:37,660 dari nama seperti Daven atau Davenport atau Daud? 559 00:23:37,660 --> 00:23:39,340 Nah, Daven adalah lima langkah. 560 00:23:39,340 --> 00:23:42,350 Davenport akan sembilan langkah, jadi ia akan menjadi beberapa langkah. 561 00:23:42,350 --> 00:23:44,250 Daud akan menjadi lima langkah juga. 562 00:23:44,250 --> 00:23:47,230 Jadi mereka adalah konkrit nombor, tapi pasti ada 563 00:23:47,230 --> 00:23:49,550 had atas pada panjang nama seseorang. 564 00:23:49,550 --> 00:23:52,240 Dan memang, dalam masalah set lima spesifikasi, 565 00:23:52,240 --> 00:23:54,050 kita akan mencadangkan bahawa itu sesuatu 566 00:23:54,050 --> 00:23:55,470 itulah aksara 40-beberapa-aneh. 567 00:23:55,470 --> 00:23:58,180 >> Realistik, tidak ada seorang pun nama panjang tak terhingga, 568 00:23:58,180 --> 00:24:01,542 yang mengatakan bahawa panjang yang nama atau panjang tali yang kita mungkin 569 00:24:01,542 --> 00:24:03,750 mempunyai tertentu keadaan struktur ini boleh dibilang apa? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Ia adalah malar. 572 00:24:06,250 --> 00:24:06,430 Betul? 573 00:24:06,430 --> 00:24:09,310 Mungkin yang tetap besar seperti 40-an, tetapi ia adalah tetap. 574 00:24:09,310 --> 00:24:13,752 Dan ia tidak mempunyai pergantungan kepada berapa banyak nama-nama lain adalah di dalam struktur data ini. 575 00:24:13,752 --> 00:24:15,460 Dalam erti kata lain, jika saya ingin memasukkan sekarang 576 00:24:15,460 --> 00:24:20,540 Colton atau Jibril atau Rob atau Zamyla atau Alison atau Belinda atau mana-mana nama-nama lain 577 00:24:20,540 --> 00:24:23,940 daripada kakitangan ke dalam data ini struktur, adalah masa yang berjalan 578 00:24:23,940 --> 00:24:26,750 memasukkan nama-nama lain akan berada di semua kesan 579 00:24:26,750 --> 00:24:30,220 oleh berapa banyak elemen lain dalam struktur data yang sudah? 580 00:24:30,220 --> 00:24:31,040 Ia bukan. 581 00:24:31,040 --> 00:24:31,540 Betul? 582 00:24:31,540 --> 00:24:36,150 Karena kita berkesan dengan menggunakan ini jadual hash multi-layer. 583 00:24:36,150 --> 00:24:38,280 Dan masa yang berjalan dari mana-mana operasi ini 584 00:24:38,280 --> 00:24:41,510 tidak bergantung kepada bilangan unsur-unsur yang ada dalam struktur data 585 00:24:41,510 --> 00:24:43,090 atau yang akhirnya akan berada dalam struktur data, 586 00:24:43,090 --> 00:24:44,714 tetapi pada panjang apa yang secara khusus? 587 00:24:44,714 --> 00:24:46,500 588 00:24:46,500 --> 00:24:49,200 >> Rentetan menjadi dimasukkan, yang tidak membuat 589 00:24:49,200 --> 00:24:52,580 ini asimtotik berterusan O besar time-- satu. 590 00:24:52,580 --> 00:24:54,720 Dan terus terang, kalau- dunia sebenar, ini 591 00:24:54,720 --> 00:24:58,380 ertinya memasukkan nama Daven ini mengambil seperti lima langkah, atau Davenport sembilan 592 00:24:58,380 --> 00:25:00,100 langkah-langkah, atau David lima langkah. 593 00:25:00,100 --> 00:25:03,071 Itu cukup darn masa kecil berjalan. 594 00:25:03,071 --> 00:25:05,320 Dan, memang, itu yang sangat perkara yang baik, terutama ketika 595 00:25:05,320 --> 00:25:08,126 ia tidak bergantung kepada jumlah beberapa elemen di sana. 596 00:25:08,126 --> 00:25:10,500 Jadi bagaimana kita boleh melaksanakan ini jenis struktur dalam kod? 597 00:25:10,500 --> 00:25:12,900 Ini lebih sedikit kompleks, tetapi masih ia 598 00:25:12,900 --> 00:25:15,050 hanya permohonan dari blok binaan asas. 599 00:25:15,050 --> 00:25:17,830 Saya akan mentakrifkan semula nod kami seperti berikut: 600 00:25:17,830 --> 00:25:21,100 bool disebut word-- dan ini boleh dipanggil apa-apa. 601 00:25:21,100 --> 00:25:23,970 Tetapi bool mewakili apa yang saya menarik sebagai tanda semak. 602 00:25:23,970 --> 00:25:24,490 Ya. 603 00:25:24,490 --> 00:25:26,720 Ini adalah akhir dari rentetan dalam struktur data ini. 604 00:25:26,720 --> 00:25:30,702 >> Dan, sudah tentu, bintang nod terdapat adalah merujuk kepada kanak-kanak. 605 00:25:30,702 --> 00:25:32,410 Dan, memang, hanya suka pohon keluarga, anda 606 00:25:32,410 --> 00:25:34,370 akan mempertimbangkan nod yang menggantung 607 00:25:34,370 --> 00:25:36,920 dari bahagian bawah ibu bapa beberapa elemen untuk menjadi kanak-kanak. 608 00:25:36,920 --> 00:25:40,510 Karena itu, anak akan menjadi array 27, yang ke-27 609 00:25:40,510 --> 00:25:41,680 hanya menjadi untuk tanda kutip. 610 00:25:41,680 --> 00:25:43,390 Kami akan menyusun kes khas itu. 611 00:25:43,390 --> 00:25:45,400 Jadi, anda boleh mempunyai beberapa nama dengan apostrof. 612 00:25:45,400 --> 00:25:47,399 Mungkin bahkan sempang harus masuk ke sana, tetapi anda akan 613 00:25:47,399 --> 00:25:50,330 lihat dalam p set 5 kita hanya penjagaan tentang huruf dan tanda baca. 614 00:25:50,330 --> 00:25:52,990 >> Kemudian bagaimana anda mewakili struktur data itu sendiri? 615 00:25:52,990 --> 00:25:56,454 Bagaimana anda mewakili akar dari indone ini, boleh dikatakan? 616 00:25:56,454 --> 00:25:59,620 Yah, hanya suka dengan senarai yang disambungkan, anda memerlukan pointer ke elemen pertama. 617 00:25:59,620 --> 00:26:04,270 Dengan indone a, anda perlu satu pointer ke akar indone ini. 618 00:26:04,270 --> 00:26:07,290 Dan dari sana anda boleh hash cara anda ke bawah yang lebih mendalam dan lebih mendalam 619 00:26:07,290 --> 00:26:10,460 kepada setiap nod yang lain dalam struktur. 620 00:26:10,460 --> 00:26:13,440 Jadi hanya dengan dapat ini kami mewakili struct. 621 00:26:13,440 --> 00:26:15,877 >> Sekarang Meanwhile-- Oh, soalan. 622 00:26:15,877 --> 00:26:17,220 >> PENONTON: Apa kata bool? 623 00:26:17,220 --> 00:26:20,490 >> DAVID MALAN: Kata Bool adalah hanya penjelmaan C ini 624 00:26:20,490 --> 00:26:22,920 dari apa yang saya jelaskan di ruang ini di sini, ketika 625 00:26:22,920 --> 00:26:26,000 Saya mula membelah setiap satu daripada unsur dan ini menjadi dua bagian. 626 00:26:26,000 --> 00:26:27,600 Satu adalah pointer ke nod seterusnya. 627 00:26:27,600 --> 00:26:30,280 Yang lain harus menjadi sesuatu seperti kotak semak 628 00:26:30,280 --> 00:26:33,770 untuk mengatakan ya, ada Daven perkataan yang berakhir di sini, 629 00:26:33,770 --> 00:26:35,610 kerana kita tidak mahu, pada masa ini, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Walaupun Dave akan menjadi kata yang sah, ia tidak dalam trie 631 00:26:39,320 --> 00:26:39,830 lagi. 632 00:26:39,830 --> 00:26:40,950 Dan D bukan perkataan. 633 00:26:40,950 --> 00:26:42,770 Dan D-A bukan perkataan atau nama. 634 00:26:42,770 --> 00:26:45,020 Jadi tanda cek menunjukkan hanya sekali anda 635 00:26:45,020 --> 00:26:48,190 memukul nod ini adalah jalur sebelumnya aksara 636 00:26:48,190 --> 00:26:50,700 sebenarnya rentetan yang anda telah dimasukkan. 637 00:26:50,700 --> 00:26:53,660 Jadi itu sahaja bool ada lakukan untuk kita. 638 00:26:53,660 --> 00:26:55,500 >> Sebarang pertanyaan lain di cuba? 639 00:26:55,500 --> 00:26:56,215 Yeah. 640 00:26:56,215 --> 00:26:58,035 >> PENONTON: Apa yang tumpang tindih? 641 00:26:58,035 --> 00:26:59,945 Bagaimana jika anda mempunyai Dave dan Daven? 642 00:26:59,945 --> 00:27:00,820 DAVID MALAN: Perfect. 643 00:27:00,820 --> 00:27:02,580 Bagaimana jika anda mempunyai Dave dan Daven? 644 00:27:02,580 --> 00:27:06,240 Jadi, jika kita memasukkan, berkata nama panggilan, untuk David-- Dave-- D-A-V-E? 645 00:27:06,240 --> 00:27:07,370 646 00:27:07,370 --> 00:27:08,700 Ini sebenarnya adalah super mudah. 647 00:27:08,700 --> 00:27:10,325 Oleh itu, kita hanya akan mengambil empat langkah. 648 00:27:10,325 --> 00:27:11,042 649 00:27:11,042 --> 00:27:15,847 D-A-V-E. Dan apa yang saya perlu lakukan setelah saya menekan bahwa nod keempat? 650 00:27:15,847 --> 00:27:16,680 Hanya pergi untuk memeriksa. 651 00:27:16,680 --> 00:27:18,000 Kita sudah baik untuk pergi. 652 00:27:18,000 --> 00:27:18,840 Selesai. 653 00:27:18,840 --> 00:27:19,750 Empat langkah. 654 00:27:19,750 --> 00:27:21,590 Pemalar masa asimtotik. 655 00:27:21,590 --> 00:27:26,300 Dan sekarang kita telah menunjukkan bahawa kedua-dua Dave dan Daven adalah wayang dalam struktur. 656 00:27:26,300 --> 00:27:27,710 Jadi tidak menjadi masalah. 657 00:27:27,710 --> 00:27:30,200 Dan perhatikan bagaimana kehadiran dari Daven tidak berjaya 658 00:27:30,200 --> 00:27:34,750 mengambil masa lebih kurang masa untuk Dave dan sebaliknya. 659 00:27:34,750 --> 00:27:36,000 >> Jadi apa lagi yang boleh kita lakukan? 660 00:27:36,000 --> 00:27:40,680 Kami telah menggunakan metafora ini sebelum dulang yang mewakili sesuatu. 661 00:27:40,680 --> 00:27:43,380 Tetapi ternyata bahawa tumpukan dulang sebenarnya 662 00:27:43,380 --> 00:27:47,187 demonstratif yang lain data abstrak type-- struktur data tahap yang lebih tinggi 663 00:27:47,187 --> 00:27:49,770 bahawa pada akhir hari itu hanya seperti array atau senarai berpaut 664 00:27:49,770 --> 00:27:50,970 atau sesuatu yang lebih biasa. 665 00:27:50,970 --> 00:27:53,270 Tetapi ia lebih menarik konsep konsep. 666 00:27:53,270 --> 00:27:56,440 Tumpukan, seperti ini baki di sini di Mather, 667 00:27:56,440 --> 00:27:58,750 umumnya disebut hanya bahawa- tumpukan. 668 00:27:58,750 --> 00:28:02,540 >> Dan dalam jenis struktur data anda mempunyai dua operations-- 669 00:28:02,540 --> 00:28:05,880 anda mempunyai satu yang disebut dorongan untuk menambahkan sesuatu ke tepi, 670 00:28:05,880 --> 00:28:08,320 seperti meletakkan dulang lain belakang pada bahagian atas tindanan. 671 00:28:08,320 --> 00:28:11,350 Dan kemudian pop, yang bermakna anda mengambil baki off paling atas. 672 00:28:11,350 --> 00:28:16,210 Tetapi apa yang penting tentang tumpukan ialah itu punya ciri-ciri ingin tahu ini. 673 00:28:16,210 --> 00:28:19,560 Sebagai staf dewan makan adalah menyusun semula baki untuk makan seterusnya, 674 00:28:19,560 --> 00:28:21,380 apa yang akan menjadi benar tentang bagaimana pelajar 675 00:28:21,380 --> 00:28:22,856 berinteraksi dengan struktur data ini? 676 00:28:22,856 --> 00:28:24,480 PENONTON: Mereka akan muncul satu-satunya. 677 00:28:24,480 --> 00:28:26,550 DAVID MALAN: Mereka akan pop hanya satu-satunya, mudah-mudahan atas. 678 00:28:26,550 --> 00:28:28,910 Jika tidak, ia hanya semacam bodoh untuk pergi sepanjang jalan ke bawah. 679 00:28:28,910 --> 00:28:29,070 Betul? 680 00:28:29,070 --> 00:28:31,620 Struktur data tidak benar-benar membolehkan Anda untuk mengambil baki bahagian bawah sekurang-kurangnya 681 00:28:31,620 --> 00:28:32,520 dengan mudah. 682 00:28:32,520 --> 00:28:35,040 Jadi ada ini ingin tahu harta kepada tumpukan 683 00:28:35,040 --> 00:28:39,730 bahawa perkara yang terakhir dalam adalah akan menjadi pertama keluar itu. 684 00:28:39,730 --> 00:28:43,400 Dan ahli-ahli sains komputer memanggil ini LIFO-- bertahan, keluar pertama. 685 00:28:43,400 --> 00:28:45,540 Dan ia benar-benar tidak mempunyai aplikasi menarik. 686 00:28:45,540 --> 00:28:50,090 Ia tidak semestinya jelas seperti beberapa orang lain, tetapi ia boleh, memang, bermanfaat, 687 00:28:50,090 --> 00:28:54,040 dan ia boleh, memang, dilaksanakan dalam beberapa cara yang berbeza. 688 00:28:54,040 --> 00:28:58,550 >> Jadi satu, dan benar-benar, biarlah saya untuk tidak menyelam ke dalam. 689 00:28:58,550 --> 00:28:59,860 Mari kita buat ini sebagai gantinya. 690 00:28:59,860 --> 00:29:03,700 Mari kita lihat satu yang hampir Idea yang sama, tetapi ia lebih adil sedikit. 691 00:29:03,700 --> 00:29:04,200 Betul? 692 00:29:04,200 --> 00:29:07,560 Jika anda salah seorang dari anak-anak peminat atau kanak-kanak perempuan yang benar-benar suka produk Apple 693 00:29:07,560 --> 00:29:10,130 dan anda bangun pada 3:00 AM untuk beratur di beberapa kedai 694 00:29:10,130 --> 00:29:14,150 untuk mendapatkan iPhone yang terkini, anda mungkin beratur seperti ini. 695 00:29:14,150 --> 00:29:15,800 >> Sekarang giliran sangat sengaja dinamakan. 696 00:29:15,800 --> 00:29:18,190 Ini garis kerana ada beberapa keadilan kepadanya. 697 00:29:18,190 --> 00:29:18,690 Betul? 698 00:29:18,690 --> 00:29:21,690 Ia jenis akan disedut jika anda mempunyai sampai di sana pertama di Kedai Apple 699 00:29:21,690 --> 00:29:25,700 tetapi anda secara efektif paling bawah yang dulang kerana pekerja Apple kemudian 700 00:29:25,700 --> 00:29:28,189 pop orang yang terakhir benar-benar mendapat dalam talian. 701 00:29:28,189 --> 00:29:31,230 Jadi tumpukan dan beratur, walaupun fungsi mereka agak same-- yang 702 00:29:31,230 --> 00:29:33,105 ia hanya koleksi ini sumber yang 703 00:29:33,105 --> 00:29:36,210 akan tumbuh dan shrink-- ada yang aspek keadilan ini kepadanya, 704 00:29:36,210 --> 00:29:39,634 sekurang-kurangnya dalam dunia sebenar, di mana operasi anda bersenam 705 00:29:39,634 --> 00:29:40,800 pada dasarnya berbeza. 706 00:29:40,800 --> 00:29:43,360 A stack-- antrian rather-- dikatakan mempunyai 707 00:29:43,360 --> 00:29:45,320 dua operasi: n barisan dan d barisan. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Atau anda boleh menghubungi mereka mana-mana beberapa perkara. 710 00:29:48,090 --> 00:29:50,770 Tetapi anda hanya ingin menangkap tanggapan bahawa seseorang itu menambah 711 00:29:50,770 --> 00:29:53,230 dan seseorang itu akhirnya menolak. 712 00:29:53,230 --> 00:29:58,840 >> Sekarang di bawah hood, kedua-dua tindanan dan barisan yang boleh dilaksanakan bagaimana? 713 00:29:58,840 --> 00:30:01,390 Kami tidak akan masuk ke dalam kod ia kerana tahap yang lebih tinggi 714 00:30:01,390 --> 00:30:03,387 idea adalah semacam lebih jelas. 715 00:30:03,387 --> 00:30:04,470 Maksud saya, apa yang manusia lakukan? 716 00:30:04,470 --> 00:30:07,030 Jika saya seorang yang pertama di Apple Simpan dan ini adalah pintu depan, 717 00:30:07,030 --> 00:30:08,130 Anda tahu, saya akan berdiri di sini. 718 00:30:08,130 --> 00:30:09,750 Dan orang yang depan akan berdiri di sini. 719 00:30:09,750 --> 00:30:11,500 Dan orang yang depan akan berdiri di sini. 720 00:30:11,500 --> 00:30:13,792 Jadi apa struktur data cocok untuk beratur? 721 00:30:13,792 --> 00:30:14,542 >> PENONTON: Sebuah antrian. 722 00:30:14,542 --> 00:30:15,667 DAVID MALAN: Baik, antrian. 723 00:30:15,667 --> 00:30:16,390 Tentu. 724 00:30:16,390 --> 00:30:16,920 Apa lagi? 725 00:30:16,920 --> 00:30:17,600 >> PENONTON: Senarai berkaitan. 726 00:30:17,600 --> 00:30:18,990 >> DAVID MALAN: A dikaitkan daftar anda boleh melaksanakan. 727 00:30:18,990 --> 00:30:22,500 Dan senarai berpaut adalah bagus kerana selepas itu ia boleh membesar secara sewenang-wenangnya panjang yang bertentangan 728 00:30:22,500 --> 00:30:24,880 untuk mempunyai beberapa jumlah tetap orang di kedai. 729 00:30:24,880 --> 00:30:27,030 Tetapi mungkin beberapa tetap tempat-tempat yang sah. 730 00:30:27,030 --> 00:30:30,350 Kerana jika mereka hanya mempunyai seperti 20 iPhone pada hari pertama, mungkin 731 00:30:30,350 --> 00:30:33,930 mereka hanya perlu pelbagai saiz 20 sebagai menggambarkan yang antrian, yang 732 00:30:33,930 --> 00:30:37,070 hanya untuk mengatakan sekarang setelah kami mula bercakap mengenai masalah yang lebih tinggi, 733 00:30:37,070 --> 00:30:38,890 anda boleh melaksanakannya dalam mana-mana cara. 734 00:30:38,890 --> 00:30:42,030 Dan ada mungkin hanya akan menjadi trade off dalam ruang dan waktu 735 00:30:42,030 --> 00:30:43,950 atau hanya dalam kerumitan kod anda sendiri. 736 00:30:43,950 --> 00:30:45,380 >> Bagaimana stack? 737 00:30:45,380 --> 00:30:48,190 Nah, tumpukan, kita telah melihat terlalu hanya boleh menjadi dulang ini. 738 00:30:48,190 --> 00:30:50,007 Dan anda boleh melaksanakan ini array. 739 00:30:50,007 --> 00:30:53,090 Tetapi pada satu masa nanti jika anda menggunakan array, apa yang akan berlaku kepada baki 740 00:30:53,090 --> 00:30:54,173 anda cuba untuk meletakkan? 741 00:30:54,173 --> 00:30:55,170 742 00:30:55,170 --> 00:30:55,670 Baik. 743 00:30:55,670 --> 00:30:57,490 Anda hanya akan dapat pergi begitu tinggi. 744 00:30:57,490 --> 00:31:00,156 Dan saya fikir dalam Mather mereka sebenarnya tersembunyi dalam pembukaan itu. 745 00:31:00,156 --> 00:31:01,950 Jadi sesungguhnya, hampir seperti Mather menggunakan 746 00:31:01,950 --> 00:31:03,783 pelbagai saiz tetap, kerana anda hanya boleh 747 00:31:03,783 --> 00:31:08,302 memasang sedemikian banyak dulang di yang dibuka pada dinding di bawah lutut rakyat. 748 00:31:08,302 --> 00:31:10,010 Dan sebagainya yang mungkin dikatakan array, 749 00:31:10,010 --> 00:31:14,300 tetapi kita boleh melaksanakan yang lebih umum dengan senarai berpaut. 750 00:31:14,300 --> 00:31:16,390 >> Nah, bagaimana struktur data yang lain? 751 00:31:16,390 --> 00:31:18,760 Izinkan saya menarik yang lain dengar sini. 752 00:31:18,760 --> 00:31:24,710 Sesuatu seperti bagaimana kira-kira satu ini di sini? 753 00:31:24,710 --> 00:31:28,920 Mengapa hal ini mungkin berguna untuk tidak mempunyai sesuatu yang mewah sebagai indone, yang 754 00:31:28,920 --> 00:31:32,370 kami melihat memiliki nod ini sangat luas, yang masing-masing dalam array? 755 00:31:32,370 --> 00:31:35,740 Tapi bagaimana kalau kita melakukan sesuatu yang lebih sederhana, seperti pohon keluarga sekolah lama, 756 00:31:35,740 --> 00:31:38,110 setiap yang node di sini hanya menyimpan nombor. 757 00:31:38,110 --> 00:31:42,180 Sebagai ganti nama atau keturunan yang hanya menyimpan beberapa seperti ini. 758 00:31:42,180 --> 00:31:45,250 >> Nah, jargon yang kita gunakan dalam struktur data adalah kedua-dua negara- 759 00:31:45,250 --> 00:31:49,510 dan pokok-pokok, di mana trie, sekali lagi, adalah hanya satu yang node array, 760 00:31:49,510 --> 00:31:51,680 masih apa yang anda mungkin gunakan dari sekolah dasar 761 00:31:51,680 --> 00:31:53,860 apabila anda membuat keluarga yang daun tree-- dan punca kuasa 762 00:31:53,860 --> 00:31:57,250 pohon dan kanak-kanak daripada ibu bapa dan adik-beradik itu. 763 00:31:57,250 --> 00:32:03,670 Dan kita mungkin melaksanakan pokok, misalnya, sebagai hanya kerana ini. 764 00:32:03,670 --> 00:32:07,420 Pokok A, jika sebagai nod, salah satu ini kalangan yang mempunyai nombor, 765 00:32:07,420 --> 00:32:09,947 ia tidak akan mempunyai satu penunjuk, tetapi dua. 766 00:32:09,947 --> 00:32:11,780 Dan sebaik sahaja anda menambah pointer kedua, anda 767 00:32:11,780 --> 00:32:13,905 sebenarnya kini boleh membuat semacam data dua dimensi 768 00:32:13,905 --> 00:32:14,780 struktur dalam ingatan. 769 00:32:14,780 --> 00:32:16,660 Sama seperti a-dua dimensi array, anda boleh 770 00:32:16,660 --> 00:32:18,904 mempunyai jenis dua dimensi daftar terkait tetapi yang 771 00:32:18,904 --> 00:32:20,820 yang mengikuti corak yang di mana tidak ada kitaran. 772 00:32:20,820 --> 00:32:24,487 Ini benar-benar pohon dengan satu cara nenek di sini dan kemudian 773 00:32:24,487 --> 00:32:27,320 beberapa orang tua dan kanak-kanak dan cucu dan cicit. 774 00:32:27,320 --> 00:32:28,370 dan sebagainya. 775 00:32:28,370 --> 00:32:32,390 >> Tetapi apa yang benar-benar rapi tentang ini juga, hanya untuk menggoda anda dengan sedikit kod, 776 00:32:32,390 --> 00:32:35,370 recall rekursi daripada beberapa waktu yang lalu, di mana 777 00:32:35,370 --> 00:32:38,220 Anda menulis fungsi yang memanggil dirinya sendiri. 778 00:32:38,220 --> 00:32:41,140 Ini adalah kesempatan yang indah untuk melaksanakan sesuatu 779 00:32:41,140 --> 00:32:42,920 seperti rekursi, kerana menganggap ini. 780 00:32:42,920 --> 00:32:43,860 >> Ini adalah pokok. 781 00:32:43,860 --> 00:32:48,040 Dan Aku sudah menjadi dubur kecil dengan cara Aku meletakkan bilangan bulat ke jalan. 782 00:32:48,040 --> 00:32:51,020 Sehingga ia mempunyai khas name-- pokok carian binari. 783 00:32:51,020 --> 00:32:53,460 Sekarang kita telah mendengar dari binari mencari, tetapi anda boleh 784 00:32:53,460 --> 00:32:55,180 bekerja ke belakang dari nama ini perkara ini? 785 00:32:55,180 --> 00:32:59,280 Bagaimana pola tentang bagaimana saya dimasukkan integer ke dalam pokok ini? 786 00:32:59,280 --> 00:33:00,696 Ia bukan sewenang-wenang. 787 00:33:00,696 --> 00:33:01,570 Ada beberapa corak. 788 00:33:01,570 --> 00:33:02,090 Yeah. 789 00:33:02,090 --> 00:33:03,370 >> PENONTON: orang-orang yang lebih kecil di sebelah kiri. 790 00:33:03,370 --> 00:33:03,690 >> DAVID MALAN: Ya. 791 00:33:03,690 --> 00:33:05,062 Orang-orang yang lebih kecil di sebelah kiri. 792 00:33:05,062 --> 00:33:06,270 Yang lebih besar adalah di sebelah kanan. 793 00:33:06,270 --> 00:33:12,940 Sehingga pernyataan yang benar adalah orang tua adalah lebih besar daripada anak kiri, 794 00:33:12,940 --> 00:33:14,850 tetapi kurang daripada kanak-kanak yang benar. 795 00:33:14,850 --> 00:33:17,750 Dan itu saja bahkan ada definisi lisan rekursif 796 00:33:17,750 --> 00:33:20,500 kerana anda boleh memohon supaya logik yang sama untuk setiap nod 797 00:33:20,500 --> 00:33:23,080 dan hanya bahagian bawah keluar, kasus dasar jika anda 798 00:33:23,080 --> 00:33:25,740 akan, ketika anda menekan salah satu daun, boleh dikatakan, 799 00:33:25,740 --> 00:33:28,580 jika kebenaran yang tidak mempunyai anak-anak lagi. 800 00:33:28,580 --> 00:33:30,614 >> Sekarang bagaimana anda boleh mendapatkan nombor 44? 801 00:33:30,614 --> 00:33:32,280 Anda akan bermula pada akar dan berkata, hm. 802 00:33:32,280 --> 00:33:35,690 55 bukan 44 Jadi saya mahu pergi hak atau yang ingin saya ke kiri? 803 00:33:35,690 --> 00:33:37,190 Nah, jelas anda mahu pergi kiri. 804 00:33:37,190 --> 00:33:40,060 Dan sebagainya itu hanya seperti telefon buku contoh dalam pencarian binari 805 00:33:40,060 --> 00:33:41,099 secara lebih umum. 806 00:33:41,099 --> 00:33:43,390 Tapi kami melaksanakannya sekarang sedikit lebih dinamik 807 00:33:43,390 --> 00:33:45,339 daripada array mungkin mengizinkan. 808 00:33:45,339 --> 00:33:48,130 Dan sebenarnya, jika anda ingin melihat kode tersebut, pada pandangan pertama pasti. 809 00:33:48,130 --> 00:33:49,671 Ia kelihatan seperti sejumlah besar garis. 810 00:33:49,671 --> 00:33:51,220 Tapi itu indah sederhana. 811 00:33:51,220 --> 00:33:54,490 Jika anda ingin untuk melaksanakan fungsi disebut carian yang tujuannya dalam kehidupan 812 00:33:54,490 --> 00:33:57,290 adalah untuk mencari nilai yang seperti n, integer, 813 00:33:57,290 --> 00:34:01,756 dan anda berlalu dalam pointer-- satu pointer ke nod akar, 814 00:34:01,756 --> 00:34:04,380 sebaliknya, pokok yang yang Anda boleh mengakses segala sesuatu yang lain, 815 00:34:04,380 --> 00:34:08,850 perhatikan bagaimana lugas anda boleh melaksanakan logik. 816 00:34:08,850 --> 00:34:10,880 Jika pokok adalah tidak sah, Jelas sekali ia tidak ada di sana. 817 00:34:10,880 --> 00:34:11,880 Mari kita kembali palsu. 818 00:34:11,880 --> 00:34:12,000 Betul? 819 00:34:12,000 --> 00:34:14,040 Jika anda serahkan apa-apa, ada apa-apa di sana. 820 00:34:14,040 --> 00:34:17,900 >> Yang lain, jika n adalah kurang daripada pokok panah n-- sekarang arrow n, 821 00:34:17,900 --> 00:34:20,670 ingat kami memperkenalkan super secara ringkas pada hari yang lain, 822 00:34:20,670 --> 00:34:25,100 dan itu hanya berarti de-rujukan penunjuk dan melihat bidang yang disebut n. 823 00:34:25,100 --> 00:34:27,690 Jadi ia bermakna pergi ke sana dan melihat bidang yang disebut n. 824 00:34:27,690 --> 00:34:33,810 Jadi, jika n, nilai yang anda diberikan, adalah kurang daripada nilai integer di pokok itu, 825 00:34:33,810 --> 00:34:35,449 di mana anda mahu pergi? 826 00:34:35,449 --> 00:34:36,389 Ke kiri. 827 00:34:36,389 --> 00:34:37,780 >> Jadi melihat rekursi. 828 00:34:37,780 --> 00:34:39,860 Saya returning-- tidak benar. 829 00:34:39,860 --> 00:34:40,989 Tidak palsu. 830 00:34:40,989 --> 00:34:45,670 Aku kembali apa sahaja jawapan adalah dari panggilan kepada diri saya sendiri, lulus 831 00:34:45,670 --> 00:34:50,100 n lagi, yang berlebihan, tetapi apa yang sedikit berbeza ini? 832 00:34:50,100 --> 00:34:51,989 Bagaimana saya membuat masalah yang lebih kecil? 833 00:34:51,989 --> 00:34:54,920 Saya lulus sebagai yang kedua hujah, bukan akar pokok itu, 834 00:34:54,920 --> 00:34:59,616 tetapi kanak-kanak di sebelah kiri dalam kes ini. 835 00:34:59,616 --> 00:35:00,990 Jadi, saya lulus dalam kanak-kanak di sebelah kiri. 836 00:35:00,990 --> 00:35:04,720 >> Sementara itu, jika n lebih besar daripada nod saya sedang melihat, 837 00:35:04,720 --> 00:35:06,690 Saya mencari sebelah kanan. 838 00:35:06,690 --> 00:35:10,880 Yang lain, jika pokok itu tidak batal, dan jika elemen bukan ke kiri 839 00:35:10,880 --> 00:35:13,240 dan ia bukan ke kanan, apa yang hebat berlaku? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Kami telah benar-benar menemukan nod di pertanyaan, dan dengan itu kita kembali benar. 842 00:35:18,440 --> 00:35:21,490 >> Oleh itu, kita baru sahaja tercalar permukaan sekarang beberapa struktur data. 843 00:35:21,490 --> 00:35:24,370 Dalam masalah meletakkan lima anda akan meneroka ini belum lagi, 844 00:35:24,370 --> 00:35:27,250 dan anda akan diberikan reka bentuk anda pilihan bagaimana untuk pergi tentang ini. 845 00:35:27,250 --> 00:35:30,250 Apa yang saya ingin membuat kesimpulan mengenai hanya 30 teaser kedua 846 00:35:30,250 --> 00:35:32,080 dari apa yang menanti minggu depan dan seterusnya. 847 00:35:32,080 --> 00:35:35,390 >> Seperti yang kita begin-- bersyukur kerana anda mungkin think-- transisi kita perlahan-lahan 848 00:35:35,390 --> 00:35:38,680 dari dunia C dan lebih rendah rincian pelaksanaan peringkat, 849 00:35:38,680 --> 00:35:42,090 untuk sebuah dunia di mana kita boleh mengambil untuk diberikan bahawa orang lain mempunyai akhirnya 850 00:35:42,090 --> 00:35:44,010 dilaksanakan data ini struktur bagi kita, 851 00:35:44,010 --> 00:35:47,570 dan kami akan mula memahami dunia nyata berarti melaksanakan 852 00:35:47,570 --> 00:35:50,560 program berasaskan web dan laman web yang lebih umum 853 00:35:50,560 --> 00:35:52,910 dan juga keselamatan sangat implikasi yang kita baru 854 00:35:52,910 --> 00:35:54,850 mula menggores permukaan. 855 00:35:54,850 --> 00:35:57,320 Berikut adalah apa yang menanti kita pada hari-hari yang akan datang. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO MAIN SEMULA] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Dia Datang dengan mesej, dengan protokol yang semua sendiri. 859 00:36:12,780 --> 00:36:26,110 860 00:36:26,110 --> 00:36:30,894 Dia datang ke dunia yang kejam firewall, router tidak peduli, 861 00:36:30,894 --> 00:36:33,368 dan bahaya yang jauh lebih buruk daripada kematian. 862 00:36:33,368 --> 00:36:35,280 863 00:36:35,280 --> 00:36:36,236 Dia cepat. 864 00:36:36,236 --> 00:36:37,980 Dia kuat. 865 00:36:37,980 --> 00:36:42,830 Dia TCP / IP, dan dia punya alamat anda. 866 00:36:42,830 --> 00:36:45,290 867 00:36:45,290 --> 00:36:48,074 "Laskar yang bersih." 868 00:36:48,074 --> 00:36:49,660 [AKHIR VIDEO MAIN SEMULA] 869 00:36:49,660 --> 00:36:50,910 DAVID MALAN: Bakal minggu depan. 870 00:36:50,910 --> 00:36:51,880 Kami akan melihat anda kemudian. 871 00:36:51,880 --> 00:36:54,615 872 00:36:54,615 --> 00:36:56,060 [VIDEO MAIN SEMULA] 873 00:36:56,060 --> 00:36:59,240 -Dan Sekarang, "Pemikiran Deep" oleh Daven Farnham. 874 00:36:59,240 --> 00:37:02,030 875 00:37:02,030 --> 00:37:05,820 -David Selalu dimulai kuliah dengan, "Baiklah." 876 00:37:05,820 --> 00:37:08,750 Mengapa tidak, "Inilah penyelesaian untuk set masalah "minggu ini 877 00:37:08,750 --> 00:37:12,180 atau "Kami memberikan anda semua A?" 878 00:37:12,180 --> 00:37:13,380 [TERTAWA] 879 00:37:13,380 --> 00:37:15,530 [AKHIR VIDEO MAIN SEMULA]