[Swift Collections] deque

Swift-Collections 패키지(Commonly used data structures for Swift) 에 있는

deque 라는 자료구조를 살펴보겠습니다.

 

deque는 파이썬에서 오래전부터 많이 봐왔던 친구라.. 

파이썬 문서랑 Swift 문서를 함께 살펴볼게요! 

 

[1] Deque 란 ?

- deque는 "double-ended-queue" 의 줄임말입니다.  발음은 "deck" 이라고 합니다. 

 

- 양쪽 끝에서 삽입, 삭제가 가능한 큐입니다.

(파이썬 문서에서는 'Deques are a generalization of stacks and queues' 라고 말합니다)

 

- array 와 굉장히 비슷합니다.  

deque와 array 는 모두 ordered, random-access, mutable, range-replaceable collection with integer indices 이기 때문입니다. 

var colors: Deque = ["red", "yellow", "blue"]

colors.prepend("green")
colors.append("orange")
// `colors` is now ["green", "red", "yellow", "blue", "orange"]

colors.popFirst() // "green"
colors.popLast() // "orange"
// `colors` is back to ["red", "yellow", "blue"]


colors[1] // "yellow"
colors[1] = "peach"

colors.insert(contentsOf: ["violet", "pink"], at: 1)
// `colors` is now ["red", "violet", "pink", "peach", "blue"]

colors.remove(at: 2) // "pink"
// `colors` is now ["red", "violet", "peach", "blue"]

colors.sort()
// `colors` is now ["blue", "peach", "red", "violet"]

 

[2] Deque -  insert/remove

 

deque는 array와 비슷하지만,  deque를 쓰는 main benefit 은

양쪽 끝(both ends) 에서 삽입, 삭제를 빠른 속도로 할 수 있다는 점입니다.

 

양쪽 끝(both ends)에서 삽입, 삭제를 할 때 

dequeue의 performance는 O(1) 인 반면,  array의 performance 는 O(n) 입니다.

 

(예를들어 맨앞에서 element를 삭제하는 경우,

deque는 맨앞의 element를 지우면 끝이지만, array는 맨앞의 element를 지우고 나머지 elements 들을 한칸씩 땡겨줘야합니다.) 

 

사실상 정확하게 말하면 removeLast 는 array 에서도 O(1) 입니다.

removeFirst 만 O(n) 인 것..! 

 

# prepend (맨앞에 넣는 연산) 시간비교

 

https://www.swift.org/blog/swift-collections/

 

Prepending an element is a constant time operation for Deque, but a linear time operation for Array.

Note: All graphs plot the average per-element processing time on a log-log scale. Lower is better. The benchmarks were run on my 2017 iMac Pro.

 

 

반면 양쪽 끝(처음, 마지막)이 아닌 위치에 삽입, 삭제하는 경우라면

deque는 array와 동일한 O(n)의 퍼포먼스를 내는 것 같네요 

  /// - Complexity: O(`count`). The operation shifts existing elements either
  ///    towards the beginning or the end of the deque to minimize the number of
  ///    elements that need to be moved. When inserting at the start or the end,
  ///    this reduces the complexity to amortized O(1).
  @inlinable
  public mutating func insert(_ newElement: Element, at index: Int) {

  /// - Complexity: O(`count`). Removing elements from the start or end of the
  ///    deque costs O(1) if the deque's storage isn't shared.
  @inlinable
  @discardableResult
  public mutating func remove(at index: Int) -> Element {

 

[3] Deque - access

 

swift 문서에서는

random access에 대한 그래프도 제공해주고 있습니다. 

 

# random access 시간 비교 

 

https://www.swift.org/blog/swift-collections/

 

Like Array, accessing an element at an arbitrary offset is a constant time operation for Deque.

 

맨앞에서 효율적인 삽입을 지원하기 위해 deque는 연속적인 버퍼에서 요소들을 유지하는 것을 포기해야한다고 합니다.

그래서 array보다 속도가 약간 느리므로 front에서 element를 삽입/제거 할 필요가 없는 경우라면

array를 deque로 맹목적으로 교체하지 않는 것은 좋지 않다고 하네요! 

 

(DequeModule 안의 소스코드를 대충보면 storage, buffer 가 보입니다..) 

 

subscript(index:)  의 주석도 참고해주세요! 

    /// - Complexity: Reading an element from a deque is O(1). Writing is O(1)
    ///    unless the deque’s storage is shared with another deque, in which case
    ///    writing is O(`count`).
    @inlinable public subscript(index: Int) -> Element

 

 

[4] Swift 에서 Stack, Queue 를 구현할 때 

 

Swift에서 Stack, Queue를 구현할때 보통 array 기반으로 구현하는데,,

deque 기반으로 구현하는 게 더 속도가 빠르겠군요! 

 

(다만 deque 모듈을 import할 수 있는 상황이라면 + 읽기 보다 양끝에서 삽입/삭제 연산이 주목적이라면..  )

(참고로 LinkedList로 Stack, Queue 구현하는 방법도 있지만 여기서는 다루지 X) 

 

 

# as is

 

 

 

# to be 

 

 

 

 

 

[참고]

 

참고로

파이썬에서는 여러가지 연산에 대해

array와 deque의 퍼포먼스를 비교해볼 수 있는 표도 제공해주고 있더라구요! 

 

https://wiki.python.org/moin/TimeComplexity

TimeComplexity - Python Wiki