Performance improvement suggestion

Ouverte
  • Quelque chose ne va pas ?
#516 1 commentaire 3 réactions 0 personnes assignées Voir sur GitHub

Les mainteneurs répondent en général sous 1 jour

Personne n'a encore pris cette issue.

Évaluation

Difficulté
4/5
Temps estimé
3-5 jours
Accessibilité débutants
38/100
Type d'issue
Fonctionnalité
Clarté
Plutôt claire
Activité
À l'abandon
Stack technique
javascript
Domaine
performance

Piste de recherche

Commencez au point d’entrée diff_core et comparez les ajustements proposés de trimming et de callback-index avec le comportement diff existant de la bibliothèque. Testez les cas de préfixage, d’ajout en fin, d’insertion, de suppression, de correspondance exacte et de diff général sur de grands arrays ; le travail est terminé lorsque les modifications simples courantes sont plus rapides, tandis que les callbacks et les résultats restent corrects.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

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
        );
    
}
Langage dominant
JavaScript
Étoiles
9.2k
Forks
555
Merge moyen
1 j 9 h
PR mergées (30 j)
5

Préparer son environnement

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de kpdecker/jsdiff

Toutes les issues de kpdecker/jsdiff

Issues similaires

Plus d'issues JavaScript

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.