7
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))))))
Instead of storing intersect-p as a variable and keeping it until the end of the loop, you can return early as soon as you find the first intersection.
Even though a hash table has better symtotic run time, you might find after benchmarking that the O(n^2) is faster for your use case. If you are set on using a hash table, you might consider setting the initial size to something a bit larger (relative to the input lists) to avoid having to dynamically grow the hash table.
I think also the return value of the inner loop is never used...
I personally like to keep my tests assertions top level so I can interactively run each one by itself.
Thanks for the code review and feedback. Here's a 2nd attempt: https://pastebin.com/WBqs9u8L
I essentially threw away my bloated Java/C#'esq implementation and started from scratch. Please let me know what you think ๐
This version is definitely a bit harder to follow what is going on.
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
seq1andseq2and sequence of sequencessequences,seq-intersect-pshould return non-nilif at least one pair of the input sequences have got an intersection.seq1andseq2intersect returntseq1intersects w/ any element insequences. If it does, returnt. Otherwise we knowseq1is safe to be ignored - no intersection whatsoever.seq2intersects w/ any element insequences. If they don't, we knowseq2is safe to be ignored too.sequencesintersect w/ each other.There's no caching or optimisation in this version. So it's always O(n^2^).
Noted. Makes sense.