Title: Hey folks,<p>I&#x27;ve been building a rendering engine for a code editor the past couple of days. Rendering huge chunks of highlighted syntax can get laggy. It&#x27;s not worth switching to React at this stage, so I wanted to just write a quick diff algorithm that would selectively update only changed lines.<p>I found this article:
https:&#x2F;&#x2F;blog.jcoglan.com&#x2F;2017&#x2F;02&#x2F;12&#x2F;the-myers-diff-algorithm-part-1&#x2F;<p>With a link to this paper, the initial Git diff implementation:
http:&#x2F;&#x2F;www.xmailserver.org&#x2F;diff2.pdf<p>I couldn&#x27;t find the PDF to start with, but read &quot;edit graph&quot; and immediately thought — why don&#x27;t I just use a hashtable to store lines from LEFT_TEXT and references to where they are, then iterate over RIGHT_TEXT and return matches one by one, also making sure that I keep track of the last match to prevent jumbling?<p>The algorithm I produced is only a few lines and seems accurate. It&#x27;s O(N) time complexity, whereas the paper above gives a best case of O(ND) where D is minimum edit distance.<p><pre><code>  function lineDiff (left, right) {
    left = left.split(&#x27;\n&#x27;);
    right = right.split(&#x27;\n&#x27;);
    let lookup = {};
    &#x2F;&#x2F; Store line numbers from LEFT in a lookup table
    left.forEach(function (line, i) {
      lookup[line] = lookup[line] || [];
      lookup[line].push(i);
    });
    &#x2F;&#x2F; Last line we matched
    var minLine = -1;
    return right.map(function (line) {
      lookup[line] = lookup[line] || [];
      var lineNumber = -1;
      if (lookup[line].length) {
        lineNumber = lookup[line].shift();
        &#x2F;&#x2F; Make sure we&#x27;re looking ahead
        if (lineNumber &gt; minLine) {
          minLine = lineNumber;
        } else {
          lineNumber = -1
        }
      }
      return {
        value: line,
        from: lineNumber
      };
    });
  }
</code></pre>
RunKit link:
https:&#x2F;&#x2F;runkit.com&#x2F;keithwhor&#x2F;line-diff<p>What am I missing? I can&#x27;t find other references to doing diffing like this. Everything just links back to that one paper.
Upvote: