[erlang-questions] documentation of data structures

Matej Kosik <>
Mon Dec 10 23:36:44 CET 2007


-----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.

(snip)
- --
Matej Kosik
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHXb98L+CaXfJI/hgRAqxKAKCEpla9qGZBtfJW0bKjcoUanopXBACgwmyW
x4eZCs+K8PMjQ+PNWDSg9gg=
=nxc6
-----END PGP SIGNATURE-----



More information about the erlang-questions mailing list