Hi Guys,
I was going through Operation.swift's code and I noticed an opportunity to improve the time complexity of operations like dequeue and remove.
The current implementation of OperationQueue uses an internal struct called _OperationList which contains 6 arrays of operations,
struct _OperationList {
var veryLow = [Operation]()
var low = [Operation]()
var normal = [Operation]()
var high = [Operation]()
var veryHigh = [Operation]()
var all = [Operation]()
}
When an operation is cancelled or finished, OperationQueue is calling _OperatonList.removing(_:Operation) method and when an operation is dequeued _OperationList.dequeue() is calling.
Now, given the nature of OperationQueue, which frequently adds, dequeues and removes operations from the queue, the program end up running at 0(n) runtime, for search and delete, as the operations are performed on Array data structure.
Im thinking this O(n) time can be reduced down to O(1) if we use LinkedList and HashTable together.
Heres the updated interface,
Double Linked List
internal class _IndexedOperationLinkedList {
internal class Node {
var operation: Operation
var next: _IndexedOperationLinkedList.Node? = nil
var previous: _IndexedOperationLinkedList.Node? = nil
}
private(set) var root: _IndexedOperationLinkedList.Node? = nil
private(set) weak var tail: _IndexedOperationLinkedList.Node? = nil
private(set) var count: Int = 0
private var nodeForOperation: [Operation: _IndexedOperationLinkedList.Node] = [:]
func insert(_ operation: Operation) { }
func remove(_ operation: Operation) { }
func removeFirst() -> Operation? { }
func map<T>(_ transform: (Operation) throws -> T) rethrows -> [T] { }
}
_OperationList
internal struct _OperationList {
var veryLow = _IndexedOperationLinkedList()
var low = _IndexedOperationLinkedList()
var normal = _IndexedOperationLinkedList()
var high = _IndexedOperationLinkedList()
var veryHigh = _IndexedOperationLinkedList()
var all = _IndexedOperationLinkedList()
mutating func insert(_ operation: Operation) {
all.insert(operation)
switch operation.queuePriority {
case .veryLow:
veryLow.insert(operation)
case .low:
low.insert(operation)
case .normal:
normal.insert(operation)
case .high:
high.insert(operation)
case .veryHigh:
veryHigh.insert(operation)
}
}
mutating func remove(_ operation: Operation) {
all.remove(operation)
switch operation.queuePriority {
case .veryLow:
veryLow.remove(operation)
case .low:
low.remove(operation)
case .normal:
normal.remove(operation)
case .high:
high.remove(operation)
case .veryHigh:
veryHigh.remove(operation)
}
}
mutating func dequeue() -> Operation? {
if let operation = veryHigh.removeFirst() {
return operation
}
if let operation = high.removeFirst() {
return operation
}
if let operation = normal.removeFirst() {
return operation
}
if let operation = low.removeFirst() {
return operation
}
if let operation = veryLow.removeFirst() {
return operation
}
return nil
}
func map<T>(_ transform: (Operation) throws -> T) rethrows -> [T] {
return try all.map(transform)
}
}
Please give me your suggestions.