Swift 巨大的数组字典，非常慢

Question

我正在 Swift 中使用 dictionary.

进行一个项目

这本词典的类型是[String : [Posting]]。我有大约 20 万个不同的 "terms"（键）要插入其中，对于每个术语，我有大约 500 到 1000 个对象要附加到列表中。我知道这是一种奇怪的做法，但我别无选择，我必须处理所有这些因素。

问题是随着字典变大，这非常非常慢。我尝试切换到 NSMutableDictionary，但没有成功。

每次我需要插入元素时都会调用我的 addTerm 函数：

   func addTerm(_ term: String, withId id: Int, atPosition position: Int) {

        if self.map[term] == nil {
            self.map[term] = [Posting]()
        }

        if self.map[term]!.last?.documentId == id {
            self.map[term]!.last?.addPosition(position)
        }
        else {
            self.map[term]!.append(Posting(withId: id, atPosition: position, forTerm: term))
        }
    }

编辑：我意识到不是字典导致了所有这些滞后，而是它实际上包含的数组。添加新元素时，数组重新分配的方式太多，我能做的最好的就是用 ContiguousArray 替换它们。

Answer 1

当您的代码太慢时，一般的方法是在 Instruments 中对其进行分析，以确定哪些行实际花费的时间最长，然后从那里开始。其他地方可能存在瓶颈等。运行您的应用程序直接从 Xcode 内部创建也会创建调试版本，这会牺牲性能以换取可调试性。发布版本的性能可能会好得多。

此外，如果您的程序占用大量内存，系统可能难以为您的应用提供这些内存。在非 iOS 平台上，这将导致将内存换出到磁盘，这将显着影响应用程序的性能，因为系统无法预测接下来将访问字典的哪些元素。

如果内存需求不是导致速度下降的原因，我会尝试以下几种方法：

如果您可以估计要插入字典的项目数，则可以使用 dictionary.reserveCapacity(numberOfItems)。随着字典的增长，它可能需要调整大小，这可能需要重建字典类型内部使用的散列table。这种方法也适用于数组。
Swift 提供了使用公共键自动将项目分组到字典中的方法：Dictionary(grouping: collection, by: { item in item.property })。这种方法在计算上可能更有效，因为所有内容都可以在一批中处理。
另一种方法可能是使用其他数据类型，例如树图，不需要频繁重新分配。 Swift 但是在标准库中没有提供这样的类型。

Answer 2

这是相当常见的性能陷阱，在以下方面也观察到了：

问题源于这样一个事实，即您在表达式 self.map[term]!.append(...) 中改变的数组是字典存储中基础数组的临时可变副本。这意味着该数组永远不会被唯一引用，因此总是会重新分配其缓冲区。

这种情况将在 Swift 5 中通过非官方的广义访问器引入得到解决，但在此之前，一种解决方案（如上述问答中所述）是使用 Dictionary 的 subscript(_:default:) 从 Swift 4.1 可以直接在存储中改变值。

尽管您的案例并不是应用单个突变的简单案例，因此您需要某种包装函数以允许您对可变数组进行范围内访问。

例如，这可能看起来像：

class X {

  private var map: [String: [Posting]] = [:]

  private func withPostings<R>(
    forTerm term: String, mutations: (inout [Posting]) throws -> R
  ) rethrows -> R {
    return try mutations(&map[term, default: []])
  }

  func addTerm(_ term: String, withId id: Int, atPosition position: Int) {

    withPostings(forTerm: term) { postings in
      if let posting = postings.last, posting.documentId == id {
        posting.addPosition(position)
      } else {
        postings.append(Posting(withId: id, atPosition: position, forTerm: term))
      }
    }

  }
  // ...
}

Answer 3

我遇到了同样的问题。 200K 条目的速度太慢了...... 所以我做了一个 class 并将数组放在那里......

class MyIndex
{
    var entries: [Posting]
}

var map = [String: MyIndex]()

现在似乎工作得很快

Swift 巨大的数组字典，非常慢

Swift enormous dictionary of arrays, very slow

arrays

performance

dictionary

nsdictionary

swift