[erlang-questions] : documentation of data structures

[Lev Walkin]

Raimo Niskanen wrote:

>>>> Check the implementation. You will reveal that the operations for
>>>> adding/removing elements from/to
>>>> the head/tail can have O(1) complexity in some cases but in some cases
>>>> they will have O(n) complexity.
>>>>
> 
> Adding and removing elements from head or tail is as concluded above
> that is amortized O(1). queue:len/1 is O(n), queue:reverse/1 is O(1),
> queue:join(Q1, Q2) should be O(len(Q1)) by reading the code
> and queue:split/2 should be O(n) by reading the code.

Actually, it'd be neat if queue:len/1 were O(1), since it is just
a simple matter of another element in the tuple.

>>> Okasaki shows a way to have a queue with O(1) worst-case complexity.
>>> However the constant factor is rather large. The queue ADT has O(1)
>>> amortized complexity. In addition to that, it has a rather small
>>> constant factor, so it'll be faster overall.
>>>
> 
> The erlang module 'queue' originates from an Okasaki queue implementation
> that is small, neat, amortized O(1) with low overhead. If he (Okasaki)
> has shown an O(1) worst-case that must be another creature.

The current implementation in `queue` is O(1) amortized non-persistent
and described in Okasaki [1] Chapter 5.2. There's another one, which
is O(1) amortized persistent (Ibid Chapter 6.3.2, 6.4.2), and yet
another one, O(1) worst-case persistent (Ibid. Chapter 7.2,
"Real-Time Queues", also 8.4.2 for real-time deque).

I was referring to the latter.

[1] Chris Okasaki. Purely Functional Data Structures.

-- 
Lev Walkin
vlm@REDACTED