Circular Buffer, Ring Buffer

Circular Buffer란?

생산자와 소비자 처리 사이의 통신에 버퍼를 제공하기 위해 일정량의 기억 장치를 할당한다.

그 로직이 원형으로 형성되는 버퍼를 말한다.

• 고정적인 크기: queue with a maximum size, constrained size or capacity, stores data in a fixed-size array
• 원형으로 탐색: continue to loop back over itself in a circular motion

---

Circular Buffer의 작동 방식

두 개의 포인터(front, back)로 읽을 위치, 삭제할 위치, 쓸 위치 등을 정한다.

• storing two pointer to the front and back of the structure

버퍼가 모두 차면 가장 오래된 것을 지우고, 그자리를 덮어 쓴다.

• once the size is set and the buffer is full, the oldest item in the buffer will be pushed out if more data is added
• As more data is added to the structure, the old data will be removed so no data will ever need to be shifted

---

사용예시

• AR 
  • 손이나 신체 움직임을 저장해두는 데 사용.
  • 짧은 시간 동안 빠르게 움직일 때 , 버퍼에 움직임 저장해 두었다가 실시간으로 표시
• 비디오 스트리밍
  • 영상을 되감을 때, 이전의 프레임들이 원형 버퍼에 저장되어 있어서 빠르게 접근 가능
• 키보드 입력
  • 키 입력이 너무 빠르게 들어왔을 때, 원형 버퍼에 저장해두고 입력을 순차적으로 처리

---

Circular Buffer의 이점

In conclusion, if you need to quickly access streaming data that has already been observed or used, a circular buffer might be a good solution!

 

DDoS 공격에 강하다.

길이가 정해져 있어서 무한하게 처리가 발생하지 않기 때문!

---

C# Circular Buffer구현하기

나는 queue를 사용해서 풀었는데, queue 자체가 circular queue를 기반으로 구현되어 있다고 하여,

List로 연습하는것이 원리 이해에 좋을 것!

https://exercism.org/tracks/csharp/exercises/circular-buffer

Circular Buffer in C# on Exercism

 

using System;
using System.Collections.Generic;
using System.Linq;

public class CircularBuffer<T>
{
    private readonly int _capacity;
    private List<T> _items;

    public CircularBuffer(int capacity)
    {
        _capacity = capacity;
        _items = new List<T>(capacity);
    }

    public T Read()
    {
        if (_items.Count == 0) throw new InvalidOperationException("Cannot read from empty buffer");

        var value = _items[0];

        DequeueHead();

        return value;
    }

    public void Write(T value)
    {
        if (_items.Count == _capacity) throw new InvalidOperationException("Cannot write to full buffer");

        _items.Add(value);
    }

    public void Overwrite(T value)
    {
        if (_items.Count == _capacity) DequeueHead();

        Write(value);
    }

    public void Clear() => _items.Clear();

    private void DequeueHead() => _items = _items.Skip(1).ToList();
}

---

참고 사이트

https://github.com/dotnet/csharplang

GitHub - dotnet/csharplang: The official repo for the design of the C# programming language

https://medium.com/towards-data-science/circular-queue-or-ring-buffer-92c7b0193326

Circular Queue or Ring Buffer

https://medium.com/better-programming/now-buffering-7a7d384faab5

Data Structures: Your Quick Intro to Circular Buffers

https://computer.howstuffworks.com/keyboard2.htm?source=post_page-----7a7d384faab5---------------------------------------

How Computer Keyboards Work