RingBuffer

안녕하세요! deque 관련된 문제를 풀다가 간만에 자료구조를 하나 정리해볼까 합니다.

아시다시피 array에서는 뒤에 추가하거나 빼는 작업은 O(1) 이지만, 

앞 또는 중간에 추가하거나 빼는 작업은 O(n)의 시간 복잡도가 소요됩니다. 배열의 크기는 고정되어 있기 때문에 앞이나 중간에 작업을 하려면 그 뒤의 나머지 원소들을 모두 옮겨주는 작업이 필요하기 때문이에요.

그럼 원소들을 옮기지 않고 인덱스만 조절하면 되지 않을까? 

하는 데서 시작된 아이디어가 RingBuffer가 아닐까 싶어요.

RingBuffer는 read /  write 포인터를 둬서 배열의 원소들을 움직이지 않고 인덱스만 조절해 덮어쓰는 방식을 사용합니다.

예시를 보면서 살펴볼게요.  처음엔 Read, Write 모두 0번째 인덱스에서 출발합니다.

 

Read / Write를 하고나면 각 인덱스를 증가시킵니다.

원소를 8개까지 쭉쭉 추가시키고 2개를 읽어볼까요?

write가 배열의 끝인 8까지 도달했습니다. 여기서 333을 한 번 더 write 하려면 어떻게 할까요?

이미 읽어서 사용한 0으로 돌아가 새로 덮어씌우면 되겠죠? 이때 나머지 연산을 이용합니다 :)

mutating func write(_ element: T) {
  array[writeIndex % array.count] = element
  writeIndex += 1
}

 

큰 원리는 이게 끝입니다! 나머지는 여기서 파생되는 것들이에요!

읽어들일 수 있는 공간은 writeIndex - readIndex

쓸 수 있는 전체 배열 크기 - 공간은 읽을 수 있는 공간 

으로 생각해볼 수 있습니다. 이제 이걸로 isEmpty, isFull 등까지 구해줄 수 있습니다.

var availableSpacingForReading: Int {
    return writeIndex - readIndex
}

var isEmpty: Bool {
    return availableSpacingForReading == 0
}

var availableSpacingForWriting: Int {
    return array.count - availableSpacingForReading
}

var isFull: Bool {
    return availableSpacingForWriting == 0
}

 

현재 상태로서는 배열이 가득차면 더이상 write 할 수 없습니다. 따라서 write가 성공했는지 실패했는지 bool 값을 리턴해줍니다.

mutating func write(_ element: T) -> Bool {
  if !isFull {
    array[writeIndex % array.count] = element
    writeIndex += 1
    return true
  } else {
    return false
  }
}

mutating func read() -> T? {
  if !isEmpty {
    let element = array[readIndex % array.count]
    readIndex += 1
    return element
  } else {
    return nil
  }
}

 

 

여기서 조금 더 확장시켜서 배열이 가득차면 배열의 크기를 늘려서 더 추가하도록 개선해볼 수 있겠습니다.

가득차면 배열의 크기를 두 배로 늘리는 방식으로 개선했습니다.

mutating func write(_ element: T) {
    if isFull {
        array.append(contentsOf: [T?](repeating: nil, count: array.count))
    }
    array[writeIndex % array.count] = element
    writeIndex += 1
}

 

read도 가능하다면 인덱스를 읽어들이고 싶네요!

subscript로 만들어서 기존의 배열처럼 사용하도록 만들면 더 좋겠죠??

현재는 read에서 바로 제거하는 식으로 되어 있는데, 필요하다면 읽기와 제거를 구분시켜서 개선할 수도 있겠지만,
여기선 거기까진 하지 않도록 할게요 :)

var buffer = RingBuffer<Int>(count: 4)
buffer.write(0)
buffer.write(1)
buffer.write(2)
buffer.write(3)

print(buffer[3])  // 3
print(buffer[4])  // nil

 

전체 코드는 다음과 같습니다.

struct RingBuffer<T> {
    private(set) var array: [T?]
    var readIndex = 0
    var writeIndex = 0
    
    init(count: Int) {
        self.array = [T?](repeating: nil, count: count)
    }
    
    mutating func write(_ element: T) {
        if isFull {
            array.append(contentsOf: [T?](repeating: nil, count: array.count))
        }
        array[writeIndex % array.count] = element
        writeIndex += 1
    }
    
    mutating func read() -> T? {
        if !isEmpty {
            let element = array[readIndex % array.count]
            readIndex += 1
            return element
        } else {
            return nil
        }
    }
    
    var availableSpacingForReading: Int {
        return writeIndex - readIndex
    }

    var isEmpty: Bool {
        return availableSpacingForReading == 0
    }

    var availableSpacingForWriting: Int {
        return array.count - availableSpacingForReading
    }

    var isFull: Bool {
        return availableSpacingForWriting == 0
    }
    
    subscript(_ offset: Int) -> T? {
        return offset < availableSpacingForReading ? array[(readIndex+offset) % array.count] : nil
    }
}

 

 

읽어주셔서 감사합니다!

도움이 되셨다면 좋겠네요 :)