[erlang-questions] documentation of data structures
Thu Dec 13 06:15:05 CET 2007
Matej Kosik wrote:
> Andras Georgy Bekes wrote:
>> -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.
Persistent FIFO queues with O(1) worst-case complexity of add, remove,
and even catenation (surprisingly) are possible. See
Simple and Efficient Purely Functional Queues and Deques,
Journal of Functional Programming 5(4) pages 583-592, October 1995.
Haim Kaplan, Robert E. Tarjan,
Purely Functional, Real-Time Deques with Catenation,
Journal of the ACM, 46(5) pages 577-603, 1999.
More information about the erlang-questions