[erlang-questions] documentation of data structures
Andras Georgy Bekes
Fri Dec 7 09:17:13 CET 2007
I've checked the manpage of the new array data structure, and I don't
find any info about its runtime (and space) compexity. I think not
knowing the implementation details is OK, but the runtime complexity of
the most frequently used operations on a data structure is needed in
the documentation I think.
I've checked (hopefully) every data structure:
- ordsets and orddict: The doc states that they are represented as
ordered lists. It doesn't mention the complexities of the operations,
it is OK because the implementation is rather trivial and an Erlang
programmer is expected to know the runtime behaviour of such
-sets and dict: The doc states that the representation is not defined.
I think the doc shoud give a worst case complexity of the operations
that will not change no matter how the implementation changes.
- gb_sets and gb_trees: The doc states the implementation. For gb_trees,
the complexities are not given. For gb_sets it gives info about the
complexity on set operations, however, it might be better to give the
complexities of for each of the operations, instead of just
separating "set operations" and "lookup (membership testing), insertion
-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.
- array: The doc doesn't say anything. Not even that the implementation
is not defined.
The docs should be made complete and consistent ie. should state the
same infos in the same style for each of these data structures.
More information about the erlang-questions