[Swift 자료구조] 1. Array 배열 (생성, CRUD, COW)

Apple Developer Documentation

https://nitinagam17.medium.com/data-structure-in-swift-ios-part-1-305dd33e19f5

위의 두 문서를 기반으로 정리했습니다.

Array

배열 : 순서가 있고 임의 접근이 가능한 컬렉션(값의 모음).

가장 흔하게 쓰는 데이터 타입이다.

Array

An ordered, random-access collection.

@frozen struct Array<Element>

• Array : 단일 타입의 요소들을 담음
• Element : Array 내부의 요소의 타입

생성

let nameArray = ["Alex", "Martin", "Harry"]
let oddNumbers = [1, 3, 5, 7, 9, 11, 13, 15]

// Element 타입을 선언해 빈 배열을 만들 수 있다
var emptyDoubles: [Double] = []
var emptyFloats: Array<Float> = Array()

var digitCounts = Array(repeating: 0, count: 10)
print(digitCounts) // [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

배열의 값에 접근하기

let oddNumbers = [1, 3, 5, 7, 9, 11, 13, 15]

if oddNumbers.isEmpty {
    print("I don't know any odd numbers.")
} else {
    print("I know \(oddNumbers.count) odd numbers.")
}
// Prints "I know 8 odd numbers."

if let firstElement = oddNumbers.first, let lastElement = oddNumbers.last {
    print(firstElement, lastElement, separator: ", ")
}
// Prints "1, 15"

print(emptyDoubles.first, emptyDoubles.last, separator: ", ")
// Prints "nil, nil"

print(oddNumbers[0], oddNumbers[3], separator: ", ")
// Prints "1, 7"

print(emptyDoubles[0])
// Triggers runtime error: Index out of range

• isEmpty : O(1)
• count : O(1)
• first
• last : O(1)
• 등등 다양한 프로퍼티가 존재함
• 서브스크립트를 사용해 인덱스로도 접근 가능

배열의 특징

for name in nameArray { // Sequence
        print(name)
}

let firstName = nameArray.[0]
let lastName = nameArray.last

• 제네릭으로 구현된 컬렉션임
  • = 어떤 타입의 데이터든 담을 수 있다.
• 배열은 Sequence 임
  • 반복문을 사용해 배열을 반복(iterate)할 수 있음.
• 배열은 컬렉션임
  • 요소를 순회할 수 있음
  • 서브스크립트를 사용할 수 있음. Array[index]
• 배열은 RandomAccessCollection 프로토콜을 준수함
  • = 효율성을 보장함
  • 예를 들어, 배열의 크기가 크든 작든 Array.count 프로퍼티의 값을 가져오는 데 동일한 시간이 걸림.

배열의 메서드 - 삽입, 삭제, 수정, 탐색 (CRUD) 등등

• 삽입 Insert
  • append(_:)
    • 배열의 마지막에 요소 삽입 : O(1) . 가장 효율적인 방법.
    • 메모리 재할당이 일어날 때는 예외적으로 O(n) 시간이 걸린다.
  • append(contentsOf:)
    • 배열의 마지막에 배열 삽입 : O(M) (M은 새로운 Elements의 개수)
  • insert(_:at:)
    • 배열의 특정 위치에 요소 삽입 : O(n)시간이 걸린다.
• 삭제 Remove
  • removeLast()
    • 배열의 마지막 요소 삭제 : O(1)
  • remove(at:)
    • 배열의 특정 위치의 요소 삭제 : O(n)
  • removeFirst()
    • 배열의 첫 요소 삭제 : O(n)
• 수정 Update
  • 이미 존재하는 요소에 새 값을 할당함으로서 값을 바꿀 수 있다.
• 탐색 Read / Search
  • 서브스크립트 : O(1)
  • contains(_:) : O(n)
  • firstIndex(of:) , lastIndex(of:)
    • 첫 번쨰로 나타나는 / 마지막으로 나타나는 원소의 인덱스 찾기 : O(n)
  • min(), max()
    • 최소/최댓값 찾기 : O(n)
• 정렬 Sort
  • sort(), sorted()
    • 정렬하기 : O(N logN) . Tim Sort 라는 방법 사용.
• split(separator:maxSplits:omittingEmptySubsequences:)
  • separator 기준으로 나누기 - O(n)

배열의 크기 늘리기

모든 배열은 요소를 담기 위해 일정량의 메모리를 차지한다.

요소를 추가했을 때 배열의 크기가 늘어나야 한다면, 기존 배열의 2배에 해당하는 새 메모리 공간을 잡고 기존 값을 복사해 넣는 식으로 크기가 늘어난다. 이러한 재할당(reallocation) 작업은 성능 비용이 있지만, 배열이 커짐에 따라 발생 빈도가 줄어든다.

만약 배열에 얼마나 많은 요소들을 저장하게 될지 대략적으로 알고 있다면, 배열에 값을 넣기 전에 reserveCapacity(_:) 메서드를 사용해 재할당을 피할 수 있다. 또, capacity 와 count 프로퍼티를 사용해 재할당 없이 얼마나 더 많은 요소들을 배열에 저장할 수 있는지 가늠할 수 있다.

배열의 복사값 수정하기

각각의 배열은 자신의 요소들을 모두 포함하는 독립적인 값을 가진다.

• 배열의 요소가 간단한 타입이나 구조체의 경우
  • 값을 통째로 복사하므로, 어떤 배열의 수정내역이 다른 배열에 영향을 미치지 않는다.
  • Swift의 배열은 구조체이기 때문에, 다른 상수나 변수에 할당되거나 함수에 전달될 때 배열의 값은 복사되어 전달된다.
  • 아래 예시 참조.

let numberArray = [1, 2, 3, 4, 5]
var otherNumberArray = numberArray

print(numberArray) // [1, 2, 3, 4, 5]
print(otherNumberArray) // [1, 2, 3, 4, 5]

otherNumberArray[2] = 10

print(numberArray) // [1, 2, 3, 4, 5]
print(otherNumberArray) // [1, 2, 10, 4, 5]

• 배열의 요소가 클래스의 인스턴스인 경우
  • 배열에 저장된 값들이 각각 배열 외부 객체에 대한 참조가 된다.
  • 같은 객체를 참조하는 배열들은, 그 객체가 변경되었을 때 함께 변경된다.
  • 아래 예시 참조.

// An integer type with reference semantics
class IntegerReference {
    var value = 10
}
var firstIntegers = [IntegerReference(), IntegerReference()]
var secondIntegers = firstIntegers

// Modifications to an instance are visible from either array
firstIntegers[0].value = 100
print(secondIntegers[0].value)
// Prints "100"

// Replacements, additions, and removals are still visible
// only in the modified array
firstIntegers[0] = IntegerReference()
print(firstIntegers[0].value)
// Prints "10"
print(secondIntegers[0].value)
// Prints "100"

배열의 Copy-On-Write (COW)

Swift Standard Library의 모든 가변 크기 컬렉션과 마찬가지로, 배열도 copy-on-write 최적화를 사용한다.

한 배열에 대한 여러 복사본이 있더라 해도, 그 중 하나를 수정하기 전까지는 같은 저장 공간을 공유한다.

만약 복사본에 대한 수정이 생기면, 그 시점에 비로소 복사본이 별도의 저장공간을 만들어 갖게 되고, 그 자리에서 수정이 이루어진다.

즉, 배열이 다른 (배열의)복사본들과 저장 공간을 공유하는 경우, 그 배열에 대해 처음으로 이루어지는 변경 연산은 ‘배열의 복사’라는 비용을 발생시킵니다. 저장 공간의 유일한 소유권을 갖는 배열만이 제자리에서 변경 연산을 수행할 수 있기 때문입니다.

var numbers = [1, 2, 3, 4, 5]
var firstCopy = numbers
var secondCopy = numbers

// The storage for 'numbers' is copied here
numbers[0] = 100
numbers[1] = 200
numbers[2] = 300
// 'numbers' is [100, 200, 300, 4, 5]
// 'firstCopy' and 'secondCopy' are [1, 2, 3, 4, 5]

위 예시에서, numbers 배열은 같은 저장공간을 공유하는 두 복사본과 함께 생성되었습니다. 원래의 배열인 numbers 배열이 수정될 때, 그 시점에 numbers 는 비로소 자신만의 유일한 복사본을 만들고, 그 다음 수정 작업을 합니다. 그 이후 numbers 에 대한 수정 작업은 제자리에서 수행됩니다. 값이 수정된 적이 없는 두 복사본은 여전히 원래의 저장 공간을 공유합니다.