Performance of Erlang data structures

[Sebastian Bello]

Ok. Thank you Raimo for your explanation.

----- Original Message -----
From: "Raimo Niskanen" <raimo@REDACTED>
To: <erlang-questions@REDACTED>
Sent: Tuesday, January 25, 2005 10:58 AM
Subject: Re: Performance of Erlang data structures


> Sorry, broken link, see the other reply instead.
>
> Raimo Niskanen <raimo@REDACTED> writes:
>
> > You can have a look at:
> >
http://otp.ericsson.se:8000/product/info/otp_unix/doc/efficiency_guide/part_
frame.html
> > 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
>