7
submitted 1 year ago* (last edited 1 year ago) by bahmanm@lemmy.ml to c/lisp@lemmy.ml

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, 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))))))
you are viewing a single comment's thread
view the rest of the comments
[-] charje@lemmy.ml 1 points 1 year ago

This version is definitely a bit harder to follow what is going on.

[-] bahmanm@lemmy.ml 1 points 1 year ago* (last edited 1 year ago)

Oh!? And I was under the impression that the code reads more naturally than the initial version ๐Ÿ˜‚


Let me try putting it in words and see if it makes sense to you:

Given sequences seq1 and seq2 and sequence of sequences sequences, seq-intersect-p should return non-nil if at least one pair of the input sequences have got an intersection.

  1. If seq1 and seq2 intersect return t
  2. Recursively check if seq1 intersects w/ any element in sequences. If it does, return t. Otherwise we know seq1 is safe to be ignored - no intersection whatsoever.
  3. Recursively check if seq2 intersects w/ any element in sequences. If they don't, we know seq2 is safe to be ignored too.
  4. Recursively check if any elements of sequences intersect w/ each other.

There's no caching or optimisation in this version. So it's always O(n^2^).

this post was submitted on 08 Sep 2023
7 points (100.0% liked)

Lisp Community

687 readers
1 users here now

A community for the Lisp family of programming languages.

Lisp (historically LISP) is a family of programming languages with a long history and a distinctive, fully parenthesized prefix notation. Originally specified in 1958, Lisp is the second-oldest high-level programming language. Only Fortran is older, by one year.

History

Associations and meetings

Resources - TODO

Related communities (dialects) - TODO

founded 5 years ago
MODERATORS