-
RingBufferAlgorithm/Theory 2021. 4. 7. 10:48728x90
안녕하세요! 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 } }
읽어주셔서 감사합니다!
도움이 되셨다면 좋겠네요 :)
'Algorithm > Theory' 카테고리의 다른 글
후위표기식 변환 (5) 2021.04.26 SegmentTree (0) 2021.04.08 선택문제 Quick Select (0) 2021.01.07 Combination 조합 (3) 2020.08.25 Floyd Wharshall 플로이드 와샬 (2) 2020.06.18