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

Ответ 1

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

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

Ответ 2

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

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

Edit:

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

Ответ 3

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

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

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.

Ответ 4

Ваш алгоритм выглядит довольно хорошо, если вы сами придумали это! 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

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

Javascript string diff algorithm (JS Code)

Ответ 5

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

Ответ 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;
}

Ответ 7

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

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

Ответ 8

Решение 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 <[email protected]>
 * 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