Co je kruhová vyrovnávací paměť (ring buffer) a kdy byste ji použili?

Question

Accepted Answer

**Kruhová vyrovnávací paměť** je pole pevné velikosti, které se považuje za to, že jsou jeho konce spojeny do kruhu. Dva indexy — **head** (čtení) a **tail** (zápis) — postupují vpřed a obtáčejí se kolem pomocí aritmetiky modulo, což poskytuje frontu FIFO s O(1) **bez přidělení** po vytvoření.

## Jak funguje obtáčení

```text
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)
```

## Code

```python
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
```

| Operace | Čas |
|---|---|
| enqueue / dequeue | O(1) |
| space | O(n) pevné |

## Kdy se používá

- **Streamování / zvuk / video vyrovnávací paměti** — omezené, stálá propustnost.
- **Producent–spotřebitel** potrubí s backpressure.
- **Protokolování posledních N událostí** (přepsání nejstarší).

## Proč to záleží

Kruhová vyrovnávací paměť poskytuje předvídatelné chování FIFO bez přidělení, které je nezbytné v systémech v reálném čase a vestavěných systémech, kde je dynamické přidělení příliš pomalé nebo riskantní.

Jeho omezená velikost také funguje jako přirozená backpressure, která zabraňuje rychlým producentům v vyčerpání paměti.