1

I thought the fastest way to reverse a string is using just a for loop. but after measuring execution time, It turns out that Convert this to an array, reversing it then join it is faster which is not reasonable as far as I know.

This is how I measured

const { PerformanceObserver, performance } = require("perf_hooks");

var t0 = performance.now();

var reverse = function (x) {
  x = x.toString();
  result = "";
  for (let i = x.length - 1; i >= 0; i--) { // O(n)
    result += x[i];
  }
  return;
};

reverse(1534236469);
var t1 = performance.now();
console.log("took " + (t1 - t0) + " milliseconds.");

var t3 = performance.now();

var reverse = function (x) {
  const xStrArr = Math.abs(x).toString().split(""); O(n)
  const reversStr = xStrArr.reverse().join(""); O(2n)
  return;
};

reverse(1534236469);
var t4 = performance.now();
console.log("took " + (t4 - t3) + " milliseconds.");

How could second execution, O(3n) be faster than O(n)? Can someone explain to me?

Shawn
  • 367
  • 4
  • 13
  • 2
    The loop will keep allocating more and more strings each iteration. You might just be seeing the effect of GC cleaning up old ones. – VLAZ Mar 29 '21 at 07:41
  • [I think this is the same as this. Kindly check the link](https://stackoverflow.com/questions/958908/how-do-you-reverse-a-string-in-place-in-javascript) – CThru Mar 29 '21 at 07:43
  • To measure it, you should isolate the tests without running sequentially – Manuel Spigolon Mar 29 '21 at 07:44
  • 1
    `.reverse()` is a native method that can be much more highly optimized (perhaps even entirely native code) than constructing your own Javascript to reverse the string manually. – jfriend00 Mar 29 '21 at 07:44
  • 1
    If you express complexity using the `O` notation, you should know that `O(n) === O(3n)`, so beyond having linear time complexity, either could be faster. – FZs Mar 29 '21 at 07:44
  • Also, there is no `O(3n)`. It's just `O(n)`. When it comes to complexity, there is no real use to count anything but the highest growth rate and discard constants. Two `O(n)` functions *even if they perform a single loop*, are not likely to have the same execution time. If one takes 1ms per iteration, the other 2ms per iteration, the execution time would differ but *the growth rate* doesn't. That's what complexity measures. – VLAZ Mar 29 '21 at 07:45
  • 1
    Plus, `result += x[i];` inside a loop is a sub-optimal way to construct a string as it keeps having to grow the memory required and copy the string to the new memory location. – jfriend00 Mar 29 '21 at 07:48
  • @Nick [This one](https://stackoverflow.com/a/26610963/)? Are you sure that performance analysis is *valid*? Because it's a lot of years out of date. It compares IE9 vs FF7 and Chrome 15. There have been huge steps taken to runtime optimisation since then. JIT is a thing nowadays. – VLAZ Mar 29 '21 at 07:49
  • @VLAZ my bad, I hadn't noticed just how old it was. I'll retract vote and comments – Nick Mar 29 '21 at 07:50
  • @jfriend00 yep. It'd be `O(n^2)` in terms of space complexity, yet GC runs might skew that heavily. I remember testing straight string concatenation vs StringBuilder in Java a long time ago and it opened my eyes to just *how slow* string concatenation can be. Over the same big dataset changing this one thing lead to a runtime difference of something like 5-ish minutes (concatenation) to 20-ish seconds (StringBuilder). Same thing happens in JS but there is no dedicated string builder. I'd expect an array join to be much much more optimised, though. – VLAZ Mar 29 '21 at 08:06
  • FYI, because strings are immutable in Javascript (you can't modify an existing string, you can only create a new one that contains a modification), the language tends to not be very efficient at doing your own string manipulation in Javascript, particularly any type of building a string in a loop. – jfriend00 Mar 29 '21 at 08:06
  • @VLAZ - I doubt we're seeing the results of GC here. This is a really, really small amount of memory and the GC isn't very likely to interrupt the second performance run just to do some GC work when there's tons of memory still available. When I do 100 runs of each, separated by a 2 second `setTimeout()`, I get very consistent results where the second option is 20-30% faster. If I reverse the order the two tests run, I still get the `.reverse()` option to be 20-30% faster. I don't think this is dominated or significantly affected by GC. – jfriend00 Mar 29 '21 at 08:08
  • for a string like 'hello world', ```'hello world'.split('').reverse().join('')```... – bloo Mar 29 '21 at 08:13
  • @jfriend00 hmm, you're probably right. I didn't read through the test case well enough, I just assumed it's run in a loop a large amount of times, since that's what most performance testing does. In that case, this is a microbenchmark that might be going wrong for any amount of reasons. And it's also not doing a JIT warm-up. Your test sounds more reliable and still not very surprising. – VLAZ Mar 29 '21 at 08:20

1 Answers1

1

This can be as another solution example, here as you can see time complexity is O(n/2) which is asymptotic to O(n)

var reverse = function (x) {
  const length = x.length;
  for(let i = 0; i < Math.floor(length / 2); i++) {
    const temp = x[i]
    x = x.substring(0, i) + 
      x.charAt(length - i - 1) +  
      x.substring(i + 1, length - i - 1) + 
      temp + 
      x.substring(length - i)
  }
  return x
};
Hovakimyan
  • 510
  • 3
  • 10