წრიული ბუფერი არის ფიქსირებული ზომის მასივი, რომელიც ისე იქცევა, თითქოს მისი ბოლოები ქმნიან რგოლს. ორი ინდექსი — head (წაკითხვა) და tail (ჩაწერა) — წინ მოძრაობენ და ბრუნდებიან მოდულო არითმეტიკის გამოყენებით, რაც აძლევს O(1) FIFO რიგს განაწილების გარეშე შექმნის შემდეგ.
capacity 5, after writing A,B,C,D and reading A,B:
index: 0 1 2 3 4
[ . ][ . ][ C ][ D ][ . ]
head^ tail^ (tail wraps to 0 next write)
class RingBuffer:
def __init__(self, n):
self.buf = [None]*n
self.head = self.tail = self.size = 0
self.cap = n
def enqueue(self, x): # O(1)
if self.size == self.cap: raise Exception("full")
self.buf[self.tail] = x
self.tail = (self.tail + 1) % self.cap # wrap
self.size += 1
def dequeue(self): # O(1)
x = self.buf[self.head]
self.head = (self.head + 1) % self.cap # wrap
self.size -= 1
return x
| ოპერაცია | დრო |
|---|---|
| enqueue / dequeue | O(1) |
| სივრცე | O(n) ფიქსირებული |
წრიული ბუფერი უზრუნველყოფს წინასწარმეტყველ, განაწილების გარეშე FIFO ქცევას, რაც გადამწერი და ჩაშენებული სისტემებში ან ზღვარი რეალურ დროში, სადაც დინამიური განაწილება ძალიან ნელი ან სახطерი.
მისი შეზღუდული ზომა ასევე ემსახურება ბუნებრივ უკუწნევას, რაც მხეთ არ იძლევა სწრაფი პროდიუსერებისთვის მეხსიერების გამოწურვა.