Back
+30 XP
Concept

Fixed-Size Circular Ring Buffer

Calling `list.pop(0)` in Python forces the runtime to re-index and shift every element in memory in $O(N)$ time. A Circular Ring Buffer uses a pre-allocated fixed-size array and modulo pointer arithmetic (`(head + 1) % capacity`) to overwrite the oldest items in true $O(1)$ constant time 🔄🍩⚡.

python
class Ring:
    def __init__(self, cap):
        self.cap = cap
        self.buf = [None] * cap
        self.idx = 0

    def push(self, x):
        self.buf[self.idx] = x
        self.idx = (self.idx + 1) % self.cap

r = Ring(3)
for i in [1, 2, 3, 4]: r.push(i)
print("Ring state after 4 pushes:", r.buf)

# 18. Fixed-Size Circular Ring Buffer In high-throughput logging, operating system kernels, audio signal processors, and sliding metrics windows, you frequently need to track the "most recent $N$ events" without incurring continuous memory allocations 🛑. ```python # The Ring Buffer Array Layout: # Capacity = 4 # Push 1, 2, 3: [1, 2, 3, None] (Head=0, Tail=3, Size=3) # Push 4: [1, 2, 3, 4] (Head=0, Tail=0, Size=4 - FULL) # Push 5 (Wrap!): [5, 2, 3, 4] (Head=1, Tail=1, Size=4 - 1 was overwritten!) ``` ### The $O(1)$ Modulo Pointer Invariant - **No Resizing**: The backing array `[None] * capacity` is allocated once at startup. - **No Element Shifting**: Instead of shifting elements in RAM, advance the pointer using integer modulo: $$\text{tail} = (\text{tail} + 1) \pmod{\text{capacity}}$$ - Writes and reads run in **guaranteed sub-microsecond $O(1)$ time** 🔄🍩⚡. --- ### Interactive Pop-Quiz 🧠 #### Why is list.pop(0) an anti-pattern for rolling queues and sliding windows in Python? - [ ] It has $O(N)$ linear time complexity because all remaining memory elements must shift one slot forward in RAM 🛑 - [ ] Because `list.pop(0)` permanently disables garbage collection - [ ] Because index 0 is read-only in Python arrays - [ ] It crashes the operating system kernel --- ### Practical Challenge 🎯 Implement `CircularRingBuffer(capacity: int)` with `append(val)` (overwriting oldest when full), `pop_oldest() -> val` (raising `IndexError` if empty), and `to_list() -> list` returning items in chronological order. Initialize with capacity 3, append 10, 20, 30, then 40 (overwriting 10). Assert `to_list()` is `[20, 30, 40]`, pop oldest (assert 20), assert `[30, 40]`, and print results. <details> <summary>Solution</summary> ```python class CircularRingBuffer: def __init__(self, capacity: int): self.capacity = capacity self.buffer = [None] * capacity self.head = 0 self.tail = 0 self.size = 0 def append(self, val): self.buffer[self.tail] = val self.tail = (self.tail + 1) % self.capacity if self.size < self.capacity: self.size += 1 else: self.head = (self.head + 1) % self.capacity def pop_oldest(self): if self.size == 0: raise IndexError("Empty ring buffer") val = self.buffer[self.head] self.buffer[self.head] = None self.head = (self.head + 1) % self.capacity self.size -= 1 return val def to_list(self) -> list: return [self.buffer[(self.head + i) % self.capacity] for i in range(self.size)] rb = CircularRingBuffer(3) rb.append(10) rb.append(20) rb.append(30) assert rb.to_list() == [10, 20, 30] rb.append(40) # Overwrites 10 assert rb.to_list() == [20, 30, 40] oldest = rb.pop_oldest() assert oldest == 20 assert rb.to_list() == [30, 40] print(f"CircularRingBuffer verified: popped={oldest}, buffer={rb.to_list()}") ``` </details>

Checkpoint

Why is `list.pop(0)` an anti-pattern for rolling queues and sliding windows in Python? 🧠

Practice

Implement `CircularRingBuffer(capacity: int)` with `append(val)` (overwriting oldest when full), `pop_oldest() -> val` (raising `IndexError` if empty), and `to_list() -> list` returning items in chronological order. Initialize with capacity 3, append 10, 20, 30, then 40 (overwriting 10). Assert `to_list()` is `[20, 30, 40]`, pop oldest (assert 20), assert `[30, 40]`, and print results. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks