《swift-algorithm-club》——数据结构/变体数组

变体数组(Variations on arrays)

二维数组

在C和Objective-C中，我们可以这样创建二维数组

int cookies[9][7];
myCookie = cookies[3][6];
复制代码

在Swift中，可以这样

var cookies = [[Int]]()
for _ in 1...9 {
  var row = [Int]()
  for _ in 1...7 {
    row.append(0)
  }
  cookies.append(row)
}

let myCookie = cookies[3][6]
复制代码

或者这样

var cookies = [[Int]](repeating: [Int](repeating: 0, count: 7), count: 9)
复制代码

我们可以用辅助函数来简化它：

func dim<T>(_ count: Int, _ value: T) -> [T] {
  return [T](repeating: value, count: count)
}
复制代码

然后我们就可以这样创建数组：

var cookies = dim(9, dim(7, 0))
复制代码

以这种方式使用多维数组或多个嵌套数组的缺点是无法跟踪什么纬度代表什么。

我们可以创建自己的类型

public struct Array2D<T> {
  public let columns: Int
  public let rows: Int
  fileprivate var array: [T]
  
  public init(columns: Int, row: Int, initialValue: T) {
    self.columns = columns
    self.rows = rows
    array = .init(repeating: initialValue, count: rows*columns)
  }
  
  public subscript(column: Int, row: Int) -> T {
    get {
      precondition(column < columns, "Column \(column) Index is out of range. Array<T>(columns: \(columns), rows: \(rows))")
      precondition(row < rows, "Row \(row) Index is out of range. Array<T>(columns: \(columns), row: \(rows)")
      return array[row*columns + column]
    }
    set {
      precondition(column < columns, "Column \(column) Index is out of range. Array<T>(columns: \(columns), rows: \(rows))")
      precondition(row < rows, "Row \(row) Index is out of range. Array<T>(columns: \(columns), row: \(rows)")
      array[row*columns + column] = newValue
    }
  }
}
复制代码

然后就可以这样使用了

var cookies = Array2D(columns: 9, rows: 7, initialValue: 0)

let myCookie = cookies[column, row]

cookies[colimn, row] = newCookie
复制代码

比特集

固定大小的n个比特序列。也成为位数组或位向量。

比特集只是数组的简单封装。该数组不存储单个比特，而是存储被称为words的较大整数。BitSet的主要工作是将比特映射到正确的word。

public struct BitSet {
  private(set) public var size: Int
  
  private let N = 64
  public typealias Word = UInt64
  fileprivate(set) public var words: [Word]
  
  public init(size: Int) {
    precondition(size > 0)
    self.size = size
    
    // Round up the count to the next multiple of 64.
    let n = (size + (N-1)) / N
    words = [Word](repeating: 0, count: n)
  }
}
复制代码

查找比特

private func indexOf(_ i: Int) -> (Int, Word) {
  precondition(i >= 0)
  precondition(i < size)
  let o = i / N
  let m = Word(i - o*N)
  return (o, 1 << m)
}
复制代码

indexOf()函数返回word的数组索引，以及一个“掩码”，它显示该比特在该word内的确切位置。

栗子：

indexOf(2) 返回元组 (0,4)

0010000000000000000000000000000000000000000000000000000000000000
复制代码

indexOf(127) 返回元组 (1, 9223372036854775808)

0000000000000000000000000000000000000000000000000000000000000001
复制代码

设置和获取比特

public mutating func set(_ i: Int) {
  let (j, m) = indexOf(i)
  words[j] |= m
}
复制代码

public mutating func clear(_ i: Int) {
  let (j, m) = indexOf(i)
  words[j] &= ~m
}
复制代码

public func isSet(_ i: Int) -> Bool {
  let (j, m) = indexOf(i)
  return (words[j] & m) != 0
}
复制代码

添加一个下标函数，使这一切可以表达得更加自然

public subscript(i: Int) -> Bool {
  get { return isSet(i) }
  set { if newValue { set (i) } else { clear(i) } }
}
复制代码

现在，我们可以这样写了：

var bits = BitSet(size: 140)
bits[2] = true
bits[99] = true
bits[128] = true
print(bits)
复制代码

这将打印140位BitSet用于存储所有内容的三个单词：

0010000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000010000000000000000000000000000
1000000000000000000000000000000000000000000000000000000000000000
复制代码

翻转

public mutating func flip(_ i: Int) -> Bool {
  let (j, m) = indexOf(i)
  words[j] ^= m
  return (words[j] & m) != 0
}
复制代码

public mutating func clearAll() {
  for i in 0..<words.count {
    words[i] = 0
  }
}
复制代码

public mutating func setAll() {
  for i in 0..<words.count {
    words[i] = allOnes
  }
  clearUnusedBits()
}
复制代码

注意：setAll 方法，我们并没有使用最后一个word的全部部分，我们应该将未使用的部分保留为0。

private func lastWordMask() -> Word {
  let diff = words.count*N - size
  if diff > 0 {
    let mask = 1 << Word(63 - diff)
    return mask | (mask - 1)
  } else {
    return ~Word()
  }
}

private mutating func clearUnuesdBits() {
  words[words.count - 1] &= lastWordMask()
}
复制代码

下面是 | 运算符的实现方式：

public func |(lhs: BitSet, rhs: BitSet) -> BitSet {
  var out = copyLargest(lhs, rhs)
  let n = min(lhs.words.count, rhs.words.count)
  for i in 0..<n {
    out.words[i] = lhs.words[i] | rhs.words[i]
  }
  return out
}
复制代码

计算设置为1的位数，扫描整个数组是可以的——O(n)操作——但是更聪明的方法：

public var cardinality: Int {
  var count = 0
  for var x in words {
    while x != 0 {
      let y = x & ~(x - 1)    // find lowest 1-bit
      x = x ^ y               // and erase it
      ++count
    }
  }
  return count
}
复制代码

固定大小数组

假定两个约束条件——元素数量受限&&数组不排序

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)
  }
  
  subecript(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
  }
}
复制代码

有序数组

当您希望对数据进行排序并且相对较少地插入新元素时，有序数组非常有用。在这种情况下，它比排序整个数组更快。

public struct OrderedArray<T: Comparable> {
  fileprivate var array = [T]()
  
  public init(array: [T]) {
    self.array = array.sorted()
  }
  
  public var isEmpty: Bool {
    return array.isEmpty
  }
  
  public var count: Int {
    return array.count
  }
  
  public subscript(index: Int) -> T {
    return array[index]
  }
  
  public mutating func removeAtIndex(index: Int) -> T {
    return array.remove(at: index)
  }
  
  public mutating func removeAll() {
    array.removeAll()
  }
  
  extension OrderedArray: CustomStringConvertible {
    public var description: String {
      return array.description
    }
  }
}
复制代码

public mutating func insert(_ newElement: T) -> Int {
  let i = findInsertionPoint(newElement)
  array.insert(newElement, at: i)
  return i
}

private func findInsertionPoint(_ newElement: T) -> Int {
  for i in 0..<array.count {
    if newElement <= array[i] {
      return i
    }
  }
  return array.count    // insert at the end
}
复制代码

二分搜索版本辅助函数

private func findInsertionPoint(_ newElement: T) -> Int {
  var startIndex = 0
  var endIndex = array.count
  
  while startIndex < endIndex {
    let midIndex = startIndex + (endIndex - startIndex) / 2
    if array[midIndex] == newElement {
      return midIndex
    } else if array[midIndex] < newElement {
      startIndex = midIndex + 1
    } else {
      endIndex = midIndex
    }
  }
  return startIndex
}
复制代码

Rootish Array Stack

Rootish Array Stack是一种基于有序数组的结构，可最大限度地减少浪费的空间 ( 基于高斯求和 )

高斯求和公式

sum from 1...n = n * (n + 1) / 2
复制代码

import Darwin

public struct RootishArrayStack<T> {
  fileprivate var blocks = [Array<T?>]()
  fileprivate var internalCount = 0
  
  public init() { }
  
  var count: Int {
    return internalCount
  }
  
  ...
}
复制代码

var capacity: Int {
  return blocks.count * (blocks.count + 1) / 2
}
复制代码

fileprivate func block(fromIndex: Int) -> Int {
  let block = Int(ceil((-3.0) + sqrt(9.0 + 8 * Double(index))) / 2)) // 一元二次方程求解公式
	return block
}

fileprivate func innerBlockIndex(fromIndex index: Int, fromBlock block: Int) -> Int {
  return index - block * (block + 1) / 2
}

public subscript(index: Int) -> T {
  get {
    let block = self.block(fromIndex: index)
    let innerBlockIndex = self.innerBlockIndex(fromIndex: index, fromBlock: block)
    return blocks[block][innerBlockIndex]!
  }
  set(newValue) {
    let block = self.block(fromIndex: index)
    let innerBlockIndex = self.innerBlockIndex(formIndex: index, fromBlock: block)
    blocks[block][innerBlockIndex] = newValue
  }
}
复制代码

fileprivate mutating func growIfNeeded() {
  if capacity - blocks.count < count + 1 {
    let newArray = [T?](repeating: nil, count: blocks.count + 1)
    blocks.append(newArray)
  }
}

fileprivate mutating func shrinkIfNeeded() {
  if capacity + blocks.count >= count {
    while blocks.count > 0 && (blocks.count - 2) * (blocks.count - 1) / 2 > count {
      blocks.remove(at: blocks.count - 1)
    }
  }
}
复制代码

public mutating func insert(element: T, atIndex index: Int) {
  growIfNeeded()
  internalCount += 1
  var i = count - 1
  while i > index {
    self[i] = self[i - 1]
    i -= 1
  }
  self[index] = element
}

public mutating func append(element: T) {
  insert(element: element, atIndex: count)
}

public mutating func remove(atIndex index: Int) -> T {
  let element = self[index]
  for i in index..<count - 1 {
    slef[i] = self[i + 1]
  }
	internalCount -= 1
  makeNil(atIndex: count)
  shrinkIfNeeded()
  return element
}

fileprivate mutating func makeNil(atIndex index: Int) {
  let block = self.block(fromIndex: Index)
  let innerBlockIndex = self.innerBlockIndex(fromIndex: index, fromBlock: block)
  blocks[block][innerBlockIndex] = nil
}
复制代码