how to optimize search difference between array / list of object

Question

Premesis: I am using ActionScript with two arraycollections containing objects with values to be matched...
I need a solution for this (if in the framework there is a library that does it better) otherwise any suggestions are appreciated...

Let's assume I have two lists of elements A and B (no duplicate values) and I need to compare them and remove all the elements present in both, so at the end I should have

• in A all the elements that are in A but not in B
• in B all the elements that are in B but not in A

now I do something like that:

            for (var i:int = 0 ; i < a.length ;)
            {
                var isFound:Boolean = false;
                for (var j:int = 0 ; j < b.length ;)
                {
                    if (a.getItemAt(i).nome == b.getItemAt(j).nome)
                    {
                        isFound = true;
                        a.removeItemAt(i);
                        b.removeItemAt(j);
                        break;
                    }
                    j++;
                }
                if (!isFound)
                    i++;
            }

I cycle both the arrays and if I found a match I remove the items from both of the arrays (and don't increase the loop value so the for cycle progress in a correct way)

I was wondering if (and I'm sure there is) there is a better (and less CPU consuming) way to do it...

Answer 1

If you must use a list, and you don't need the abilities of arraycollection, I suggest simply converting it to using AS3 Vectors. The performance increase according to this (http://www.mikechambers.com/blog/2008/09/24/actioscript-3-vector-array-performance-comparison/) are 60% compared to Arrays. I believe Arrays are already 3x faster than ArrayCollections from some article I once read. Unfortunately, this solution is still O(n^2) in time.

As an aside, the reason why Vectors are faster than ArrayCollections is because you provide type-hinting to the VM. The VM knows exactly how large each object is in the collection and performs optimizations based on that.

Another optimization on the vectors is to sort the data first by nome before doing the comparisons. You add another check to break out of the loop if the nome of list b simply wouldn't be found further down in list A due to the ordering.

If you want to do MUCH faster than that, use an associative array (object in as3). Of course, this may require more refactoring effort. I am assuming object.nome is a unique string/id for the objects. Simply assign that the value of nome as the key in objectA and objectB. By doing it this way, you might not need to loop through each element in each list to do the comparison.