[erlang-questions] Performance of matches

Richard Carlsson <>
Tue Jun 3 23:17:08 CEST 2008


Robert Virding wrote:
> The only O(1) data structure I know of in Erlang are ETS and dict, 

And it should be noted that the O(1) is just for the read operations.
I'm not entirely sure, but it looks like dict is actually O(n) for
writes, although it is not noticeable until n gets pretty large.
(Actually, it could be a good idea to reimplement the dict module
using the same underlying data structure as the array module.)

ETS is probably the closest approximation to O(1) read/write that
you'll get in Erlang, but it has another source of overhead: data
is always copied in and out of the ETS tables, so you don't want to
use it for storing large data structures (unless they are accessed
infrequently).

     /Richard



More information about the erlang-questions mailing list