[erlang-questions] documentation of data structures

Richard Carlsson richardc@REDACTED
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).

     /Richard





More information about the erlang-questions mailing list