Swift中按指定字段对结构体数组去重的最佳实现方案

原实现的性能问题 #

你当前的写法可以得到预期的去重结果，但存在明显的性能缺陷：每次向临时数组追加元素前，都会调用filter遍历整个临时数组统计同名元素数量，整体时间复杂度为O(n²)，当数组元素量级较大时性能损耗会非常明显。

原实现代码：

struct DistinctListOnName{
    init(){
        let alist: [myList] = [myList(id: 1, name: "Jeff", status: "A"),
                             myList(id: 2, name: "Mike", status: "A"),
                             myList(id: 3, name: "Mike", status: "B"),
                             myList(id: 4, name: "Ron", status: "B")]
        
        var tmp: [myList] = []
        for i in alist{
            if (tmp.filter({ item in
                item.name == i.name
            }).count == 0) {
                tmp.append(i)
            }
        }
        print(tmp)
    }
}

struct myList {
    var id: Int
    var name: String
    var status: String
    init(id: Int, name: String, status: String){
        self.id = id
        self.name = name
        self.status = status
    }
}

运行后得到预期输出：

[(id: 1, name: "Jeff", status: "A"), (id: 2, name: "Mike", status: "A"), (id: 4, name: "Ron", status: "B")]

O(n)复杂度的优化实现 #

核心优化思路是额外维护一个Set集合记录已经出现过的name值，利用Set元素查找O(1)的时间特性，把整体时间复杂度降到O(n)，不需要每次遍历临时数组做检查：

struct DistinctListOnName{
    init(){
        let alist: [myList] = [myList(id: 1, name: "Jeff", status: "A"),
                             myList(id: 2, name: "Mike", status: "A"),
                             myList(id: 3, name: "Mike", status: "B"),
                             myList(id: 4, name: "Ron", status: "B")]
        
        var tmp: [myList] = []
        // 记录已经出现过的name
        var seenNames = Set<String>()
        for item in alist {
            // Set的insert方法会返回插入是否成功的标记，成功代表name是第一次出现
            if seenNames.insert(item.name).inserted {
                tmp.append(item)
            }
        }
        print(tmp)
    }
}

struct myList {
    var id: Int
    var name: String
    var status: String
    init(id: Int, name: String, status: String){
        self.id = id
        self.name = name
        self.status = status
    }
}

方案优势 #

• 去重逻辑和原实现完全一致：保留原数组元素顺序，同名元素默认保留第一次出现的条目
• 时间复杂度从O(n²)降至O(n)，数组元素量级越大，性能提升越明显
• 去掉了嵌套的filter遍历，代码逻辑更简洁易读

如果有多处类似的按字段去重需求，也可以把这段逻辑封装成Sequence的扩展方法，直接传入去重依据的KeyPath即可复用。

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