<div dir="ltr"><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Aug 17, 2015 at 9:30 AM, Erik Søe Sørensen <span dir="ltr"><<a href="mailto:eriksoe@gmail.com" target="_blank">eriksoe@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Also, you don't state the size of the data structure you're manipulating - only the number of iterations.</blockquote></div><br></div><div class="gmail_extra">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<br><br></div><div class="gmail_extra">PropList = [{x, y} | PL],<br></div><div class="gmail_extra">lists:keyfind(x, 1, PropList).<br><br></div><div class="gmail_extra">Then the key lookup will be in constant time. If on the other hand I do<br><br></div><div class="gmail_extra">PropList = PL ++ [{x,y}]<br><br></div><div class="gmail_extra">Then the lookup is in the order of O(n) where n is the length of PL.<br><br></div><div class="gmail_extra">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).<br><br></div><div class="gmail_extra">Beware the synthetic benchmark. For it lures you into false thinking.<br><br clear="all"></div><div class="gmail_extra"><br>-- <br><div class="gmail_signature">J.</div>
</div></div>