Алгоритм для получения изменений между двумя массивами

Я думаю, что реализация метода diff верна, временная сложность вашего алгоритма составляет O(n * log(n)) из-за методов сортировки. Если вы используете массивы, вам нужно отсортировать их перед сравнением, а временная сложность алгоритмов сортировки составляет как минимум O(n * log(n)).

Если массивы o и n не могут содержать одно и то же значение более одного раза, возможно, лучшим выбором будет использование объектов (ассоциативных массивов) вместо массивов.

Пример:

function diff(o, n) { 
    var a = {}; var r = {}; 

    for (var i in o) {
        if (!(i in n)) {
            r[i] = 1;
        }
    }
    for (var i in n) {
        if (!(i in o)) {
            a[i] = 1;
        }
    }
    return {added: a, removed: r};
}

    // how to use
var o = {"a":1, "b":1, "ab":1};
var n = {"a":1, "aa":1};

var diffon = diff (o, n);

    // display the results
var added = "", removed = "";
for (var i in diffon.added) {
    added += i + ", ";
}
for (var i in diffon.removed) {
    removed += i + ", ";
}

alert ("added: " + added);
alert ("removed: " + removed);

Временная сложность в этом случае равна O(n).

Если вам нужна более подробная информация о массивах, ассоциативных массивах в JavaScript, я предлагаю вам следующую ссылку: Array object

Ваш алгоритм выглядит довольно хорошо для того, чтобы придумать его самому! Поздравляю!
Следует помнить, что хотя ваш алгоритм показывает изменения содержимого двух массивов (удаление элементов и т.д.), он не показывает изменения порядка содержимого (или удаленные элементы добавляются снова позже).

Например, вы можете удалить элемент 1 из массива a и добавить его обратно позже, технически изменяя массив a по сравнению с массивом b, но оставаясь незамеченным вашим алгоритмом.

array a: {1, 2, 3, 4, 5, 6}

array b: {1, 2, 3, 4, 5, 6}

array a: {2, 3, 4, 5, 6}    //after a.shift();
array a: {2, 3, 4, 5, 6, 1} //after a.push(1);

=> a != b //your algorithm would return "a == b" though

Ваш алгоритм может быть достаточным для ваших конкретных потребностей, однако для действительно строгого алгоритма различения массивов я бы попытался перенести алгоритм различения строк. По сути, изменив алгоритм так, чтобы вместо сравнения символов/пробелов в строке он сравнивал элементы в вашем массиве.

Javascript string diff algorithm (JS Code)

Я создал тест скорости между двумя возможными реализациями.

Исходный код:

function diff1 (o, n) { 
  // deal with empty lists 
  if (o == undefined) o = []; 
  if (n == undefined) n = []; 

  // sort both arrays (or this won't work) 
  o.sort(); n.sort(); 

  // don't compare if either list is empty 
  if (o.length == 0 || n.length == 0) return {added: n, removed: o}; 

  // declare temporary variables 
  var op = 0; var np = 0; 
  var a = []; var r = []; 

  // compare arrays and add to add or remove lists 
  while (op < o.length && np < n.length) { 
      if (o[op] < n[np]) { 
          // push to diff? 
          r.push(o[op]); 
          op++; 
      } 
      else if (o[op] > n[np]) { 
          // push to diff? 
          a.push(n[np]); 
          np++; 
      } 
      else { 
          op++;np++; 
      } 
  } 

  // add remaining items 
  if( np < n.length ) 
    a = a.concat(n.slice(np, n.length)); 
  if( op < o.length ) 
    r = r.concat(o.slice(op, o.length)); 

  return {added: a, removed: r};  
}

function diff2 (o, n) {
        // convert array items to object members
    var objO = {}, objN = {};
    for (var i = 0; i < o.length; i++) {
        objO[o[i]] = 1;
    }
    for (var i = 0; i < n.length; i++) {
        objN[n[i]] = 1;
    }

    var a = []; var r = []; 

    for (var i in objO) {
        if (i in objN) {
            delete objN[i];
        }
        else {
            r.push (i);
        }
    }
    for (var i in objN) {
        a.push (i);
    }
    return {added: a, removed: r};
}

var o = [], n = [];
for (var i = 0; i < 300000; i++) {
    if (i % 2 == 0) {
        o.push (i);
    }
    if (i % 3 == 0) {
        n.push (i);
    }
}

var start = new Date ();
diff1 (o, n);
var end1 = new Date ();
diff2 (o, n);
var end2 = new Date ();

alert ((end1 - start) + ", " + (end2 - end1));

Недостаток diff2 в том, что возвращаемые массивы (добавленные, удаленные) не сортируются.

Тест скорости:

IE7: diff1: 2578ms, diff2: 1906ms

IE8: diff1: 1953ms, diff2: 1152ms

Firefox: diff1: 254ms, diff2: 527ms

Opera: diff1: 143ms, diff2: 253ms

Safari: diff1: 466ms, diff2: 657ms

Chrome: diff1: 734ms, diff2: 581ms

Вывод: diff1 быстрее в Firefox, Opera и Safari, diff2 быстрее в IE и Chrome.

Не существует константы undefined . Вместо этого вам следует проверить тип переменной:

if (typeof o === 'undefined') o = [];

Изменить:

Как показал Тим Даун, свойство фактически определено в стандарте, но, поскольку стандарт не определяет его как постоянный, он ненадежен и не должен использоваться.

// I prefer to not sort the arrays

Array.prototype.diff= function(ar){
    var a= [], i= 0, L= this.length,
    ar= ar.concat(), t1, t2;
    while(i<L){
        t1= this[i++];
        t2= ar.indexOf(t1);
        if(t2!= -1){
            ar.splice(t2, 1);
        }
        else a.push(t1);
    }
    return a;
}

Array.prototype.compare= function(a2){
    return{
        r: this.diff(a2), a: a2.diff(this)
    }
}

/* 
test

var a1= [-1, 2, 3, 3, 4, 5], a2= [0, 2, 4, 3, 5, 6, 8];
var o= a1.compare(a2);

alert('added: '+o.a+'\nremoved: '+o.r);


returned:

added: 0, 6, 8
removed: -1, 3

*/


// oldbrowser code:

if(![].indexOf){
    Array.prototype.indexOf= function(what, i){
        i= i || 0;
        var L= this.length;
        while(i< L){
            if(this[i]=== what) return i;
            ++i;
        }
        return -1;
    }
}

// Return common values instead of differences
Array.prototype.incommon= function(ar){
    var a= [], i= 0, L= this.length, a2= ar.concat(), t1, t2;
    while(i<L && a2.length){
        t1= this[i++];
        t2= a2.indexOf(t1);
        if(t2 != -1){
            a.push(a2.splice(t2, 1));
        }
    }
    return a;
}