1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:03,340 [MUSIC PLAYING] 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 baik awal dan end-- seperti literally-- hampir akhir 6 00:00:18,090 --> 00:00:18,825 minggu enam. 7 00:00:18,825 --> 00:00:20,030 8 00:00:20,030 --> 00:00:22,640 >> Saya pikir saya akan berbagi sedikit dari fakta yang menyenangkan. 9 00:00:22,640 --> 00:00:25,370 Aku sudah menarik ini naik dari mengatur data masa lalu semester. 10 00:00:25,370 --> 00:00:29,710 Anda mungkin ingat bahwa kami meminta Anda pada setiap bentuk set p jika Anda telah menyaksikan secara online 11 00:00:29,710 --> 00:00:31,580 atau jika Anda telah menghadiri secara pribadi. 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 sangat banyak diprediksi. 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 menerka mengapa hal ini Grafik begitu bergerigi, naik turun, naik turun, 16 00:00:40,599 --> 00:00:41,265 begitu konsisten? 17 00:00:41,265 --> 00:00:42,980 18 00:00:42,980 --> 00:00:45,130 Apa masing-masing puncak dan palung mewakili? 19 00:00:45,130 --> 00:00:46,005 >> AUDIENCE: [tidak terdengar] 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 menggelikan, Allah melarang, kita memegang salah satu kuliah pada hari Jumat 24 00:00:55,480 --> 00:00:58,960 pada awal semester, itulah yang kita lihat terjadi. 25 00:00:58,960 --> 00:01:03,430 Jadi hari ini, kami ikut serta dalam sedikit lebih lanjut tentang struktur data. 26 00:01:03,430 --> 00:01:06,660 Dan untuk memberikan Anda lebih dari yang solid model mental untuk masalah jam lima, 27 00:01:06,660 --> 00:01:07,450 yang sekarang keluar. 28 00:01:07,450 --> 00:01:10,817 Salah ejaan, dimana, kita akan tangan Anda file teks 100.000 29 00:01:10,817 --> 00:01:12,650 ditambah kata-kata bahasa Inggris, dan Anda akan memiliki 30 00:01:12,650 --> 00:01:17,770 untuk mengetahui bagaimana cerdik beban mereka ke dalam memori, ke dalam RAM, dengan 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 bisa jadi, tapi mungkin tidak boleh, 33 00:01:22,470 --> 00:01:25,630 yang terkait daftar yang cukup sederhana, yang kami memperkenalkan terakhir kali. 34 00:01:25,630 --> 00:01:29,220 Dan sebuah linked list memiliki setidaknya satu keuntungan atas array. 35 00:01:29,220 --> 00:01:32,096 Apa salah satu keuntungan dari linked list bisa dibilang? 36 00:01:32,096 --> 00:01:32,950 >> AUDIENCE: Penyisipan. 37 00:01:32,950 --> 00:01:33,908 >> DAVID Malan: Penyisipan. 38 00:01:33,908 --> 00:01:34,155 39 00:01:34,155 --> 00:01:35,196 Apa yang Anda maksud dengan itu? 40 00:01:35,196 --> 00:01:37,872 >> AUDIENCE: Di mana saja sepanjang daftar [tidak terdengar]. 41 00:01:37,872 --> 00:01:38,770 >> DAVID Malan: Baik. 42 00:01:38,770 --> 00:01:42,090 Jadi Anda dapat memasukkan unsur mana pun Anda ingin di tengah-tengah daftar 43 00:01:42,090 --> 00:01:45,490 tanpa harus mengocok apa-apa, yang kami menyimpulkan, dalam pemilahan kami 44 00:01:45,490 --> 00:01:47,630 diskusi, tidak selalu hal yang baik, 45 00:01:47,630 --> 00:01:51,200 karena butuh waktu untuk benar-benar bergerak semua orang manusia ke kiri atau kanan. 46 00:01:51,200 --> 00:01:55,540 Dan dengan linked list, Anda dapat hanya mengalokasikan dengan malloc, node baru, 47 00:01:55,540 --> 00:01:58,385 dan kemudian memperbarui beberapa pointers-- dua, tiga operasi max-- 48 00:01:58,385 --> 00:02:01,480 dan kami dapat slot seseorang di mana saja ke dalam daftar. 49 00:02:01,480 --> 00:02:03,550 >> Apa lagi yang menguntungkan tentang linked list? 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 >> AUDIENCE: [tidak terdengar] 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 Ini benar-benar dinamis. 58 00:02:12,070 --> 00:02:15,100 Dan bahwa Anda tidak melakukan, di muka, beberapa ukuran tetap 59 00:02:15,100 --> 00:02:18,750 sepotong memori, seperti Anda akan memiliki untuk dengan array, terbalik dari yang 60 00:02:18,750 --> 00:02:22,455 adalah bahwa Anda dapat mengalokasikan node hanya pada permintaan sehingga hanya menggunakan banyak ruang 61 00:02:22,455 --> 00:02:23,330 karena Anda benar-benar membutuhkan. 62 00:02:23,330 --> 00:02:26,830 Sebaliknya dengan array, Anda mungkin sengaja mengalokasikan terlalu sedikit. 63 00:02:26,830 --> 00:02:28,871 Dan kemudian itu hanya akan menjadi sakit di leher 64 00:02:28,871 --> 00:02:32,440 untuk mengalokasikan array yang lebih besar baru, copy semuanya berakhir, membebaskan array tua, 65 00:02:32,440 --> 00:02:33,990 dan kemudian bergerak tentang bisnis Anda. 66 00:02:33,990 --> 00:02:37,479 Atau lebih buruk, Anda mungkin mengalokasikan cara memori lebih dari yang sebenarnya Anda butuhkan, 67 00:02:37,479 --> 00:02:40,520 dan sehingga Anda akan memiliki yang sangat jarang penduduknya array, sehingga untuk berbicara. 68 00:02:40,520 --> 00:02:44,350 >> Jadi sebuah linked list memberikan Anda ini keuntungan dari dinamika dan fleksibilitas 69 00:02:44,350 --> 00:02:46,080 dengan sisipan dan penghapusan. 70 00:02:46,080 --> 00:02:48,000 Tapi tentunya harus ada harga yang harus dibayar. 71 00:02:48,000 --> 00:02:50,000 Bahkan, salah satu tema dieksplorasi pada kuis nol 72 00:02:50,000 --> 00:02:52,430 adalah beberapa trade-off kita lihat sejauh ini. 73 00:02:52,430 --> 00:02:56,161 Jadi apa harga yang harus dibayar atau downside dari linked list? 74 00:02:56,161 --> 00:02:56,660 Ya. 75 00:02:56,660 --> 00:02:57,560 >> AUDIENCE: Tidak ada akses random. 76 00:02:57,560 --> 00:02:58,809 >> DAVID Malan: Tidak ada akses random. 77 00:02:58,809 --> 00:02:59,540 Tapi siapa yang peduli? 78 00:02:59,540 --> 00:03:01,546 Akses acak tidak terdengar menarik. 79 00:03:01,546 --> 00:03:02,421 >> AUDIENCE: [tidak terdengar] 80 00:03:02,421 --> 00:03:04,865 81 00:03:04,865 --> 00:03:05,740 DAVID Malan: Tepat. 82 00:03:05,740 --> 00:03:07,580 Jika Anda ingin memiliki a algorithm-- tertentu 83 00:03:07,580 --> 00:03:10,170 dan biarkan aku benar-benar mengusulkan pencarian biner khususnya, yang 84 00:03:10,170 --> 00:03:12,600 adalah salah satu kami telah digunakan cukup bit-- sebuah jika Anda tidak memiliki akses acak, 85 00:03:12,600 --> 00:03:15,516 Anda tidak bisa melakukan itu aritmatika sederhana menemukan seperti elemen tengah 86 00:03:15,516 --> 00:03:16,530 dan melompat tepat untuk itu. 87 00:03:16,530 --> 00:03:20,239 Anda malah harus mulai dari pertama elemen dan linear mencari dari kiri 88 00:03:20,239 --> 00:03:22,780 ke kanan jika Anda ingin menemukan tengah atau elemen lainnya. 89 00:03:22,780 --> 00:03:24,410 >> AUDIENCE: Mungkin membutuhkan 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 Dimana adalah bahwa tambahan biaya datang dari dalam memori? 92 00:03:27,464 --> 00:03:28,339 >> AUDIENCE: [tidak terdengar] 93 00:03:28,339 --> 00:03:32,566 94 00:03:32,566 --> 00:03:33,440 DAVID Malan: Tepat. 95 00:03:33,440 --> 00:03:35,679 Dalam hal ini di sini, kami memiliki daftar link untuk bilangan bulat, 96 00:03:35,679 --> 00:03:37,470 namun kami dua kali lipat 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 karena struct Anda mendapatkan lebih besar 99 00:03:42,090 --> 00:03:45,320 dan Anda menyimpan bukan angka tapi mungkin seorang mahasiswa atau objek lain. 100 00:03:45,320 --> 00:03:46,880 Tetapi intinya pasti tetap. 101 00:03:46,880 --> 00:03:49,421 Dan sejumlah 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 pencarian atau penghapusan dalam kasus elemen 104 00:03:54,730 --> 00:03:57,720 kebetulan berada di bagian paling akhir daftar apakah itu diurutkan 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 mungkin juga menjadi waktu yang konstan jika Anda selalu melihat elemen pertama, 107 00:04:04,250 --> 00:04:05,070 misalnya. 108 00:04:05,070 --> 00:04:09,360 Tetapi pada akhirnya, kami berjanji untuk mencapai grail suci 109 00:04:09,360 --> 00:04:12,630 struktur data, atau beberapa daripadanya pendekatan, 110 00:04:12,630 --> 00:04:14,290 dengan cara konstanta waktu. 111 00:04:14,290 --> 00:04:17,579 Dapatkah kita menemukan elemen atau menambahkan elemen atau menghapus elemen dari daftar? 112 00:04:17,579 --> 00:04:19,059 Kita akan melihat cukup segera. 113 00:04:19,059 --> 00:04:21,100 Dan ternyata salah satu yang mekanisme kami 114 00:04:21,100 --> 00:04:23,464 akan mulai menggunakan hari ini, Penggunaan tahunan p set lima, 115 00:04:23,464 --> 00:04:24,630 sebenarnya cukup akrab. 116 00:04:24,630 --> 00:04:27,430 Misalnya, jika ini adalah a bunch buku ujian, masing-masing 117 00:04:27,430 --> 00:04:29,660 memiliki siswa pertama nama dan nama belakang di atasnya, 118 00:04:29,660 --> 00:04:31,820 dan saya menjemput mereka dari pada akhir ujian, 119 00:04:31,820 --> 00:04:33,746 dan mereka semua cantik banyak dalam urutan acak, 120 00:04:33,746 --> 00:04:36,370 dan kami ingin pergi tentang pemilahan ujian ini sehingga setelah dinilai 121 00:04:36,370 --> 00:04:38,661 itu hanya jauh lebih mudah dan lebih cepat untuk menyerahkan mereka kembali 122 00:04:38,661 --> 00:04:40,030 kepada siswa abjad. 123 00:04:40,030 --> 00:04:42,770 Apa yang akan naluri Anda menjadi untuk tumpukan ujian seperti ini? 124 00:04:42,770 --> 00:04:45,019 >> Nah, jika Anda seperti saya, Anda mungkin melihat bahwa ini adalah m, 125 00:04:45,019 --> 00:04:48,505 jadi aku akan semacam menempatkan ini dalam, jika ini adalah meja saya atau lantai mana 126 00:04:48,505 --> 00:04:50,650 Saya menyebarkan hal-hal out-- atau array saya really-- 127 00:04:50,650 --> 00:04:52,210 Aku mungkin menempatkan semua Ms di sana. 128 00:04:52,210 --> 00:04:52,710 Oh. 129 00:04:52,710 --> 00:04:55,020 Berikut ini adalah A. Jadi saya mungkin menempatkan Seperti di sini. 130 00:04:55,020 --> 00:04:55,520 Oh. 131 00:04:55,520 --> 00:04:57,980 Berikut A. lain aku akan untuk menempatkan bahwa di sini. 132 00:04:57,980 --> 00:05:02,490 Berikut Z. sebuah Berikut ini adalah M. lain Dan Aku mungkin mulai membuat tumpukan seperti ini. 133 00:05:02,490 --> 00:05:06,620 Dan kemudian mungkin aku akan pergi nanti dan semacam sangat nitpicky-ly semacam 134 00:05:06,620 --> 00:05:07,710 tumpukan individu. 135 00:05:07,710 --> 00:05:11,300 Tapi yang penting saya akan melihat pada masukan bahwa aku tangan 136 00:05:11,300 --> 00:05:14,016 dan saya akan membuat beberapa dihitung keputusan berdasarkan masukan itu. 137 00:05:14,016 --> 00:05:15,640 Jika dimulai dengan A, meletakkannya di sana. 138 00:05:15,640 --> 00:05:18,980 Jika dimulai dengan Z, meletakkannya di atas di sana, dan segala sesuatu di antaranya. 139 00:05:18,980 --> 00:05:22,730 >> Jadi ini adalah teknik yang umumnya dikenal sebagai hashing-- H-A-S-H-- 140 00:05:22,730 --> 00:05:26,550 yang umumnya berarti mengambil sebagai input dan menggunakan input tersebut untuk menghitung 141 00:05:26,550 --> 00:05:30,940 nilai, umumnya angka, dan bahwa nomor adalah indeks ke penyimpanan 142 00:05:30,940 --> 00:05:32,260 wadah, seperti array. 143 00:05:32,260 --> 00:05:35,490 Jadi dengan kata lain, saya mungkin memiliki Fungsi hash, seperti yang saya lakukan di kepalaku, 144 00:05:35,490 --> 00:05:37,940 bahwa jika saya melihat seseorang yang Nama yang dimulai dengan A, 145 00:05:37,940 --> 00:05:40,190 Aku akan memetakan bahwa ke nol di kepala saya. 146 00:05:40,190 --> 00:05:44,160 Dan jika saya melihat seseorang dengan Z, aku akan memetakan bahwa untuk 25 di kepala saya 147 00:05:44,160 --> 00:05:46,220 dan kemudian memasukkan ke dalam paling tumpukan terakhir. 148 00:05:46,220 --> 00:05:50,990 >> Sekarang, jika Anda berpikir tentang tidak otakku tapi program C, nomor apa bisa 149 00:05:50,990 --> 00:05:53,170 Anda andalkan untuk mencapai itu hasil yang sama? 150 00:05:53,170 --> 00:05:55,594 Dengan kata lain, jika Anda memiliki ASCII karakter A, 151 00:05:55,594 --> 00:05:57,510 bagaimana Anda menentukan apa ember untuk memasukkannya ke dalam? 152 00:05:57,510 --> 00:05:59,801 Anda mungkin tidak ingin memasukkannya ke dalam ember 65, yang 153 00:05:59,801 --> 00:06:01,840 akan seperti di sana tanpa alasan. 154 00:06:01,840 --> 00:06:04,320 Di mana Anda ingin menempatkan A dalam hal nilai ASCII nya? 155 00:06:04,320 --> 00:06:05,600 156 00:06:05,600 --> 00:06:08,920 Di mana Anda ingin lakukan untuk ASCII Nilai untuk datang dengan lebih cerdas ember 157 00:06:08,920 --> 00:06:09,480 untuk memasukkannya ke dalam? 158 00:06:09,480 --> 00:06:10,206 >> AUDIENCE: Minus A. 159 00:06:10,206 --> 00:06:10,956 >> DAVID Malan: Ya. 160 00:06:10,956 --> 00:06:13,190 Jadi dikurangi A atau minus khusus 65 jika 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 sehingga akan memungkinkan kita untuk, sangat sederhana dan sangat deret hitung, 163 00:06:21,300 --> 00:06:23,260 menempatkan sesuatu ke dalam ember seperti itu. 164 00:06:23,260 --> 00:06:26,010 Jadi ternyata kita benar-benar melakukan ini juga bahkan dengan kuis. 165 00:06:26,010 --> 00:06:29,051 >> Jadi, Anda mungkin ingat Anda dilingkari Anda Nama mengajar sesama pada penutup. 166 00:06:29,051 --> 00:06:32,270 Dan nama TF yang terorganisir ke kolom ini abjad, 167 00:06:32,270 --> 00:06:34,400 baik, percaya atau tidak, ketika semua 80 plus kami 168 00:06:34,400 --> 00:06:37,800 berkumpul malam itu 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 [tidak terdengar] 170 00:06:41,830 --> 00:06:45,110 dan untuk meletakkan kuis semua orang keluar persis urutan TF mereka 171 00:06:45,110 --> 00:06:47,700 nama pada cover, karena maka itu jauh lebih mudah bagi kita 172 00:06:47,700 --> 00:06:51,290 untuk mencari melalui bahwa menggunakan linear pencarian atau semacam kepandaian 173 00:06:51,290 --> 00:06:54,050 untuk TF untuk menemukan atau kuis siswanya. 174 00:06:54,050 --> 00:06:56,060 >> Jadi ini ide hashing yang akan Anda lihat adalah 175 00:06:56,060 --> 00:07:00,520 cukup kuat sebenarnya cukup biasa dan sangat intuitif, 176 00:07:00,520 --> 00:07:03,000 seperti mungkin membagi dan Mendatuk berada di minggu nol. 177 00:07:03,000 --> 00:07:05,250 Saya maju cepat untuk hackathon yang beberapa tahun yang lalu. 178 00:07:05,250 --> 00:07:08,040 Ini adalah Zamyla dan beberapa siswa staf ucapan lainnya 179 00:07:08,040 --> 00:07:09,030 ketika mereka datang. 180 00:07:09,030 --> 00:07:12,680 Dan kami memiliki sejumlah besar lipat tabel ada dengan tag nama. 181 00:07:12,680 --> 00:07:15,380 Dan kami telah tag nama terorganisir dengan seperti As 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 salah satu TF sangat cerdik menulis ini sebagai petunjuk 184 00:07:20,350 --> 00:07:21,030 untuk hari. 185 00:07:21,030 --> 00:07:24,480 Dan dalam minggu ke-12 semester ini semua masuk akal dan semua orang 186 00:07:24,480 --> 00:07:25,310 tahu apa yang harus dilakukan. 187 00:07:25,310 --> 00:07:27,900 Tapi kapan saja Anda sudah antri dengan cara yang sama, 188 00:07:27,900 --> 00:07:30,272 Anda menerapkan gagasan yang sama hash. 189 00:07:30,272 --> 00:07:31,730 Jadi mari kita memformalkan itu sedikit. 190 00:07:31,730 --> 00:07:32,890 Berikut adalah array. 191 00:07:32,890 --> 00:07:36,820 Ini diambil untuk menjadi sedikit lebar hanya untuk menggambarkan, secara visual, 192 00:07:36,820 --> 00:07:38,920 bahwa kita mungkin menempatkan string dalam hal seperti ini. 193 00:07:38,920 --> 00:07:41,970 Dan array ini adalah jelas dari ukuran total 26. 194 00:07:41,970 --> 00:07:43,935 Dan hal ini disebut tabel sewenang-wenang. 195 00:07:43,935 --> 00:07:48,930 Tapi ini hanya rendition artis apa tabel hash mungkin. 196 00:07:48,930 --> 00:07:52,799 >> Jadi tabel hash sekarang akan menjadi lebih tinggi struktur data tingkat. 197 00:07:52,799 --> 00:07:54,840 Pada akhir hari kita akan melihat bahwa Anda 198 00:07:54,840 --> 00:07:58,700 dapat menerapkan tabel hash, yang jauh seperti garis check-in 199 00:07:58,700 --> 00:08:02,059 pada hackathon seperti ini tabel yang digunakan untuk menyortir buku ujian. 200 00:08:02,059 --> 00:08:03,850 Tapi tabel hash adalah semacam tingkat tinggi ini 201 00:08:03,850 --> 00:08:08,250 Konsep yang bisa menggunakan array di bawah tenda untuk menerapkannya, 202 00:08:08,250 --> 00:08:11,890 atau bisa menggunakan daftar panjang, atau bahkan mungkin beberapa struktur data lainnya. 203 00:08:11,890 --> 00:08:15,590 Dan sekarang itu pengambilan theme-- beberapa dari bahan dasar 204 00:08:15,590 --> 00:08:18,310 seperti array dan bangunan ini memblokir sekarang dari daftar panjang 205 00:08:18,310 --> 00:08:21,740 dan melihat apa lagi yang bisa kita membangun di atas mereka, seperti bahan 206 00:08:21,740 --> 00:08:26,550 menjadi resep, membuat semakin banyak hasil akhir yang menarik dan berguna. 207 00:08:26,550 --> 00:08:28,680 >> Jadi dengan tabel hash kita mungkin menerapkannya 208 00:08:28,680 --> 00:08:32,540 dalam memori pictorially seperti ini, tapi bagaimana mungkin itu benar-benar dikodekan up? 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 KAPASITAS di semua topi, hanya beberapa constant-- misalnya 26, 211 00:08:38,270 --> 00:08:42,030 untuk 26 surat alphabet-- yang Saya sebut meja variabel saya, 212 00:08:42,030 --> 00:08:45,630 dan aku mungkin mengklaim bahwa aku akan menempatkan bintang char dalam sana, atau tali. 213 00:08:45,630 --> 00:08:49,880 Jadi itu yang sederhana seperti ini jika Anda ingin menerapkan tabel hash. 214 00:08:49,880 --> 00:08:51,490 Namun, ini benar-benar hanya sebuah array. 215 00:08:51,490 --> 00:08:53,198 Tapi sekali lagi, hash tabel sekarang apa yang kita akan 216 00:08:53,198 --> 00:08:57,470 memanggil tipe data abstrak yang hanya semacam layering konseptual di atas 217 00:08:57,470 --> 00:09:00,780 sesuatu yang lebih biasa sekarang seperti sebuah array. 218 00:09:00,780 --> 00:09:02,960 >> Sekarang, bagaimana kita pergi tentang memecahkan masalah? 219 00:09:02,960 --> 00:09:06,980 Nah, sebelumnya aku punya kemewahan memiliki ruang meja yang cukup di sini 220 00:09:06,980 --> 00:09:09,460 sehingga saya bisa menempatkan kuis di mana saja yang saya inginkan. 221 00:09:09,460 --> 00:09:10,620 Jadi Seperti yang mungkin 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 Ms mungkin pergi di sini. 224 00:09:13,230 --> 00:09:14,740 Dan kemudian aku punya beberapa ruang tambahan. 225 00:09:14,740 --> 00:09:18,740 Tapi ini adalah sedikit dari hak contekan sekarang karena tabel ini, jika aku benar-benar 226 00:09:18,740 --> 00:09:22,720 menganggapnya sebagai sebuah array, hanya akan beberapa ukuran tetap. 227 00:09:22,720 --> 00:09:25,380 >> Jadi secara teknis, jika saya menarik up kuis lain siswa 228 00:09:25,380 --> 00:09:28,490 dan lihat, oh, orang ini namanya dimulai dengan A juga, 229 00:09:28,490 --> 00:09:30,980 Aku agak ingin menaruhnya di sana. 230 00:09:30,980 --> 00:09:34,740 Tapi begitu aku taruh di sana, jika tabel ini memang merupakan sebuah array, 231 00:09:34,740 --> 00:09:37,840 Aku akan meng-override atau clobbering siapa kuis ini siswa adalah. 232 00:09:37,840 --> 00:09:38,340 Benar? 233 00:09:38,340 --> 00:09:41,972 Jika ini adalah array, hanya satu hal dapat pergi di setiap sel-sel ini atau elemen. 234 00:09:41,972 --> 00:09:43,680 Dan jadi aku agak punya untuk memilih. 235 00:09:43,680 --> 00:09:45,735 >> Sekarang sebelumnya aku agak ditipu dan melakukan ini atau aku 236 00:09:45,735 --> 00:09:47,526 hanya jenis ditumpuk mereka di atas satu sama lain. 237 00:09:47,526 --> 00:09:49,170 Tapi itu tidak akan terbang dalam kode. 238 00:09:49,170 --> 00:09:52,260 Jadi di mana aku bisa meletakkan mahasiswa kedua yang namanya 239 00:09:52,260 --> 00:09:54,964 adalah A jika semua yang saya punya adalah ini tersedia ruang meja? 240 00:09:54,964 --> 00:09:57,880 Dan aku telah menggunakan tiga slot dan Sepertinya hanya ada beberapa orang lain. 241 00:09:57,880 --> 00:09:58,959 Apa yang bisa Anda lakukan? 242 00:09:58,959 --> 00:09:59,834 AUDIENCE: [tidak terdengar] 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 Benar? 247 00:10:02,660 --> 00:10:04,243 Ini tidak cocok di mana saya ingin menaruhnya. 248 00:10:04,243 --> 00:10:07,450 Jadi aku akan meletakkannya teknis di mana B akan pergi. 249 00:10:07,450 --> 00:10:09,932 Sekarang, tentu saja, aku mulai melukis diri ke sudut. 250 00:10:09,932 --> 00:10:11,890 Jika saya bisa mahasiswa yang namanya sebenarnya B, 251 00:10:11,890 --> 00:10:14,840 sekarang B akan dipindahkan sedikit maju, seperti yang mungkin terjadi, ya, 252 00:10:14,840 --> 00:10:17,530 jika ini adalah B, sekarang harus pergi di sini. 253 00:10:17,530 --> 00:10:20,180 >> Dan jadi ini sangat cepat bisa menjadi bermasalah, 254 00:10:20,180 --> 00:10:23,850 tapi teknik yang benar-benar disebut sebagai linear probing, 255 00:10:23,850 --> 00:10:26,650 dimana Anda hanya mempertimbangkan Anda array untuk menjadi sepanjang garis. 256 00:10:26,650 --> 00:10:29,680 Dan Anda hanya jenis menyelidiki atau memeriksa setiap elemen tersedia 257 00:10:29,680 --> 00:10:31,360 mencari tempat yang tersedia. 258 00:10:31,360 --> 00:10:34,010 Dan segera setelah Anda menemukan satu, Anda menaruhnya di sana. 259 00:10:34,010 --> 00:10:38,390 >> Sekarang, harga yang dibayar sekarang untuk solusi ini adalah apa? 260 00:10:38,390 --> 00:10:41,300 Kami memiliki ukuran array tetap, dan ketika saya menyisipkan nama 261 00:10:41,300 --> 00:10:44,059 ke dalamnya, paling tidak pada awalnya, apa waktu berjalan penyisipan 262 00:10:44,059 --> 00:10:46,350 untuk menempatkan siswa kuis di ember yang tepat? 263 00:10:46,350 --> 00:10:48,710 264 00:10:48,710 --> 00:10:50,002 Big O apa? 265 00:10:50,002 --> 00:10:51,147 >> AUDIENCE: 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 menggoda terpisah mengapa hanya dalam beberapa saat. 270 00:10:56,490 --> 00:10:57,702 Apa lagi mungkin itu? 271 00:10:57,702 --> 00:10:58,755 >> AUDIENCE: [tidak terdengar] 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 huruf S. 274 00:11:04,720 --> 00:11:05,604 >> AUDIENCE: Itu salah satu. 275 00:11:05,604 --> 00:11:06,520 DAVID Malan: Itu salah satu. 276 00:11:06,520 --> 00:11:06,710 Benar? 277 00:11:06,710 --> 00:11:08,950 Ini adalah array, yang berarti kita memiliki akses random. 278 00:11:08,950 --> 00:11:11,790 Dan jika kita berpikir tentang hal ini sebagai nol dan ini sebagai 25, 279 00:11:11,790 --> 00:11:13,800 dan kami menyadari bahwa, oh, inilah saya masukan S, 280 00:11:13,800 --> 00:11:16,350 Saya pasti dapat mengkonversi S, karakter ASCII, 281 00:11:16,350 --> 00:11:18,540 ke angka yang sesuai antara nol dan 25 282 00:11:18,540 --> 00:11:20,910 dan kemudian segera meletakkannya di tempatnya. 283 00:11:20,910 --> 00:11:26,120 >> Tapi tentu saja, segera setelah 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 probing sebagai solusi saya, 285 00:11:29,300 --> 00:11:31,360 waktu berjalan dari penyisipan dalam kasus terburuk 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 benar sejak dini. 289 00:11:36,045 --> 00:11:36,920 AUDIENCE: [tidak terdengar] 290 00:11:36,920 --> 00:11:41,620 DAVID Malan: Jadi n memang sekali Anda memiliki satu set data yang cukup besar. 291 00:11:41,620 --> 00:11:44,410 Jadi, di satu sisi, jika array cukup besar 292 00:11:44,410 --> 00:11:48,287 dan data Anda jarang cukup, Anda mendapatkan ini waktu konstan yang indah. 293 00:11:48,287 --> 00:11:50,620 Tapi begitu Anda mulai semakin elemen, 294 00:11:50,620 --> 00:11:53,200 dan hanya statistik Anda mendapatkan lebih banyak orang dengan huruf 295 00:11:53,200 --> 00:11:56,030 A sebagai nama mereka atau huruf B, itu bisa berpotensi 296 00:11:56,030 --> 00:11:57,900 berpindah ke sesuatu yang lebih linier. 297 00:11:57,900 --> 00:11:59,640 Jadi tidak cukup sempurna. 298 00:11:59,640 --> 00:12:00,690 Jadi kita bisa berbuat lebih baik? 299 00:12:00,690 --> 00:12:03,210 >> Nah, apa yang kami solusi sebelumnya ketika kita 300 00:12:03,210 --> 00:12:06,820 ingin memiliki lebih dinamisme dari sesuatu seperti sebuah array diperbolehkan? 301 00:12:06,820 --> 00:12:08,085 302 00:12:08,085 --> 00:12:08,960 AUDIENCE: [tidak terdengar] 303 00:12:08,960 --> 00:12:10,030 DAVID Malan: Apa yang kami memperkenalkan? 304 00:12:10,030 --> 00:12:10,530 Ya. 305 00:12:10,530 --> 00:12:11,430 Jadi sebuah linked list. 306 00:12:11,430 --> 00:12:14,430 Nah, mari kita lihat apa yang terkait daftar mungkin lakukan untuk kita sebagai gantinya. 307 00:12:14,430 --> 00:12:17,630 Nah, biarkan aku mengusulkan kita bahwa menggambar gambar sebagai berikut. 308 00:12:17,630 --> 00:12:19,620 Sekarang ini adalah berbeda gambar dari contoh 309 00:12:19,620 --> 00:12:24,750 dari teks yang berbeda, sebenarnya, bahwa sebenarnya menggunakan sebuah array dari ukuran 31. 310 00:12:24,750 --> 00:12:28,220 Dan penulis ini hanya memutuskan untuk hash string 311 00:12:28,220 --> 00:12:32,430 tidak didasarkan pada nama-nama orang tersebut, namun berdasarkan tanggal lahir mereka. 312 00:12:32,430 --> 00:12:35,680 Terlepas dari bulan, mereka pikir jika Anda lahir pada hari pertama dari bulan 313 00:12:35,680 --> 00:12:39,580 atau 31 bulan, penulis akan hash berdasarkan nilai tersebut, 314 00:12:39,580 --> 00:12:44,154 sehingga untuk menyebarkan nama-nama keluar sedikit lebih dari sekedar 26 spot mungkin mengizinkan. 315 00:12:44,154 --> 00:12:47,320 Dan mungkin itu adalah lebih seragam sedikit daripada pergi dengan huruf abjad, 316 00:12:47,320 --> 00:12:50,236 karena tentu saja mungkin ada lebih banyak orang di dunia dengan nama 317 00:12:50,236 --> 00:12:54,020 yang mulai dengan A daripada tentu beberapa surat lainnya dari alfabet. 318 00:12:54,020 --> 00:12:56,380 Jadi mungkin ini sedikit lebih seragam, dengan asumsi 319 00:12:56,380 --> 00:12:58,640 distribusi seragam bayi di bulan. 320 00:12:58,640 --> 00:12:59,990 >> Tapi, tentu saja, ini masih tidak sempurna. 321 00:12:59,990 --> 00:13:00,370 Benar? 322 00:13:00,370 --> 00:13:01,370 Kami mengalami tabrakan. 323 00:13:01,370 --> 00:13:04,680 Beberapa orang di ini struktur data masih 324 00:13:04,680 --> 00:13:08,432 memiliki tanggal lahir yang sama setidaknya Anda terlepas dari bulan. 325 00:13:08,432 --> 00:13:09,640 Tapi apa yang telah penulis lakukan? 326 00:13:09,640 --> 00:13:13,427 Yah, sepertinya kita memiliki sebuah array di sisi kiri ditarik secara vertikal, 327 00:13:13,427 --> 00:13:15,010 tapi itu hanya rendition seorang seniman. 328 00:13:15,010 --> 00:13:18,009 Tidak peduli apa arah Anda menggambar sebuah array, itu masih sebuah array. 329 00:13:18,009 --> 00:13:20,225 Apa ini sebuah array rupanya? 330 00:13:20,225 --> 00:13:21,500 >> AUDIENCE: Daftar Linked. 331 00:13:21,500 --> 00:13:21,650 >> DAVID Malan: Ya. 332 00:13:21,650 --> 00:13:23,490 Sepertinya itu adalah array linked list. 333 00:13:23,490 --> 00:13:26,490 Jadi sekali lagi, ke titik ini semacam menggunakan struktur data ini sekarang 334 00:13:26,490 --> 00:13:28,550 sebagai bahan untuk lebih solusi yang menarik, 335 00:13:28,550 --> 00:13:30,862 Anda benar-benar dapat mengambil mendasar, seperti sebuah array, 336 00:13:30,862 --> 00:13:33,320 dan kemudian mengambil sesuatu yang lebih menarik seperti linked list 337 00:13:33,320 --> 00:13:36,660 dan bahkan menggabungkan mereka ke dalam bahkan struktur data yang lebih menarik. 338 00:13:36,660 --> 00:13:39,630 Dan memang, ini juga akan disebut tabel hash, 339 00:13:39,630 --> 00:13:42,610 dimana array adalah benar-benar tabel hash, 340 00:13:42,610 --> 00:13:45,600 tapi itu tabel hash memiliki rantai, sehingga untuk berbicara, 341 00:13:45,600 --> 00:13:50,220 yang dapat tumbuh atau menyusut berdasarkan jumlah elemen yang ingin Anda masukkan. 342 00:13:50,220 --> 00:13:52,990 >> Sekarang, oleh karena itu, apa yang sekarang waktu berjalan? 343 00:13:52,990 --> 00:13:58,030 Jika saya ingin memasukkan seseorang yang berulang tahun tanggal 31 Oktober 344 00:13:58,030 --> 00:13:59,040 mana dia 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 bagian 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 waktu yang konstan. 350 00:14:05,060 --> 00:14:08,760 Tapi bagaimana kalau kita menemukan orang lain yang ulang tahun adalah, mari kita lihat, 351 00:14:08,760 --> 00:14:10,950 Oktober, November, Desember 31? 352 00:14:10,950 --> 00:14:12,790 Dimanakah 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 sekalipun. 355 00:14:13,970 --> 00:14:15,303 Itu konstan meskipun 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 saat itu. 359 00:14:17,840 --> 00:14:20,570 Tetapi dalam kasus umum, semakin banyak orang kita tambahkan, 360 00:14:20,570 --> 00:14:23,790 probabilistically, kita akan untuk mendapatkan lebih banyak dan lebih banyak tabrakan. 361 00:14:23,790 --> 00:14:26,820 >> Sekarang ini sedikit lebih baik karena secara teknis 362 00:14:26,820 --> 00:14:34,580 sekarang rantai saya bisa di kasus 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 kasus terburuk itu akan menjadi n. 365 00:14:41,080 --> 00:14:41,815 Mengapa? 366 00:14:41,815 --> 00:14:43,332 >> AUDIENCE: Karena jika semua orang memiliki ulang tahun 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 Ini mungkin sedikit dibikin, tapi benar-benar dalam kasus terburuk, 370 00:14:47,480 --> 00:14:50,117 jika setiap orang memiliki ulang tahun yang sama, diberikan input yang Anda miliki, 371 00:14:50,117 --> 00:14:51,950 Anda akan memiliki rantai besar-besaran panjang. 372 00:14:51,950 --> 00:14:54,241 Dan, Anda bisa menyebutnya hash table, tapi benar-benar 373 00:14:54,241 --> 00:14:56,810 hanya linked list besar dengan seluruh banyak ruang kosong. 374 00:14:56,810 --> 00:15:00,460 Tapi secara umum, jika kita mengasumsikan bahwa setidaknya ulang tahun yang uniform-- 375 00:15:00,460 --> 00:15:01,750 dan mungkin tidak. 376 00:15:01,750 --> 00:15:02,587 Aku membuat bahwa sampai. 377 00:15:02,587 --> 00:15:04,420 Tetapi jika kita berasumsi, untuk kepentingan diskusi 378 00:15:04,420 --> 00:15:07,717 bahwa mereka, maka secara teori, jika ini adalah representasi vertikal 379 00:15:07,717 --> 00:15:11,050 dari array, baik maka mudah-mudahan Anda akan mendapatkan rantai yang, Anda tahu, 380 00:15:11,050 --> 00:15:15,880 panjang kurang lebih sama di mana masing-masing ini merupakan hari bulan. 381 00:15:15,880 --> 00:15:19,930 >> Sekarang jika ada 31 hari dalam sebulan, yang berarti waktu berjalan saya 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 Tapi apa yang salah dari kami komitmen beberapa minggu 384 00:15:27,950 --> 00:15:31,145 lalu setiap kali datang untuk mengekspresikan waktu berjalan dari algoritma? 385 00:15:31,145 --> 00:15:33,450 386 00:15:33,450 --> 00:15:35,190 Hanya saja melihat istilah urutan tinggi. 387 00:15:35,190 --> 00:15:35,690 Benar? 388 00:15:35,690 --> 00:15:37,400 31 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 Tapi salah satu tema masalah set lima 391 00:15:41,730 --> 00:15:43,950 akan menjadi ke mengakui bahwa benar-benar, 392 00:15:43,950 --> 00:15:47,320 asimtotik, secara teoritis struktur data 393 00:15:47,320 --> 00:15:50,470 tidak lebih baik dari sekedar satu linked list besar. 394 00:15:50,470 --> 00:15:53,550 Dan memang, dalam kasus terburuk, ini tabel hash mungkin berpindah ke dalam. 395 00:15:53,550 --> 00:15:57,620 >> Tapi di dunia nyata, dengan kita manusia yang sendiri Mac atau PC atau apa pun 396 00:15:57,620 --> 00:16:01,240 dan menjalankan dunia nyata perangkat lunak data dunia nyata, 397 00:16:01,240 --> 00:16:03,260 yang algoritma yang akan Anda sukai? 398 00:16:03,260 --> 00:16:09,180 Salah satu yang mengambil langkah akhir atau salah satu yang memakan waktu n dibagi dengan 31 langkah 399 00:16:09,180 --> 00:16:12,900 untuk menemukan beberapa bagian dari data atau untuk mencari beberapa informasi? 400 00:16:12,900 --> 00:16:16,580 Maksudku, benar-benar 31 merek perbedaan di dunia nyata. 401 00:16:16,580 --> 00:16:18,540 Ini 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 menyadari dikotomi ada antara benar-benar 404 00:16:23,004 --> 00:16:25,920 berbicara tentang hal-hal yang secara teoritis dan asimtotik yang pasti 405 00:16:25,920 --> 00:16:28,760 memiliki nilai seperti yang kita lihat, tapi di dunia nyata, 406 00:16:28,760 --> 00:16:32,930 jika Anda peduli tentang hanya membuat senang manusia untuk input umum, 407 00:16:32,930 --> 00:16:36,010 Anda mungkin sangat baik ingin menerima fakta bahwa, ya, ini adalah linear, 408 00:16:36,010 --> 00:16:38,360 tapi itu 31 kali lebih cepat linear mungkin. 409 00:16:38,360 --> 00:16:41,610 Dan lebih baik lagi, kita tidak hanya harus melakukan sesuatu sewenang-wenang seperti tanggal lahir seorang, 410 00:16:41,610 --> 00:16:44,030 kita bisa menghabiskan sedikit lebih banyak waktu dan kepandaian 411 00:16:44,030 --> 00:16:47,140 dan berpikir tentang apa yang bisa kita lakukan, diberi nama seseorang dan mungkin 412 00:16:47,140 --> 00:16:50,130 tanggal lahir mereka untuk menggabungkan mereka 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 sehingga untuk berbicara daripada gambar ini saat ini menunjukkan mungkin. 415 00:16:56,250 --> 00:16:57,750 Bagaimana kita bisa menerapkan ini dalam kode? 416 00:16:57,750 --> 00:17:00,280 Nah, biarkan aku mengusulkan kita bahwa hanya meminjam beberapa sintaks kita sudah 417 00:17:00,280 --> 00:17:01,799 digunakan beberapa kali sejauh ini. 418 00:17:01,799 --> 00:17:03,590 Dan aku akan menentukan node, yang lagi-lagi 419 00:17:03,590 --> 00:17:06,812 adalah istilah umum untuk hanya beberapa wadah untuk beberapa struktur data. 420 00:17:06,812 --> 00:17:09,020 Aku akan mengusulkan bahwa string akan di sana. 421 00:17:09,020 --> 00:17:11,369 Tapi kita akan mulai mengambil mereka pelatihan roda off sekarang. 422 00:17:11,369 --> 00:17:13,230 >> Tidak ada lagi CS50 perpustakaan benar-benar, kecuali jika Anda ingin 423 00:17:13,230 --> 00:17:15,230 menggunakannya untuk akhir Anda Proyek, yang baik-baik saja, 424 00:17:15,230 --> 00:17:18,569 tapi sekarang kita akan menarik kembali tirai dan mengatakan itu hanya bintang arang. 425 00:17:18,569 --> 00:17:22,069 Jadi kata ada akan menjadi nama orang yang bersangkutan. 426 00:17:22,069 --> 00:17:25,079 Dan sekarang aku punya link di sini untuk node berikutnya 427 00:17:25,079 --> 00:17:28,170 sehingga ini mewakili masing-masing node 428 00:17:28,170 --> 00:17:30,950 dalam rantai, berpotensi, dari linked list. 429 00:17:30,950 --> 00:17:34,090 >> Dan sekarang bagaimana cara mendeklarasikan tabel hash itu sendiri? 430 00:17:34,090 --> 00:17:36,660 Bagaimana cara mendeklarasikan seluruh struktur ini? 431 00:17:36,660 --> 00:17:40,960 Nah, benar-benar, seperti saya menggunakan pointer hanya elemen pertama dari daftar 432 00:17:40,960 --> 00:17:44,510 sebelumnya, sama bisa saya katakan Aku hanya perlu sekelompok pointer 433 00:17:44,510 --> 00:17:46,270 untuk menerapkan tabel ini hash keseluruhan. 434 00:17:46,270 --> 00:17:49,484 Aku akan memiliki sebuah array disebut meja untuk tabel hash. 435 00:17:49,484 --> 00:17:50,900 Ini akan menjadi ukuran kapasitas. 436 00:17:50,900 --> 00:17:52,525 Itu berapa banyak elemen bisa muat di dalamnya. 437 00:17:52,525 --> 00:17:56,180 Dan masing-masing elemen dalam hal ini array akan menjadi bintang simpul. 438 00:17:56,180 --> 00:17:56,810 Mengapa? 439 00:17:56,810 --> 00:18:00,160 Nah, per gambar ini, apa yang saya menerapkan tabel hash sebagai 440 00:18:00,160 --> 00:18:04,330 efektif pada awalnya hanya array ini bahwa kita telah ditarik secara vertikal, 441 00:18:04,330 --> 00:18:06,820 masing-masing kotak yang merupakan pointer. 442 00:18:06,820 --> 00:18:09,170 Bahwa orang yang memiliki garis miring melalui mereka hanya nol. 443 00:18:09,170 --> 00:18:11,410 Dan orang-orang yang memiliki panah akan ke kanan 444 00:18:11,410 --> 00:18:16,140 pointer sebenarnya untuk node yang sebenarnya, ergo awal dari linked list. 445 00:18:16,140 --> 00:18:19,050 >> Jadi di sini, kemudian, adalah bagaimana kita mungkin menerapkan tabel hash yang 446 00:18:19,050 --> 00:18:21,580 mengimplementasikan chaining terpisah. 447 00:18:21,580 --> 00:18:22,840 Sekarang kita bisa berbuat lebih baik? 448 00:18:22,840 --> 00:18:25,632 Baiklah saya berjanji terakhir kali kita bisa mencapai waktu konstan. 449 00:18:25,632 --> 00:18:27,381 Dan aku agak memberi Anda waktu yang konstan di sini, 450 00:18:27,381 --> 00:18:29,850 tapi kemudian mengatakan tidak benar-benar konstanta waktu karena masih 451 00:18:29,850 --> 00:18:31,890 tergantung pada total jumlah 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 Tapi bagaimana kalau kita melakukan hal ini. 454 00:18:35,980 --> 00:18:39,550 Biarkan aku pergi kembali ke layar di sini. 455 00:18:39,550 --> 00:18:44,520 Saya juga memproyeksikan ini di sini, jelas layar, dan kira saya melakukan ini. 456 00:18:44,520 --> 00:18:49,300 Misalkan saya ingin memasukkan nama Daven di dalam struktur data saya. 457 00:18:49,300 --> 00:18:52,100 >> Jadi saya ingin menyisipkan string Daven ke dalam struktur data. 458 00:18:52,100 --> 00:18:54,370 Bagaimana jika saya tidak menggunakan hash table, tapi 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 memiliki 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 Misalkan saat itu, bahwa saya ingin memasukkan Daven ini 463 00:19:04,450 --> 00:19:06,430 menjadi apa yang saat ini daftar kosong. 464 00:19:06,430 --> 00:19:09,780 Aku akan melakukan hal berikut: Aku akan membuat simpul di keluarga ini 465 00:19:09,780 --> 00:19:15,170 seperti pohon struktur data yang terlihat sedikit seperti ini, masing-masing 466 00:19:15,170 --> 00:19:19,640 persegi panjang telah, katakanlah, untuk saat ini 26 elemen di dalamnya. 467 00:19:19,640 --> 00:19:21,650 Dan masing-masing sel dalam array ini akan 468 00:19:21,650 --> 00:19:23,470 untuk mewakili huruf dari alfabet. 469 00:19:23,470 --> 00:19:28,190 >> Secara khusus, aku akan mengobati 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 efektif mewakili huruf D. 472 00:19:32,940 --> 00:19:36,040 Tetapi untuk memasukkan semua Daven ini nama saya perlu melakukan sedikit lebih. 473 00:19:36,040 --> 00:19:37,840 Jadi aku pertama akan hash, sehingga untuk berbicara. 474 00:19:37,840 --> 00:19:41,049 Aku akan melihat huruf pertama di Daven ini yang jelas D, 475 00:19:41,049 --> 00:19:42,840 dan aku akan mengalokasikan node yang terlihat 476 00:19:42,840 --> 00:19:45,570 seperti this-- persegi panjang besar besar cukup untuk memenuhi seluruh alfabet. 477 00:19:45,570 --> 00:19:47,140 >> Sekarang D dilakukan. 478 00:19:47,140 --> 00:19:49,720 Sekarang 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 Segera setelah saya mulai pemberitahuan D tidak ada pointer di sana. 481 00:19:54,027 --> 00:19:56,860 Ini nilai sampah saat ini, atau aku mungkin menginisialisasi ke null. 482 00:19:56,860 --> 00:19:59,630 Tapi biarkan aku terus berjalan dengan ide ini membangun pohon. 483 00:19:59,630 --> 00:20:04,260 Mari saya mengalokasikan salah satu dari ini node yang memiliki 26 elemen di dalamnya. 484 00:20:04,260 --> 00:20:05,150 >> Dan kau tahu apa? 485 00:20:05,150 --> 00:20:09,130 Jika ini hanyalah sebuah node dalam memori yang Saya buat dengan malloc, menggunakan struct 486 00:20:09,130 --> 00:20:11,240 karena kami akan segera melihat, Aku akan melakukan this-- 487 00:20:11,240 --> 00:20:14,450 Aku akan menggambar panah dari hal yang diwakili D turun 488 00:20:14,450 --> 00:20:15,860 untuk node baru ini. 489 00:20:15,860 --> 00:20:19,240 Dan sekarang, pertama berikutnya huruf di nama Daven ini, 490 00:20:19,240 --> 00:20:24,150 V-- D-A-V-- Aku akan pergi ke depan dan menarik node lain seperti ini, 491 00:20:24,150 --> 00:20:30,150 dimana, elemen V di sini, yang kami akan menarik untuk whoops 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 Itu akan pergi di sini. 494 00:20:31,936 --> 00:20:32,890 495 00:20:32,890 --> 00:20:35,712 >> Maka 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 ke dalam apa yang akan kita pertimbangkan E. 497 00:20:44,920 --> 00:20:50,100 Dan kemudian dari sini kita akan pergi memiliki satu node ini di sini. 498 00:20:50,100 --> 00:20:52,930 Dan sekarang kita memiliki pertanyaan untuk menjawab. 499 00:20:52,930 --> 00:20:57,840 Saya perlu entah bagaimana menunjukkan bahwa kita berada di akhir string Daven. 500 00:20:57,840 --> 00:20:59,490 Jadi saya hanya bisa meninggalkannya null. 501 00:20:59,490 --> 00:21:02,670 >> Tapi bagaimana jika kita memiliki Daven ini nama lengkap 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 bagaimana jika Daven adalah sebenarnya substring, 504 00:21:06,970 --> 00:21:08,960 awalan string lebih lama? 505 00:21:08,960 --> 00:21:11,450 Kita tidak bisa hanya secara permanen mengatakan apa-apa yang terjadi 506 00:21:11,450 --> 00:21:14,410 untuk pergi ke sana, karena kita bisa tidak pernah memasukkan kata seperti Davenport 507 00:21:14,410 --> 00:21:15,840 ke ini Struktur Data 508 00:21:15,840 --> 00:21:19,560 >> Jadi apa yang bisa kita lakukan sebagai gantinya adalah memperlakukan masing-masing elemen 509 00:21:19,560 --> 00:21:22,170 sebagai mungkin memiliki dua unsur dalam diri mereka. 510 00:21:22,170 --> 00:21:24,810 Salah satunya adalah pointer, memang, seperti yang telah saya lakukan. 511 00:21:24,810 --> 00:21:27,100 Jadi masing-masing kotak-kotak ini bukan hanya satu sel. 512 00:21:27,100 --> 00:21:29,855 Tapi bagaimana kalau atas satu-- bawah seseorang 513 00:21:29,855 --> 00:21:32,230 akan menjadi nol, karena tidak ada Davenport dulu. 514 00:21:32,230 --> 00:21:34,197 Bagaimana jika orang yang top beberapa nilai khusus? 515 00:21:34,197 --> 00:21:36,530 Dan itu akan menjadi sedikit sulit untuk menggambar ukuran ini. 516 00:21:36,530 --> 00:21:38,130 Tapi rasa itu hanya tanda centang. 517 00:21:38,130 --> 00:21:38,920 Periksa. 518 00:21:38,920 --> 00:21:44,230 D-A-V-E-N adalah string dalam struktur data. 519 00:21:44,230 --> 00:21:48,350 >> Sementara itu, jika saya memiliki lebih banyak ruang di sini, aku bisa melakukan P-O-R-T, 520 00:21:48,350 --> 00:21:52,650 dan saya bisa menempatkan cek di node yang memiliki huruf T di akhir. 521 00:21:52,650 --> 00:21:55,460 Jadi ini adalah besar-besaran Kompleks tampak 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 Tapi jika saya ingin memasukkan sesuatu lain, pertimbangkan apa yang akan kita lakukan. 524 00:22:00,043 --> 00:22:03,370 Jika kita ingin menempatkan David in, kami akan mengikuti logika yang sama, D-A-V, 525 00:22:03,370 --> 00:22:08,802 tapi sekarang saya akan menunjukkan di depan elemen tidak dari E, tapi dari saya ke D. 526 00:22:08,802 --> 00:22:10,760 Jadi ada akan menjadi node lainnya di pohon ini. 527 00:22:10,760 --> 00:22:12,325 Kita akan memiliki panggilan malloc lagi. 528 00:22:12,325 --> 00:22:14,700 Tapi aku tidak ingin membuat berantakan lengkap gambar ini. 529 00:22:14,700 --> 00:22:17,710 Jadi mari kita malah melihat salah satu yang telah pra-dirumuskan 530 00:22:17,710 --> 00:22:21,810 seperti ini dengan tidak dot, dot, titik, tapi array hanya disingkat. 531 00:22:21,810 --> 00:22:23,950 Tetapi masing-masing dari node di pohon ini di sini 532 00:22:23,950 --> 00:22:26,700 mewakili thing-- sama array Ray ukuran 26. 533 00:22:26,700 --> 00:22:28,860 >> Atau jika kita ingin menjadi benar-benar tepat sekarang, apa 534 00:22:28,860 --> 00:22:30,790 jika nama seseorang sebagai apostrof, mari kita 535 00:22:30,790 --> 00:22:35,560 mengasumsikan bahwa setiap node sebenarnya memiliki seperti 27 indeks di dalamnya, bukan hanya 26. 536 00:22:35,560 --> 00:22:42,020 Jadi sekarang ini akan menjadi data struktur disebut trie-- T-R-I-E. 537 00:22:42,020 --> 00:22:46,120 Sebuah trie, yang diduga historis nama pintar untuk pohon 538 00:22:46,120 --> 00:22:49,040 yang dioptimalkan untuk pengambilan, yang tentu saja, 539 00:22:49,040 --> 00:22:50,870 dieja dengan I-E sehingga trie. 540 00:22:50,870 --> 00:22:52,710 Tapi itu adalah sejarah trie. 541 00:22:52,710 --> 00:22:55,860 >> Jadi trie data seperti pohon ini struktur seperti pohon keluarga 542 00:22:55,860 --> 00:22:57,510 yang pada akhirnya berperilaku seperti itu. 543 00:22:57,510 --> 00:23:00,890 Dan di sini hanyalah contoh lain dari Seluruh sekelompok nama orang lain. 544 00:23:00,890 --> 00:23:03,540 Tetapi pertanyaan sekarang di tangan adalah apa yang harus 545 00:23:03,540 --> 00:23:08,070 kami memperoleh dengan memperkenalkan dibilang 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 >> Karena meskipun, pada saat ini, aku hanya 548 00:23:11,703 --> 00:23:15,050 menggunakan D's pointer dan A dan V dan Es dan Ns, 549 00:23:15,050 --> 00:23:16,700 Aku membuang-buang heck of banyak memori. 550 00:23:16,700 --> 00:23:18,030 551 00:23:18,030 --> 00:23:22,660 Tapi di mana saya menghabiskan satu sumber daya, Saya cenderung untuk melakukan mendapatkan kembali lain. 552 00:23:22,660 --> 00:23:26,020 Jadi jika saya menghabiskan lebih banyak ruang, apa mungkin harapan? 553 00:23:26,020 --> 00:23:27,407 Bahwa aku menghabiskan kurang apa? 554 00:23:27,407 --> 00:23:28,240 AUDIENCE: Kurang waktu. 555 00:23:28,240 --> 00:23:28,990 DAVID Malan: Time. 556 00:23:28,990 --> 00:23:30,320 Sekarang mengapa mungkin itu? 557 00:23:30,320 --> 00:23:33,880 Nah, apa penyisipan waktu, dalam hal O besar sekarang, 558 00:23:33,880 --> 00:23:37,660 dari nama seperti Daven atau Davenport atau David? 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, sehingga akan langkah beberapa lagi. 561 00:23:42,350 --> 00:23:44,250 David akan menjadi lima langkah juga. 562 00:23:44,250 --> 00:23:47,230 Jadi mereka adalah beton angka, tapi pasti ada 563 00:23:47,230 --> 00:23:49,550 atas terikat 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 mengusulkan bahwa itu sesuatu 566 00:23:54,050 --> 00:23:55,470 itulah karakter 40-beberapa-aneh. 567 00:23:55,470 --> 00:23:58,180 >> Realistis, tidak ada yang memiliki nama panjang tak terhingga, 568 00:23:58,180 --> 00:24:01,542 yang berarti bahwa panjang dari nama atau panjang string kita mungkin 569 00:24:01,542 --> 00:24:03,750 memiliki beberapa keadaan Struktur ini bisa dibilang apa? 570 00:24:03,750 --> 00:24:05,550 571 00:24:05,550 --> 00:24:06,250 Ini konstan. 572 00:24:06,250 --> 00:24:06,430 Benar? 573 00:24:06,430 --> 00:24:09,310 Mungkin konstan besar seperti 40-sesuatu, tapi itu adalah konstan. 574 00:24:09,310 --> 00:24:13,752 Dan tidak memiliki ketergantungan pada berapa banyak Nama-nama lain dalam struktur data. 575 00:24:13,752 --> 00:24:15,460 Dengan kata lain, jika saya ingin sekarang memasukkan 576 00:24:15,460 --> 00:24:20,540 Colton atau Gabriel atau Rob atau Zamyla atau Alison atau Belinda atau nama lain 577 00:24:20,540 --> 00:24:23,940 dari staf menjadi data ini struktur, adalah waktu yang berjalan 578 00:24:23,940 --> 00:24:26,750 memasukkan nama lain akan sama sekali terkena dampak 579 00:24:26,750 --> 00:24:30,220 oleh berapa banyak elemen lain yang dalam struktur data yang telah? 580 00:24:30,220 --> 00:24:31,040 Hal ini tidak. 581 00:24:31,040 --> 00:24:31,540 Benar? 582 00:24:31,540 --> 00:24:36,150 Karena kita secara efektif menggunakan tabel hash multi-layer. 583 00:24:36,150 --> 00:24:38,280 Dan waktu berjalan dari salah satu operasi ini 584 00:24:38,280 --> 00:24:41,510 tergantung bukan pada jumlah elemen yang berada di struktur data 585 00:24:41,510 --> 00:24:43,090 atau yang pada akhirnya akan berada di 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 >> String yang dimasukkan, yang tidak membuat 589 00:24:49,200 --> 00:24:52,580 ini asimtotik konstan time-- O besar satu. 590 00:24:52,580 --> 00:24:54,720 Dan terus terang, hanya dalam dunia nyata, ini 591 00:24:54,720 --> 00:24:58,380 berarti memasukkan nama Daven ini membawa seperti lima langkah, atau Davenport sembilan 592 00:24:58,380 --> 00:25:00,100 langkah, atau David lima langkah. 593 00:25:00,100 --> 00:25:03,071 Itu pretty darn kali berjalan kecil. 594 00:25:03,071 --> 00:25:05,320 Dan, memang, itu sangat hal yang baik, terutama ketika 595 00:25:05,320 --> 00:25:08,126 itu tidak tergantung pada total jumlah elemen dalam sana. 596 00:25:08,126 --> 00:25:10,500 Jadi bagaimana mungkin kita menerapkan ini jenis struktur dalam kode? 597 00:25:10,500 --> 00:25:12,900 Ini sedikit lebih kompleks, tapi tetap saja 598 00:25:12,900 --> 00:25:15,050 hanya aplikasi blok bangunan dasar. 599 00:25:15,050 --> 00:25:17,830 Aku akan mendefinisikan kembali kita simpul sebagai berikut: 600 00:25:17,830 --> 00:25:21,100 bool disebut word-- dan ini bisa disebut apa-apa. 601 00:25:21,100 --> 00:25:23,970 Tapi bool merupakan apa yang saya menarik sebagai tanda centang. 602 00:25:23,970 --> 00:25:24,490 Ya. 603 00:25:24,490 --> 00:25:26,720 Ini adalah akhir dari string dalam struktur data. 604 00:25:26,720 --> 00:25:30,702 >> Dan, tentu saja, bintang simpul ada adalah mengacu pada anak-anak. 605 00:25:30,702 --> 00:25:32,410 Dan, memang, sama seperti pohon keluarga, Anda 606 00:25:32,410 --> 00:25:34,370 akan mempertimbangkan node yang menggantung 607 00:25:34,370 --> 00:25:36,920 dari bagian bawah beberapa orangtua elemen untuk menjadi anak-anak. 608 00:25:36,920 --> 00:25:40,510 Dan anak-anak akan menjadi sebuah array dari 27, yang 27 609 00:25:40,510 --> 00:25:41,680 hanya menjadi untuk tanda kutip. 610 00:25:41,680 --> 00:25:43,390 Kita akan memilah kasus khusus yang. 611 00:25:43,390 --> 00:25:45,400 Sehingga Anda dapat memiliki tertentu nama dengan apostrof. 612 00:25:45,400 --> 00:25:47,399 Mungkin bahkan tanda hubung harus masuk ke sana, tapi Anda akan 613 00:25:47,399 --> 00:25:50,330 lihat dalam p set 5 kita hanya perawatan tentang surat dan apostrof. 614 00:25:50,330 --> 00:25:52,990 >> Dan kemudian bagaimana Anda mewakili struktur data itu sendiri? 615 00:25:52,990 --> 00:25:56,454 Bagaimana Anda mewakili akar dari trie ini, sehingga untuk berbicara? 616 00:25:56,454 --> 00:25:59,620 Nah, sama seperti dengan linked list, Anda membutuhkan pointer ke elemen pertama. 617 00:25:59,620 --> 00:26:04,270 Dengan trie Anda hanya perlu satu pointer ke akar trie ini. 618 00:26:04,270 --> 00:26:07,290 Dan dari sana Anda dapat hash jalan turun lebih dalam dan lebih 619 00:26:07,290 --> 00:26:10,460 ke setiap node lain dalam struktur. 620 00:26:10,460 --> 00:26:13,440 Jadi hanya dengan kaleng ini kami mewakili struct itu. 621 00:26:13,440 --> 00:26:15,877 >> Sekarang Meanwhile-- Oh, pertanyaan. 622 00:26:15,877 --> 00:26:17,220 >> AUDIENCE: Apa kata bool? 623 00:26:17,220 --> 00:26:20,490 >> DAVID Malan: Kata Bool adalah hanya inkarnasi C ini 624 00:26:20,490 --> 00:26:22,920 dari apa yang saya jelaskan dalam kotak ini di sini, ketika 625 00:26:22,920 --> 00:26:26,000 Aku mulai membelah masing-masing elemen array menjadi dua bagian. 626 00:26:26,000 --> 00:26:27,600 Salah satunya adalah pointer ke node berikutnya. 627 00:26:27,600 --> 00:26:30,280 Yang lain harus sesuatu seperti kotak centang 628 00:26:30,280 --> 00:26:33,770 untuk mengatakan ya, ada kata Daven yang berakhir di sini, 629 00:26:33,770 --> 00:26:35,610 karena kita tidak ingin, pada saat, Dave. 630 00:26:35,610 --> 00:26:39,320 >> Meskipun Dave akan menjadi Kata yang sah, dia tidak dalam trie 631 00:26:39,320 --> 00:26:39,830 Belum. 632 00:26:39,830 --> 00:26:40,950 Dan D tidak sepatah kata pun. 633 00:26:40,950 --> 00:26:42,770 Dan D-A bukanlah sebuah kata atau nama. 634 00:26:42,770 --> 00:26:45,020 Jadi tanda centang menunjukkan hanya sekali Anda 635 00:26:45,020 --> 00:26:48,190 memukul node ini adalah jalur sebelumnya karakter 636 00:26:48,190 --> 00:26:50,700 sebenarnya string yang telah Anda masukkan. 637 00:26:50,700 --> 00:26:53,660 Jadi itu semua bool ada lakukan untuk kita. 638 00:26:53,660 --> 00:26:55,500 >> Pertanyaan lain pada mencoba? 639 00:26:55,500 --> 00:26:56,215 Ya. 640 00:26:56,215 --> 00:26:58,035 >> AUDIENCE: Apa tumpang tindih? 641 00:26:58,035 --> 00:26:59,945 Bagaimana jika Anda memiliki 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 memiliki Dave dan Daven? 644 00:27:02,580 --> 00:27:06,240 Jadi jika kita memasukkan, mengatakan 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 super sederhana. 647 00:27:08,700 --> 00:27:10,325 Jadi 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 harus saya lakukan setelah aku memukul simpul keempat? 650 00:27:15,847 --> 00:27:16,680 Hanya akan 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 Konstanta waktu asimtotik. 655 00:27:21,590 --> 00:27:26,300 Dan sekarang kita sudah menunjukkan bahwa kedua Dave dan Daven adalah string dalam struktur. 656 00:27:26,300 --> 00:27:27,710 Jadi tidak masalah. 657 00:27:27,710 --> 00:27:30,200 Dan perhatikan bagaimana kehadiran dari Daven tidak berhasil 658 00:27:30,200 --> 00:27:34,750 mengambil lebih banyak waktu atau kurang waktu untuk Dave dan sebaliknya. 659 00:27:34,750 --> 00:27:36,000 >> Jadi apa lagi yang bisa kita lakukan sekarang? 660 00:27:36,000 --> 00:27:40,680 Kami telah menggunakan metafora ini sebelum nampan yang mewakili sesuatu. 661 00:27:40,680 --> 00:27:43,380 Tapi ternyata bahwa tumpukan nampan sebenarnya 662 00:27:43,380 --> 00:27:47,187 demonstratif data abstrak lain type-- lebih tinggi struktur data tingkat 663 00:27:47,187 --> 00:27:49,770 bahwa pada akhir hari hanya seperti array atau linked list 664 00:27:49,770 --> 00:27:50,970 atau sesuatu yang lebih biasa. 665 00:27:50,970 --> 00:27:53,270 Tapi itu lebih menarik Konsep konseptual. 666 00:27:53,270 --> 00:27:56,440 Sebuah stack, seperti ini baki sini di Mather, 667 00:27:56,440 --> 00:27:58,750 umumnya disebut hanya itu-- stack. 668 00:27:58,750 --> 00:28:02,540 >> Dan dalam jenis struktur data Anda memiliki dua operations-- 669 00:28:02,540 --> 00:28:05,880 Anda memiliki satu disebut dorongan untuk menambahkan sesuatu ke stack, 670 00:28:05,880 --> 00:28:08,320 seperti meletakkan baki lainnya kembali di atas tumpukan. 671 00:28:08,320 --> 00:28:11,350 Dan kemudian pop, yang berarti Anda mengambil baki off paling atas. 672 00:28:11,350 --> 00:28:16,210 Tapi apa kunci tentang stack adalah bahwa itu punya karakteristik penasaran ini. 673 00:28:16,210 --> 00:28:19,560 Sebagai staf ruang makan yang menata ulang baki untuk makan berikutnya, 674 00:28:19,560 --> 00:28:21,380 apa yang akan menjadi benar tentang bagaimana siswa 675 00:28:21,380 --> 00:28:22,856 berinteraksi dengan struktur data? 676 00:28:22,856 --> 00:28:24,480 AUDIENCE: Mereka akan pop satu. 677 00:28:24,480 --> 00:28:26,550 DAVID Malan: Mereka akan pop satu dari, mudah-mudahan atas. 678 00:28:26,550 --> 00:28:28,910 Jika itu hanya agak bodoh untuk pergi semua jalan ke bawah. 679 00:28:28,910 --> 00:28:29,070 Benar? 680 00:28:29,070 --> 00:28:31,620 Struktur data tidak benar-benar memungkinkan Anda untuk mengambil baki bawah setidaknya 681 00:28:31,620 --> 00:28:32,520 mudah. 682 00:28:32,520 --> 00:28:35,040 Jadi ada ini penasaran properti untuk stack 683 00:28:35,040 --> 00:28:39,730 bahwa item terakhir dalam adalah akan menjadi yang pertama keluar. 684 00:28:39,730 --> 00:28:43,400 Dan ilmuwan komputer panggilan ini LIFO-- bertahan, keluar pertama. 685 00:28:43,400 --> 00:28:45,540 Dan itu benar-benar tidak memiliki aplikasi menarik. 686 00:28:45,540 --> 00:28:50,090 Ini tidak selalu sejelas beberapa lain, tetapi bisa, memang, berguna, 687 00:28:50,090 --> 00:28:54,040 dan dapat, memang, dilaksanakan dalam beberapa cara yang berbeda. 688 00:28:54,040 --> 00:28:58,550 >> Jadi satu, dan benar-benar, biarkan saya untuk tidak menyelam ke dalam. 689 00:28:58,550 --> 00:28:59,860 Mari kita lakukan ini sebagai gantinya. 690 00:28:59,860 --> 00:29:03,700 Mari kita lihat satu yang hampir ide yang sama, tapi itu lebih adil sedikit. 691 00:29:03,700 --> 00:29:04,200 Benar? 692 00:29:04,200 --> 00:29:07,560 Jika Anda salah satu dari penggemar anak-anak ini atau gadis-gadis yang benar-benar menyukai produk Apple 693 00:29:07,560 --> 00:29:10,130 dan Anda bangun pukul 03:00 untuk berbaris di beberapa toko 694 00:29:10,130 --> 00:29:14,150 untuk mendapatkan iPhone sangat terbaru, Anda mungkin antri seperti ini. 695 00:29:14,150 --> 00:29:15,800 >> Sekarang antrian sangat sengaja bernama. 696 00:29:15,800 --> 00:29:18,190 Ini garis karena ada beberapa keadilan untuk itu. 697 00:29:18,190 --> 00:29:18,690 Benar? 698 00:29:18,690 --> 00:29:21,690 Ini akan mengisap jenis jika Anda sudah sampai di sana pertama di Apple Store 699 00:29:21,690 --> 00:29:25,700 tetapi Anda efektif yang terendah yang nampan karena Karyawan Apple kemudian 700 00:29:25,700 --> 00:29:28,189 pop orang terakhir yang benar-benar mendapat sejalan. 701 00:29:28,189 --> 00:29:31,230 Jadi tumpukan dan antrian, meskipun fungsional mereka agak same-- yang 702 00:29:31,230 --> 00:29:33,105 itu hanya koleksi ini sumber daya yang 703 00:29:33,105 --> 00:29:36,210 akan tumbuh dan shrink-- ada yang Aspek keadilan ini untuk itu, 704 00:29:36,210 --> 00:29:39,634 setidaknya di dunia nyata, di mana operasi Anda berolahraga 705 00:29:39,634 --> 00:29:40,800 pada dasarnya berbeda. 706 00:29:40,800 --> 00:29:43,360 Sebuah stack-- antrian rather-- dikatakan memiliki 707 00:29:43,360 --> 00:29:45,320 dua operasi: n antrian dan d antrian. 708 00:29:45,320 --> 00:29:46,341 709 00:29:46,341 --> 00:29:48,090 Atau Anda dapat memanggil mereka banyak hal. 710 00:29:48,090 --> 00:29:50,770 Tapi Anda hanya ingin menangkap gagasan bahwa seseorang menambahkan 711 00:29:50,770 --> 00:29:53,230 dan satu pada akhirnya mengurangi. 712 00:29:53,230 --> 00:29:58,840 >> Sekarang di bawah kap mesin, baik stack dan antrian dapat diterapkan bagaimana? 713 00:29:58,840 --> 00:30:01,390 Kami tidak akan masuk ke kode itu karena tingkat yang lebih tinggi 714 00:30:01,390 --> 00:30:03,387 Ide adalah semacam lebih jelas. 715 00:30:03,387 --> 00:30:04,470 Maksudku, apa yang manusia lakukan? 716 00:30:04,470 --> 00:30:07,030 Jika aku orang pertama di Apple Menyimpan dan ini adalah pintu depan, 717 00:30:07,030 --> 00:30:08,130 Anda tahu, aku akan berdiri di sini. 718 00:30:08,130 --> 00:30:09,750 Dan orang berikutnya akan berdiri di sini. 719 00:30:09,750 --> 00:30:11,500 Dan orang berikutnya akan berdiri di sini. 720 00:30:11,500 --> 00:30:13,792 Jadi apa struktur data cocok untuk antrian? 721 00:30:13,792 --> 00:30:14,542 >> AUDIENCE: antrian A. 722 00:30:14,542 --> 00:30:15,667 DAVID Malan: Yah, 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 >> AUDIENCE: Sebuah linked list. 726 00:30:17,600 --> 00:30:18,990 >> DAVID Malan: A terkait daftar Anda bisa menerapkan. 727 00:30:18,990 --> 00:30:22,500 Dan daftar link bagus karena kemudian itu dapat tumbuh sewenang-wenang panjang sebagai lawan 728 00:30:22,500 --> 00:30:24,880 untuk memiliki beberapa nomor tetap orang di toko. 729 00:30:24,880 --> 00:30:27,030 Tapi mungkin sejumlah tetap tempat yang sah. 730 00:30:27,030 --> 00:30:30,350 Karena jika mereka hanya memiliki seperti 20 iPhone pada hari pertama, mungkin 731 00:30:30,350 --> 00:30:33,930 mereka hanya perlu sebuah array dari ukuran 20 untuk mewakili bahwa antrian, yang 732 00:30:33,930 --> 00:30:37,070 hanya untuk mengatakan sekarang setelah kami mulai berbicara tentang masalah-masalah tingkat yang lebih tinggi, 733 00:30:37,070 --> 00:30:38,890 Anda dapat menerapkannya dalam berbagai 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 kompleksitas kode Anda sendiri. 736 00:30:43,950 --> 00:30:45,380 >> Bagaimana dengan stack? 737 00:30:45,380 --> 00:30:48,190 Nah, stack, kita telah melihat terlalu bisa saja nampan ini. 738 00:30:48,190 --> 00:30:50,007 Dan Anda bisa menerapkan ini array. 739 00:30:50,007 --> 00:30:53,090 Tapi di beberapa titik jika Anda menggunakan sebuah array, apa yang akan terjadi pada nampan 740 00:30:53,090 --> 00:30:54,173 Anda mencoba 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 bisa pergi begitu tinggi. 744 00:30:57,490 --> 00:31:00,156 Dan saya pikir di Mather mereka sebenarnya tersembunyi dalam membuka itu. 745 00:31:00,156 --> 00:31:01,950 Jadi memang, hampir seperti Mather menggunakan 746 00:31:01,950 --> 00:31:03,783 array ukuran tetap, karena Anda hanya bisa 747 00:31:03,783 --> 00:31:08,302 cocok begitu banyak nampan dalam pembukaan di dinding bawah lutut orang. 748 00:31:08,302 --> 00:31:10,010 Dan sehingga mungkin dikatakan array, 749 00:31:10,010 --> 00:31:14,300 tapi kita pasti bisa menerapkan bahwa lebih umum dengan linked list. 750 00:31:14,300 --> 00:31:16,390 >> Nah, bagaimana dengan struktur data lain? 751 00:31:16,390 --> 00:31:18,760 Biarkan aku menarik yang lain visual yang di sini. 752 00:31:18,760 --> 00:31:24,710 Sesuatu seperti bagaimana satu ini di sini? 753 00:31:24,710 --> 00:31:28,920 Mengapa itu berguna untuk memiliki tidak sesuatu yang mewah sebagai trie, yang 754 00:31:28,920 --> 00:31:32,370 kami melihat memiliki ini node yang sangat luas, masing-masing adalah dalam array? 755 00:31:32,370 --> 00:31:35,740 Tapi bagaimana kalau kita melakukan sesuatu yang lebih sederhana, seperti pohon keluarga sekolah tua, 756 00:31:35,740 --> 00:31:38,110 masing-masing yang node di sini hanya menyimpan nomor. 757 00:31:38,110 --> 00:31:42,180 Alih-alih nama atau keturunan sebuah hanya menyimpan nomor seperti ini. 758 00:31:42,180 --> 00:31:45,250 >> Nah, jargon yang kami gunakan dalam struktur data adalah baik mencoba 759 00:31:45,250 --> 00:31:49,510 dan pohon-pohon, 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 ketika Anda membuat sebuah keluarga daun tree-- dan akar 762 00:31:53,860 --> 00:31:57,250 pohon dan anak-anak dari orang tua dan saudara kandung tersebut. 763 00:31:57,250 --> 00:32:03,670 Dan kita mungkin menerapkan pohon, misalnya, sesederhana ini. 764 00:32:03,670 --> 00:32:07,420 Sebuah pohon, jika sebagai node, salah satu kalangan ini yang memiliki nomor, 765 00:32:07,420 --> 00:32:09,947 itu tidak akan memiliki satu pointer, tapi dua. 766 00:32:09,947 --> 00:32:11,780 Dan segera setelah Anda menambahkan pointer kedua, Anda 767 00:32:11,780 --> 00:32:13,905 benar-benar dapat sekarang membuat semacam data dua dimensi 768 00:32:13,905 --> 00:32:14,780 struktur dalam memori. 769 00:32:14,780 --> 00:32:16,660 Sama seperti dua dimensi array, Anda dapat 770 00:32:16,660 --> 00:32:18,904 memiliki jenis dua dimensi daftar terhubung tapi yang 771 00:32:18,904 --> 00:32:20,820 yang mengikuti pola di mana tidak ada siklus. 772 00:32:20,820 --> 00:32:24,487 Ini benar-benar sebuah pohon dengan satu cara nenek di sini dan kemudian 773 00:32:24,487 --> 00:32:27,320 beberapa orang tua dan anak-anak dan cucu dan cicit. 774 00:32:27,320 --> 00:32:28,370 dan lain sebagainya. 775 00:32:28,370 --> 00:32:32,390 >> Tapi apa benar-benar rapi tentang ini juga, hanya untuk menggoda Anda dengan sedikit kode, 776 00:32:32,390 --> 00:32:35,370 ingat rekursi dari beberapa waktu yang lalu, dimana 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, karena menganggap ini. 780 00:32:42,920 --> 00:32:43,860 >> Ini adalah pohon. 781 00:32:43,860 --> 00:32:48,040 Dan aku sudah anal kecil dengan cara Aku meletakkan bilangan bulat ke jalan. 782 00:32:48,040 --> 00:32:51,020 Begitu banyak sehingga ia memiliki khusus name-- pohon pencarian biner. 783 00:32:51,020 --> 00:32:53,460 Sekarang kita telah mendengar tentang biner pencarian, tapi Anda juga bisa 784 00:32:53,460 --> 00:32:55,180 bekerja mundur dari nama hal ini? 785 00:32:55,180 --> 00:32:59,280 Bagaimana pola dari bagaimana saya memasukkan bilangan bulat ke pohon ini? 786 00:32:59,280 --> 00:33:00,696 Hal ini tidak sewenang-wenang. 787 00:33:00,696 --> 00:33:01,570 Ada beberapa pola. 788 00:33:01,570 --> 00:33:02,090 Ya. 789 00:33:02,090 --> 00:33:03,370 >> AUDIENCE: 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 Yang lebih kecil berada di sebelah kiri. 792 00:33:05,062 --> 00:33:06,270 Yang lebih besar berada di sebelah kanan. 793 00:33:06,270 --> 00:33:12,940 Sehingga pernyataan yang benar adalah orang tua lebih besar dari anak kiri, 794 00:33:12,940 --> 00:33:14,850 tetapi kurang dari anak kanan. 795 00:33:14,850 --> 00:33:17,750 Dan itu saja bahkan definisi lisan rekursif 796 00:33:17,750 --> 00:33:20,500 karena Anda dapat menerapkan bahwa Logika yang sama ke setiap node 797 00:33:20,500 --> 00:33:23,080 dan hanya pantat out, kasus dasar jika Anda 798 00:33:23,080 --> 00:33:25,740 akan, ketika anda menekan salah satu daun, sehingga untuk berbicara, 799 00:33:25,740 --> 00:33:28,580 di mana cuti tidak memiliki anak lagi. 800 00:33:28,580 --> 00:33:30,614 >> Sekarang bagaimana mungkin Anda menemukan nomor 44? 801 00:33:30,614 --> 00:33:32,280 Anda akan mulai pada akar dan berkata, hm. 802 00:33:32,280 --> 00:33:35,690 55 tidak 44 Jadi apakah saya ingin pergi benar atau apakah saya ingin ke kiri? 803 00:33:35,690 --> 00:33:37,190 Yah, jelas Anda ingin pergi kiri. 804 00:33:37,190 --> 00:33:40,060 Dan itu hanya seperti telepon contoh buku dalam pencarian biner 805 00:33:40,060 --> 00:33:41,099 lebih umum. 806 00:33:41,099 --> 00:33:43,390 Tapi kita mengimplementasikannya sekarang sedikit lebih dinamis 807 00:33:43,390 --> 00:33:45,339 dari array mungkin mengizinkan. 808 00:33:45,339 --> 00:33:48,130 Dan pada kenyataannya, jika Anda ingin terlihat kode tersebut, sekilas yakin. 809 00:33:48,130 --> 00:33:49,671 Sepertinya sejumlah besar baris. 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 menerapkan fungsi disebut pencarian yang tujuannya dalam hidup 812 00:33:54,490 --> 00:33:57,290 adalah untuk mencari nilai seperti n, integer, 813 00:33:57,290 --> 00:34:01,756 dan Anda lulus dalam satu pointer-- pointer ke node akar, 814 00:34:01,756 --> 00:34:04,380 bukan, pohon itu dari mana Anda dapat mengakses segala sesuatu yang lain, 815 00:34:04,380 --> 00:34:08,850 perhatikan bagaimana tedeng aling-aling Anda dapat menerapkan logika. 816 00:34:08,850 --> 00:34:10,880 Jika pohon null, jelas itu 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 Benar? 819 00:34:12,000 --> 00:34:14,040 Jika Anda menyerahkannya apa-apa, tidak ada ada. 820 00:34:14,040 --> 00:34:17,900 >> Lain, jika n kurang dari pohon panah n-- sekarang panah n, 821 00:34:17,900 --> 00:34:20,670 ingat kami memperkenalkan Super singkat hari lain, 822 00:34:20,670 --> 00:34:25,100 dan itu hanya berarti de-referensi pointer dan melihat lapangan yang disebut n. 823 00:34:25,100 --> 00:34:27,690 Jadi itu berarti pergi ke sana dan melihat lapangan yang disebut n. 824 00:34:27,690 --> 00:34:33,810 Jadi jika n, nilai Anda diberi, kurang dari nilai di pohon-pohon integer, 825 00:34:33,810 --> 00:34:35,449 di mana Anda ingin 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 Aku returning-- tidak benar. 829 00:34:39,860 --> 00:34:40,989 Tidak salah. 830 00:34:40,989 --> 00:34:45,670 Aku kembali apa pun jawabannya adalah dari panggilan untuk diriku sendiri, melewati 831 00:34:45,670 --> 00:34:50,100 n lagi, yang berlebihan, tapi apa yang sedikit berbeda sekarang? 832 00:34:50,100 --> 00:34:51,989 Bagaimana aku membuat masalah yang lebih kecil? 833 00:34:51,989 --> 00:34:54,920 Aku lewat di sebagai yang kedua argumen, bukan akar pohon, 834 00:34:54,920 --> 00:34:59,616 tapi anak kiri dalam kasus ini. 835 00:34:59,616 --> 00:35:00,990 Jadi aku lewat di anak kiri. 836 00:35:00,990 --> 00:35:04,720 >> Sementara itu, jika n lebih besar dari node Saat ini saya melihat, 837 00:35:04,720 --> 00:35:06,690 Saya mencari sisi kanan. 838 00:35:06,690 --> 00:35:10,880 Lain, jika pohon tidak null, dan jika elemen tidak ke kiri 839 00:35:10,880 --> 00:35:13,240 dan itu tidak ke kanan, apa yang biasa terjadi? 840 00:35:13,240 --> 00:35:14,630 841 00:35:14,630 --> 00:35:18,440 Kami telah benar-benar menemukan node di pertanyaan, dan jadi kami kembali benar. 842 00:35:18,440 --> 00:35:21,490 >> Jadi kami baru saja menggaruk permukaan sekarang beberapa struktur data tersebut. 843 00:35:21,490 --> 00:35:24,370 Dalam permasalahan yang lima Anda akan mengeksplorasi ini belum lebih lanjut, 844 00:35:24,370 --> 00:35:27,250 dan Anda akan diberi desain Anda pilihan tentang bagaimana untuk pergi tentang ini. 845 00:35:27,250 --> 00:35:30,250 Apa yang saya ingin menyimpulkan tentang hanya teaser 30 detik 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-- untungnya Anda mungkin think-- transisi kita perlahan-lahan 848 00:35:35,390 --> 00:35:38,680 dari dunia C dan rendah Rincian pelaksanaan tingkat, 849 00:35:38,680 --> 00:35:42,090 untuk sebuah dunia di mana kita dapat mengambil untuk saja bahwa orang lain memiliki akhirnya 850 00:35:42,090 --> 00:35:44,010 diimplementasikan data ini struktur bagi kita, 851 00:35:44,010 --> 00:35:47,570 dan kami akan mulai memahami dunia nyata berarti pelaksanaan 852 00:35:47,570 --> 00:35:50,560 program berbasis web dan website lebih umum 853 00:35:50,560 --> 00:35:52,910 dan juga sangat keamanan implikasi yang kita baru 854 00:35:52,910 --> 00:35:54,850 mulai menggores permukaan. 855 00:35:54,850 --> 00:35:57,320 Berikut adalah apa yang menanti kita di masa yang akan datang. 856 00:35:57,320 --> 00:36:00,480 >> [VIDEO PLAYBACK] 857 00:36:00,480 --> 00:36:03,432 858 00:36:03,432 --> 00:36:12,780 >> -Dia Datang dengan pesan, dengan protokol 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 "Warriors of the Net." 868 00:36:48,074 --> 00:36:49,660 [END VIDEO PLAYBACK] 869 00:36:49,660 --> 00:36:50,910 DAVID Malan: Segera 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 PLAYBACK] 873 00:36:56,060 --> 00:36:59,240 -Dan Sekarang, "Deep Thoughts" 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 solusinya untuk minggu ini masalah set " 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 [END VIDEO PLAYBACK]