Queue 구현 (feat. Swift)

https://github.com/kodecocodes/swift-algorithm-club/tree/master/Queue
해당 문서를 직접 번역하면서 공부한 내용입니다.

BFS를 공부하면서 Queue를 쓰고싶었는데, built-in swift에서의 removieFirst()함수는 배열에서 맨 앞단의 요소를 제거하는 것이기 때문에 O(n)의 시간복잡도가 생긴다.

파이썬에서 deque라이브러리를 통해 O(1)로 맨 앞단의 요소를 제거하는 것처럼 하기 위해서 Swift의 Queue에 대해서 공부해보았다.

단순한 Queue의 구현

---

public struct Queue<T> {
  fileprivate var array = [T]()

  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  public var count: Int {
    return array.count
  }

  public mutating func enqueue(_ element: T) {
    array.append(element)
  }
  
  public mutating func dequeue() -> T? {
    if isEmpty {
      return nil
    } else {
      return array.removeFirst()
    }
  }
  
  public var front: T? {
    return array.first
  }
}

Enqueueing은 언제나 O(1)

---

큐에 삽입하는 것은 언제나 **O(1)**의 시간이 소요된다. 그 이유가 뭘까??

그 이유는 Swift가 항상 마지막에 빈공간(empty space)를 확보하고 있기 때문이다.

var queue = Queue<String>()
queue.enqueue("Ada")
queue.enqueue("Steve")
queue.enqueue("Tim")

이렇게 한다면 배열의 실제 모습은 아래와 같다

[ "Ada", "Steve", "Tim", xxx, xxx, xxx ]

xxx는 예약된 메모리이지만 아직 채워지지 않은 부분이다. 새로운 요소를 추가하는 것은 다음 사용되지 않은 빈 공간을 채워넣게 된다.

[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]

한 곳에서 다른 곳으로 메모리를 복사하는 것은 결국 상수 시간의 작업이 된다.

하지만 이렇게 뒷공간의 빈공간을 예약하는 데에도 제한이 있다. 마지막의 xxx가 사용되고 만약 다른 요소를 더 추가하고 싶다면, 배열은 더 많은 공간을 만들기 위해 resize를 해야한다.

Resizing 작업은 새로운 메모리를 할당받고 기존의 모든 데이터들을 새로운 배열에 복사하는 것을 포함하고 있다. 따라서 상대적으로 느린, **O(n)**의 시간복잡도를 가진다. 하지만 이것은 간헐적으로 일어나는 것이므로, 배열의 마지막에 새로운 요소를 추가하는 것은 평균적으로 여전히 O(1)이라고 할 수 있다.

Dequeuing은 다르다

---

큐에서의 삭제는 FIFO(First-In First-Out), 배열의 시작부분에서 삭제가 이루어진다.

이 작업은 모든 남아있는 요소들을 메모리에서 앞으로 shift해주어야 하기 때문에 항상 **O(n)**작업이다. 아래 예제에서 첫번째 요소인 “Ada”를 제거하면 아래와 같이 된다

before   [ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
                   /       /      /
                  /       /      /
                 /       /      /
                /       /      /
 after   [ "Steve", "Tim", "Grace", xxx, xxx, xxx ]

이러한 동작은 항상 O(n)이기 때문에 dequeing 작업은 최적화가 필요하다

더욱 효과적인 Queue

더욱 효과적인 큐를 만들기 위해서 enqueue했을 때와 같이 이번에는 앞의 공간에 추가로 빈공간을 만들어 줄 수 있다. 이 부분은 built-in Swift에서는 제공하지 않는 부분이기 때문에 우리가 직접 구현해야한다.

핵심 아이디어는 우리가 아이템을 dequeue할 때마다, 배열의 요소들을 앞으로 shift하지 않는 대신(slow) 지우고자 하는 아이템의 위치를 빈 공간(empty)로 마크하는 것이다.

아래는 맨 앞 요소인 “Ada”를 dequeue하는 예시이다.

[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]

“Steve”를 추가로 dequeue한다면?

[ xxx, xxx, "Tim", "Grace", xxx, xxx ]

이렇게 앞쪽에 생긴 빈공간들이 재사용되지 않는다면, 주기적으로 앞쪽의 빈공간들을 trimming해주어서 남아있는 요소드들을 앞으로 움직여준다.

[ "Tim", "Grace", xxx, xxx, xxx, xxx ]

Trimming작업은 memory shifting을 포함하기 때문에 **O(n)**작업이지만 가끔 일어나는 작업이기 때문에, 평균적으로 O(1)의 작업이 된다.

public struct Queue<T> {
  fileprivate var array = [T?]()
  fileprivate var head = 0
  
  public var isEmpty: Bool {
    return count == 0
  }

  public var count: Int {
    return array.count - head
  }
  
  public mutating func enqueue(_ element: T) {
    array.append(element)
  }
  
  public mutating func dequeue() -> T? {
    guard head < array.count, let element = array[head] else { return nil }

    array[head] = nil
    head += 1

    let percentage = Double(head)/Double(array.count)
    if array.count > 50 && percentage > 0.25 {
      array.removeFirst(head)
      head = 0
    }
    
    return element
  }
  
  public var front: T? {
    if isEmpty {
      return nil
    } else {
      return array[head]
    }
  }
}

배열의 요소들을 empty, 즉 nil로 담아야하기 때문에 array는 이제 T가 아닌 T?를 담고 있는다.

head는 배열의 맨 앞에 있는 아이템의 인덱스이다.

우리가 dequeue할 때, 우선 array[head]를 nil로 바꾸면서 배열에서 해당 아이템을 삭제한다. 그리고 head를 증가시켜서 다음 아이템이 가장 맨 앞의 아이템이 되게끔한다.

 

Before:

 

[ "Ada", "Steve", "Tim", "Grace", xxx, xxx ]
  head

After:

[ xxx, "Steve", "Tim", "Grace", xxx, xxx ]
        head

 

이건 마치 슈퍼마켓에서 사람들이 계산대 앞으로 막 가지않고, 계산대가 큐를 앞으로 움직여주는 것과 같다.

만약 우리가 배열의 앞쪽의 빈 공간들을 지워주지 않는다면, 우리가 enqueue, dequeue할 때마다 배열은 계속해서 증가할 것이다. 주기적으로 배열을 trim down 해주기 위해서 우리는 아래처럼 한다.

 

let percentage = Double(head)/Double(array.count)
if array.count > 50 && percentage > 0.25 {
  array.removeFirst(head)
  head = 0
}

 

총 배열 크기의 앞쪽의 빈 공간의 비율이 얼마나 되는지 비율을 계산한다.

만약, 배열의 25%이상이 unused상태라면? 낭비된 공간을 잘라낸다

하지만, 만약 배열이 작다면 우리는 매번 resize를 하지 않는다. 그래서 우리가 trim down을 시도하기 이전에 배열의 크기가 최소 50은 되어야한다.

 

Note: 이 숫자들은 임의로 떠올린 숫자이기 때문에, 프로덕션 환경에서 앱의 동작에 따라 조정해야 할 수도 있다.

Playground에서 이를 test해보기 위해서 아래를 실행시켜보면 된다.

 

var q = Queue<String>()
q.array                   // [] empty array

q.enqueue("Ada")
q.enqueue("Steve")
q.enqueue("Tim")
q.array             // [{Some "Ada"}, {Some "Steve"}, {Some "Tim"}]
q.count             // 3

q.dequeue()         // "Ada"
q.array             // [nil, {Some "Steve"}, {Some "Tim"}]
q.count             // 2

q.dequeue()         // "Steve"
q.array             // [nil, nil, {Some "Tim"}]
q.count             // 1

q.enqueue("Grace")
q.array             // [nil, nil, {Some "Tim"}, {Some "Grace"}]
q.count             // 2

trimming작업을 시험해보기 위해서는 이 라인을

 

if array.count > 50 && percentage > 0.25 {

 

이걸로 바꾸고

 

if head > 2 {

 

이제 다른 아이템을 dequeue하면, 배열은 아래와 같이 보일 것이다.

 

q.dequeue()         // "Tim"
q.array             // [{Some "Grace"}]
q.count             // 1

 

앞쪽의 nil이 모두 삭제되었고, array는 더 이상 공간을 낭비하지 않는다.

이 새로운 버전의 큐는 단지 우리가 배열을 어떻게 사용했는지에 대해 알고 있었다는 이유로 첫번째 버전보다 엄청 복잡하지도 않지만 dequeueing이 O(1) 작업이 된다.

---