synchronization - JavaScript sync two arrays (of objects)find delta - Stack Overflow

admin管理员组

文章数量:1191355

I have two arrays, old and new, which hold objects at each position. How would I sync or find the delta (i.e. what is new, updated and deleted from the new array compared to the old array)

var o = [
    {id:1, title:"title 1", type:"foo"},
    {id:2, title:"title 2", type:"foo"},
    {id:3, title:"title 3", type:"foo"}
];

var n = [
    {id:1, title:"title 1", type:"foo"},
    {id:2, title:"title updated", type:"foo"},
    {id:4, title:"title 4", type:"foo"}
];

With the above data, using id as the key, we'd find that item with id=2 has an updated title, item with id=3 is deleted, and item with id=4 is new.

Is there an existing library out there that has useful functions, or is it a case of loop and inner loop, compare each row..e.g.

for(var i=0, l=o.length; i<l; i++)
{   
    for(var x=0, ln=n.length; x<ln; x++)
    {
        //compare when o[i].id == n[x].id    
    }  
}

Do this kind of comparison three times, to find new, updated and deleted?

I have two arrays, old and new, which hold objects at each position. How would I sync or find the delta (i.e. what is new, updated and deleted from the new array compared to the old array)

var o = [
    {id:1, title:"title 1", type:"foo"},
    {id:2, title:"title 2", type:"foo"},
    {id:3, title:"title 3", type:"foo"}
];

var n = [
    {id:1, title:"title 1", type:"foo"},
    {id:2, title:"title updated", type:"foo"},
    {id:4, title:"title 4", type:"foo"}
];

With the above data, using id as the key, we'd find that item with id=2 has an updated title, item with id=3 is deleted, and item with id=4 is new.

Is there an existing library out there that has useful functions, or is it a case of loop and inner loop, compare each row..e.g.

for(var i=0, l=o.length; i<l; i++)
{   
    for(var x=0, ln=n.length; x<ln; x++)
    {
        //compare when o[i].id == n[x].id    
    }  
}

Do this kind of comparison three times, to find new, updated and deleted?

• javascript
• synchronization

Share Improve this question Follow asked Feb 19, 2013 at 19:55 FergalFergal 2,47444 gold badges3636 silver badges4949 bronze badges 6

• 1 You could speed things up a little, if the ids are unique and you use an object with the id as keys. – Sirko Commented Feb 19, 2013 at 20:03
• You should explain what is the output? An object with three properties? {added: 4], changed: [2], deleted: [3]} – Ruan Mendes Commented Feb 19, 2013 at 20:05
• Output would probably be best in three arrays. The deleted would only need IDs, added and changed would need the full "row" / object – Fergal Commented Feb 19, 2013 at 20:07
• @Sirko the input will always be arrays of objects. I could of course convert them to objects with keys before the comparison starts – Fergal Commented Feb 19, 2013 at 20:22
• @Fergal: Since they are arrays, is their order important? Or do they represent sets? – Bergi Commented Feb 19, 2013 at 20:25

 |  Show 1 more comment

3 Answers 3

Sorted by: Reset to default 22

There's no magic to do what you need. You need to iterate through both objects looking for changes. A good suggestion is to turn your structure into maps for faster searches.

/**
 * Creates a map out of an array be choosing what property to key by
 * @param {object[]} array Array that will be converted into a map
 * @param {string} prop Name of property to key by
 * @return {object} The mapped array. Example:
 *     mapFromArray([{a:1,b:2}, {a:3,b:4}], 'a')
 *     returns {1: {a:1,b:2}, 3: {a:3,b:4}}
 */
function mapFromArray(array, prop) {
    var map = {};
    for (var i=0; i < array.length; i++) {
        map[ array[i][prop] ] = array[i];
    }
    return map;
}

function isEqual(a, b) {
    return a.title === b.title && a.type === b.type;
}

/**
 * @param {object[]} o old array of objects
 * @param {object[]} n new array of objects
 * @param {object} An object with changes
 */
function getDelta(o, n, comparator)  {
    var delta = {
        added: [],
        deleted: [],
        changed: []
    };
    var mapO = mapFromArray(o, 'id');
    var mapN = mapFromArray(n, 'id');    
    for (var id in mapO) {
        if (!mapN.hasOwnProperty(id)) {
            delta.deleted.push(mapO[id]);
        } else if (!comparator(mapN[id], mapO[id])){
            delta.changed.push(mapN[id]);
        }
    }

    for (var id in mapN) {
        if (!mapO.hasOwnProperty(id)) {
            delta.added.push( mapN[id] )
        }
    }
    return delta;
}

// Call it like
var delta = getDelta(o,n, isEqual);

See http://jsfiddle.net/wjdZ6/1/ for an example

This is typescript version of @Juan Mendes answer

  mapFromArray(array: Array<any>, prop: string): { [index: number]: any } {
    const map = {};
    for (let i = 0; i < array.length; i++) {
      map[array[i][prop]] = array[i];
    }
    return map;
  }

  isEqual(a, b): boolean {
    return a.title === b.title && a.type === b.type;
  }

  getDelta(o: Array<any>, n: Array<any>, comparator: (a, b) => boolean): { added: Array<any>, deleted: Array<any>, changed: Array<any> } {
    const delta = {
      added: [],
      deleted: [],
      changed: []
    };
    const mapO = this.mapFromArray(o, 'id');
    const mapN = this.mapFromArray(n, 'id');
    for (const id in mapO) {
      if (!mapN.hasOwnProperty(id)) {
        delta.deleted.push(mapO[id]);
      } else if (!comparator(mapN[id], mapO[id])) {
        delta.changed.push(mapN[id]);
      }
    }

    for (const id in mapN) {
      if (!mapO.hasOwnProperty(id)) {
        delta.added.push(mapN[id]);
      }
    }
    return delta;
  }

Same as @Juan Mendes but for built-in Maps and a bit more efficient (on finding added values)

function mapDelta(oldMap, newMap, compare) {

    var delta = {
        added: [],
        deleted: [],
        changed: []
    };

    var newKeys = new Set(newMap.keys());

    oldMap.forEach(function (oldValue, oldKey) {
        newKeys.delete(oldKey);
        var newValue = newMap.get(oldKey);
        if (newValue == undefined) {
            delta.deleted.push({ key: oldKey, value: oldValue });
            return;
        }
        else if (!compare(oldValue, newValue)) {
            delta.changed.push({ key: oldKey, oldValue: oldValue, newValue: newValue });
        }
    });

    newKeys.forEach(function (newKey) {
        delta.added.push({ key: newKey, value: newMap.get(newKey) });
    });

    return delta;
}

and using typescript

function mapDelta<K, T>(oldMap: Map<K, T>, newMap: Map<K, T>, compare: (a: T, b: T) => boolean) {

  const delta = {
    added: [] as { key: K, value: T }[],
    deleted: [] as { key: K, value: T }[],
    changed: [] as { key: K, oldValue: T, newValue: T }[]
  };

  const newKeys = new Set(newMap.keys());

  oldMap.forEach((oldValue, oldKey) => {
    newKeys.delete(oldKey);
    const newValue = newMap.get(oldKey);
    if (newValue == undefined) {
      delta.deleted.push({ key: oldKey, value: oldValue });
      return;
    } else if (!compare(oldValue, newValue)) {
      delta.changed.push({ key: oldKey, oldValue: oldValue, newValue: newValue });
    }
  })

  newKeys.forEach((newKey) => {
    delta.added.push({ key: newKey, value: newMap.get(newKey) });
  })

  return delta;
}

本文标签： synchronizationJavaScript sync two arrays (of objects)find deltaStack Overflow