[erlang-questions] documentation of data structures

[Lev Walkin]

Matej Kosik wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Andras Georgy Bekes wrote:
> 
> (snip)
> 
>> -queue: The doc doesn't say anything about the implementation, 
>> only: "implements FIFO queues in an efficient manner".
>> It states that "all operations has an amortised O(1) running time", 
>> except for some, that are "probably O(n)". This is rather vague.
>>
> 
> 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.
> 
> It would be particularly attractive, if someone implemented `queue' (with the same signature and
> semantics of operations) where those operations would have always O(1) complexity. That is, as I
> believe, impossible. Of course, queues can be implemented more efficiently, but in a different
> (non-functional-like) way.


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.

-- 
Lev Walkin
vlm@REDACTED