Performance improvement suggestion

オープン
  • 何か問題がありますか？
#516 コメント 1 件 リアクション 3 件 担当者 0 名 GitHub で見る

メンテナーはふだん 1 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
38/100
issue の種類
機能追加
明瞭さ
おおむね明確
活発さ
停滞
技術スタック
javascript
領域
performance

調査の方向性

diff_core エントリポイントから開始し、提案されている trimming と callback-index の調整を、ライブラリに既存の diff 動作と比較します。大きな配列について、先頭への追加、末尾への追加、挿入、削除、完全一致、一般的な diff のケースを検証します。一般的な単純編集が高速化され、callbacks と結果が正しいままであれば完了です。

索引モデルが issue の本文から書いたものです。

説明

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
        );
    
}
主要言語
JavaScript
スター
9.2k
フォーク
555
平均マージ
1日 9時間
マージ済み PR（30日）
5

環境構築

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

kpdecker/jsdiff のほかの issue

kpdecker/jsdiff の issue をすべて見る

似ている issue

JavaScript の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。