longest-common-prefix

Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

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.

signature.asc (673 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: longest-common-prefix

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 

On Fri, 21 Aug 2020, 15:47 Victor Martinez, <[hidden email]> 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.