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

Question

Мне нужно было создать алгоритм, который будет (эффективно) принимать старый массив и новый массив и возвращать мне изменения между ними (какие элементы добавлены, а какие удалены). Это должно быть в JavaScript (для запуска в браузере), но алгоритм важнее языка.

Вот что я придумал: http://jsbin.com/osewu3/13. Кто-нибудь может увидеть какие-либо проблемы с этим / предложить какие-либо улучшения?

Спасибо!

Листинг кода:

function diff(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}; 
}

(я также опубликовал это в качестве потенциального решения другого SO вопроса, здесь: Разница в массиве JavaScript )

Answer 1

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

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

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: разница 1: 2578 мс, разница 2: 1906 мс

IE8: разница 1: 1953 мс, разница 2: 1152 мс

Firefox: diff1: 254ms , diff2: 527ms

Опера: diff1: 143ms , diff2: 253ms

Safari: diff1: 466ms , diff2: 657ms

Chrome: diff1: 734ms, diff2: 581ms

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

Answer 2

Нет постоянной undefined.Вместо этого вы должны проверить тип переменной:

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

Редактировать:

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

Answer 3

Ваш алгоритм выглядит неплохо, если вы придумали его сами! Congrats!
Имейте в виду, что, хотя ваш алгоритм выявляет изменения содержимого двух массивов (удаление элементов и т. Д.), Он не выявляет изменения порядка содержимого (или удаления элементов, добавляемых позже).

Например, вы можете удалить элемент 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

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

Алгоритм сравнения строк JavaScript ( Код JS )

Answer 4

PHP-решение для ассоциативных массивов, разделяющее вставки / обновления / удаления на отдельные массивы:

/**
 * compute differences between associative arrays.
 * the inserts, updates, deletes are returned
 * in separate arrays. Note: To combine arrays
 * safely preserving numeric keys, use $a + $b
 * instead of array_merge($a, $b).
 *
 * Author: Monte Ohrt <monte@ohrt.com>
 * Version: 1.0
 * Date: July 17th, 2014
 *
 * @param array $a1
 * @param array $a2
 * @return array ($inserts, $updates, $deletes)
 */
get_array_differences($a1, $a2) {
    // get diffs forward and backward
    $forward = array_diff_assoc($a1, $a2);
    $backward = array_diff_assoc($a2, $a1);
    // compute arrays
    $inserts = array_diff_key($forward, $backward);
    $updates = array_intersect_key($forward, $backward);
    $deletes = array_diff_key($backward, $forward);
    return array($inserts, $updates, $deletes);
}

https://gist.github.com/mohrt/f7ea4e2bf2ec8ba7542c

Answer 5

Я использую эту функцию:

function diffArray(from, to){
    /*
    result will hold the transformations (in order) that need to 
    be done to make the from array equal to the to array
    */
    var result = [];
    var fromValue, fromIndex, fromCount, fromOffset;
    var toValue, toIndex, toCount, toMap;

    /*
    Buld an index for the two arrays to speed up the process. Do
    note that due to this optimization all values in the array will
    be transformed to strings. So the number 1 will be equal to the
    string '1'. Also all objects will converted to strings (via
    toString) and therefore probably considered equal.
    */
    toMap = to.reduce(function(result, value, index){
        if(value in result) result[value].push(index);
        else result[value] = [index];
        return result;
    }, {});
    toIndex = 0;
    toCount = to.length;

    fromOffset = 0;
    fromIndex = 0;
    fromCount = from.length;

    /*
    loop until we reach the end of one of the two arrays
    */
    while(fromIndex < fromCount && toIndex < toCount){
        fromValue = from[fromIndex];
        toValue = to[toIndex];

        /*
        when the two values are equal, no transformation is required.
        */
        if(fromValue === toValue){
            fromIndex++;
            toIndex++;
        }
        else{
            /*
            if fromValue is not in the remainder of the to array
            */
            // if(~to.indexOf(fromValue, toIndex)){ 
            if(
                fromValue in toMap
                && toMap[fromValue].some(function(value){
                    return toIndex <= value;
                })
            ){
                result.push({
                    type: 'insert'
                    , index: fromIndex + fromOffset
                    , value: toValue
                });
                toIndex++
                fromOffset++;
            }
            else{
                result.push({
                    type: 'delete'
                    , index: toIndex
                    , value: fromValue
                });
                fromIndex++
                fromOffset--;
            }

        }

    }

    return result
    /*
    add the remainder of the from array to the result as deletions
    */
    .concat(
        from
        .slice(fromIndex)
        .map(function(value, index){
            var result = {
                type: 'delete'
                , index: index + fromIndex + fromOffset
                , value: value
            };
            fromOffset--;
            return result;
        })
    )
    /*
    add the remainder of the to array to the result as insertions
    */
    .concat(
        to
        .slice(toIndex)
        .map(function(value, index){
            var result = {
                type: 'insert'
                , index: index + toIndex
                , value: value
            };
            fromOffset++;
            return result;
        })
    )
    ;

}//diffArray

Проверьте репозиторий на наличие обновлений и модульных тестов: https://github.com/elmerbulthuis/diff-array

Answer 6

// 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;
}

Answer 7

Я думаю, что реализация метода 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, я предлагаю вам следующую ссылку: Объект массива

Answer 8

На следующей странице есть функция, которая удаляет один массив из другого и может использоваться для получения двух значений. Удаление элементов из массива JavaScript с помощью RemoveArrayItems ()

var newItemsAdded=RemoveArrayItems(oldArray,newArray);
var ItemsRemoved =RemoveArrayItems(newArray,oldArray);