Johan / Stefan - any progress on the reviewing part?
Only possible error I'm aware of is that I made the indices/counts
32 bit signed/unsigned integers, which means it'll run into trouble
if there are more than ~2 billion different tokens (lines) or more than
~4 billion occurrences of the same token. If the library should be
able to handle such files, they should be made 64 bit (for the
indices, it should be safe to keep them 32 bit on 32 bit machines,
as those could never have the memory to run such diffs anyway).
I have a couple of other changes ready:
One is a minor simplification, by getting rid of the idx parameter in
lcs.c - there is a simpler way to accomplish what it's for.
The other change is a partial implementation of the other possible
enhancement I mentioned earlier, which takes advantage of unique
matches to "restart" the lcs algorithm whenever possible, thus
reducing the effect of the square computational complexity. The
"partial" part is that this version is only really effective if the two
files have roughly the same number of (non-unique) lines; it will not
reduce the (P * length difference) part of the complexity. For good
cases, though, it can reduce the time required by the lcs algorithm
by large factors (roughly the number of well-separated sections of
difference, if they are all about the same size).
The question is how I should post these changes. The idx change
is relatively independent of the others; should I post a patch from
current HEAD revision for that change alone, should I post it in this
thread or a new one, and should I specify how that patch interacts
with the other patches (and if so, where)? The other patch is based
on my original patch; should I post a patch of the additional
changes or a cumulative patch from current HEAD revision?
Received on 2011-05-24 22:23:25 CEST