GitLab

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.

@@ -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)

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

Commits:

1 changed file:

Changes: