Reverse a String - 3 solutions - unexpected efficiency [SPOILERS]

For anyone who has yet to solve Reverse a String, just ignore this post.

OK, so I finished this challenge back in January when I was first going through the Basic Algorithm challenges and came up with the following fairly simple solution:

var reverseString_v1 = function(s) {
  for (var rev='',i=s.length-1; i >=0;i--)  rev += s[i];
  return rev;
};

This can also be solved with a more functional approach by converting the string to arrayswhich is less efficient for large strings (1,000,000+ characters) with the following:

var reverseString_v2 = s => s.split('').reverse().join(''); 

Anyway, lately I have been going back through my old challenge solutions in the basic and intermediate sections after completing the advance algorithm challenges and trying to make my solutions more readable and/or more efficient. When I looked back at this challenged, I wondered if I could modify the first version (at the top) faster for very large strings. I came up with the following solution which seemed to me like it would take about half the time to run as the first version:

var reverseString_v3 = function(s) {
  var midpoint = Math.floor(s.length/2);
  for (var rev1='',rev2='',i=midpoint-1,j=s.length-1; i >= 0;) {
    rev1 += s[i--];
    rev2 += s[j--];
  }
  return s.length&1 ? rev2+s[midpoint]+rev1 : rev2+rev1;
};

After running several tests with various string sizes (100 up to 1,000,000 characters) I found for 1000 to 1,000,000 characters the 3rd version ranged between 2-4 times as fast as the 1st version. I kept stepping up the number of characters in my testing by 1,000,000 each time. From 6,000,000 to 9,000,000 characters, version 3 was only 40% faster. When I am went to 10,000,000 (ten million) characters, all of the sudden version 3 was twice as SLOW as version 1.

Can someone explain why it slowed down so dramatically once reach around ten million characters?

Note: I ran all of my tests running node from the command line on a new windows 10 machine with 32 GB of RAM in case that is important.

I’m actually surprised that there’s any measurable difference between v1 and v3 at all. How many times did you run each test?

100 times at each # characters. It makes sense to me that since I am only iterating half as many times as the length of the string, it would be faster in version #3. Version #3 is significantly faster than Version #1 up to about 1,000,000 characters.

Either way, it was fun trying a completely different solution to the problem.

would putting the concatenation within the for loop make it faster? rev += s[i--] instead of just i-- and leave the body blank { }

Not really sure what you are saying. The concatenation does occur within the for loop. As far as putting the i-- at the top of the loop or where the concatenation would not change anything. That is just another way of writing the same code.

My actual question was why my version #3 was faster than version #1 up to a certain number of characters, but then slows down dramatically around ten million characters.

okay cool, thanks for responding. just curious. :slight_smile:

It’s maybe because of the type of the iterators (i and j) in memory (short, int, long, double like in C) !?