0

I am trying to find a fast method for comparing two arrays and returning the difference in elements of the arrays. I came up with something of N2, but with few more loops, is there a better way to do this?

/**
* Return the difference of two arrays
* 
* @param {Array} other, the second array to be compared
* @param {Funciton} comparison_function, callback function for comparisons
* @returns {Array} 0 -- indexes of elements only in the first array 
*                  1 -- indexes of elements only in the second array
*/
Array.prototype.difference = function(other, comparison_function){
    comparison_function = comparison_function || function(a,b){ return a == b;};
    var extra = [],
        matched = []
        element_found = false;
    // fill matched with all values
    for(var _j = 0; _j < other.length; _j++){matched.push(_j);}
    for(var _i = 0; _i < this.length; _i++){
        element_found = false;
        for(var _j = 0; _j < other.length; _j++){
            if(comparison_function(this[_i], other[_j])){
                matched[_j] = undefined;
                element_found = true;
                break;
            }
        }
        if(!element_found) extra.push(_i);
    }
    return [extra, matched.filter(function(x){ return x !== undefined })];
}
xcorat
  • 1,434
  • 2
  • 17
  • 34
  • 3
    This question appears to be off-topic because it belongs to [Code Review](http://codereview.stackexchange.com). – Jon Jun 20 '14 at 22:49
  • possible duplicate of [JavaScript array difference](http://stackoverflow.com/a/4026828/341201) – feeela Jun 20 '14 at 22:51
  • @feeela what i want is not only extra elements in the array, but also the missing elements, the question you referenced have only extra elements – xcorat Jun 20 '14 at 23:00
  • And i don't think im asking to review my code, whats the difference between this and if I had asked the best way to get the difference between arrays without posting wht i have? – xcorat Jun 20 '14 at 23:07

1 Answers1

1

The algorithm you're running would take O(n^2) time. It's much better to just sort the two arrays and then find the difference in a way similar to merging. That would take O(n*logn) time.

aa333
  • 2,556
  • 16
  • 23
  • hmm... but then you need a way to sort, wouldn't that take longer for shorter arrays? – xcorat Jun 20 '14 at 23:03
  • 1
    How short are your arrays? If some array is too small then sorting by say quicksort, does take longer, but in that case you can just sort by direct comparisons. You could probably select the sorting algorithm based on how long the array is. But still sorting would win over O(n^2). – aa333 Jun 20 '14 at 23:09