[erlang-questions] Ets bag complexity
Mon Dec 10 15:46:15 CET 2012
Gleb Peregud wrote:
>>> - insert operations are amortized O(1) (sometimes resizing of arrays is
>> insert in bag is also O(1+K) as we have to make sure that we do not insert
> 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.
More information about the erlang-questions