13 · Collection과 메모리

Sequence                    한 번 순회할 수 있다 (다시 순회 가능하다는 보장 없음)
  └ Collection              여러 번 순회 가능 · Index로 접근 · count가 O(1)
      └ BidirectionalCollection    뒤로도 갈 수 있다 (index(before:))
          └ RandomAccessCollection  임의 위치로 O(1) 점프 · 거리 계산 O(1)

// 구체 타입이 어디에 속하는가
Array          → RandomAccessCollection   (i번째로 바로 점프 가능)
String         → BidirectionalCollection  (⚠️ RandomAccess 아님!)
Set/Dictionary → Collection               (순서가 없으니 앞뒤 개념도 없음)

// 왜 나눠 놨나 — 함수가 "필요한 최소 능력"만 요구할 수 있게
func middle<C: RandomAccessCollection>(_ c: C) -> C.Element {
    c[c.index(c.startIndex, offsetBy: c.count / 2)]   // O(1) 점프가 필요하다
}
// String을 넘기면 컴파일 에러 → "이 알고리즘은 String에 쓰면 O(n)이 된다"를
// 런타임 성능 문제가 아니라 컴파일 에러로 미리 막는다

let s = "가나다"
// s[2]                      // ❌ 컴파일 에러
let i = s.index(s.startIndex, offsetBy: 2)
print(s[i])                  // "다"

// 왜? Swift의 String은 "사람이 인식하는 문자(Character)" 단위인데,
// 그 하나가 UTF-8에서 1~4바이트로 길이가 제각각이다.
"a".utf8.count      // 1
"가".utf8.count     // 3
"👨‍👩‍👧‍👦".utf8.count   // 25  ← 이모지 하나가 25바이트, Character로는 1개

// 저장은 연속 바이트인데 "n번째 문자"는 앞에서부터 세어야만 안다 → O(n)
// 만약 s[2] 문법을 허용했다면?
//   · 보기엔 O(1)처럼 생겼는데 실제로는 O(n)
//   · for i in 0..<s.count { s[i] } 가 조용히 O(n²)가 된다
//
// ★ Swift의 선택: "O(1)처럼 보이는 O(n)"을 허용하느니 문법을 불편하게 만든다.
//   Index 타입을 따로 둬서 "이건 공짜 점프가 아니다"를 눈에 보이게 했다.

var a = [1, 2, 3]
var b = a          // O(1) — 버퍼를 공유, 참조 카운트만 +1
b.append(4)        // 여기서 실제 복사 (유일 소유자가 아니므로)

// 그래서 이런 코드가 안전하다 — 방어적 복사가 필요 없다
func process(_ items: [Item]) {
    // items를 아무리 읽어도 호출자의 배열이 바뀔 일이 없다
}

// ⚠️ 하지만 CoW는 "공짜"가 아니라 "미룬" 것이다
var big = Array(0..<1_000_000)
var copy = big                 // 여기까지 O(1)
copy[0] = 99                   // 💥 여기서 100만 개 전체 복사 (O(n))
// 루프 안에서 이런 패턴이 나오면 O(n²)가 된다

MemoryLayout<[Int]>.size            // 8   ← 원소가 100만 개여도 8
MemoryLayout<[String]>.size         // 8
MemoryLayout<Set<Int>>.size         // 8
MemoryLayout<[Int: Int]>.size       // 8
MemoryLayout<String>.size           // 16  ← 짧은 문자열을 인라인에 담으려고 조금 크다

// ★ 그래서 Array를 함수에 넘기는 건 "8바이트 복사"다.
//   "큰 배열을 값으로 넘기면 느리다"는 오해가 여기서 갈린다 —
//   느려지는 건 넘길 때가 아니라 CoW가 실제 복사를 트리거할 때다.

var a: [Int] = []
for i in 1...40 { a.append(i) }

a.count      // 40
a.capacity   // 76   ← 36칸(47%)이 비어 있다

// 용량이 커진 순간들을 기록해 보면
// capacity 변화: [2, 4, 8, 16, 36, 76, 156]
//                            ↑ 여기서부터 정확히 2배가 아니다. 왜?

// reserveCapacity로 미리 잡으면
var b: [Int] = []
b.reserveCapacity(40)
for i in 1...40 { b.append(i) }
b.capacity   // 44   ← 재할당이 일어나지 않는다

// Swift의 Dictionary/Set = 오픈 어드레싱(open addressing) + 선형 탐사(linear probing)
//   버킷 배열이 원소를 "직접" 담고, 자리가 차 있으면 다음 칸을 본다.
//   Java HashMap 처럼 버킷마다 연결 리스트를 매다는 체이닝이 아니다.

버킷:  [ _ ][ A ][ B ][ _ ][ C ][ _ ][ _ ][ _ ]
              ↑
        hash(B) = 1 인데 이미 A가 있음 → 다음 칸(2)에 저장 (선형 탐사)

// 오픈 어드레싱의 장점 — 여기가 CS와 만나는 지점
//   원소가 버킷 배열 안에 연속으로 놓여 있다 → 탐사가 캐시 라인을 타고 간다
//   체이닝은 포인터를 따라 힙 여기저기로 점프한다 → 캐시 미스 (04번의 포인터 추격)

// 대가
//   삭제가 까다롭다(빈 칸을 그냥 만들면 탐사가 끊긴다 → tombstone 필요)
//   load factor가 높아지면 탐사 길이가 급격히 늘어난다

var s = Set<Int>()
for i in 1...80 { s.insert(i) }   // 용량이 바뀐 순간들을 기록

Set  capacity: [1, 3, 6, 12, 24, 48, 96]
Dict capacity: [1, 3, 6, 12, 24, 48, 96]   // 같은 구현을 공유한다

// 대조해 보면 정확히 맞는다
//   버킷   2 × 3/4 =  1
//   버킷   4 × 3/4 =  3
//   버킷   8 × 3/4 =  6
//   버킷  16 × 3/4 = 12
//   버킷  32 × 3/4 = 24
//   버킷  64 × 3/4 = 48
//   버킷 128 × 3/4 = 96

// ★ 두 가지를 알 수 있다
//   ① 버킷 수는 항상 2의 거듭제곱 → 나머지 연산을 비트 마스킹(h & (n-1))으로 대체
//   ② load factor 상한이 3/4 → 4칸 중 1칸은 의도적으로 비워 둔다
//      (꽉 채우면 선형 탐사가 길어져 O(1)이 무너지므로)
//
// 즉 Dictionary는 "원소 수"가 아니라 "버킷 배열 전체"만큼 메모리를 쓴다.
// 원소 96개짜리 Dictionary = 버킷 128칸 + 각 버킷의 키/값/점유 비트맵

// ① 튜플 — 원소 수가 타입에 박힌다
MemoryLayout<(Int, Int, Int, Int)>.size    // 32  ← 힙 없음, 통째로 인라인
MemoryLayout<[Int]>.size                   //  8  ← 포인터 (데이터는 힙)

// ② InlineArray (Swift 6.2, SE-0453) — 고정 길이 배열이 언어에 들어왔다
let a: InlineArray<4, Int> = [1, 2, 3, 4]
MemoryLayout<InlineArray<4, Int>>.size     // 32  ← 힙 할당 0
// 길이가 타입 파라미터라서 컴파일 타임에 크기가 확정된다

// ③ withUnsafeTemporaryAllocation — 스택에 임시 버퍼
withUnsafeTemporaryAllocation(of: Int.self, capacity: 64) { buf in
    for i in 0..<64 { buf[i] = i }
    // 이 스코프 안에서만 유효 — 벗어나면 사라진다
}   // 힙 할당·해제 없음

let s: Set = [1,2,3,4,5,6,7,8,9,10]
print(Array(s))

// 1회차: [4, 1, 2, 5, 6, 8, 7, 3, 9, 10]
// 2회차: [10, 4, 8, 7, 9, 6, 1, 3, 2, 5]   ← 같은 코드, 같은 내용, 다른 순서

// 왜? Swift 4.2부터 해시 시드가 프로세스마다 무작위로 생성된다.
// 버그가 아니라 해시 플러딩 공격(HashDoS) 방어 설계다.
//
// ★ 그래서 절대 하면 안 되는 것
//   · Set/Dictionary 순회 순서에 의존하는 로직
//   · hashValue를 파일·DB·네트워크에 저장하고 다음 실행에서 비교
//   · 순서를 가정한 스냅샷 테스트
//
// 테스트에서 순서를 고정해야 하면 SWIFT_DETERMINISTIC_HASHING=1 (테스트 전용)

final class Box { deinit { Counter.freed += 1 } }

func run(_ mode: String) {
    Counter.freed = 0
    var keep: Any? = nil
    do {
        let big = (0..<1000).map { _ in Box() }   // 객체 1000개
        switch mode {
        case "slice": keep = big[0..<1]           // 1개짜리 슬라이스 보관
        case "copy":  keep = Array(big[0..<1])    // 새 배열로 복사해서 보관
        default:      break                        // 아무것도 안 보관
        }
    }   // big 스코프 종료
    print("[\(mode)] 해제 \(Counter.freed)/1000")
}

// 실행 결과 (Swift 6.2.1 실측)
//   [none ] 해제 1000/1000   → 살아남음    0개   ✅ 정상
//   [copy ] 해제  999/1000   → 살아남음    1개   ✅ 의도대로
//   [slice] 해제    0/1000   → 살아남음 1000개   💥 전부 살아 있다

let big = Array(0..<10)
let slice = big[5...]

slice.startIndex   // 5   ← 0이 아니다!
slice.endIndex     // 10
slice.count        // 5
slice.first        // 5
slice[5]           // 5   ✅ 유효
// slice[0]        // 💥 Index out of bounds 크래시

// ✅ 안전한 접근
slice.first
slice[slice.startIndex]
for (offset, v) in slice.enumerated() { }   // offset은 0부터

n개를 append 하는 동안 일어나는 복사 횟수의 총합
  = 마지막 재할당에서 n/2개 + 그 전 n/4개 + n/8 + …
  = n/2 + n/4 + n/8 + … < n              ← 등비급수(공비 1/2)의 합은 n 미만

총비용 O(n)을 n번으로 나누면 → 평균 O(1)   ★ 이게 amortized의 정의

// ⚠️ "일정량씩" 늘리면 왜 안 되는가 — 대조해 보면 명확하다
//   매번 +1칸씩 늘린다면:
//     복사 총합 = 1 + 2 + 3 + … + n = n(n+1)/2 = O(n²)
//     평균 = O(n)  → 상수가 아니다!
//
// ★ 그래서 "지수적 성장"은 구현 편의가 아니라 amortized O(1)의 필요조건이다.

① 해시 함수가 값을 고르게 흩뿌린다
   → 몰리면 탐사가 길어져 최악 O(n)
② load factor(채움 비율)를 낮게 유지한다
   → 꽉 찰수록 선형 탐사 길이가 급격히 늘어난다 → 리해싱으로 관리
③ 해시 계산 자체가 싸다
   → 긴 String 키는 해시 한 번에 전체를 훑는다. "O(1)"의 상수가 크다

// ★ Hashable 계약 — 어기면 조용히 망가진다
//   a == b 이면 반드시 a.hashValue == b.hashValue
//   (역은 성립 안 해도 된다 — 다른 값이 같은 해시일 수 있다 = 충돌)

struct User: Hashable {
    let id: UUID
    var nickname: String        // 자주 바뀐다

    // ❌ == 는 id만 보는데 hash는 nickname까지 넣으면 계약 위반
    static func == (l: User, r: User) -> Bool { l.id == r.id }
    func hash(into hasher: inout Hasher) {
        hasher.combine(id)
        // hasher.combine(nickname)   // 💥 넣으면 안 된다
    }
}
// 어기면? Set에 넣은 뒤 nickname을 바꾸는 순간 그 원소를 "찾을 수 없게" 된다.
// 크래시가 아니라 조용한 오작동이라 더 나쁘다.

  n         Array.contains   Set.contains    승자
  4              1.0 ns          3.8 ns      Array   ← O(n)이 이긴다
  8              2.7 ns          9.0 ns      Array
  16             9.1 ns          7.9 ns      Set     ← 교차점
  32            12.6 ns          5.5 ns      Set
  128           41.7 ns          4.8 ns      Set
  1,000        266.7 ns          4.2 ns      Set
  100,000   24,359.6 ns          4.5 ns      Set     ← 5,400배

// 두 가지가 동시에 보인다
//   ① Set은 n이 10만 배 늘어도 4~5ns로 평평하다 → 진짜 O(1)
//   ② 그런데 n ≤ 8 에서는 Array가 이긴다

① Array      : 헤더 32B + capacity × 원소크기  (실측 40개 → 76칸, 47% 여유)
               removeAll()은 기본적으로 capacity 유지
② Set/Dict   : 버킷 수(2의 거듭제곱) × 3/4 가 capacity  (실측 [1,3,6,12,24,48,96])
               4칸 중 1칸은 의도적으로 비워 둔다 — 꽉 채우면 탐사가 길어지므로
③ 슬라이스    : 원본 버퍼 전체 (실측 1개 슬라이스 → 1000개 전부 생존)
④ 원소가 클래스: 배열은 "포인터 배열" → 실제 데이터는 힙 여기저기
               순회할 때마다 포인터 추격 + 캐시 미스 (04번)

// 그래서 대용량 컬렉션에서 메모리를 아끼려면
//   · reserveCapacity로 재할당 자체를 줄인다 (원소 복사가 비쌀 때 특히)
//   · 오래 보관할 슬라이스는 Array(...)로 복사해 원본을 끊는다
//   · 값 타입 원소를 쓰면 연속 배치 + ARC 없음
//   · 다 쓴 캐시 배열은 removeAll(keepingCapacity: false)