Jenikeju

비동기 프로그래밍은 개발에 있어서 중요한 부분입니다.

하나의 앱은 한개의 프로세스가 순차적으로 이루어지는 것이 아닌 다양한 작업이 동시다발적으로 이루어지기 때문에 이러한 작업을 효율적으로 나누고 한번에 처리하도록 설계해야합니다.

설계하는데 있어서 중요한 비동기 프로그래밍에 대해서 적어보고자 합니다.

동기 / 비동기

동기(Synchronous): 작업이 완료될 때까지 대기한 후, 작업이 완료되면 다음 작업을 실행

비동기(Asynchronous): 작업 완료를 기다리지 않고 바로 다음 작업을 실행

직렬(serial) / 병렬(concurrent)

직렬(Serial): 순차적으로 진행

병렬(Concurrent): 동시에 진행

이름에서 의미를 찾아 볼 수 있지만, 직렬 병렬을 나누는 이유는 작업이 들어가는 큐에는 직렬 수행, 병렬 수행을 지정할 수 있기 떄문입니다.

Main Queue(Serial): Main thread로 serial queue를 사용합니다.

Global Queue(Concurrent): 그 외 thread로 concurrent queue를 사용합니다.

Custom Queue(Serial & Concurrent): 직렬, 병렬 수행을 직접 지정한 queue를 사용합니다.

DispatchQueue

iOS에서 비동기 프로그래밍을 설계할 수 있도록 지원하는 API입니다.

별도로 설치없이 사용할 수 있고 구문은 다음과 같습니다.

// Main Thread에서 비동기적 실행
DispatchQueue.main.async {
    
}
// Sub Thread에서 동기적 실행
DispatchQueue.global().sync {
    
}
// Sub Thread에서 비동기적 실행
DispatchQueue.global().async {
    
}

class 와 같은 인스턴스는 참조 형식 인스턴스 입니다.

두 개의 참조 형식 인스턴스가 서로 강한 참조(Strong reference)를 한다면 순환 참조가 발생합니다.

이는 두 인스턴스가 메모리에서 해제되어도 서로에 대한 참조가 해제되지 않기 때문에 메모리에 남게되고 심해지면 메모리 릭 현상이 발생합니다.

이러한 순환참조를 해결하기 위해 참조할 때 weak, unowned 키워드를 사용합니다.

먼저 순환참조가 발생하는 예시입니다.

// Person Class
class Person {
    var name: String
    var pet: Pet?
    
    init(name: String) {
        self.name = name
        print("Person init")
    }
    deinit {
        print("Person deinit")
    }
}
// Pet Class
class Pet {
    var owner: Person?
    
    init() {
        print("Pet init")
    }
    
    deinit {
        print("Pet deinit")
    }
}

// 두 개의 인스턴스 생성
var person: Person?
var pet: Pet?
person = Person(name: "cheolsu")
pet = Pet()

// 각 인스턴스의 속성을 다른 인스턴스가 강한 참조하도록 설정
person?.pet = pet
pet?.owner = person

// 메모리에서 해제한다.
person = nil
pet = nil

// 출력 결과
Person init
Pet init
-> Person 클래스와 Pet 클래스의 메모리 해제가 이루어지지 않음

person, pet 인스턴스를 모두 메모리에서 해제하여도 deinit 이 되지 않았습니다.

결국 서로의 참조 상태는 메모리에 남아있습니다.

약한 참조 weak

선언하는 프로퍼티 앞에 weak 키워드를 붙여 약한 참조하도록 명시적으로 설정하는 방법입니다.

class Pet {
    weak var owner: Person?
    
    init() {
        print("Pet init")
    }
    
    deinit {
        print("Pet deinit")
    }
}

weak 키워드가 붙여진 프로퍼티는 다음과 같은 특징을 갖고 있습니다.

- 참조하는 인스턴스의 RC(Reference Count)를 증가시키지 않습니다.

- 참조하는 인스턴스가 메모리에서 해제되면 nil이 할당되어 메모리에서 해제시킵니다.

- 런타임중 nil이 할당되는 경우가 존재할 수 있으므로 옵셔널 형식입니다.

unowned

두번째로는 unowned 키워드를 선언하는 프로퍼티 앞에 붙이는 방법이 있습니다.

class Pet {
    unowned var owner: Person
    
    init() {
        print("Pet init")
    }
    
    deinit {
        print("Pet deinit")
    }
}

unowned 키워드가 붙여진 프로퍼티는 다음과 같은 특징을 갖고 있습니다.

- 참조하는 인스턴스의 RC(Reference Count)를 증가시키지 않습니다.

- 참조하는 인스턴스가 메모리에서 해제되어도 여전히 Heap영역의 인스턴스를 가리키는 포인터가 됩니다.

따라서 unowned은 옵셔널 형식이 아니게 됩니다.

weak와 unowned의 차이점은 참조하는 인스턴스가 메모리에서 해제될 때 나타납니다.

weak은 nil이 되지만, unowned은 여전히 포인터로 남습니다.

따라서 참조되는 인스턴스가 메모리에 할당되는 기간이 참조하는 인스턴스보다 짧다면 weak을 사용하는 편이 좋고,

참조되는 인스턴스가 메모리에 할당되는 기간이 참조하는 인스턴스보다 같거나 길다면, 또는 필연적인 관계라면 unowned를 사용하는게 좋습니다.

배열

- 데이터를 순차적으로 저장하는 구조

- 인덱스를 사용해 특정위치의 요소에 접근할 수 있음

- 특정 인덱스를 통해 접근하는 것은 빠르지만(O(1)), 삽입/삭제 과정은 오래걸린다(O(n))

예시

큐

선입선출의 형식인 데이터구조 (FIFO)

- Enqueue: 큐 맨 뒤에 요소 추가

- Dequeue: 큐 맨 앞의 데이터를 반환

- Peek: Front에 위치한 데이터 값 반환

- Front: 큐의 앞부분 (가장 먼저 들어온 데이터가 위치함)

- Rear: 큐의 뒷부분 ( 가장 최근에 들어온 데이터가 위치함)

dequeue하는 과정에서 removeFirst() 메소드를 이용한다면 시간복잡도가 O(n)이 걸리게된다.

이를 해결하기위해 index를 이용해 front부분을 확인하여 데이터를 반환하는 방법도 있지만,

reversed()도 O(1)이 걸리므로 이 방법을 사용했다.

import Foundation

struct Queue<T> {
    var elements: [T] = []
    
    // 큐 갯수
    var count: Int {
        return elements.count
    }
    // 큐의 가장 먼저 나갈 데이터
    var peek: T? {
        if elements.isEmpty {
            return nil
        } else {
            return elements[0]
        }
    }
    // 큐의 앞부분
    var front: T? {
        if elements.isEmpty {
            return nil
        } else {
            return elements[0]
        }
    }
    // 큐의 뒷부분
    var rear: T? {
        if elements.isEmpty {
            return nil
        } else {
            return elements.last!
        }
    }
    // 큐 비어있는지
    var isEmpty: Bool {
        return elements.isEmpty
    }
    // 큐 데이터 삽입
    mutating func enqueue(element: T) {
        elements.append(element)
    }
    // 큐 데이터 삭제(반환)
    mutating func dequeue() -> T? {
        if elements.isEmpty {
            return nil
        } else {
            var arr = Array(elements.reversed())
            let returnValue = arr.popLast()
            elements = Array(arr.reversed())
            return returnValue
        }
    }
}

구조체와 클래스는 비슷하면서 서로 다른 성질을 갖고 있습니다.

먼저 공통점으로는 다음과 같습니다.

- 변수나 상수를 사용하여 값을 저장하는 프로퍼티로 정의할 수 있음

- 함수를 사용하여 기능을 제공하는 메서드로 정의할 수 있음

- 속성값에 접근할 수 있는 방법을 제공하는 서브스크립트를 정의할 수 있음

- 객체를 원하는 초기 상태로 설정해주는 초기화 블록(init)을 정의할 수 있음

- 객체에 함수적 기능을 추가하는 확장 구문을 사용할 수 있음

- 특정 형식의 함수적 표준을 제공하기 위한 프로토콜을 구현할 수 있음

이와 같은 공통점이 있지만, 구조체에서는 안되지만 클래스에서는 할 수 있는 기능이 다음과 같이 있습니다.

- 클래스의 특성을 다른 클래스에게 물려줄 수 없음

- 실행 시 컴파일러가 클래스 인스턴스의 타입을 미리 파악하고 검사할 수 있음

- 인스턴스가 소멸되기 직전에 처리해야 할 구문을 미리 등록해 놓을 수 있음 (deinit)

- 클래스 인스턴스가 전달될 때에는 참조 형식으로 제공되며, 참조가 가능한 개수는 제약이 없음

 또한 클래스는 참조형식, 구조체는 값형식 프로퍼티로 클래스는 값이 변경됨에 따라 참조된 클래스의 값에 영향을 주고 구조체는 영향을 주지 않는 성질을 갖고 있습니다.

// 구조체
struct User {
    var name: String
    var age: Int
}

var userStruct = User(name: "", age: 0)
var cheolsu = userStruct
var yuri = userStruct

print("cheolsu: \(cheolsu)")
print("yuri: \(yuri)")

yuri.name = "yuri"
yuri.age = 5

print("cheolsu: \(cheolsu)")
print("yuri: \(yuri)")

// 출력 결과
cheolsu: User(name: "", age: 0)
yuri: User(name: "", age: 0)
cheolsu: User(name: "", age: 0)
yuri: User(name: "yuri", age: 5)
// yuri의 값을 변경했지만 cheolsu 객체에 영향을 주지 않는다.

// 클래스
class User {
    var name: String = ""
    var age: Int = 0
}

var userClass = User()
var cheolsuClass = userClass
var yuriClass = userClass

yuriClass.name = "yuri"
yuriClass.age = 5

print(yuriClass.age)
print(yuriClass.name)
print(cheolsuClass.age)
print(cheolsuClass.name)

// 출력 결과
5
yuri
5
yuri
// yuri의 값을 변경했지만, cheolsu객체의 특성도 변경되었다.

- Swift.org를 참고하여 작성

Swift는 구조화된 방식으로 비동기 및 병렬 코드를 작성하기위해 기본적으로 기능을 제공합니다.

Swift의 언어자원을 사용하지 않고도 동시코드를 작성할 수 있지만, 읽기가 더 어렵고 복잡합니다.

사용하지 않은 예

listPhotos(inGallery: "Summer Vacation") { photoNames in
    let sortedNames = photoNames.sorted()
    let name = sortedNames[0]
    downloadPhoto(named: name) { photo in
        show(photo)
    }
}

위 예제에서도 코드를 완료 핸들러로 작성해야 하기 때문에 중첩된 클로저를 사용하게 되고, 코드가 더 복잡하여 다루기 힘들어질 수 있습니다.

비동기 함수 및 호출

Swift에서 제공하는 비동기 함수 또는 비동기 메서드는 실행 중간에 일시 중단될 수 있는 특수한 종류의 함수 또는 메서드 입니다.

비동기 함수는 동기함수처럼 실행되거나 오류를 발생시키거나 반환하지않는 세가지 중 하나를 수행하지만, 중간에 일시 중단할 수 도 있습니다. 본문 내부에서 실행을 일시 중단할 수 있는 위치를 표시합니다.

먼저 함수나 메서드가 비동기함수임을 나타내려면 선언에서 매개변수 뒤 async 키워드를 작성하면됩니다. 이는 throws throw 함수를 표시하는데 사용하는 방법과 비슷합니다.

함수나 메서드가 값을 반환하는 경우 return 화살표 앞에 async 를 쓰면 됩니다. 

func listPhotos(inGallery name: String) async -> [String] {
    let result = // ... some asynchronous networking code ...
    return result
}

- 비동기면서 에러를 반환하는 throws기능을 하는 함수나 메서드인 경우 throws 앞에 async를 작성합니다.

func dataFetch<T: Decodable>(type: T.Type) async throws -> T? {
        return try await AF.request(components.getComponents()).serializingDecodable(T.self).value
    }

비동기 메서드를 호출할 때 해당 메서드가 반환될 때까지 실행이 중단됩니다. 이때 await 키워드를 작성하여 비동기 함수를 호출 하는 지점 앞에 중단지점을 표시합니다. 이는 try throw 함수를 호출할 때 오류가 발생하는 경우 프로그램 흐름에 대한 변경 가능 사항을 표시하기 위해 작성하는 것과 같습니다. 중단은 중단지점 없이 암묵적으로 진행되거나 먼저 진행되지 않습니다.

코드의 실행 과정

let photoNames = await listPhotos(inGallery: "Summer Vacation")
let sortedNames = photoNames.sorted()
let name = sortedNames[0]
let photo = await downloadPhoto(named: name)
show(photo)

1. 첫째줄 코드가 실행을 시작하여 listPhotos함수가 실행되고 반환될 때 까지 일시 중단됩니다.

2. 이 코드가 중단되는 동안 다른 동시코드들은 실행이 됩니다.

3. listPhotos가 반환되고 반환된 값을 photoNames에 할당합니다. 코드는 일시중단된 지점에서 다시 시작합니다.

4. sortedName를 정의하고 name에 값을 할당합니다. await 표시가 없는 동기 함수이므로 그대로 실행됩니다.

5. 다음 함수는 downloadPhoto를 호출하는 함수입니다. 해당 함수가 반환될때 까지 일시 중단하여 다른 동시코드가 실행할 수 있도록 기회를 제공합니다.

6. downloadPhoto 반환 후 반환된 값이 할당되고 show함수를 호출할 때 인자로 전달됩니다.

-> 비동기함수를 호출할 때 await 키워드가 적힌 곳은 현재 코드가 실행을 일시 중지할 수 있음을 나타냅니다. 이를 스레드 양보라고 합니다. Swift가 내부적으로 현재 스레드에서 코드 실행을 일시 중지하고 대신 해당 스레드에서 다른 코드를 실행하기 때문입니다. 

Task.yield()

Task.yield() 메서드를 호출하여 명시적으로 중단지점을 삽입 할 수 있습니다.

func generateSlideshow(forGallery gallery: String) async {
    let photos = await listPhotos(inGallery: gallery)
    for photo in photos {
        // ... render a few seconds of video for this photo ...
        await Task.yield()
    }
}

예시로 비디오를 렌더링하는 코드가 동기식이라면, 그 코드는 await같은 정지지점을 포함하지 않습니다. 비디오를 렌더링 하는 작업은 오랜시간이 걸릴 수 있으므로 위와 같이 주기적으로 호출하여 정지점을 명시적으로 추가할 수 있습니다.

Task.sleep(for: second)

중단 최소시간을 지정하여 일시중단할 수 있습니다.

func listPhotos(inGallery name: String) async throws -> [String] {
    try await Task.sleep(for: .seconds(2))
    return ["IMG001", "IMG99", "IMG0404"]
}

위 함수는 비동기적이면서 오류를 리턴할 수 있는 async throw 함수입니다. 위와 같은 함수를 호출할 때는 try await 모두 작성합니다.

let photos = try await listPhotos(inGallery: "A Rainy Weekend")

비동기 함수는 throw함수와 유사하지만 중요한 차이점이 있습니다.

throw코드는 do-catch블록으로 감싸서 오류를 처리하거나 Result<Data, Error>오류를 저장하여 다른곳에서 처리할 수 있습니다.

func availableRainyWeekendPhotos() -> Result<[String], Error> {
    return Result {
        try listDownloadedPhotos(inGallery: "A Rainy Weekend")
    }
}

반면 비동기 코드를 래핑하여 동기 코드에서 호출하고 결과를 기다릴 수 있는 안전한 방법은 없습니다. 이를 직접 구현하려고 하면 미묘한 경합, 스레딩 문제 및 교착상태와 같은 문제가 발생할 수 있습니다. 

비동기 시퀀스

이전에는 배열의 모든 요소가 준비된 후 전체배열을 한번에 비동기적으로 반환했지만 비동기 시퀀스를 사용하여 한번에 한개의 요소를 기다는 방법도 있습니다. 비동기 시퀀스를 반복하는 모습은 다음과 같습니다.

import Foundation


let handle = FileHandle.standardInput
for try await line in handle.bytes.lines {
    print(line)
}

일반적은 for-in루프를 사용하는 대신 뒤에 try await을 사용합니다.

비동기 함수를 병렬로 호출

비동기 함수를 호출하면 한번에 한개의 코드만 실행됩니다. 비동기 코드가 실행되는 동안 호출자는 다음 코드 줄을 실행하기 전 해당 코드가 완료될 때까지 기다립니다. 예를 들어 갤러리에서 처음 세 장의 사진을 가져오려면 다음과 같이 downloadPhoto 함수에 대한 세 번의 호출을 기다릴 수 있습니다.

let firstPhoto = await downloadPhoto(named: photoNames[0])
let secondPhoto = await downloadPhoto(named: photoNames[1])
let thirdPhoto = await downloadPhoto(named: photoNames[2])


let photos = [firstPhoto, secondPhoto, thirdPhoto]
show(photos)

이 접근 방식에는 중요한 단점이 있습니다. 다운로드가 완료되기 전에 다음 다운로드가 진행되지 않는다는 점 입니다.

이러한 작업을 기다릴 필요 없이 독립적으로 또는 동시에 다운로드할 수 있습니다.

async let firstPhoto = downloadPhoto(named: photoNames[0])
async let secondPhoto = downloadPhoto(named: photoNames[1])
async let thirdPhoto = downloadPhoto(named: photoNames[2])


let photos = await [firstPhoto, secondPhoto, thirdPhoto]
show(photos)

비동기 함수를 호출하고 주변 코드와 병렬로 실행하려면 상수를 정의할 때 let앞에 async를 쓰고 상수를 사용할 때마다 뒤에 await를 씁니다. 위 예제에서 세 개의 호출은 모두 이전 호출이 완료될 때까지 기다리지 않고 시작합니다. 코드가 함수의 결과를 기다리지 위해 일시 중지 되지 않기 때문에 함수 호출 중 어느곳도 await로 표시되지 않습니다. 대신 photos가 정의된 줄까지 실행이 계속 됩니다. 이 비동기 호출의 결과가 필요하므로 세장의 사진 모두 다운로드가 완료될 때까지 실행을 일시 중지하기 위해 await를 작성합니다.

두가지 접근 방식의 차이점은 다음과 같습니다.

• 다음 줄의 코드가 해당 함수의 결과에따라 달라지는 경우 await를 사용하여 비동기 함수를 호출합니다. 이렇게 하면 순차적으로 수행되는 작업이 생성됩니다.
• 해당 함수의 결과와 상관없는경우 async-let으로 비동기 함수를 호출합니다. 이렇게하면 병렬로 수행할 수 있는 작업이 생성됩니다.
• await 및 async-let 둘 다 일시중단된 동안 다른코드가 실행되도록 허용합니다.
• await는 두 경우 모두 필요한 경우 비동기 함수가 반환될 때 까지 실행이 일시 중지됨을 나타냅니다.

작업 및 작업 그룹 Task and Task Groups

Task는 프로그램의 일부가 비동기적으로 실행할 수 있는 작업단위입니다. 모든 비동기 코드는 일부 작업의 일부로 실행됩니다. Task 자체는 한가지 작업만 수행하지만 여러 작업을 만들면 동시에 실행되도록 예약할 수 있습니다.

이전 섹션에서 설명한 async-let구문은 암시적으로 자식 Task를 생성합니다. 이 구문은 프로그램에서 실행해야 하는 작업을 이미 알고 있는 경우에 효과적입니다. Task Group을 생성하고 해당 그룹에 자식 Task를 명시적으로 추가할 수도 있습니다. 이를 통해 우선수위와 작업 취소를 더 제어하기 쉽고 동적인 작업 수를 생성할 수 있습니다.

Task는 계층구조로 배열됩니다. 주어진 Task Group 에서 각 Task는 동일한 부모 작업을 갖고 자식 Task를 가질 수 있습니다.

Task와 Task Group간의 명시적 관계 때문에 이 접근 방식을 구조적 동시성 이라고 합니다. 이런 관계에는 여러가지 이점이 있습니다.

• 부모 작업에서는 자식 작업이 완료될 때까지 기다리는 것을 잊을 수 없다.
• 자식 작업에 더 높은 우선순위를 설정하면 부모 작업의 우선순위가 자동으로 높아진다.
• 부모 작업이 취소되면, 해당 자식 작업도 모두 자동으로 취소된다.
• 작업 로컬 값은 자식 작업으로 효율적이고 자동으로 전파됩니다.

다음은 많은 사진 다운로드 할 수 있는 코드입니다.

await withTaskGroup(of: Data.self) { group in
    let photoNames = await listPhotos(inGallery: "Summer Vacation")
    for name in photoNames {
        group.addTask {
            return await downloadPhoto(named: name)
        }
    }


    for await photo in group {
        show(photo)
    }
}

위 코드는 새로운 Task Group을 만든 다음, 갤러리의 각 사진을 다운로드하기 위한 자식 Task를 만듭니다. Swift는 조건이 허락되면 작업을 동시에 실행합니다. 자식 Task가 사진 다운로드를 완료하자마자 해당 사진이 표시됩니다. 완료되는 순서에 대한 보장은 없어서 갤러리의 사진은 어떤 순서로든 표시될 수 있습니다.

- 사진을 다운로드하는 코드에서 오류가 발생하면 대신 withThrowingTaskGruop을 호출하면 됩니다.

위 코드는 사진을 다운로드된 다음 표시되므로 Task Group은 결과를 반환하지 않습니다.

결과를 변환하는 Task Group인 경우 클로저 내부에 결과를 누적하여 전달하는 코드를 추가합니다.

let photos = await withTaskGroup(of: Data.self) { group in
    let photoNames = await listPhotos(inGallery: "Summer Vacation")
    for name in photoNames {
        group.addTask {
            return await downloadPhoto(named: name)
        }
    }


    var results: [Data] = []
    for await photo in group {
        results.append(photo)
    }


    return results
}

이전 예제와 마찬가자로 이 예제도 각 사진에 대한 다운로드할 자식 Task를 생성합니다. for-await-in 루프는 다음 작업이 완료될 때까지 기다리고 해당 작업의 결과를 결과배열에 추가한 다음 모든 자식 Task가 완료될 때까지 계속 기다립니다. 마지막으로 다운로드한 사진배열을 전체 결과로 반환합니다.

작업 취소 Task Cancellation

Swift 동시성은 협력 취소 모델을 사용합니다. 각 Task는 실행의 적절한 지점에서 취소되었는지 확인하고 적절하게 대응합니다.

취소에 대한 대응은 일반적으로 다음 중 하나를 의미합니다.

• CancellationErro와 같은 오류가 발생했을 때
• nil 또는 빈 컬렉션을 반환할 때
• 부분적으로 완료된 작업을 반환할 때

데이터가 크거나 네트워크가 느린경우 다운로드하는데 시간이 오래걸릴 수 있습니다. 모든 작업이 완료될 때까지 기다리지 않고 사용자가 작업중지할 수 있도록 하려면 작업이 취소되었는지 확인하고 취소된 경우 실행을 중지해야 합니다. 여기엔 두가지 방법이 있습니다.

Task.checkCancellation() type메서드를 호출하거나 Task.isCancelled type 속성을 읽는것

작업이 취소되면 check Cancellation() 호출시 오류가 발생합니다. throw 작업은 오류를 작업 외부로 전파하여 Task의 모든 작업을 중지할 수 있습니다. 이는 구현과 이해가 간단하다는 장점이 있습니다.

유연성을 높이려면 isCancelled속성을 사용하는 방법이 있습니다. 이 속성을 사용하면 네트워크 연결 닫기, 임시 파일 삭제 등 작업 중지의 일부로 정리 작업을 수행할 수 있습니다.

let photos = await withTaskGroup(of: Optional<Data>.self) { group in
    let photoNames = await listPhotos(inGallery: "Summer Vacation")
    for name in photoNames {
        let added = group.addTaskUnlessCancelled {
            guard !Task.isCancelled else { return nil }
            return await downloadPhoto(named: name)
        }
        guard added else { break }
    }


    var results: [Data] = []
    for await photo in group {
        if let photo { results.append(photo) }
    }
    return results
}

위 코드는 이전 버전과 비교해 여러 가지 변경 사항을 적용했습니다.

• 각 작업은 취소 후 새 작업을 시작하는 것을 방지하기 위해 TaskGroup.addTaskUnlessCancelled(priority: operation: ) 사용합니다.
• addTaskUnlessCancelled 에 대한 호출 후 코드는 새 자식 Task가 추가되었음을 확인합니다. 그룹이 취소되면 added 값은 false가 됩니다. 이 경우 코드는 추가 사진을 다운로드 하려는 시도를 중단합니다.
• 각 Task는 사진을 다운로드하기 전에 취소 여부를 확인합니다. 취소된 경우 Task는 nil로 반환됩니다.
• 마지막으로 각 Task Group은 결과를 확인할 때 nil 값을 건너뜁니다. nil 반환을 통해 취소를 처리한다는 것은 Task Group이 완료된 작업을 삭제하는 대신 취소 시 이미 다운로드한 사진으로 부분 결과를 반환할 수 있음을 의미합니다. 

- 해당 작업 외부에서 작업이 취소되었는지 확인하려면 Task.isCancelled type 속성 대신 instance 속성을 사용합니다.

만약 취소에 대한 즉각적인 통지가 필요한 작업의 경우 이 방법을 사용합니다:

Task.withTaskCancellationHandler(operation: onCancel: isolation:)

let task = await Task.withTaskCancellationHandler {
    // ...
} onCancel: {
    print("Canceled!")
}


// ... some time later...
task.cancel()  // Prints "Canceled!"

취소 핸들러를 사용할때 작업 취소는 여전히 협력적입니다. 작업은 완료될 때까지 실행되거나 취소를 확인한 후 일찍 중지됩니다. 취소 핸들러가 시작될 떄 작업이 계속 실행 중이므로 작업과 해당 취소 핸들러 사이 상태를 공유하지 마세요. 이로 인해 데이터 레이스 현상이 발생할 수 있습니다.

구조화되지 않은 동시성 Unstructured Concurrency

이전 섹션에서는 동시성에 대한 구조화된 접근방식이였습니다. 그외에도 Swift는 구조화되지 않은 동시성도 지원합니다.

Task Group의 일부 Task와 다르게 구조화되지 않은 작업에는 부모 작업이 없습니다. 프로그램이 의도한 방식대로 구조화되지 않은 작업을 관리할 수 있다는 완전한 유연성을 갖고 있지만 정확성에 대한 전적인 책임도 프로그램한테 존재합니다. Actor에서 실행되는 구조화되지 않은 Task를 생성하려면 Task.init(priority: Operation:) 생성자를 호출하세요. 액터의 일부가 아닌 구조화되지 않은 작업을 생성하려면 Task.detached(priority: Operation:) 클래스 메서드를 호출하세요. 두 작업 모두 결과를 기다리거나 취소하는 등 상호작용할 수 있는 Task를 반환합니다.

let newPhoto = // ... some photo data ...
let handle = Task {
    return await add(newPhoto, toGalleryNamed: "Spring Adventures")
}
let result = await handle.value

Task에 대한 자세한 정보

https://developer.apple.com/documentation/swift/task

Actors

Task를 사용하여 프로그램을 격리도니 동시적 부분으로 나눌 수 있습니다. 작업은 서로 격리되어 있어 동시에 실행해도 안전하지만, 때로는 작업 간에 일부 정보를 공유해야 합니다. actor를 사용하면 동시적 코드 간에 안전하게 정보를 공유할 수 있습니다.

클래스와 마찬가지로 actor는 참조유형입니다. 참조 유형과 값 유형의 비교는 클래스뿐만 아니라 actor에도 적용됩니다.

클래스와 달리 actor는 한번에 하나의 작업만 변경 가능한 상태에 액세스하도록 허용하므로 여러 작업의 코드가 액터의 동일한 인스턴스와 상호 작용하는 것이 안전합니다.

여기 온도를 기록하는 actor가 있습니다.

actor TemperatureLogger {
    let label: String
    var measurements: [Int]
    private(set) var max: Int


    init(label: String, measurement: Int) {
        self.label = label
        self.measurements = [measurement]
        self.max = measurement
    }
}

actor 키워드로 소개한 다음 중괄호 쌍으로 정의합니다. TemperatureLogger actor는 외부의 다른 코드가 액세스할 수 있는 속성을 가지고 있으며 actor 내부의 코드만 최대값을 업데이트할 수 있도록 max 속성을 제한합니다. 구조체 및 클래스와 동일한 초기화 구문을 사용하여 actor의 인스턴스를 생성합니다. actor의 속성이나 메서드에 액세스할 때 await 키워드를 사용하여 잠재적 일시 중단 지점을 표시합니다.

let logger = TemperatureLogger(label: "Outdoors", measurement: 25)
print(await logger.max)
// Prints "25"

이 예시에서 logger.max에 액세스하는 것이 일시 정지 지점이 될 수 있습니다. actor는 한번에 하나의 작업만 변경 가능한 상태에 액세스하도록 허용하므로 다른 작업의 코드가 이미 logger와 상호 작용하고 있는 경우 이 코드는 속성에 액세스하기를 기다리는 동안 일시 중지됩니다.

대조적으로 actor의 일부인 코드는 actor의 속성에 액세스할 때 대기를 작성하지 않습니다.

예시로 새로운 온도로 TemperatureLogger를 업데이트하는 방법은 다음과 같습니다.

extension TemperatureLogger {
    func update(with measurement: Int) {
        measurements.append(measurement)
        if measurement > max {
            max = measurement
        }
    }
}

이 update 메서드는 이미 actor에서 실행 중이므로 max와 같은 속성에 대한 엑세스를 await로 표시하지 않습니다. 또한 이 방법은 actor가 변경 가능한 상태와 상호 작용하기 위해 한 번에 하나의 작업만 허용하는 이유 중 하나를 보여줍니다. actor의 상태에 대한 일부 업데이트는 일시적으로 불변성을 깨트립니다. TemperatureLogger actor는 온도 목록과 최대 온도를 추적하고 새 측정 값을 기록할 때 최대 온도를 업데이트합니다. 업데이트 도중에 새 측정값을 추가한 후 최대값을 업데이트하기 전에 TemperatureLogger가 일시적으로 일관되지 않은 상태에 있습니다. 여러 작업이 동일한 인스턴스와 동시에 상호작용하는 것을 방지하면 다음과 같은 일련의 이벤트와 같은 문제를 방지할 수 있습니다.

1. update 메서드를 호출합니다. 이것은 measurements 배열을 처음으로 업데이트합니다.

2. max가 업데이트 되기전에 다른 곳의 코드가 max와 온도 배열을 읽습니다.

3. 코드는 max를 변경하여 업데이트를 완료합니다.

이 경우 다른 곳에서 실행되는 코드는 데이터가 일시적으로 유효하지 않은 동안 update 호출 중간에 actor에 대한 엑세스가 인터리브 되었기 때문에 잘못된 정보를 읽습니다. swift actor를 사용하면 한번에 해당 상태에서 하나의 작업만 허용하고 해당 코드는 정지 지점을 표시하는 await가 정지 지점을 표시하는 위치에서만 중단될 수 있기 때문에 이 문제를 방지할 수 있습니다. update에는 정지 지점이 포함되어 있지 않으므로 업데이트 도중에는 다른 코드가 데이터에 엑세스할 수 없습니다.

actor 외부의 코드가 구조체나 클래스의 속성에 접근하는 것처럼 해당 속성에 직접 접근하려고 하면 컴파일 타임 오류가 발생합니다.

print(logger.max)  // Error

await를 쓰지 않고 logger.max에 액세스하면 actor의 격리된 로컬 상태의 일부이기 때문에 실패합니다. 이 속성에 액세스하는 코드는 actor의 일부로 실행되어야 하며, 이는 비동기 작업이며 await키워드가 필요합니다. Swift는 actor에서 실행되는 코드만 해당 actor의 로컬 상태에 액세스할 수 있음을 보장합니다. 이러한 보장을 actore isolation 이라고 합니다.

Swift 동시성 모델의 다음 측면은 공유된 변경 가능 상태에 대해 더 쉽게 추론할 수 있도록 함께 작동합니다.

• 일시 중단 가능성이 있는 지점 사이에 있는 코드는 다른 동시 코드로 인해 중단될 가능성 없이 순차적으로 실행됩니다.
• actor의 로컬 상태와 상호 작용하는 코드는 해당 actore내부에서만 실행됩니다.
• actor는 한번에 하나의 코드만 실행합니다.

이러한 보장으로 인해 await를 포함하지 않고 actor 내부에 있는 코드는 프로그램의 다른 위치에서 일시적으로 유효하지 않은 상태를 관찰할 위험 없이 업데이트를 수행할 수 있습니다. 

아래 코드는 측정된 온도를 화씨에서 섭씨로 변환합니다.

extension TemperatureLogger {
    func convertFahrenheitToCelsius() {
        measurements = measurements.map { measurement in
            (measurement - 32) * 5 / 9
        }
    }
}

위의 코드는 측정 배열을 한 번에 하나씩 변환합니다. map 작업이 진행되는 동안 일부 온도는 화씨, 다른 온도는 섭씨로 표시됩니다. 그러나 코드에는 await가 포함되어 있지 않으므로 이 메서드에는 잠재적인 일시 중단 지점이 없습니다. 이 메서드가 수정하는 상태는 actor에 속하며 해당 코드가 액터에서 실행될 때를 제외하고는 코드를 읽거나 수정하지 못하도록 보호합니다. 즉, 단위 변환이 진행되는 동안 다른 코드에서 부분적으로 변환된 온도 목록을 읽을 수 있는 방법이 없습니다.

잠재적인 중단 지점을 생략하여 일시적인 유효하지 않은 상태를 보호하는 actor에 코드를 작성하는 것 외에도 해당 코드를 동기식 메서드로 이동할 수 있습니다. 위의 ConvertFahrenheitToCelsius()메서드는 동기 메서드이므로 잠재적인 정지 지점이 포함되지 않음이 보장됩니다. 이 기능은 데이터 모델을 일시적으로 불일치하게 만드는 코드를 캡슐화하고, 작업을 완료하여 데이터 일관성이 복원되기 전에는 다른 코드를 실행할 수 없다는 것을 코드를 읽는 사람이 더 쉽게 인식할 수 있도록 합니다. 앞으로 이 함수에 동시 코드를 추가하여 일시 중단 지점을 도입하려고 하면 버그가 발생하는 대신 컴파일 시간 오류가 발생하게 됩니다.

보낼 수 있는 유형 Sendable Types

Task와 Actor를 사용하면 프로그램을 안전하게 동시에 실행할 수 있는 부분으로 나눌 수 있습니다. Task나 Actor 인스턴스 내부에서 변수와 속성과 같은 변경 가능한 상태를 포함하는 프로그램 부분을 동시성 도메인(Concurrency Domain) 이라고합니다. 일부 데이터는 변경 가능한 상태를 포함하기 때문에 동시성 도메인 간에 공유할 수 없지만 중복 액세스로부터 보호하지는 않습니다.

한 동시성 도메인에서 다른 동시성 도메인으로 공유할 수 있는 유형을 Sendable type이라고 합니다.

예를 들어, actor 메서드를 호출할 때 인수로 전달하거나 Task의 결과로 반환할 수 있습니다. 이 장의 앞부분에 나온 예제에서는 sendability에 대해 설명하지 않았는데, 이러한 예제에서는 동시성 도메인 간에 전달되는 데이터에 대해 항상 안전하게 공유할 수 있는 간단한 값 유형을 사용하기 때문입니다. 반면, 일부 유형은 동시성 도메인 간에 전달하는 것이 안전하지 않습니다. 예를 들어, 변경 가능한 속성을 포함하고 해당 속성에 대한 액세스를 직렬화하지 않는 클래스는 다른 직업간에 해당 클래스의 인스턴스를 전달할 때 예측할 수 없고 잘못된 결과를 생성할 수 있습니다

Sendable protocol을 사용하여 보낼 수 있는 유형으로 표시합니다. 해당 프로토콜에는 코드 요구 사항이 없지만 Swift에서 적용하는 의미적 요구 사항이 있습니다.

일반적으로 유형을 보낼 수 있는 방법에는 세 가지가 있습니다.

• 유형은 값 유형이고, 변경 가능한 상태는 다른 전송 가능한 데이터로 구성됩니다. 예를 들어, 전송 가능한 저장된 속성이 있는 구조체나 전송 가능한 연관된 값이 있는 열거형이 있습니다.
• 이 유형에는 변경 가능한 상태가 없으며, 변경 불가능한 상태는 다른 전송 가능한 데이터(예: 읽기 전용 속성만 있는 구조체나 클래스)로 구성됩니다.
• 이 유형에는 변경 가능한 상태의 안정성을 보장하는 코드가 있는데, 이는 @MainActor 표시된 클래스나 특정 스레드나 큐에서 속성에 다ㅐ한 액세스를 직렬화하는 클래스와 같습니다.

일부 유형은 항상 보낼 수 있습니다.

예를 들어, 보낼 수 있는 속성만 있는 구조체와 보낼 수 있는 연관된 값만 있는 열거형이 있습니다.

struct TemperatureReading: Sendable {
    var measurement: Int
}


extension TemperatureLogger {
    func addReading(from reading: TemperatureReading) {
        measurements.append(reading.measurement)
    }
}


let logger = TemperatureLogger(label: "Tea kettle", measurement: 85)
let reading = TemperatureReading(measurement: 45)
await logger.addReading(from: reading)

TemperatureReading은 sendable 속성만 있는 구조이고, 구조가 public 또는 @usableFromInline으로 표시되지 않은 경우 암묵적으로 sendable입니다. 다음은 Sendable protocol 준수가 암묵적으로 포함된 구조 버전입니다.

struct TemperatureReading {
    var measurement: Int
}

Sendable protocol에 대한 암묵적 적합성을 재정의하여 유형을 보낼 수 없음으로 명시적으로 표시하려면 extension을 사용합니다.

struct FileDescriptor {
    let rawValue: CInt
}


@available(*, unavailable)
extension FileDescriptor: Sendable { }

위 코드는 POSIX 파일 디스크립터에 대한 래퍼의 일부를 보여줍니다. 파일 디스크립터에 대한 인터페이스는 정수를 사용하여 열린 파일을 식별하고 상호 작용하고 정수 값을 보낼 수 있지만, 파일 디스크립터는 동시성 도메인을 통해 보내는 것이 안전하지 않습니다.

위의 코드에서 FileDescriptor는 암묵적으로 보낼 수 있는 기준을 충족하는 구조입니다. 그러나 확장은 해당 적합성을 사용할 수 없게 만들어서 해당 유형이 보낼 수 없게 합니다.

트라이

트라이는 문자열이 트리형태로 저장된 자료구조이다.

특정 문자열을 탐색할때 특화된 알고리즘으로, 트리는 K진 트리이다. (K는 문자열의 첫번째 문자의 종류)

예로 문자열 "apple", "banana", "avocado" 세가지가 있다고 하면 아래와 같은 트리형태로 만들 수 있다.

트리의 최상단노드는 비워두고, 그아래로 k개의 접두사를 갖는 자식노드들을 만든다.

문자열 세개중 중복되지 않는 접두사는 a,b로 최상단노드는 두개의 자식노드를 갖는다.

우리가 문자열을 비교할때, 앞에서부터 차례로 읽어나가듯이, 주어진 문자열을 순차적으로 연결시킨다.

그리고 문자열을 모두 연결시켰다면 마지막노드에 해당노드가 마지막임을 저장해둔다.(Bool 변수를 이용)

주어진 문자열에서 특정 문자열을 찾을때, 최상단 노드부터 시작하여 문자열을 검사해나간다.

이때 문자열이 연결되어 있지 않거나, 문자를 모두 찾아갔지만 해당 노드가 끝이아니라면, 해당 문자열은 찾을 수 없다.

트라이 자료구조는 특정문자열을 수정하거나 찾는데 O(N)만큼 걸리지만(트리형태의 자료구조에서 문자수만큼 연결하면된다.)

각 노드의 자식노드는 문자열의 최대 경우의수(소문자 26개, 대문자 26개)를 저장하기위해 메모리를 할당해야하므로

메모리가 추가적으로 많이필요하다.

트라이를 코드로 구현하면 다음과 같다.

import Foundation

// 트라이 자료구조
class Trie {
    // 트라이의 자식노드 메모리 할당(여기서는 소문자만 취급한다.)
    // 소문자의 아스키코드로 접근하기위해서 소문자의 갯수만큼 할당
    var child: [Trie?] = Array(repeating: nil, count: 26)
    // 해당 노드가 문자열의 마지막인지?
    var end = false
    
    // 트라이에 문자열을 넣는다. 외부에서 문자열String을 받음
    // 받은 문자열을 한개의 문자들로 나누고 insertCharater함수에 넘겨준다.
    // index는 0: 최상단노드부터 추가해주기 위해서
    func insert(_ s: String) {
        let arr: [Character] = Array(s)
        insertCharacter(arr, 0)
    }
    // 문자 배열과 인덱스를 넘겨받고 실행
    func insertCharacter(_ arr: [Character],_ index: Int) {
        // 해당 문자열을 모두 입력했다면 현재 노드가 마지막임을 설정하고 종료
        if arr.count == index {
            self.end = true
            return
        }
        // 아스키코드로 변환 범위: 0...25 (자식노드배열에 넣기위해)
        let num = toNumber(arr[index])
        
        // 현재 문자열의 아스키코드로 자식노드를 생성해준다.
        // apple을 입력해놓고 avocado를 입력할때, a는 이전에 생성해두었지만, v는 생성해두지 않았기에 생성
        if child[num] == nil {
            child[num] = Trie()
        }
        //남은 문자도 트리에 연결하기 위해 재귀호출
        child[num]?.insertCharacter(arr, index+1)
    }
    // 해당 문자를 아스키코드로 변환하지만 0~25 범위에 존재하게끔 소문자의 첫번째 문자 a의 아스키코드를 뺌
    func toNumber(_ c: Character) -> Int{
        return Int(c.asciiValue! - Character("a").asciiValue!)
    }
    
    // 문자열String을 받으면 해당 문자가 존재하는지 bool값 리턴
    // 문자열String을 역시 문자배열로 변환하여 내부함수 findCharacter를 실행
    func find(_ s: String) -> Bool{
        let arr: [Character] = Array(s)
        return findCharacter(arr,0)
    }
    // 문자열이 존재하는지 파악하기위해 재귀호출
    func findCharacter(_ arr: [Character],_ index: Int) -> Bool {
        // 문자열이 모두 존재하고, 마지막 문자가 끝나는노드라면 true
        // 문자열이 모두 존재했지만, 마지막 문자가 끝나지않는 노드라면 false
        if arr.count == index {
            if self.end { return true }
            return false
        }
        // 해당 문자를 아스키코드로 변환
        let num = toNumber(arr[index])
        // 해당문자의 자식노드가 존재하지않다면 더 찾을 수 없으므로 false
        if child[num] == nil { return false }
        // 그다음 문자도 확인
        return child[num]!.findCharacter(arr, index+1)
    }
}

세그먼트 트리

세그먼트 트리는 트리형태의 자료구조로 해당 노드에는 구간합이 저장되어 있다.

일반적으로 배열에서 특정 구간의 합을 구해야 한다면 O(N)이 걸린다.

세그먼트 트리는 노드마다 구간의 합이 저장되어 있기때문에 해당 노드에 접근하여 반환하면 되므로 O(logN)이 걸리게 된다.

이처럼 세그먼트 트리는 여러개의 데이터가 연속적으로 있을 때, 특정 구간의 합을 구하는데 효율적인 자료구조이다.

세그먼트 트리만들어보기

배열 A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이 주어졌다. 편의상 인덱스는 1부터 시작한다.

이를 트리로 만들어보자.

위 그림은 배열 A를 트리로 만들어본 형태다.

왼쪽노드는 index*2, 오른쪽노드는 index*2+1이 되고, 트리의 특성상 합을 구하면 O(logN)이 걸리게 된다.

구간힙 트리로 만들어보자.

맨 위 최상단노드는 모든 원소의 합이 들어간다.

그다음 두 번째 세번째 노드를 구해주는데 두번째노드는 1번부터 5번까지의 구간합, 세 번째 노드는 6번부터 10번까지의 구간합이 들어간다.

그 다음 자식노드도 구해보자. 

두번째 노드는 1~5의 구간합이고, 세번째노드는 6~10의 구간합이다.

중간인덱스를 구해 두 번째 노드의 왼쪽자식노드는 1~3, 오른쪽자식노드는 4~5

세 번째 노드의 왼쪽자식노드는 6~8, 오른쪽자식노드는 9~10 이 된다.

이렇게 마지막 노드까지 구하면 구간합 트리는 아래와 같다.

이전의 배열의 크기는 10이었고 트리로 만들어도 크기는 달라지지 않았지만, 구간힙 트리로 만들면서 크기가 변경되었다.

이처럼 배열을 구간힙트리로 만들려면 배열의 크기보다 크면서 가장 인접한 제곱수 * 2만큼의 크기를 할당해야 한다.

예시의 배열크기는 10이어서 10보다 큰 인접한 제곱수 4^2 = 16이고, 16*2 = 32이다. 최소 32의 크기를 할당해야 하지만, 더 넉넉하게 주려면 배열의 크기보다 4배 크면 된다.(최소로만 크기를 할당해도 상관은 없다.)

※종합

1. 연속된 데이터의 특정범위를 빠르게 구하기 위해 세그먼트 트리를 작성

2. 세그먼트 트리의 크기는 적어도 주어진 데이터크기보다 크며 가장 인접한 제곱수의 2배만큼 할당(넉넉히 4배만큼 줘도 상관은 없다)

3. 세그먼트 트리의 각 노드는 특정 구간의 합이 저장되어 있어 선형탐색(O(N))보다 효율적(O(logN))

이를 코드로 구현해 보자.

1. 세그먼트 트리 만들기

// 연속된 데이터 예시
// 트리의 특성(왼쪽자식인덱스:index*2, 오른쪽자식인덱스:index*2+1)를 이용하기위해 배열 첫번째는 임의의데이터를 넣는다.
var arr = Array(0...10)
// 크기 할당
var segTree = Array(repeating: 0, count: arr.count*4)

// 세그먼트 트리 만들기 (재귀호출)
// 구간합을 구해서 더한값이 부모노드가 됨
// 재귀호출로 맨 아래의 노드(start=end)까지 도달 후 더해서 부모노드를 채워가는 형식으로 진행됨
// start: 배열arr의 첫번째인덱스, end: 배열arr의 마지막인덱스
// index: 세그먼트트리의 인덱스
func segmentTreeInit(_ start: Int, _ end: Int, _ index: Int) -> Int{
	// 구간의 start == end는 해당 위치의 원소를 의미
    // 배열 arr의 3부터3까지의 구간합은 결국 arr[3]이다.
    if start == end {
        segTree[index] = arr[start]
        return segTree[index]
    }
    // 구간을 둘로 나누어 트리 특성상 왼쪽노드의 위치는 index*2, 오른쪽노드는 index*2+1
    var mid = (start + end) / 2
    // 재귀호출
    // 해당 구간합은 그 위치의 왼쪽 자식노드와 오른쪽자식노드의 합이다.
    segTree[index] = segmentTreeInit(start, mid, index*2) + segmentTreeInit(mid+1, end, index*2+1)
    return segTree[index]
}

결과:

segmentTreeInit(1, arr.count-1, 1)
print(segTree)
print(segmentTreeInit(1, arr.count-1, 1))

// [0, 55, 15, 40, 6, 9, 21, 19, 3, 3, 4, 5, 13, 8, 9, 10, 1, 2, 0, 0, 0, 0, 0, 0, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
// 55

2. 특정 구간의 합 구하기

세그먼트 트리를 만드는 이유가 되기도 하는 특정구간의 합을 구해보자.

특정 구간의 합을 구하는 과정은 세그먼트트리의 최상단 노드부터 시작하며,

해당노드가 구간 안에 존재한다면, 모두 더해준다.

해당 구간을 찾아가는 방법은 재귀호출로 찾아갈 것이다.

예를 들어 4~6구간의 합을 구한다고 하자.

파랑노드를 찾아가는 조건은 재귀호출마다 해당 노드의 구간이 구하려는 범위 내에 존재하면 그 노드로 탐색하는 것이다.

- [4~6] 구간을 구할 때, 왼쪽은 [1~5] 오른쪽은 [6~10]이므로 범위 내에 존재한다. 진입

- [1~5]에서 왼쪽 [1~3]은 범위내에 존재하지 않는다 0

- [1~5]에서 오른쪽 [4~5]는 범위내에 존재한다. 해당노드를 더해줌 9

- [6~10]에서 오른쪽노드는 범위 내에 존재하지않고, 왼쪽노드는 존재한다. 왼쪽노드 진입

- [6~8]에서 왼쪽노드가 범위내에 존재 왼쪽노드진입

- [6~7]에서 왼쪽노드가 범위내에 존재 왼쪽노드 진입

- [6]은 범위내에 존재. 더해준다.

-나머지 범위들은 모두 범위밖에 구간합이므로 0을 더해준다.

코드로 구현하면 다음과 같다.

// 특정 구간합 구하기
// start: 배열arr의 시작인덱스, end: 배열arr의 마지막인덱스
// index: 세그먼트 트리의 인덱스(재귀호출을위해 1로 입력)
// left: 구하려는 범위의 시작인덱스, right: 구하려는범위의 마지막인덱스
func segmentTreeSum(_ start: Int,_ end: Int,_ index: Int,_ left: Int,_ right: Int) -> Int{
	// left...right 범위를 벗어났다면 0리턴
    if left > end || right < start { return 0 }
    // left...right 범위내에 있는 구간합이라면 출력
    if left <= start && right >= end { return segTree[index] }
    // 자식노드로 재귀호출
    // 범위내의 구간합을 찾는다.
    let mid = (start + end) / 2
    return segmentTreeSum(start, mid, index*2, left, right) + segmentTreeSum(mid+1, end, index*2+1, left, right)
}

결과:

print(segmentTreeSum(1, arr.count-1, 1, 4, 6))
// 15

3. 특정 원소의 값 수정하기

세그먼트 트리는 구간합이 저장되어 있으므로, 특정원소의 값을 수정한다면 그 원소의 구간합 노드들을 전부 수정해 주면 된다.

세그먼트 트리의 특정원소를 수정할 때에는 새로운 값으로 초기화하는 방법이 아닌 증가, 감소하는 방향으로 구한다.

만약 아예 새로운 값으로 초기화한다면 새로 변경된 배열을 토대로 세그먼트 트리를 다시 만들어주면 된다.

예를 들어 배열 세 번째의 값을 6으로 만든다면

위 그림과 같이 구간합노드 중 세번째 값이 해당범위에 존재하면 모두 바꿔준다.

재귀호출로 특정원소까지 갈 때마다 증가 혹은 감소되는 값을 더해주며 내려간다.

코드로 구현하면 다음과 같다.

// 특정원소의 값 수정(증가 혹은 감소)
// start: 배열arr의 시작인덱스, end: 배열arr의 마지막인덱스
// index: 세그먼트트리의 인덱스
// node: 변경하려는 원소의 위치
// newValue: 변경값(증가 혹은 감소)
func segmentUpdate(_ start: Int,_ end: Int,_ index: Int,_ node: Int,_ newValue: Int) {
    // 수정하려는 값의 위치가 범위를 벗어나면 종료
    if node > end || node < start { return }
    // 수정하려는 값의 위치가 범위내에 존재하면 해당 구간합도 수정해준다.
    // 이때 수정하려는값을 더해준다.
    segTree[index] += newValue
    // 해당위치에 도달했다면 종료
    // 예: 배열arr의 3번째 원소를 수정한다면 3이 포함된 구간합을 모두 수정 후, 구간합 3~3의 노드까지 도달하면 종료
    if start == end { return }
    let mid = (start + end) / 2
    // 세그먼트트리의 왼쪽자식노드와 오른쪽자식노드 모두 접근
    segmentUpdate(start, mid, index*2, node, newValue)
    segmentUpdate(mid+1, end, index*2+1, node, newValue)
}

결과:

// 3번째 위치한 원소의 값을 3 증가시킨다. (arr[3]을 6으로 변경)
segmentUpdate(1, arr.count-1, 1, 3, 3)
print(segTree)
//     1   2       4                9 -> 변경된 값
// [0, 58, 18, 40, 9, 9, 21, 19, 3, 6, 4, 5, 13, 8, 9, 10, 1, 2, 0, 0, 0, 0, 0, 0, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

이렇게 세그먼트리를 이용한다면 특정 구간의 합을 구하거나 수정할 때, 선형탐색 O(N) 보다 더 효율적이다 O(logN)

전체코드:

import Foundation

// 연속된 데이터 예시
// 트리의 특성(왼쪽자식인덱스:index*2, 오른쪽자식인덱스:index*2+1)를 이용하기위해 배열 첫번째는 임의의데이터를 넣는다.
var arr = Array(0...10)
// 크기 할당
var segTree = Array(repeating: 0, count: arr.count*4)

// 세그먼트 트리 만들기 (재귀호출)
// 구간합을 구해서 더한값이 부모노드가 됨
// 재귀호출로 맨 아래의 노드(start=end)까지 도달 후 더해서 부모노드를 채워가는 형식으로 진행됨
// start: 배열arr의 첫번째인덱스, end: 배열arr의 마지막인덱스
// index: 세그먼트트리의 인덱스
func segmentTreeInit(_ start: Int, _ end: Int, _ index: Int) -> Int{
    // 구간의 start == end는 해당 위치의 원소를 의미
    // 배열 arr의 3부터3까지의 구간합은 결국 arr[3]이다.
    if start == end {
        segTree[index] = arr[start]
        return segTree[index]
    }
    // 구간을 둘로 나누어 트리 특성상 왼쪽노드의 위치는 index*2, 오른쪽노드는 index*2+1
    var mid = (start + end) / 2
    // 재귀호출
    // 해당 구간합은 그 위치의 왼쪽 자식노드와 오른쪽자식노드의 합이다.
    segTree[index] = segmentTreeInit(start, mid, index*2) + segmentTreeInit(mid+1, end, index*2+1)
    return segTree[index]
}

// 특정 구간합 구하기
// start: 배열arr의 시작인덱스, end: 배열arr의 마지막인덱스
// index: 세그먼트 트리의 인덱스(재귀호출을위해 1로 입력)
// left: 구하려는 범위의 시작인덱스, right: 구하려는범위의 마지막인덱스
func segmentTreeSum(_ start: Int,_ end: Int,_ index: Int,_ left: Int,_ right: Int) -> Int{
    // left...right 범위를 벗어났다면 0리턴
    if left > end || right < start { return 0 }
    // left...right 범위내에 있는 구간합이라면 출력
    if left <= start && right >= end { return segTree[index] }
    // 자식노드로 재귀호출
    // 범위내의 구간합을 찾는다.
    let mid = (start + end) / 2
    return segmentTreeSum(start, mid, index*2, left, right) + segmentTreeSum(mid+1, end, index*2+1, left, right)
}

// 특정원소의 값 수정(증가 혹은 감소)
// start: 배열arr의 시작인덱스, end: 배열arr의 마지막인덱스
// index: 세그먼트트리의 인덱스
// node: 변경하려는 원소의 위치
// newValue: 변경값(증가 혹은 감소)
func segmentUpdate(_ start: Int,_ end: Int,_ index: Int,_ node: Int,_ newValue: Int) {
    // 수정하려는 값의 위치가 범위를 벗어나면 종료
    if node > end || node < start { return }
    // 수정하려는 값의 위치가 범위내에 존재하면 해당 구간합도 수정해준다.
    // 이때 수정하려는값을 더해준다.
    segTree[index] += newValue
    // 해당위치에 도달했다면 종료
    // 예: 배열arr의 3번째 원소를 수정한다면 3이 포함된 구간합을 모두 수정 후, 구간합 3~3의 노드까지 도달하면 종료
    if start == end { return }
    let mid = (start + end) / 2
    // 세그먼트트리의 왼쪽자식노드와 오른쪽자식노드 모두 접근
    segmentUpdate(start, mid, index*2, node, newValue)
    segmentUpdate(mid+1, end, index*2+1, node, newValue)
}

    
segmentTreeInit(1, arr.count-1, 1)
print(segmentTreeSum(1, arr.count-1, 1, 4, 6))
segmentUpdate(1, arr.count-1, 1, 3, 3)
print(segTree)

Reference:

https://m.blog.naver.com/ndb796/221282210534

분리집합

분리 집합은 서로 다른원소를 갖는 집합이다. 그래서 각각 분리집합의 공통원소는 없다.

전체집합 U라고 하고, 분리집합 A와 B가 있다면, 아래의 수식이 성립한다.

- U = A U B

- A ∩ B = Ø

(A와B는 U의 부분집합이다.)

Union-Find

분리집합끼리의 표현을 효율적으로 구현하고, 조작하기 위해 생긴 알고리즘이다.

서로다른 분리집합을 합치는 Union연산과 임의의 원소가 어디의 집합에 속하는지 알기위한 find연산이 주어져서 Union-Find라고 불린다.

이 알고리즘을 사용하기위해 3가지의 연산을 구현해야한다.

1. 초기화: 기본적으로 구현하고 조작하기위해 분리집합을 구현해야한다. 분리집합의 원소는 자기 자신을 루트노드로 갖는다.

2. Union(x,y): 두 원소 x와 y가 주어졌을때, 서로 포함하는 분리집합을 합친다.

3. Find(x): x원소의 루트노드를 찾는다. 혹은 집합을 반환한다.

분리집합은 기본적으로 트리형태로 구현한다. 일반적인 트리는 부모노드가 자식노드를 가리키지만 분리집합은 부모노드만 추적하면 된다.

배열을 사용하여 구현해보자.

배열을 이용해 분리집합으로 구현하면 처음엔 원소는 자기원소를 루트노드로 갖는다.(편의를 위해 0은 비우고만든다.)

parent[index] = x 의 표현은 index라는 원소의 루트노드는 x다.

(보통 배열을 사용하면 위와 반대로 index위치에 원소가 존재한다라고 생각했는데 여기서는 index가 원소고, 위치에 있는 원소가 부모노드원소가 되는것이다.)

초기화 할때는 자기 자신이 루트노드가 되므로 모형으로 보면 다음과 같다.

분리집합 [1,3,5]와 [2,4,6]을 만든다.

Union(1,3): 원소3을 원소1의 루트노드로 연결한다.

Union(1,5): 원소 5를 원소1의 루트노드로 연결한다.

이렇게 하면 원소1,3,5를 갖는 분리집합이 완성된다.

Find(1): 원소1의 루트노드를 출력한다. -> 원소1은 자기 자신을 루트노드를 갖고있으므로 1을 반환

Find(5): 원소5의 루트노드를 출력한다 -> 원소5는 원소1을 루트노드로 갖고있다. 1을반환

예시의 deph는 2단계라 바로 루트노드를 출력하지만, 더 깊다면 재귀호출을 통해 해당 집합의 루트노드를 반환한다.

두개의 분리집합을 합치는연산 Union을 사용하면 다음 그림과 같다.

Union(1,2): 원소 1이 속한 집합과 원소2가 속한집합을 합친다.

합치는과정은 해당 루트노드가 합치려는 집합의 루트노드로 연결만 해주면된다.

합쳐졌다면 원소2,4,6 또한 루트노드 1을 가리키게 된다.

Union-Find의 시간복잡도는 Union연산은 연결만 해주므로 O(1)이 들지만, Find연산은 트리의 depth 만큼 재귀호출을 하므로

최소 O(1)에서 최대 O(depth)가 걸리게 된다.

이를 코드로 구현해보자.

import Foundation

// Union-Find
// 분리집합을 저장할 배열 parent
// parent[i] = a : i의 부모노드는 a다.
var parent = Array(repeating: 0, count: 7)

// 처음 초기화할땐 자기 자신을 루트노드로 갖는다.
for i in 1...6 {
    parent[i] = i
}

// 원소 x가 포함된 집합과 y가 포함된 집합을 합친다.
// 이때 합쳐진 집합의 루트노드는 x의 루트노드가 된다.
func union(_ x: Int, _ y: Int) {
    var rootX = find(x)
    var rootY = find(y)
    parent[rootY] = rootX
}
// 원소 x의 루트노드를 반환한다. (재귀호출)
// 재귀호출은 트리의 depth만큼 실행된다.
func find(_ x: Int) -> Int {
    if parent[x] == x { return x}
    parent[x] = find(parent[x])
    return parent[x]
}

Reference:

https://gunjoon.tistory.com/140

https://victorqi.gitbooks.io/swift-algorithm/content/union-find.html