Best way to reverse string

Question

Hi

We can use reverse from algorithm to reverse the string. Is that efficient most way ?

Refer code below where I tried two other options :

Obviously first method use stack so even if it is efficient, not a good choice as it need extra space of N and also adds burden to push and pop

Does second method is faster than reverse ? If yes , still this implementation is not correct as it involves VLA (variable length array ) which does not work on standard c++. So again overhead of heap allocation for this implementation.

In short , what is best way to reverse string?
https://code.sololearn.com/cZ2Xoe102hCS/?ref=app

Answer 1

I usually wouldn't see a direct reason to doubt the standard library. Since its algorithms are used extensively, I would assume they are tested and optimized accordingly. And if in doubt, benchmark.
I modified the program a little bit:

https://code.sololearn.com/ca110a19a1A2

Here are the results on my machine:

Compiled in debug mode, no special optimizations enabled, targeted at a 64-bit architecture:

Stack: 4.0902 seconds
VLA: 0.614992 seconds
Traversal: 0.461058 seconds
Constructor: 2.33255 seconds
Reverse: 1.08326 seconds

Compiled in release mode, optimized for more speed -O2, targeted at a 64-bit architecture:

Stack: 0.35568 seconds
VLA: 0.152778 seconds
Traversal: 0.0810989 seconds
Constructor: 0.123869 seconds
Reverse: 0.0743707 seconds

Interestingly, in debug mode the manual loop traversal suggested by @gitkp is twice as fast as std::reverse(), although both implement the exact same algorithm. Maybe because the iterator interface abstracts away more? Also the VLA method beats many others despite its overhead, I would guess it is more efficient because the memory can be copied in bulks?

However, it definitely falls behind with optimizations enabled. Traversal, and Reverse both offer almost the same speed, although std::reverse() performs marginally better for me.

Perhaps unsurprisingly, Stack and Constructor perform the worst out of all the methods in both versions.

I am absolutely no expert when it comes to such optimizations, but still some interesting results in my opinion. However, I would think that as long as you choose a somewhat sensible method (i.e. not Stack, and maybe not Constructor), a O( n ) algorithm like this should never be the source of a bottleneck in your application, and then there is no need to over-engineer stuff like this.

EDIT: The Copy method is undefined behaviour and will not work correctly. I removed it from the code/ benchmark.

Answer 2

Martin Taylor interesting answer there. Didn't knew. Learnt a lot from that SO ,answer

Answer 3

Take two variables iterate first variable from start till less than 2nd variable and 2nd variable from end of array till greater than first variabke and swap them on each iteration.

Answer 4

Actual complexity is n/2 and space complexity is just for new 2 variables that's it. You can even swap two variables without extra 2 variables just by adding subtracting values

Answer 5

https://code.sololearn.com/cxu9QL379Q8H/?ref=app

Answer 6

Thanks gitkp , Martin Taylor ,Mirielle[ Exams ] Nd Shadow

Answer 7

That's great gitkp ... However, is strlen itself not having O(n) resulting to total of O(n)?