| ... |
... |
@@ -45,7 +45,7 @@ |
|
45
|
45
|
tree-equal list-length nth %setnth nthcdr last make-list append
|
|
46
|
46
|
copy-list copy-alist copy-tree revappend nconc nreconc butlast
|
|
47
|
47
|
nbutlast ldiff member member-if member-if-not tailp adjoin union
|
|
48
|
|
- nunion intersection nintersection set-difference nset-difference
|
|
|
48
|
+ nunion intersection nintersection nset-difference
|
|
49
|
49
|
set-exclusive-or nset-exclusive-or subsetp acons pairlis assoc
|
|
50
|
50
|
assoc-if assoc-if-not rassoc rassoc-if rassoc-if-not subst subst-if
|
|
51
|
51
|
subst-if-not nsubst nsubst-if nsubst-if-not sublis nsublis))
|
| ... |
... |
@@ -744,11 +744,13 @@ |
|
744
|
744
|
list
|
|
745
|
745
|
(cons item list)))
|
|
746
|
746
|
|
|
|
747
|
+;; The minimum length of a list before we can use a hashtable
|
|
747
|
748
|
(defparameter *min-list-length-for-hashtable*
|
|
748
|
749
|
15)
|
|
749
|
750
|
|
|
750
|
751
|
;; Convert a list to a hashtable. Given 2 lists, find the shorter of
|
|
751
|
|
-;; the two lists and add the shorter list to a hashtable.
|
|
|
752
|
+;; the two lists and add the shorter list to a hashtable. Returns the
|
|
|
753
|
+;; hashtable and the shorter list.
|
|
752
|
754
|
(defun list-to-hashtable (list1 list2 &key test test-not key)
|
|
753
|
755
|
;; Don't currently support test-not when converting a list to a hashtable
|
|
754
|
756
|
(unless test-not
|
| ... |
... |
@@ -763,13 +765,18 @@ |
|
763
|
765
|
(unless hash-test
|
|
764
|
766
|
(return-from list-to-hashtable (values nil nil)))
|
|
765
|
767
|
(multiple-value-bind (len shorter-list)
|
|
|
768
|
+ ;; Find the list with the shorter length. If they're they
|
|
|
769
|
+ ;; same, we prefer the second list to the first list since
|
|
|
770
|
+ ;; the hashtable implementation is slightly simplier.
|
|
766
|
771
|
(do ((length 0 (1+ length))
|
|
767
|
772
|
(l1 list1 (cdr l1))
|
|
768
|
773
|
(l2 list2 (cdr l2)))
|
|
769
|
|
- ((cond ((null l1)
|
|
770
|
|
- (return (values length list1)))
|
|
771
|
|
- ((null l2)
|
|
772
|
|
- (return (values length list2))))))
|
|
|
774
|
+ ((cond ((null l2)
|
|
|
775
|
+ (return (values length list2)))
|
|
|
776
|
+ ((null l1)
|
|
|
777
|
+ (return (values length list1))))))
|
|
|
778
|
+ ;; If the list is too short, the hashtable makes things
|
|
|
779
|
+ ;; slower. We also need to balance memory usage.
|
|
773
|
780
|
(when (< len *min-list-length-for-hashtable*)
|
|
774
|
781
|
(return-from list-to-hashtable (values nil nil)))
|
|
775
|
782
|
(cond ((eq shorter-list list2)
|
| ... |
... |
@@ -855,18 +862,20 @@ |
|
855
|
862
|
(declare (inline member))
|
|
856
|
863
|
(if (and testp notp)
|
|
857
|
864
|
(error "Test and test-not both supplied."))
|
|
|
865
|
+ ;; Quick exit
|
|
|
866
|
+ (when (null list)
|
|
|
867
|
+ (return-from set-difference list1))
|
|
|
868
|
+
|
|
858
|
869
|
(multiple-value-bind (hashtable shorter-list)
|
|
859
|
870
|
(list-to-hashtable list1 list2 :key key :test test :test-not test-not)
|
|
860
|
871
|
(cond ((null hashtable)
|
|
861
|
872
|
;; Default implementation because we didn't create the hash
|
|
862
|
873
|
;; table.
|
|
863
|
|
- (if (null list2)
|
|
864
|
|
- list1
|
|
865
|
|
- (let ((res nil))
|
|
866
|
|
- (dolist (elt list1)
|
|
867
|
|
- (if (not (with-set-keys (member (apply-key key elt) list2)))
|
|
868
|
|
- (push elt res)))
|
|
869
|
|
- res)))
|
|
|
874
|
+ (let ((res nil))
|
|
|
875
|
+ (dolist (elt list1)
|
|
|
876
|
+ (if (not (with-set-keys (member (apply-key key elt) list2)))
|
|
|
877
|
+ (push elt res)))
|
|
|
878
|
+ res))
|
|
870
|
879
|
((eq shorter-list list2)
|
|
871
|
880
|
;; list2 was placed in hash table.
|
|
872
|
881
|
(let (diff)
|