Benchmark: Comparing two string difference methods, one using LCS - Longest Common Subsequence

Tests:

Using LCS
function diff(a, b) { const lcsMatrix = Array(b.length + 1).fill(null).map(() => Array(a.length + 1).fill(null)); for (let i = 0; i <= a.length; i++) { for (let j = 0; j <= b.length; j++) { if (i === 0 || j === 0) { lcsMatrix[i][j] = 0; } else if (a[i - 1] === b[j - 1]) { lcsMatrix[i][j] = lcsMatrix[i - 1][j - 1] + 1; } else { lcsMatrix[i][j] = Math.max(lcsMatrix[i - 1][j], lcsMatrix[i][j - 1]); } } } let i = a.length, j = b.length; const diffs = []; while (i > 0 && j > 0) { if (a[i - 1] === b[j - 1]) { i--; j--; } else if (lcsMatrix[i - 1][j] > lcsMatrix[i][j - 1]) { diffs.unshift(['-', i - 1, a[i - 1]]); i--; } else { diffs.unshift(['+', i, b[j - 1]]); j--; } } while (j > 0) { diffs.unshift(['+', i, b[j - 1]]); j--; i--; } return diffs; } diff("hello","hello world")
Generic
const diff = (a, b) => [...a].map((c, i) => c !== b[i] && [i, b[i] || '']).filter(Boolean); diff("hello","hello world")

Rendered benchmark preparation results:

Previous results

Test case name	Result
Using LCS
Generic

ⓘ Get performance results from real users on your website with Request Metrics.

Latest run results:

Run details: (Test run date: one year ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/107.0.0.0 Safari/537.36

Browser/OS: Chrome 107 on Windows

Test name	Executions per second
Using LCS	58188.4 Ops/sec
Generic	2707843.0 Ops/sec

Comparing two string difference methods, one using LCS - Longest Common Subsequence (version: 0)