3
\$\begingroup\$

I've been working on this task (see screenshot).

Codewars "Sum of Pairs" kata

Here's my answer to it so far:

var sum_pairs=function(ints, s){
  //your code here

  var ptr_1 = 0,
      ptr_2 = 0,
      i = 0,
      j = 0,
      len = ints.length,
      j_min = len,
      arr_sum = [];

  for (i; i < len-1; i++){
    for (j = i+1; j < len; j++){
      if(ints[i] + ints[j] === s){
        if (j < j_min){
          j_min = j;
          arr_sum = [parseInt(ints[i]), parseInt(ints[j])]
        }
      }
    }
  }

return ( (arr_sum.length === 0)? undefined : arr_sum ); 

}

However, while the tests all pass, it throws an STDERR about 'optimising the code':

STDERR about optimising my code

How might I be able to optimise my code further?

\$\endgroup\$
  • 1
    \$\begingroup\$ You have a for in a for while I'm pretty sure you don't need two. This is probably why it takes too long. \$\endgroup\$ – Mast Aug 9 '16 at 7:33
  • \$\begingroup\$ @Mast, can you show a one-loop solution? I think it's impossible unless you mean recursion, which is even slower due to invocation overhead. \$\endgroup\$ – wOxxOm Aug 9 '16 at 8:03
  • 1
    \$\begingroup\$ Recursion would be worse indeed. I'm thinking more along the lines of a map, filter or reduce. Recursion would be worse indeed. Unfortunately I'm not a JS expert, so you'll have to find someone else to enlighten you further. \$\endgroup\$ – Mast Aug 9 '16 at 8:05
  • \$\begingroup\$ But in case of map, reduce, filter function callbacks are required and in js it's expensive, and becomes noticeable in case of large number of iterations, which is the exact condition tested by the admission program. Anyway it'd be interesting to run comparative timing tests once someone submits a solution along these lines. \$\endgroup\$ – wOxxOm Aug 9 '16 at 8:21
3
\$\begingroup\$

Straightforward enumeration algorithms utilizing 2-layered loops will always take a lot of time on extremely large arrays where a possibility exists that the first match is achieved by elements near the start/end of the array (e.g. indices 515 and 9123456 of a 10 million elements array), which would lead to the same excessive number of iterations as the original code performed.

Here's an updated code that performs much faster on the average. The idea is to build a map of unique values and their minimal indices in the source array, and simultaneously check if there's an entry for the complementary number (addend) already.

var sum_pairs = function(ints, s) {
    var map = {},
        pair, pairMaxIndex = ints.length - 1;

    for (var i = 0; i <= pairMaxIndex; i++) {
        var a = ints[i];
        var b = s - a;
        var j = map[b];
        if (j !== undefined && i <= pairMaxIndex && j <= pairMaxIndex) {
            pairMaxIndex = i > j ? i : j;
            pair = i < j ? [a, b] : [b, a];
        }
        var tmp = map[a];
        if (tmp === undefined || i < tmp) {
            map[a] = i;
        }
    }
    return pair;
};

10 million randoms in -100..100 range: 1ms - 1000ms
10 million randoms in -1,000,000..1,000,000 range: 1ms - 5000ms
10 million randoms in -10,000,000..10,000,000 range: 1ms - crash
1 million randoms in -1,000,000,000..1,000,000,000 range: 1ms - 2000ms

The worst time in each case was caused by artificially crafting an array described above.
The crash in the 3rd test occured because the number of unique values neared 1G and the object exceeded 32-bit Javascript engine's memory limit of 2 GB. All tests were run on i7 CPU.

The code above incorporates the following optimizations as well:

  1. Flambino's answer shows there's no need to continue enumeration if current index is bigger than the matching values' max index found already.
  2. Jodrell's answer shows it's possible to do everything in just one loop, pointed out by Jonah.

And the tests:

console.clear();
var arr = [], max = 1000000;
for (var i = 0; i<10000000; i++) arr[i] = Math.random() * max * 2 - max |0;
console.log('array of', arr.length, 'elements is built');

console.time(1);
console.log(sum_pairs(arr, 1000));
console.timeEnd(1);
\$\endgroup\$
  • \$\begingroup\$ @Heslacher that was my initial thought - I was going to include that in my answer anyway. \$\endgroup\$ – Siobhan Aug 9 '16 at 9:07
  • \$\begingroup\$ Thanks. I've edited the answer and added a new algorithm. \$\endgroup\$ – wOxxOm Aug 9 '16 at 13:06
  • 1
    \$\begingroup\$ You don't even need to bother with the uniqueness part to make it pass. Memoizing the previous searches will be enough. \$\endgroup\$ – Jonah Aug 9 '16 at 19:50
  • 1
    \$\begingroup\$ See this solution: codereview.stackexchange.com/a/74187/35368. found holds the memo-ized values. The point is worrying about the duplicates is an optimization that's unlikely to matter, and it doesn't affect the big-oh running time. \$\endgroup\$ – Jonah Aug 9 '16 at 20:03
  • \$\begingroup\$ @Jonah, thank you, that's just beautiful in its simplicity and the performance gain: up to 5000x from my v2, which in turn was many-many times faster than a straightforward nested iteration. \$\endgroup\$ – wOxxOm Aug 9 '16 at 21:16
1
\$\begingroup\$
  • You have some declared variables you don't use (ptr_*). Not a performance issue at all, just a matter of cleanliness.

  • You calculate len-1 for each loop through the outer loop. Really, really minimal performance hit, but still: You don't need to. If i == len-1, then j+1 will be equal to len and the inner loop won't run anyway.

  • As was pointed out in a (now deleted) answer, there's no reason for parseInt. The fact that you do the addition and comparison to the target sum without using parseInt should tell you that you don't need it for the results array either.

  • Most importantly: Rather than break the loops, you complete the ints[i] + ints[j] === s calculation for every pairing even if you don't need to.

You have the j_min variable which is supposed to keep you from finding pairing "later" in the array. And it does - but you still calculate the pairing first.

So, if the array is 100 numbers long, you'll do 4950 additions and comparisons, even if the the first two numbers match the sum.

Even if you flip the two ifs around, and check j_min first, and only do a comparison, you'd still complete the loops all the way to len-1/len.

So instead of messing around with j_min, just lower the loop limit to j. It'll cause the inner loop to exit immediately after finding a pair, and reduce the iterations overall.

function sumPairs(values, target) { // or "sum_pairs", but camelCase is the JS convention
  var limit = values.length,
      result,
      i, j;

  for(i = 0 ; i < limit ; i++) {
    for(j = i+1 ; j < limit ; j++) {
      if(values[i] + values[j] == target) {
        result = [values[i], values[j]];
        limit = j;
      }
    }
  }

  return result;
}

I don't know if this is enough to meet the time limit for the crazy input, but maybe.


A possible alternative, depending on input: You could maybe filter the list to only include unique values (with the exception of target / 2, which may occur two or more times). Now, unique'ing the array only makes sense if there are a limited number of possible values (e.g. numbers 0-10). The more repetition there is, the more it makes sense. But if the array is already unique, it'll be a huge waste of time.

The problem statement doesn't mention what the possible input values are, so I don't know if it makes sense.

Anyway, the point would be that for an array like [4, 3, 2, 3, 4] with a target sum of 6, you'd reduce the array to [4, 3, 2, 3]. The 3 is there twice since it's half of the target value, and could prove useful, but the other numbers need only occur once. After filtering, you can use the same procedure as above to find matching pairs, but you'd be working with a smaller array... or not, depending on input.

\$\endgroup\$
  • \$\begingroup\$ In case the first match is achieved by elements near the start/end of the array (e.g. indices 5 and 9756 of a 10k array), this is gonna loop pretty much as many times as the OP's code. \$\endgroup\$ – wOxxOm Aug 9 '16 at 11:18
  • \$\begingroup\$ @wOxxOm True, it's a risk \$\endgroup\$ – Flambino Aug 9 '16 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.