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

[Hynek Vychodil]

It depends of ets table content, what is best in "absolute" time. For short
sets using lists:member/2 can be fastest.
For big data where amount of tuples with same first element is low, using
ets:match_object/2 should be fastest.
But for worst case, where there is big amount of tuples with same first
elemnt, best should be transform ets talbe from bag to set where each item
will be transformed by function (Tuple) -> {Tuple}. And time will be O(N).
(But with big constant factor.)

check_list(List, Table) ->
    Set = ets:new(set, [set, private]),
    true = ets:foldl(fun(X, _) -> true = ets:insert(Set, {X}) end, true,
Table),
    try lists:foreach(fun(X) -> case ets:member(Set, {X}) of true -> ok;
false-> throw(not_found) end end, List) of
       _ -> true
    catch
       throw:not_found -> false
    after
       ets:delete(Set)
    end.


2008/6/20 Doug Edmunds <dougedmunds@REDACTED>:

> 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
>
> findlist2(List, Table) ->
>     AsList = ets:tab2list(Table),
>     R1 = [E || E <- List, not lists:member(E,AsList)],
>     io(R1),   %% same as above
>     io(length(R1)).
>
> 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?
>
> 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).
>
> Thanks.
>
> -dae
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>



-- 
--Hynek (Pichi) Vychodil
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080620/7bf4333c/attachment.htm>