Is there a more efficient AS3 way to compare 2 arrays for adds, removes & updates?

Question

Hi all - I'm wondering if there is a better way to approach this than my current solution...

I have a list of items, I then retrieve another list of items. I need to compare the two lists and come up with a list of items that are existing (for update), a list that are not existing in the new list (for removal) and a list of items that are not existing in the old list (for adding).

Here is what I'm doing now - basically creating a lookup object for testing if an item exists. Thanks for any tips.

            for each (itm in _oldItems)
        {
            _oldLookup[itm.itemNumber] = itm;
        }

        // Loop through items and check if they already exist in the 'old' list
        for each (itm in _items)
        {
            // If an item exists in the old list - push it for update
            if (_oldLookup[itm.itemNumber])
            {
                _itemsToUpdate.push(itm);
            }
            else // otherwise push it into the items to add
            {
                _itemsToAdd.push(itm);
            }

            // remove it from the lookup list - this will leave only
            // items for removal remaining in the lookup
            delete _oldLookup[itm.itemNumber];
        }

        // The items remaining in the lookup object have neither been added or updated - 
        // so they must be for removal  - add to list for removal
        for each (itm in _oldLookup)
        {
            _itemsToRemove.push(itm);
        }

Answer 1

Instead of using an Array, which requires O(n) time to determine if a value is present, you should use an Object, which should give you better performance (either O(1) or O(log n) per-lookup on average, depending on whether they are using a hash map or a tree in their implementation). So, as an example:

var array1 : Array = // ... first array
var array2 : Array = // ... second array

// Build up dictionary of items in array1
var array1_presence_dictionary : Object = new Object();
for each (var item : * in array1 ){
    array1_presence_dictionary[item] = item;
}

// Iterate over array2, constructing list of common and not common elements
var both : Array = new Array();
var only_in_array2 : Array = new Array();
for each (var item : * in array2 ){
      var key : String = String(item);
      if ( array1_presence_dictionary.hasOwnObject(key) ){
          both.push(item);
      }else{
          only_in_array2.push(item);
      }
}

Note that if you are doing this frequently, as in you really want to have a Set implementation, then you should simply store all your values in an Object or Dictionary. That will ensure that elements are not repeated... you simply add elements by assigning dict[item]=item;, and you delete using del dict[item];.

Answer 2

If you must do this, then Michael's way is probably best (although it will still be quite slow if it is run frequently or for large arrays). It will also need a minor change to give you the array only_in_array1, since array1_presence_dictionary is an object not an array. And since you won't be using array1_presence_dictionary later you can change the line array1_presence_dictionary[item] = item; to array1_presence_dictionary[item.itemNumber] = true;

Actually, now that I look at the code, there are quite a bit of minor errors, such as casting item to a String, resulting in the key [Object Class_Of_Item] which is not unique, etc. But those are just minor problems and does not affect the answer.

The best way would be to make a design change if possible. Either create 3 different arrays for add, update, remove, or for the item create a variable status that will be updated to say what needs to be done, and you can loop through just once checking item.status. There are many alternatives.