I need help in understanding the difference of function 'mirror' and how it is superior in listing 19.10 where it is stated that by adding side effects of having a mutable list, wasteful copying is avoided by performing at most one trailing to leading adjustment for any sequence of head operations.
excerpt from listing 19.1
def mirror = if (leading.isEmpty) new QueueImpl(trailing.reverse, Nil) else this
excerpt from listing 19.10
private def mirror() = if (leading.isEmpty) { while (!trailing.isEmpty) { leading = trailing.head :: leading trailing = trailing.tail } }
In both cases, when leadning.isEmpty is true and there is a sequence of head operations, reversing as in 19.1 as well as 'while' as in 19.10 both have linear complexity on number of elements in trailing list.
For me in both the cases, it appears that trailing adjustment will actually happen every time if the leading is empty and there is a sequence of consecutive head operations.
Even after thinking a lot, I am missing something to actually see the reason for how side effecting Queue is better.
Hi, I tried to figure out some example to see why the mutable version can be more efficient. Note however that the mutable version (from listing 19.10) is not thread safe.
// A) Immutable version
// Create a queue with an empty leading list
val immuQueue = Queue().enqueue(1).enqueue(2).enqueue(3)
// Calling head twice on the same instance causes reversing the trailing list twice
immuQueue.head
immuQueue.head
// B) Mutable version
val mutaQueue = Queue().enqueue(1).enqueue(2).enqueue(3)
// Calling head twice reverses the trailing list only once
// (because the first call rearranges internal structure of the queue)
mutaQueue.head
mutaQueue.head
Previous Topic
