[erlang-questions] documentation of data structures
Mon Dec 10 23:36:44 CET 2007
-----BEGIN PGP SIGNED MESSAGE-----
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. That is, as I
believe, impossible. Of course, queues can be implemented more efficiently, but in a different
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
-----END PGP SIGNATURE-----
More information about the erlang-questions