代码之家 › 专栏 › 技术社区 › Scaraux

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

nsdictionary dictionary performance swift arrays

Scaraux · 技术社区 · 6 年前

我正在Swift的一个项目中工作,使用 dictionary .

这本词典是那种类型的 [String : [Posting]]

问题是,这是非常非常缓慢,因为字典越来越大。我试着换了一个 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 .

2 回复 | 直到 6 年前

Hamish 6 年前

self.map[term]!.append(...) 是字典存储中基础数组的临时可变副本。这意味着数组永远不会被唯一引用,因此总是重新分配其缓冲区。

这种情况将在swift5中通过非官方的通用访问器的引入得到解决,但在此之前,只有一种解决方案(如上述两个Q&作为)使用 Dictionary 的 subscript(_:default:)

虽然您的情况并不是一个简单的应用单一变异的情况,但是您需要某种包装函数,以便允许您对可变数组进行范围访问。

例如,这可能看起来像:

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))
      }
    }

  }
  // ...
}

Palle 6 年前

另外,如果你的程序占用了大量内存,系统可能很难将这些内存提供给你的应用程序。在非iOS平台上,这将导致将内存交换到磁盘,这将显著影响应用程序的性能,因为系统无法预料接下来将访问字典中的哪些元素。

如果内存需求不是导致速度减慢的原因,那么我可以尝试以下几种方法:

dictionary.reserveCapacity(numberOfItems) . 随着字典的增长,它可能需要调整大小,这可能需要重建哈希表,字典类型在内部使用哈希表。这种方法也适用于数组。
Swift提供了使用公共键将项目自动分组到字典中的方法: Dictionary(grouping: collection, by: { item in item.property })
另一种方法可能是使用其他数据类型,例如树映射,它不需要频繁的重新分配。然而,Swift在标准库中没有提供这样的类型。

Paul Stevenson 5 年前

我也有同样的问题。20万的参赛速度太慢了。。。所以我做了一个类,把数组放进去。。。

class MyIndex
{
    var entries: [Posting]
}

var map = [String: MyIndex]()