[erlang-questions] Ets bag complexity
Sverker Eriksson
<>
Mon Dec 10 15:46:15 CET 2012
Gleb Peregud wrote:
>>> - insert operations are amortized O(1) (sometimes resizing of arrays is
>>> needed)
>>>
>> insert in bag is also O(1+K) as we have to make sure that we do not insert
>> duplicates.
>>
>
> Good point!
>
>
Also to be clear, there is no heavy resizing of entire hash array.
Linear hashing is used which means table grows by splitting and
rehashing one bucket at a time.
>>> - select operations are O(N+K) where N is a number of keys, K is
>>> number of values
>>>
>> I guess you mean O(N*K) if K is average number of values per key. In other
>> words traversal of the entire table.
>>
>
> Yes, in general case. I assumed (and didn't inform you) a specific
> case when only a single key matches the select match specification.
>
>
If the key in match-spec is totally bound, the select implementation
does a hash lookup and thereby get O(1+K).
Otherwise we get O(N*K) from total table traversal.
/Sverker
More information about the erlang-questions
mailing list