Swift中如何避免数组查找的O(n)复杂度？赛车场景优化

原代码中overtake和use wormhole按钮每次点击都会执行两次firstIndex(where:)操作，每次操作的时间复杂度为O(n)。当数组规模较大时，两次遍历会带来明显的性能开销，且数组顺序不能修改（排序会破坏原有顺序并消耗CPU），因此需要在保持数组顺序的前提下优化查找效率。

方案一：单次遍历完成双重查找 #

将两次O(n)的遍历合并为一次，在遍历数组时同时定位"Me"的位置和目标车辆的位置，将时间复杂度从O(2n)降低到O(n)。

修改后的按钮代码示例：

Button("overtake") {
    var myIndex: Int?
    var targetRank: Int?
    var overtakeIndex: Int?
    
    // 一次遍历同时找到自身位置和目标车辆位置
    for (index, car) in cars.enumerated() {
        if car.name == "Me" {
            myIndex = index
            targetRank = car.rank - 1
        } else if let rank = targetRank, car.rank == rank {
            overtakeIndex = index
        }
    }
    
    guard let idx = myIndex, let overIdx = overtakeIndex, cars[idx].rank != 1 else {
        return
    }
    
    cars[idx].rank -= 1
    cars[overIdx].rank += 1
}

Button("use wormhole") {
    var myIndex: Int?
    var overtakeIndex: Int?
    
    for (index, car) in cars.enumerated() {
        if car.name == "Me" {
            myIndex = index
        } else if car.rank == 1 {
            overtakeIndex = index
        }
    }
    
    guard let idx = myIndex, let overIdx = overtakeIndex, cars[idx].rank != 1 else {
        return
    }
    
    let originalMyRank = cars[idx].rank
    cars[idx].rank = 1
    cars[overIdx].rank = originalMyRank
}

方案二：维护缓存映射实现O(1)查找 #

利用rank的唯一性（每个车辆rank不重复），维护一个rank -> 数组索引的字典，以及记录自身的索引。仅在数组变化时更新缓存，后续所有查找操作都为O(1)复杂度，适合数组规模大、按钮点击频繁的场景。

完整修改后的代码：

struct ContentView: View {
    
    @State private var cars: [CarType] = [CarType("A", rank: 5), CarType("B", rank: 3), CarType("C", rank: 1), CarType("D", rank: 2), CarType("E", rank: 4), CarType("Me", rank:6)]
    @State private var rankToIndex: [Int: Int] = [:]
    @State private var myCurrentIndex: Int?
    
    var body: some View {
        
        VStack(spacing: 10.0) {
            
            ForEach(cars, id:\.id) { car in
                Text(car.name)
                    .frame(width: 25, height: 25)
                    .background(Color.gray.opacity(0.5).cornerRadius(5.0))
                    .offset(x: 100 - Double(car.rank)*20)
            }
            .animation(.default, value: cars)
            
            Button("overtake") {
                guard let myIdx = myCurrentIndex, cars[myIdx].rank != 1 else {
                    return
                }
                let targetRank = cars[myIdx].rank - 1
                guard let overtakeIdx = rankToIndex[targetRank] else {
                    return
                }
                
                cars[myIdx].rank -= 1
                cars[overtakeIdx].rank += 1
            }
            
            Button("use wormhole") {
                guard let myIdx = myCurrentIndex, cars[myIdx].rank != 1 else {
                    return
                }
                guard let overtakeIdx = rankToIndex[1] else {
                    return
                }
                
                let originalMyRank = cars[myIdx].rank
                cars[myIdx].rank = 1
                cars[overtakeIdx].rank = originalMyRank
            }
            
            Button("reset") {
                cars = [CarType("A", rank: 5), CarType("B", rank: 3), CarType("C", rank: 1), CarType("D", rank: 2), CarType("E", rank: 4), CarType("Me", rank:6)]
            }
            
        }
        .frame(width: 200)
        .padding()
        .overlay(Text("🏁"), alignment: .trailing)
        .onChange(of: cars) { newCars in
            // 更新缓存映射
            var map: [Int: Int] = [:]
            var meIdx: Int?
            for (index, car) in newCars.enumerated() {
                map[car.rank] = index
                if car.name == "Me" {
                    meIdx = index
                }
            }
            rankToIndex = map
            myCurrentIndex = meIdx
        }

    }
}

struct CarType: Equatable {
    
    let id: UUID = UUID()
    var name: String
    var rank: Int
    
    init(_ name: String, rank: Int) {
        self.name = name
        self.rank = rank
    }
}

方案对比 #

• 方案一：实现简单，无需额外状态维护，适合数组规模中等的场景，将时间复杂度从O(2n)优化为O(n)。
• 方案二：需要维护缓存状态，但查找操作降为O(1)，数组变化时仅需一次O(n)遍历更新缓存，性能最优，适合数组规模大、交互频繁的场景。

内容的提问来源于stack exchange，提问作者swiftPunk