Thanks so much for this library. I've been using a highly modified version for diffing arrays and found for some large array sets with simple edits it was quite slow (eg: 2+ seconds when prepending many items).
For my use case, the edits are often single append, prepend, insert or delete operations and I found for these common cases I could speed up things considerably by trimming common items from the start/end before calling the core diff routine. With this tweak, many operations that previously took 150 - 2000ms now take 1-2 ms.
The code below shows the basic concept. As mentioned, I'm using a modified version of the library with different callbacks that just give the insert and delete operations - but it should be relatively easy to adapt it to work with this library again.
// callback(op, index, count) where op = "insert" or "delete"
export function diff(oldArray, newArray, callback, compareEqual)
{
if (!compareEqual)
compareEqual = function(a,b) { return a == b; }
// Get the min and max length of the two arrays
let minLength = Math.min(oldArray.length, newArray.length);
let maxLength = Math.max(oldArray.length, newArray.length);
// Work out how many matching items at the start
let trimStart = 0;
while (trimStart < minLength &&
compareEqual(oldArray[trimStart], newArray[trimStart]))
{
trimStart++;
}
// Exact match?
if (trimStart == maxLength)
return;
// Simple Append?
if (trimStart == oldArray.length)
{
callback('insert', oldArray.length, newArray.length - oldArray.length);
return;
}
// Work out how many matching items at the end
let trimEnd = 0;
while (trimEnd < (minLength - trimStart) &&
compareEqual(oldArray[oldArray.length - trimEnd - 1], newArray[newArray.length - trimEnd - 1]))
{
trimEnd++;
}
// Simple prepend?
if (trimEnd == oldArray.length)
{
callback('insert', 0, newArray.length - oldArray.length);
return;
}
// Simple insert?
if (trimStart + trimEnd == oldArray.length)
{
callback('insert', trimStart, newArray.length - oldArray.length);
return;
}
// Simple delete?
if (trimStart + trimEnd == newArray.length)
{
callback('delete', trimStart, oldArray.length - newArray.length);
return;
}
// Untrimmed?
if (trimStart == 0 && trimEnd == 0)
{
return diff_core(oldArray, newArray, callback, compareEqual);
}
// Trimmed diff - slice the arrays and adjust the indicies on the callbacks
return diff_core(
oldArray.slice(trimStart, -trimEnd),
newArray.slice(trimStart, -trimEnd),
(op, index, count) => callback(op, index + trimStart, count),
compareEqual
);
}
Thanks so much for this library. I've been using a highly modified version for diffing arrays and found for some large array sets with simple edits it was quite slow (eg: 2+ seconds when prepending many items).
For my use case, the edits are often single append, prepend, insert or delete operations and I found for these common cases I could speed up things considerably by trimming common items from the start/end before calling the core diff routine. With this tweak, many operations that previously took 150 - 2000ms now take 1-2 ms.
The code below shows the basic concept. As mentioned, I'm using a modified version of the library with different callbacks that just give the insert and delete operations - but it should be relatively easy to adapt it to work with this library again.