what is the fastest way to reverse string in javascript?

Question

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?

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
– VLAZ, Commented Mar 29, 2021 at 7:41
.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
– jfriend00, Commented Mar 29, 2021 at 7:44
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
– FZs, Commented Mar 29, 2021 at 7:44
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
– jfriend00, Commented Mar 29, 2021 at 7:48

Hovakimyan · Accepted Answer · 2021-04-05 20:53:06Z

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

answered Apr 5, 2021 at 20:53

Hovakimyan

5583 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

what is the fastest way to reverse string in javascript?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related