longest-common-prefix

Victor Martinez <[email protected]> Fri, 21 Aug 2020 07:46:50 +0000

Newsgroups	gmane.comp.window-managers.stumpwm.devel
Message-ID	<[email protected]>

in input.lisp:

(defun lcp (seqs &key (test #'eql))
 (length (reduce (lambda (x y) (subseq x 0 (mismatch x y :test test))) seqs)))

would do the job for longest-common-prefix?

(let ((l (loop repeat 9000 collect (alexandria:iota 1000))))
 (time (lcp l)))

Evaluation took:
  1.083 seconds of real time
  1.083 seconds of real time
  1.066142 seconds of total run time (0.699486 user, 0.366656 system)
  [ Run times consist of 0.750 seconds GC time, and 0.317 seconds non-GC time. ]
  98.43% CPU
  2,374,861,962 processor cycles
  143,991,952 bytes consed

1000

where the current function

(defun longest-common-prefix (seqs &key (test #'eql))
  "Returns the length of the longest common prefix of the sequences."
  (flet ((longest-common-prefix-2 (seq1 seq2)
           (alexandria:if-let ((i (mismatch seq1 seq2 :test test)))
             i
             (length seq1))))
    (apply #'min (alexandria:map-product #'longest-common-prefix-2 seqs seqs))))

would give a sb-kernel::control-stack-exhausted-error.

signature.asc (application/pgp-signature, 659 B)