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:

===================================== src/code/list.lisp ===================================== @@ -746,7 +746,7 @@

;; 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 @@ -767,7 +767,7 @@ ;; 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) @@ -855,7 +855,7 @@ (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))

===================================== tests/sets.lisp ===================================== @@ -72,3 +72,20 @@ (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))) + +

View it on GitLab: https://gitlab.common-lisp.net/cmucl/cmucl/-/compare/3fbae4d018b9bc6891effd4...