Edit on GitHub

Queues

Unlike lists, queues iterate in first-in, last-out order. They implement the following efficiently:

  • push (to push to the end, analogous to Base.push! – kinda wish they had called this pushlast! but alas)
  • first
  • popfirst

You can use any existing list implementation as a Queue, using the Batched.@deque functor. However, the resulting queue achieves amortized constant complexity guarantees by batching expensive rebalancing operations: most operations are fast, but occasionally an operation takes $\mathcal{O}(n)$ time, and we refer to those as expensive operations. In amortized mutable data structures, expensive operations restore internal balance, which guarantees you a budget of cheap operations before the next rebalancing is required. An expensive operation on an immutable data structure returns a new, balanced data structure, and once again if you restrict your usage to this new value then the amortized analysis that we used in the immutable case still applies. But unlike a mutable data structure, a given instance of an immutable data structure may have multiple logical futures – after calling an expensive operation, we can go back to the same imbalanced data structure and call an expensive operation again, without having first benefitted from all the cheap operations in between. The concept is explored in Chapter 6 ($\S{6.1}$) of Purely Functional Data Structures, which introduces the use of lazy evaluation in restoring amortized bounds in persistent settings.

Use the following queue types if your use-case involves utilizing multiple logical futures (example: concurrency/multi-threading):

Bootstrapped.Queue $\S{10.1.3}$

PureFun.Bootstrapped.Queue — Type
Bootstrapped.Queue{T}()
Bootstrapped.Queue(iter)

first takes $\mathcal{O}(1)$ time, while both push and popfirst take $\mathcal{O}(\log^{*}{n})$ amortized time, where $\log^{*}$ is the iterated logarithm, which is "constant in practice." The amortized bounds extend to settings that require persistence, this is achieved via disciplined use of lazy evaluation along with memoization

Examples

julia> using PureFun, PureFun.Bootstrapped
julia> q = Bootstrapped.Queue(1:3)
3-element PureFun.Bootstrapped.NonEmpty{Int64}
1
2
3

julia> push(q, 4)
4-element PureFun.Bootstrapped.NonEmpty{Int64}
1
2
3
4

julia> popfirst(q)
2-element PureFun.Bootstrapped.NonEmpty{Int64}
2
3
source

RealTime.Queue $\S{7.2}$

PureFun.RealTime.Queue — Type
RealTime.Queue{T}()
RealTime.Queue(iter)

All operations are worst-case $\mathcal{O}(1)$. These queues make heavy use of lazy evaluation. Due to the overheads associated with lazy evaluation, the PureFun.RealTime.Queue is slower on average than others, but can still be useful in settings (such as interactive user-interfaces) where bounded worst-case performance is more important than average performance.

source

HoodMelville.Queue $\S{8.2.1}$

PureFun.HoodMelville.Queue — Type
HoodMelville.Queue{T}()
HoodMelville.Queue(iter)

HoodMelville.Queues require worst-case constant time for all 3 queue operations. Unlike the PureFun.RealTime.Queue, the Hood-Melville queue does not use lazy evaluation, as it more explicitly schedules incremental work during each operation, smoothing out the costs of rebalancing across cheap operations. Since this requires doing rebalancing work before it becomes necessary, the Hood-Melville queues can end up doing unnecessary work, leading to higher on-average overheads. Use when worst-case performance is more important than average performance.

source

Function reference

StaticArrays.push — Function
push(vec::StaticVector, item)

Return a new StaticVector with item inserted on the end of vec.

Examples

julia> push(@SVector[1, 2, 3], 4)
4-element SArray{Tuple{4},Int64,1,4} with indices SOneTo(4):
 1
 2
 3
 4
push(xs::PFQueue, x)
snoc(xs::PFQueue, x)

Return the PFQueue that results from adding an element to the rear of xs.

source
push(xs::PFHeap, x)

Return the PFHeap that results from adding x to the collection.

source
StaticArrays.popfirst — Function
popfirst(vec::StaticVector)

Return a new vector with the first item in vec removed.

Examples

julia> popfirst(@SVector[1,2,3])
2-element SArray{Tuple{2},Int64,1,2} with indices SOneTo(2):
 2
 3
popfirst(xs)

Return the collection xs without its first element (without modifying xs).

source