`result += mid + 1 - lo` is, indeed, way cheaper than `result.add`, but that
binary search approach only does the `result.add` about `ceil(log_2(minLen))`
times (i.e., like 3-10 times probably). I couldn't even measure the difference
on my 3078 entry average total length 17 `/usr/bin/\*` example (i.e. noise was
>> difference).
Regardless, I **100% agree** that separating into a prefixLen and then getting
that slice would be a nicer factoring anyway. The caller may only need to test
the length against `0` or something.
Another algorithm of interest in terms of this whole thread is the "just
compare first & last in sorted order" approach. This very "tidy" from both a
conceptual and coding point of view:
proc range*[T](xs: openArray[T]): tuple[min, max: T] =
if xs.len < 1: return # default vals for T
result.min = xs[0]
result.max = xs[0]
for x in xs:
result.min = min(result.min, x)
result.max = max(result.max, x)
proc longestCommonPrefixLen*(strs: openArray[string]): int =
let (min, max) = strs.range
for i, c in min:
if c != max[i]: return i
return min.len
Run
As written, that's about 6x slower than the binary search approach for L2
resident data. It's probably possible to really speed up `range` for
`openArray[string]` with some shallow copies in the loop and a real copy at the
end. That might be a fun exercise for someone.
Indeed, for very large inputs, bandwidth starvation of modern CPUs will mean
that doing only one pass over said inputs is going to be best, even if it does
quite a bit more CPU ALU-type work. So, even if that `range` cannot be sped up
to match/beat the binary search in this context, one would still want to switch
to this (or some other) one pass algo to accommodate giant inputs in a more
general setting..probably past the L2 or L3 boundary (assuming it can run with
minimal cache competition).
@marks did not really discuss the size of his inputs or his use case, though
his second "faster on his test set" is notably a multi-pass algorithm.
