[erlang-questions] documentation of data structures
Fri Dec 7 10:20:16 CET 2007
Andras Georgy Bekes wrote:
> - 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.
I agree. We just forgot to mention it. Meanwhile, here is a summary
for the array module:
- The implementation uses a tree of tuples.
- Operations that access or update a single element are O(log n).
- Whole-array operations are O(n * log n).
- The main reasons why arrays are more efficient than binary trees
are that they use wider tuples (log10 instead of log2), and that the
computations while traversing a chain of nodes are simpler (integer
arithmetic for selecting a subtree, rather than key comparisons).
More information about the erlang-questions