โครงสร้างข้อมูลถาวร

ในด้านการคำนวณโครงสร้างข้อมูลถาวรหรือโครงสร้างข้อมูลที่ไม่ชั่วคราวคือโครงสร้างข้อมูลที่รักษาเวอร์ชันก่อนหน้าของตัวเองไว้เสมอเมื่อมีการแก้ไข โครงสร้างข้อมูลดังกล่าวถือว่าเปลี่ยนแปลงไม่ได้ อย่างมีประสิทธิภาพ เนื่องจากการดำเนินการของโครงสร้างจะไม่อัปเดตโครงสร้างในตำแหน่งเดิม (ที่มองเห็นได้) แต่จะสร้างโครงสร้างใหม่ที่ได้รับการอัปเดตเสมอ คำนี้ได้รับการแนะนำในบทความของ Driscoll, Sarnak, Sleator และ Tarjan ในปี 1986 ^{[ 1 ]}

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

โครงสร้างข้อมูลประเภทนี้พบได้ทั่วไปใน การเขียนโปรแกรม เชิงตรรกะและเชิงฟังก์ชัน^{[ 2 ]}เนื่องจากภาษาในกระบวนทัศน์เหล่านั้นไม่สนับสนุน (หรือห้ามโดยสิ้นเชิง) การใช้ข้อมูลที่เปลี่ยนแปลงได้

ความคงอยู่บางส่วนเทียบกับความคงอยู่เต็มรูปแบบ

ในโมเดลการคงอยู่แบบบางส่วน โปรแกรมเมอร์สามารถสอบถามเวอร์ชันก่อนหน้าของโครงสร้างข้อมูลได้ แต่สามารถอัปเดตได้เฉพาะเวอร์ชันล่าสุดเท่านั้น ซึ่งหมายถึงลำดับเชิงเส้นระหว่างแต่ละเวอร์ชันของโครงสร้างข้อมูล^{[ 3 ]}ในโมเดลการคงอยู่แบบสมบูรณ์ ทั้งการอัปเดตและการสอบถามสามารถทำได้กับทุกเวอร์ชันของโครงสร้างข้อมูล ในบางกรณี อาจยอมให้ ลักษณะการทำงานของการสอบถามหรือการอัปเดตเวอร์ชันเก่าของโครงสร้างข้อมูลลดลงได้ เช่นเดียวกับโครงสร้างข้อมูลแบบเชือก [ ^{4 ] นอกจาก}นี้ โครงสร้างข้อมูลยังสามารถเรียกว่าคงอยู่แบบต่อเนื่องได้ หากนอกเหนือจากการคงอยู่แบบสมบูรณ์แล้ว ยังสามารถรวมสองเวอร์ชันของโครงสร้างข้อมูลเดียวกันเข้าด้วยกันเพื่อสร้างเวอร์ชันใหม่ที่ยังคงคงอยู่แบบสมบูรณ์ได้^{[ 5 ]}

เทคนิคการรักษารุ่นก่อนหน้าไว้

ลิขสิทธิ์แบบเขียน

วิธีหนึ่งในการสร้างโครงสร้างข้อมูลถาวรคือการใช้โครงสร้างข้อมูลชั่วคราวที่แพลตฟอร์มจัดหาให้ เช่นอาร์เรย์เพื่อจัดเก็บข้อมูลในโครงสร้างข้อมูลนั้น แล้วคัดลอกโครงสร้างข้อมูลทั้งหมด วิธีนี้ไม่มีประสิทธิภาพ เนื่องจากต้องคัดลอกโครงสร้างข้อมูลพื้นฐานทั้งหมดทุกครั้งที่มีการเขียนข้อมูล ซึ่งอาจนำไปสู่ผลลัพธ์ที่เลวร้ายที่สุด $O(n\cdot m)$ ลักษณะการทำงานสำหรับ การ แก้ไข m ครั้งของอาร์เรย์ขนาดn การจัดการหน่วยความจำ แบบ Copy-on-writeสามารถลดต้นทุนสำหรับการอัปเดตจาก $\Theta (n)$ ถึง $O(Bu)$ โดยที่Bคือขนาดของบล็อกหน่วยความจำ และuคือจำนวนหน้าที่ได้รับการอัปเดตในการดำเนินการหนึ่งครั้ง

ต่อมไขมัน

วิธีการโหนดแบบ "อ้วน" (Fat Node) คือการบันทึกการเปลี่ยนแปลงทั้งหมดที่เกิดขึ้นกับฟิลด์ของโหนดไว้ในตัวโหนดเอง โดยไม่ลบค่าเก่าของฟิลด์เหล่านั้น วิธีนี้จำเป็นต้องอนุญาตให้โหนด "อ้วน" ได้มากเท่าที่ต้องการ กล่าวคือ โหนดแบบอ้วนแต่ละโหนดจะมีข้อมูลและ ฟิลด์ ตัวชี้เหมือนกับโหนดชั่วคราว (Ephemeral Node) พร้อมกับพื้นที่สำหรับค่าฟิลด์เพิ่มเติมจำนวนมาก แต่ละค่าฟิลด์เพิ่มเติมจะมีชื่อฟิลด์ที่เกี่ยวข้องและตราประทับเวอร์ชันซึ่งระบุเวอร์ชันที่ฟิลด์ที่มีชื่อนั้นถูกเปลี่ยนแปลงให้มีค่าตามที่ระบุ นอกจากนี้ โหนดแบบอ้วนแต่ละโหนดยังมีตราประทับเวอร์ชันของตัวเอง ซึ่งระบุเวอร์ชันที่สร้างโหนดนั้นขึ้นมา จุดประสงค์เดียวของการมีตราประทับเวอร์ชันในโหนดคือเพื่อให้แน่ใจว่าแต่ละโหนดมีเพียงค่าเดียวต่อชื่อฟิลด์ต่อเวอร์ชันเท่านั้น เพื่อให้สามารถนำทางผ่านโครงสร้างได้ ค่าฟิลด์ดั้งเดิมแต่ละค่าในโหนดจะมีตราประทับเวอร์ชันเป็นศูนย์

ความซับซ้อนของก้อนไขมัน

การใช้วิธี fat node จะใช้พื้นที่ O(1) สำหรับการแก้ไขแต่ละครั้ง: เพียงแค่จัดเก็บข้อมูลใหม่ การแก้ไขแต่ละครั้งใช้เวลาเพิ่มเติม O(1) ในการจัดเก็บการแก้ไขไว้ที่ส่วนท้ายของประวัติการแก้ไข นี่คือ ขอบเขต เวลาเฉลี่ยโดยสมมติว่าประวัติการแก้ไขถูกจัดเก็บไว้ในอาร์เรย์ ที่ขยายได้ ในเวลาที่เข้าถึงจะต้องค้นหาเวอร์ชันที่ถูกต้องในแต่ละโหนดในขณะที่โครงสร้างถูกสำรวจ หากมีการแก้ไขm ครั้ง การดำเนินการเข้าถึงแต่ละครั้งจะมี $O(\log m)$ ความช้าลงเกิดจากต้นทุนในการค้นหาการแก้ไขที่ใกล้ที่สุดในอาร์เรย์ อีกทางเลือกหนึ่งคือการใช้โครงสร้างต้นไม้แบบ van Emde Boasที่แต่ละโหนด (อาจใช้เวอร์ชันที่มีประสิทธิภาพด้านพื้นที่โดยใช้การแฮช) เพื่อลดเวลาในการเข้าถึง $O(\log \log m)$ โดยแลกกับการเพิ่มเวลาในการอัปเดต $O(\log \log m)$ หากต้องการการคงอยู่ของข้อมูลเพียงบางส่วน เวลาในการอัปเดตสามารถคงไว้ในลำดับขนาดเดิมได้ โดยคำนึงถึงการสุ่มและการคิดค่าเฉลี่ย (เนื่องจากเวลาในการอัปเดตเพียงครั้งเดียวไปยังโหนดขนาดใหญ่สามารถคิดค่าเฉลี่ยได้ตามที่คาดไว้) $O(1)$ ^{[ 6 ]} ).

การคัดลอกเส้นทาง

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

ความซับซ้อนของการคัดลอกเส้นทาง

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

การผสมผสาน

Driscoll, Sarnak, Sleator , Tarjanได้คิดค้น^{[ 1 ]}วิธีการรวมเทคนิคของโหนดอ้วนและการคัดลอกเส้นทาง ซึ่งทำให้การเข้าถึงช้าลง O(1) และค่าใช้จ่ายเฉลี่ย O(1) ในพื้นที่และเวลาต่อการแก้ไข วิธีการของพวกเขาถือว่าโครงสร้างข้อมูลเชื่อมโยงมีตัวชี้ขาเข้าไม่เกินdตัวไปยังแต่ละโหนด โดยที่dเป็นค่าคงที่ที่ทราบ

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

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

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

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

ความซับซ้อนของการรวมกัน

เวลาและพื้นที่สำหรับการปรับเปลี่ยนต้องใช้การวิเคราะห์แบบเฉลี่ย การปรับเปลี่ยนใช้พื้นที่เฉลี่ย O(1) และเวลาเฉลี่ย O(1) เพื่อให้เข้าใจเหตุผล ให้ใช้ฟังก์ชันศักยภาพϕโดยที่ϕ (T) คือจำนวนโหนดที่มีชีวิตที่สมบูรณ์ใน T โหนดที่มีชีวิตของ T คือโหนดที่สามารถเข้าถึงได้จากรากปัจจุบัน ณ เวลาปัจจุบัน (นั่นคือ หลังจากการปรับเปลี่ยนครั้งล่าสุด) โหนดที่มีชีวิตที่สมบูรณ์คือโหนดที่มีชีวิตซึ่งกล่องการปรับเปลี่ยนเต็มแล้ว

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

เมื่อนำทุกอย่างมารวมกัน การเปลี่ยนแปลงของϕคือ Δ ϕ =1 − kดังนั้น อัลกอริทึมจึงใช้พื้นที่ O( k +Δ ϕ )= O(1) และเวลา O( k +Δ ϕ +1) = O(1)

รูปแบบทั่วไปของความคงอยู่

การคัดลอกเส้นทางเป็นหนึ่งในวิธีการง่ายๆ ในการรักษาความคงทนของข้อมูลในโครงสร้างข้อมูลบางอย่าง เช่น ต้นไม้ค้นหาแบบไบนารี การมีกลยุทธ์ทั่วไปในการรักษาความคงทนของข้อมูลที่สามารถใช้ได้กับโครงสร้างข้อมูลใดๆ ก็ตามนั้นเป็นสิ่งที่ดี เพื่อให้บรรลุเป้าหมายนั้น เราพิจารณากราฟแบบมีทิศทาง $G$ เราสมมติว่าแต่ละจุดยอด $v$ ใน $G$ มีจำนวนขอบขาออกคงที่ $c$ ซึ่งแทนด้วยตัวชี้ แต่ละจุดยอดมีป้ายกำกับที่แสดงถึงข้อมูล เราพิจารณาว่าจุดยอดมีจำนวนขอบขาเข้า จำกัด $d ซึ่งเรากำหนดให้เป็น inedges($ $v$ ) เราอนุญาตให้มีการดำเนินการต่างๆ ต่อไปนี้บน $G$

CREATE-NODE(): สร้างจุดยอดใหม่ที่ไม่มีเส้นเชื่อมเข้าหรือออก
CHANGE-EDGE( $v$ , $i$ , $u$ ): เปลี่ยน ขอบ ^ที่ $i$ ของ $v$ ให้ชี้ไปยัง $u$
CHANGE-LABEL( $v$ , $x$ ): เปลี่ยนค่าของข้อมูลที่เก็บไว้ในตัวแปร $v$ เป็น $ค่า x$

การดำเนินการใดๆ ข้างต้นจะดำเนินการในเวลาที่กำหนด และจุดประสงค์ของการแสดงกราฟแบบถาวรคือเพื่อให้สามารถเข้าถึง $G$ เวอร์ชันใดก็ได้ ในเวลาใดก็ได้ ด้วยเหตุนี้ เราจึงกำหนดตารางสำหรับแต่ละจุดยอด $v$ ใน $G$ ตารางนี้ประกอบด้วย คอลัมน์ $c$ คอลัมน์ และ $d+1$ ตารางประกอบด้วยแถวต่างๆ แต่ละแถวนอกจากจะมีตัวชี้สำหรับขอบขาออกแล้ว ยังมีป้ายกำกับที่แสดงข้อมูลที่จุดยอด และเวลา $t$ ที่ดำเนินการนั้นๆ นอกจากนี้ยังมีอาร์เรย์ inedges( $v$ ) ที่เก็บขอบขาเข้าทั้งหมดไปยัง $v$ เมื่อตารางเต็มแล้ว จะมีการสร้างตารางใหม่ที่มี $d+1$ สามารถสร้างแถวใหม่ได้ ตารางเก่าจะกลายเป็นตารางที่ไม่ใช้งาน และตารางใหม่จะกลายเป็นตารางที่ใช้งานอยู่

สร้างโหนด

การเรียกใช้คำสั่ง CREATE-NODE จะสร้างตารางใหม่และกำหนดค่าอ้างอิงทั้งหมดเป็นค่าว่าง (null)

เชนจ์เอดจ์

ถ้าเราสมมติว่ามีการเรียกใช้ CHANGE-EDGE( $v$ , $i$ , $u$ ) แล้ว จะมีสองกรณีที่ต้องพิจารณา

มีแถวว่างอยู่ในตารางของจุดยอด $v$ : ในกรณีนี้ เราจะคัดลอกแถวสุดท้ายในตาราง และเปลี่ยน ขอบ ที่ $i$ ของจุดยอด $v$ ให้ชี้ไปยังจุดยอดใหม่ $u$
ตารางของจุดยอด $v$ เต็มแล้ว: ในกรณีนี้ เราจำเป็นต้องสร้างตารางใหม่ เราคัดลอกแถวสุดท้ายของตารางเก่าไปยังตารางใหม่ เราต้องวนลูปในอาร์เรย์ inedges( $v$ ) เพื่อให้จุดยอดแต่ละจุดในอาร์เรย์ชี้ไปยังตารางใหม่ที่สร้างขึ้น นอกจากนี้ เราต้องเปลี่ยนค่า $v$ ใน inedges(w) สำหรับทุกจุดยอด $w$ ที่มีขอบv $,w$ อยู่ในกราฟ $G$

เปลี่ยนป้ายกำกับ

หลักการทำงานเหมือนกับ CHANGE-EDGE ทุกประการ ยกเว้นว่าแทนที่จะเปลี่ยน ขอบ ^ที่ $i$ ของจุดยอด เราจะเปลี่ยนป้ายกำกับ^ที่ $i แทน$

ประสิทธิภาพของโครงสร้างข้อมูลถาวรแบบทั่วไป

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

การสร้างตารางหนึ่งตารางต้องใช้หนึ่งหน่วยกิต
การเรียกใช้ CREATE-NODE แต่ละครั้งจะได้รับเครดิตสองหน่วย
ทุกครั้งที่โทรไปยัง CHANGE-EDGE จะได้รับเครดิต 1 หน่วย

ระบบการให้เครดิตจะต้องเป็นไปตามเงื่อนไขต่อไปนี้เสมอ: แต่ละแถวของแต่ละตารางที่ใช้งานอยู่จะเก็บเครดิตได้หนึ่งหน่วย และตารางนั้นจะมีจำนวนเครดิตเท่ากับจำนวนแถว ขอให้เราตรวจสอบว่าเงื่อนไขนี้ใช้ได้กับทั้งสามการดำเนินการ ได้แก่ CREATE-NODE, CHANGE-EDGE และ CHANGE-LABEL

คำสั่ง CREATE-NODE: จะใช้เครดิตสองหน่วย หน่วยหนึ่งใช้ในการสร้างตาราง และอีกหน่วยหนึ่งจะมอบให้กับแถวหนึ่งแถวที่เพิ่มเข้าไปในตาราง ดังนั้นจึงรักษารูปแบบคงที่ไว้ได้
CHANGE-EDGE: มีสองกรณีที่ต้องพิจารณา กรณีแรกเกิดขึ้นเมื่อยังมีแถวว่างอย่างน้อยหนึ่งแถวในตาราง ในกรณีนี้จะใช้เครดิตหนึ่งหน่วยสำหรับแถวที่แทรกใหม่ กรณีที่สองเกิดขึ้นเมื่อตารางเต็ม ในกรณีนี้ตารางเก่าจะไม่มีผลใช้งานอีกต่อไป และ $d+1$ เครดิตจะถูกแปลงไปยังตารางใหม่ นอกเหนือจากเครดิตหนึ่งที่ได้รับจากการเรียกใช้ CHANGE-EDGE ดังนั้นโดยรวมแล้วเราจึงมี $d+2$ หน่วยกิต หนึ่งหน่วยจะถูกใช้สำหรับการสร้างตารางใหม่ อีกหนึ่งหน่วยจะถูกใช้สำหรับแถวใหม่ที่เพิ่มเข้าไปในตาราง และหน่วยกิต $ที่$ เหลือจะถูกใช้สำหรับการอัปเดตตารางของจุดยอดอื่นๆ ที่จำเป็นต้องชี้ไปยังตารางใหม่ เราสรุปได้ว่าเงื่อนไขคงที่ยังคงอยู่
CHANGE-LABEL: ใช้งานเหมือนกับ CHANGE-EDGE ทุกประการ

โดยสรุป เราจึงได้ข้อสรุปว่า การมี $n_{1}$ การเรียกใช้ CREATE_NODE และ $n_{2}$ การเรียกใช้ฟังก์ชัน CHANGE_EDGE จะส่งผลให้เกิดการสร้าง $2\cdot n_{1}+n_{2}$ ตาราง เนื่องจากแต่ละตารางมีขนาด $O(d)$ หากไม่คำนึงถึงการเรียกซ้ำ การกรอกข้อมูลลงในตารางจะต้องใช้... $O(dc)$ ดังนั้น ปริมาณงานที่จำเป็นในการดำเนินการตามลำดับจึงถูกจำกัดด้วยจำนวนตารางที่สร้างขึ้นคูณด้วย $O(dc)$ การดำเนินการเข้าถึงแต่ละครั้งสามารถทำได้ใน $O(\log(d))$ และมี การดำเนินการขอบและป้ายกำกับ $m ครั้ง$ ดังนั้นจึงต้องใช้ $m\cdot O(\log(d))$ เราสรุปได้ว่า มีโครงสร้างข้อมูลที่สามารถดำเนินการตาม ลำดับ $n$ ของคำสั่ง CREATE-NODE, CHANGE-EDGE และ CHANGE-LABEL และการดำเนินการเข้าถึงm ครั้งได้ $O(n\cdot dc)+m\cdot O(\log(d))$ .

การประยุกต์ใช้โครงสร้างข้อมูลแบบถาวร

ค้นหาองค์ประกอบถัดไปหรือระบุตำแหน่งจุด

หนึ่งในแอปพลิเคชันที่มีประโยชน์ซึ่งสามารถแก้ไขได้อย่างมีประสิทธิภาพโดยใช้โครงสร้างข้อมูลแบบคงอยู่คือ การค้นหาองค์ประกอบถัดไป (Next Element Search) สมมติว่ามีส่วนของเส้นตรงที่ไม่ตัดกัน $n เส้น ซึ่งขนานกับแกน x เราต้องการสร้างโครงสร้างข้อมูลที่สามารถสอบถามจุด$ $p$ และส่งคืนส่วนของเส้นตรงที่อยู่เหนือ $p$ (ถ้ามี) เราจะเริ่มต้นด้วยการแก้ปัญหาการค้นหาองค์ประกอบถัดไปโดยใช้วิธีการแบบง่าย จากนั้นเราจะแสดงวิธีการแก้ปัญหาโดยใช้วิธีโครงสร้างข้อมูลแบบคงอยู่

วิธีการแบบง่ายๆ

เราเริ่มต้นด้วยส่วนของเส้นตรงแนวตั้งที่เริ่มต้นจากอนันต์ และเราลากส่วนของเส้นตรงจากซ้ายไปขวา เราหยุดชั่วคราวทุกครั้งที่พบจุดสิ้นสุดของส่วนของเส้นตรงเหล่านี้ เส้นแนวตั้งจะแบ่งระนาบออกเป็นแถบแนวตั้ง ถ้ามี ส่วนของเส้นตรง $n$ เส้น เราก็จะได้ $2\cdot n+1$ แถบแนวตั้ง เนื่องจากแต่ละส่วนมีมีจุดปลาย 2จุด ไม่มีส่วนใดเริ่มต้นและสิ้นสุดบนแถบ ทุกส่วนจะไม่สัมผัสกับแถบหรือจะตัดผ่านแถบโดยสมบูรณ์ เราสามารถคิดว่าส่วนต่างๆ เหล่านั้นเป็นวัตถุที่เรียงลำดับจากบนลงล่าง สิ่งที่เราสนใจคือจุดที่เรากำลังดูอยู่นั้นอยู่ในตำแหน่งใดในลำดับนี้ เราเรียงลำดับจุดปลายของส่วนต่างๆ ตาม พิกัด $x$ สำหรับแต่ละแถบ $s_{i}$ เราจัดเก็บเซกเมนต์ย่อยที่ตัดกัน $s_{i}$ ในพจนานุกรม เมื่อเส้นแนวตั้งกวาดไปตามส่วนของเส้นตรง เมื่อใดก็ตามที่มันผ่านจุดปลายด้านซ้ายของส่วนของเส้นตรง เราจะเพิ่มส่วนนั้นลงในพจนานุกรม เมื่อมันผ่านจุดปลายด้านขวาของส่วนของเส้นตรง เราจะลบส่วนนั้นออกจากพจนานุกรม ที่จุดปลายแต่ละจุด เราจะบันทึกสำเนาของพจนานุกรม และจัดเก็บสำเนาทั้งหมดโดยเรียงลำดับตาม พิกัด $x$ ดังนั้นเราจึงมีโครงสร้างข้อมูลที่สามารถตอบคำถามใดๆ ได้ ในการค้นหาส่วนของเส้นตรงที่อยู่เหนือจุด $p$ เราสามารถดู พิกัด $x$ ของ $p$ เพื่อทราบว่ามันเป็นของสำเนาหรือแถบใด จากนั้นเราสามารถดู พิกัด $y$ เพื่อค้นหาส่วนของเส้นตรงที่อยู่เหนือมัน ดังนั้นเราจึงต้องการการค้นหาแบบไบนารีสองครั้ง ครั้งหนึ่งสำหรับ พิกัด $x$ เพื่อค้นหาแถบหรือสำเนา และอีกครั้งสำหรับ พิกัด $y$ เพื่อค้นหาส่วนของเส้นตรงที่อยู่เหนือมัน ดังนั้นเวลาในการค้นหาจึงใช้เวลา $O(\log(n))$ ในโครงสร้างข้อมูลนี้ พื้นที่จัดเก็บเป็นปัญหา เนื่องจากหากเราสมมติว่าส่วนต่างๆ ถูกจัดโครงสร้างในลักษณะที่แต่ละส่วนเริ่มต้นก่อนจุดสิ้นสุดของส่วนอื่นๆ พื้นที่ที่จำเป็นสำหรับการสร้างโครงสร้างโดยใช้วิธีการแบบง่ายๆ จะเป็น $O(n^{2})$ มาดูกันว่าเราจะสร้างโครงสร้างข้อมูลถาวรอีกแบบหนึ่งที่มีเวลาในการค้นหาข้อมูลเท่าเดิม แต่ใช้พื้นที่จัดเก็บข้อมูลได้ดีกว่าได้อย่างไร

วิธีการโครงสร้างข้อมูลแบบถาวร

เราจะสังเกตได้ว่าสิ่งที่ใช้เวลานานจริงๆ ในโครงสร้างข้อมูลที่ใช้ในวิธีการแบบง่ายๆ ก็คือ ทุกครั้งที่เราย้ายจากแถบหนึ่งไปยังอีกแถบหนึ่ง เราจำเป็นต้องบันทึกภาพของโครงสร้างข้อมูลที่เราใช้เพื่อรักษาลำดับการเรียงให้คงที่ เราจะสังเกตได้ว่าเมื่อเราได้ส่วนที่ตัดกันแล้ว $s_{i}$ เมื่อเราย้ายไป $s_{i+1}$ สิ่งหนึ่งจะออกไป หรืออีกสิ่งหนึ่งจะเข้ามา ถ้าความแตกต่างระหว่างสิ่งที่อยู่ด้านในคือ... $s_{i}$ และมีอะไรอยู่ข้างใน $s_{i+1}$ หากมีการเพิ่มหรือลบข้อมูลเพียงครั้งเดียว การคัดลอกทุกอย่างจากที่เดิมจึงไม่ใช่ความคิดที่ดี $s_{i}$ ถึง $s_{i+1}$ เคล็ดลับก็คือ เนื่องจากสำเนาแต่ละชุดจะแตกต่างจากชุดก่อนหน้าเพียงแค่การแทรกหรือลบเพียงหนึ่งรายการ ดังนั้นเราจึงจำเป็นต้องคัดลอกเฉพาะส่วนที่เปลี่ยนแปลงเท่านั้น สมมติว่าเรามีต้นไม้ที่มีรากอยู่ที่ $T$ เมื่อเราแทรกคีย์ $k$ เข้าไปในต้นไม้ เราจะสร้างใบใหม่ที่มี $k$ การหมุนเพื่อปรับสมดุลต้นไม้จะแก้ไขเฉพาะโหนดของเส้นทางจาก $k$ ไปยัง $T$ เท่านั้น ก่อนที่จะแทรกคีย์ $k$ เข้าไปในต้นไม้ เราจะคัดลอกโหนดทั้งหมดบนเส้นทางจาก $k$ ไปยัง $T$ ตอนนี้เรามีต้นไม้ 2 เวอร์ชัน เวอร์ชันดั้งเดิมที่ไม่มี $k$ และเวอร์ชันใหม่ที่มี $k$ และรากของต้นไม้ใหม่นี้เป็นสำเนาของรากของ $T$ เนื่องจาก1การคัดลอกเส้นทางจาก $k$ ไปยัง $T$ ไม่ได้เพิ่มเวลาในการแทรกมากกว่าค่าคงที่ ดังนั้นการแทรกในโครงสร้างข้อมูลถาวรจึงใช้เวลา $O(\log(n))$ เวลา สำหรับการลบ เราต้องหาว่าโหนดใดบ้างที่จะได้รับผลกระทบจากการลบ สำหรับแต่ละโหนด $v$ ที่ได้รับผลกระทบจากการลบ เราจะคัดลอกเส้นทางจากรากไปยัง $v$ ซึ่งจะทำให้ได้ต้นไม้ใหม่ที่มีรากเป็นสำเนาของรากของต้นไม้เดิม จากนั้นเราจะทำการลบในต้นไม้ใหม่ เราจะได้ต้นไม้ 2 เวอร์ชัน เวอร์ชันเดิมที่มี $k$ และเวอร์ชันใหม่ที่ไม่มี $k$ เนื่องจากการลบใดๆ จะแก้ไขเฉพาะเส้นทางจากรากไปยัง $v$ และอัลกอริทึมการลบที่เหมาะสมใดๆ ก็ทำงานได้ในเวลาไม่นาน $O(\log(n))$ ดังนั้นการลบในโครงสร้างข้อมูลถาวรจึงใช้เวลา $O(\log(n))$ ทุกลำดับของการแทรกและการลบจะก่อให้เกิดลำดับของพจนานุกรม เวอร์ชัน หรือโครงสร้างแบบต้นไม้ $S_{1},S_{2},\dots S_{i}$ โดยที่แต่ละ $S_{i}$ เป็นผลมาจากการดำเนินการ $S_{1},S_{2},\dots S_{i}$ ถ้าแต่ละ $S_{i}$ ประกอบด้วย องค์ประกอบ $m$ จากนั้นการค้นหาในแต่ละองค์ประกอบ $S_{i}$ นำไป $O(\log(m))$ ด้วยโครงสร้างข้อมูลแบบถาวรนี้ เราสามารถแก้ปัญหาการค้นหาองค์ประกอบถัดไปได้ใน $O(\log(n))$ เวลาในการสอบถามและ $O(n\cdot \log(n))$ พื้นที่แทนที่จะเป็น $O(n^{2})$ ด้านล่างนี้ คือ ซอร์สโค้ดตัวอย่างที่เกี่ยวข้องกับปัญหาการค้นหาต่อไปนี้

ตัวอย่างของโครงสร้างข้อมูลแบบถาวร

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

โครงสร้างข้อมูลอ้างอิงทั่วไปหลายอย่าง เช่นต้นไม้แดง-ดำ [ ⁷^]สแต็ก [ ⁸^]^และเทรป [ ⁹^]^{สามารถ ปรับเปลี่ยนเพื่อสร้างเวอร์ชันถาวรได้อย่างง่ายดาย ส่วน}^{โครงสร้าง} อื่นๆ บางอย่างต้องใช้ความพยายามมากขึ้นเล็กน้อย เช่นคิวดีคิวและส่วนขยายต่างๆ รวมถึงมินเดคิว (ซึ่งมีการดำเนินการเพิ่มเติมO (1) คือ minที่ส่งคืนองค์ประกอบขั้นต่ำ) และเดคิวแบบเข้าถึงแบบสุ่ม (ซึ่งมีการดำเนินการเพิ่มเติมคือการเข้าถึงแบบสุ่มที่มีความซับซ้อนแบบย่อยเชิงเส้น ส่วนใหญ่เป็นแบบลอการิทึม)

โครงสร้างข้อมูลถาวรซึ่งอิงตามโครงสร้างที่ไม่สามารถเปลี่ยนแปลงได้ ("ฟังก์ชันบริสุทธิ์") ควรถูกนำมาเปรียบเทียบกับโครงสร้างที่ใช้การอัปเดตแบบทำลายล้าง (การกลายพันธุ์) และทำให้คงอยู่ถาวรโดยใช้เทคนิคการคัดลอกโหนดหรือเส้นทางแบบอ้วน (fat node or path copying) ดังที่ได้อธิบายไว้ข้างต้น

รายการเชื่อมโยง

รายการเชื่อมโยงเดี่ยวเป็นโครงสร้างข้อมูลพื้นฐานในภาษาฟังก์ชัน^{[ 10 ]} ภาษาที่ได้มาจาก MLบางภาษา เช่นHaskellเป็นภาษาฟังก์ชันโดยสมบูรณ์ เนื่องจากเมื่อโหนดในรายการได้รับการจัดสรรแล้ว จะไม่สามารถแก้ไขได้ ทำได้เพียงคัดลอก อ้างอิง หรือถูกทำลายโดยตัวเก็บขยะเมื่อไม่มีสิ่งใดอ้างอิงถึง (โปรดทราบว่า ML เองไม่ใช่ภาษาฟังก์ชันโดยสมบูรณ์ แต่รองรับการดำเนินการรายการแบบไม่ทำลาย ซึ่งเป็นความจริงในภาษาฟังก์ชันLisp (LISt Processing) เช่น SchemeและRacketด้วย)

พิจารณารายชื่อทั้งสองรายการต่อไปนี้:

xs = [0, 1, 2] ys = [3, 4, 5]

สิ่งเหล่านี้จะถูกแทนไว้ในความทรงจำด้วย:

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

ตอนนี้เราจะรวมสองรายการเข้าด้วยกัน:

zs = xs ++ ys

ส่งผลให้โครงสร้างหน่วยความจำเป็นดังนี้:

โปรดสังเกตว่าโหนดในรายการxsถูกคัดลอกแล้ว แต่โหนดในรายการนั้นysใช้ร่วมกัน ดังนั้น รายการเดิม ( xsและys) จึงยังคงอยู่และไม่ได้ถูกแก้ไข

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

ต้นไม้

พิจารณาต้นไม้ค้นหาไบนารี [ ¹⁰^]โดยที่ทุกโหนดในต้นไม้มีเงื่อนไขคงที่แบบเรียกซ้ำ^ว่าโหนดย่อยทั้งหมดที่อยู่ในซับทรีด้านซ้ายจะมีค่าที่น้อยกว่าหรือเท่ากับค่าที่เก็บไว้ในโหนด และโหนดย่อยที่อยู่ในซับทรีด้านขวาจะมีค่าที่มากกว่าค่าที่เก็บไว้ในโหนด

ตัวอย่างเช่น ชุดข้อมูล

xs = [a, b, c, d, f, g, h]

อาจแสดงได้ด้วยแผนผังต้นไม้ค้นหาแบบไบนารี ดังต่อไปนี้:

ฟังก์ชันที่แทรกข้อมูลลงในต้นไม้ไบนารีและรักษาสภาพคงที่ไว้คือ:

fun insert ( x , E ) = T ( E , x , E ) | insert ( x , s as T ( a , y , b )) = if x < y then T ( insert ( x , a ), y , b ) else if x > y then T ( a , y , insert ( x , b )) else s

หลังจากดำเนินการเสร็จสิ้น

ys = แทรก ("e", xs)

ผลลัพธ์ที่ได้คือการกำหนดค่าดังต่อไปนี้:

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

อาร์เรย์แฮชถาวรที่แมปกับไทร

ไทรที่แมปด้วยอาร์เรย์แฮชแบบถาวรเป็นรูปแบบเฉพาะของไทรที่แมปด้วยอาร์เรย์แฮชซึ่งจะรักษาเวอร์ชันก่อนหน้าของตัวเองไว้ในการอัปเดตใดๆ มักใช้เพื่อใช้งานโครงสร้างข้อมูลแผนที่แบบถาวรทั่วไป^{[ 11 ]}

โครงสร้างข้อมูล Hash array mapped tries ได้รับการอธิบายครั้งแรกในบทความปี 2001 โดยPhil Bagwellในชื่อ "Ideal Hash Trees" บทความนี้นำเสนอตาราง Hash ที่เปลี่ยนแปลงได้ โดยที่ "เวลาในการแทรก ค้นหา และลบมีขนาดเล็กและคงที่ ไม่ขึ้นอยู่กับขนาดของชุดคีย์ การดำเนินการเป็น O(1) สามารถรับประกันเวลาที่เลวร้ายที่สุดสำหรับการแทรก ค้นหา และการลบได้ และการค้นหาที่พลาดมีค่าใช้จ่ายน้อยกว่าการค้นหาที่สำเร็จ" ^{[ 12 ]}ต่อมาโครงสร้างข้อมูลนี้ได้รับการปรับปรุงโดยRich Hickeyให้มีความคงทนอย่างสมบูรณ์เพื่อใช้ในภาษาการเขียนโปรแกรมClojure ^{[ 13 ]}

ในเชิงแนวคิด Hash Array Mapped Tries ทำงานคล้ายกับ ต้นไม้ทั่วไปตรงที่จัดเก็บโหนดแบบลำดับชั้นและดึงข้อมูลโดยการติดตามเส้นทางลงไปยังองค์ประกอบเฉพาะ ความแตกต่างที่สำคัญคือ Hash Array Mapped Tries จะใช้ฟังก์ชันแฮชเพื่อแปลงคีย์การค้นหาเป็นจำนวนเต็ม (โดยปกติคือ 32 หรือ 64 บิต) ก่อน จากนั้นจึงกำหนดเส้นทางลงต้นไม้โดยใช้สไลซ์ของการแสดงเลขฐานสองของจำนวนเต็มนั้นเพื่อจัดทำดัชนีลงในอาร์เรย์แบบเบาบางในแต่ละระดับของต้นไม้ โหนดใบของต้นไม้จะทำงานคล้ายกับบัคเก็ตที่ใช้ในการสร้างตารางแฮชและอาจมีหรือไม่มีตัวเลือกหลายตัวขึ้นอยู่กับการชนกันของแฮช^{[ 11 ]}

การใช้งานส่วนใหญ่ของไทรที่แมปด้วยอาร์เรย์แฮชแบบถาวรจะใช้ปัจจัยการแตกกิ่งที่ 32 ในการใช้งาน ซึ่งหมายความว่าในทางปฏิบัติ แม้ว่าการแทรก การลบ และการค้นหาในไทรที่แมปด้วยอาร์เรย์แฮชแบบถาวรจะมีความซับซ้อนในการคำนวณO (log n ) แต่สำหรับแอปพลิเคชันส่วนใหญ่แล้วจะใช้เวลาคงที่อย่างมีประสิทธิภาพ เนื่องจากจะต้องมีจำนวนรายการมากเป็นพิเศษจึงจะทำให้การดำเนินการใดๆ ใช้เวลามากกว่าสิบสองขั้นตอน^{[ 14 ]}

การใช้งานในภาษาโปรแกรม

ฮัสเคลล์

Haskell เป็นภาษาฟังก์ชันบริสุทธิ์ดังนั้นจึงไม่อนุญาตให้มีการเปลี่ยนแปลง ดังนั้นโครงสร้างข้อมูลทั้งหมดในภาษานี้จึงคงอยู่ เนื่องจากเป็นไปไม่ได้ที่จะไม่รักษาสถานะก่อนหน้าของโครงสร้างข้อมูลด้วยความหมายเชิงฟังก์ชัน^{[ 15 ]} ทั้งนี้เพราะการเปลี่ยนแปลงใด ๆต่อโครงสร้างข้อมูลที่จะทำให้เวอร์ชันก่อนหน้าของโครงสร้างข้อมูลไม่ถูกต้องจะละเมิดความโปร่งใสของการอ้างอิง

ในไลบรารีมาตรฐาน Haskell มีการใช้งานแบบถาวรที่มีประสิทธิภาพสำหรับรายการเชื่อมโยง^{[ 16 ]}แผนที่ (ใช้งานเป็นต้นไม้ที่มีขนาดสมดุล) ^{[ 17 ]}และเซต^{[ 18 ]}และอื่นๆ^{[ 19 ]}

โคลจูร์

เช่นเดียวกับภาษาโปรแกรมหลายภาษาใน ตระกูล Lisp , Clojure มีการใช้งานรายการเชื่อมโยง แต่แตกต่างจากภาษาถิ่นอื่นๆ การใช้งานรายการเชื่อมโยงของ Clojure มีการบังคับให้คงอยู่แทนที่จะคงอยู่ตามธรรมเนียม^{[ 20 ]} Clojure ยังมีการใช้งานเวกเตอร์ แผนที่ และเซตที่คงอยู่ได้อย่างมีประสิทธิภาพโดยอิงจากไทรที่แมปกับอาร์เรย์แฮชที่คงอยู่ โครงสร้างข้อมูลเหล่านี้ใช้ส่วนที่เป็นการอ่านอย่างเดียวที่จำเป็นของ เฟรมเวิร์กคอลเลกชัน ของJava ^{[ 21 ]}

นักออกแบบภาษา Clojure สนับสนุนการใช้โครงสร้างข้อมูลถาวรมากกว่าโครงสร้างข้อมูลที่เปลี่ยนแปลงได้ เนื่องจากมีความหมายของค่าซึ่งให้ประโยชน์ในการทำให้สามารถแบ่งปันได้อย่างอิสระระหว่างเธรดด้วยนามแฝงราคาถูก สร้างได้ง่าย และไม่ขึ้นกับภาษา^{[ 22 ]}

โครงสร้างข้อมูลเหล่านี้เป็นพื้นฐานของการสนับสนุนการประมวลผลแบบขนาน ของ Clojure เนื่องจากช่วยให้สามารถลองดำเนินการซ้ำได้ง่ายเพื่อหลีกเลี่ยงการแข่งขันข้อมูลและความหมายของการเปรียบเทียบและการสลับ อะตอมิก ^{[ 23 ]}

ต้นเอล์ม

ภาษาโปรแกรม Elmเป็นภาษาเชิงฟังก์ชันล้วนๆ เช่นเดียวกับ Haskell ซึ่งทำให้โครงสร้างข้อมูลทั้งหมดมีความคงทนโดยจำเป็น ประกอบด้วยการใช้งานรายการเชื่อมโยงแบบคงทน รวมถึงอาร์เรย์ พจนานุกรม และเซตแบบคงทน^{[ 24 ]}

Elm ใช้ การใช้งาน virtual DOM แบบกำหนดเอง ที่ใช้ประโยชน์จากลักษณะการคงอยู่ของข้อมูล Elm ณ ปี 2016 นักพัฒนาของ Elm รายงานว่า virtual DOM นี้ช่วยให้ภาษา Elm สามารถแสดงผล HTML ได้เร็วกว่าเฟรมเวิร์กJavaScript ยอดนิยม ^{อย่าง} React , EmberและAngular ^[²⁵ ]

ชวา

ภาษาการเขียนโปรแกรม Javaไม่ได้เป็นภาษาเชิงฟังก์ชันโดยเฉพาะ ถึงกระนั้น แพ็กเกจหลักของ JDK java.util.concurrent ก็มี CopyOnWriteArrayList และ CopyOnWriteArraySet ซึ่งเป็นโครงสร้างแบบถาวรที่นำไปใช้โดยใช้เทคนิค copy-on-write อย่างไรก็ตาม การใช้งานแผนที่แบบพร้อมกันทั่วไปใน Java คือ ConcurrentHashMap ซึ่งไม่ใช่แบบถาวร คอลเลกชันแบบถาวรอย่างสมบูรณ์มีอยู่ในไลบรารีของบุคคลที่สาม^{[ 26 ]}หรือภาษา JVM อื่นๆ

โค้ด JavaScript

Reactซึ่งเป็นเฟรมเวิร์กฟรอนต์เอนด์ JavaScript ยอดนิยมมักใช้ร่วมกับระบบจัดการสถานะที่ใช้สถาปัตยกรรม Flux [ ²⁷^]^[²⁸^]ซึ่งการใช้งานที่เป็นที่นิยมอย่างหนึ่งคือ^{ไลบรารี} JavaScript Reduxไลบรารี Redux ได้รับแรงบันดาลใจจากรูปแบบการจัดการสถานะที่ใช้ในภาษาการเขียนโปรแกรม Elm ซึ่งหมายความว่ามันกำหนดให้ผู้ใช้ต้องจัดการข้อมูลทั้งหมดเป็นแบบถาวร^[²⁹^]ด้วยเหตุนี้ โครงการ Redux จึงแนะนำให้ผู้ใช้ใช้ไลบรารีสำหรับโครงสร้างข้อมูลถาวรที่มีประสิทธิภาพและบังคับใช้ได้ในบางกรณี ซึ่งมีรายงานว่าช่วยให้มีประสิทธิภาพมากกว่าเมื่อเปรียบเทียบหรือคัดลอกวัตถุ JavaScript ทั่วไป^[³⁰^]

Immutable.js เป็นหนึ่งในไลบรารีโครงสร้างข้อมูลถาวรที่ใช้โครงสร้างข้อมูลที่ Clojure และ Scala ทำให้ใช้งานได้และเป็นที่นิยม^{[ 31 ]}เอกสารของ Redux กล่าวถึงไลบรารีนี้ว่าเป็นหนึ่งในไลบรารีที่สามารถบังคับให้ข้อมูลไม่เปลี่ยนแปลงได้^{[ 30 ]} Mori.js นำโครงสร้างข้อมูลที่คล้ายกับใน Clojure มาใช้ใน JavaScript ^{[ 32 ]} Immer.js นำเสนอวิธีการที่น่าสนใจโดย "สร้างสถานะที่ไม่เปลี่ยนแปลงถัดไปโดยการเปลี่ยนแปลงสถานะปัจจุบัน" ^{[ 33 ]} Immer.js ใช้ JavaScript object ดั้งเดิมและโครงสร้างข้อมูลถาวรที่ไม่มีประสิทธิภาพ ซึ่งอาจทำให้เกิดปัญหาด้านประสิทธิภาพเมื่อขนาดข้อมูลมีขนาดใหญ่

บทนำ

เงื่อนไข Prolog นั้นไม่สามารถเปลี่ยนแปลงได้โดยธรรมชาติ ดังนั้นโครงสร้างข้อมูลจึงมักเป็นโครงสร้างข้อมูลถาวร ประสิทธิภาพขึ้นอยู่กับการแบ่งปันและการเก็บขยะที่ระบบ Prolog นำเสนอ^{[ 34 ]}การขยายเงื่อนไข Prolog ที่ไม่ใช่พื้นฐานนั้นไม่สามารถทำได้เสมอไปเนื่องจากการระเบิดของพื้นที่ค้นหา เป้าหมายที่ล่าช้าอาจช่วยบรรเทาปัญหานี้ได้

อย่างไรก็ตาม ระบบ Prolog บางระบบก็มีการดำเนินการทำลายล้าง เช่น setarg/3 ซึ่งอาจมีหลายรูปแบบ ทั้งแบบมี/ไม่มีการคัดลอก และมี/ไม่มีการย้อนกลับการเปลี่ยนแปลงสถานะ มีบางกรณีที่ใช้ setarg/3 เพื่อประโยชน์ของการจัดหาเลเยอร์การประกาศใหม่ เช่น ตัวแก้ข้อจำกัด^{[ 35 ]}

สกาล่า

ภาษาการเขียนโปรแกรม Scala ส่งเสริมการใช้โครงสร้างข้อมูลถาวรสำหรับการนำโปรแกรมไปใช้โดยใช้ "รูปแบบเชิงวัตถุ-ฟังก์ชัน" ^{[ 36 ]} Scala มีการใช้งานโครงสร้างข้อมูลถาวรหลายอย่าง รวมถึงรายการเชื่อมโยงต้นไม้แดง-ดำตลอดจนไทรที่แมปอาร์เรย์แฮชถาวรตามที่แนะนำใน Clojure ^{[ 37 ]}

การเก็บขยะ

เนื่องจากโครงสร้างข้อมูลแบบถาวรมักถูกนำไปใช้ในลักษณะที่เวอร์ชันต่อเนื่องของโครงสร้างข้อมูลใช้หน่วยความจำพื้นฐานร่วมกัน^{[ 38 ]}การใช้งานโครงสร้างข้อมูลดังกล่าวอย่างเหมาะสมโดยทั่วไปจึงต้องการ ระบบ การเก็บขยะอัตโนมัติ บางรูปแบบ เช่นการนับการอ้างอิงหรือการทำเครื่องหมายและกวาด [ ^{39 ] ใน}บางแพลตฟอร์มที่ใช้โครงสร้างข้อมูลแบบถาวร การไม่ใช้การเก็บขยะเป็นทางเลือกหนึ่ง ซึ่งแม้ว่าการทำเช่นนั้นอาจนำไปสู่การรั่วไหลของหน่วยความจำแต่ในบางกรณีอาจส่งผลดีต่อประสิทธิภาพโดยรวมของแอปพลิเคชันได้^{[ 40 ]}

ดูเพิ่มเติม

ลิงก์ภายนอก

การใช้งาน Persistent Red-Black Tree ในรูปแบบ Java ที่มีน้ำหนักเบา
โครงสร้างการจัดเก็บข้อมูลถาวรที่มีประสิทธิภาพใน C# เก็บถาวรเมื่อ 2017-12-21 ที่Wayback Machine
PersistentBST บนGitHub - คลังเก็บโค้ดบน GitHub ที่รวบรวมการใช้งาน BST แบบถาวรโดยใช้ Fat Nodes, Copy-on-Write และเทคนิคการคัดลอกเส้นทาง หากต้องการใช้งาน BST แบบถาวร เพียงแค่โคลนคลังเก็บโค้ดและทำตามคำแนะนำในไฟล์ README

[ 1 ]

[ 2 ]

[ 3 ]

4 ] นอกจาก

[ 5 ]

[ 6 ]

7

8

9

[ 10 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

อย่าง

[ 26 ]

27

[

[

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

39 ] ใน

[ 40 ]