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