บัพเฟอร์วงกลม

จากวิกิพีเดีย สารานุกรมเสรี
Jump to navigation Jump to search

บัพเฟอร์วงกลม (อังกฤษ: circular buffer) เป็นโครงสร้างข้อมูลประเภทหนึ่ง ซึ่งเป็นการจัดการข้อมูลในรูปแบบวงกลม แต่ขนาดหรือความจุของข้อมูลจะต้องจำกัดไม่สามารถเพิ่มขึ้นได้ หลักการทำงานส่วนใหญ่จะเป็นการเก็บข้อมูลแบบตามลำดับ จนข้อมูลเต็มก็จะทำการเพิ่มข้อมูลไปใหม่ โดยใช้หลักการ FIFO (FIRST IN FIRST OUT) หรือ มาก่อนก็ออกก่อน

CircularBuffer.png

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

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

ความซับซ้อนของการทำงาน[แก้]

จะขึ้นอยู่กับขนาดของข้อมูลทั้งหมด ดังนั้นสรุปได้ว่า Big(o) = O(n) จะได้ว่า Best Case คือ ขนาดของข้อมูลมีน้อยที่สุดหรือไม่มีเลย และ Worst Case คือ ขนาดของข้อมูลมีมากที่สุด

ตัวอย่างการเขียนโปรแกรม[แก้]

ตัวอย่างการเขียนโปรแกรมด้วยภาษาไพทอน (Python)

 1 class CircularBuffer:
 2     def __init__(self, size):
 3         self.size = size
 4         self.data = [None]*size
 5         self.cur = 0
 6 
 7     def append(self, x):
 8         self.data[self.cur] = x
 9         self.cur = (self.cur + 1) % self.size
10 
11 
12     def get(self):
13         return self.data[self.cur:]+self.data[:self.cur]

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

O'Reilly Media. (2002). Implementing a Ring Buffer. Python Cookbook. Retrieved 30 April 2018.