iOS Swift의 자료 구조, 알고리즘에 대해서 알아보자 (3)

2024.10.28 - [◽️ Programming/◽️ Computer Science] - iOS Swift의 자료 구조, 알고리즘에 대해서 알아보자 (1)

2024.10.30 - [◽️ Programming/◽️ Computer Science] - iOS Swift의 자료구조, 알고리즘에 대해서 알아보자 (2)

 

오늘은 3번째 시간으로 Swift의 자료구조에 대해서 알아보고자 한다. 오늘 알아 볼 내용들은 평소 개발을 진행하면서 주로 많이 사용하는 Array, Dictionary 등 익숙한 개념이지만 이 내용을 그냥 단순하게 집합의 느낌 정도로 사용했다면 어떤 개념을 가지고 있는지 보다 더 자세하게 다뤄 보고자 한다.

 

먼저 스위프트 표준 라이브러리가 제공하는 세가지 주요 데이터 구조는 Array, Dictionary, Set 이 있다.

 

Array

배열은 일반 컨테이너로 정렬된 요소들의 컬렉션을 저장하며, 스위프트에서 일반적으로 많이 사용된다. 대괄호로 둘러싸고 쉼표로 구분한 값들의 목록인 배열 리터럴을 이용해 배열을 생성할 수 있다.

let people = ["Brian", "Stanley", "Ringo"]

Swift는 프로토콜을 이용해 배열을 정의하는데 이 각 프로토콜은 배열에 더 많은 기능을 부여한다. 예를 들어 배열은 시퀀스이기 때문에 한번 이상 반복이 가능하다. 또한 Collection이기도 하기 때문에 비파괴적으로 여러분 순회 할 수 있고, 첨자 연산자를 이용해 접근할 수도 있다.

 

스위프트의 배열은 어떤 타입에서도 작동할 수 있기 때문에 제네릭 컬렉션으로도 알려져 있다. 실제로 대부분의 표준 라이브러리는 제네릭 코드로 구축되어 있다.

 

모든 자료 구조와 마찬가지로 꼭 알아야 하는 첫번째 개념은 order (순서) 의 개념이다.

 

순서

배열의 요소는 명시적으로 정렬되어있다 위 people 배열을 예시로 들자면, “Brian”은 Stanley앞에 위치한다.

배열의 요소들은 모두 0기반의 정수 인덱스를 가지고 있다. 예를 들어 people 배열은 3개의 인덱스를 가지고 있고 각각 요소에 대응된다.

people[0] // "Brian"
people[1] // "Stanley"
people[2] // "Ringo"

배열의 자료구조에서 순서가 정의되며 이 개념을 당연하게 여겨서는 안된다. 딕셔너리와 같은 일부 자료구조는 순서에 대한 개념이 약하다.

 

랜덤 액세스

랜덤 액세스는 정해진 시간에 요소 검색을 처리할 수 있을 경우 거론할 수 있는 특성이다. 예를 들어 people 배열에서 Ringo 라는 요소를 가져오는데는 일정한 시간이 걸린다. 다시 말해 이 성능을 당연하게 여겨서는 안되며 연결리스트나 트리는 일정한 시간동안 접근하는 권한이 없다.

 

배열의 성능

랜덤 액세스 외에도 다른 성능 영역들은 개발자로써 관심을 가질 영역이다. 특히 데이터의 양이 증가할 때 자료구조가 얼마나 잘 작동하는지 혹은 작동하지 않는지 말이다. 배열의 경우 두가지 요인에 따라 달라진다.

 

첫번째 요인은 새로운 요소를 배열 어디에 삽입할 지 결정하는 것이다. 가장 효율적인 시나리오는 새로운 요소를 추가할 때 배열 가장 뒤에 추가하는 것

people.append("Charles")
print(people) // ["Brian", "Stanley", "Ringo", "Charles"]

append 메소드를 이용해 Charles를 삽입하면 배열의 가장끝에 위치하게 된다. 이를 상수 시간 constant time 작업이라고 한다.

 

이는 배열이 얼마나 커지든 상관없이 작업이 수행하는데 동일한 시간이 걸린다는 뜻이다. 하지만 배열의 한 중간과 같이 특정 위치에 요소를 삽입해야될 때도 있다.

people.insert("Andy", at: 0)
// ["Andy", "Brian", "Stanley", "Ringo", "Charles"]

모든 요소는 반드시 인덱스 하나만큼 뒤로 이동해야한다. n번의 단계가 필요하다. 만약 배열의 요소가 두배라면 삽입 작업에는 두배의 시간이 든다.

 

만약 요소를 배열에 맨 앞에 삽입하는 것이 프로그램의 일반적인 작업이라면, 데이터를 유지하기 위해 다른 자료구조를 고려해봐야 한다.

 

삽입의 속도를 결정하는 두번째 요소는 배열의 용량이다. 보이진 않지만 스위프트의 배열은 안의 요소를 위한 공간을 미리 결쟁해 할당된다.

 

이미 최대 용량인 배열에 새로운 요소를 추가한다면 배열은 더 많은 공간을 만들기 위해 재구조화 해야한다. 배열의 기존 요소들을 모두 메모리상으로 더 큰 새 컨테이너에 복사하는 것이다. 하지만 이건 배열의 각 요소에 접근하고 복사하는 비용이 발생한다.

 

어떤 삽입이든 심지어 끝에 삽입하더라도, 사본이 만들어 지는 순간 n개의 단계가 걸린다는 것이다. 하지만 표준 라이브러리는 이 복사가 발생할 때 필요한 시간을 최소화하는 전략을 차용하고 있다. 스토리지가 부족해 복사를 행할 때 마다 용량은 두배로 늘어난다.

 

딕셔너리 Dictionary

딕셔너리는 키-값의 쌍을 가지고 있는 또 다른 제네릭 콜렉션이다. 예를 들어 사용자의 이름과 스코어를 보유하는 딕셔너리가 있다.

var scores: [String: Int] = ["Eric": 9, "Mark": 12, "Wayne": 1]

딕셔너리는 순서를 보장하지 않고 특정한 인덱스에 삽입 할 수도 없다. 또한 키 타입이 Hashable 해야한다. 다행히도 거의 대부분은 표준 타입은 Hashable 하며, 최근 버전의 스위프트에서 Hashable 프로토콜은 자주 사용하게 된다.

scores["Andrew"] = 0

딕셔너리 내 새로운 키-값 쌍을 생성한다.

["Eric": 9, "Mark": 12, "Andrew": 0, "Wayne": 1]

“Andrew” 키는 딕셔너리의 어딘가에 삽입되어 있다. 딕셔너리는 순서가 지정되지 않으므로 새 항목이 어디에 들어가는지 보장할 수 없다.

 

Collection 프로토콜이 가능하므로, 딕셔너리의 키-값을 여러번 순회하는 것이 가능하다. 순회의 순서는 지정되지는 않았지만 콜렉션이 변경되기 전까지는 동일하다.

 

명시적인 순서가 없다는 단점은 일부 특성이 함께 따라간다. 배열과 다르게 딕셔너리는 요소가 섞이는 것에 대해 걱정할 필요가 없다. 딕셔너리에 삽입하는 것은 항상 일정한 상수시간이 든다.

 

조회 작업에도 똑같이 상수시간이 걸린다. 이는 배열에서 특정 요소를 찾을때 배열의 처음부터 삽입 위치까지 가야하는 것보다 현저하게 빠르다.

 

세트 Set

세트는 고유한 값을 가진 컨테이너이다. 아이템을 넣을 수 있지만 이미 가지고 있는 아이템은 거부하는 가방을 떠 올려보자

var bag: Set<String> = ["Candy", "Juice", "Gummy"]
bag.insert("Candy")
print(bag) // prints ["Candy", "Juice", "Gummy"]

세트는 고유성을 적용하므로, 콜렉션에 중복값을 찾는 등 다양한 어플리케이션에 사용된다.

let values: [String] = [...]
var bag: Set<String> = []

for value in values {
	if bag.contains(value) {
	
	}
	bag.insert(value)
}

딕셔너리나 배열처럼 세트를 자주 사용하지는 않지만 그래도 알아둬야하는 중요한 개념이다. 딕셔너리와 유사하게 세트의 값들은 순서라는 개념이 없다.