[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
union performance bug in symbolics CL
the implementation of union in symbolics CL has a nasty performance bug.
i haven't analyzed the algorithm, but it appears that the number of
pairwise comparisons done in this implementation of union is quadratic
in terms of the lengths of the arguments; the length of the second argument
is in the square term.
ouch. this can be done with N * M comparisons.
the following demonstrates the badness:
(defun union-lossage (n m)
(let ((nn 0)
(x1 (loop for i below n collect i))
(x2 (loop for i from n below (+ n m) collect i)))
(flet ((nneq (a b) (incf nn) (eq a b)))
(union x1 x2 :test #'nneq)
(union-lossage 1 1000) ==> 500500
(union-lossage 1000 1) ==> 1000