[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
longest-common-prefix
From: |
Victor Martinez |
Subject: |
longest-common-prefix |
Date: |
Fri, 21 Aug 2020 07:46:50 +0000 |
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
Description: PGP signature
- longest-common-prefix,
Victor Martinez <=