[erlang-questions] testing a list against an ets table

[Håkan Stenholm]

Doug Edmunds wrote:
> Scenario:
> The goal is determine if any tuples in the List are not
> in the Table (and if so, identify which are missing).
>
> I wrote two functions, one which uses ets:match_object/2 and
> the other which uses lists:member/2.
>
> Function parameters:
> List is a list of tuples [{a,b}, {c,d,e}, {a,d}, ...].
> Table is an open ets table of type 'bag', which means
> there can be more than one item with the same key in
> the table.
>
> Which of these methods is preferable, and why?
>
> %% a quick display utility function
> io(X) -> io:format("~p~n",[X]).
>
> findlist1(List,Table) ->
>     R1 = [E || E <- List, length(ets:match_object(Table, E)) == 0],
>     io(R1),           %% elements not found in table
>     io(length(R1)).   %% if length(R1) == 0, all are in list
>   
I guess that this is something like O(N) or O(N log N), as 
ets:match_object/2 is
fast if the key is defined in the match pattern (E).
> findlist2(List, Table) ->
>     AsList = ets:tab2list(Table),
>     R1 = [E || E <- List, not lists:member(E,AsList)],
>     io(R1),   %% same as above
>     io(length(R1)).
>   
This is O(N^2) - it does a O(N) scan over the list AsList for each 
element in List.
There is also a minor O(N) cost of copying the Table into a list (AsList).
> length(R1) could be turned into true/false thus:
>
> case length(R1) of
>
>       0 -> true;  % all in table
>       _Other -> false
> end.
>
> What are some other alternatives?
>   
You could use sets (sets, ordset, ...)

find_tuples_not_in_table(List, Table) ->
    LSet = sets:from_list(List),
    TSet = sets:from_list(ets:tab2list(Table)),
    sets:subtract(LSet, TSet).

This should (probably) be O(N log N) to build the sets and O(N)
to do the set subtraction - this may depend on the set module used.
>
> Also, I would appreciate suggestions on
> how to short-circuit the evaluation
> (stopping as soon as one element of the
> list is not found in the table).
%% short circuit loop by doing manual List traversal
findlist1([],Table) ->
    true;
findlist1([E | List], Table) ->
    case ets:match_object(Table, E) of
	[] -> false;                   %% stop when E not found
	_  -> findlist1(List, Table)
    end.


%% short circuit using exceptions, this allow the use of standard
%% list traversal functions like map, foldl, ... although it's kind
%% of ugly to use exceptions for something thats not really a error
findlist1(List,Table) ->
    F = fun(E, Acc) ->
	case ets:match_object(Table, E) of
		[] -> throw(end);
		_  -> Acc
    	end,
    try lists:foldl(F, true, List)
    catch throw:end -> false
    end.


>
> Thanks.
>
> -dae
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions