时间戳

首页 > 解决方案 > 过滤具有大量对象的数组的唯一名称

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

问题描述

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

标签： iosswiftperformance

解决方案

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

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

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

伪代码：

  • 获取街道名称
  • 对于每个街道名称
    • 在现有数组中找到街道名称所在的位置（我建议二进制搜索，因为数组已经排序）
    • 如果街道名称已经存在，请跳过
    • 如果名称不存在，请插入它。

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

推荐阅读