Queue Optimized - dequeu is not O(1)
chipbk10 opened this issue · 11 comments
Brief Intro
Queue Optimized - dequeue is not O(1)
More Details
if array.count > 50 && percentage > 0.25 {
array.removeFirst(head)
head = 0
}
If the condition happens, the complexity will be O(n/4) ~ O(n)
I think you should use LinkedList to implement a Queue to archive O(1) in all cases of dequeue
The text says that it's O(1) on average, or "O(1) amortized". Same as appending to an array. When it happens it's slow but it only happens rarely, so it doesn't matter. (Unless you need a guarantee that it's "never slower than X", which this doesn't give.)
"Same as appending to an array" is not correct. Appending element in array in Swift is always O(1). Do you think in Java or Python, they have the same implementation like we do here for the Queue?
Appending an element to a Swift array is also O(1) amortized, which is not the same as O(1).
Just to make it clear: this Queue implementation does not mean to be optimal. It just shows one way that dequeuing can be made faster. Using a linked list would give O(1) dequeuing indeed but comes with other trade-offs.
Can you please tell me what is the other trade-offs if we use LinkedList?
The advantage of using an array as the backing store for the queue is that this is a contiguous area of memory. That means it's really easy to iterate through the queue (just increment or decrement the index). It also helps with efficient cache access. With a linked list, the nodes are connected with pointers so it's slower to go from one node to the next, plus the nodes could be located anywhere in memory, which is worse for the cache.
You are right about appending an element to a Swift array is also O(1) amortized. Thanks for that.
https://developer.apple.com/documentation/swift/array/3126937-append
The trade-off to use LinkedList here is the memory cost. It will cost more memory than using an array, because, each node in LinkedList holds data and reference to next. Meanwhile, an array holds only actual data and its index.
Thank you for the discussion.
You are right about appending an element to a Swift array is also O(1) amortized. Thanks for that.
https://developer.apple.com/documentation/swift/array/3126937-append
The trade-off to use
LinkedListhere is the memory cost. It will cost more memory than using an array, because, each node in LinkedList holds data and reference to next. Meanwhile, an array holds only actual data and its index.Thank you for the discussion.
Memory + the fact that reference types are always stored in the heap. This means every modification to the linked list (such as appending / removing a node) would require a locking operation on the heap. That has a cost to performance - whereas simple values in a Swift array can sit in the stack - which doesn't require a lock
I don't think that appending / removing nodes uses any kind of lock, plus there is no guarantee that a Swift array will be stored on the stack. (Allocating new nodes, however, might require a lock.)
Hmm, I was under the assumption that if the array housed "simple" types (i.e. [Int]), then it could be guaranteed in the stack.