std-set-difference | ![]() |
STD-SET-DIFFERENCE
returns the set difference of the two lists set and subset, all elements of set that are not member of subset. Or you can say "set minus subset", all elements of set minus the ones in subset.
This function is stable. The returned list keeps the order of the first list.
(std-set-difference '(0 1 2) '(2 3 4)) => (0 1)
(std-set-difference '(0 1 2 3 4 5) '(2 0 6 7)) => (1 3 4 5)
(std-set-difference '(5 4 3 2 1 0) '(2 0 6 7)) => (5 4 3 1)
set, subset: proper lists, without defined order.
A list of copies of some elements from the first argument set.
None.
Performance Note
Big lists as second argument are slightly faster than as first argument, but the two lists are not interchangable as they are in std-union:
(setq big (std-int-list 1000) small (std-int-list 10)) (std-time '(std-set-difference small big)) (STD-SET-DIFFERENCE SMALL BIG) : 0 ms (std-time '(std-set-difference big small)) (STD-SET-DIFFERENCE BIG SMALL) : 50 ms
Normally set is bigger than subset, but subset can also be a big list. The rest elements of subset are simply ignored because only the first set is iterated: O(n), the second set is used for member: O(n/2).
In certain situations one might try to use to subtract from the working list a large list of fixed elements. This is quite fast. But one should try to shrinken the first list as early as possible, for example removing duplicates before.
(setq *knowns* (atoms-family)) ... (while code (setq lst (std-flatten (read code)))
;; lst might get large
(setq new (std-set-difference lst *knowns*)) ... )
builds a list of new symbols in some arbitrary code.
The better possibility would be:
(while code (setq lst (std-flatten (read code)))
;; lst might get large, but *knowns* is larger if
;; there are not many duplicates
(setq new (std-set-difference (std-remove-duplicates lst) *knowns*)) ... )
Or even better write around std-flatten, removing duplicates and *knowns*
in the loop which processes (read code)
.
(std-require 'STDLIST)
Defined in STDLIST