26
1
cross-posted from: https://lemmy.ml/post/4591838
Suppose I need to find out if the intersection of an arbitrary number of lists or sequences is empty.
Instead of the obvious O(n^2^) approach I used a hash table to achieve an O(n) implementation.
Now,
loopmini-language aside, is this idiomatic elisp code? Could it be improved w/o adding a lot of complexity?You can view the same snippet w/ syntax highlighting on pastebin.
(defun seq-intersect-p (seq1 seq2 &rest sequences) "Determine if the intersection of SEQ1, SEQ2 and SEQUENCES is non-nil." (cl-do* ((sequences `(,seq1 ,seq2 ,@sequences) (cdr sequences)) (seq (car sequences) (car sequences)) (elements (make-hash-table :test #'equal)) (intersect-p nil)) ((or (seq-empty-p sequences)) intersect-p) (cl-do* ((seq seq (cdr seq)) (element (car seq) (car seq))) ((or intersect-p (seq-empty-p seq)) intersect-p) (if (ht-get elements element) (setf intersect-p t) (ht-set elements element t))))) (defun test-seq-intersect-p () "Test cases." (cl-assert (null (seq-intersect-p '() '()))) (cl-assert (null (seq-intersect-p '(1) '()))) (cl-assert (null (seq-intersect-p '(1 2) '(3 4) '(5 6)))) (cl-assert (seq-intersect-p '(1 2) '(3 4) '(5 6) '(1))) t) (test-seq-intersect-p)
Version 2
(defun seq-intersect-p (first second & sequences)
"Determine if FIRST, SECOND and any of the sequences in SEQUENCES have
an intersection."
(if (seq-empty-p sequences)
(seq-intersection first second)
(or (seq-intersection first second)
(apply #'seq-intersect-p
first
(seq-first sequences)
`,@(seq-rest sequences))
(apply #'seq-intersect-p
second
(seq-first sequences)
`,@(seq-rest sequences))
(apply #'seq-intersect-p
(seq-first sequences)
(seq-elt sequences 2)
`,@(seq-rest (seq-rest sequences))))))
