Oops. Didn't survive some edits. Good catch as always, @e. Will fix in the
prior post with a note. Does not effect my results which are like this:
$ echo /usr/bin/*|wc
1 3077 58306
$ (repeat 50; lcp -alcpV /usr/bin/*)|mnsd
9 in 53.97 +- 0.30 microseconds via lcpVertical
$ (repeat 50; lcp -alcpR /usr/bin/*)|mnsd
9 in 51.33 +- 0.42 microseconds via lcpRange
$ (repeat 50; lcp -alcpB /usr/bin/*)|mnsd
9 in 39.29 +- 0.78 microseconds via lcpBinSearch
Run
(I use Zsh which has `repeat` and a little mean-sdev computer.) Then for a
larger inputs:
$ echo /usr/lib/python3.6/**|wc
1 39036 3108640
$ (repeat 10 lcp -alcpV /usr/lib/python3.6/**)|mnsd
19 in 2388. +- 14. microseconds via lcpVertical
$ (repeat 10 lcp -alcpR /usr/lib/python3.6/**)|mnsd
19 in 1131.1 +- 1.5 microseconds via lcpRange
$ (repeat 10 lcp -alcpB /usr/lib/python3.6/**)|mnsd
19 in 1523. +- 17. microseconds via lcpBinSearch
Run
The L3 on an i7-6700k is 8MB. So, this is showing the range method pulling
ahead while still in L3 (3.1 MB). At one pass, it really has to be
approximately the fastest at large scale. Reading from DIMMs the difference
should be even more pronounced in favor of range.
It's possible that that marks/vertical scan style might be faster if the answer
is very small. E.g., for a zero common prefix length, the answer will be
concluded after just one pass down the first column via `lcpVertical`.
