Performance of Erlang data structures
Tue Jan 25 13:55:56 CET 2005
You can have a look at:
but there might be other documents that more directly answers your
Regarding the basic types, lists are chains of cons cells and there
are no reverse pointers, nor pointers to the end of the list. This
means that append, search, insert, indexing, etc. are O(n), while consing
or matching from the head is O(1).
Tuples are fixed size arrays, but when replacing an element in
a tuple, a copy of the whole tuple except for one element
has to be made. This means that search, replace, copy is O(n) while
indexing is O(1).
Often you want to use higher abstraction data organisation, e.g
ets, gb_trees, gb_sets. Look at their manpages. They might at
least contain a hint of what basic algorithms are used,
tree or hash or such, and that might give you indirect
information about their performance.
sebastian@REDACTED (Sebastian Bello) writes:
> is there a document regarding performance of Erlang data structures? For example, what is the performance (order, o(n), constant, etc) of the insertion in a list, the lookup, etc. Just to know what data structures to use when performance is an issue.
/ Raimo Niskanen, Erlang/OTP, Ericsson AB
More information about the erlang-questions