set-difference and friends are somewhat slow
Describe the feature
set-difference
is somewhat slow. In an example from maxima, I have two lists of length 3072. I need to compute the set difference between these two. On my machine, it takes about 0.4 sec to do this. With clisp, it's about 0.28 sec.
Is there a prototype?
I don't have a prototype, but the implementation in clisp can provide some hints on the approach to use. See https://gitlab.com/gnu-clisp/clisp/-/blob/master/src/defs1.lisp#L259-428 for how to use a hashtable to speed these up.
Describe the feature in more detail
To speed this up clisp uses a hashtable when the test is one of the supported hash-table tests. We could do something similar. This optimization could also be applied to
-
UNION
-
INTERSECTION
-
SET-DIFFERENCE
-
SET-EXCLUSIVE-OR
-
SUBSETP
. -
NUNION
-
NINTERSECTION
-
NSET-DIFFERENCE
-
NSET-EXCLUSIVE-OR
A hash table could also be used for REMOVE-DUPLICATES
and
DELETE-DUPLICATES
but these are more complicated.
Edited by Raymond Toy