longest-common-prefix

[Victor Martinez]

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.

[Elias Mårtenson]

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