เมนูนำทาง
แถวลำดับพลวัต ประสิทธิภาพเทียบกับโครงสร้างข้อมูลอื่นรายการโยง | แถวลำดับ | รายการ แถวลำดับ | ต้นไม้ สมดุล | รายการเข้าถึง ข้อมูลแบบสุ่ม | |
---|---|---|---|---|---|
การเข้าถึงข้อมูล | Θ(n) | Θ(1) | Θ(1) | Θ(log n) | Θ(log n) |
การเพิ่มและลบที่ด้านหน้า | Θ(1) | N/A | Θ(n) | Θ(log n) | Θ(1) |
การเพิ่มและลบที่ปลาย | Θ(1) | N/A | Θ(1) ถัวเฉลี่ย | Θ(log n) | Θ(log n) ในการปรับ |
การเพิ่มและลบตรงกลาง | เวลาค้นหา + Θ(1)[6][7][8] | N/A | Θ(n) | Θ(log n) | Θ(log n) ในการปรับ |
พื้นที่ซึ่งเสียไป (โดยเฉลี่ย) | Θ(n) | 0 | Θ(n)[9] | Θ(n) | Θ(n) |
แถวลำดับพลวัตมีประสิทธิภาพเหมือนแถวลำดับทุกประการ นอกจากนี้ยังมีความสามารถมากขึ้นด้วยการสามารถเพิ่มหรือลบข้อมูลทางปลายได้เรื่อย ๆ ความสามารถของแถวลำดับพลวัตมีดังนี้
จะเห็นได้ว่าข้อดีทั้งหลายของแถวลำดับพลวัตมาจากข้อดีของแถวลำดับ เช่นการที่สามารถแคชข้อมูล มีความแน่นของข้อมูลมาก (ใช้เนื้อที่น้อย) การเข้าถึงโดยสุ่ม มีเพียงตัวแปรเก็บขนาดและความจุที่ต้องเก็บเพิ่มเท่านั้น ดังนั้นแถวลำดับพลวัตจึงเป็นโครงสร้างข้อมูลที่เหมาะในการทำงานหลาย ๆ อย่าง
เปรียบเทียบกับรายการโยงแล้ว แถวลำดับพลวัตสามารถเข้าถึงข้อมูลแบบสุ่มได้ ในขณะที่รายการโยงต้องใช้เวลาเชิงเส้น นอกจากนี้ยังมีความสามารถในการแคช ต่างจากรายการโยงที่ข้อมูลไม่ได้มีที่อยู่หน่วยความจำติดกัน ทำให้ไม่สามารถแคชข้อมูลได้ อย่างไรก็ตาม ความสามารถในการเพิ่มและลบข้อมูลกลางแถวลำดับพลวัตจะใช้เวลาเชิงเส้นเหมือนแถวลำดับเนื่องจากข้อมูลต้องเลื่อนเป็นจำนวนมาก ในขณะที่รายการโยงสามารถทำได้ในเวลาคงที่ ข้อด้อยนี้อาจใช้บัฟเฟอร์ช่องว่าง, tiered vector ช่วยได้ (อธิบายไว้ข้างล่างในหัวข้อโครงสร้างข้อมูลอื่นที่คล้ายกัน) สำหรับเครื่องที่มีหน่วยความจำน้อยหรือมีความกระจัดกระจายของพื้นที่หน่วยความจำสูง อาจจะไม่สามารถหาพื้นที่ติดกันที่มากพอในการจัดสรรให้แถวลำดับพลวัตได้
สำหรับต้นไม้สมดุล มีความสามารถในการดำเนินการต่าง ๆ ด้วยเวลาที่น้อยมาก เช่นเข้าถึงข้อมูลตัวใด ๆ, เพิ่มและลบข้อมูล ณ ตำแหน่งใด ๆ ในเวลา O ( log n ) {\displaystyle O(\log n)} อย่างไรก็ตาม เนื้อที่ที่เก็บข้อมูลในโครงสร้างต้นไม้นั้นไม่ติดกัน จึงทำให้ไม่สามารถแคชได้
เมนูนำทาง
แถวลำดับพลวัต ประสิทธิภาพเทียบกับโครงสร้างข้อมูลอื่นใกล้เคียง
แถวลำดับพลวัต แถวลำดับแบบจับคู่ แถวลำดับ แถวลำดับเส้นฐานยาวมาก แถวลำดับจูดี้ แถวลำดับขนาดใหญ่มาก แถวลำดับแอลซีพี แถวลำดับซัฟฟิกซ์ แถวลำดับแบบขนาน แถบลำดับหลักแหล่งที่มา
WikiPedia: แถวลำดับพลวัต http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-... http://www.collectionspy.com http://www.cplusplus.com/reference/deque/deque/ http://www.cplusplus.com/reference/vector/vector/ http://www.ddj.com/architect/184409965?pgno=5 http://channel9.msdn.com/Events/GoingNative/GoingN... http://download.oracle.com/javase/7/docs/api/java/... http://kjellkod.wordpress.com/2012/02/25/why-you-s... http://www.juniata.edu/faculty/kruse/cs240/linkedl... http://www.juniata.edu/faculty/kruse/cs240/syllabu...