For explicitness,
proc lcpLenVRange(strs: openArray[string]): int =
if strs.len == 0: return -1 # raise?
var minAt, maxAt: int
for i in 1 ..< strs.len:
if strs[i] < strs[minAt]: minAt = i
if strs[i] > strs[maxAt]: maxAt = i
if strs[i].len > 0 and strs[i][0] != strs[0][0]:
return 0
for i, c in strs[minAt]:
if c != strs[maxAt][i]: return i
return strs[minAt].len
Run
Integrating that into the test harness appropriately and running on my two
running data input examples (extended to a case with zero length common
prefix), and switching to `mnmx` (which gives the range of times instead of
mean+-sdev) then gives:
$ for a in lcpVe lcpR lcpB lcpVR; { (repeat 20; lcp -a$a
/usr/lib/python3.6/**)|mnmx }
19 in 2300.262..2448.32 microseconds via lcpVertical
19 in 1122.236..1162.767 microseconds via lcpRange
19 in 1523.256..1558.781 microseconds via lcpBinSearch
19 in 1189.47..1224.756 microseconds via lcpVRange
$ for a in lcpVe lcpR lcpB lcpVR; { (repeat 20; lcp -a$a /usr/bin/*)|mnmx }
9 in 51.737..76.532 microseconds via lcpVertical
9 in 48.637..68.903 microseconds via lcpRange
9 in 36.24..40.054 microseconds via lcpBinSearch
9 in 46.253..54.598 microseconds via lcpVRange
$ for a in lcpVe lcpR lcpB lcpVR; { (cd /usr/bin; repeat 20; lcp -a$a
*)|mnmx }
0 in 3.099..5.722 microseconds via lcpVertical
0 in 43.392..80.109 microseconds via lcpRange
0 in 8.583..13.113 microseconds via lcpBinSearch
0 in 3.099..5.245 microseconds via lcpVRange
$ for a in lcpVe lcpR lcpB lcpVR; { (cd /usr/lib/python3.6; repeat 20; lcp
-a$a **)|mnmx }
0 in 7.868..11.683 microseconds via lcpVertical
0 in 911.713..959.158 microseconds via lcpRange
0 in 174.522..190.735 microseconds via lcpBinSearch
0 in 9.537..14.782 microseconds via lcpVRange
Run
So, you can get the early exit of the vertical method for zero common prefices
in the range method without very much extra cost. Eg., slightly
negative/in-the-noise cost for the L2 prefixLen==9 case and 6% slower for the
prefixLen=19 L3 case with the early exits basically matching times in the two
prefixLen==0 cases.
(and, yeah, yeah..the Nim program should `import stats`, do the repeated loops
internally updating a `RunningStat`, and report. It could even take an `lcpAll`
enum to report on all algorithms..and -- if one wants to commit to only file
tree inputs -- maybe even take just a directory as a command parameter, `import
oswalkdir`, and use `walkDir` and `walkDirRec` instead of `*` and `**` to
remove dependency on shell features.)
