String의 joined(separator:) DeepDive

문제상황

평소에 String을 사용할 때와 알고리즘 문제를 풀이할 때,

String을 합치는 + 연산자와 joined() 함수에 대해 별 생각없이 사용하고 있었습니다.

그러다 문득, joined() 함수 내부도 + 연산자 를 사용한 코드 형태를 갖고있지 않을까? 라는 의문을 가지면서 해당 실험을 시작하게 되었습니다.

해결과정

joined()  함수 내부를 살펴봐야겠습니다!

Swift의 github를 살펴봐야할 것 같습니다!

 

아래와 같이 구현되어 있네요?

모든 내용을 다 해석하기 보다는 핵심적인 내용만 보겠습니다..!

internal func _joined(separator: String) -> String {
    // A likely-under-estimate, but lets us skip some of the growth curve
    // for large Sequences.
    let underestimatedCap =
      (1 &+ separator._guts.count) &* self.underestimatedCount
    var result = ""
    result.reserveCapacity(underestimatedCap)
    if separator.isEmpty {
      for x in self {
        result.append(x._ephemeralString)
      }
      return result
    }

    var iter = makeIterator()
    if let first = iter.next() {
      result.append(first._ephemeralString)
      while let next = iter.next() {
        result.append(separator)
        result.append(next._ephemeralString)
      }
    }
    return result
  }

underestimatedCap 의 의미는 최소한 필요한 용량의 의미로 해석이 되네요~

joined의 reserveCapacity(_:)

자, 여기서 중요한게 reserveCapacity(_:)  함수 인데요

 

이 함수는 만약 배열의 할당할 공간의 크기를 알고 있을 때, 사용하면 여러번 할당되는 것을 피할 수 있다고 공식 문서에 적혀있습니다!

 

Array와 비슷한 매커니즘으로 메모리공간을 차지한다고, 가정하고 아래에서 Array의 메모리공간 할당방식을 통해 설명을 진행하겠습니다!

실제 + 코드에서도 append()함수를 사용하고 append()함수는 String이 Character의 Array인 것처럼 추가를 합니다.

String.swift

public static func + (lhs: String, rhs: String) -> String {
    var result = lhs
    result.append(rhs)
    return result
  }

StringRangeReplaceableCollection.swift

public mutating func append(contentsOf newElements: String) {
    self.append(newElements)
  }

여기서 우리는 Swift를 사용하면서 간과하기 쉬운 Array 라는 자료구조에 대해서 알아보겠습니다.

 

원래 Array는 Fixed-Size 라는 특성을 갖고 있는데요.

 

Array의 크기를 미리 알고 처음 선언할 때 크기를 함께 할당해줘야한다는 특성입니다!

 

아래는, Swift에서 Array를 작성하실 때 아직 몇개의 데이터를 넣을지, 어떤 데이터를 넣을지 모를 때 보통 사용하는 코드의 예시입니다.

var arr: [Int] = []

전혀 Size 에 대한 언급이 없죠?

 

미리 배열의 크기를 정하고 배열을 생성하는 방법도 있습니다.

 

바로 Array(repeating: ,count: ) Array의 또 다른 init 방식입니다.

let arr: [Int] = Array(repeating: 1, count: 5)

용량이 정해져 있지 않은 배열을 선언해서 해당 배열의 크기를 어떻게 늘리는 걸까요~?

Dynamic Array

이렇게 배열의 크기를 유동적으로 resize 하는 자료구조를 Dynamic Array 라고 부릅니다.

 

Swift에서는 크기를 추가할 때마다 배열의 실질적인 용량이 1씩 증가하는걸로 봐서는 Doubling 은 사용하지 않는것 같습니다.

 

위의 사진과 아래 사진을 비교해보면,

 

새롭게 할당하는것에 부담이 없는 범위내에서는 1씩 용량을 증가시키고,

 

어느 정도의 크기를 넘으면 배열의 용량을 크게 할당 해놓는것을 볼 수 있습니다.

 

어떤 기준일까요?🤔 (혹시나 아시는분께서는 알려주시면 감사드리겠습니다 😊)

 

배열의 용량이 초과되면 새로운 인스턴스에 복사되는 매커니즘은 같기 때문에,

 

이번 글에서는 Doubling 기준으로 설명드리겠습니다.

 

보통 Dynamic Array는 Doubling이라는 방식을 통해 아래와 같이 동작합니다.

 

Doubling 이란?
배열의 메모리크기를 resize할 때 두 배씩 키워줍니다.

그림을 보시면 배열의 Size가 1 → 2 → 4로 2배씩 늘어나죠?

 

이게 Dynamic Array의 Doubling 의 원리입니다.

 

우리가 아무런 생각없이 배열을 사용하는 동안 배열은 저렇게 크기를 계속해서 resize 한답니다.

 

이렇게만 보면 문제가 없어보일 수 있습니다.

 

하지만 저렇게 크기가 변경되는 과정을 resize라고 계속해서 언급하고 있습니다.

 

크기가 늘어날 때마다 새로운 인스턴스의 공간이 할당되고 기존의 공간은 해제된다고 생각하시면 됩니다.

 

Size를 resize하게되는 경우를 코드로 설명드려보겠습니다!

 

아래의 코드에서 배열의 크기를 메모리 공간 내에서 배열이 원소를 저장할 수 있는 용량이라고 생각해주시면 감사하겠습니다 ㅎㅎ.. 원소 1개당 배열의 용량 1을 차지한다고 생각하면 될것같습니다!

 

아래와 같은 경우에 어떤일이 일어나게될까요?

var arr = [1, 2, 3]
arr.append(4)

resizedArr은 배열의 용량이 6으로 할당된다고 생각해주세요!

 

let arr = [1, 2, 3]
var resizedArr = Array(repeating: 0, count: 6)
for i in 0..<arr.count {
    resizedArr[i] = arr[i]
}
resizedArr[arr.count] = 4

 

위와같이 arr의 용량이 3개밖에 없는 상태에서 append()를 하게되면 배열의 용량을 늘리기 위해서 O(N)의 시간복잡도가 발생하게됩니다!

 

그런데, 우리가 알고있는 append()의 시간복잡도는 O(1)이죠?

 

이유는 이미 append()로 인해 늘어난 배열의 물리적인 크기는 4이지만,

배열의 용량이 6개로 늘어나있기 때문에, 그 뒤에 append(5)와 append(6) 두번을 추가하는 경우동안은 그냥 뒤에 이미 만들어진 배열의 용량에 원소를 집어넣는것이기 때문에 O(1)의 시간복잡도가 발생하게 됩니다~

 

이렇게 2배수로 배열의 용량이 증가하게되면 메모리 용량의 마지막에서 append()할때 용량을 증가시키면서 발생하는 O(n)의 시간복잡도보다 O(1)의 시간복잡도가 훨~~씬 많겠죠?

 

이걸 Amortized O(1)이라고 합니다.

그래서 append()의 시간복잡도가 O(1)로 표현되는 것입니다~

 

DynamicArray 를 설명한 이유는 reserveCapacity(_:) 를 사용함으로써 얻을 수 있는 이점을 설명하기 위함이었는데요~

 

reserveCapacity(_:) 는 배열의 용량을 미리 지정한 만큼 할당해주기 때문에 위처럼 여러번 Allocation하는 것을 방지하기 위해 사용하는 함수입니다!

 

그래서 joined()에서는 최적화를 해준다고 말할 수 있겠네요!

joined의 나머지 코드

for문과 while문으로 별다른 최적화없이 저희가 일반적으로 구현하는것과 별다를 바 없어보입니다~

 

성능 비교를 위한 테스트코드 작성

코드는 CommandLineTool로 작성했습니다.

 

main 코드

import Foundation

@discardableResult
func plusString(_ arr: [String]) -> String {
    var result = ""
    for element in arr {
        result += element
        result += ","
    }
    result.removeLast()
    return result
}

@discardableResult
func joinedString(_ arr: [String]) -> String {
    return arr.joined(separator: ",")
}

테스트 코드

의미있는 시간 차이를 도출하기 위해 배열의 크기를 20,000,000으로 설정했습니다!

import XCTest

final class Tests: XCTestCase {

    let strArray: [String] = Array(repeating: "123", count: 20_000_000)

    func test_Plus_String_Array_Performance() {
        measure {
            plusString(strArray)
        }
    }

    func test_Joined_String_Array_Performance() {
        measure {
            joinedString(strArray)
        }
    }

}

결과

 

의미있는 2배가 넘는 시간차이가 나타났네요..

다들 + 쓰지말고 joined() 사용합시다 하하..