[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