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/f9485d0873657a8e83336341...