Swift Dictionary:消除时间复杂度 [英] Swift Dictionary: remove time complexity

问题描述

如官方

解决方案

removeValue的源码为:

let (bucket, found) = asNative.find(key)守卫发现其他{返回零}让 isUnique = isUniquelyReferenced()return asNative.uncheckedRemove(at: bucket, isUnique: isUnique).value

虽然 uncheckedRemove 的代码是:

_internalInvariant(hashTable.isOccupied(bucket))let rehashed = ensureUnique(isUnique: isUnique, capacity: capacity)_internalInvariant(!rehashed)让 oldKey = (_keys + bucket.offset).move()让 oldValue = (_values + bucket.offset).move()_delete(at: 桶)返回(旧键，旧值)

endureUnique 定义为:

if _fastPath(capacity <= self.capacity && isUnique) {返回假}如果是唯一的{调整大小(容量:容量)返回真}如果容量 <= self.容量 {复制()返回假}copyAndResize(容量:容量)返回真

虽然大多数操作将在 O(1) 上运行，但 ensureUnique 函数可能有 O(n)，如果项目不是唯一的，hashmap 将执行 copy()，这花费 O(n) 时间复杂度.

As stated by the official website, removing by key from a dictionary (or map, in other languages) is O(n) in Swift, making it a decently inefficient operation.

Why isn't it O(1) if put() and get() should be O(1) based on hashing?

解决方案

The source code of removeValue is:

let (bucket, found) = asNative.find(key)
guard found else { return nil }
let isUnique = isUniquelyReferenced()
return asNative.uncheckedRemove(at: bucket, isUnique: isUnique).value

While the uncheckedRemove's code is:

_internalInvariant(hashTable.isOccupied(bucket))
let rehashed = ensureUnique(isUnique: isUnique, capacity: capacity)
_internalInvariant(!rehashed)
let oldKey = (_keys + bucket.offset).move()
let oldValue = (_values + bucket.offset).move()
_delete(at: bucket)
return (oldKey, oldValue)

And the endureUnique is defined as:

if _fastPath(capacity <= self.capacity && isUnique) {
  return false
}
if isUnique {
  resize(capacity: capacity)
  return true
}
if capacity <= self.capacity {
  copy()
  return false
}
copyAndResize(capacity: capacity)
return true

While most operation will be run on O(1), the ensureUnique func may have O(n), if the item is not unique, the hashmap will do a copy(), which spends O(n) time complexity.

这篇关于Swift Dictionary:消除时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！