[erlang-questions] Checking if the keys of a list of tuples match a list
Fri Apr 13 19:17:21 CEST 2018
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,
> % of the order.
> sublistmember(_, ) -> true;
> sublistmember(List1, List2) ->
> [Head|Tail] = List2,
> case lists:member(Head, List1) of
> true -> sublistmember(List1, Tail);
> false -> false
> 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.
More information about the erlang-questions