Performance improvement suggestion

Đang mở
  • Có gì không ổn?
#516 1 bình luận 3 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
38/100
Loại issue
Tính năng
Độ rõ ràng
Khá rõ ràng
Mức độ hoạt động
Đình trệ
Công nghệ
javascript
Lĩnh vực
performance

Hướng nghiên cứu

Bắt đầu từ điểm vào diff_core và so sánh các điều chỉnh trimming và callback-index được đề xuất với hành vi diff hiện có của thư viện. Kiểm thử các trường hợp prepend, append, insert, delete, khớp chính xác và diff tổng quát trên các mảng lớn; được xem là hoàn tất khi các chỉnh sửa đơn giản thường gặp nhanh hơn trong khi callbacks và kết quả vẫn chính xác.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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
        );
    
}
Ngôn ngữ chính
JavaScript
Star
9.2k
Fork
555
Merge trung bình
1 ngày 9 giờ
Pull request đã merge (30 ngày)
5

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của kpdecker/jsdiff

Tất cả issue của kpdecker/jsdiff

Issue tương tự

Thêm issue về JavaScript

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.