Swift에서 효율적으로 배열쓰기

도입
Swift로 조합을 구현하는 코드를 작성해보려고 하면, 다음과 같이 작성할 수 있습니다.

  // Swift Algorithm Club 오픈 채팅방에서 Algo님이 작성해주신 코드입니다.
  func getCombination<T>(elements: Array<T>, select: Int, repetition: Bool) -> [[T]] {
      guard select > 0 else {
          return [[]]
      }

      guard let firstElement = elements.first else {
          return []
      }

      let head = [firstElement]
      let subCombination = getCombination(elements: repetition ? elements :  Array(elements.dropFirst()), select: select - 1, repetition: repetition)

      var combination = subCombination.map { $0 + head }
      combination += getCombination(elements: Array(elements.dropFirst()), select: select, repetition: repetition)

      return combination
  }

결과는 잘 나오지만 성능적인 부분에서는 아쉬운 부분이 있습니다.

subCombination을 구할 때, dropFirst()를 수행한 결과를 다시 Array로 바꾸고 있습니다. 이는 새로운 Array 인스턴스를 만들면서 값의 복사를 유발합니다.
subCombination의 결과를 map을 통해서 다시 Array로 반환하고 있습니다. 이 과정이 재귀 호출을 거치면서 많은 양의 복사 연산을 유발합니다.

이 값 복사들은 굳이 수행할 필요가 없는 동작입니다. 이것을 어떻게 최적화할 수 있을까요?

ArraySlice
Array는 drop, prefix등 원소의 일부분만을 가져오기 위한 메소드를 제공합니다. 그런데 이들의 반환값은 같은 Array가 아니라 ArraySlice라는 별도 타입입니다. 이것 때문에 시그니처가 호환되지 않아서 그대로는 함수호출이 안되기 때문에 Array로 바꾸는 코드가 예제에도 있습니다. 하지만 이는 위에서 말했다시피 배열의 복사를 일으킵니다. 그렇다면 ArraySlice가 뭐길래 이렇게 불편하게 만들어 놨을까요?

ArraySlice는 Array의 SubSequence입니다. SubSequence는 Collection 프로토콜에서 associatedType으로 요구하는 것으로, 해당 콜렉션의 일부분을 효과적으로 참조하기 위해서 존재하는 타입입니다. 이 SubSequence는 원본 Collection의 참조처럼 동작하고, 원본 콜렉션 인덱스 범위의 부분 집합을 유효한 인덱스 범위로 가지게 됩니다.

주의할 점은 원본 배열이 바뀌게 되면 이 SubSequence는 원본 Collection과의 연관성이 사라지게 되면서 쓸모없는 데이터가 된다는 것입니다. 이는 반대로 SubSequence를 통해서 내용물을 변경해도 마찬가지입니다. 즉, SubSequence는 원본배열이 바뀌지 않을때, 효율적으로 일부분만 넘기는데 사용할 수 있습니다.

  var arr = [1,2,3]
  var slice = arr.dropFirst()

  print(arr.indices) // 0..<3
  print(slice.indices) // 1..<3

  slice[2] = 4 // 이 시점에서 원본 배열과 slice의 연관성은 사라졌습니다. 이는 arr을 통해서 원소를 바꿔도 마찬가지입니다.

  print(arr) // [1, 2, 3]
  print(slice) // [2, 4]

이제 위 코드를 ArraySlice를 통해서 넘기도록 수정하겠습니다.

func getCombinationImmediate<T>(elements: Array<T>, select: Int, repetition: Bool) -> [[T]] {
  func getCombination<T>(elements: ArraySlice<T>, select: Int, repetition: Bool) -> [[T]] {
      guard select > 0 else {
          return [[]]
      }

      guard let firstElement = elements.first else {
          return []
      }

      let head = [firstElement]
      let subCombination = getCombination(elements: repetition ? elements :  elements.dropFirst(), select: select - 1, repetition: repetition)

      var combination = subCombination.map { $0 + head }
      combination += getCombination(elements: elements.dropFirst(), select: select, repetition: repetition)

      return combination
  }

  return getCombination(elements: elements[...], select: select, repetition: repetition)
}

성능 테스트를 할텐데, 테스트 코드를 실행한 장비의 스펙은 다음과 같습니다.

SystemSpec

테스트 코드와 결과는 다음과 같습니다.

import XCTest

class AlgorithmTest: XCTestCase {

  var values = Array(repeating: 100, count: 20)
  func testOriginalCombination() throws {
      measure {
          for i in 1..<10 {
              _ = getCombinationOriginal(elements: values, select: i, repetition: false)
          }
      }
  }

  func testIntermediateCombination() throws {
      measure {
          for i in 1..<10 {
              _ = getCombinationIntermediate(elements: values, select: i, repetition: false)
          }
      }
  }

  func testOriginalCombinationWithRepetition() throws {
      measure {
          for i in 1..<10 {
              _ = getCombinationOriginal(elements: values, select: i, repetition: true)
          }
      }
  }

  func testIntermediateCombinationWithRepetition() throws {
      measure {
          for i in 1..<10 {
              _ = getCombinationIntermediate(elements: values, select: i, repetition: true)
          }
      }
  }
}

IntermediateTest

약간의 성능 향상이 있음을 볼 수 있습니다. 하지만 좀 더 잘할 수는 없을까요?

inout으로 변경하기
결과값을 만들어내는 부분을 보면 매번 새로운 배열을 만들어서 반환하고, 이를 다시 합치고 있음을 알 수 있습니다. 이는 상당히 많은 배열이 중간단계에서 만들어지고 사라짐을 뜻합니다. 이 과정을 줄이려면 배열을 반환값으로 쓰는게 아니라, inout으로 그자리에서 직접 바꾸는 게 중간 단계 배열을 덜 만들 수 있기 때문에 더 효율적입니다. 여기서는 결과값 배열과 최종 결과 배열을 inout으로 받아서 직접 바꾸도록 수정하겠습니다.

func getCombinationRefined<T>(elements:[T], select: Int, repetition: Bool) -> [[T]] {
  func getCombination<T>(elements: ArraySlice<T>, select: Int, repetition: Bool,  partialResult: inout [T], totalResult: inout [[T]]) {
      guard select > 0 else {
          totalResult.append(partialResult)
          return
      }

      guard let firstElement = elements.first else { return }

      let remains = elements.dropFirst()

      partialResult.append(firstElement)
      if repetition {
          getCombination(elements: elements, select: select-1, repetition: repetition, partialResult: &partialResult, totalResult: &totalResult)
      } else {
          getCombination(elements: remains, select: select-1, repetition: repetition, partialResult: &partialResult, totalResult: &totalResult)
      }
      partialResult.removeLast()


      getCombination(elements: remains, select: select, repetition: repetition, partialResult: &partialResult, totalResult: &totalResult)
  }

  var result: [[T]] = []
  var partialResult: [T] = []
  partialResult.reserveCapacity(select)

  getCombination(elements: elements[...], select: select, repetition: repetition, partialResult: &partialResult, totalResult: &result)

  return result
}

여기서 partialResult는 최대 select만큼만 원소가 담길 것으로 예상할 수 있으므로, reserveCapacity로 좀 더 성능 향상을 꾀할 수 있습니다. 위 테스트 코드에 이를 테스트 하는 코드를 추가한 뒤 실행하면 결과가 다음과 같습니다.

FinalTest

극적인 성능 향상이 있음을 알 수 있습니다.

성능 테스트를 실행할 때 주의사항
성능테스트는 반드시 실제 실행될 코드로 수행해야 합니다. 따라서 디버그 모드가 아닌 릴리즈 모드로 컴파일을 수행하여 테스트를 진행해야 합니다. 위에서 실행한 테스트 결과는 모두 릴리즈 모드에서 실행한 결과로, 디버그 모드에서 같은 테스트를 수행했을 때는 다음과 같이 상당한 차이를 보입니다.

성능은 언제나 개발에서 중요한 고려요소입니다. 이를 위해서는 Swift의 이런 특징들을 잘 이해하고 있어야만 합니다.