数组变体
二维数组－固定尺寸的二维数组，可用于棋盘游戏。
比特集－*n** 位大小固定尺度的序列。
*固定长度数组－如果你确切的知道数据的大小，使用老式的固定长度的数组会更加高效。
*有序数组－一个永远有序的数组。
*Rootish Array Stack - 空间时间高效率的Swift数组
二维数组（Array2D）
在C和Objective-C中，您可以编写下面代码，
int cookies[9][7];
制作9x7网格的cookies。 这将创建一个包含63个元素的二维数组。 要在第3列和第6行找到cookie，您可以写：
myCookie = cookies[3][6];
这段代码在Swift中不能成立的。 要在Swift中创建一个多维数组，您可以编写：
var cookies = [[Int]]()
for _ in 1...9 {
var row = [Int]()
for _ in 1...7 {
row.append(0)
}
cookies.append(row)
}然后，要查找cookie，您可以写：
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)
}译注：这边的dim，应该是dimension（维度）的缩写。
然后，你可以这样创建数组：
var cookies = dim(9, dim(7, 0))Swift推断数组的数据类型必须是Int，因为您指定了0作为数组元素的默认值。 要使用字符串数组，您可以编写：
var cookies = dim(9, dim(7, "yum"))dim()函数可以更容易地创建更多维度的数组：
var threeDimensions = dim(2, dim(3, dim(4, 0)))以这种方式使用多维数组或多个嵌套数组的缺点是无法跟踪什么维度代表什么。
然而，您可以创建自己的类型，其作用类似于二维数组，使用起来更方便：
public struct Array2D<T> {
public let columns: Int
public let rows: Int
fileprivate var array: [T]
public init(columns: Int, rows: 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), rows:\(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), rows:\(rows))")
array[row*columns + column] = newValue
}
}
}译注：precondition(_:_:file:line:)函数类似assert，满足条件会造成程序的提前终止并抛出错误信息，详细查看官方文档。此处有来表示当下标超过范围的提示，效果如下：
Array2D是一个泛型，因此能够支持所有类型对象，而不是只能是数字
创建Array2D示例代码：
var cookies = Array2D(columns: 9, rows: 7, initialValue: 0)通过使用下标函数，您可以从数组中检索一个对象：
let myCookie = cookies[column, row]或者设置对象：
cookies[column, row] = newCookie在内部，Array2D使用单个一维数组来存储数据。 该数组中对象的索引由(row x numberOfColumns) + column给出，但作为Array2D的用户，您只需要考虑column和row，具体事件将 由Array2D完成。 这是将基本类型包装成包装类或结构中的优点。
比特集合(Bit Set)
固定大小的n个比特序列。 也称为位数组或位向量。
要存储某些内容是真还是假使用Bool类型。 每个程序员都知道......但是如果你需要记住10,000个事物是真是假呢？
你可以制作一个包含10,000个布尔值的数组，但你也可以使用10,000比特代替。 这更加紧凑，因为在64位CPU上，10,000比特正好小于160个Int。（译注：160*64=10240）
因为操纵单个比特有点棘手，所以你可以使用BitSet来隐藏棘手的工作。
代码
比特集只是数组的简单封装。 该数组不存储单个比特，而是存储称为“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)
}N是word的比特大小。 它是64，因为我们将这些比特存储在无符号64位整数列表中。 （将BitSet改为使用32位字也相当容易。）
译注： 本文的word，如果直接翻译成单词，可能会引起误解，所以就不翻译直接用word，它表示由固定数目的比特组成的部分。
如果你这样写：
var bits = BitSet(size: 140)然后BitSet分配一个由三个word组成的数组。每个word有64位，因此三个word可以容纳192比特。我们只使用140个这样的比特，所以我们浪费了一点空间（当然我们永远不会使用这一整个word）。
注意： words数组中的第一个条目是最不重要的单词，因此这些单词以小端序存储在数组中。（译注：关于小端序可查看字节顺序）查找比特
BitSet上的大多数操作都将比特的索引作为参数，因此有一种方法可以找到包含某比特的word。
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)，因为第2位在第一个字（索引0）中。 掩码为4。在二进制中，掩码如下所示：
0010000000000000000000000000000000000000000000000000000000000000那1指向该word的第二个比特。
注意： 请记住，所有内容都以小端序显示，包括比特本身。 比特0位于最左侧，比特63位于最右侧。
另一个例子：indexOf(127)返回元组(1, 9223372036854775808) （9223372036854775808 = 2^63）。 这是第二个word的最后一个比特。 掩码是：
0000000000000000000000000000000000000000000000000000000000000001请注意，掩码总是64位，因为我们一次查看一个word的数据。
设置和获取比特
现在我们知道在哪里找到比特，将其设置为1很容易：
public mutating func set(_ i: Int) {
let (j, m) = indexOf(i)
words[j] |= m
}这会查找word索引和掩码，然后在该word和掩码之间执行按位OR。 如果该位为0则变为1.如果已经设置，则它保持设置。
清除该位 - 即将其更改为0 - 同样简单：
public mutating func clear(_ i: Int) {
let (j, m) = indexOf(i)
words[j] &= ~m
}我们现在使用掩码的反转进行按位AND，而不是按位OR。 因此，如果掩码是00100000 ... 0，那么反转是11011111 ... 1。 除了我们想要设置为0的位之外，所有位都是1.由于＆的工作方式，这会使所有其他位保持不变，并且只将该位更改为0。
要查看是否设置了位，我们还使用按位AND但不反转：
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其他有趣的事情就是翻转它们。 这会将0变为1，将1变为0.这里是flip()：
public mutating func flip(_ i: Int) -> Bool {
let (j, m) = indexOf(i)
words[j] ^= m
return (words[j] & m) != 0
}这使用剩余的按位运算符“异或”来进行翻转。 该函数还返回该位的新值。
忽略未使用的比特
很多BitSet函数都很容易实现。 例如，clearAll()，它将所有位重置为0：
public mutating func clearAll() {
for i in 0..<words.count {
words[i] = 0
}
}还有setAll()来创建所有位1.然而，这必须处理一个微妙的问题。
public mutating func setAll() {
for i in 0..<words.count {
words[i] = allOnes
}
clearUnusedBits()
}首先，我们将数据复制到数组中的所有ward中。 该数组现在是：
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111但这是不正确的......因为我们不使用最后一个word的大部分，所以我们应该将这些位保留为0：
1111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111
1111111111110000000000000000000000000000000000000000000000000000我们现在只有140个一位，而不是192位。 事实上，最后一个字可能没有被完全填满，这意味着我们总是要特别对待这个最后一个字。
将那些“剩余”比特设置为0是clearUnusedBits()辅助函数的作用。 如果BitSet的大小不是N的倍数（即64），那么我们必须清除我们没有使用的比特。 如果我们不这样做，两个不同大小的BitSet之间的按位运算将出错（下面是一个例子）。
这使用了一些高级位操作，因此请仔细注意：
private func lastWordMask() -> Word {
let diff = words.count*N - size // 1
if diff > 0 {
let mask = 1 << Word(63 - diff) // 2
return mask | (mask - 1) // 3
} else {
return ~Word()
}
}
private mutating func clearUnusedBits() {
words[words.count - 1] &= lastWordMask() // 4
} 这是它的作用，分步是：
1) diff是“剩余”比特的数量。 在上面的例子中，因为3 * 64 - 140 = 52是52。
2) 创建一个全0的掩码，除了仍然有效的最高位是1.在我们的例子中，那将是：
00000000000100000000000000000000000000000000000000000000000000003) 减去1把它变成：
1111111111100000000000000000000000000000000000000000000000000000并将高位添加回来获取：
1111111111110000000000000000000000000000000000000000000000000000这个词现在有12位，因为140 - 2 * 64 = 12。
4) 最后，关闭所有高的比特。 最后一个word中的任何剩余位现在都是0。
这个重要的一个例子就是当你组合两个不同大小的BitSet时。 为了便于说明，我们采用两个8比特值之间的按位OR：
10001111 size=4
00100011 size=8第一个只使用前4位; 第二个使用8位。 第一个应该是10000000但让我们假装忘记在最后清除那些1。 然后两者之间的按位OR导致：
10001111
00100011
-------- OR
10101111这是错误的，因为这些1位中的两个不应该在这里。 正确的方法是：
10000000 unused bits set to 0 first!
00100011
-------- OR
10100011下面是|运算符的实现方式：
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
}请注意，我们|整个word，而不是单个比特。 那太慢了！ 如果左侧和右侧具有不同的位数，我们还需要做一些额外的工作：我们将两个BitSets中最大的一个复制到out变量然后将它与单词组合 来自较小的BitSet。
例子：
var a = BitSet(size: 4)
a.setAll()
a[1] = false
a[2] = false
a[3] = false
print(a)
var b = BitSet(size: 8)
b[2] = true
b[6] = true
b[7] = true
print(b)
let c = a | b
print(c) // 1010001100000000...0按位AND（＆），异或（^）和反转（~）以类似的方式实现。
计算1-bits的数目
要计算设置为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
}当你写 x & ~(x - 1) 时，它会给你一个只设置一个位的新值。 这是最低的一个。 例如，取这个8位值（再次，我用左边最低位显示这个值）：
00101101首先我们减去1得到：
11001101然后我们反转它，翻转所有比特：
00110010并与原始值按位AND：
00101101
00110010
-------- AND
00100000它们共有的唯一值是最低（或最不重要）的1位。 然后我们使用异或从原始值中删除它：
00101101
00100000
-------- XOR
00001101这是原始值，但删除了最低的1位。
我们不断重复此过程，直到该值包含全部为零。 时间复杂度是O(s)其中 s 是1位的数量。
扩展阅读
固定大小数组(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)操作 —— 数组越大，所需的时间越长。
固定大小数组是一个很好的解决方案：
您事先知道您需要的最大元素数量。 在游戏中，这可能是一次可以激活的精灵数量。 对此加以限制并非没有道理。 （对于游戏，最好事先分配你需要的所有对象。）
数组没有必要排序，即元素的顺序无关紧要。
如果数组不需要排序，则不需要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覆盖最后一个元素来清理留下的“垃圾”对象。 通常将重复的对象留在数组中并不重要，但是如果它是一个类或结构，它可能具有对其他对象的强引用，将这些对象归零是很好的做法。
有序数组(Ordered Array)
这是一个始终从低到高排序的数组。 每当您向此数组添加新元素时，它都会插入到其排序位置。
当您希望对数据进行排序并且相对较少地插入新元素时，有序数组非常有用。在这种情况下，它比排序整个数组更快。但是，如果您需要经常更改数组，则使用常规数组并手动对其进行排序可能会更快。
实现是非常基础的。 它只是Swift内置数组的包装器：
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
}
}如您所见，所有这些方法只是在内部array变量上调用相应的方法。
剩下的是insert()函数。 这是对它的初步尝试：
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
}辅助函数findInsertionPoint()只是遍历整个数组，寻找插入新元素的正确位置。
注意：array.insert(... atIndex: array.count)将新对象添加到数组的末尾，所以如果没有找到合适的插入点，我们可以简单地返回array.count作为索引。
在playground中测试：
var a = OrderedArray<Int>(array: [5, 1, 3, 9, 7, -1])
a // [-1, 1, 3, 5, 7, 9]
a.insert(4) // inserted at index 3
a // [-1, 1, 3, 4, 5, 7, 9]
a.insert(-2) // inserted at index 0
a.insert(10) // inserted at index 8
a // [-2, -1, 1, 3, 4, 5, 7, 9, 10]数组的内容将始终从低到高排序。
不幸的是，当前的findInsertionPoint()函数有点慢。 在最坏的情况下，它需要扫描整个数组。 我们可以通过使用二分搜索查找插入点来加快速度。
新的版本：
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
}与常规二分搜索的最大区别在于，当找不到值时，不会返回nil，而是返回元素本身所在的数组索引。 这就是我们插入新对象的地方。
请注意，使用二分搜索不会改变insert()的最坏情况运行时复杂性。二分搜索本身只需要O(log n)时间，但在数组中间插入一个新对象仍然需要移动内存中的所有剩余元素。 总的来说，时间复杂度仍然是O(n)。但实际上这个新版本肯定要快得多，特别是在大型数组上。
更完整的代码可以查看Ole Begemann的排序数组。 对应的文章解释了优势和权衡。
Rootish数组栈(Rootish Array Stack)
Rootish Array Stack 是一种基于有序数组的结构，可最大限度地减少浪费的空间（基于高斯求和技术）。一个Rootish Array Stack由一个数组组成，该数组保存许多固定大小数组，这些数组的大小逐渐递增。
可调整大小数组保存对块（固定大小数组）的引用。块的容量与可调整大小数组中的索引相同。块不像常规Swift数组那样可增长/缩小。相反，当达到可调整大小数组的容量时，会创建一个稍大的新块。当块被清空时，最后一个块被释放。这是对Swift数组在浪费空间方面所做的很大改进。
这边，您可以看到插入/删除操作的行为（非常类似于Swift数组处理插入/删除操作的方式）。
高斯求和技巧
著名数学家卡尔·弗里德里希·高斯最着名的传说之一，可以追溯到他上小学时。 有一天，高斯的老师要求他的班级同学求从1加100所有数字的和，老师原本认为这项任务需要足够长的时间，可以让他走出去休息一下。当年轻的高斯举手回答5050时，老师很震惊。 真快？ 老师怀疑作弊，但没有。 高斯找到了一个公式来避免手动将所有数字一个一个的相加。他的公式：
sum from 1...n = n * (n + 1) / 2为了理解这个想象中的n块，来看一个例子，假设n为5，其中x代表1个单元：
blocks: [x] [x x] [x x x] [x x x x] [x x x x x]
# of x's: 1 2 3 4 5block1有1个x，block2为2x，block3有3x，。。。
如果现在想得到所有1到n块的和，可以通过简单地一个一个相加来计算。 这没关系，但对于大量的块可能需要很长时间！ 然而，您可以将块排列为如下 半金字塔 结构：
# | blocks
--|-------------
1 | x
2 | x x
3 | x x x
4 | x x x x
5 | x x x x x
然后我们镜像 半金字塔 ，并重新排列镜像，使其与初始_半金字塔_相匹配形成一个矩形结构：
x o x o o o o o
x x o o x x o o o o
x x x o o o => x x x o o o
x x x x o o o o x x x x o o
x x x x x o o o o o x x x x x o现在我们有 n 行和 n + 1 列：5行和6列。
我们可以像计算矩形面积一样计算和！ 让我们用n表示宽度和高度：
area of a rectangle = height * width = n * (n + 1)我们只想计算x的数量，而不是o的数量。 由于x和o之间的比例为 1：1，我们可以将这个面积除以2！
area of only x = n * (n + 1) / 2瞧！ 一个超快速的方法来获取所有块元素的总和！ 该等式对于快速导出block和inner block index方程非常有用。
Get/Set
接下来，我们希望找到一种有效且准确的方法来访问随机索引处的元素。 例如，rootishArrayStack[12]指向哪个块？ 要回答这个问题，我们需要学习更多数学！
确定内部块index比较容易。 如果index在某个block中，那么：
inner block index = index - block * (block + 1) / 2确定索引指向哪个block比较困难。 请求元素的元素数量为：index + 1元素。 块0...block中的元素数是 (block + 1) * (block + 2) / 2 （上面导出的等式）。 block和index之间的关系如下：
(block + 1) * (block + 2) / 2 >= index + 1可以重写为：
(block)^2 + (3 * block) - (2 * index) >= 0使用解一元二次方程公式，可以得到：
block = (-3 ± √(9 + 8 * index)) / 2译注： 这是维基百科 一元二次方程公式，此处的index是常量。
二次方程:
求x的公式：
此处负数没有意义，所以我们采用正根。 通常，此解决方案不是整数。 然而，回到我们的不等式，我们想要最小的块，例如block => (-3 + √(9 + 8 * index)) / 2。 接下来，我们取结果的上限：
block = ⌈(-3 + √(9 + 8 * index)) / 2⌉现在我们可以弄清楚rootishArrayStack[12]指向的是什么！ 首先，让我们看看12指向哪个块：
block = ⌈(-3 + √(9 + 8 * (12))) / 2⌉
block = ⌈(-3 + √105) / 2⌉
block = ⌈(-3 + (10.246950766)) / 2⌉
block = ⌈(7.246950766) / 2⌉
block = ⌈3.623475383⌉
block = 4然后，看看在对应块中的索引：
inner block index = (12) - (4) * ((4) + 1) / 2
inner block index = (12) - (4) * (5) / 2
inner block index = (12) - 10
inner block index = 2因此，rootishArrayStack[12]指向索引为4的块和内部块索引2。
有趣的发现
使用block方程，我们可以看到blocks的数量与元素数量的平方根成正比：O(blocks) = O(√n).
实现细节
让我们从实例变量和结构声明开始：
import Darwin
public struct RootishArrayStack<T> {
fileprivate var blocks = [Array<T?>]()
fileprivate var internalCount = 0
public init() { }
var count: Int {
return internalCount
}
...
}
元素是泛型T，因此任何类型的数据都可以存储在列表中。 blocks是一个可调整大小的数组，用于保存类型为T?的固定大小数组。
固定大小数组采用类型T?的原因是，对元素的引用在删除后不会保留。例如：如果删除最后一个元素，则必须将最后一个索引设置为nil，以防止最后一个元素在内存被访问。
internalCount是一个内部可变计数器，用于跟踪元素的数量。 count是一个只读变量，它返回internalCount值。 这里引入了Darwin来提供简单的数学函数，例如ceil()和sqrt()。
结构体的capacity就是高斯求和：
var capacity: Int {
return blocks.count * (blocks.count + 1) / 2
}接下来，让我们看看我们将如何get和set元素：
fileprivate func block(fromIndex: Int) -> Int {
let block = Int(ceil((-3.0 + sqrt(9.0 + 8.0 * 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(fromIndex: index, fromBlock: block)
blocks[block][innerBlockIndex] = newValue
}
}block(fromIndex:)和 innerBlockIndex(fromIndex:, fromBlock:) 分别是我们之前导出的 block 和 inner block index 方程。 superscript（下标）让我们方便地使用用熟悉的[index:]语法对结构体进行get和set访问。 对于superscript中的get和set，我们使用相同的逻辑：
确定索引指向的块
确定内部块索引
get/set这个值
译注： 下标 (subscripts)是Swift提高的有一种便捷访问方式，在类(class)、结构体(structure)和枚举(enumeration)中都可以使用，而且可以定义多个下标，具体可查看官方手册
接下来，让我们看看我们将如何growIfNeeded()和shrinkIfNeeded()。
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)
}
}
}如果我们的数据增大或缩小，也希望我们的数据结构适应变化。就像Swift数组一样，当容量达到阈值时，我们将使用grow或shrink修改结构体的大小。 对于Rootish数组堆栈，在insert操作，如果倒数第二个块中已满就要grow；如果最后两个块为空，则shrink。
现在来到比较熟悉的Swift数组操作。
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 {
self[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
} insert(element:, atIndex:) 中，我们将index之后的所有元素向右移动1位。使用subscript方式，移动元素，为要插入的元素创建空间。
append(element:)只是非常方便的insert到最后。
对于remove(atIndex:)，我们将index之后的所有元素向左移动1位。之后将结构体中的最后一个值设置为nil。
makeNil(atIndex:)使用与subcript相同的逻辑，只是将特定索引的元素设置为nil。
性能
内部计数器跟踪结构体中的元素数量。
count在O(1)时间执行。capacity可以使用高斯求和来计算，需要O(1)时间来执行。由于
subcript[index:]使用block和inner block index方程式，可以在O(1)时间内执行，所有get和set操作都是O(1)。忽略
grow和shrink的时间成本，insert(atIndex:)和remove(atIndex:)操作会移动指定索引的所有元素，导致O(n)时间。
生长与缩小的分析
性能分析没有考虑grow和shrink的成本。 与常规的Swift数组不同，grow和shrink操作不会将所有元素复制到备份数组中。 它们只分配或释放与blocks数量成比例的数组。 blocks的数量与元素数量的平方根成比例。 增长和缩小只需要成本 O(√n)。
浪费的空间
Wasted space is how much memory with respect to the number of elements n is unused. The Rootish Array Stack never has more than 2 empty blocks and it never has less than 1 empty block. The last two blocks are proportional to the number of blocks, which is proportional to the square root of the number of elements. The number of references needed to point to each block is the same as the number of blocks. Therefore, the amount of wasted space with respect to the number of elements is O(√n).
浪费的空间是关于元素数量n的未使用的内存量。 Rootish Array Stack永远不会有超过2个空块，并且它永远不会有少于1个空块。 最后两个块与块的数量成比例，这与块的数量的平方根成比例。 指向每个块所需的引用数与块数相同。 因此，相对于元素数量的浪费空间量是 O(√n)。