Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
Increasing Performance by Reducing Dynamic Dispatch
Swift allows a class to override methods and properties declared in its superclasses. This means that the program has to determine at runtime which method or property is being referred to and then perform an indirect call or indirect access. This technique, called dynamic dispatch, increases language expressivity at the cost of a constant amount of runtime overhead for each indirect usage. In performance sensitive code such overhead is often undesirable. This blog post showcases three ways to improve performance by eliminating such dynamism: final, private, and Whole Module Optimization.
class ParticleModel {
var point = ( 0.0, 0.0 )
var velocity = 100.0
func updatePoint(newPoint: (Double, Double), newVelocity: Double) {
point = newPoint
velocity = newVelocity
}
func update(newP: (Double, Double), newV: Double) {
updatePoint(newP, newVelocity: newV)
}
}
var p = ParticleModel()
for i in stride(from: 0.0, through: 360, by: 1.0) {
//dynamically dispatched call
p.update((i * sin(i), i), newV:i*1000)
}
As written, the compiler will emit a dynamically dispatched call to:
Call update on p.
Call updatePoint on p.
Get the property point tuple of p.
Get the property velocity of p.
The dynamic calls are necessary because a subclass of ParticleModel might override point or velocity with a computed property or override updatePoint() or update() with new implementations.
In Swift, dynamic dispatch calls are implemented by looking up a function from a method table and then performing an indirect call. This is slower than performing a direct call. Additionally, indirect calls also prevent many compiler optimizations, making the indirect call even more expensive. In performance critical code there are techniques you can use to restrict this dynamic behavior when it isn’t needed to improve performance.
Apple
Use final keyword
class ParticleModel {
final var point = ( x: 0.0, y: 0.0 )
final var velocity = 100.0
final func updatePoint(newPoint: (Double, Double), newVelocity: Double) {
point = newPoint
velocity = newVelocity
}
//This function performing a indirect call because no final keyword
func update(newP: (Double, Double), newV: Double) {
updatePoint(newP, newVelocity: newV)
}
}
/*
It is possible to mark an entire class as final by attaching the attribute to the class itself. This forbids subclassing the class, implying that all functions and properties of the class are final as well.
*/
final class ParticleModel {
var point = ( x: 0.0, y: 0.0 )
var velocity = 100.0
// ...
}
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
Life cycle
I checked what functions are called when first launches, enter background, foreground and terminated.
figure shows the state transitions for scenes. When the user or system requests a new scene for your app, UIKit creates it and puts it in the unattached state. User-requested scenes move quickly to the foreground, where they appear onscreen. A system-requested scene typically moves to the background so that it can process an event. For example, the system might launch the scene in the background to process a location event. When the user dismisses your app’s UI, UIKit moves the associated scene to the background state and eventually to the suspended state. UIKit can disconnect a background or suspended scene at any time to reclaim its resources, returning that scene to the unattached state.
When UIKit connects a scene to your app, configure your scene’s initial UI and load the data your scene needs.
Upon entering the background state, finish crucial tasks, free up as much memory as possible, and prepare for your app snapshot. See Preparing your UI to run in the background.
At scene disconnection, clean up any shared resources associated with the scene.
Creates the application object and the application delegate and sets up the event cycle.
This function instantiates the application object from the principal class and instantiates the delegate (if any) from the given class and sets the delegate for the application. It also sets up the main event loop, including the application’s run loop, and begins processing events. If the application’s Info.plist file specifies a main nib file to be loaded, by including the NSMainNibFile key and a valid nib file name for the value, this function loads that nib file.
Despite the declared return type, this function never returns.
Restoration occurs during the middle of your app’s initialization, and it proceeds only when a state restoration archive is available and your app delegate’s application(_:shouldRestoreApplicationState:) method returns true.
Some codes are sourced from Loony Corn’s Udemy Course (https://www.udemy.com/user/janani-ravi-2/). This post is for personal notes where I summarize the original contents to grasp the key concepts
What is Linked List
It is a list data structure where each element in the list holds some information and points to where the next element lies.
Linked List vs Arrays
Linked List
List sizes are unlimited, you don’t need to know up front how many elements will be added to the linked list, the size of the linked list can grow dynamically
Inserting a new element in a linked list is a very easy operation, the logical next pointers have to be reassigned but not much else needs to be done
Similarly deleting an element in a list is very easy and efficient
Random access to an element at a specific index in the linked list is not possible. The entire list up-to that element has to be traversed
Each element requires additional space to store a pointer to the next element
Cannot take advantage of spatial locality (for caching) when accessing the elements
Each element can live pretty much anywhere in memory and be pointed to
Arrays
Arrays have to be declared upfront with the number of elements it will hold, the size of array cannot be increased dynamically <- In Swift, You can increase size, You can read details at Apple Document – Growing the Size of an Array
Arrays are located in contiguous memory locations, in order to insert an element, the elements to it’s right have to move over to make room for it. It is a more heavyweight operation.
Array elements have to be moved in the case of deletion as well
Arrays provide very quick lookup for elements at specific indices, since they are in contiguous memory locations, we know exactly where in memory the element is
No extra space is required other than for the actual elements which make up the array
As elements are in contiguous memory locations access to arrays takes significant advantage of spatial locality in caches
This can be a significant performance improvement
Use Linked Lists when
You have a large number of insert or delete operations to perform
You have no idea how large your list might be
Use Array when
Read operations need to be extremely fast and you have relatively few updates to the array
class Node {
let value: Int
var next: Node?
init(value: Int, next: Node? = nil) {
self.value = value
self.next = next
}
}
let head = Node(value: 1)
let second = Node(value: 2)
let third = Node(value: 3)
let fourth = Node(value: 4)
//Make linked list
head.next = second
second.next = third
third.next = fourth
fourth.next = nil
var start: Node? = head
while start != nil {
print("\(start!.value)")
var next = start?.next
start = next
}
//Prints
1
2
3
4
Exercise 1. Get Length of a linked list
func length(of linkedList: Node?) -> Int {
var length = 0
var head = linkedList
while head != nil {
length += 1
head = head?.next
}
return length
}
length(of: head)
Exercise 2. Get the N-th element in a Linked List
func element(of linkedList: Node?, at index: Int) -> Node? {
if index < 0 {
return nil
}
var length = 0
var head = linkedList
while head != nil {
if index == length {
return head
}
length += 1
head = head?.next
}
return nil
}
// 1 -> 2 -> 3 -> 4, Index 3 is 4
element(of: head, at: 3)?.value //Prints 4, It's correct
Exercise 3. Append an element to the end of a linked list
There is 2 case you need to handle
head is null -> create a head node
there is a linked list, create a new node and append it as a last node. Don’t forget to handle last node’s next is nil
var head: Node? = Node(value: 1)
let second = Node(value: 2)
let third = Node(value: 3)
let fourth = Node(value: 4)
//Make linked list
head?.next = second
second.next = third
third.next = fourth
fourth.next = nil
func print(linkedList: Node?) {
var head = linkedList
while head != nil {
print("\(head!.value)")
head = head?.next
}
}
//To handle if linkedList is nil, and You don't want to return anything then use inout parameter.
func append(data: Int, at linkedList: inout Node?) {
if linkedList == nil {
linkedList = Node(value: data)
return
}
var head = linkedList
var lastItem: Node?
while linkedList?.next != nil {
linkedList = linkedList?.next
}
lastItem = linkedList
lastItem?.next = Node(value: data)
//Important, Reset head node
linkedList = head
}
var emptyHead: Node?
//Case 1. Empty Head
append(data: 4, at: &emptyHead)
print(emptyHead?.value)
//Case 2. 1 -> 2 -> 3 -> 4, append 5
append(data: 5, at: &head)
print(linkedList: head)
Exercise 5. Delete all the elements (All nodes should be removed from Memory)
class Node {
let value: Int
var next: Node?
init(value: Int, next: Node? = nil) {
self.value = value
self.next = next
}
deinit {
print("Node \(value) is deinit")
}
}
func removeAll(linkedList: inout Node?) {
guard linkedList != nil else {
return
}
while linkedList != nil {
print("Remove : \(linkedList!.value) Refcount: \(CFGetRetainCount(linkedList))")
var next = linkedList?.next
linkedList?.next = nil
linkedList = next
}
}
//Prints
Remove : 1 Refcount: 2
Node 1 is deinit
Remove : 2 Refcount: 3
Remove : 3 Refcount: 3
Remove : 4 Refcount: 3
What’s wrong? Only Node 1 deinit. The rest of nodes are still remaining in Memory.
To remove all nodes from Memory, We need to fix previous example of linked list.
Let’s make a linkedList function.
func linkedList(_ input: [Int]) -> Node? {
guard input.count > 0 else {
return nil
}
var head: Node? = Node(value: input.first!)
var linkedList = head
for i in 1..<input.count {
let value = input[i]
linkedList?.next = Node(value: value)
linkedList = linkedList?.next
}
return head
}
var newList = linkedList([1, 2, 3, 4])
removeAll(linkedList: &newList)
//Prints
Remove : 1 Refcount: 2
Node 1 is deinit
Remove : 2 Refcount: 2
Node 2 is deinit
Remove : 3 Refcount: 2
Node 3 is deinit
Remove : 4 Refcount: 2
Node 4 is deinit
I used a same removeAll function. I only change the linkedList by using linkedList function. This function returns linkedList and all nodes has a same reference counts.
Now You can see all nodes are completely removed from Memory.
Next example, I’ll continue use linkedList function for creating a linked list.
Exercise 6. Insert an elements at index
func print(linkedList: Node?) {
var head = linkedList
while head != nil {
print("\(head!.value)", terminator: head?.next == nil ? "" : " -> ")
head = head?.next
}
}
func insert(value: Int, at index: Int, in linkedList: inout Node?) {
guard linkedList != nil else {
return
}
var head = linkedList
//Edge case
if index == 0 {
var newHead = Node(value: value, next: linkedList)
linkedList = newHead
return
}
for i in 0..<index - 1 {
var next = linkedList?.next
linkedList = next
}
var prevItem = linkedList
var prevNextItem = prevItem?.next
prevItem?.next = Node(value: value)
prevItem?.next?.next = prevNextItem
//Pointing to head node
linkedList = head
}
var newList = linkedList([1, 2, 3, 4])
//MARK: Print All nodes
print("Current List")
print(linkedList: newList)
print("\n")
insert(value: 9, at: 2, in: &newList)
print("After insert 9 at index 2")
print(linkedList: newList)
print("\n")
insert(value: 10, at: 0, in: &newList)
print("After insert 10 at index 0")
print(linkedList: newList)
//Prints
Current List
1 -> 2 -> 3 -> 4
After insert 9 at index 2
1 -> 2 -> 9 -> 3 -> 4
After insert 10 at index 0
10 -> 1 -> 2 -> 9 -> 3 -> 4
Example 7. Insert an element at the right position in Sorted Linked List
func insert(value: Int, in sortedLinkedList: inout Node?) {
guard sortedLinkedList != nil else {
return
}
var head = sortedLinkedList
while sortedLinkedList != nil, sortedLinkedList!.value < value {
var next = sortedLinkedList?.next
if let nextValue = next?.value, nextValue > value {
break
}
else {
sortedLinkedList = sortedLinkedList?.next
}
}
var prevItem = sortedLinkedList
var prevNextItem = prevItem?.next
prevItem?.next = Node(value: value)
prevItem?.next?.next = prevNextItem
//Pointing to head node
sortedLinkedList = head
}
var newList = linkedList([1, 2, 3, 5])
//MARK: Print All nodes
print("Current List")
print(linkedList: newList)
print("\n")
insert(value: 4, in: &newList)
print("After insert 4 in sorted LinkedList")
print(linkedList: newList)
//Prints
Current List
1 -> 2 -> 3 -> 5
After insert 4 in sorted LinkedList
1 -> 2 -> 3 -> 4 -> 5
Example 8. Append one linked list to the end of another
func append(a: inout Node?, b: inout Node?) {
var mergedLinkedListHeader = a
while a?.next != nil {
a = a?.next
}
a?.next = b
a = mergedLinkedListHeader
b = mergedLinkedListHeader
}
var a = linkedList([1, 2, 3, 4])
var b = linkedList([5, 6, 7, 8])
//MARK: Print All nodes
print("A: Linked List")
print(linkedList: a)
print("\n")
print("B: Linked List")
print(linkedList: b)
print("\n")
print("A+B")
append(a: &a, b: &b)
print(linkedList: a)
print("\n")
//Prints
A: Linked List
1 -> 2 -> 3 -> 4
B: Linked List
5 -> 6 -> 7 -> 8
A+B
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
Example 9. Split one Linked List to two Linked List, find a mid point and split it!
🤔 Wait, why use 2 pointer?
Without 2 pointer, You need to get a length of linkedList first and then iterate linkedList again to split it.
func split(list: inout Node?) -> (first: Node?, seconds: Node?) {
var firstNode: Node? = list
var secondsNode: Node?
//for 1 step
var slowPointer = list
//for 2 steps
var fastPointer = list?.next
while fastPointer?.next != nil {
slowPointer = slowPointer?.next
fastPointer = fastPointer?.next?.next
}
//Split first list
secondsNode = slowPointer?.next
slowPointer?.next = nil
return (firstNode, secondsNode)
}
Test case 1. Input = [1, 2, 3, 4, 5, 6, 7, 8]
var list = linkedList([1, 2, 3, 4, 5, 6, 7, 8])
//MARK: Print All nodes
print("Linked List")
print(linkedList: list)
print("\n")
var (firstSubList, secondsSublist) = split(list: &list)
print("First Sub Linked List")
print(linkedList: firstSubList)
print("\n")
print("Seconds Sub Linked List")
print(linkedList: secondsSublist)
print("\n")
/Prints
Linked List
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
First Sub Linked List
1 -> 2 -> 3 -> 4
Seconds Sub Linked List
5 -> 6 -> 7 -> 8
Test case 2. Input = [1, 2, 3, 4, 5, 6, 7]
var list = linkedList([1, 2, 3, 4, 5, 6, 7])
//MARK: Print All nodes
print("Linked List")
print(linkedList: list)
print("\n")
var (firstSubList, secondsSublist) = split(list: &list)
print("First Sub Linked List")
print(linkedList: firstSubList)
print("\n")
print("Seconds Sub Linked List")
print(linkedList: secondsSublist)
print("\n")
//Prints
Linked List
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7
First Sub Linked List
1 -> 2 -> 3 -> 4
Seconds Sub Linked List
5 -> 6 -> 7
Example 10. Remove duplicate nodes in a sorted linked list
func removeDuplicates(linkedList: inout Node?) {
var head: Node? = linkedList
while linkedList?.next != nil {
var nextNode = linkedList?.next
//Check duplicates
if linkedList?.value == nextNode?.value {
while nextNode?.value == nextNode?.next?.value {
var tempNext = nextNode?.next
nextNode = tempNext
}
linkedList?.next = nextNode?.next
}
linkedList = linkedList?.next
}
linkedList = head
}
var list = linkedList([1, 2, 3, 3, 3, 4, 4, 5])
//MARK: Print All nodes
print("Linked List")
print(linkedList: list)
print("\n")
removeDuplicates(linkedList: &list)
print("Removed duplicates in Linked List")
print(linkedList: list)
print("\n")
Example 11. Move node from the head of one list and add to the front of another
func moveHeadToAnother(source: inout Node?, dest: inout Node?) {
var sourceHead = source
source = source?.next
var destHead = dest
sourceHead?.next = destHead
dest = sourceHead
}
var source = linkedList([1, 2, 3])
var dest = linkedList([7, 8, 9])
//MARK: Print All nodes
print("Source Linked List")
print(linkedList: source)
print("\n")
print("Destination Linked List")
print(linkedList: dest)
print("\n")
moveHeadToAnother(source: &source, dest: &dest)
print("Result: Source Linked List")
print(linkedList: source)
print("\n")
print("Result: Destination Linked List")
print(linkedList: dest)
print("\n")
//Prints
Source Linked List
1 -> 2 -> 3
Destination Linked List
7 -> 8 -> 9
Result: Source Linked List
2 -> 3
Result: Destination Linked List
1 -> 7 -> 8 -> 9
🤯 Example 12. Merge two sorted linked list and then return a new sorted linked list
func merge(a: Node?, b: Node?) -> Node? {
//Edge cases
if a == nil, b == nil {
return nil
}
if a == nil, b != nil {
return b
}
if a != nil, b == nil {
return a
}
var result: Node?
var resultHead: Node?
var headA = a
var headB = b
if headA!.value < headB!.value {
resultHead = headA
headA = headA?.next
}
else {
resultHead = headB
headB = headB?.next
}
resultHead?.next = nil
result = resultHead
while headA != nil && headB != nil {
if headA!.value < headB!.value {
result?.next = headA
headA = headA?.next
}
else {
result?.next = headB
headB = headB?.next
}
result = result?.next
}
//Add rest of nodes
var restNodes = headA ?? headB
//When one list runs out make sure the remaining elements of the other are appended to the end of the result
result?.next = restNodes
//Pointing to head
result = resultHead
return result
}
var listA = linkedList([1, 2, 5])
var listB = linkedList([1, 4, 6])
//MARK: Print All nodes
print("listA Linked List")
print(linkedList: listA)
print("\n")
print("listB Linked List")
print(linkedList: listB)
print("\n")
let mergedList = merge(a: listA, b: listB)
print("Merged Linked List")
print(linkedList: mergedList)
print("\n")
//Prints
listA Linked List
1 -> 2 -> 5
listB Linked List
1 -> 4 -> 6
Merged Linked List
1 -> 1 -> 2 -> 4 -> 5 -> 6
Example 13. Reverse a Linked List
Code
func reverseLinkedList(input: Node?) -> Node? {
//Prev will become a head of reversed linked list
var prev = input
var current = input?.next
//At this time, prev is tail node, but after while loop, It become a head node
prev?.next = nil
while current != nil {
//next node is input's next step
var next = current?.next
//It makes reversed direction
current?.next = prev
//next step for reversed linkedList
prev = current
current = next
}
return prev
}
var input = linkedList([1, 2, 5])
//MARK: Print All nodes
print("Input Linked List")
print(linkedList: input)
print("\n")
var reversedLinkedList = reverseLinkedList(input: input)
print("Reversed Linked List")
print(linkedList: reversedLinkedList)
print("\n")
//Prints
Input Linked List
1 -> 2 -> 5
Reversed Linked List
5 -> 2 -> 1
Doubly Linked List
A doubly linked list has pointers to the next element as well as pointers to the previous element.
This requires additional memory in every node to store the previous pointer.
Some codes are sourced from Loony Corn’s Udemy Course (https://www.udemy.com/user/janani-ravi-2/). This post is for personal notes where I summarize the original contents to grasp the key concepts
Tree Data Structure
class Node {
var left: Node?
var right: Node?
var value: Int
init(value: Int) {
self.value = value
}
}
//Create a Tree
let root = Node(value: 5)
root.left = Node(value: 3)
root.right = Node(value: 7)
root.right?.left = Node(value: 6)
root.right?.right = Node(value: 9)
BFS: Breadth First Search
func bfs(root: Node) {
var root = root
var queue = [Node]()
queue.append(root)
while !queue.isEmpty {
let dequeue = queue.removeFirst()
print("\(dequeue.value)", terminator: " ")
if let leftChild = dequeue.left {
queue.append(leftChild)
}
if let rightChild = dequeue.right {
queue.append(rightChild)
}
}
}
bfs(root: root)
DFS: Depth First Search
Use Recursion!
Define base case -> when the root is null
Recursion technique -> Processing can be performed
Before -> Pre-Order
In-Between or -> In-Order
After -> Post-Order
Pre-Order
Each node is processed first (PRE) before It’s right and left subtrees
In-Order
Post-Order
func dfs(root: Node?) {
//base: node is not null
guard root != nil else {
return
}
dfs(root: root?.left)
dfs(root: root?.right)
//Post-Order - print value after recursing to the left and right subtrees
print("\(root!.value)", terminator: " ")
}
dfs(root: root)
//Prints
3 6 9 7 5
Binary Search Tree
It is called an Ordered Binary Tree.
Each node in the left sub-tree of that node has a value less than or equal to the value of the node
Each node in the right sub-tree of that node has a value greater than the value of the node
Key Feature
Typically used for Fast Insertion and Fast Lookup
Fast Insertion
In a tree when a new node is added there is exactly one place that it can be
The structure of a tree depends on the order in which the nodes are added
Fast Lookup
While searching for a node in the tree there is only one place where that node can be found
You can simply follow the right or left sub-trees based on the value you want to find
Insertion
🙏 Below Images are wrong, Level 4 -> Level 3.
Let’s see step by step.
Step 1
Step 2
Step 3
Step 4
Step 5
Step 6
Step 7
Step 8 -> Finish
class Node {
var left: Node?
var right: Node?
var value: Int
init(value: Int) {
self.value = value
}
}
let root = Node(value: 8)
//Level 1
root.left = Node(value: 6)
root.right = Node(value: 14)
//Level 2
root.left?.left = Node(value: 4)
root.left?.right = Node(value: 7)
root.right?.right = Node(value: 16)
//Level 3
root.right?.right?.right = Node(value: 18)
func insertion(root: Node?, newNode: Node) -> Node? {
if root == nil {
return newNode
}
if newNode.value < root!.value {
root?.left = insertion(root: root?.left, newNode: newNode)
}
else {
root?.right = insertion(root: root?.right, newNode: newNode)
}
return root
}
insertion(root: root, newNode: Node(value: 15))
func bfs(root: Node) {
var root = root
var queue = [Node]()
queue.append(root)
while !queue.isEmpty {
let dequeue = queue.removeFirst()
print("\(dequeue.value)", terminator: " ")
if let leftChild = dequeue.left {
queue.append(leftChild)
}
if let rightChild = dequeue.right {
queue.append(rightChild)
}
}
}
bfs(root: root)
//Prints
8 6 14 4 7 16 15 18
func minimumValue(root: Node?) -> Int {
if root == nil {
return 0 //or return Int.min
}
//Left child has a minimum value
if root?.left == nil {
return root!.value
}
return minimumValue(root: root?.left)
}
minimumValue(root: root)
Exercise 2. Maximum Depth
🙏 Below Images are wrong, Level 4 -> Level 3.
func maximumDepth(root: Node?) -> Int {
if root == nil {
return 0
}
//Leaf node
if root?.left == nil, root?.right == nil {
return 0
}
//Count up when look up next level
let leftDepth = 1 + maximumDepth(root: root?.left)
let rightDepth = 1 + maximumDepth(root: root?.right)
return max(leftDepth, rightDepth)
}
maximumDepth(root: root) //Prints 3
Exercise 3. Mirror Tree
func mirror(root: Node?) {
if root == nil {
return
}
mirror(root: root?.left)
mirror(root: root?.right)
//Switch left and right child
let temp = root?.left
root?.left = root?.right
root?.right = temp
}
mirror(root: root)
🤯 Exercise 4. Create the number of structurally unique Binary Trees possible
Problem definition
Let say If you have 3 nodes, How many various binary trees you can create?
func countTrees(nodeCount: Int) -> Int {
//Base case: node 1 -> possible tree is 1, If it is zero then root node will be null
if nodeCount <= 1 {
return 1
}
var sum = 0
//Every node can be the root
for i in 1...nodeCount {
//Left and right form their own sub trees
//The nodes before it will be on the left
let leftTrees = countTrees(nodeCount: i - 1)
//THe nodes after it on the right
let rightTrees = countTrees(nodeCount: nodeCount - i)
//leftTree * rightTrees = the number of possible trees with this root
sum = sum + leftTrees * rightTrees
}
return sum
}
countTrees(nodeCount: 3) //Prints 5
Exercise 5. Print all nodes within a range in a Binary Search Tree
func printAllNodeWithin(root: Node?, range: ClosedRange<Int>) {
if root == nil {
return
}
//If the range low value is less than the current, run the operation on the left subtree
if root!.value >= range.lowerBound {
printAllNodeWithin(root: root?.left, range: range)
}
//In-Order
if range ~= root!.value {
print("\(root!.value)", terminator: " ")
}
//If the range high value is greater than the current node, run the operation on the right subtree
if root!.value < range.upperBound {
printAllNodeWithin(root: root?.right, range: range)
}
}
print("\nExercise: Print All Nodes\n")
printAllNodeWithin(root: root, range: 6...14)
//Prints
Exercise: Print All Nodes
6 7 8 14
Exercise 6. Is a Binary Tree is a Binary Search Tree?
Remind what is Binary Search Tree?
For every node in a binary search tree – The nodes with values <= node are in the left subtree and nodes with values > node are in the right sub tree
let nonBinarySearchTreeRoot = Node(value: 8)
//Level 1
nonBinarySearchTreeRoot.left = Node(value: 14)
nonBinarySearchTreeRoot.right = Node(value: 6)
//Level 2
nonBinarySearchTreeRoot.left?.left = Node(value: 4)
nonBinarySearchTreeRoot.left?.right = Node(value: 7)
nonBinarySearchTreeRoot.right?.right = Node(value: 16)
//Level 3
nonBinarySearchTreeRoot.right?.right?.right = Node(value: 18)
func isBinarySearchTree(root: Node?) -> Bool {
//Null node consider valid binary search tree
if root == nil {
return true
}
if let left = root?.left?.value, root!.value < left {
return false
}
if let right = root?.right?.value, root!.value > right {
return false
}
return isBinarySearchTree(root: root?.left) && isBinarySearchTree(root: root?.right)
}
isBinarySearchTree(root: nonBinarySearchTreeRoot) //Prints false
Exercise 7. Has Path Sum?
func hasPathSum(root: Node?, sum: Int) -> Bool {
//Check hasPathSum or not
if root?.left == nil, root?.right == nil {
return root?.value == sum
}
if root == nil {
return false
}
let subSum = sum - root!.value
if let left = root?.left {
var hasPathSum = hasPathSum(root: root?.left, sum: subSum)
if hasPathSum {
return true
}
}
if let right = root?.right {
var hasPassSum = hasPathSum(root: root?.right, sum: subSum)
if hasPassSum {
return true
}
}
return false
}
hasPathSum(root: root, sum: 21) //True
Exercise 9. Find the Least Common Ancestor for 2 nodes
Let’s check step by step.
Remember, This step is important!
Found! The lease common ancestor is 3
//It's not a Binary Search Tree
let findAncestorRoot = Node(value: 1)
//Level 1
findAncestorRoot.left = Node(value: 2)
findAncestorRoot.right = Node(value: 3)
//Level 2
findAncestorRoot.right?.left = Node(value: 7)
findAncestorRoot.right?.right = Node(value: 6)
//Level 3
findAncestorRoot.right?.left?.left = Node(value: 8)
findAncestorRoot.right?.left?.right = Node(value: 5)
findAncestorRoot.right?.right?.right = Node(value: 4)
func findLeastCommonAncestor(root: Node?, targetNodeValue1: Int, targetNodeValue2: Int) -> Int? {
if root == nil {
return nil
}
//If the current root is either of the two node then return it itself. (It will be use later)
if root!.value == targetNodeValue1 || root!.value == targetNodeValue2 {
return root!.value
}
let leftAncestor = findLeastCommonAncestor(root: root?.left, targetNodeValue1: targetNodeValue1, targetNodeValue2: targetNodeValue2)
let rightAncestor = findLeastCommonAncestor(root: root?.right, targetNodeValue1: targetNodeValue1, targetNodeValue2: targetNodeValue2)
//If both exist it means - either the node or it's ancestor exist in the left and right subtree. So current node is the least common ancestor
if let leftAncestor, let rightAncestor {
return root!.value
}
if let leftAncestor {
return leftAncestor
}
return rightAncestor
}
findLeastCommonAncestor(root: findAncestorRoot, targetNodeValue1: 8, targetNodeValue2: 6) //It is 3
Exercise 10. iOS, Find the Least Common Ancestor for 2 subview
UIView is not a binary tree. It has more 2 child views.
func createNodeView(tag: Int) -> UIView {
let view = UIView()
view.tag = tag
return view
}
//Level 0
let rootView = createNodeView(tag: 1)
//Level 1
let tag3View = createNodeView(tag: 3)
rootView.addSubview(createNodeView(tag: 2))
rootView.addSubview(tag3View)
//Level 2
let tag7View = createNodeView(tag: 7)
let tag6View = createNodeView(tag: 6)
let tag9View = createNodeView(tag: 9)
tag3View.addSubview(tag7View)
tag3View.addSubview(tag6View)
tag3View.addSubview(tag9View)
//Level 3
tag7View.addSubview(createNodeView(tag: 11))
tag6View.addSubview(createNodeView(tag: 8))
tag6View.addSubview(createNodeView(tag: 5))
tag9View.addSubview(createNodeView(tag: 4))
func findLeastCommonAncestor(root: UIView?, targetNodeValue1: Int, targetNodeValue2: Int) -> UIView? {
print("visited: \(root?.tag)")
if root == nil {
return nil
}
//If the current root is either of the two node then return it itself. (It will be use later)
if root!.tag == targetNodeValue1 || root!.tag == targetNodeValue2 {
return root
}
var ancestors = [UIView]()
for subView in root!.subviews {
if let ancestor =
findLeastCommonAncestor(root: subView, targetNodeValue1: targetNodeValue1, targetNodeValue2: targetNodeValue2) {
ancestors.append(ancestor)
}
}
print(ancestors.compactMap { $0.tag })
let tags = ancestors.compactMap { $0.tag }
//If rootView has both nodes then return it
if tags.contains(targetNodeValue1), tags.contains(targetNodeValue2) {
return root
}
if ancestors.isEmpty {
return nil
}
//Need to check whether It's okay to return last item or not..but most of cases It works correctly so far.
return ancestors.last
}
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
Archives and serializations are two ways in which you can create architecture-independent byte streams of hierarchical data. Byte streams can then be written to a file or transmitted to another process, perhaps over a network. When the byte stream is decoded, the hierarchy is regenerated. Archives provide a detailed record of a collection of interrelated objects and values. Serializations record only the simple hierarchy of property-list values
Apple
Example 1, Conforms NSCoding
class Person: NSObject, NSCoding {
var name: String
var age: Int
var friend: Person?
init(name: String, age: Int, friend: Person? = nil) {
self.name = name
self.age = age
self.friend = friend
}
required convenience init?(coder: NSCoder) {
guard let name = coder.decodeObject(forKey: "name") as? String
else {
return nil
}
let age = coder.decodeInteger(forKey: "age")
let friend = coder.decodeObject(forKey: "friend") as? Person
self.init(name: name, age: age, friend: friend)
}
func encode(with coder: NSCoder) {
coder.encode(name, forKey: "name")
coder.encode(age, forKey: "age")
coder.encode(friend, forKey: "friend")
}
}
func savePerson(_ person: Person, to path: String) {
do {
let data = try NSKeyedArchiver.archivedData(withRootObject: person, requiringSecureCoding: false)
try data.write(to: URL(fileURLWithPath: path))
print("Saved Person")
} catch {
print("Failed: \(error)")
}
}
func loadPerson(from path: String) -> Person? {
do {
let data = try Data(contentsOf: URL(fileURLWithPath: path))
//Instead unarchiveTopLevelObjectWithData You can use unarchivedObject(ofClass:from:) when you conforms NSSecureCoding protocol
if let loadedPerson = try NSKeyedUnarchiver.unarchiveTopLevelObjectWithData(data) as? Person {
return loadedPerson
}
} catch {
print("Failed: \(error)")
}
return nil
}
let friend = Person(name: "Bob", age: 35)
let person = Person(name: "Alice", age: 30, friend: friend)
let filePath = NSTemporaryDirectory() + "person_with_friend.archive"
savePerson(person, to: filePath)
if let loadedPerson = loadPerson(from: filePath) {
if let loadedFriend = loadedPerson.friend {
print("Person: \(loadedPerson.name), \(loadedPerson.age)")
print("Friend: \(loadedFriend.name), \(loadedFriend.age)")
} else {
print("No friends")
}
}
Example 2. Conforms NSSecureCoding
In example 1, You may see this warning. unarchiveTopLevelObjectWithData was deprecated. To resolve it, let’s conforms NSSecureCoding.
class Person: NSObject, NSSecureCoding {
static var supportsSecureCoding = true
var name: String
var age: Int
var friend: Person?
init(name: String, age: Int, friend: Person? = nil) {
self.name = name
self.age = age
self.friend = friend
}
required convenience init?(coder: NSCoder) {
guard let name = coder.decodeObject(forKey: "name") as? String
else {
return nil
}
let age = coder.decodeInteger(forKey: "age")
let friend = coder.decodeObject(forKey: "friend") as? Person
self.init(name: name, age: age, friend: friend)
}
func encode(with coder: NSCoder) {
coder.encode(name, forKey: "name")
coder.encode(age, forKey: "age")
coder.encode(friend, forKey: "friend")
}
}
func savePerson(_ person: Person, to path: String) {
do {
let data = try NSKeyedArchiver.archivedData(withRootObject: person, requiringSecureCoding: true)
try data.write(to: URL(fileURLWithPath: path))
print("Saved Person")
} catch {
print("Failed: \(error)")
}
}
func loadPerson(from path: String) -> Person? {
do {
let data = try Data(contentsOf: URL(fileURLWithPath: path))
if let loadedPerson = try NSKeyedUnarchiver.unarchivedObject(ofClass: Person.self, from: data) {
return loadedPerson
}
} catch {
print("Failed: \(error)")
}
return nil
}
let friend = Person(name: "Bob", age: 35)
let person = Person(name: "Alice", age: 30, friend: friend)
let filePath = NSTemporaryDirectory() + "person_with_friend.archive"
savePerson(person, to: filePath)
if let loadedPerson = loadPerson(from: filePath) {
if let loadedFriend = loadedPerson.friend {
print("Person: \(loadedPerson.name), \(loadedPerson.age)")
print("Friend: \(loadedFriend.name), \(loadedFriend.age)")
} else {
print("No friends")
}
}
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
When layoutSubViews has called?
Subclasses can override this method as needed to perform more precise layout of their subviews. You should override this method only if the autoresizing and constraint-based behaviors of the subviews do not offer the behavior you want. You can use your implementation to set the frame rectangles of your subviews directly.
You should not call this method directly. If you want to force a layout update, call the setNeedsLayout() method instead to do so prior to the next drawing update. If you want to update the layout of your views immediately, call the layoutIfNeeded() method.
Test it your self. When you call a setNeedsLayout a layoutSubviews in CustomView will be called.
viewWillLayoutSubviews and viewDidLayoutSubviews
When a view’s bounds change, the view adjusts the position of its subviews. Your view controller can override this method to make changes before the view lays out its subviews. The default implementation of this method does nothing.
When you changed a subview’s bounds, viewWillLayoutSubviews and viewDidLayoutSubviews are called. And then subview’s layoutSubviews is also called
When use Autolayout and changes NSLayoutConstraints, It also calls viewWillLayoutSubviews and viewDidLayoutSubviews
What is intrinsicContentSize?
The natural size for the receiving view, considering only properties of the view itself.
Custom views typically have content that they display of which the layout system is unaware. Setting this property allows a custom view to communicate to the layout system what size it would like to be based on its content. This intrinsic size must be independent of the content frame, because there’s no way to dynamically communicate a changed width to the layout system based on a changed height, for example.
If a custom view has no intrinsic size for a given dimension, it can use noIntrinsicMetric for that dimension.
Let’s test. UILabel has 2 constraints which are leading and top. I set font and text. As you can see It’s intrinsicContentSize is based on it’s content.
I added trailingAnchor. As you can see frame width is bigger than first one. ButintrinsicSize doesn’t changed. Because It’s based on contents. Now we know that It is independent from frame
UIImageView
An image view uses its contentMode property and the configuration of the image itself to determine how to display the image. It’s best to specify images whose dimensions match the dimensions of the image view exactly, but image views can scale your images to fit all or some of the available space. If the size of the image view itself changes, it automatically scales the image as needed.
You can create a resizable image that stretches using the resizableImage(withCapInsets:resizingMode:) method of UIImage. When using an image of this type, you typically set the image view’s content mode to UIView.ContentMode.scaleToFill so that the image stretches in the appropriate places and fills the image view’s bounds.
Image scaling and alpha blending are two relatively expensive operations that can impact your app’s performance. To maximize performance of your image view code, consider the following tips:
Cache scaled versions of frequently used images. If you expect certain large images to be displayed frequently in a scaled-down thumbnail view, consider creating the scaled-down images in advance and storing them in a thumbnail cache. Doing so alleviates the need for each image view to scale them separately.
Use images whose size is close to the size of the image view. Rather than assigning a large image to an image view, created a scaled version that matches the current size of the image view. You can also create a resizable image object using the UIImage.ResizingMode.tile option, which tiles the image instead of scaling it.
Make your image view opaque whenever possible. Unless you’re intentionally working with images that contain transparency (drawing UI elements, for example), make sure the isOpaque property of your image view is set to true. For more information about how transparency is determined, see Determine the final transparency of the image.
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts.
References
Apple official documents
Raywenderlich.com
An object that controls access to a resource across multiple execution contexts through use of a traditional counting semaphore.
A dispatch semaphore is an efficient implementation of a traditional counting semaphore. Dispatch semaphores call down to the kernel only when the calling thread needs to be blocked. If the calling semaphore does not need to block, no kernel call is made.
You increment a semaphore count by calling the signal()method, and decrement a semaphore count by calling wait() or one of its variants that specifies a timeout.
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
🔥 Apple documents about Dynamic and Static library was written for OSX Application.
Two important factors that determine the performance of apps are their launch times and their memory footprints. Reducing the size of an app’s executable file and minimizing its use of memory once it’s launched make the app launch faster and use less memory once it’s launched. Using dynamic libraries instead of static libraries reduces the executable file size of an app. They also allow apps to delay loading libraries with special functionality only when they’re needed instead of at launch time. This feature contributes further to reduced launch times and efficient memory use.
This article introduces dynamic libraries and shows how using dynamic libraries instead of static libraries reduces both the file size and initial memory footprint of the apps that use them. This article also provides an overview of the dynamic loader compatibility functions apps use to work with dynamic libraries at runtime.
Most of an app’s functionality is implemented in libraries of executable code. When an app is linked with a library using a static linker, the code that the app uses is copied to the generated executable file. A static linker collects compiled source code, known as object code, and library code into one executable file that is loaded into memory in its entirety at runtime. The kind of library that becomes part of an app’s executable file is known as a static library. Static libraries are collections or archives of object files.
Note: Static libraries are also known as static archive libraries and static linked shared libraries.
When an app is launched, the app’s code—which includes the code of the static libraries it was linked with—is loaded into the app’s address space. Linking many static libraries into an app produces large app executable files. Figure 1 shows the memory usage of an app that uses functionality implemented in static libraries. Applications with large executables suffer from slow launch times and large memory footprints. Also, when a static library is updated, its client apps don’t benefit from the improvements made to it. To gain access to the improved functionality, the app’s developer must link the app’s object files with the new version of the library. And the apps users would have to replace their copy of the app with the latest version. Therefore, keeping an app up to date with the latest functionality provided by static libraries requires disruptive work by both developers and end users.
Apple
When you create a module using SPM, It is a static library.
Dynamic Library
A better approach is for an app to load code into its address space when it’s actually needed, either at launch time or at runtime. The type of library that provides this flexibility is called dynamic library. Dynamic libraries are not statically linked into client apps; they don’t become part of the executable file. Instead, dynamic libraries can be loaded (and linked) into an app either when the app is launched or as it runs.
Using dynamic libraries, programs can benefit from improvements to the libraries they use automatically because their link to the libraries is dynamic, not static. That is, the functionality of the client apps can be improved and extended without requiring app developers to recompile the apps. Apps written for OS X benefit from this feature because all system libraries in OS X are dynamic libraries. This is how apps that use Carbon or Cocoa technologies benefit from improvements to OS X.
Another benefit dynamic libraries offer is that they can be initialized when they are loaded and can perform clean-up tasks when the client app terminates normally. Static libraries don’t have this feature. For details, see Module Initializers and Finalizers.
Apple
Reduce dependencies on external frameworks and dynamic libraries
Before any of your code runs, the system must find and load your app’s executable and any libraries on which it depends.
The dynamic loader (dyld) loads the app’s executable file, and examines the Mach load commands in the executable to find frameworks and dynamic libraries that the app needs. It then loads each of the frameworks into memory, and resolves dynamic symbols in the executable to point to the appropriate addresses in the dynamic libraries.
Each additional third-party framework that your app loads adds to the launch time. Although dyld caches a lot of this work in a launch closure when the user installs the app, the size of the launch closure and the amount of work done after loading it still depend on the number and sizes of the libraries loaded. You can reduce your app’s launch time by limiting the number of 3rd party frameworks you embed. Frameworks that you import or add to your app’s Linked Frameworks and Libraries setting in the Target editor in Xcode count toward this number. Built-in frameworks, like CoreFoundation, have a much lower impact on launch, because they use shared memory with other processes that use the same framework.
Some codes and contents are sourced from Apple’s official documentation. This post is for personal notes where I summarize the original contents to grasp the key concepts
Property Wrappers
A property wrapper adds a layer of separation between code that manages how a property is stored and the code that defines a property. For example, if you have properties that provide thread-safety checks or store their underlying data in a database, you have to write that code on every property. When you use a property wrapper, you write the management code once when you define the wrapper, and then reuse that management code by applying it to multiple properties.
When you apply a wrapper to a property, the compiler synthesizes code that provides storage for the wrapper and code that provides access to the property through the wrapper. (The property wrapper is responsible for storing the wrapped value, so there’s no synthesized code for that.)
struct SmallRectangle {
private var _height = TwelveOrLess()
private var _width = TwelveOrLess()
var height: Int {
get { return _height.wrappedValue }
set { _height.wrappedValue = newValue }
}
var width: Int {
get { return _width.wrappedValue }
set { _width.wrappedValue = newValue }
}
}
projected Value
The name of the projected value is the same as the wrapped value, except it begins with a dollar sign ($)
Apple
@propertyWrapper
struct TwelveOrLess {
private var number = 0
private(set) var projectedValue = true
var wrappedValue: Int {
get { return number }
set {
number = min(newValue, 12)
projectedValue = number == 0
}
}
init() {
self.number = 0
self.projectedValue = true
}
}
struct Number {
@TwelveOrLess var lessNumber
}
var number = Number()
number.lessNumber = 10
number.$lessNumber
Projected Value, property name should be projectedValue
And Compiler doesn’t allow to mutating the projectedValue from the others. So Access control for it, setting the private(set) var is make sense.
You must be logged in to post a comment.