It's a bit tricky to explain why your `foldl` would be much faster than my
`minLen` (note "min" not "max"). Perhaps you aren't compiling with max
optimization/`-d:danger` or something? Or perhaps some peculiarity related to
your test data. Total data size, number of strings, and size of the found
prefices are more salient statistics than how many times you repeat, though
another possible explanation is that 100k repeats in a tight loop does
something weird with a warmed up CPU branch predictor. My timings come from a
Unix shell loop doing 10..100 repeated runs of the whole program. As with much
benchmarking, it's debatable what is most representative.
I'll include the whole program below for reference. I called @marks' algorithm
`lcpVertical` for vertically-oriented scanning and swapped `i` & `j` to have
more traditional `j=column index` notation and slightly earlier exit. Because
cligen allows unique prefixes `./lcp -alcpb /usr/bin/\*` is a valid way to run
things in binary search mode. I don't do the final `rfind(sep)` work in any of
those, but it's the same work for all the algorithms anyway and just a couple
line wrapper `proc`.
Anyway, I've run with a variety of inputs and things track my stated
expectations perfectly (compiled with devel version of nim, d:danger, gcc-9.2,
on Linux, i6700k). For really large inputs the range algo works best..for
really small the binary search. So, an optimal at all scales would probably
switch from binary search to range at some machine/system-load dependent
threshold.
stdlib-wise, the `range` LCP algo is never worse than about 2X the run time on
my various /usr/xyz/* type tests, though. So, from a non-tuning/performance
robustness point of view, it would be a better candidate for stdlib inclusion.
Beyond the "one stop shopping" algo-wise and almost trivial implementation, its
`rangeAt` & `range` helpers are much more basic/common operations than longest
common prefix. Beyond that basicness, as mentioned the value-based `range` may
afford strong-speed-ups for specialized types. So, it might be helpful to have
a single point of reference that could be optimized/assumed optimized the way
certain standard C library functions are, such as `memchr`.
when defined(foldl):
import sequtils # For me this is slower
proc minLen(strs: openArray[string]): int {.inline.} =
foldl(strs.mapIt(len(it)), min(a, b))
else:
proc minLen(strs: openArray[string]): int {.inline.} =
result = int.high
for s in strs: result = min(result, s.len)
proc check(strs: openArray[string]; j0, j1: int): bool =
let first = strs[0]
for s in strs:
for j in j0 .. j1:
if s[j] != first[j]: return false
return true
proc lcpLenBinSearch(strs: openArray[string]): int =
if strs.len == 0: return 0 # maybe -1 instead?
if strs.len == 1: return strs[0].len
var lo = 0 # Binary search
var hi = strs.minLen - 1
while lo <= hi:
let mid = lo + (hi - lo) div 2
if check(strs, lo, mid): # All strs match this
result += mid + 1 - lo # Append to answer
lo = mid + 1 # Go higher
else: # Go lower
hi = mid - 1
proc rangeAt*[T](xs: openArray[T]): tuple[minAt, maxAt: int] =
if xs.len == 0: return (-1, -1) # raise?
for i in 1 ..< xs.len:
if xs[result.minAt] < xs[i]: result.minAt = i
if xs[result.minAt] > xs[i]: result.minAt = i
proc range*[T](xs: openArray[T]): tuple[min, max: T] =
if xs.len == 0: return # raise?
let (minAt, maxAt) = xs.rangeAt
result.min = xs[minAt]
result.max = xs[maxAt]
proc lcpLenRange(strs: openArray[string]): int =
if strs.len == 0: return -1 # raise?
let (minAt, maxAt) = strs.rangeAt
for i, c in strs[minAt]:
if c != strs[maxAt][i]: return i
return strs[minAt].len
proc lcpLenVertical(strs: openArray[string]): int =
if strs.len == 0: return 0 # simplified marks algo
let first = strs[0]
for j in 0 ..< first.len:
for i in 1 ..< strs.len:
if j >= strs[i].len or first[j] != strs[i][j]:
return j
return first.len
type lcpAlgo* = enum lcpBinSearch, lcpRange, lcpVertical
proc lcpLen*(strs: openArray[string], algo=lcpVertical): int =
case algo
of lcpBinSearch: return strs.lcpLenBinSearch
of lcpRange: return strs.lcpLenRange
of lcpVertical: return strs.lcpLenVertical
proc lcp*(strs: openArray[string], algo=lcpBinSearch): string =
if strs.len < 1: return ""
result = strs[0][0 ..< strs.lcpLen(algo)]
when isMainModule: # asserts are the Rosetta Code tests
assert lcp(["interspecies", "interstellar", "interstate"]) == "inters"
assert lcp(["throne", "throne"]) == "throne"
assert lcp(["throne", "dungeon"]) == ""
assert lcp(["throne", "", "dungeon"]) == ""
assert lcp(["cheese"]) == "cheese"
assert lcp([""]) == ""
assert lcp(@[]) == ""
assert lcp(["prefix", "suffix"]) == ""
assert lcp(["foo", "foobar"]) == "foo"
import cligen, cligen/osUt
proc timeAlgo(algo=lcpRange, strs: seq[string]) =
timeIt(" in", 1e6, 3, " microseconds via " & $algo & "\n"):
stdout.write strs.lcpLen(algo)
dispatch(timeAlgo)
Run
