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

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

#1

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.


#2

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


#3

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.


#4

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


#5

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.


#6

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


#7

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