alvises
February 22, 2019, 8:18pm
#1
After benchmarking queues they seem much faster than Lists on
appending .

`[1,...1000] ++ [1001]`

O(n)
`:queue.in(1,q)`

should be O(1) right?
last element

`List.last([1,..,1000])`

again O(n)
`:queue.get_r(q)`

again O(1)
and they should be similar on prepending

List `[0 | [1,..,1000]]`

`:queue.in_r(0,q)`

Now, seeing queues implementation it seems reasonable. A queue generated from a list of numbers from 1 to 1000 is implemented as a tuple of two lists.

`{ [1000, 999, 998,.., 501], [1, 2, 3, 4, .., 500] }`

So the list is split in two and the last half part of the list is reversed. Since prepending an item in a list is fast O(1) then appending `1001`

is fast because `1001`

is prepended to the first list in the tuple. Same thing for getting the last element, with lists is O(n) and while with `:queue`

is O(1).

My question is, what are the downsides of using queues over lists? Maybe enumerating the numbers from 500 to 1000 since that list is reversed?
Some rebalancing when enqueueing new elements?

3 Likes

al2o3cr
February 22, 2019, 9:03pm
#2
Your intuition is correct - the documentation for `:queue`

has a list of slow operations:

```
All operations [have] an amortized O(1) running time, except
filter/2, join/2, len/1, member/2, split/2 that have O(n).
```

See also the paper referenced in those docs, â€śPurely Functional Data Structuresâ€ť by Chris Okasaki for detailed analysis.

10 Likes

alvises
February 22, 2019, 9:28pm
#3
Thanks a lot for the pdf! Super interesting!!

Isnâ€™t len O(n) also on lists?

len/1 couldnâ€™t it be made O(1) wrapping the queue around a struct, which has a :count field that is incremented/decremented at each operation?

1 Like

dom
February 22, 2019, 11:10pm
#4
Yes, some queue implementations do just that:

defmodule Okasaki.Implementations.AmortizedQueue do
@moduledoc """
The standard implementation of a queue as a pair of lists.
This implementation is somewhat simpler than the guaranteed constant-time implementation in `Queue`,
but any particular `remove` might take O(n).
"""
defstruct [left: [], right: [], size: 0]
@opaque t :: %__MODULE__{
size: integer,
left: list,
right: list
}
use FunLand.Mappable
@spec map(t, (any -> any)) :: t
def map(queue = %__MODULE__{left: left, right: right}, fun) do

http://ucsd-progsys.github.io/liquidhaskell-tutorial/09-case-study-lazy-queues.html

3 Likes