Selective Array Reversing

Question

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?

Answer 1

• 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.

Answer 2

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.

Answer 3

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)];
}