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(n2) approach I used a hash table to achieve an O(n) implementation.

Now, loop mini-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))))))
  • Cid@lemmy.sdf.orgEnglish
    2·
    1 year ago

    If you don’t care about the intersection values:

    init empty hashmap w best guess on size
Iterate sequences
  Iterate elements
    If elt in hashmap return t
  Add elt to hashmap
return nil

    If you have maybe million+ elements, a db like sqlite might help. Unique index, insert each item til you get a unique constraint failure.

    • bahmanmOPEnglish
      1·
      1 year ago

      Yes, that’s essentially the snippet in my post 👍

      • Cid@lemmy.sdf.orgEnglish
        2·
        1 year ago

        Personally, I’d drop all the macro template syntax, applys, intersects, etc. And simplify the function arg to be just: (sequences)

        let item-map make-hash-table
  dolist seq sequences
    dolist item seq
      ;; gethash / return / or setf & continue