diff options
author | polykernel <81340136+polykernel@users.noreply.github.com> | 2021-11-01 00:16:52 -0400 |
---|---|---|
committer | polykernel <81340136+polykernel@users.noreply.github.com> | 2021-11-01 16:29:01 -0400 |
commit | cd6397519fe8f94fae3646050d8742b11e287bfa (patch) | |
tree | 1a7de29ff19814b4d28e803c425567299f7dca95 /lib | |
parent | 509d236edf0056d05547c776140fe7cfcf2305bd (diff) |
lib/lists: mutuallyExclusive function optimization
The current implementation of `mutuallyExclusive` builds a new list with
length subtracted by one on every recursive call which is expensive. When
b is empty, the function still traverses a in its entirety before returning
a result.
The new implementation uses `any` to check if each element of list b is in
list a using `elem`. This maintains short circuiting when list a or b is empty
and has a worst case time complexity of O(nm).
Diffstat (limited to 'lib')
-rw-r--r-- | lib/lists.nix | 7 |
1 files changed, 2 insertions, 5 deletions
diff --git a/lib/lists.nix b/lib/lists.nix index e469f3ef2652..1dbff7668d75 100644 --- a/lib/lists.nix +++ b/lib/lists.nix @@ -642,7 +642,7 @@ rec { unique [ 3 2 3 4 ] => [ 3 2 4 ] */ - unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) []; + unique = foldl' (acc: e: if elem e acc then acc else acc ++ [ e ]) []; /* Intersects list 'e' and another list. O(nm) complexity. @@ -663,9 +663,6 @@ rec { /* Test if two lists have no common element. It should be slightly more efficient than (intersectLists a b == []) */ - mutuallyExclusive = a: b: - (builtins.length a) == 0 || - (!(builtins.elem (builtins.head a) b) && - mutuallyExclusive (builtins.tail a) b); + mutuallyExclusive = a: b: length a == 0 || !(any (x: elem x a) b); } |