GitLab

at 2023-08-17T13:33:59+00:00

Address #240: Speed up intersection by using a hashtable

Merge branch 'issue-240-intersection-with-hash-table' into 'master'

Address #240: Speed up intersection by using a hashtable

Closes #240

See merge request cmucl/cmucl!160
   (declare (inline member))

   (if (and testp notp)

       (error "Test and test-not both supplied."))

-  (let ((res nil))

-    (dolist (elt list1)

-      (if (with-set-keys (member (apply-key key elt) list2))

-	  (push elt res)))

-    res))

+  (let ((hashtable 

+	  (list-to-hashtable list2 key test test-not)))

+    (cond (hashtable

+	   (let ((res nil))

+	     (dolist (item list1)

+	       (when (nth-value 1 (gethash (apply-key key item) hashtable))

+		 (push item res)))

+	     res))

+	  ((null hashtable)

+	   (let ((res nil))

+	     (dolist (elt list1)

+	       (if (with-set-keys (member (apply-key key elt) list2))

+		   (push elt res)))

+	     res)))))

 

 (defun nintersection (list1 list2 &key key

 			    (test #'eql testp) (test-not nil notp))

Raymond Toy pushed to branch master at cmucl / cmucl

Commits:

1 changed file:

Changes: