gb_trees:search/3

Ulf Wiger (AL/EAB) <>
Wed Sep 14 13:13:49 CEST 2005


> From: Sven-Olof Nyström wrote:
>
> I'm a little bit curious about the efficency of
> select(). In the general case, select must be
> implemented using a search through the entire table.
> It seems reasonable to assume that select() may
> sometimes use a more efficient search. (If you
> accept the cost of linear search, implementing select
> over a gb-tree is easy, of course.)

ets:select() detects the trivial case where the whole
key is known, and then reduces to a lookup.

If the first part of the key is known, and it's an 
ordered_set, the cost of ets:select() will be 
proportional to the number of records matching
the bound part of the key.

OTOH, searches like 

 ets:select(Tab,[{{'$1','_'},[{'>','$1',17}], ['$_']}])

will result in a linear search, even though one could
imagine a more efficient strategy.


/Uffe



More information about the erlang-questions mailing list