对大量项目使用数组、集合或字典更好吗？

Question

我的应用程序加载两个 json 文件，一个包含 27 个项目（州），另一个包含 5.000 个项目（城市），所有项目都是唯一的，json 示例：

state:{
        "_id": "58c0a61052effb00a396d399",
        "sigla": "AM",
        "descricao": "Amazonas"
}

city:{
      "_id": "5949767555cb9533e09c2932",
      "state": "58c0a6104ace7c56035f7691",
      "nome": "Abadia dos Dourados",
      "ibge": 3100104,
 }

我需要执行以下操作：

• 搜索一个州的所有城市；

• 搜索状态以获取 id；

• 搜索一个城市的 id；

• 搜索城市名称；

在这种情况下使用数组、集合或字典更好吗？

Answer 1

要了解以下信息，您需要了解Big O 符号。简而言之，这是您的算法在最坏情况下完成任务所需的步骤数。例如，如果元素位于最后一个位置，则在最坏的情况下将元素搜索到数组中将花费n步。因此，搜索数组中的元素可以认为是 O(n)。有关 O 表示法的更多参考资料，请查看本答案末尾的参考资料。

好的，知道了这一点，现在您应该选择执行较少步骤的数据结构来完成您想要的任务。这将使您的算法更快，并且在某些情况下，这种差异可能很大。

根据 Raywenderlich 参考，以下是您询问的数据结构及其性能的一些信息：

大批

当项目的顺序很重要时使用数组。示例：按名字或姓氏排序的联系人、按日期的待办事项列表，或按特定顺序查找或显示数据至关重要的其他情况。

根据 Apple 文档的性能：

1. 创建一个 Swift 数组和一个 NSArray 在 O(log n) 和 O(n) 之间以大致相同的速率降级。
2. 访问特定索引处的任何值最坏的情况是 O(log n)，但通常应该是 O(1)。
3. 在未知索引处搜索对象最坏的情况是 O (n (log n))，但通常是 O(n)。
4. 插入或删除对象最坏的情况是 O(n (log n))，但通常是 O(1)。

基本上，这些性能预期意味着当您知道对象的索引时数组是好的，主要使用 O(1) 操作。

字典

当您需要存储的内容没有特定的顺序，但数据具有有意义的关联时，最好使用字典。字典使用称为哈希表的数据结构，它允许一些与数组相关的性能改进。

根据 Apple 文档，字典的预期性能是：

1. 获取单个值的性能下降最坏保证为 O(log n)，但通常为 O(1)。
2. 插入和删除可能与 O(n (log n)) 一样糟糕，但通常会更接近 O(1)。

放

集合是一种存储无序、唯一值的数据结构。独特是关键词；您将无法添加重复项。

Apple 没有像对字典和数组那样概述对集合性能的总体期望，因此在这种情况下，您只需查看实际性能。

根据 Raywenderlich 所做的测试，该套装的性能为：

1. 集合创建复杂度约为 O(n)。
2. 将对象添加到 NSSet 保持接近 O(1)，而使用 Swift 的 Set 结构，它可以以高于 O(n) 的速率降级。
3. 删除一个元素大约是 O(1)。
4. 搜索一个元素大约是 O(1)。

综上所述

因此，对于您的情况，我建议您使用以id为键的字典，因为您的大多数搜索都会使用它。这意味着，大多数情况下，程序需要一步 O(1) 才能找到字典中的任何城市。如果它是一个数组，它可能需要 5000 步，如果你有 5000 个城市。

您也可以使用集合，因为它在内部使用散列。但是，我想在集合中，当您搜索实例对象城市而不是其中的属性时，这种优势会很有用。例如：

let citiesSet = Set()
// add some cities into citiesSet
let city = City()
citiesSet.contains(city) //this search will be O(1)

我不确定上述信息，但我想它是如何发生的（如果我错了，有人可以纠正我）。

对于按名称搜索城市，它仍然需要在字典中进行n步，因为名称不是关键。但这还是比对所有操作都采取n步要好哈哈。

您可以使用另一个以 name 为键的字典，但这种数据重复对我来说听起来像是一个额外的复杂问题，因为您需要保证两个字典中的数据都得到更新。所以我不会那样做。

下面的 Raywenderlich 参考非常有助于更好地了解这些结构及其性能。我建议你阅读它。

参考：

大 O 符号 - 维基百科

Swift 中的数据结构 - Raywenderlich