[erlang-questions] Checking if the keys of a list of tuples match a list

[Mikael Pettersson]

On Fri, Apr 13, 2018 at 5:18 PM, Silas <silas@REDACTED> wrote:
> 2. Now a question about Erlang data structures: To check if a list has   all
> elements of another list (regardless of the order), I'm using   this:
>
>    % This function returns true if all elements in List2 are in List1,
> regardless
>    % of the order.
>    sublistmember(_, []) -> true;
>    sublistmember(List1, List2) ->
>        [Head|Tail] = List2,
>        case lists:member(Head, List1) of
>            true -> sublistmember(List1, Tail);
>            false -> false
>        end.
>
> Its complexity is O(len(List1)) * O(len(List2)) which is not actually a
> problem for small lists (I can limit the number of tags the user may
> provide) but I was wondering if there is a more effective way.  I thought
> about using sets to simplify but list -> set -> list conversion may be even
> slower, right?  Any suggestions on this?

lists:member/2 is a BIF, so implemented by C code in the VM.  For
short lists this is going to be pretty much optimal.  I'd move the
[Head|Tail] extraction into the function head however.

You can easily do the check in linear time if the lists are sorted;
otherwise you may pre-sort for O(N*logN) overall cost.  But this is
only worthwhile for longer lists, so you'd have to run some
measurements to determine a suitable cut-off point.