Need to increase performance in function that finds earliest pair that equals a given sum

Question

I have a function that takes an array and a number. It scans the array for the two numbers that appear earliest in the array that add up to the number. I would like to know, performance-wise, what could help this function run faster. It has to process a list of like 10,000,000 items in under 6 seconds. I have refactored it a few times now, but still not getting there.

What is the best array iteration method for speed? I assumed for loops would be the slowest so I chose map. Is there a faster way? every()?

NOTE: the provided array could have duplicate, positive, or negative numbers (let's say up to 1000000...for now).

var low_pair = function (ints, s) {
    var lowNum = ints.length, lowMatch, highNum, clone = [], i;

    for (i = 0; i < ints.length; i++) {
        clone[i] = ints.map(function (n, ind) {
            if (ind !== i && ints[i] + n == s) {
                i > ind ? highNum = i : highNum = ind;
                if (highNum < lowNum) {
                    lowNum = highNum;
                    lowMatch = [ints[i], ints[ind]];
                }
            }
        });
    }
    return lowMatch;
};

Answer 1

We are going to create a function that returns the earliest pair of elements that add up to the needed sum:

function find_pair(l, s) {
    var min_indexes = {};
    for (var i = 0; i < l.length; i++) {
        var a = l[i];
        if ((s - a) in min_indexes)
            return [s - a, a];
        if (!(a in min_indexes))
            min_indexes[a] = i;
    }
}

For this purpose, for every number we process, we store its minimum index. If we currently process number a, we check if s - a has its minimum index set. If yes, this means we found our wanted sum and we return both elements.

For example:

> var l = [2, 3, 4, 5, 5, 7, 8]
> find_pair(l, 10)
[5, 5]
> find_pair(l, 6)
[2, 4]
> find_pair(l, 5)
[2, 3]
> find_pair(l, 15)
[7, 8]
> find_pair([5, 9, 13, -3], 10)
[13, -3]

Answer 2

What is the best array iteration method for speed?

See What's the fastest way to loop through an array in JavaScript? for that. But notice the answers there might be deprecated, and current engines are better at optimising different things. You should always benchmark yourself, in your own target environment.

However, instead of looking for raw speed and microoptimisations, you should try to improve your algorithm. In your case, you can double the speed of your function by simply starting the inner loop at i so you don't visit all combinations twice. Also, by returning early from the function you can speed up the average case (depending on your data). To find the "earliest pair" you don't have to loop through the entire array and calculate a minimum, you just have to iterate the pairs in the chosen order. If the data is ordered (or at least skewed to some distribution) you could take advantage of that as well.

I'd use

function firstPair(ints, s) {
    var len = ints.length;
    for (var end = 0; end < len; end++)
        for (var i=0, j=end; i<end; i++)
            if (i != --j && ints[i]+ints[j] == s)
                return [i, j];
    for (var start = 0; start < len; start++)
        for (var i=start, j=len; i<len; i++)
            if (i != --j && ints[i]+ints[j] == s)
                return [i, j];
    return null;
}

As suggested by the other answers, if the range of the values in your array is limited, you could drastically reduce the complexity of your algorithm by using a lookup table - trading memory for performance. Using a bitmap for already-occured integers, it could look like this:

function firstPair(ints, s) {
    var map = []; // or, if domain is known and typed arrays are supported, use
//  var map = new Uint16Array(Math.ceil(domainSize / 16));
    for (var i=0; i<ints.length; i++) {
        var x = ints[i],
            r = s - x;
        if (map[r >> 4] & (1 << (r & 0xF))) // get
            return [r, x];
        map[x >> 4] |= 1 << (x & 0xF); // set
    }
    return null;
}

Answer 3

The main problem is that your current function complexity is O(n^2) which is way too high for a 10000000 element array. The map function iterates through the entire array. So you make 10000000 * 10000000 = 100 trillion "operations". The complexity needs to be decreased. My best guess -> use a hash table within a linear loop. Below is my example code with a worst case test of 10 million elements that runs in around 8 seconds on my old machine. It makes only 10 million runs instead of 100 trillion.

<!DOCTYPE html>
<html>
<head>
<script type="text/javascript">
var low_pair = function (ints, s) {
    var found = {};
    var lowMatch;
    for (var i = 0; i < ints.length; i++) {
        var num = ints[i];
        var prevNum = s-num;
        if (found[prevNum] === true){
            if (prevNum>num){
                lowMatch = [num, prevNum];
            } else {
                lowMatch = [prevNum, num];
            }
            break;
        } else {
            found[num] = true;
        }
    }
    return lowMatch;
};
var test_array_size = 10000000;
var test_array = new Array(test_array_size);
for (var i=0;i<test_array_size;++i){
    test_array[i] = test_array_size-i;
}
console.log("Array initialized");
var start = new Date().getTime();
console.log(low_pair(test_array, 12));
var end = new Date().getTime();
console.log("Running time: "+(end-start)+" ms");
</script>
<head>
<body>
</body>
</html>

Answer 4

This function consistently runs a 50,000,000 items array in 0ms:

var low_pair = function (s) {
var ints = [];
for(var i = 0; i < 50000000; i++) {
    ints.push(Math.floor(Math.random() * 9));
}
console.time('pair');
var counter = 1;
for (var i = 0; i < ints.length; i++) {
    var sum = ints[i] + ints[counter];
    if (i !== counter) {
        if (sum === s) {
            console.timeEnd('pair');
            return console.log([ints[i], ints[counter]]);
        }
    }
    if (i == counter) {
        counter++;
        i = -1;
    }
}
console.time('pair');
console.log( undefined);
};