O (N) Реализация простого алгоритма дифференцирования - это правильно? - PullRequest
Новая
       20

O (N) Реализация простого алгоритма дифференцирования - это правильно?

0 голосов
/ 29 октября 2019

Я только что опубликовал это на HN, но, похоже, он не очень популярен, у меня возник вопрос по поводу различий - я хотел узнать, в порядке ли используемая мной реализация: она кажется слишком простой,и литература по диффузии очень плотная.

Справочная информация: последние пару дней я создавал движок рендеринга для редактора кода. Рендеринг огромных кусков выделенного синтаксиса может запаздывать. На этом этапе переходить на React не стоит, поэтому я хотел просто написать алгоритм быстрого сравнения, который бы выборочно обновлял только измененные строки.

Я нашел эту статью: https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/

С помощьюссылка на этот документ, первоначальная реализация Git diff: http://www.xmailserver.org/diff2.pdf

Я не смог найти PDF для начала, но прочитал «редактировать график» и сразу подумал - почему бы мне просто не использовать хеш-таблицусохранить строки из LEFT_TEXT и ссылки на них, затем перебрать RIGHT_TEXT и возвращать совпадения одну за другой, а также следить за последним совпадением, чтобы избежать путаницы?

Алгоритм, который я создал, тольконесколько строк и кажется точным. Это сложность времени O (N), тогда как в приведенном выше документе лучше всего описывается O (ND), где D - минимальное расстояние редактирования. 

  function lineDiff (left, right) {
    left = left.split('\n');
    right = right.split('\n');
    let lookup = {};
    // Store line numbers from LEFT in a lookup table
    left.forEach(function (line, i) {
      lookup[line] = lookup[line] || [];
      lookup[line].push(i);
    });
    // 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();
        // Make sure we're looking ahead
        if (lineNumber > minLine) {
          minLine = lineNumber;
        } else {
          lineNumber = -1
        }
      }
      return {
        value: line,
        from: lineNumber
      };
    });
  }

Ссылка RunKit: https://runkit.com/keithwhor/line-diff

Чтоя скучаю? Я не могу найти другие ссылки на проведение различий, как это. Все просто ссылается на эту статью.

...