Learning New Data Structures for iOS Developers
Mobile developers rarely encounter complex data structures in their work. As a rule, in routine tasks it is quite enough to be able to use Array
, Dictionary
And Set
.
In my experience, even with these data structures, developers have problems. Not everyone can explain why, for example, a key in a dictionary requires Hashable
protocol, but not for the value. There are also problems with assessing the complexity of operations. But that's not what we're talking about today. There are plenty of good articles about how basic data structures work.
You've probably heard of trees, graphs, linked lists Tree
, Graph
, Linked List,
but in your daily work as a mobile developer, you are unlikely to encounter them. Today I would like to tell you about rare and underestimated data structures. And most importantly, how to let them into your routine work as a programmer.
I took the open-source library from Apple as a basis swift-collectionsThe following data structures are of greatest interest to me:
Deque
Heap (Priority Queue)
OrderedSet
OrderedDictionary
Deque (Double-ended queue)
Deque
(pronounced “deck”) is a data structure that provides the ability to work with a collection of elements, to which elements can be added and removed from both the beginning and the end.
You may ask why it is needed, because it is an ordinary array Array
can do the same thing. The special feature is that deletion and insertion at the beginning and end have amortized complexity О(1)
while arrays require 0(n)
when inserting an element at the beginning.
Amortized performance (or amortized running time) is a technique in algorithm analysis that is used to estimate the average execution time of operations in a sequence, even though some operations may be significantly slower than others.
This feature can greatly improve performance when working with large collections where you need to insert and remove elements from the beginning or end frequently.
Example of using Deque
Let's say we need a class that is responsible for canceling and resuming some operations. We have several restrictions.
The number of operations that can be undone is finite.
If we cancel some operations and make new ones, then the possibility of resuming disappears
Working with the data structure itself will not differ much from an array, the interface and other properties are similar.
import Collections
final class UndoRedoService<Operation> {
private var operations: Deque<Operation> = []
private var lastOperationIndex = -1
private let capacity: Int
init(capacity: Int = 100) {
self.capacity = capacity
}
func register(_ operation: Operation) {
// Удаляем отмененные операции из очереди операций
if lastOperationIndex != operations.count - 1 && lastOperationIndex != -1 {
operations.removeLast(operations.count - lastOperationIndex - 1)
}
// Удаляем первую операцию в случае переполнения допустимого размера очереди
if operations.count > capacity {
operations.removeFirst()
}
operations.append(operation)
lastOperationIndex = operations.count - 1
}
func undo() -> Operation? {
guard !operations.isEmpty else { return nil }
let last = operations.last
lastOperationIndex -= 1
return last
}
func redo() -> Operation? {
guard lastOperationIndex != operations.count - 1 else { return nil }
lastOperationIndex += 1
let redo = operations[lastOperationIndex]
return redo
}
}
In this exampleDeque
will be the preferred choice. Adding a new operation to the queue, deleting the first operation if it overflows, or deleting several if there are canceled ones is more efficient than Array
. How much more effective can be seen on the graph:
![Adding an element to the beginning is constant time for Deque, but linear for Array. Adding an element to the beginning is constant time for Deque, but linear for Array.](https://habrastorage.org/getpro/habr/upload_files/154/112/d76/154112d76f07d8a72a5cbd2fc1cf4ad5.png)
Deque
but linear for Array
.
Hidden text
If you want to dive deeper into the features of Deque, I suggest solving the problem Circular Deck Design
Heap
Heap (in Russian-language literature you can find the name heap) – a partially ordered tree with efficient insertion and deletion operations.
Elements stored in the heap must conform to the protocol Comparable
.
public struct Heap<Element: Comparable>
Example of use with integers:
var heap = Heap([5,7,1,20,2,10,15])
print("heap.unordered: \(heap.unordered)") // heap.unordered: [1, 20, 15, 7, 2, 10, 5]
let max = heap.max
print("heap.max: \(String(describing: max))") // "heap.max: Optional(20)
let popedMax = heap.popMax()
print("heap.popMax: \(String(describing: popedMax))") // "heap.popMax: Optional(20)
let removedMax = heap.removeMax()
print("heap.removeMax(): \(String(describing: removedMax))") // "heap.removeMax(): 15
heap.insert(0)
let removedMin = heap.removeMin()
print("heap.removeMin(): \(String(describing: removedMin))") // "heap.removeMin(): 0
print("heap.unordered: \(heap.unordered)") // heap.unordered: [1, 7, 10, 5, 2]
Complexity of operations in Heap
Operation | Complexity |
---|---|
Insert |
|
Get the minimum element |
|
Get the maximum element |
|
Remove minimum element |
|
Remove maximum element |
|
Task scheduler example
Heap
can be used to solve various problems, for example:
Queue of requests to the network or database;
Multimedia processing (audio and video);
Processing notifications in order of importance.
Let's say we have some structure Task
. This could mean any type of task, a network request, a database, any heavy-duty task.
struct Task: Comparable {
enum Priority: Comparable {
case low
case medium
case high
}
let id: String
let priority: Priority
let action: () -> Void
static func < (lhs: Task, rhs: Task) -> Bool {
return lhs.priority < rhs.priority
}
static func == (lhs: Task, rhs: Task) -> Bool {
lhs.id == rhs.id && lhs.priority == rhs.priority
}
}
structure
Task
complies with protocolComparable
;Comparability is set depending on priorities (
low
,medium
,high
).
final class TaskScheduler {
private var taskQueue = Heap<Task>()
// Добавляет новую задачу в очередь
func scheduleTask(_ task: Task) {
taskQueue.insert(task)
executeNextTaskIfExist()
}
// Достает и исполняет самую приоритетную задачу, если есть в очереди
private func executeNextTaskIfExist() {
guard let task = taskQueue.popMax() else { return }
task.action()
// взять новую задачу если есть
}
}
TaskScheduler
controls the order of execution of tasks in accordance with Task.Priority
OrderedSet
OrderedSet
– powerful and comfortable hybrid Array
And Set
Collection elements must comply with the protocol Hashable
. The main difference from the usual Set
– now we can access elements by index, and the order will not be disturbed.
For myself, I found a convenient use for this collection in iOS when working with Diffable Data Source
. Usually, to work with this API, an array is used as a data source. But a situation may arise when there are duplicates in this data source. Then either we will see duplicate elements on the screen, or, even worse, a crash in case of incorrect implementation Hashable
protocol.
Example of using OrderedSet
We will use the structure as data Item
struct Item: Hashable {
let id: String
let title: String
func hash(into hasher: inout Hasher) {
hasher.combine(id)
}
static func == (lhs: Item, rhs: Item) -> Bool {
lhs.id == rhs.id
}
}
Let's say we have a screen c UITableView
And UITableViewDiffableDataSource
class DiffableViewController: UIViewController {
var tableView: UITableView!
var dataSource: UITableViewDiffableDataSource<Int, Item>!
var items = [Item]()
override func viewDidLoad() {
super.viewDidLoad()
tableView = UITableView(frame: view.bounds, style: .plain)
view.addSubview(tableView)
dataSource = UITableViewDiffableDataSource<Int, Item>(tableView: tableView) { (tableView, indexPath, item) -> UITableViewCell? in
let cell = tableView.dequeueReusableCell(withIdentifier: "cell", for: indexPath)
cell.textLabel?.text = item.title
return cell
}
tableView.register(UITableViewCell.self, forCellReuseIdentifier: "cell")
// 1
let item1 = Item(id: UUID().uuidString, title: "Item 1")
let item2 = Item(id: UUID().uuidString, title: "Item 1")
items.append(item1)
items.append(item2)
// warning: Две одинаковые строки будут отображены на экране
updateSnapshot()
// 2
let item3 = Item(id: "123456789", title: "Item 3")
let item4 = Item(id: "123456789", title: "Item 4")
items.append(item3)
items.append(item4)
// crash: Приведет к крашу, так как item3 и item4 будут иметь одинаковый хэш
updateSnapshot()
}
func updateSnapshot() {
var snapshot = NSDiffableDataSourceSnapshot<Int, Item>()
snapshot.appendSections([0])
snapshot.appendItems(items)
dataSource.apply(snapshot, animatingDifferences: true)
}
func addItem(_ newItem: Item) {
items.append(newItem)
updateSnapshot()
}
In the first case, we add two identical ones
Item
but sinceUUID
generates a different value, we will simply see two identical cells on the screen;In the second case
id
will be the same, which will cause the application to crash.Diffable Data Source
accepts only unique objects.
Keeping track of the fact that the hashes are always different can be a problem, especially if we want to tie in to the data from the backend. In this case, OrderedSet
. It will help filter out duplicates and transfer only unique values to the snapshot.
var items = OrderedSet<Item>()
...
func updateSnapshot() {
var snapshot = NSDiffableDataSourceSnapshot<Int, Item>()
snapshot.appendSections([0])
snapshot.appendItems(Array(items)) // конвертируем в массив
dataSource.apply(snapshot, animatingDifferences: true)
}
OrderedDictionary
OrderedDictionary
– an ordered collection of key-value pairs. OrderedDictionary
has properties of both a dictionary and an array.
import OrderedCollections
@frozen struct OrderedDictionary<Key: Hashable, Value>
Let's immediately look at an example of use from a real project on iOS.
Example of using OrderedDictionary
We have a structure of a certain post, for example, like in social networks:
struct Post: Codable {
let id: String
var title: String
var content: String
}
There is also API
which returns new and updated posts in the method fetchPosts
struct PostsResponse: Codable {
let newPosts: [Post]
let updatedPosts: [Post]
}
...
func fetchPosts() async throws -> PostsResponse
Manager PostManager
is responsible for adding and updating posts according to the following logic:
final class PostManager {
typealias ID = String
/// Хранит посты в заданном порядке
private var postArray: [Post] = []
/// Хранит пару id и порядковый номер поста
private var postDictionary: [ID: Int] = [:]
func addOrUpdatePosts(_ response: PostsResponse) {
// Проверяем, что таких постов еще нет и добавляем в конец
for post in response.newPosts where postDictionary[post.id] == nil {
postArray.append(post)
postDictionary[post.id] = postArray.count - 1
}
// Находим пост по id чтобы обновить его в массиве
for post in response.updatedPosts {
if let index = postDictionary[post.id] {
postArray[index] = post
}
}
}
}
Now try refactoring this code. Here comes into play OrderedDictionary
:
private var posts = OrderedDictionary<ID, InstagramPost>()
func addOrUpdatePosts(_ response: PostsResponse) {
// Если пост новый, то он добавится в конец
for post in response.newPosts {
posts[post.id] = post
}
// Если пост существует, то он обновится
for post in response.updatedPosts {
posts[post.id] = post
}
}
Usage OrderedDictionary
greatly simplifies the task, as it combines the functionality of an array and a dictionary:
Maintains the order of elements;
Ensures the uniqueness of keys;
Makes it easy to add and update items.
While using a separate array and dictionary requires additional logic and increases the chance of making a mistake.
Usage OrderedDictionary
makes the code cleaner and more maintainable.
Conclusion
The purpose of this article is to convey to the reader the benefits of efficient data structures and show how to use them in routine iOS developer tasks.
If I managed to interest you in this article, then as a bonus I suggest you sort out Trie
This is the data structure behind the question, “How does Google search work?” At my interview, it was at Google. That's what they asked me.
It is often said that algorithms and data structures are not needed, especially for mobile developers. In my opinion, the truth is somewhere in the middle. There is no point in trying to learn all possible tricky algorithms and techniques, this knowledge is unlikely to find application.
I feel that the ability to solve algorithmic problems and the ability to choose the right data structure help me write code more consciously, make fewer mistakes, see corner cases in advance and build logical chains before implementation.
Another lifehack that helps me not to give up if I can't solve a difficult problem on LeetCode is to treat it like a game of chess. Today you lose (couldn't solve the problem), but tomorrow you come with new knowledge and win. Sports interest gives energy for self-improvement.
P.S. To learn more about mobile development and life in London, visit my Telegram channel https://t.me/ios_mobile_developer