[erlang-questions] Todays Topic: Performance Stuffs->records vs maps vs proplists

Jesper Louis Andersen jesper.louis.andersen@REDACTED
Mon Aug 17 14:03:53 CEST 2015


On Mon, Aug 17, 2015 at 9:30 AM, Erik Søe Sørensen <eriksoe@REDACTED>
wrote:

> Also, you don't state the size of the data structure you're manipulating -
> only the number of iterations.


Indeed. And also you don't specify what the key order is. If I have a
proplist of any size, PL, and then I do

PropList = [{x, y} | PL],
lists:keyfind(x, 1, PropList).

Then the key lookup will be in constant time. If on the other hand I do

PropList = PL ++ [{x,y}]

Then the lookup is in the order of O(n) where n is the length of PL.

In other words, a proplist can hit the two extreme cases, with the typical
case being O(n) (since you have to search half the elements on average). In
contrast, a map has an upper bound of O(lg n) (with an extremely wide
branching factor).

Beware the synthetic benchmark. For it lures you into false thinking.


-- 
J.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20150817/da49ba79/attachment.htm>


More information about the erlang-questions mailing list