我目前正在获取大量包含街道名称和坐标的对象。返回的数组大约有 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 秒。这太慢了。有任何想法吗?

最佳答案

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

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

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

伪代码:

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

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

    关于ios - 过滤具有大量对象的数组的唯一名称,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/50057516/

    10-10 18:29
    查看更多