Swift数据结构自定义与优化方法
2022-07-067.7k 阅读
Swift 数据结构基础
在 Swift 中，数据结构是组织和存储数据的方式，常见的系统提供的数据结构如数组（Array）、字典（Dictionary）和集合（Set）等能满足大部分基础需求。不过，在特定场景下，自定义数据结构能带来更高效的性能和更贴合业务逻辑的实现。
结构体（Struct）
结构体是值类型，它可以包含属性和方法。当我们创建一个结构体实例时，会在栈上分配内存，并且传递时是值传递。
// 定义一个简单的结构体
struct Point {
var x: Int
var y: Int
}
// 创建结构体实例
let point = Point(x: 10, y: 20)
类（Class）
类是引用类型，实例存储在堆上，通过引用访问。类支持继承、多态等面向对象特性。
class Shape {
var name: String
init(name: String) {
self.name = name
}
func draw() {
print("Drawing \(name)")
}
}
class Circle: Shape {
var radius: Double
init(name: String, radius: Double) {
self.radius = radius
super.init(name: name)
}
override func draw() {
print("Drawing circle with radius \(radius)")
}
}
自定义数据结构的设计原则
明确目的和需求
在自定义数据结构之前，需要清楚地了解这个数据结构要解决什么问题。例如，如果要实现一个高效存储和查询学生成绩的数据结构，就需要考虑查询的方式（按学生ID，还是按科目等），以及数据的插入、删除操作频率等。
性能考量
- 时间复杂度：数据结构的各种操作（如插入、删除、查找）的时间复杂度要尽可能低。例如，使用哈希表实现的字典，查找操作平均时间复杂度为 O(1)，而线性链表的查找操作时间复杂度为 O(n)。
- 空间复杂度：要权衡数据结构所占用的内存空间。有些数据结构为了提高时间性能，可能会牺牲一定的空间，比如哈希表需要额外的空间来存储哈希值等信息。
可维护性和扩展性
自定义数据结构的代码应该易于理解和维护。合理的命名、清晰的代码结构以及适当的注释都很重要。同时，要考虑数据结构的扩展性，以便在未来业务需求变化时能够方便地进行修改和升级。
自定义栈（Stack）
栈是一种后进先出（LIFO）的数据结构，在很多算法和实际应用中都有广泛使用，比如表达式求值、深度优先搜索等。
用数组实现栈
struct Stack<T> {
private var elements: [T] = []
mutating func push(_ element: T) {
elements.append(element)
}
mutating func pop() -> T? {
return elements.popLast()
}
func peek() -> T? {
return elements.last
}
func isEmpty() -> Bool {
return elements.isEmpty
}
}
// 使用示例
var stack = Stack<Int>()
stack.push(10)
stack.push(20)
print(stack.pop()) // 输出: Optional(20)
print(stack.peek()) // 输出: Optional(10)
print(stack.isEmpty()) // 输出: false
栈的优化
- 预分配内存：如果能提前预估栈中元素的大致数量，可以在初始化时预分配数组的容量，减少动态扩容带来的性能开销。
struct Stack<T> {
private var elements: [T]
private var capacity: Int
init(capacity: Int) {
self.capacity = capacity
elements = Array<T>(repeating: <#default value#>, count: capacity)
}
mutating func push(_ element: T) {
if elements.count >= capacity {
// 处理扩容逻辑
}
elements.append(element)
}
// 其他方法类似...
}
- 减少不必要的操作：在栈的实现中，比如 pop 操作时，如果栈为空返回 nil 即可，不需要再做其他额外的复杂判断，以提高效率。
自定义队列（Queue）
队列是一种先进先出（FIFO）的数据结构，常用于任务调度、广度优先搜索等场景。
用数组实现队列
struct Queue<T> {
private var elements: [T] = []
mutating func enqueue(_ element: T) {
elements.append(element)
}
mutating func dequeue() -> T? {
guard!elements.isEmpty else {
return nil
}
return elements.removeFirst()
}
func peek() -> T? {
return elements.first
}
func isEmpty() -> Bool {
return elements.isEmpty
}
}
// 使用示例
var queue = Queue<Int>()
queue.enqueue(10)
queue.enqueue(20)
print(queue.dequeue()) // 输出: Optional(10)
print(queue.peek()) // 输出: Optional(20)
print(queue.isEmpty()) // 输出: false
用双向链表实现队列
双向链表可以更高效地实现队列的操作，特别是在频繁插入和删除元素的场景下。
class Node<T> {
var value: T
var next: Node<T>?
var previous: Node<T>?
init(value: T) {
self.value = value
}
}
class Queue<T> {
private var head: Node<T>?
private var tail: Node<T>?
func enqueue(_ element: T) {
let newNode = Node(value: element)
if tail == nil {
head = newNode
tail = newNode
} else {
tail?.next = newNode
newNode.previous = tail
tail = newNode
}
}
func dequeue() -> T? {
guard let head = head else {
return nil
}
let value = head.value
head = head.next
if head == nil {
tail = nil
} else {
head.previous = nil
}
return value
}
func peek() -> T? {
return head?.value
}
func isEmpty() -> Bool {
return head == nil
}
}
队列的优化
- 循环队列：对于基于数组实现的队列，使用循环队列可以更有效地利用数组空间，避免频繁的内存移动。当队尾指针到达数组末尾时，重新回到数组开头。
struct CircularQueue<T> {
private var elements: [T?]
private var head = 0
private var tail = 0
private var capacity: Int
init(capacity: Int) {
self.capacity = capacity
elements = Array<T?>(repeating: nil, count: capacity)
}
mutating func enqueue(_ element: T) {
if (tail + 1) % capacity == head {
// 队列已满，处理扩容或报错
}
elements[tail] = element
tail = (tail + 1) % capacity
}
mutating func dequeue() -> T? {
guard head != tail else {
return nil
}
let value = elements[head]
elements[head] = nil
head = (head + 1) % capacity
return value
}
func peek() -> T? {
guard head != tail else {
return nil
}
return elements[head]
}
func isEmpty() -> Bool {
return head == tail
}
}
- 批量操作优化：如果有批量入队或出队的需求，可以对操作进行优化，减少不必要的循环和判断。例如，可以一次入队多个元素，在入队结束后统一处理队列状态的更新。
自定义链表（Linked List）
链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的引用（单向链表）或指向前一个和下一个节点的引用（双向链表）。
单向链表
class Node<T> {
var value: T
var next: Node<T>?
init(value: T) {
self.value = value
}
}
class LinkedList<T> {
private var head: Node<T>?
func append(_ element: T) {
let newNode = Node(value: element)
if head == nil {
head = newNode
} else {
var current = head
while current?.next != nil {
current = current?.next
}
current?.next = newNode
}
}
func delete(_ element: T) {
if let head = head, head.value == element {
head = head.next
return
}
var current = head
while let node = current?.next {
if node.value == element {
current?.next = node.next
return
}
current = current?.next
}
}
func printList() {
var current = head
while let node = current {
print(node.value, terminator: " -> ")
current = node.next
}
print("nil")
}
}
// 使用示例
let list = LinkedList<Int>()
list.append(10)
list.append(20)
list.append(30)
list.printList() // 输出: 10 -> 20 -> 30 -> nil
list.delete(20)
list.printList() // 输出: 10 -> 30 -> nil
双向链表
class Node<T> {
var value: T
var next: Node<T>?
var previous: Node<T>?
init(value: T) {
self.value = value
}
}
class DoublyLinkedList<T> {
private var head: Node<T>?
private var tail: Node<T>?
func append(_ element: T) {
let newNode = Node(value: element)
if tail == nil {
head = newNode
tail = newNode
} else {
newNode.previous = tail
tail?.next = newNode
tail = newNode
}
}
func delete(_ element: T) {
if let head = head, head.value == element {
head = head.next
head?.previous = nil
return
}
var current = head
while let node = current?.next {
if node.value == element {
if node.next != nil {
node.next?.previous = node.previous
} else {
tail = node.previous
}
node.previous?.next = node.next
return
}
current = current?.next
}
}
func printList() {
var current = head
while let node = current {
print(node.value, terminator: " <-> ")
current = node.next
}
print("nil")
}
}
// 使用示例
let doublyList = DoublyLinkedList<Int>()
doublyList.append(10)
doublyList.append(20)
doublyList.append(30)
doublyList.printList() // 输出: 10 <-> 20 <-> 30 <-> nil
doublyList.delete(20)
doublyList.printList() // 输出: 10 <-> 30 <-> nil
链表的优化
- 虚拟头节点：在链表的头部添加一个虚拟节点，可以简化插入和删除操作，特别是在处理头节点的插入和删除时，不需要额外的判断。
class Node<T> {
var value: T
var next: Node<T>?
init(value: T) {
self.value = value
}
}
class LinkedList<T> {
private var dummyHead: Node<T>
init() {
dummyHead = Node(value: <#default value#>)
}
func append(_ element: T) {
let newNode = Node(value: element)
var current = dummyHead
while current.next != nil {
current = current.next!
}
current.next = newNode
}
func delete(_ element: T) {
var current = dummyHead
while let node = current.next {
if node.value == element {
current.next = node.next
return
}
current = current.next!
}
}
func printList() {
var current = dummyHead.next
while let node = current {
print(node.value, terminator: " -> ")
current = node.next
}
print("nil")
}
}
- 缓存链表长度：在链表类中维护一个属性记录链表的长度，这样在获取链表长度时可以直接返回，而不需要遍历链表，时间复杂度从 O(n) 降为 O(1)。
自定义树（Tree）
树是一种分层数据结构，常用于组织具有层次关系的数据，如文件系统目录、HTML 文档结构等。
二叉树
二叉树每个节点最多有两个子节点，分别称为左子节点和右子节点。
class TreeNode<T> {
var value: T
var left: TreeNode<T>?
var right: TreeNode<T>?
init(value: T) {
self.value = value
}
}
class BinaryTree<T> {
var root: TreeNode<T>?
func insert(_ value: T) {
let newNode = TreeNode(value: value)
if root == nil {
root = newNode
} else {
var current = root
while true {
if value < current!.value as! Comparable {
if current?.left == nil {
current?.left = newNode
break
} else {
current = current?.left
}
} else {
if current?.right == nil {
current?.right = newNode
break
} else {
current = current?.right
}
}
}
}
}
func inorderTraversal(_ node: TreeNode<T>?) {
guard let node = node else {
return
}
inorderTraversal(node.left)
print(node.value, terminator: " ")
inorderTraversal(node.right)
}
}
// 使用示例
let tree = BinaryTree<Int>()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.inorderTraversal(tree.root) // 输出: 3 5 7
二叉搜索树（BST）的优化
- 平衡二叉搜索树：普通的二叉搜索树在某些情况下（如插入的数据有序）可能会退化为链表，导致操作的时间复杂度变为 O(n)。平衡二叉搜索树（如 AVL 树、红黑树）通过自动调整树的结构，保持树的高度平衡，使得插入、删除和查找操作的时间复杂度始终保持在 O(log n)。
- 自调整：一些自调整的二叉搜索树（如伸展树），在每次访问节点后，通过旋转操作将被访问的节点调整到树的根部附近，从而提高后续对该节点及其附近节点的访问效率。
自定义哈希表（Hash Table）
哈希表是一种根据键值对进行快速查找的数据结构，通过哈希函数将键映射到一个索引位置，从而实现快速的插入、删除和查找操作。
struct HashTable<K: Hashable, V> {
private var capacity: Int
private var buckets: [[(K, V)]]
init(capacity: Int = 16) {
self.capacity = capacity
buckets = Array(repeating: [], count: capacity)
}
private func hashFunction(_ key: K) -> Int {
return abs(key.hashValue) % capacity
}
mutating func set(_ key: K, value: V) {
let index = hashFunction(key)
for (i, (k, _)) in buckets[index].enumerated() {
if k == key {
buckets[index][i].1 = value
return
}
}
buckets[index].append((key, value))
}
func get(_ key: K) -> V? {
let index = hashFunction(key)
for (k, v) in buckets[index] {
if k == key {
return v
}
}
return nil
}
}
// 使用示例
var hashTable = HashTable<String, Int>()
hashTable.set("one", value: 1)
hashTable.set("two", value: 2)
print(hashTable.get("one")) // 输出: Optional(1)
哈希表的优化
- 负载因子控制：负载因子是哈希表中已占用的桶数与总桶数的比率。当负载因子超过一定阈值（通常为 0.75）时，需要对哈希表进行扩容，重新计算所有键的哈希值并重新分配到新的桶中，以保持哈希表的性能。
struct HashTable<K: Hashable, V> {
private var capacity: Int
private var buckets: [[(K, V)]]
private var count: Int = 0
private let loadFactorThreshold: Double = 0.75
init(capacity: Int = 16) {
self.capacity = capacity
buckets = Array(repeating: [], count: capacity)
}
private func hashFunction(_ key: K) -> Int {
return abs(key.hashValue) % capacity
}
mutating func set(_ key: K, value: V) {
if Double(count + 1) / Double(capacity) >= loadFactorThreshold {
rehash()
}
let index = hashFunction(key)
for (i, (k, _)) in buckets[index].enumerated() {
if k == key {
buckets[index][i].1 = value
return
}
}
buckets[index].append((key, value))
count += 1
}
func get(_ key: K) -> V? {
let index = hashFunction(key)
for (k, v) in buckets[index] {
if k == key {
return v
}
}
return nil
}
private mutating func rehash() {
capacity *= 2
let oldBuckets = buckets
buckets = Array(repeating: [], count: capacity)
count = 0
for bucket in oldBuckets {
for (key, value) in bucket {
set(key, value: value)
}
}
}
}
- 优化哈希函数：设计一个好的哈希函数对于哈希表的性能至关重要。哈希函数应该尽可能均匀地将键映射到不同的桶中，减少哈希冲突。例如，对于字符串键，可以使用更复杂的哈希算法，如 DJB2 算法，而不是简单地使用系统默认的哈希值。
数据结构的内存管理优化
- 减少内存碎片：对于像链表这样的动态数据结构，频繁的插入和删除操作可能会导致内存碎片。可以通过内存池技术，预先分配一块较大的内存，当需要创建新节点时从内存池中获取，节点删除时将内存返回给内存池，而不是直接调用系统的内存分配和释放函数。
- 自动释放池（Autorelease Pool）：在 Swift 中，自动释放池可以帮助管理临时对象的内存。当一个对象被发送 autorelease 消息时，它会被放入最近的自动释放池中。当自动释放池被销毁时，池中的所有对象都会被释放。在处理大量临时对象的场景下，手动创建自动释放池可以及时释放内存，避免内存峰值过高。
func processLargeData() {
autoreleasepool {
for _ in 0..<1000 {
let largeObject = <#create large object#>
// 处理 largeObject
}
}
// 自动释放池销毁，其中的对象被释放
}
- 弱引用和无主引用：在类之间存在相互引用时，如果都使用强引用，会导致循环引用，使得对象无法被释放。使用弱引用（weak）或无主引用（unowned）可以打破循环引用。弱引用是一种不持有对象所有权的引用，当对象被释放时，弱引用会自动变为 nil。无主引用同样不持有对象所有权，但当对象被释放后，访问无主引用会导致运行时错误，所以无主引用适用于确定对象在其生命周期内不会被释放的场景。
class Person {
let name: String
var apartment: Apartment?
init(name: String) {
self.name = name
}
}
class Apartment {
let number: Int
weak var tenant: Person?
init(number: Int) {
self.number = number
}
}
var person: Person? = Person(name: "John")
var apartment: Apartment? = Apartment(number: 101)
person?.apartment = apartment
apartment?.tenant = person
person = nil
apartment = nil
// 此时 Person 和 Apartment 对象都可以被释放，因为没有强引用循环
数据结构的性能测试与分析
- 使用 XCTest 进行性能测试：XCTest 框架提供了方便的性能测试功能。可以编写测试用例来测量数据结构的各种操作（如插入、删除、查找）的性能。
import XCTest
class DataStructurePerformanceTests: XCTestCase {
func testStackPerformance() {
var stack = Stack<Int>()
measure {
for i in 0..<1000 {
stack.push(i)
}
for _ in 0..<1000 {
stack.pop()
}
}
}
}
- 分析工具：利用 Instruments 等分析工具，可以深入了解数据结构在运行时的性能瓶颈，如内存使用情况、CPU 占用等。通过分析工具的可视化界面，可以直观地看到哪些操作耗时较长，哪些对象占用内存较多，从而有针对性地进行优化。
在自定义 Swift 数据结构时，深入理解数据结构的本质、遵循设计原则、合理进行优化，并通过性能测试和分析不断改进，能够打造出高效、稳定且符合业务需求的数据结构。