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.
>

Reply via email to