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

Commits:

• 96e66071
  by Raymond Toy at 2023-07-26T18:59:10-07:00

  Make +min-list-length-for-hashtable+ a defparameter again
  
  Rename it using the `*foo*` convention too.  It's super-convenient to
  be able to set this for testing, which we do in the existing test
  suite for this.
  
  It's also convenient to be able to do this when doing timing tests so
  we can compare what happens when the list version is used vs when the
  hashtable is used.
  

• 7ab5d243
  by Raymond Toy at 2023-07-26T19:00:59-07:00

  Add some additional tests for set-difference
  
  Add a test where a key is given to make sure that hashtable works
  correctly with a key
  
  Add a test where both a test and a test-not is given.  This must
  signal an error.
  

2 changed files:

• src/code/list.lisp
• tests/sets.lisp

Changes:

 ;; The minimum length of a list before we can use a hashtable.  This

 ;; was determined experimentally.

-(defconstant +min-list-length-for-hashtable+

+(defparameter *min-list-length-for-hashtable*

   15)

 ;; Convert a list to a hashtable.  The hashtable does not handle

       ;; If the list is too short, the hashtable makes things

       ;; slower.  We also need to balance memory usage.

       (let ((len (length list)))

-	(when (< len +min-list-length-for-hashtable+)

+	(when (< len *min-list-length-for-hashtable*)

           (return-from list-to-hashtable nil))

 	(let ((hashtable (make-hash-table :test hash-test :size len)))

 	  (dolist (item list)

     (cond (hashtable

 	   ;; list2 was placed in hash table.

 	   (let ((res nil))

-	     (dolist (item list1)

+	     (doli st (item list1)

 	       (unless (nth-value 1 (gethash (apply-key key item) hashtable))

 		 (push item res)))

 	     res))

 		  (set-difference '("a" "b" "b" "C")

 				  '("c" "D" "e" "f" "g" "h")

 				  :test #'equalp))))

+

+;; Simple test that we handle a key correctly

+(define-test set-diff.hash-eql-with-key

+  (let ((lisp::*min-list-length-for-hashtable* 2))

+    (assert-equal '((3 "b") (2 "b"))

+		  (set-difference '((1 "a") (2 "b") (3 "b"))

+				  '((1 "a") (4 "c") (5 "d"))

+				  :key #'first))))

+

+(define-test set-diff.test-and-test-not

+  (assert-error 'simple-error

+		(set-difference '(1 2)

+				'(3 4)

+				:test 'eql

+				:test-not 'eql)))

+

+