ios - 过滤具有大量对象的数组的唯一名称

Question

我目前正在获取大量包含街道名称和坐标的对象。返回的数组大约有 22.000 个对象，而我们想要的结果数组大约有 4000 个，其余的都是重复的。这种数据的问题是获取的对象可以具有相同的名称但坐标不同，我只对基于唯一名称获取对象感兴趣。如果有多个同名对象，我只想保留第一个对象。

到目前为止，我一直在尝试通过比较名称来遍历街道。我宁愿使用 filter 或其他一些性能更高效的解决方案。

我的结构

struct StreetName {
    var name: String
    var polyLine: CLLocationCoordinate2D
}

到目前为止我的代码

DataManager.shared.getStreetNames { (streets) in  
    var namesArray: [StreetName] = []
    for streetName in streets {
        let name = streetName.name
        if namesArray.count == 0 {
            namesArray.append(streetName)
        } else if namesArray.contains(where: {$0.name == name }) { 
             /* Dont add */ 
        } else {
             namesArray.append(streetName)
        }
    }

    self.streetNames = namesArray.sorted(by: {$0.name < $1.name})
    self.filteredStreetNames = self.streetNames
    OperationQueue.main.addOperation {
        self.streetTableView.reloadData()
    }
}

此代码块有效，但在 iPhone X 上运行大约需要 30 秒。这太慢了。有什么想法吗？

Answer 1

我想如果您分析一下，您会发现排序 花费的时间最多。我找不到官方说明，但很有可能底层实现是快速排序，当数组已经排序(或数组以相反顺序排序)时，它的复杂性最差.

快速排序的平均情况复杂度为 O(n log n)，但在最坏情况下为 O(n²)。

我认为您应该改为实现插入排序，或者更准确地说，始终将新元素插入到已排序的位置。这应该可以将整个函数的复杂度降低到 O(n)。

伪代码:

• 获取街道名称
• 对于每个街道名称
  • 在现有数组中找到街道名称所在的位置(我建议二分查找，因为数组已经排序)
  • 如果街道名称已经存在，则跳过
  • 如果名称不存在，请插入。

结果应该是一个排序的唯一街道名称数组，要求每个名称只能读取和插入一次。