คำถาม: สร้างแถวลำดับขนาดคงที่ขึ้นมาให้มีขนาดในระดับหนึ่ง เรียกขนาดนี้ว่าอะไร?

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

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

text: ชนิดข้อมูลแถวลำดับ (array) ในภาษาซีแบบดั้งเดิมมีขนาดคงที่และสถิต ซึ่งจะถูกกำหนดตอนแปลโปรแกรม (ในเวลาถัดมา มาตรฐานภาษาซี99 อนุญาตให้สร้างแถวลำดับที่มีความยาวแปรได้) อย่างไรก็ตามแถวลำดับสามารถกำหนดให้จัดสรรเนื้อที่หน่วยความจำขนาดใดก็ได้ขณะทำงาน โดยใช้ฟังก์ชัน codice_187 จากไลบรารีมาตรฐาน แล้วทำให้เป็นแถวลำดับ การทำให้เป็นหนึ่งเดียวระหว่างแถวลำดับและตัวชี้ของภาษาซี ทำให้หมายความว่าแถวลำดับที่แท้จริงและแถวลำดับที่จัดสรรอย่างพลวัตเสมือนใช้แทนกันได้ เนื่องด้วยแถวลำดับเข้าถึงผ่านตัวชี้เสมอ (ในทางปฏิบัติ) การเข้าถึงแถวลำดับจึงไม่มีการตรวจสอบขนาดภายใต้แถวลำดับ แม้ว่าตัวแปลโปรแกรมอาจมีตัวเลือกสำหรับตรวจสอบขอบเขตก็ตาม การใช้งานเกินขอบเขตของแถวลำดับจึงยังคงสามารถเป็นไปได้ ซึ่งเกิดขึ้นค่อนข้างเป็นปกติในรหัสที่เขียนอย่างไม่ระมัดระวัง และนำไปสู่ผลสะท้อนกลับหลายอย่างอาทิ การเข้าถึงหน่วยความจำที่ไม่อนุญาต การทำให้ข้อมูลผิดแปลกไป บัฟเฟอร์ส่วนล้น และสิ่งผิดปรกติขณะทำงาน
title: ภาษาซี

text: ในกรณีที่ทราบว่าแถวลำดับพลวัตจะเก็บข้อมูลเท่าใด สามารถกำหนด"ความจุ"ให้เป็นค่าคงที่หนึ่งที่มีค่ามากกว่าหรือเท่ากับจำนวนของข้อมูล เพื่อรับประกันว่าจะไม่มีปัญหาที่"ขนาดของแถวลำดับพลวัต"มีค่าเกิน"ความจุของแถวลำดับพลวัต" ซึ่งนำไปสู่การเสียเวลาจากการขยายความจุ นอกจากนี้ เนื่องจากความจุเป็นค่าคงที่ พื้นที่ที่สูญเสียไปโดยไม่จำเป็นก็เป็นค่าคงที่เช่นเดียวกัน อย่างไรก็ตาม ในทางปฏิบัติมักจะไม่รู้ถึงจำนวนของข้อมูลที่แน่นอน และการเก็บข้อมูลด้วยแถวลำดับพลวัตที่ความจุเป็นค่าคงที่ในบางสถานการณ์ กลับทำให้สูญเสียพื้นที่โดยไม่จำเป็นอย่างมากมาย เช่นหากมีข้อมูล formula_2 ตัวที่จะนำมาเก็บบนรายการ formula_5 รายการตามคำสั่งที่กำหนด จะได้ว่ารายการหนึ่ง ๆ มีโอกาสที่จะมีข้อมูลมากสุดถึง formula_2 ตัว ดังนั้นหากใช้แถวลำดับพลวัตที่ความจุเป็นค่าคงที่ในการทำรายการทั้ง formula_5 รายการนั้น ก็ต้องหน่วยความจำถึง formula_8 เพื่อรับประกันว่าข้อมูลจะสามารถเก็บได้หมด แต่ถ้าหากใช้แถวลำดับพลวัตที่ความจุไม่เป็นค่าคงที่ ("หัวข้อถัด ๆ ไป") จะใช้หน่วยความจำเพียง formula_9 เท่านั้น
title: แถวลำดับพลวัต

text: เนื่องจากแถวลำดับมีขนาดจำกัดในบางครั้งอาจมีการทำแถวคอยวนรอบ (circular array queue) กล่าวคือบางครั้งแถวคอยอาจมีการเข้าแถวและออกจากแถวสลับกัน ทำให้ดัชนีหัวแถวเลื่อนๆออกไปจนจะตกขอบขวาของแถวลำดับ ทำให้มีเนื้อที่ของแถวลำดับด้านหน้าเหลือไม่ได้ใช้ จึงมีการวนเอาหางแถวมาแทนส่วนหน้าของแถวลำดับ กล่าวคือเมื่อท้ายแถวตกขอบขวาของแถวลำดับ ก็จะมีการเริ่มดัชนีท้ายแถวที่ศูนย์ใหม่และต่อท้ายคิวมาเรื่อยๆ ข้อด้อยของวิธีนี้คือ เมื่อท้ายแถวมาทับหัวแถวอีกครั้งจะตีความไม่ได้ว่าข้อมูลเต็มแถวลำดับหรือว่างกันแน่ จึงอาจใช้ตัวแปรขนาด (size) หรือตัวแปรอื่นๆช่วยในการบอกว่าแถวคอยว่างหรือไม่
title: แถวคอย

text: เมื่อมีการใส่ข้อมูลตัวที่ formula_2 เข้ามาและเกิดการขยายเกิดขึ้น จะมีการจองหน่วยความจำและคัดลอกข้อมูลซึ่งใช้เวลา formula_3 ความจุจะเพิ่มขึ้น "c" เท่า นั่นหมายความว่าเมื่อพิจารณาถึงจำนวนคำสั่งที่ใช้รวมทั้งหมด ความถี่ในการขยายขนาดในแต่ละครั้งจะห่างขึ้นเรื่อย ๆ เป็นอัตราเรขาคณิต ทำให้เมื่อวิเคราะห์แบบถัวเฉลี่ย การเพิ่มข้อมูลที่บางครั้ง formula_1 บางครั้ง formula_3 จะสามารถถัวเฉลี่ยให้ทุก ๆ การดำเนินการกลายเป็น formula_1 ได้ ตารางข้างล่างนี้แสดงถึงการขยายความจุที่ความจุเพิ่มเป็นอัตราเรขาคณิต
title: แถวลำดับพลวัต

text: หลังลำดับหินขั้นแรกถูกทับถมแล้ว หน่วยหินสามารถเปลี่ยนลักษณะ และ/หรือ เปลี่ยนสัณฐานได้ การเปลี่ยนลักษณะโดยทั่วไปเกิดขึ้นเป็นผลของการย่อสั้นลงในแนวนอน การขยายขนาดในแนวนอน หรือการเคลื่อนที่ตามแนวระดับ กฎเกณฑ์โครงสร้างเหล่านี้เกี่ยวข้องอย่างกว้าง ๆ กับแนวแผ่นเปลือกโลกลู่เข้าหากัน แนวแผ่นเปลือกโลกลู่ออกจากกัน และแนวแผ่นเปลือกโลกเคลื่อนที่สวนกันตามลำดับ
title: ธรรมชาติ

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

text: ในวิทยาการคอมพิวเตอร์ แถวลำดับ () คือโครงสร้างข้อมูลที่เป็นรายการอย่างหนึ่ง ข้อมูล (value) จะถูกเก็บบนหน่วยความจำคอมพิวเตอร์ แบบอยู่ติดกันไปเรื่อย ๆ การเข้าถึงข้อมูลสามารถกระทำได้ผ่านดัชนี (index) หรืออาจเรียกว่า คีย์ โดยดัชนีจะเป็นจำนวนเต็มซึ่งบอกถึงลำดับที่ของข้อมูลในแถวลำดับ นอกจากนี้ ค่าของดัชนียังไปจับคู่กับที่อยู่หน่วยความจำ ผ่านสูตรคณิตศาสตร์ ทำให้สามารถเข้าถึงข้อมูลได้
title: แถวลำดับ

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

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

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

text: ในปี 1999 Brodnik et al ได้นำเสนอแถวลำดับพลวัตซึ่งใช้พื้นที่เพียง formula_49 ในทุก ๆ ขณะของการดำเนินการ เมื่อ "n" คือจำนวนข้อมูลในแถวลำดับในขณะนั้น นอกจากนี้ยังพิสูจน์ให้เห็นว่าขั้นตอนวิธีในการสร้างโครงสร้างข้อมูลแถวลำดับพลวัตใด ๆ ก็ต้องใช้พื้นที่อย่างน้อยเทียบเท่ากับแถวลำดับพลวัตของเขาหมด ยิ่งไปกว่านั้น การเพิ่มและลบข้อมูลจากปลายของแถวลำดับพลวัตนี้ยังใช้เวลาคงที่เท่านั้นโดยไม่ต้องมีการถัวเฉลี่ยเลย
title: แถวลำดับพลวัต

text: สถานการณ์เลวร้ายสุดของการดำเนินการบนแถวลำดับพลวัตก็คือการที่ต้องมีการดำเนินการ"เพิ่มความจุ"หรือ"ลดความจุ"บ่อย ๆ ดังนั้นเมื่อพิจารณาในสถานการณ์นี้แล้ว สมมุติให้ขณะนี้มีข้อมูลอยู่ "n" ตัวซึ่ง "n" เป็นความจุของแถวลำดับพลวัตพอดีด้วย เมื่อใส่ข้อมูลเพิ่มอีกหนึ่งตัวจะเกิดจากขยายความจุ "c" เท่า มีความจุเป็น "nc" และมีขนาดเป็น "n" + 1 หากจะต้องการให้เกิดการลดความจุ จะต้องทำให้ขนาดของแถวลำดับพลวัตลดลงไปจนน้อยกว่า formula_30 นั่นคือต้องลบข้อมูลออกไป formula_31 และเพื่อที่เมื่อถัวเฉลี่ยกับการคัดลอกข้อมูลซึ่งใช้เวลา formula_27 แล้ว การดำเนินการแต่ละครั้งจะได้ใช้เวลา formula_28 จึงจะได้ว่าเวลาที่ใช้ในการลบข้อมูลจนเกิดการลดความจุต้องมากกว่าเวลาเชิงเส้น หรือ formula_34
title: แถวลำดับพลวัต

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

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

text: จากตาราง เมื่อมีการใส่ข้อมูลเข้ามาในแถวลำดับพลวัตเป็นจำนวน formula_10 ตัว จะมีการทำงานจากการจองหน่วยความจำและคัดลอกข้อมูลถึง formula_11 ครั้ง เนื่องจาก formula_12 จะได้ว่าการใส่ข้อมูลเข้าไป formula_2 ตัวใช้เวลาถึง formula_14 ถึงแม้วิธีนี้จะเสียเวลามาก แต่พื้นที่ที่สูญเสียไปก็คือส่วนที่ยังไม่ได้ใช้ซึ่งเป็นเพียงค่าคงที่เท่านั้น อย่างไรก็ตาม ในทางปฏิบัติมักจะคำนึงถึงความรวดเร็วของการทำงานมากกว่าพื้นที่ที่สูญเสียไป
title: แถวลำดับพลวัต