【译】Swift算法俱乐部-固定大小数组

苏浩瀚
2023-12-01

本文是对 Swift Algorithm Club 翻译的一篇文章。

Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。

?andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习?。当然也欢迎加⭐️,?????。

本文的翻译原文和代码可以查看?swift-algorithm-club-cn/Fixed-Size Arrays


固定大小数组(Fixed-Size Arrays)

早期的编程语言没有非常奇特的数组。 您将创建具有固定大小的数组,从那时起它将永远不会增长或缩小。 甚至C和Objective-C中的标准数组仍然是这种类型。

当您定义这样的数组时,

int myArray[10];
复制代码

编译器分配一个可以容纳40个字节的连续内存块(假设int是4个字节):

那就是你的数组。 它总是这么大。 如果你需要超过10个元素,那你就不幸了......没有空间。

要获得一个在装满时增容的数组,你需要使用动态数组对象,比如在Objective-C中的NSMutableArray或在C ++中的std::vector。当然,像Swift这样的语言,其数组本身可以根据需要增加容量。

旧式数组的一个主要缺点是它们空间需求太大或者空间不足。 如果它们太大你就会浪费内存。 并且您需要注意由于缓冲区溢出导致的安全漏洞和崩溃。 总之,固定大小数组不灵活,但不会留下错误。

也就是说,我喜欢固定大小的数组因为它们简单,快速且可预测。

以下典型的数组操作:

  • 在最后附加一个新元素
  • 在开头或中间某处插入一个新元素
  • 删除元素
  • 按索引查找元素
  • 计算数组的大小

对于固定大小的数组,只要数组尚未满,则添加很容易:

按索引查找也很简单:

这两个操作复杂度是O(1),这意味着执行它们所花费的时间与数组的大小无关。

对于可以增长的数组,关于添加:如果数组已满,则必须分配新内存并将旧内容复制到新的内存缓冲区。 平均而言,添加仍然是**O(1)**操作,但是在之后发生的事情是不太可预测的。

昂贵的操作是插入和删除。 当你在一个不在末尾的某个地方插入一个元素时,它需要将数组的其余部分往后移动一个位置。 这涉及相对昂贵的内存复制操作。 例如,在数组的中间插入值7

如果您的代码使用的索引超过了插入点,但这些索引现在引用了错误的对象。

删除需要相反的操作:

顺便说一下,对于NSMutableArray或Swift数组也是如此。 插入和删除是**O(n)**操作 —— 数组越大,所需的时间越长。

固定大小数组是一个很好的解决方案:

  1. 您事先知道您需要的最大元素数量。 在游戏中,这可能是一次可以激活的精灵数量。 对此加以限制并非没有道理。 (对于游戏,最好事先分配你需要的所有对象。)
  2. 数组没有必要排序,即元素的顺序无关紧要。

如果数组不需要排序,则不需要insertAt(index)操作。 您可以简单地将任何新元素附加到末尾,直到数组已满。

添加元素的代码变为:

func append(_ newElement: T) {
  if count < maxSize {
    array[count] = newElement
    count += 1
  }
}
复制代码

count变量跟踪数组的大小,可以认为是最后一个元素之后的索引。 这也就是您将插入新元素的索引。

确定数组中元素的数量只是读取count变量,**O(1)**操作。

删除元素的代码同样简单:

func removeAt(index: Int) {
  count -= 1
  array[index] = array[count]
}
复制代码

这会将最后一个元素复制到删除的元素的位置,然后减小数组的大小。

这就是数组不排序的原因。 为了避免昂贵的数组复制,我们只复制一个元素,但这确实改变了元素的顺序。

现在在数组中有两个元素6的副本,但之前的最后一个元素不再是活动数组的一部分。 它只是垃圾数据 —— 下次添加新元素时,这个旧的6将被覆盖。

在这两个约束条件下 —— 元素数量和不排序数组的限制 —— 固定大小的数组仍然非常适合在现代软件中使用。

这是Swift中的一个实现:

struct FixedSizeArray<T> {
  private var maxSize: Int
  private var defaultValue: T
  private var array: [T]
  private (set) var count = 0
  
  init(maxSize: Int, defaultValue: T) {
    self.maxSize = maxSize
    self.defaultValue = defaultValue
    self.array = [T](repeating: defaultValue, count: maxSize)
  }
  
  subscript(index: Int) -> T {
    assert(index >= 0)
    assert(index < count)
    return array[index]
  }
  
  mutating func append(_ newElement: T) {
    assert(count < maxSize)
    array[count] = newElement
    count += 1
  }
  
  mutating func removeAt(index: Int) -> T {
    assert(index >= 0)
    assert(index < count)
    count -= 1
    let result = array[index]
    array[index] = array[count]
    array[count] = defaultValue
    return result
  }
  
  mutating func removeAll() {
    for i in 0..<count {
      array[i] = defaultValue
    }
    count = 0
  }
}
复制代码

创建数组时,指定最大大小和默认值:

var a = FixedSizeArray(maxSize: 10, defaultValue: 0)
复制代码

注意removeAt(index: Int)用这个defaultValue覆盖最后一个元素来清理留下的“垃圾”对象。 通常将重复的对象留在数组中并不重要,但是如果它是一个类或结构,它可能具有对其他对象的强引用,将这些对象归零是很好的做法。

作者:Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron

 类似资料: