Swift庞大的数组字典，速度非常慢。

Question

我正在使用Swift开发一个项目，使用了一个字典。

这个字典的类型是[String : [Posting]]。我有大约20万个不同的“术语”（键）要插入其中，对于每个术语，我有大约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替换它们。

- Scaraux

---

因为这是一个课程项目，一个搜索引擎，可以使用Java或C#开发，但我决定用Swift来完成它。相同的实现在Java中完美运行，但Swift似乎不喜欢大字典。 - Scaraux

字典使用哈希进行键查找，应该提供接近 O(1)（常数时间）的性能。它不会变得“非常非常慢”。正如Palle在他的答案中建议的那样，您应该使用工具来对代码进行时间分析。 - Duncan C

我知道！但是如果有36000个文件，每个文件包含250个由10个字母组成的单词，O(1)仍然需要永远... - Scaraux

我会尝试进行性能分析。 - Scaraux

但是，你发布的代码中并没有涉及到这一点。可能是构建字典所花费的时间太长了。每个文件包含250个10个字母的单词，总共有36000个文件。 - Rakesha Shastri

Answer 1

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

• 使用可变数组作为Swift中字典值执行非常缓慢？如何优化或正确构建？
• 有关Swift语义的字典访问

问题源于在表达式self.map[term]！.append（...）中进行突变的数组是字典存储中底层数组的临时可变副本。这意味着该数组永远没有被唯一引用，因此其缓冲区始终会被重新分配。

这种情况将在Swift 5中通过非正式引入广义访问器来解决，但在此之前，一种解决方案（如上述两个Q&As中提到的）是使用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))
      }
    }

  }
  // ...
}

- Hamish

Answer 2

当您的代码运行速度过慢时，一般的方法是使用Instruments进行分析，找出哪些代码行实际上需要最长时间，并从那里入手。可能存在其他瓶颈等问题。在Xcode中直接运行应用程序也会创建一个调试版本，这会牺牲性能以获得可调试性。发布版本可能会表现更好。

此外，如果您的程序占用大量内存，系统可能会努力使此内存可用于您的应用程序。在非iOS平台上，这将导致将内存交换到磁盘上，这将显著影响应用程序的性能，因为系统无法预测将访问字典的哪些元素。

如果内存要求不是减速的原因，这里有一些我会尝试的方法：

• 如果您能够估计要插入字典的项目数量，可以使用 dictionary.reserveCapacity(numberOfItems)。随着字典的增长，它可能需要被重新调整大小，这可能需要重建哈希表，而字典类型在内部使用。这种方法也适用于数组。

• Swift提供了自动将项目分组到具有共同键的字典中的方法：Dictionary(grouping: collection, by: { item in item.property })。这种方法可能在计算上更有效，因为一切都可以一次性处理。

• 另一种方法可能是使用其他数据类型，例如树映射，这不需要频繁的重新分配。然而，Swift在标准库中没有提供这样的类型。

- Palle

Answer 3

我曾经遇到过同样的问题。当有200K条目时，速度非常慢......所以我创建了一个类并将数组放在其中......

class MyIndex
{
    var entries: [Posting]
}

var map = [String: MyIndex]()

现在似乎运行得相当快

- Paul Stevenson