1 seconds to sound awfully slow. It's O(n^2). If you sort it first you bring it down to O(log n) which should be benefitting pretty much instantaneous for these use cases.
Regards, Elias On Fri, 21 Aug 2020, 15:47 Victor Martinez, <v...@danwin1210.me> wrote: > 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. >
