Performance of Erlang data structures

Raimo Niskanen raimo@REDACTED
Tue Jan 25 13:58:56 CET 2005

Sorry, broken link, see the other reply instead.

Raimo Niskanen <raimo@REDACTED> writes:

> You can have a look at:
> but there might be other documents that more directly answers your
> question.
> 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:
> > Hi,
> > 
> > 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.
> > Thanks,
> >     Sebastian-
> > 
> -- 
> / Raimo Niskanen, Erlang/OTP, Ericsson AB


/ Raimo Niskanen, Erlang/OTP, Ericsson AB

More information about the erlang-questions mailing list