แถวลำดับพลวัต

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

แถวลำดับพลวัต (อังกฤษ: dynamic array) หรืออาจเรียกว่า แถวลำดับที่ขยายได้ (growable array) , แถวลำดับที่เปลี่ยนขนาดได้ (resizable array) , ตารางพลวัต (dynamic table) , รายการแถวลำดับ (array list) หรือ เวกเตอร์ (vector) เป็นรายการประเภทหนึ่ง มีคุณสมบัติการเข้าถึงโดยสุ่มเหมือนแถวลำดับ แต่ต่างจากแถวลำดับธรรมดาตรงที่สามารถขยายขนาดเองได้เมื่อใส่ข้อมูลเพิ่มเข้าไป^[1]

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

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

หลักการทำงาน[แก้]

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

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

รูปแบบการทำงานของแถวลำดับพลวัต อาจแบ่งได้ออกเป็น 3 แบบ คือ

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

การทำงานที่ทราบจำนวนของข้อมูล[แก้]

ในกรณีที่ทราบว่าแถวลำดับพลวัตจะเก็บข้อมูลเท่าใด สามารถกำหนดความจุให้เป็นค่าคงที่หนึ่งที่มีค่ามากกว่าหรือเท่ากับจำนวนของข้อมูล เพื่อรับประกันว่าจะไม่มีปัญหาที่ขนาดของแถวลำดับพลวัตมีค่าเกินความจุของแถวลำดับพลวัต ซึ่งนำไปสู่การเสียเวลาจากการขยายความจุ นอกจากนี้ เนื่องจากความจุเป็นค่าคงที่ พื้นที่ที่สูญเสียไปโดยไม่จำเป็นก็เป็นค่าคงที่เช่นเดียวกัน อย่างไรก็ตาม ในทางปฏิบัติมักจะไม่รู้ถึงจำนวนของข้อมูลที่แน่นอน และการเก็บข้อมูลด้วยแถวลำดับพลวัตที่ความจุเป็นค่าคงที่ในบางสถานการณ์ กลับทำให้สูญเสียพื้นที่โดยไม่จำเป็นอย่างมากมาย เช่นหากมีข้อมูล $n$ ตัวที่จะนำมาเก็บบนรายการ $m$ รายการตามคำสั่งที่กำหนด จะได้ว่ารายการหนึ่ง ๆ มีโอกาสที่จะมีข้อมูลมากสุดถึง $n$ ตัว ดังนั้นหากใช้แถวลำดับพลวัตที่ความจุเป็นค่าคงที่ในการทำรายการทั้ง $m$ รายการนั้น ก็ต้องหน่วยความจำถึง $\Theta (nm)$ เพื่อรับประกันว่าข้อมูลจะสามารถเก็บได้หมด แต่ถ้าหากใช้แถวลำดับพลวัตที่ความจุไม่เป็นค่าคงที่ (หัวข้อถัด ๆ ไป) จะใช้หน่วยความจำเพียง $\Theta (n+m)$ เท่านั้น

การขยายความจุเป็นค่าคงที่[แก้]

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

ตารางแสดงจำนวนคำสั่งในการขยายความจุเมื่อความจุเพิ่มทีละ c
ครั้งที่ของการขยายความจุ	$1$	$2$	$3$	...	$k$	สรุป
ขนาดของแถวลำดับพลวัตในรอบนั้น ๆ	$c$	$2\times c$	$3\times c$	...	$k\times c$	ขนาดสุดท้าย	$k\times c$
จำนวนคำสั่งในการคัดลอกข้อมูลในรอบนั้น ๆ	$c$	$2\times c$	$3\times c$	...	$k\times c$	รวมจำนวนคำสั่ง	$(1+2+3+...+k)\times c$

จากตาราง เมื่อมีการใส่ข้อมูลเข้ามาในแถวลำดับพลวัตเป็นจำนวน $n=k\times c$ ตัว จะมีการทำงานจากการจองหน่วยความจำและคัดลอกข้อมูลถึง $(1+2+...+k)\times c=\Theta (k^{2})$ ครั้ง เนื่องจาก $k\propto n$ จะได้ว่าการใส่ข้อมูลเข้าไป $n$ ตัวใช้เวลาถึง $\Theta (n^{2})$ ถึงแม้วิธีนี้จะเสียเวลามาก แต่พื้นที่ที่สูญเสียไปก็คือส่วนที่ยังไม่ได้ใช้ซึ่งเป็นเพียงค่าคงที่เท่านั้น อย่างไรก็ตาม ในทางปฏิบัติมักจะคำนึงถึงความรวดเร็วของการทำงานมากกว่าพื้นที่ที่สูญเสียไป

การขยายความจุเป็นอัตราเรขาคณิตและการถัวเฉลี่ย[แก้]

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

function insertEnd (dynarray a, element e)
    if (a.size = a.capacity)
        // resize a to c times of its current capacity:
        a.capacity ← a.capacity * c
        //  (copy the contents to the new memory location here) 
    a[a.size] ← e
    a.size ← a.size + 1

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

ตารางแสดงจำนวนคำสั่งในการขยายขนาดเมื่อความจุเพิ่มทีละ c เท่า
ครั้งที่ของการขยายขนาด	$1$	$2$	$3$	...	$k$	สรุป
ขนาดของแถวลำดับพลวัตในรอบนั้น ๆ	$1$	$c$	$c^{2}$	...	$c^{k-1}$	ขนาดสุดท้าย	$c^{k-1}$
จำนวนคำสั่งในการคัดลอกข้อมูลในรอบนั้น ๆ	$1$	$c$	$c^{2}$	...	$c^{k-1}$	รวมจำนวนคำสั่ง	$1+c+c^{2}+...+c^{k-1}$

สรุปได้ว่าเมื่อมีการใส่ข้อมูลเข้ามาในแถวลำดับพลวัตเป็นจำนวน $n=c^{k-1}$ ตัว จะมีการทำงาน $1+c+c^{2}+...+c^{k-1}=\Theta (c^{k})$ ครั้ง เนื่องจาก $k\propto \log _{c}n$ จะได้ว่าการใส่ข้อมูลเข้าไป $n$ ตัวใช้เวลา $\Theta (c^{\log _{c}n})=\Theta (n)$ ดังนั้นจึงอาจถัวเฉลี่ยให้การดำเนินการเพิ่มข้อมูลครั้งหนึ่งใช้เวลา $\Theta (1)$ ได้ ข้อเสียของแถวลำดับพลวัตที่ขยายความจุเป็นอัตราเรขาคณิตคือพื้นที่ที่เสียไปโดยไม่จำเป็นอาจมีมากถึงเชิงเส้น $O(n)$ ^[1]

ค่า c นั้นสามารถเลือกใช้เป็นจำนวนใด ๆ ก็ได้ที่มากกว่า 1 เพื่อให้เห็นภาพได้ชัด หนังสือส่วนใหญ่ใช้ค่า c = 2 ^[3]^[4] แต่เพื่อให้พื้นที่ที่เสียไปโดยไม่จำเป็นไม่มากนัก ในทางปฏิบัติมักจะใช้ค่า c ที่น้อยกว่านั้น เช่น ArrayList ของภาษาจาวาใช้ค่า c = 3/2 ^[2] list ของภาษาไพธอน (ซึ่งเขียนด้วยภาษา C) ใช้ค่า c = 9/8^[5]

แถวลำดับพลวัตเป็นตัวอย่างที่นิยมใช้ในการสอนเรื่องการวิเคราะห์แบบถัวเฉลี่ย^[3]^[4]

การคืนหน่วยความจำให้กับระบบ[แก้]

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

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

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

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

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

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

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

ประสิทธิภาพเทียบกับโครงสร้างข้อมูลอื่น[แก้]

	รายการโยง	แถวลำดับ	รายการ แถวลำดับ	ต้นไม้ สมดุล	รายการเข้าถึง ข้อมูลแบบสุ่ม
การเข้าถึงข้อมูล	Θ(n)	Θ(1)	Θ(1)	Θ(log n)	Θ(log n)
การเพิ่มและลบที่ด้านหน้า	Θ(1)	—	Θ(n)	Θ(log n)	Θ(1)
การเพิ่มและลบที่ปลาย	Θ(1)	—	Θ(1) ถัวเฉลี่ย	Θ(log n)	Θ(log n) ในการปรับ
การเพิ่มและลบตรงกลาง	เวลาค้นหา + Θ(1)^[6]^[7]^[8]	—	Θ(n)	Θ(log n)	Θ(log n) ในการปรับ
พื้นที่ซึ่งเสียไป (โดยเฉลี่ย)	Θ(n)	0	Θ(n)^[9]	Θ(n)	Θ(n)

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

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

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

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

สำหรับต้นไม้สมดุล มีความสามารถในการดำเนินการต่าง ๆ ด้วยเวลาที่น้อยมาก เช่นเข้าถึงข้อมูลตัวใด ๆ, เพิ่มและลบข้อมูล ณ ตำแหน่งใด ๆ ในเวลา $O(\log n)$ อย่างไรก็ตาม เนื้อที่ที่เก็บข้อมูลในโครงสร้างต้นไม้นั้นไม่ติดกัน จึงทำให้ไม่สามารถแคชได้

โครงสร้างข้อมูลอื่นที่คล้ายกัน[แก้]

บัฟเฟอร์ช่องว่าง (อังกฤษ: Gap buffer) เป็นโครงสร้างข้อมูลที่คล้ายกับแถวลำดับพลวัต ความแตกต่างของบัฟเฟอร์ช่องว่างกับแถวลำดับพลวัตคือบัฟเฟอร์ช่องว่างจะมีพื้นที่ส่วนที่ไม่ได้ใช้แทรกอยู่เป็นจำนวนมาก แทนที่จะอยู่ฝั่งขวาเหมือนกับแถวลำดับพลวัต

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

Goodrich ^[10]ได้เสนอขั้นตอนวิธีในการสร้างแถวลำดับพลวัต เรียกว่า Tiered Vector ซึ่งใช้เวลา $O({\sqrt {n}})$ ในการเพิ่มและลบข้อมูลกลางแถวลำดับพลวัต

ต้นไม้แถวลำดับแฮช (อังกฤษ: Hash array tree; HAT) เป็นขั้นตอนวิธีของรายการแถบลำดับซึ่งตีพิมพ์ในปี 1996^[11] ต้นไม้แถวลำดับแฮชใช้พื้นที่ $O({\sqrt {n}})$ เมื่อ n คือจำนวนข้อมูลในแถวลำดับนี้ ขั้นตอนวิธีนี้ทำให้การเพิ่มอนุกรมเข้าไปที่ท้ายของต้นไม้แถวลำดับแฮช มีประสิทธิภาพทางเวลาถัวเฉลี่ย $O(1)$

ในปี 1999 Brodnik et al^[9] ได้นำเสนอแถวลำดับพลวัตซึ่งใช้พื้นที่เพียง ${\sqrt {n}}$ ในทุก ๆ ขณะของการดำเนินการ เมื่อ n คือจำนวนข้อมูลในแถวลำดับในขณะนั้น นอกจากนี้ยังพิสูจน์ให้เห็นว่าขั้นตอนวิธีในการสร้างโครงสร้างข้อมูลแถวลำดับพลวัตใด ๆ ก็ต้องใช้พื้นที่อย่างน้อยเทียบเท่ากับแถวลำดับพลวัตของเขาหมด ยิ่งไปกว่านั้น การเพิ่มและลบข้อมูลจากปลายของแถวลำดับพลวัตนี้ยังใช้เวลาคงที่เท่านั้นโดยไม่ต้องมีการถัวเฉลี่ยเลย

ในปี 2002 Bagwell ^[12] นำเสนอว่าสามารถใช้วีลิสต์ในการอิมพลีเมนต์แถวลำดับพลวัตได้

แถวลำดับพลวัตในภาษาต่าง ๆ[แก้]

การอิมพลีเมนต์แถวลำดับพลวัตในภาษาต่าง ๆ

ภาษาซีพลัสพลัส มี std::vector เป็นแถวลำดับพลวัต^[13] และ std::deque เป็นเป็นแถวคอยสองหน้าที่เข้าถึงข้อมูลแบบสุ่มได้^[14]
ภาษาจาวาและดอตเน็ตเฟรมเวิร์ก มี ArrayList^[15] เป็นแถวลำดับพลวัต
ในดอตเน็ตเฟรมเวิร์กเวอร์ชัน 2 มี List<> เป็นแถวลำดับพลวัต
ภาษาสมอลล์ทอล์กมี OrderedCollection เป็นแถวคอยสองหน้าที่เข้าถึงข้อมูลแบบสุ่มได้
ภาษาไพธอนมี list เป็นแถวลำดับพลวัต
ภาษาเดลฟีและภาษาดีมีแถวลำดับพลวัตในแกนหลักของภาษา
ภาษาเอดามี Ada.Containers.Vectors เป็นแถวลำดับพลวัต
ภาษาสคริปต์เช่นภาษาเพิร์ลและภาษารูบี้มีแถวลำดับพลวัตเป็นชนิดข้อมูลพื้นฐาน
เฟรมเวิร์ก หลายระบบปฏิบัติการจำนวนมากมีแถวลำดับพลวัตให้ภาษาซี เช่น CFArray และ CFMutableArray ใน Core Foundation หรือ GArray และ GPtrArray ใน GLib.

อ้างอิง[แก้]

↑ ^1.0 ^1.1 สมชาย ประสิทธิ์จูตระกูล, การออกแบบและวิเคราะห์อัลกอริทึม, พิมพ์ครั้งที่ 4
↑ ^2.0 ^2.1 การอิมพลีเมนต์แถวลำดับพลวัตในภาษาจาวา source code of java.util.ArrayList class from OpenJDK 6.
↑ ^3.0 ^3.1 Goodrich, Michael T.; Tamassia, Roberto (2002), "1.5.2 Analyzing an Extendable Array Implementation", Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, pp. 39–41.
↑ ^4.0 ^4.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "17.4 Dynamic tables". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 416–424. ISBN 0-262-03293-7.
↑ List object implementation from python.org, retrieved 2011-09-27.
↑ Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.
↑ Day 1 Keynote - Bjarne Stroustrup: C++11 Style at GoingNative 2012 on channel9.msdn.com from minute 45 or foil 44
↑ Number crunching: Why you should never, ever, EVER use linked-list in your code again at kjellkod.wordpress.com
↑ ^9.0 ^9.1 Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo
↑ Goodrich, Michael T.; Kloss II, John G. (1999), "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences", Workshop on Algorithms and Data Structures, 1663: 205–216, doi:10.1007/3-540-48447-7_21
↑ Sitarski, Edward (September 1996), "HATs: Hashed array trees", Algorithm Alley, Dr. Dobb's Journal, 21 (11)
↑ Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays, EPFL
↑ STL vector คำอธิบายหลักการทำงานของ vector
↑ STL deque คำอธิบายหลักการทำงานของ deque
↑ Javadoc on ArrayList

แหล่งข้อมูลอื่น[แก้]

NIST Dictionary of Algorithms and Data Structures: Dynamic array
VPOOL - C language implementation of dynamic array.
CollectionSpy — A Java profiler with explicit support for debugging ArrayList- and Vector-related issues.
Open Data Structures - Chapter 2 - Array-Based Lists

[somchai-1] 1.0 ^1.1 สมชาย ประสิทธิ์จูตระกูล, การออกแบบและวิเคราะห์อัลกอริทึม, พิมพ์ครั้งที่ 4

[java_util_ArrayList-2] 2.0 ^2.1 การอิมพลีเมนต์แถวลำดับพลวัตในภาษาจาวา source code of java.util.ArrayList class from OpenJDK 6.

[gt-ad-3] 3.0 ^3.1 Goodrich, Michael T.; Tamassia, Roberto (2002), "1.5.2 Analyzing an Extendable Array Implementation", Algorithm Design: Foundations, Analysis and Internet Examples, Wiley, pp. 39–41.

[clrs-4] 4.0 ^4.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "17.4 Dynamic tables". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 416–424. ISBN 0-262-03293-7.

[5] List object implementation from python.org, retrieved 2011-09-27.

[6] Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.

[7] Day 1 Keynote - Bjarne Stroustrup: C++11 Style at GoingNative 2012 on channel9.msdn.com from minute 45 or foil 44

[8] Number crunching: Why you should never, ever, EVER use linked-list in your code again at kjellkod.wordpress.com

[brodnik-9] 9.0 ^9.1 Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Resizable Arrays in Optimal Time and Space (Technical Report CS-99-09) (PDF), Department of Computer Science, University of Waterloo

[10] Goodrich, Michael T.; Kloss II, John G. (1999), "Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences", Workshop on Algorithms and Data Structures, 1663: 205–216, doi:10.1007/3-540-48447-7_21

[sitarski96-11] Sitarski, Edward (September 1996), "HATs: Hashed array trees", Algorithm Alley, Dr. Dobb's Journal, 21 (11)

[12] Bagwell, Phil (2002), Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays, EPFL

[13] STL vector คำอธิบายหลักการทำงานของ vector

[14] STL deque คำอธิบายหลักการทำงานของ deque

[15] Javadoc on ArrayList

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

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