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

Gilberio Carmenates Garcia co7eb@REDACTED
Thu Aug 20 18:53:36 CEST 2015

Hi all. Yes indeed thanks for replying, Jesper, luckedly I did all test with the same order and I did the lookup with the first element. The only problem is with maps, because maps reorders its keys. So I will do the test again taking in count the order of the final constructed map and make that same order to the records and proplists, and lookup with the first and last key, just to see the different between cases and O(1) y O(N).



Ivan (son of Gilberio).





De: Jesper Louis Andersen [mailto:jesper.louis.andersen@REDACTED] 
Enviado el: lunes, 17 de agosto de 2015 8:04
Para: Erik Søe Sørensen
CC: Gilberio Carmenates Garcia; Erlang Questions
Asunto: Re: [erlang-questions] Todays Topic: Performance Stuffs->records vs maps vs proplists



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.



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20150820/9172df38/attachment.htm>

More information about the erlang-questions mailing list