Performance improvement suggestion

未关闭
  • 哪里不对？
#516 1 条评论 3 个 reaction 已指派 0 人 在 GitHub 查看

维护者通常 1 天内回复

还没有人认领这个 Issue。

评估

难度
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 小时
30 天内合并 PR
5

环境准备

  • 没有 Dockerfile 或 Docker Compose 文件
  • 没有 Pull Request 模板
  • 阅读贡献指南

从这里开始

  1. 先读完整个 Issue，再读项目的贡献指南。
  2. 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
  3. Fork 仓库，在一个分支上完成修改。
  4. 提交 Pull Request，并在描述里引用这个 Issue 编号。

kpdecker/jsdiff 的其他 Issue

查看 kpdecker/jsdiff 的全部 Issue

相似的 Issue

更多 JavaScript Issue

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。