โครงสร้างข้อมูลแบบย้อนหลัง
ในวิทยาการคอมพิวเตอร์โครงสร้างข้อมูลแบบย้อนหลังคือโครงสร้างข้อมูลที่สนับสนุนการแก้ไขที่มีประสิทธิภาพต่อลำดับการดำเนินการที่ได้ดำเนินการกับโครงสร้าง การแก้ไขเหล่านี้สามารถอยู่ในรูปแบบของการแทรก การลบ หรือการอัปเดตแบบย้อนหลังของการดำเนินการที่ดำเนินการในช่วงเวลาใดเวลาหนึ่งในอดีต[ 1 ]
การประยุกต์ใช้โครงสร้างข้อมูลแบบย้อนหลังบางประการ
ในโลกแห่งความเป็นจริง มีหลายกรณีที่บุคคลต้องการแก้ไขการดำเนินการในอดีตจากลำดับการดำเนินการต่างๆ ตัวอย่างการใช้งานบางส่วนมีดังต่อไปนี้:
- การแก้ไขข้อผิดพลาด : ป้อนข้อมูลไม่ถูกต้อง ข้อมูลควรได้รับการแก้ไข และผลกระทบรองทั้งหมดที่เกิดจากข้อมูลที่ไม่ถูกต้องควรถูกกำจัดออกไป
- ข้อมูลผิดพลาด : เมื่อทำงานกับระบบขนาดใหญ่ โดยเฉพาะอย่างยิ่งระบบที่เกี่ยวข้องกับการถ่ายโอนข้อมูลอัตโนมัติจำนวนมาก การเกิดข้อมูลผิดพลาดไม่ใช่เรื่องแปลก ตัวอย่างเช่น สมมติว่าเซ็นเซอร์ตัวใดตัวหนึ่งในเครือข่ายตรวจอากาศทำงานผิดปกติและเริ่มรายงานข้อมูลที่ไม่ถูกต้องหรือไร้ประโยชน์ วิธีแก้ปัญหาที่ดีที่สุดคือการลบข้อมูลทั้งหมดที่เซ็นเซอร์นั้นสร้างขึ้นนับตั้งแต่เกิดความผิดปกติ พร้อมทั้งลบผลกระทบทั้งหมดที่ข้อมูลผิดพลาดเหล่านั้นมีต่อระบบโดยรวมด้วย
- การกู้คืนข้อมูล : สมมติว่าเซ็นเซอร์ฮาร์ดแวร์เสียหาย แต่ตอนนี้ได้รับการซ่อมแซมแล้ว และสามารถอ่านข้อมูลจากเซ็นเซอร์ได้ เราต้องการที่จะสามารถป้อนข้อมูลกลับเข้าไปในระบบราวกับว่าเซ็นเซอร์ไม่เคยเสียหายมาก่อน
- การบิดเบือนอดีต : การเปลี่ยนแปลงอดีตอาจเป็นประโยชน์ในกรณีของการควบคุมความเสียหาย และโครงสร้างข้อมูลย้อนหลังถูกออกแบบมาเพื่อการบิดเบือนอดีตโดยเจตนา
เวลาในฐานะมิติเชิงพื้นที่
เราไม่สามารถพิจารณาเวลาเป็นมิติเชิงพื้นที่เพิ่มเติมได้ เพื่อแสดงให้เห็นภาพ ลองสมมติว่าเราแมปมิติของเวลาลงบนแกนของพื้นที่ โครงสร้างข้อมูลที่เราจะใช้เพื่อเพิ่มมิติเวลาเชิงพื้นที่คือ มินฮีป (min-heap) ให้แกน y แทนค่าคีย์ของรายการภายในฮีป และแกน x คือมิติเวลาเชิงพื้นที่ หลังจากดำเนินการแทรกและลบค่าต่ำสุดหลายครั้ง (ทั้งหมดทำโดยไม่ย้อนหลัง) มินฮีปของเราจะปรากฏดังรูปที่ 1 ทีนี้ลองสมมติว่าเราแทรกศูนย์เข้าไปที่จุดเริ่มต้นของรายการดำเนินการแบบย้อนหลัง มินฮีปของเราจะปรากฏดังรูปที่ 2 สังเกตว่าการดำเนินการเพียงครั้งเดียวทำให้เกิดผลกระทบต่อเนื่องซึ่งส่งผลต่อโครงสร้างข้อมูลทั้งหมด ดังนั้นเราจะเห็นได้ว่าถึงแม้เวลาจะสามารถวาดเป็นมิติเชิงพื้นที่ได้ แต่การดำเนินการที่เกี่ยวข้องกับเวลาจะสร้างความสัมพันธ์ที่ส่งผลกระทบเป็นวงกว้างเมื่อมีการแก้ไขที่เกี่ยวข้องกับเวลา
การเปรียบเทียบกับความคงทน
เมื่อมองแวบแรก แนวคิดของโครงสร้างข้อมูลแบบย้อนหลังดูคล้ายกับโครงสร้างข้อมูลแบบถาวร มาก เนื่องจากทั้งสองคำนึงถึงมิติของเวลา ความแตกต่างที่สำคัญระหว่างโครงสร้างข้อมูลแบบถาวรและโครงสร้างข้อมูลแบบย้อนหลังอยู่ที่วิธีการจัดการองค์ประกอบของเวลา โครงสร้างข้อมูลแบบถาวรจะเก็บรักษาโครงสร้างข้อมูลไว้หลายเวอร์ชัน และสามารถดำเนินการกับเวอร์ชันหนึ่งเพื่อสร้างเวอร์ชันอื่นได้ เนื่องจากแต่ละการดำเนินการสร้างเวอร์ชันใหม่ ดังนั้นแต่ละเวอร์ชันจึงกลายเป็นไฟล์เก็บถาวรที่ไม่สามารถเปลี่ยนแปลงได้ (สามารถสร้างเวอร์ชันใหม่ได้จากไฟล์เดิมเท่านั้น) เนื่องจากแต่ละเวอร์ชันไม่เปลี่ยนแปลง ความสัมพันธ์ระหว่างแต่ละเวอร์ชันจึงไม่เปลี่ยนแปลงเช่นกัน ในโครงสร้างข้อมูลแบบย้อนหลัง เราอนุญาตให้ทำการเปลี่ยนแปลงโดยตรงกับเวอร์ชันก่อนหน้าได้ เนื่องจากแต่ละเวอร์ชันมีความสัมพันธ์กัน การเปลี่ยนแปลงเพียงครั้งเดียวอาจทำให้เกิดการเปลี่ยนแปลงต่อเนื่องไปยังเวอร์ชันต่อๆ ไปทั้งหมด รูปที่ 1 และ 2 แสดงตัวอย่างของผลกระทบต่อเนื่องนี้
คำนิยาม
โครงสร้างข้อมูลใดๆ ก็สามารถกำหนดรูปแบบใหม่ได้ในบริบทแบบย้อนหลัง โดยทั่วไปแล้ว โครงสร้างข้อมูลจะเกี่ยวข้องกับชุดของการอัปเดตและการสอบถามที่เกิดขึ้นในช่วงระยะเวลาหนึ่ง ให้ U = [u , u , u , ..., u ] เป็นลำดับของการดำเนินการอัปเดตจาก t ถึง t โดยที่ t < t < ... < t ข้อสมมติในที่นี้คือ สามารถดำเนินการได้มากที่สุดหนึ่งครั้งสำหรับเวลา t ที่กำหนด
มีผลย้อนหลังบางส่วน
เรากำหนดโครงสร้างข้อมูลว่าเป็นแบบย้อนหลังบางส่วน หากโครงสร้างข้อมูลนั้นสามารถดำเนินการอัปเดตและสอบถามข้อมูลในปัจจุบันได้และรองรับการดำเนินการแทรกและลบข้อมูลในอดีตได้ ดังนั้น สำหรับโครงสร้างข้อมูลแบบย้อนหลังบางส่วน เราจึงสนใจการดำเนินการต่อไปนี้:
- Insert(t, u): แทรกการดำเนินการใหม่ u ลงในรายการ U ณ เวลา t
- Delete(t): ลบการดำเนินการ ณ เวลา t ออกจากรายการ U
จากการดำเนินการย้อนหลังข้างต้น การดำเนินการแทรกมาตรฐานจะมีรูปแบบเป็น Insert(t, "insert(x)") การเปลี่ยนแปลงย้อนหลังทั้งหมดในประวัติการดำเนินการของโครงสร้างข้อมูลอาจส่งผลกระทบต่อการดำเนินการทั้งหมด ณ เวลาที่ดำเนินการไปจนถึงปัจจุบัน ตัวอย่างเช่น หากเรามี t < t < t แล้ว Insert(t, insert(x)) จะวางการดำเนินการใหม่opระหว่างการดำเนินการop และop สถานะปัจจุบันของโครงสร้างข้อมูล (เช่น โครงสร้างข้อมูล ณ เวลาปัจจุบัน) จะอยู่ในสถานะที่การดำเนินการop , opและop เกิดขึ้นตามลำดับ ราวกับว่าการดำเนินการopมีอยู่เสมอ ดูรูปที่ 1 และ 2 สำหรับตัวอย่างภาพประกอบ
มีผลย้อนหลังอย่างสมบูรณ์
เรากำหนดโครงสร้างข้อมูลให้เป็นแบบย้อนหลังได้อย่างสมบูรณ์ หากนอกเหนือจากการดำเนินการแบบย้อนหลังบางส่วนแล้ว เรายังอนุญาตให้มีการสอบถามข้อมูลเกี่ยวกับอดีตได้ด้วย เช่นเดียวกับการดำเนินการมาตรฐาน insert(x) ที่กลายเป็น Insert(t, "insert(x)") ในแบบจำลองแบบย้อนหลังบางส่วน การดำเนินการ query(x) ในแบบจำลองแบบย้อนหลังอย่างสมบูรณ์ก็จะมีรูปแบบเป็น Query(t, "query(x)") เช่นกัน
เวลาวิ่งย้อนหลัง
เวลาในการทำงานของโครงสร้างข้อมูลแบบย้อนหลังนั้นขึ้นอยู่กับจำนวนการดำเนินการmที่กระทำกับโครงสร้าง จำนวนการดำเนินการrที่กระทำก่อนที่จะดำเนินการแบบย้อนหลัง และจำนวนองค์ประกอบสูงสุดnในโครงสร้าง ณ เวลาใดเวลาหนึ่ง
การทำงานย้อนหลังอัตโนมัติ
คำถามหลักเกี่ยวกับการดำเนินการย้อนกลับอัตโนมัติที่เกี่ยวข้องกับโครงสร้างข้อมูลคือ มีเทคนิคทั่วไปที่สามารถแปลงโครงสร้างข้อมูลใดๆ ให้เป็นโครงสร้างข้อมูลที่สามารถดำเนินการย้อนกลับได้อย่างมีประสิทธิภาพหรือไม่ แนวทางง่ายๆ คือการย้อนกลับการเปลี่ยนแปลงทั้งหมดที่เกิดขึ้นกับโครงสร้างก่อนที่จะดำเนินการย้อนกลับ เมื่อเราได้ย้อนกลับโครงสร้างข้อมูลไปยังสถานะที่เหมาะสมแล้ว เราจึงสามารถใช้การดำเนินการย้อนกลับเพื่อทำการเปลี่ยนแปลงที่เราต้องการได้ เมื่อทำการเปลี่ยนแปลงแล้ว เราต้องนำการเปลี่ยนแปลงทั้งหมดที่เราย้อนกลับก่อนหน้านี้กลับมาใช้ใหม่เพื่อให้โครงสร้างข้อมูลอยู่ในสถานะใหม่ แม้ว่าวิธีนี้จะใช้ได้กับโครงสร้างข้อมูลใดๆ ก็ตาม แต่มันมักจะไม่มีประสิทธิภาพและสิ้นเปลือง โดยเฉพาะอย่างยิ่งเมื่อจำนวนการเปลี่ยนแปลงที่เราต้องย้อนกลับมีจำนวนมาก ในการสร้าง โครงสร้างข้อมูลที่สามารถดำเนินการย้อนกลับได้ อย่างมีประสิทธิภาพเราต้องพิจารณาคุณสมบัติของโครงสร้างนั้นเองเพื่อพิจารณาว่าสามารถเพิ่มความเร็วได้ที่ใด ดังนั้นจึงไม่มีวิธีทั่วไปในการแปลงโครงสร้างข้อมูลใดๆ ให้เป็นโครงสร้างข้อมูลที่สามารถดำเนินการย้อนกลับได้อย่างมีประสิทธิภาพErik D. Demaine , John IaconoและStefan Langermanได้พิสูจน์สิ่งนี้แล้ว[ 1 ]