<infinisil>
I have two lists, each of which contains unique elements to them
<infinisil>
I want to remove all items of one list from the other
<infinisil>
> a = [ 2 3 5 7 11 ]
<{^_^}>
a defined
<infinisil>
> b = [ 5 6 7 ]
<{^_^}>
b defined
<infinisil>
> :p filter (x: ! elem x b) a
<{^_^}>
[ 2 3 11 ]
<infinisil>
I want to have this ^^
<infinisil>
But there must be a better way than this potentially n^2 way
<infinisil>
Hm I could sort them both, then do a combined loop over them, giving O(n log n)
<infinisil>
Although, with Nix's arrays not having constant time append this might get tricky
<infinisil>
Also in my case, b has much less elements that a
<infinisil>
Hm, with a having like 100 elements, and b less than like 5, not sure how much sorting will help
<infinisil>
Idea: Loop through a, doing the `elem x b` check every time, but removing x from b if a match is found, since it can't ever occur after that, because elements are unique
<infinisil>
And a slight optimization: sort b beforehand, such that the `elem x b` can be replaced with a binary search
<infinisil>
Then with |a|=n and |b|=m and n > m, the complexity is about O(m log m + n * log m) = O(n * log m)
<infinisil>
In contrast to O(n * m) with the original approach
<infinisil>
And with sorting both it would be about O(n log n + m log m + n + m) = O(n log n)
<MichaelRaskin>
infinisil: do you want to preserve the order?
<infinisil>
Nah
<MichaelRaskin>
Just convert to attrsets maybe?
<infinisil>
Ah yeah that's another possibility, but looking at builtins.intersectAttrs, it just does the same as the `filter (x: ! elem x b) a` (but in C++)
<MichaelRaskin>
I wonder if it has absolutely anything to do with module system evaluation times…
<infinisil>
Hehe yes
<infinisil>
Background is the implementation of disabledModules
<infinisil>
I'm extending its implementation to support more features
<MichaelRaskin>
Of course, for an efficient implementation we would probably need a persistent associative array
<infinisil>
Oh, I'm also just realizing that both my n and m will be really small. n is the depth of a module through imports statements, while m is the number of disabledModules
ddellacosta has joined #nix-lang
<infinisil>
Hm, and now I'm wondering whether it's possible to modify the disabledModules feature to not even evaluate those modules
<infinisil>
Currently all modules are at least imported/parsed, eval'd to some degree, even if they later get disabledModules'd