DOUG LLOYD: ดังนั้นใน CS50 เราได้ครอบคลุม จำนวนมากของโครงสร้างข้อมูลที่แตกต่างกัน ใช่มั้ย? เราได้เห็นอาร์เรย์และเชื่อมโยง รายการและตารางแฮช และพยายามกองและการรอคิว นอกจากนี้เรายังจะได้เรียนรู้เล็ก ๆ น้อย ๆ เกี่ยวกับต้นไม้และกองซากปรักหักพัง แต่จริงๆเหล่านี้ทั้งหมดเพียงจบ ขึ้นเป็นรูปแบบในธีม มีจริงๆเหล่านี้ สี่ชนิดของความคิดพื้นฐาน ทุกอย่างอื่นที่สามารถต้มลงไป อาร์เรย์รายการที่เชื่อมโยง ตารางแฮชและพยายาม และเหมือนที่ผมกล่าวว่ามี มีรูปแบบที่พวกเขา แต่นี้สวย มากไปที่จะสรุป ทุกสิ่งที่เรากำลังจะพูดคุย เกี่ยวกับในชั้นเรียนในแง่ของซีนี้ แต่วิธีการทำสิ่งเหล่านี้วัดขึ้นทั้งหมดใช่มั้ย? เราได้พูดคุยเกี่ยวกับข้อดีและข้อเสีย ของแต่ละวิดีโอแยกพวกเขา แต่มีจำนวนมากของตัวเลข ได้รับการโยนไปรอบ ๆ มีจำนวนมากของทั่วไปเป็น ความคิดที่ได้รับการโยนไปรอบ ๆ ลองและรวบรวม มันกลายเป็นเพียงที่เดียว ลองชั่งน้ำหนักข้อดีกับ ข้อเสียและพิจารณา ซึ่งโครงสร้างข้อมูล อาจจะมีข้อมูลที่ถูกต้อง โครงสร้างสำหรับสถานการณ์เฉพาะของคุณ สิ่งที่ชนิดของข้อมูลที่คุณเก็บ คุณไม่จำเป็นต้องเสมอ ใช้การแทรกเร็วสุดลบ และการค้นหาของ Trie ถ้าคุณจริงๆ ไม่สนใจเกี่ยวกับการใส่และการลบ มากเกินไป หากคุณต้องการได้อย่างรวดเร็วเพียงแค่สุ่ม การเข้าถึงอาร์เรย์อาจจะดีกว่า ดังนั้นขอกลั่นที่ พูดคุยเกี่ยวกับแต่ละแห่งที่สี่ ชนิดที่สำคัญของโครงสร้างข้อมูล ที่เราได้พูดคุยเกี่ยวกับและ เพียงแค่เห็นเมื่อพวกเขาอาจจะดี และเมื่อพวกเขาอาจจะไม่ดีดังนั้น ดังนั้นขอเริ่มต้นด้วยอาร์เรย์ ดังนั้นการแทรกที่ชนิดของที่ไม่ดี 

แทรกในตอนท้ายของอาร์เรย์เป็น OK ถ้าเรากำลังสร้างอาร์เรย์ที่เราไป แต่ถ้าเราต้องใส่ องค์ประกอบเข้ามาตรงกลาง คิดว่ากลับไปแทรก เรียงลำดับมีจำนวนมาก ของการขยับเพื่อให้พอดีกับองค์ประกอบในการมี และดังนั้นถ้าเราจะใส่ ที่ใดก็ได้ แต่ในตอนท้ายของอาร์เรย์ ที่อาจไม่ดีดังนั้น 

ในทำนองเดียวกันการลบเว้นแต่เรา ลบจากสิ้นอาร์เรย์ อาจจะยังไม่ได้ดังนั้นดีถ้า เราไม่ต้องการที่จะออกจากช่องว่างที่ว่างเปล่า ซึ่งโดยปกติเราทำไม่ได้ เราต้องการที่จะลบองค์ประกอบและ แล้วเรียงลำดับของการทำให้มันสบายอีกครั้ง และเพื่อให้การลบองค์ประกอบจาก อาร์เรย์ยังไม่ดีดังนั้น 

ค้นหา แต่เป็นที่ดี เรามีการเข้าถึงแบบสุ่ม ค้นหาเวลาคง เราก็บอกว่าเจ็ดและที่เราจะไป การย้ายอาร์เรย์เจ็ด เราพูดว่า 20 กับไปที่ การย้ายถิ่นฐานอาร์เรย์ 20 เราไม่ได้มีการย้ำข้าม นั่นเป็นสิ่งที่ดีงาม 

อะเรย์ยังมีความสะดวกในการจัดเรียง ทุกครั้งที่เราได้พูดคุยเกี่ยวกับการเรียงลำดับ ขั้นตอนวิธีการเช่นการจัดเรียงการเลือก จัดเรียงแทรกเรียงลำดับฟองผสาน เรียงลำดับอาร์เรย์ที่เราใช้อยู่เสมอที่จะทำมัน เพราะอาร์เรย์จะสวยง่ายต่อการ เรียงลำดับเทียบกับโครงสร้างข้อมูล เราได้เห็นเพื่อให้ห่างไกล 

พวกเขายังมีขนาดค่อนข้างเล็ก มีไม่มากพื้นที่พิเศษ คุณเพียงแค่ว่าการตั้งสำรองมากที่สุดเท่าที่ ตามที่คุณต้องการเก็บข้อมูลของคุณ และที่มันสวยมาก ดังนั้นพวกเขากำลังขนาดเล็กสวย และมีประสิทธิภาพในทางที่ แต่ข้อเสียอีก แต่ ที่พวกเขาได้รับการแก้ไขในขนาด เรามีการประกาศว่าวิธีการ ขนาดใหญ่ที่เราต้องการอาร์เรย์ของเราที่จะเป็น และเราจะได้รับหนึ่งยิงไปที่มัน เราไม่สามารถเจริญเติบโตและหด 

ถ้าเราต้องการที่จะเติบโตหรือหดมันเรา จำเป็นต้องประกาศอาร์เรย์ใหม่ทั้งหมด คัดลอกทุกองค์ประกอบของ อาเรย์ครั้งแรกในแถวที่สอง และถ้าเราคาดคะเนว่า เวลาที่เราต้องทำมันอีกครั้ง ไม่ดีดังนั้น ดังนั้นอาร์เรย์ไม่ให้เรามีความยืดหยุ่น จะมีจำนวนตัวแปรขององค์ประกอบ 

กับรายการที่เชื่อมโยง แทรกเป็นเรื่องง่ายสวย เราเพียงแค่ตะปูลงบนหน้า ลบยังเป็นเรื่องง่ายสวย เราต้องไปหาองค์ประกอบ ที่เกี่ยวข้องกับการค้นหาบาง 

แต่เมื่อคุณได้พบธาตุ คุณกำลังมองหาสิ่งที่คุณต้องทำ เปลี่ยนเป็นตัวชี้ อาจจะเป็นสองถ้าคุณมี ที่เชื่อมโยง list-- ทวีคูณ รายการที่เชื่อมโยง, rather-- และจากนั้นคุณก็สามารถเพิ่มโหนด คุณไม่จำเป็นต้องที่จะเปลี่ยน ทุกอย่างรอบตัว คุณเพียงแค่เปลี่ยนสองตัวชี้ เพื่อให้เป็นอย่างรวดเร็วสวย 

การค้นหาที่ไม่ดี แต่ใช่มั้ย? เพื่อที่เราจะได้พบกับ องค์ประกอบในรายการที่เชื่อมโยง ไม่ว่าจะเป็นเดี่ยวหรือเชื่อมโยงทวีคูณ เราจะต้องค้นหามันเชิงเส้น เราต้องเริ่มต้นที่จุดเริ่มต้นและ ย้ายจุดสิ้นสุดหรือเริ่มต้นในตอนท้ายการย้าย ที่จุดเริ่มต้น เราไม่ได้มีการเข้าถึงแบบสุ่มอีกต่อไป ดังนั้นหากเรากำลังทำ จำนวนมากของการค้นหาอาจจะ รายการที่เชื่อมโยงไม่ได้ ค่อนข้างดีสำหรับเรา 

พวกเขายังได้จริงๆ ยากที่จะเรียงลำดับใช่มั้ย? วิธีเดียวที่คุณสามารถ จริงๆเรียงลำดับรายการที่เชื่อมโยง คือการจัดเรียงที่คุณสร้างมัน แต่ถ้าคุณจัดเรียงตามที่คุณ สร้างมันคุณไม่ได้ การแทรกอย่างรวดเร็วอีกต่อไป คุณไม่ได้เป็นเพียงการตรึง สิ่งบนด้านหน้า คุณต้องไปหา จุดที่เหมาะสมที่จะนำมัน, แล้วแทรกของคุณ กลายเป็นเพียงเกี่ยวกับการไม่ดีเท่า ขณะที่ใส่ลงในอาร์เรย์ รายการที่เชื่อมโยงดังนั้นไม่ได้ เพื่อให้ที่ดีสำหรับการเรียงลำดับข้อมูล 

พวกเขายังสวยขนาดเล็กขนาดที่ชาญฉลาด รายการที่เชื่อมโยงเป็นทวีคูณเล็กน้อย มีขนาดใหญ่กว่ารายการที่เชื่อมโยงโดยลำพัง ที่มีขนาดใหญ่กว่าเล็กน้อย กว่าอาร์เรย์ แต่ก็ไม่ได้ เป็นจำนวนมากของการสูญเสียพื้นที่ ดังนั้นหากพื้นที่ที่พรีเมี่ยม แต่ ไม่ได้เป็นพรีเมี่ยมที่รุนแรงจริงๆ นี้อาจจะเป็นวิธีที่จะไป 

ตารางแฮช ใส่ลงในตารางแฮช ตรงไปตรงมาเป็นธรรม มันเป็นกระบวนการที่สองขั้นตอน ครั้งแรกที่เราจำเป็นต้องเรียกใช้ข้อมูลของเราผ่าน ฟังก์ชันแฮชที่จะได้รับรหัสกัญชา และจากนั้นเราใส่องค์ประกอบเข้าไปใน ตารางแฮชที่ตั้งรหัสกัญชาที่ 

ลบคล้ายกับรายการที่เชื่อมโยง เป็นเรื่องง่ายเมื่อคุณพบองค์ประกอบ คุณต้องไปหามันเป็นครั้งแรก แต่แล้วเมื่อคุณลบมัน คุณเพียงแค่ต้องแลกเปลี่ยน คู่ของตัวชี้ที่ ถ้าคุณกำลังใช้ผูกมัดแยกต่างหาก หากคุณกำลังใช้แหย่, หรือถ้าคุณไม่ได้ ใช้ผูกมัดเลย ในตารางแฮชของคุณ การลบเป็นจริงเรื่องง่าย ทั้งหมดที่คุณต้องทำคือกัญชา ข้อมูลและจากนั้นไปที่ตำแหน่งนั้น และสมมติว่าคุณทำไม่ได้ มีชนใด ๆ คุณจะสามารถลบได้อย่างรวดเร็ว 

ตอนนี้การค้นหาคือสิ่งที่ ได้รับเพียงเล็กน้อยที่ซับซ้อนมากขึ้น มันเป็นเรื่องเกี่ยวกับค่าเฉลี่ยที่ดีขึ้น กว่ารายการที่เชื่อมโยง หากคุณกำลังใช้ผูกมัด, คุณยังมีรายการที่เชื่อมโยง ซึ่งหมายความว่าคุณยังคงมี ค้นหาความเสียหายรายการที่เชื่อมโยง แต่เนื่องจากคุณกำลังการเชื่อมโยงของคุณ รายการและแยกมันมากกว่า 100 หรือ 1000 หรือ n องค์ประกอบในตารางแฮชของคุณคุณ รายการที่เชื่อมโยงทุกคนหนึ่งที่ n ขนาด พวกเขากำลังทั้งหมดที่มีขนาดเล็กอย่างมีนัยสำคัญ คุณได้รายการที่เชื่อมโยง n แทน ของรายการที่เชื่อมโยงเป็นหนึ่งในขนาด n 

ดังนั้นนี้จริงของโลกอย่างต่อเนื่อง ปัจจัยซึ่งโดยทั่วไปเรา ไม่ได้พูดคุยเกี่ยวกับความซับซ้อนในเวลานั้น ไม่จริงสร้างความแตกต่างที่นี่ ดังนั้นการค้นหายังคงเป็นเชิงเส้น ค้นหาถ้าคุณกำลังใช้การผูกมัด, แต่ความยาวของรายการ คุณกำลังค้นหาผ่าน เป็นอย่างมากที่สั้นมากโดยเปรียบเทียบ อีกครั้งถ้าเรียงลำดับเป็นของคุณ เป้าหมายที่นี่ตารางแฮชของ อาจจะไม่ได้เป็นวิธีที่จะไป เพียงแค่ใช้อาร์เรย์ถ้าเรียงลำดับ เป็นจริงที่สำคัญกับคุณ 

และพวกเขาสามารถใช้โทนเสียงดนตรีที่มีขนาด มันยากที่จะพูดว่า ตารางแฮชมีขนาดเล็กหรือใหญ่ เพราะมันขึ้นอยู่กับ วิธีการที่มีขนาดใหญ่ตารางแฮชของคุณอยู่ หากคุณเพียง แต่จะได้รับการจัดเก็บ ห้าองค์ประกอบในตารางแฮชของคุณ และคุณมีตารางแฮช 10,000 องค์ประกอบในนั้น คุณอาจสูญเสียพื้นที่มาก คมชัดเป็นคุณยังสามารถ มีตารางกัญชาขนาดเล็กมาก แต่มีขนาดเล็กตารางแฮชของคุณได้ อีกต่อไปแต่ละรายการที่เชื่อมโยงเหล่านั้น ได้รับ และเพื่อให้มีจริงๆวิธีที่จะไม่กำหนด ว่าขนาดของตารางแฮชที่ แต่ก็อาจจะมีความปลอดภัย จะบอกว่ามันเป็นเรื่องทั่วไป จะมีขนาดใหญ่กว่าที่เชื่อมโยง รายการจัดเก็บข้อมูลเดียวกัน แต่มีขนาดเล็กกว่า Trie 

และพยายามอยู่ที่สี่ ของโครงสร้างเหล่านี้ ที่เราได้รับการพูดถึง ใส่ลงใน Trie มีความซับซ้อน มีจำนวนมากเป็นแบบไดนามิก จัดสรรหน่วยความจำ โดยเฉพาะอย่างยิ่งที่จุดเริ่มต้น ในขณะที่คุณกำลังเริ่มต้นในการสร้าง แต่มันถึงเวลาที่คงที่ มันเป็นเพียงองค์ประกอบของมนุษย์ ที่นี่ที่ทำให้มันยุ่งยาก ต้องพบตัวชี้โมฆะ malloc พื้นที่ไปที่นั่นอาจจะเป็นพื้นที่ malloc จากที่นั่นอีกครั้ง เรียงลำดับปัจจัยของการข่มขู่ คำแนะนำในการจัดสรรหน่วยความจำแบบไดนามิก เป็นอุปสรรค์ในการล้าง แต่เมื่อคุณได้ล้างมันแทรก จริงมาค่อนข้างง่าย และแน่นอนเป็นเวลาที่คงที่ 

การลบเป็นเรื่องง่าย ทั้งหมดที่คุณต้องทำคือการนำทางลง คู่ของตัวชี้และโหนดฟรี เพื่อให้เป็นที่ดีงาม นอกจากนี้ยังมีการค้นหาอย่างรวดเร็ว ก็ขึ้นอยู่เฉพาะใน ความยาวของข้อมูลของคุณ ดังนั้นหากข้อมูลทั้งหมดของคุณเป็น ห้าสตริงตัวอักษร ตัวอย่างเช่นคุณเก็บห้า สตริงตัวอักษรใน Trie ของคุณ จะใช้เวลาเพียงห้าขั้นตอน พบสิ่งที่คุณกำลังมองหา ห้าเป็นเพียงปัจจัยคงดังนั้น อีกครั้งแทรกลบและค้นหา ที่นี่มีตลอดเวลาอย่างต่อเนื่องได้อย่างมีประสิทธิภาพ 

สิ่งหนึ่งคือว่า Trie ของคุณอยู่ จริงชนิดของการเรียงอยู่แล้วใช่มั้ย? อาศัยอำนาจตามความของการที่เราอยู่ องค์ประกอบแทรก โดยไปที่ตัวอักษรตามตัวอักษรของ ที่สำคัญหรือหลักโดยหลักของที่สำคัญ โดยทั่วไป Trie ของคุณสิ้นสุดขึ้นเป็น เรียงชนิดของที่คุณสร้างมัน มันไม่ได้จริงๆที่ทำให้ ความรู้สึกที่จะคิดเกี่ยวกับการเรียงลำดับ ในลักษณะเดียวกับที่เราคิดเกี่ยวกับ กับอาร์เรย์หรือรายการที่เชื่อมโยง หรือตารางแฮช แต่ในความรู้สึกบางอย่างของคุณ Trie เรียงตามที่คุณไป 

ข้อเสียของหลักสูตรคือ Trie อย่างรวดเร็วกลายเป็นขนาดใหญ่ จากจุดทางแยกทุกครั้งที่คุณอาจจะ ถ้า have-- สำคัญของคุณประกอบด้วยตัวเลข คุณมี 10 อื่น ๆ สถานที่ที่คุณสามารถไปที่ หมายความว่าทุกโหนด มีข้อมูล เกี่ยวกับข้อมูลที่คุณต้องการในการจัดเก็บ ที่โหนดที่บวก 10 ตัวชี้ ซึ่งใน IDE CS50 เป็น 80 ไบต์ ดังนั้นจึงเป็นอย่างน้อย 80 ไบต์สำหรับ โหนดที่คุณสร้างทุก และที่ไม่ได้นับข้อมูล และถ้าโหนดของคุณ ตัวอักษรแทนตัวเลข ตอนนี้คุณมี 26 ตัวชี้ จากทุกสถานที่ และ 26 ครั้งที่ 8 น่าจะเป็น 200 ไบต์หรือสิ่งที่ต้องการ และคุณมีเงินทุน และคุณสามารถ lowercase-- ดูว่าฉันจะมีนี้ใช่มั้ย? โหนดของคุณจะได้รับจริงๆ ขนาดใหญ่และอื่น ๆ ของ Trie ตัวเองโดยรวมสามารถ ได้รับใหญ่มากเกินไป ดังนั้นหากพื้นที่เป็นที่สูง พรีเ​​มี่ยมในระบบของคุณ Trie ไม่อาจจะเป็นวิธีที่ถูกต้อง ไปแม้ว่าผลประโยชน์อื่น ๆ มาเล่น. ฉันลอยด์ดั๊ก นี่คือ CS50