[Git][cmucl/cmucl][issue-240-set-diff-with-hash-table] Handle the case of NIL in list2.

[Raymond Toy (@rtoy)]

Raymond Toy pushed to branch issue-240-set-diff-with-hash-table at cmucl / cmucl


Commits:
f9485d08 by Raymond Toy at 2023-06-19T12:46:39-07:00
Handle the case of NIL in list2.

When list2 is in the hash table and it contains NIL and list1 also
contains NIL, we were erroneously including NIL in the difference.
This was because we weren't checking the second return value for
gethash.

Also, for consistency, don't reverse the set of differences.  This
makes output from the hash-table version match the list version.

Finally, add a defparameter to specify the length threshold for
converting a list to hashtable.  This is mostly for testing to
determine an appropriate value.

- - - - -


1 changed file:

- src/code/list.lisp


Changes:

=====================================
src/code/list.lisp
=====================================
@@ -744,6 +744,8 @@
       list
       (cons item list)))
 
+(defparameter *min-list-length-for-hashtable*
+  15)
 
 ;; Convert a list to a hashtable.  Given 2 lists, find the shorter of
 ;; the two lists and add the shorter list to a hashtable.  
@@ -768,7 +770,7 @@
                       (return (values length list1)))
                      ((null l2)
                       (return (values length list2))))))
-        (when (< len 15)
+        (when (< len *min-list-length-for-hashtable*)
           (return-from list-to-hashtable (values nil nil)))
         (cond ((eq shorter-list list2)
 	       (let ((hashtable (make-hash-table :test test :size len)))
@@ -869,9 +871,9 @@
 	   ;; list2 was placed in hash table.
 	   (let (diff)
              (dolist (item list1)
-	       (unless (gethash (apply-key key item) hashtable)
+	       (unless (nth-value 1 (gethash (apply-key key item) hashtable))
                  (push item diff)))
-             (nreverse diff)))
+             diff))
           ((eq shorter-list list1)
 	   ;; list1 was placed in the hash table.
            (dolist (item list2)



View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/commit/f9485d0873657a8e83336341e4eb6bec5a6c4807

-- 
View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/commit/f9485d0873657a8e83336341e4eb6bec5a6c4807
You're receiving this email because of your account on gitlab.common-lisp.net.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/cmucl-cvs/attachments/20230619/aa6b9bb0/attachment-0001.html>