06 · 자료구조와 알고리즘

var a = [Int]()
a.reserveCapacity(10_000)          // 재할당 제거 → append가 진짜 amortized O(1)
for i in 0..<10_000 { a.append(i) }

// ❌ 배열을 큐처럼 쓰면 removeFirst가 매번 O(n) → 전체 O(n^2)
while !a.isEmpty { _ = a.removeFirst() }

import Foundation

// Array.removeFirst()는 남은 원소를 전부 앞으로 당긴다 → 매번 O(n).
// 큐로 쓰면 전체가 O(n²)가 된다.

// ❌ 1만 개 작업 큐 → 약 5천만 번의 원소 이동
func drainBad(_ jobs: inout [Job]) {
    while !jobs.isEmpty {
        let job = jobs.removeFirst()      // O(n)
        run(job)
    }
}

// ✅ ① head 인덱스를 전진시킨다 — 의존성 없이 O(1)
func drain(_ jobs: [Job]) {
    var head = 0
    while head < jobs.count {
        run(jobs[head])
        head += 1
    }
}

// ✅ ② 넣고 빼기가 섞여 있으면 Deque (swift-collections)
import Collections

final class JobQueue {
    private var storage = Deque<Job>()

    func enqueue(_ job: Job) { storage.append(job) }          // O(1)
    func dequeue() -> Job? { storage.popFirst() }             // O(1)
    var count: Int { storage.count }
}

// ✅ ③ 의존성을 추가하기 싫으면 직접 만든 링 버퍼도 방법이다
struct RingQueue<T> {
    private var storage: [T?] = Array(repeating: nil, count: 16)
    private var head = 0, tail = 0, count = 0

    mutating func enqueue(_ v: T) {
        if count == storage.count { grow() }
        storage[tail] = v
        tail = (tail + 1) % storage.count
        count += 1
    }

    mutating func dequeue() -> T? {
        guard count > 0 else { return nil }
        defer { storage[head] = nil; head = (head + 1) % storage.count; count -= 1 }
        return storage[head]
    }

    private mutating func grow() {
        var next = [T?](repeating: nil, count: storage.count * 2)
        for i in 0..<count { next[i] = storage[(head + i) % storage.count] }
        storage = next; head = 0; tail = count
    }
}

struct Job {}
func run(_ j: Job) {}

import Foundation

struct Item: Identifiable { let id: String }

// ❌ Array.contains는 O(n) — 루프 안에서 부르면 전체가 O(n·m)
func filterBad(_ items: [Item], excluding blocked: [String]) -> [Item] {
    items.filter { !blocked.contains($0.id) }     // items 1만 × blocked 1천 = 1천만 비교
}

// ✅ Set으로 바꾸면 평균 O(1) — 전체가 O(n + m)
func filter(_ items: [Item], excluding blocked: [String]) -> [Item] {
    let blockedSet = Set(blocked)                 // 한 번만 O(m)
    return items.filter { !blockedSet.contains($0.id) }
}

// ✅ 중복 방문 방지도 같은 패턴 — insert가 판정과 삽입을 한 번에 한다
func visitOnce(_ nodes: [Node]) {
    var visited = Set<Node.ID>()
    for n in nodes where visited.insert(n.id).inserted {
        process(n)                                // 처음 본 것만
    }
}

// ✅ 교집합·차집합도 Set 연산이 훨씬 빠르고 의도가 드러난다
func diff(old: [String], new: [String]) -> (added: Set<String>, removed: Set<String>) {
    let o = Set(old), n = Set(new)
    return (n.subtracting(o), o.subtracting(n))
}

// ⚠️ 변환 비용을 잊지 말 것 — 한 번만 검사한다면 Array.contains가 더 싸다
func onceOnly(_ items: [String], _ target: String) -> Bool {
    items.contains(target)        // 1회 조회면 Set 만드는 비용이 더 크다
}

struct Node: Identifiable { let id: String }
func process(_ n: Node) {}

import Foundation

// 컬렉션은 용량이 찰 때마다 더 큰 버퍼를 잡고 전체를 옮긴다.
// 최종 크기를 알면 그 재할당·재해시를 전부 없앨 수 있다.

// ✅ Array
func buildRows(_ source: [Raw]) -> [Row] {
    var rows: [Row] = []
    rows.reserveCapacity(source.count)
    for r in source { rows.append(Row(r)) }
    return rows
}

// ✅ Dictionary — 재해시가 특히 비싸다
func buildIndex(_ rows: [Row]) -> [String: Row] {
    var index = [String: Row](minimumCapacity: rows.count)
    for r in rows { index[r.id] = r }
    return index
}

// ✅ Set
func buildSeen(_ ids: [String]) -> Set<String> {
    var seen = Set<String>(minimumCapacity: ids.count)
    for id in ids { seen.insert(id) }
    return seen
}

// ✅ String도 마찬가지
func joinAll(_ parts: [String]) -> String {
    var out = ""
    out.reserveCapacity(parts.reduce(0) { $0 + $1.utf8.count } + parts.count)
    for p in parts { out += p; out += "\n" }
    return out
}

// 효과를 직접 재 본다
func measureReserve() {
    let n = 200_000
    let clock = ContinuousClock()

    let without = clock.measure {
        var a: [Int] = []
        for i in 0..<n { a.append(i) }
    }
    let with = clock.measure {
        var a: [Int] = []
        a.reserveCapacity(n)
        for i in 0..<n { a.append(i) }
    }
    print("예약 없음 \(without) vs 예약 \(with)")
}

struct Raw {}
struct Row { let id: String; init(_ r: Raw) { id = "" } }

import Foundation

// ❌ ① Set·Dictionary의 순회 순서에 로직을 의존
func brokenOrder(_ tags: Set<String>) -> String {
    tags.joined(separator: ", ")
    // Swift는 실행마다 해시 시드를 무작위화한다 —
    // 같은 입력이어도 앱을 다시 켜면 순서가 달라진다.
    // 화면에 보이는 순서가 매번 바뀌거나, 스냅샷 테스트가 깨진다.
}

// ✅ 순서가 의미 있으면 명시적으로 정렬한다
func stableOrder(_ tags: Set<String>) -> String {
    tags.sorted().joined(separator: ", ")
}

// ✅ 삽입 순서를 유지해야 하면 OrderedSet (swift-collections)
import Collections
func insertionOrdered(_ tags: [String]) -> OrderedSet<String> {
    OrderedSet(tags)
}

// ❌ ② 큰 배열에서 removeFirst()를 반복 — O(n²)
func processBad(_ queue: inout [Job]) {
    while !queue.isEmpty {
        run(queue.removeFirst())
    }
}

// ✅ 인덱스를 전진시키거나 Deque를 쓴다
func process(_ queue: [Job]) {
    for job in queue { run(job) }     // 애초에 순회면 이걸로 충분하다
}

// ❌ ③ 비슷한 함정: removeFirst(k) · remove(at:0) · insert(at:0)
func alsoBad(_ a: inout [Int]) {
    a.insert(0, at: 0)                // O(n) — 앞쪽 삽입도 전부 밀어낸다
}
// ✅ 앞뒤가 모두 필요하면 Deque, 뒤에만 쓰면 append/popLast (둘 다 O(1))

struct Job {}
func run(_ j: Job) {}

import Foundation

// 같은 코드라도 n이 20이냐 20만이냐에 따라 정답이 정반대다.
// 최적화를 시작하기 전에 '내 n'을 숫자로 적어 본다.

enum Workload {
    case tableRows          // n ≈ 20~100      (화면에 보이는 행)
    case searchResults      // n ≈ 100~1,000   (한 페이지)
    case infiniteFeed       // n ≈ 10,000+     (누적 스크롤)
    case fullSync           // n ≈ 1,000,000   (전체 동기화)
}

// ✅ n에 따라 다른 구현을 고른다
func lookup(_ id: String, in items: [Item], index: [String: Item]?) -> Item? {
    if items.count < 64 {
        // 작은 n: 연속 메모리 선형 스캔이 캐시 친화적이라 해시보다 빠를 수 있다
        return items.first { $0.id == id }
    }
    // 큰 n: 해시 인덱스
    return index?[id]
}

// ✅ 인덱스를 만들지 말지도 n으로 결정한다
struct Repository {
    private var items: [Item] = []
    private var index: [String: Item]?

    mutating func reload(_ new: [Item]) {
        items = new
        // 인덱스 구축 비용(O(n))이 조회 이득보다 큰 구간이 있다
        index = new.count >= 64
            ? Dictionary(uniqueKeysWithValues: new.map { ($0.id, $0) })
            : nil
    }
}

// ✅ 최악을 가정해 상한을 문서화해 둔다
//    "이 목록은 서버가 페이지당 100개, 최대 50페이지 → n ≤ 5,000"
//    상한이 정해져 있으면 그 범위에서만 최적화하면 된다

struct Item: Identifiable { let id: String }

import Foundation

// Big-O는 n이 클 때의 성장률이다. 작은 n에서는 상수(할당·해시·간접 참조)가 지배한다.

struct Row { let id: Int; let name: String }

// 후보 ①: 선형 스캔 — 상수가 작고 캐시 친화적
func linearFind(_ rows: [Row], id: Int) -> Row? {
    rows.first { $0.id == id }
}

// 후보 ②: 해시 조회 — 점근은 좋지만 딕셔너리 구축·해싱 상수가 붙는다
func hashFind(_ index: [Int: Row], id: Int) -> Row? {
    index[id]
}

// ✅ 추측하지 말고 실제 n 범위에서 재 본다
func benchmark(_ rows: [Row]) {
    let index = Dictionary(uniqueKeysWithValues: rows.map { ($0.id, $0) })
    let clock = ContinuousClock()
    let target = rows.count / 2

    let linear = clock.measure {
        for _ in 0..<10_000 { _ = linearFind(rows, id: target) }
    }
    let hash = clock.measure {
        for _ in 0..<10_000 { _ = hashFind(index, id: target) }
    }
    print("n=\(rows.count) → 선형 \(linear) · 해시 \(hash)")
}

// 실제로 재 보면 대략 이런 그림이 나온다:
//   n=10   선형 승  (해싱 상수 > 10번 비교)
//   n=100  비슷
//   n=1000 해시 압승
//
// ⚠️ 반드시 Release(-O)로 잰다. Debug에서는 ARC·제네릭 오버헤드가
//    양쪽을 다르게 왜곡해 결론이 뒤집힐 수 있다.

import Foundation

// 재귀는 호출마다 스택 프레임을 쌓는다. 메인 스레드는 1MB뿐이고,
// 넘치면 catch할 수 없는 EXC_BAD_ACCESS다.

final class TreeNode {
    var value: Int = 0
    var children: [TreeNode] = []
}

// ❌ 깊이가 입력에 달려 있다
func sumRecursive(_ node: TreeNode) -> Int {
    node.value + node.children.reduce(0) { $0 + sumRecursive($1) }
}

// ✅ 명시적 스택 — 깊이가 힙에서 자란다
func sum(_ root: TreeNode) -> Int {
    var total = 0
    var stack = [root]
    while let node = stack.popLast() {
        total += node.value
        stack.append(contentsOf: node.children)
    }
    return total
}

// ✅ 꼬리 재귀처럼 보이는 것도 Swift는 최적화를 보장하지 않는다 — 반복이 안전하다
func factorialLoop(_ n: Int) -> Int {
    var result = 1
    if n > 1 { for i in 2...n { result *= i } }   // max(2,n)을 쓰면 0!·1!이 2가 된다
    return result
}

// ✅ 깊이를 남겨야 하는 순회는 (노드, 깊이) 쌍을 스택에 넣는다
func maxDepth(_ root: TreeNode) -> Int {
    var best = 0
    var stack = [(node: root, depth: 1)]
    while let (node, depth) = stack.popLast() {
        best = max(best, depth)
        for c in node.children { stack.append((c, depth + 1)) }
    }
    return best
}

// ⚠️ 신뢰할 수 없는 입력(서버 JSON·사용자 파일)의 깊이는 파싱 단계에서 제한한다
enum ParseError: Error { case tooDeep }
func parse(depth: Int) throws {
    guard depth < 128 else { throw ParseError.tooDeep }
}

import Foundation

// 같은 O(n)이어도 상수가 수십 배 차이 날 수 있다.

// 세 구현 모두 O(n)이지만 실제 시간은 전혀 다르다
func sumA(_ values: [Int]) -> Int {
    values.reduce(0, +)                       // 가장 빠름 — 연속 메모리 순회
}

func sumB(_ values: [Int]) -> Int {
    var total = 0
    for v in values { total += v }            // 사실상 동일
    return total
}

func sumC(_ values: [Int]) -> Int {
    values.map { $0 }.reduce(0, +)            // 중간 배열을 하나 더 만든다 — 훨씬 느림
}

// ❌ 더 극적인 예 — 둘 다 "문자열을 만든다"지만
func joinBad(_ parts: [String]) -> String {
    var s = ""
    for p in parts { s += p }                 // 분할상환은 O(n)이지만 재할당·용량 확인이 반복돼 상수가 크다
    return s
}
func joinGood(_ parts: [String]) -> String {
    parts.joined()                            // 한 번에 크기를 계산해 할당
}

// ✅ 판단은 측정으로
func compare(_ parts: [String]) {
    let clock = ContinuousClock()
    print("직접 이어붙이기 \(clock.measure { _ = joinBad(parts) })")
    print("joined        \(clock.measure { _ = joinGood(parts) })")
}

// 숨은 상수의 대표적 출처
//   · 중간 컬렉션 생성 (map → reduce 체인)
//   · COW 복사 (공유 상태에서 mutating)
//   · ARC retain/release (참조 타입 요소)
//   · 캐시 미스 (포인터 추적 구조)
//   · 경계 검사 (withUnsafeBufferPointer로 제거 가능)

import Foundation
import Collections

// 배열로 스택·큐를 흉내 내면 의도가 코드에 안 보이고,
// 나중에 누가 removeFirst()를 넣어도 아무도 못 알아챈다.

// ❌ 의도가 이름에만 있다
var undoArray: [Command] = []
func undoBad() { _ = undoArray.popLast() }

// ✅ 타입으로 못 박는다 — 잘못된 연산이 아예 없다
struct Stack<Element> {
    private var storage: [Element] = []

    var isEmpty: Bool { storage.isEmpty }
    var top: Element? { storage.last }

    mutating func push(_ e: Element) { storage.append(e) }   // O(1)
    mutating func pop() -> Element? { storage.popLast() }    // O(1)
}

// ✅ 되돌리기 — 가장 최근 것부터
final class UndoManager2 {
    private var undoStack = Stack<Command>()
    private var redoStack = Stack<Command>()

    func perform(_ c: Command) {
        c.execute()
        undoStack.push(c)
        redoStack = Stack()          // 새 작업을 하면 redo는 무효
    }

    func undo() {
        guard let c = undoStack.pop() else { return }
        c.revert()
        redoStack.push(c)
    }
}

// ✅ 큐 — 들어온 순서대로
struct Queue<Element> {
    private var storage = Deque<Element>()
    mutating func enqueue(_ e: Element) { storage.append(e) }
    mutating func dequeue() -> Element? { storage.popFirst() }
    var isEmpty: Bool { storage.isEmpty }
}

protocol Command { func execute(); func revert() }

import UIKit
import Collections

// 깊이 우선(DFS)이면 스택, 너비 우선(BFS)이면 큐.
// 같은 순회 코드에서 자료구조만 바꾸면 탐색 순서가 바뀐다.

// ✅ DFS — 한 갈래를 끝까지 파고든다 (뷰 계층에서 특정 타입 찾기)
func findFirst<T: UIView>(_ type: T.Type, in root: UIView) -> T? {
    var stack = [root]
    while let view = stack.popLast() {
        if let match = view as? T { return match }
        stack.append(contentsOf: view.subviews)
    }
    return nil
}

// ✅ BFS — 가까운 것부터 본다 ("root에서 가장 얕은 곳에 있는 스크롤뷰 자손" 같은 문제. 반대로 '가장 가까운 조상'은 탐색이 아니라 superview 체인을 거슬러 올라가면 된다)
func findNearest<T: UIView>(_ type: T.Type, in root: UIView) -> T? {
    var queue = Deque([root])
    while let view = queue.popFirst() {
        if let match = view as? T { return match }
        queue.append(contentsOf: view.subviews)
    }
    return nil
}

// ✅ 재귀 없이 스택을 쓰면 깊이 한계도 함께 해결된다
func allLabels(in root: UIView) -> [UILabel] {
    var found: [UILabel] = []
    var stack = [root]
    while let v = stack.popLast() {
        if let l = v as? UILabel { found.append(l) }
        stack.append(contentsOf: v.subviews)
    }
    return found
}

// ✅ 그래프에서는 방문 표시가 필수 (사이클 방지)
func reachable(from start: Node, edges: [Node.ID: [Node]]) -> Set<Node.ID> {
    var visited: Set<Node.ID> = []
    var queue = Deque([start])
    while let n = queue.popFirst() {
        guard visited.insert(n.id).inserted else { continue }
        queue.append(contentsOf: edges[n.id] ?? [])
    }
    return visited
}

struct Node: Identifiable { let id: String }

import Foundation

// 이 패턴이 실제 앱에서 성능 문제로 나타나는 대표적인 자리들이다.

struct Task2 {}

// ❌ ① 작업 큐
final class BadTaskQueue {
    private var tasks: [Task2] = []
    func next() -> Task2? {
        tasks.isEmpty ? nil : tasks.removeFirst()      // O(n)
    }
}

// ❌ ② BFS 순회 — 노드 수가 많으면 바로 티가 난다
func bfsBad(_ root: TreeNode) {
    var queue = [root]
    while !queue.isEmpty {
        let n = queue.removeFirst()                    // O(n) × 노드 수
        queue.append(contentsOf: n.children)
    }
}

// ❌ ③ 슬라이딩 윈도우
func windowBad(_ values: [Int], size: Int) -> [Int] {
    var window: [Int] = []
    var out: [Int] = []
    for v in values {
        window.append(v)
        if window.count > size { window.removeFirst() }  // O(size) × n
        out.append(window.reduce(0, +))
    }
    return out
}

// ✅ 각각의 올바른 형태
import Collections

func bfs(_ root: TreeNode) {
    var queue = Deque([root])
    while let n = queue.popFirst() {                   // O(1)
        queue.append(contentsOf: n.children)
    }
}

func window(_ values: [Int], size: Int) -> [Int] {
    var deque = Deque<Int>()
    var sum = 0, out: [Int] = []
    for v in values {
        deque.append(v); sum += v
        if deque.count > size, let old = deque.popFirst() { sum -= old }
        out.append(sum)                                // 합도 증분으로 유지
    }
    return out
}

final class TreeNode { var children: [TreeNode] = [] }

struct BadKey: Hashable {
    let id: Int
    func hash(into hasher: inout Hasher) { }               // 아무것도 안 섞음 → 항상 같은 해시
    static func == (l: BadKey, r: BadKey) -> Bool { l.id == r.id }
}
// 규약(== 이면 hash 같음)은 지켰지만, 모든 키가 한 버킷에 몰려
// Set/Dictionary 조회가 평균 O(1)이 아니라 O(n)으로 떨어진다.

import Foundation
import CoreGraphics        // CGSize의 Equatable·Hashable은 여기서 온다

// 컴파일러가 합성해 주면 ==과 hash가 자동으로 일관된다.
// 직접 구현하면 그 일관성을 사람이 책임져야 한다.

// ✅ 모든 저장 프로퍼티가 Hashable이면 한 줄이면 끝난다
struct ItemID: Hashable {
    let namespace: String
    let raw: UUID
}

struct Coordinate: Hashable {
    let x: Int
    let y: Int
}

// ✅ enum도 마찬가지 (연관값이 Hashable이면)
enum Category: Hashable {
    case system
    case user(id: UUID)
}

// ⚠️ 직접 구현해야 하는 경우: 동일성에 참여하지 않는 필드가 있을 때
struct CachedImage: Hashable {
    let url: URL
    let size: CGSize
    var lastAccessed: Date          // ← 동일성과 무관 (캐시 메타데이터)

    // ✅ ==에 쓴 필드만 hash에 넣는다. 규약: a == b ⇒ hash(a) == hash(b)
    static func == (l: CachedImage, r: CachedImage) -> Bool {
        l.url == r.url && l.size == r.size
    }
    func hash(into hasher: inout Hasher) {
        hasher.combine(url)
        hasher.combine(size.width)
        hasher.combine(size.height)
    }
}

// ❌ 흔한 실수 — ==에는 쓰는데 hash에는 빠뜨림
struct Broken: Hashable {
    let a: Int
    let b: Int
    static func == (l: Broken, r: Broken) -> Bool { l.a == r.a && l.b == r.b }
    func hash(into h: inout Hasher) { h.combine(a) }   // b 누락
    // 규약은 지켜지지만(같으면 해시도 같다) b만 다른 값들이 전부 충돌해
    // Set/Dictionary가 O(n)으로 떨어진다
}

import Foundation

// 컬렉션은 삽입 시점의 해시로 버킷을 정한다. 그 뒤에 해시가 바뀌면
// 원소가 '엉뚱한 버킷'에 남아 영영 찾을 수 없게 된다.

// ❌ 클래스 + 가변 프로퍼티가 해시에 참여
final class MutableKey: Hashable {
    var name: String
    init(name: String) { self.name = name }

    static func == (l: MutableKey, r: MutableKey) -> Bool { l.name == r.name }
    func hash(into h: inout Hasher) { h.combine(name) }
}

func demonstrateBug() {
    let key = MutableKey(name: "a")
    var set: Set<MutableKey> = [key]

    key.name = "b"                       // 💥 해시가 바뀌었다

    print(set.contains(key))             // false — 자기 자신도 못 찾는다
    print(set.count)                     // 1 — 여전히 안에는 있다
}

// ✅ ① 키는 값 타입 + 불변으로
struct ImmutableKey: Hashable {
    let name: String                     // let — 바뀔 수 없다
}

// ✅ ② 가변 상태가 필요하면 해시에서 빼고 별도로 관리한다
struct Entry: Hashable {
    let id: UUID                         // 동일성·해시는 id만
    static func == (l: Entry, r: Entry) -> Bool { l.id == r.id }
    func hash(into h: inout Hasher) { h.combine(id) }
}

final class EntryStore {
    private var entries: Set<Entry> = []
    private var metadata: [UUID: Metadata] = [:]     // 가변 부분은 옆에

    func touch(_ id: UUID) {
        metadata[id, default: Metadata()].accessCount += 1   // 해시에 영향 없음
    }
}
struct Metadata { var accessCount = 0 }

import Foundation

// 해시 테이블은 부하율이 임계를 넘으면 더 큰 테이블을 잡고
// 모든 원소를 '다시 해싱'해 옮긴다. 예약하면 이걸 없앨 수 있다.

// ❌ 20만 개 삽입 중 재해시가 여러 번 일어난다
func buildBad(_ ids: [String]) -> Set<String> {
    var seen = Set<String>()
    for id in ids { seen.insert(id) }
    return seen
}

// ✅ 최종 크기를 미리 알려 준다
func build(_ ids: [String]) -> Set<String> {
    var seen = Set<String>(minimumCapacity: ids.count)
    for id in ids { seen.insert(id) }
    return seen
}

// ✅ Dictionary도 동일
func buildIndex(_ rows: [Row]) -> [String: Row] {
    var index = [String: Row](minimumCapacity: rows.count)
    for r in rows { index[r.id] = r }
    return index
}

// ✅ 키가 유일함이 보장되면 이 이니셜라이저가 가장 빠르다
func buildFast(_ rows: [Row]) -> [String: Row] {
    Dictionary(uniqueKeysWithValues: rows.map { ($0.id, $0) })
}

// ✅ 중복 가능성이 있으면 병합 규칙을 명시한다 (크래시 방지)
func buildMerging(_ rows: [Row]) -> [String: Row] {
    Dictionary(rows.map { ($0.id, $0) }, uniquingKeysWith: { _, new in new })
}

// 효과 측정
func measure(_ ids: [String]) {
    let clock = ContinuousClock()
    print("예약 없음 \(clock.measure { _ = buildBad(ids) })")
    print("예약 있음 \(clock.measure { _ = build(ids) })")
}

struct Row { let id: String }

import Foundation

// Swift의 Hasher는 프로세스마다 무작위 시드를 쓴다(해시 DoS 방어).
// 그래서 같은 값이라도 앱을 다시 켜면 hashValue가 달라진다.

struct Key: Hashable { let name: String }

// ❌ ① 디스크·서버에 저장 — 다음 실행에서 전혀 다른 값이 되어 못 찾는다
func persistBad(_ key: Key) {
    UserDefaults.standard.set(key.hashValue, forKey: "cacheKey")   // 💥
}

// ✅ 안정적인 식별자를 직접 만든다
func persist(_ key: Key) {
    UserDefaults.standard.set(key.name, forKey: "cacheKey")
}

// ✅ 콘텐츠 해시가 필요하면 암호학적 해시를 쓴다 (실행 간 안정)
import CryptoKit
func stableHash(_ s: String) -> String {
    // 파일명에 쓸 거면 base64가 아니라 16진수로 — 표준 base64에는 '/'가 들어가 경로가 깨진다
    SHA256.hash(data: Data(s.utf8)).map { String(format: "%02x", $0) }.joined()
}

// ❌ ② 동일성 판정에 hashValue 비교 — 충돌이 정상이므로 틀린다
func equalsBad(_ a: Key, _ b: Key) -> Bool {
    a.hashValue == b.hashValue        // 다른 값도 같은 해시일 수 있다
}

// ✅ 동일성은 ==가 판정한다
func equals(_ a: Key, _ b: Key) -> Bool { a == b }

// ❌ ③ 캐시 파일 이름에 hashValue 사용
func cachePathBad(_ url: URL) -> String {
    "\(url.hashValue).cache"          // 재실행 시 캐시 전체가 미아가 된다
}

// ✅ 안정적인 파일명
func cachePath(_ url: URL) -> String {
    stableHash(url.absoluteString) + ".cache"
}

func binarySearch<T: Comparable>(_ a: [T], _ target: T) -> Int? {
    var lo = 0, hi = a.count - 1
    while lo <= hi {
        let mid = lo + (hi - lo) / 2       // (lo+hi)/2 는 오버플로 위험(Swift는 트랩)
        if a[mid] == target { return mid }
        else if a[mid] < target { lo = mid + 1 }   // 정렬 기준과 같은 비교여야 함
        else { hi = mid - 1 }
    }
    return nil
}

import Foundation

struct Event { let timestamp: Date; let name: String }

// ✅ 여러 번 조회할 데이터는 정렬을 한 번만 하고 재사용한다
struct EventIndex {
    private let sorted: [Event]

    init(_ events: [Event]) {
        sorted = events.sorted { $0.timestamp < $1.timestamp }   // O(n log n) 1회
    }

    /// 주어진 시각 이후 첫 이벤트의 인덱스 (lower bound)
    func firstIndex(onOrAfter date: Date) -> Int {
        var low = 0, high = sorted.count
        while low < high {
            let mid = low + (high - low) / 2        // 오버플로 안전
            if sorted[mid].timestamp < date { low = mid + 1 } else { high = mid }
        }
        return low
    }

    /// 범위 조회도 O(log n) 두 번으로 끝난다
    func events(from start: Date, to end: Date) -> ArraySlice<Event> {
        let lo = firstIndex(onOrAfter: start)
        let hi = firstIndex(onOrAfter: end)
        return sorted[lo..<hi]
    }
}

// 사용
func usage(_ events: [Event]) {
    let index = EventIndex(events)                  // 정렬 1회
    let today = index.events(from: .now.addingTimeInterval(-86400), to: .now)
    _ = today                                        // 이후 조회는 전부 O(log n)
}

// ⚠️ 삽입이 잦으면 정렬 배열 유지 비용(삽입 O(n))이 커진다.
//    그때는 Dictionary(평균 O(1) 조회) 또는 정렬 트리를 검토한다.
//    선택 기준: 조회 : 삽입 비율과, 범위 조회가 필요한지 여부.

import Foundation

struct User { let id: Int; let name: String; let score: Int }

// ❌ 이름순으로 정렬해 놓고 점수로 이진탐색 — 조용히 틀린 답을 준다
func brokenSearch(_ users: [User], score: Int) -> User? {
    let sorted = users.sorted { $0.name < $1.name }     // 이름순
    var low = 0, high = sorted.count - 1
    while low <= high {
        let mid = (low + high) / 2
        if sorted[mid].score == score { return sorted[mid] }
        else if sorted[mid].score < score { low = mid + 1 }   // 💥 전제가 깨졌다
        else { high = mid - 1 }
    }
    return nil
}

// ✅ 정렬과 탐색이 같은 키를 쓰도록 타입으로 묶는다
struct SortedBy<T, K: Comparable> {
    private let items: [T]
    private let key: (T) -> K

    init(_ items: [T], by key: @escaping (T) -> K) {
        self.key = key
        self.items = items.sorted { key($0) < key($1) }   // 여기서 쓴 키를
    }

    func firstIndex(onOrAfter value: K) -> Int {
        var low = 0, high = items.count
        while low < high {
            let mid = low + (high - low) / 2
            if key(items[mid]) < value { low = mid + 1 } else { high = mid }
        }
        return low                                        // 탐색에서도 그대로 쓴다
    }

    subscript(i: Int) -> T { items[i] }
    var count: Int { items.count }
}

// 사용 — 키를 한 곳에만 적으므로 어긋날 수가 없다
func usage(_ users: [User]) {
    let byScore = SortedBy(users) { $0.score }
    let i = byScore.firstIndex(onOrAfter: 80)
    _ = i
}

import Foundation

struct Item { let id: Int; let priority: Int }

// ❌ 조회 한 번에 O(n log n) — 이진탐색을 쓰는 의미가 완전히 사라진다
func findBad(_ items: [Item], priority: Int) -> Item? {
    let sorted = items.sorted { $0.priority < $1.priority }   // 💥 매번 정렬
    return binarySearch(sorted, priority)
}

// 이 패턴은 특히 UI 코드에서 조용히 숨는다
final class BadViewModel {
    var items: [Item] = []

    // cellForRowAt에서 호출되면 화면에 보이는 행 수만큼 정렬이 돈다
    func item(at index: Int) -> Item {
        items.sorted { $0.priority < $1.priority }[index]      // 💥
    }
}

// ✅ 정렬 결과를 캐시하고, 원본이 바뀔 때만 무효화한다
final class ViewModel {
    private var items: [Item] = [] {
        didSet { sortedCache = nil }          // ✅ 변경 시 무효화
    }
    private var sortedCache: [Item]?

    private var sorted: [Item] {
        if let sortedCache { return sortedCache }
        let s = items.sorted { $0.priority < $1.priority }
        sortedCache = s
        return s
    }

    func item(at index: Int) -> Item { sorted[index] }   // 정렬은 최대 1회

    func reload(_ new: [Item]) { items = new }
}

// ✅ 정렬 상태를 계속 유지해야 하면 삽입 시점에 위치를 찾아 넣는다
func insertSorted(_ item: Item, into array: inout [Item]) {
    var low = 0, high = array.count
    while low < high {
        let mid = low + (high - low) / 2
        if array[mid].priority < item.priority { low = mid + 1 } else { high = mid }
    }
    array.insert(item, at: low)      // 탐색 O(log n) + 삽입 O(n)
}

func binarySearch(_ a: [Item], _ p: Int) -> Item? { nil }

// 방법1: 안정 정렬 연쇄 — 덜 중요한 키(이름) 먼저, 중요한 키(날짜) 나중
items.sort { $0.name < $1.name }
items.sort { $0.date < $1.date }   // 같은 날짜끼리 이름순 유지(안정성 보장에 의존)

// 방법2: 튜플 비교 — tie-breaker를 명시(결정적, 안정성에 덜 의존)
items.sort { ($0.date, $0.name) < ($1.date, $1.name) }

import Foundation

struct Task3 { let title: String; let due: Date; let priority: Int }

// ✅ 방법 ① 튜플 비교 — tie-breaker가 한 줄에 드러나고 정렬을 한 번만 돈다
func sortByTuple(_ tasks: inout [Task3]) {
    tasks.sort { ($0.priority, $0.due, $0.title) < ($1.priority, $1.due, $1.title) }
}

// ✅ 방법 ② 안정 정렬 연쇄 — 덜 중요한 키 먼저, 중요한 키 나중
func sortByChaining(_ tasks: inout [Task3]) {
    tasks.sort { $0.title < $1.title }        // 3차
    tasks.sort { $0.due < $1.due }            // 2차
    tasks.sort { $0.priority < $1.priority }  // 1차 — 앞 순서가 보존된다
}

// ⚠️ 연쇄는 순서를 거꾸로 생각하기 쉽다. 중요한 키가 '나중'이다.
// ⚠️ 정렬을 n번 돌므로 비용도 n배다.

// ✅ 내림차순이 섞이면 튜플이 안 되므로 비교 함수를 명시한다
func sortMixed(_ tasks: inout [Task3]) {
    tasks.sort { a, b in
        if a.priority != b.priority { return a.priority > b.priority }  // 내림차순
        if a.due != b.due { return a.due < b.due }                      // 오름차순
        return a.title < b.title
    }
}

// ✅ 재사용할 비교자는 타입으로 뽑아 둔다
struct TaskComparator: SortComparator {
    var order: SortOrder = .forward
    func compare(_ a: Task3, _ b: Task3) -> ComparisonResult {
        let base: ComparisonResult = (a.priority != b.priority)
            ? (a.priority < b.priority ? .orderedAscending : .orderedDescending)
            : a.title.compare(b.title)
        // ⚠️ order를 반영하지 않으면 컬럼 헤더로 방향을 토글해도 아무 일이 없다
        guard order == .reverse else { return base }
        switch base {
        case .orderedAscending:  return .orderedDescending
        case .orderedDescending: return .orderedAscending
        case .orderedSame:       return .orderedSame
        }
    }
}

func sortWithComparator(_ tasks: inout [Task3]) {
    tasks.sort(using: TaskComparator())
}

import UIKit

struct Post: Hashable, Identifiable {
    let id: UUID
    let author: String
    let createdAt: Date
}

// diffable 스냅샷은 '순서'로 애니메이션을 결정한다.
// 동점 항목의 순서가 갱신마다 흔들리면 실제로 변한 게 없는데도 셀이 자리를 바꾼다.

// ❌ 날짜만으로 정렬 — 같은 초에 올라온 글들의 순서가 불안정할 수 있다
func snapshotBad(_ posts: [Post]) -> NSDiffableDataSourceSnapshot<Int, Post.ID> {
    var snap = NSDiffableDataSourceSnapshot<Int, Post.ID>()
    snap.appendSections([0])
    snap.appendItems(posts.sorted { $0.createdAt > $1.createdAt }.map(\.id))
    return snap
}

// ✅ 완전히 결정적인 순서를 만든다 — id가 최종 tie-breaker
func snapshot(_ posts: [Post]) -> NSDiffableDataSourceSnapshot<Int, Post.ID> {
    var snap = NSDiffableDataSourceSnapshot<Int, Post.ID>()
    snap.appendSections([0])
    let ordered = posts.sorted {
        ($0.createdAt, $0.id.uuidString) > ($1.createdAt, $1.id.uuidString)
    }
    snap.appendItems(ordered.map(\.id))
    return snap
}

// ✅ 정렬 로직을 한 곳에 모아 두면 화면마다 어긋날 일이 없다
extension Array where Element == Post {
    /// 피드 표준 정렬 — 최신순, 동점이면 id순 (완전 결정적)
    func feedOrdered() -> [Post] {
        sorted { ($0.createdAt, $0.id.uuidString) > ($1.createdAt, $1.id.uuidString) }
    }
}

// ✅ 테스트로 결정성을 고정한다
func test_정렬이_결정적이다(_ posts: [Post]) {
    let a = posts.feedOrdered().map(\.id)
    let b = posts.shuffled().feedOrdered().map(\.id)
    assert(a == b, "입력 순서에 따라 결과가 달라진다")
}

import Foundation

struct Row { let group: String; let name: String }

// Swift 표준 sort는 안정성이 보장되지만, 그 사실에 '암묵적으로' 기대는 코드는
// 읽는 사람에게 전제가 보이지 않아 위험하다.

// ❌ 왜 이 순서가 나오는지 코드만 봐서는 알 수 없다
func sortBad(_ rows: inout [Row]) {
    rows.sort { $0.name < $1.name }
    rows.sort { $0.group < $1.group }
    // "같은 group 안에서 name순"이 되는 이유가 안정성이라는 걸
    // 주석 없이는 아무도 모른다. 누가 중간에 다른 정렬을 끼워 넣으면 조용히 깨진다.
}

// ✅ 전제를 코드에 드러낸다
func sortExplicit(_ rows: inout [Row]) {
    rows.sort { ($0.group, $0.name) < ($1.group, $1.name) }
    // 규칙이 한 줄에 다 있다. 읽는 사람이 추론할 필요가 없다.
}

// ✅ 연쇄를 써야 한다면 이유를 남긴다
func sortChained(_ rows: inout [Row]) {
    // 안정 정렬 연쇄: 2차 키(name) 먼저, 1차 키(group) 나중.
    // Swift sort는 안정성이 보장되므로 group이 같은 무리 안에서 name 순서가 유지된다.
    rows.sort { $0.name < $1.name }
    rows.sort { $0.group < $1.group }
}

// ⚠️ 다른 언어·라이브러리로 옮길 때 특히 위험하다
//    C++ std::sort, Java Arrays.sort(primitives), 대부분의 quicksort 구현은 불안정하다.
//    서버와 클라이언트가 같은 정렬을 재현해야 한다면 tie-breaker를 명시하는 게 안전하다.

// ✅ 동점 순서가 눈에 보이는 결과(UI 순서, 페이지네이션 경계)에 영향을 주면
//    안정성이 아니라 명시적 규칙에 의존한다

var items: [Feed] = []
var seen = Set<Feed.ID>()

func merge(_ page: [Feed]) {
    for item in page where seen.insert(item.id).inserted {
        items.append(item)          // 처음 본 id만 추가 → 페이지 크기에 비례(O(page))
    }
}

import Foundation

// offset은 "몇 번째부터"라서, 목록이 중간에 바뀌면 경계가 어긋난다.
//   1페이지(0~19) 받은 뒤 새 글 1개가 맨 앞에 추가되면
//   2페이지(20~39)는 원래 19번이었던 항목부터 다시 준다 → 중복
//   반대로 글이 삭제되면 → 누락

// ❌ offset 기반
struct OffsetRequest: Encodable {
    let offset: Int
    let limit: Int
}

// ✅ cursor(keyset) 기반 — "이 지점 다음부터"라 삽입·삭제에 영향받지 않는다
struct CursorRequest: Encodable {
    let after: String?      // 직전 페이지 마지막 항목의 커서
    let limit: Int
}

struct Page<T: Decodable>: Decodable {
    let items: [T]
    let nextCursor: String?     // nil이면 마지막 페이지
    var hasMore: Bool { nextCursor != nil }
}

// 클라이언트 루프
final class FeedPager {
    private var cursor: String?
    private(set) var isFinished = false

    func loadNext() async throws -> [Post] {
        guard !isFinished else { return [] }
        let page: Page<Post> = try await api.feed(after: cursor, limit: 20)
        cursor = page.nextCursor
        isFinished = !page.hasMore
        return page.items
    }

    func reset() { cursor = nil; isFinished = false }
}

// ⚠️ 커서는 불투명 문자열로 다룬다 — 클라가 파싱·생성하려 하면 안 된다.
//    서버가 (정렬키, tie-breaker id)를 인코딩한 값이다.

struct Post: Decodable {}
enum api {
    static func feed(after: String?, limit: Int) async throws -> Page<Post> {
        Page(items: [], nextCursor: nil)
    }
}

import Foundation

// 서버가 완벽해도 중복은 온다: 재시도, 경합, 푸시와 폴링의 겹침, 캐시 재생.
// 클라이언트에 얇은 방어선을 두는 비용은 거의 0이다.

struct Post: Identifiable, Hashable {
    let id: UUID
    let title: String
    let updatedAt: Date
}

final class FeedStore {
    private(set) var items: [Post] = []
    private var seen = Set<Post.ID>()

    /// 처음 본 것만 뒤에 붙인다 — 페이지 크기에 비례하는 O(page)
    func append(_ page: [Post]) {
        items.reserveCapacity(items.count + page.count)
        for post in page where seen.insert(post.id).inserted {
            index[post.id] = items.count      // append와 upsert가 같은 장부를 쓰게 한다
            items.append(post)
        }
    }

    /// 갱신이 올 수도 있으면 '최신으로 교체'까지 처리한다
    private var index: [Post.ID: Int] = [:]

    func upsert(_ page: [Post]) {
        for post in page {
            if let i = index[post.id] {
                // 더 새로운 것만 반영 (오래된 응답이 나중에 도착할 수 있다)
                if post.updatedAt > items[i].updatedAt { items[i] = post }
            } else {
                index[post.id] = items.count
                seen.insert(post.id)          // seen도 함께 갱신해야 append와 어긋나지 않는다
                items.append(post)
            }
        }
    }

    func reset() { items.removeAll(); seen.removeAll(); index.removeAll() }
}

// ✅ 순서를 유지한 채 중복만 없애는 간단한 방법
func deduped(_ posts: [Post]) -> [Post] {
    var seen = Set<Post.ID>(minimumCapacity: posts.count)
    return posts.filter { seen.insert($0.id).inserted }
}

import Foundation

// diffable data source·SwiftUI ForEach는 id로 셀 정체성을 판단한다.
// id가 불안정하면 셀이 이유 없이 재생성되고 애니메이션이 튄다.

// ❌ ① 배열 인덱스를 id로 — 목록이 바뀌면 전혀 다른 항목을 같다고 판단한다
struct BadRow: Identifiable {
    let id: Int          // 0, 1, 2 … 순번
    let title: String
}

// ❌ ② 내용 기반 id — 제목만 바뀌어도 '다른 항목'이 되어 셀이 사라졌다 나타난다
struct AlsoBad: Identifiable {
    var id: String { title }
    let title: String
}

// ❌ ③ 객체 주소·hashValue — 실행마다 달라진다

// ✅ 서버가 준 안정적 식별자를 그대로 쓴다
struct Post: Identifiable, Hashable {
    let id: UUID         // 서버 발급. 내용이 바뀌어도 유지된다.
    var title: String
    var likeCount: Int
}

// ✅ 서버 id가 없는 로컬 항목은 생성 시점에 한 번 부여한다
struct Draft: Identifiable {
    let id = UUID()      // ⚠️ let — 매번 새로 만들면 안 된다
    var text: String = ""
}

// ❌ 이렇게 하면 매 접근마다 새 id가 나온다
struct BrokenDraft: Identifiable {
    var id: UUID { UUID() }      // 💥 뷰가 그릴 때마다 다른 항목이 된다
}

// ✅ 두 소스를 합칠 때는 네임스페이스로 충돌을 막는다
enum FeedItemID: Hashable {
    case post(UUID)
    case ad(String)
}

// SwiftUI에서
// ForEach(posts) { post in ... }          // Identifiable이면 자동
// ForEach(posts, id: \.id) { ... }        // 명시
// ❌ ForEach(0..<posts.count) { ... }      // 인덱스 — 항목이 바뀌면 깨진다

import Foundation

struct Post: Identifiable { let id: UUID }

// ❌ 병합마다 기존 배열 전체를 훑는다 — 페이지가 쌓일수록 급격히 느려진다
func mergeBad(_ items: inout [Post], _ page: [Post]) {
    for post in page {
        if !items.contains(where: { $0.id == post.id }) {     // O(n)
            items.append(post)
        }
    }
    // 20페이지째면 items가 400개 → 페이지당 20 × 400 = 8,000번 비교
    // 100페이지째면 20 × 2,000 = 40,000번. 전체로는 O(n²).
}

// ✅ Set으로 O(1) 판정
final class FeedStore {
    private(set) var items: [Post] = []
    private var seen = Set<Post.ID>()

    func merge(_ page: [Post]) {
        for post in page where seen.insert(post.id).inserted {
            items.append(post)                                 // O(page)
        }
    }
}

// 두 방식의 차이를 재 본다
func benchmark() {
    let pages = (0..<100).map { p in (0..<20).map { _ in Post(id: UUID()) } }
    let clock = ContinuousClock()

    let bad = clock.measure {
        var items: [Post] = []
        for page in pages { mergeBad(&items, page) }
    }

    let good = clock.measure {
        let store = FeedStore()
        for page in pages { store.merge(page) }
    }

    print("contains \(bad) vs Set \(good)")
}

// ⚠️ 같은 함정이 숨는 다른 자리들
//    · firstIndex(where:)로 매번 위치 찾기 → 인덱스 딕셔너리를 유지한다
//    · removeAll(where:)를 루프 안에서 호출 → 한 번만 호출한다
//    · 정렬된 배열에 매번 sorted() → 삽입 위치를 이진탐색으로 찾는다