3
\$\begingroup\$

I have the following code that given an array, returns the reversed version of the array, reverse portions of the array.

For example

selReverse([1,2,3,4,5,6], 2)
//=> [2,1, 4,3, 6,5]


function selReverse(array, length) {
  console.log(array)
  var resultArray = [];
    for (var i = 0, j=array.length ; i < j; i += length) {
      resultArray.push.apply(resultArray, array.slice(i, i+length).reverse());
    }
  return resultArray;
}

This code passes the tests, but apparently, it's too slow. Is there a way to optimize it?

\$\endgroup\$
6
  • \$\begingroup\$ I'm not clear on what, exactly, is selective about this. What algorithm is it applying? Based on the result, it seems like it's reversing every length-length subsection; is that correct? If so, please edit your question to explain that. Thanks! \$\endgroup\$
    – Nic
    Apr 22, 2017 at 15:00
  • \$\begingroup\$ Why is it to slow? Is this part of a programming challenge, or something similar? Please explain, and add which programming challenge if that is the case. \$\endgroup\$
    – holroy
    Apr 22, 2017 at 15:34
  • \$\begingroup\$ @QPaysTaxes that's exactly what it does! That's what I meant by it reverses portions of the array. \$\endgroup\$
    – callback
    Apr 22, 2017 at 16:36
  • \$\begingroup\$ @holroy my code fails in codewars.com/kata/selective-array-reversing/train/javascript it apparently exceeds the 12000 ms maximum runtime. \$\endgroup\$
    – callback
    Apr 22, 2017 at 16:37
  • \$\begingroup\$ 12 seconds...? Wow, that's slow. :P \$\endgroup\$
    – cHao
    Apr 22, 2017 at 17:24

3 Answers 3

4
\$\begingroup\$
  • Don't put console.log calls in you functions unless there's a really good reason to. In this case, you're just printing the input, which is pretty pointless. It can also contribute greatly to the function's running time, since printing a large array isn't exactly free (a lot depends on how the runtime handles output)

  • You can simplify the code. You can do without slicing, reversing and applying chunks of the array

I'd just use two for-loops:

function selReverse(array, chunkSize) {
  var output = [],
      l = array.length;

  for(var i = 0 ; i < l ; i += chunkSize) {
    var start = Math.min(i + chunkSize, l) - 1;
    for(var j = start ; j >= i ; j--) {
      output.push(array[j]);
    }
  }
  return output;
}

Edit: The code above doesn't work, but I thought it was due to very large inputs or something, but that's not the case.

The simple solution is basically, that the for loop - both in my code and the original code - goes into an infinite loop if the chunkSize is zero. This works, though:

function selReverse(array, chunkSize) {
  var output = [],
      l = array.length;

  if(chunkSize === 0) return array.slice(); // could also do <= 0 to be safer

  for(var i = 0 ; i < l ; i += chunkSize) {
    var start = Math.min(i + chunkSize, l) - 1;
    for(var j = start ; j >= i ; j--) {
      output.push(array[j]);
    }
  }
  return output;
}

Since it's got nothing to do with large inputs, I imagine the original code works just as well, as long as it too checks for the chunkSize.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the reply, unfortunately your code didnt go through the tests either. I still get Process was terminated. It took longer than 12000ms to complete \$\endgroup\$
    – callback
    Apr 22, 2017 at 19:59
  • 1
    \$\begingroup\$ @callback Ah, I see the issue. I'll update the answer \$\endgroup\$
    – Flambino
    Apr 22, 2017 at 20:03
  • 1
    \$\begingroup\$ OH !!! So that's the problem! With length === 0 :D Well now my code also works fine when I return the same array if length === 0 ! Thanks for opening my eyes to it. \$\endgroup\$
    – callback
    Apr 22, 2017 at 20:09
1
\$\begingroup\$

I came up with something yet faster than both you and @Flambino, but it still gives me timeout. EDIT: The problem was infinite loop in one of the cases. Thanks to @Flambino for spotting it. Anyway, another way to do it, would be:

const selReverse = (array, length) => {
  let result     = [],
      sliceStart = 0;

  if (length === 0) {
    return array;
  }

  while (sliceStart < array.length) {
    result = result.concat(array.slice(sliceStart, sliceStart + length).reverse());
    sliceStart += length;
  }

  return result;
};

The above code concatenates buffer array (result) with reverse of slice of input array.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for trying. Actually mine passes 6 tests before reaching 12 seconds. Yours passes only until 5. \$\endgroup\$
    – callback
    Apr 22, 2017 at 20:06
  • 1
    \$\begingroup\$ @callback The test order is likely randomized. The thing that makes all these solutions fail (this one, yours, and my first one - just updated) is that one of the tests pass a length/chunk size of zero, causing an infinite loop \$\endgroup\$
    – Flambino
    Apr 22, 2017 at 20:07
  • \$\begingroup\$ Ah, of course. That explains everything. Thanks! \$\endgroup\$
    – Przemek
    Apr 22, 2017 at 20:15
1
\$\begingroup\$

Style

  • Instead of writing resultArray.push.apply I would go with the shorter and more idiomatic [].push.apply or directly access the prototype via Array.prototype.push.apply.

  • Instead of including type information in variable names as invar resultArray I recommend the shorted var result.

  • Instead of the less self-explanatory for (var i = 0, j = array.length; i < j; i += length) I would choose a more descriptive name for j such as end to better distinguish from loop iterators.

Performance

  • Replacing resultArray.push.apply with resultArray.concat improves performance for longer arrays. It leads to a 6% performance improvement on Firefox 52 for the given example array.

  • Repeatedly calling slice and reverse causes constant memory allocations in order to hold the temporary array slices. Iteratively calling push and explicitly calculating the source index is much faster.

  • Some people view assigning array.length to a separate variable in loop headers as unnecessary, but according to https://jsperf.com/for-vs-length there is still a small performance improvement even on modern optimizing JavaScript engines.

  • Preallocating the resulting array and replacing result.push(...) with an assignment result[i] = ... could lead to better performance for very large arrays, but it reduces performance for small arrays on some JavaScript engines, e.g. in Chrome.

  • Handling the last portion of the array when the array.length is not a multiple of length could either be done in a separate loop after the main loop OR by adding some conditional logic to the main loop. Since JavaScript engines optimize loop bodies only after a few runs and a separate loop would require separate optimization, a single main loop with simple additional logic is usually faster.

The resulting optimized function below runs about 30x faster in Firefox 52 compared to the original code. It turns out to be pretty similar to Flambino's exemplary code apart from replacing Math.min with a ternary operator and pushing a subtractions out of the inner loop:

function selReverse(array, length) {
  if (length < 2) return array.slice();
  let result = [];

  for (let i = -1, end = array.length - 1; i < end; i += length) {
    for (let j = (i + length < end ? i + length : end); j > i; --j) {
      result.push(array[j]);
    }
  }
  return result;
}

console.log(selReverse([1,2,3,4,5,6], 2))

See https://jsperf.com/selreverse for performance comparisons.

PS: When length is a power of 2, you can optimize even further:

for (let i = 0, end = array.length; i < end; ++i) {
  result[i] = array[i ^ (length - 1)];
}
\$\endgroup\$

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.