การคืนหน่วยความจำให้กับระบบ ของ แถวลำดับพลวัต

เนื่องจากแถวลำดับพลวัตสามารถลบข้อมูลจากด้านปลายได้ อาจจะเป็นไปได้ที่หลังจากการลบข้อมูลหลาย ๆ ครั้งแล้ว จะมีพื้นที่ส่วนที่ไม่ได้ใช้งานเป็นจำนวนมากซึ่งทำให้ระบบเสียพื้นที่ไปโดยไม่จำเป็น วิธีการแก้ปัญหานี้สามารถทำได้โดยการคืนหน่วยความจำให้กับระบบโดยการลดความจุลง (โดยที่ความจุต้องมากกว่าขนาดของแถวลำดับพลวัตเพื่อให้ยังสามารถเก็บข้อมูลได้) การลดความจุมีวิธีดำเนินการคล้ายกับการขยายความจุ นั่นคือเป็นการสร้างแถวลำดับใหม่ขึ้นมา คัดลอกข้อมูลจากแถวลำดับเดิมไปยังแถวลำดับใหม่ จากนั้นก็คืนหน่วยความจำของแถวลำดับเดิมให้กับระบบ การดำเนินการลดความจุนี้จึงใช้เวลา Θ ( n ) {\displaystyle \Theta (n)} เช่นเดียวกับการขยายความจุ ดังนั้นหากดำเนินการลดความจุถี่เกินไป จะทำให้เมื่อถัวเฉลี่ยออกมาแล้วการดำเนินการแต่ละครั้งไม่เป็น Θ ( 1 ) {\displaystyle \Theta (1)}

เพื่อรักษาให้เวลาในการดำเนินการแต่ละครั้งเมื่อถัวเฉลี่ยแล้วได้ Θ ( 1 ) {\displaystyle \Theta (1)} ความจุที่ลดลงจึงควรเป็นอัตราเรขาคณิตเช่นเดียวกับการขยายความจุ กล่าวคือเมื่อขนาดของแถวลำดับพลวัตลดลงไปน้อยกว่า cr เท่าของความจุเดิม จึงจะมีการลดความจุ อย่างไรก็ตาม ข้อจำกัดของค่า cr คือ cr ต้องมีค่ามากกว่า c

สถานการณ์เลวร้ายสุดของการดำเนินการบนแถวลำดับพลวัตก็คือการที่ต้องมีการดำเนินการเพิ่มความจุหรือลดความจุบ่อย ๆ ดังนั้นเมื่อพิจารณาในสถานการณ์นี้แล้ว สมมุติให้ขณะนี้มีข้อมูลอยู่ n ตัวซึ่ง n เป็นความจุของแถวลำดับพลวัตพอดีด้วย เมื่อใส่ข้อมูลเพิ่มอีกหนึ่งตัวจะเกิดจากขยายความจุ c เท่า มีความจุเป็น nc และมีขนาดเป็น n + 1 หากจะต้องการให้เกิดการลดความจุ จะต้องทำให้ขนาดของแถวลำดับพลวัตลดลงไปจนน้อยกว่า n c / c r {\displaystyle {nc}/{c_{r}}} นั่นคือต้องลบข้อมูลออกไป n − n c c r = ( c r − c ) c r × n {\displaystyle n-{{nc} \over {c_{r}}}={{{(c_{r}-c)} \over {c_{r}}}\times n}} และเพื่อที่เมื่อถัวเฉลี่ยกับการคัดลอกข้อมูลซึ่งใช้เวลา Θ ( n ) {\displaystyle \Theta (n)} แล้ว การดำเนินการแต่ละครั้งจะได้ใช้เวลา Θ ( 1 ) {\displaystyle \Theta (1)} จึงจะได้ว่าเวลาที่ใช้ในการลบข้อมูลจนเกิดการลดความจุต้องมากกว่าเวลาเชิงเส้น หรือ Ω ( n ) {\displaystyle \Omega (n)}

กรณีที่ c r < c {\displaystyle c_{r}<c} จะได้ว่าขนาดที่จะทำให้เกิดการคืนหน่วยความจำคือ n c / c r {\displaystyle {nc}/{c_{r}}} ซึ่งมีค่ามากกว่า n เสียอีก ดังนั้นการกำหนด c r < c {\displaystyle c_{r}<c} จึงใช้ไม่ได้

กรณีที่ c r = c {\displaystyle c_{r}=c} จะได้ว่า ( c r − c ) c r × n = 0 {\displaystyle {{{(c_{r}-c)} \over {c_{r}}}\times n}=0} ซึ่งไม่เข้ากับเงื่อนไขที่ต้องการ หรือถ้าจะให้วิเคราะห์ จะได้ว่า ขนาดที่ทำให้เกิดการขยายความจุคือ n + 1 ส่วนขนาดที่ทำให้เกิดการลดความจุคือ n ดังนั้นเพียงเพิ่มและลบข้อมูลให้ขนาดเป็น n กับ n + 1 สลับกันไปเรื่อย ๆ ก็จะทำให้เวลารวมกลายเป็น Θ ( n 2 ) {\displaystyle \Theta (n^{2})} และถัวเฉลี่ยออกมาไม่ได้เวลาตามที่ต้องการ

กรณีที่ c r > c {\displaystyle c_{r}>c} จะได้ว่า ( c r − c ) c r × n = Ω ( n ) {\displaystyle {{{(c_{r}-c)} \over {c_{r}}}\times n}=\Omega (n)} ตามที่ต้องการ

ดังนั้น หากกำหนดให้ c r > c {\displaystyle c_{r}>c} จะได้ว่าสามารถถัวเฉลี่ยให้การดำเนินการแต่ละครั้งให้ใช้เวลาคงที่ หรือ Θ ( 1 ) {\displaystyle \Theta (1)} ได้ ส่วนหากกำหนดค่า cr เป็นอย่างอื่น อาจทำให้เกิดปัญหาหรือไม่มีประสิทธิภาพได้

แหล่งที่มา

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...