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

[Gilberio Carmenates Garcia]

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).

 

Cheers,

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.




-- 

J.

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