Erlang :queue vs List

alvises · February 22, 2019, 8:18pm

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?

al2o3cr · February 22, 2019, 9:03pm

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.

alvises · February 22, 2019, 9:28pm

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?

dom · February 22, 2019, 11:10pm

Yes, some queue implementations do just that:

github.com

Qqwy/elixir_okasaki/blob/master/lib/okasaki/implementations/amortized_queue.ex#L9


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