Athit9838
บัฟเฟอร์แก็ป (Gap buffer)
บัฟเฟอร์ช่องว่างในวิทยาการคอมพิวเตอร์เป็นอาร์เรย์แบบไดนามิกที่ช่วยให้การแทรกและการลบที่มีประสิทธิภาพคลัสเตอร์อยู่ใกล้ตำแหน่งเดียวกัน บัฟเฟอร์ Gap เป็นตัวแก้ไขข้อความโดยเฉพาะซึ่งการเปลี่ยนแปลงข้อความส่วนใหญ่เกิดขึ้นที่หรือใกล้ตำแหน่งปัจจุบันของเคอร์เซอร์ ข้อความจะถูกเก็บไว้ในบัฟเฟอร์ขนาดใหญ่ในสองส่วนที่อยู่ติดกันโดยมีช่องว่างระหว่างการแทรกข้อความใหม่ การเลื่อนเคอร์เซอร์จะเป็นการคัดลอกข้อความจากด้านหนึ่งของช่องว่างไปยังอีกส่วนหนึ่ง (บางครั้งการคัดลอกจะล่าช้าจนกว่าจะมีการดำเนินการต่อไปซึ่งจะเปลี่ยนข้อความ) แทรกเพิ่มข้อความใหม่ตอนท้ายของกลุ่มแรก แล้วลบช่องว่างออก
ข้อความในบัฟเฟอร์ช่องว่างจะแสดงเป็นสตริงที่สองซึ่งใช้เนื้อที่น้อยมากและสามารถค้นหาและแสดงผลได้อย่างรวดเร็วเมื่อเทียบกับโครงสร้างข้อมูลที่ซับซ้อนมากขึ้นเช่นลิงค์ ลิสต์ อย่างไรก็ตามการดำเนินงานในตำแหน่งต่างๆในข้อความและช่องที่เติมช่องว่าง (ต้องมีช่องว่างใหม่ที่จะสร้างขึ้น) อาจต้องมีการคัดลอกข้อความส่วนใหญ่ซึ่งไม่มีประสิทธิภาพสำหรับไฟล์ขนาดใหญ่ การใช้บัฟเฟอร์ช่องว่างจะขึ้นอยู่กับสมมติฐานว่าการทำสำเนาข้อมูลย้อนหลังนั้นเกิดขึ้นไม่ค่อยเพียงพอที่จะสามารถตัดจำหน่ายค่าใช้จ่ายในส่วนที่ใช้กันทั่วไปได้ เรื่องนี้ทำให้ช่องว่างทางเลือกที่ง่ายกว่าเชือกเพื่อใช้ในการแก้ไขข้อความ [1] เช่น Emacs ได้ [2]
|
---|
ตัวอย่าง
แก้ด้านล่างเป็นตัวอย่างของการดำเนินงานที่มีช่องว่างของบัฟเฟอร์ ช่องว่างนี้แสดงด้วยช่องว่างระหว่างวงเล็บเหลี่ยม การแสดงนี้เป็นบิตที่ทำให้เข้าใจผิด: ในการใช้งานทั่วไปจุดสิ้นสุดของช่องว่างจะถูกติดตามโดยใช้คำแนะนำหรือดัชนีของอาร์เรย์และเนื้อหาของช่องว่างจะถูกละเลย นี้ช่วยให้ตัวอย่างเช่นการลบที่จะทำโดยการปรับตัวชี้โดยไม่ต้องเปลี่ยนข้อความในบัฟเฟอร์ เป็นวิธีการเขียนโปรแกรมทั่วไปเพื่อใช้ช่วงกึ่งเปิดสำหรับตัวชี้ช่องว่างเช่นจุดเริ่มต้นของช่องว่างไปยังอักขระที่ไม่ถูกต้องตามอักขระตัวสุดท้ายในบัฟเฟอร์แรกและจุดสิ้นสุดของช่องว่างจะชี้ไปที่จุดแรก อักขระที่ถูกต้องในบัฟเฟอร์ที่สอง (หรือเทียบเท่าตัวชี้จะถือเป็นจุด "ระหว่าง" อักขระ)
สถานะเริ่มต้น:
This is the way [ ]out.
ผู้ใช้แทรกข้อความใหม่:
This is the way the world started [ ]out.
ผู้ใช้เลื่อนเคอร์เซอร์ไปที่ "started"; ระบบย้าย "started" จากบัฟเฟอร์แรกไปยังบัฟเฟอร์ตัวที่สอง
This is the way the world [ ]started out.
ผู้ใช้เพิ่มข้อความเติมช่องว่าง สร้างช่องว่างใหม่:
This is the way the world as we know it [ ]started out.
ดูเพิ่มเติม
แก้- Dynamic array, the special case of a gap buffer where the gap is always at the end
- Zipper (data structure), conceptually a generalization of the gap buffer.
- Linked list
- Circular buffer
- Rope (computer science)
- Piece table - data structure used by Bravo and Microsoft Word