8
\$\begingroup\$

Test Case: Input- "I'm hungry!" Output- "!yrgnuh m'I"

Approach 1: In this approach, I used a empty string and bind it with the input string reversely.

public static class ReverseString {

   public static string Reverse (string input) {

    //bind the string to an empty string reversly
    var reversedString = "";

    //check if the input is empty
    if (input == "")
    {
        return "";
    } 
    else 
    {
        for (int i = input.Length - 1; i >= 0; i--)
        {
            reversedString += input[i];
        }
       return reversedString;
    }
  }
}

Approach 2: In this approach, I've created an empty char array which has the same length of the string. Then I've copied the value of string's last index to char array's first index and so on.

public static class ReverseString {
   public static string Reverse (string input) {

      char[] chars = new char[input.Length];

      for(int i = 0, j = input.Length -1; i <= j; i++, j--)
      {
        chars[i] = input[j];
        chars[j] = input[i];
      }

      return new string(chars);
   }
}

There are lots of approaches like this(without using built in library). But I wonder which one is the most recommended among programmers preferably C# programmers.Which one do you recommend and why?

\$\endgroup\$
  • 1
    \$\begingroup\$ Did you try timing them? \$\endgroup\$ – Solomon Ucko Jan 21 at 4:01
  • \$\begingroup\$ @SolomonUcko No Sir, I didn't :( \$\endgroup\$ – AKdeBerg Jan 21 at 5:19
  • 5
    \$\begingroup\$ @allo not in C#/.NET. Strings are immutable objects and to pin memory and play with its internal buffer, while possible, is doomed to break if implementation changes (for example, nothing dictates that a System.String` object cannot cache its hash-code). \$\endgroup\$ – Adriano Repetti Jan 21 at 9:37
  • 4
    \$\begingroup\$ @AKdeBerg first approach is possibly terrible from a performance point of view (N + 1 useless allocations + copies). Approach 2 might be GREATLY simplified or, even better you can use a StringBuilder. However the question is: do you have any constraint about string content? Because a .NET string is an array of code units which simply cannot be reversed (think about Unicode surrogates) or characters composed by multiple code points (all those emojis and some CJK characters). There are diacritics and so on (like accents, for example). Not to mention RTL languages and much much more... \$\endgroup\$ – Adriano Repetti Jan 21 at 9:41
  • 5
10
\$\begingroup\$

Performance

I didn't believe that the LINQ method could be faster, and I would never trust a profiler to give an accurate result (for numerous reasons), so I ran a benchmark with BenchmarkDotNet, and got the opposite result from tinstaafl. (Code in a gist)

Here are the results. Linq is as tinstaafl's, StringBuilder is as Joe C's, Char2 is as OP's second method, Char1a and Char1b are variations of what I would have suggested off-hand. On this machine (old i7), under .NET Core 2.1, in a dedicated benchmark, the OP's code was significantly faster than the Linq and StringBuilder methods. (Results may be very different under .NET Framework)

                Method |            TestString |         Mean |      Error |    StdDev |
---------------------- |---------------------- |-------------:|-----------:|----------:|
           ReverseLinq |                       |    81.472 ns |  0.1537 ns | 0.1284 ns |
         ReverseChar1a |                       |     7.946 ns |  0.1156 ns | 0.1081 ns |
         ReverseChar1b |                       |     7.518 ns |  0.0177 ns | 0.0157 ns |
          ReverseChar2 |                       |     7.507 ns |  0.0232 ns | 0.0206 ns |
 ReverseStringBuilders |                       |    12.894 ns |  0.1740 ns | 0.1542 ns |
           ReverseLinq |  It's (...)ow it [39] |   671.946 ns |  1.9982 ns | 1.8691 ns |
         ReverseChar1a |  It's (...)ow it [39] |    61.711 ns |  0.0774 ns | 0.0604 ns |
         ReverseChar1b |  It's (...)ow it [39] |    61.952 ns |  0.2241 ns | 0.1986 ns |
          ReverseChar2 |  It's (...)ow it [39] |    48.417 ns |  0.0877 ns | 0.0732 ns |
 ReverseStringBuilders |  It's (...)ow it [39] |   203.733 ns |  0.7540 ns | 0.6684 ns |
           ReverseLinq |               Magpies |   235.176 ns |  0.5324 ns | 0.4446 ns |
         ReverseChar1a |               Magpies |    23.412 ns |  0.0979 ns | 0.0916 ns |
         ReverseChar1b |               Magpies |    24.032 ns |  0.0582 ns | 0.0544 ns |
          ReverseChar2 |               Magpies |    22.401 ns |  0.1193 ns | 0.0996 ns |
 ReverseStringBuilders |               Magpies |    44.056 ns |  0.1313 ns | 0.1097 ns |
           ReverseLinq | ifhia(...) oiha [432] | 4,102.307 ns | 10.4197 ns | 9.2368 ns |
         ReverseChar1a | ifhia(...) oiha [432] |   454.764 ns |  1.0899 ns | 1.0195 ns |
         ReverseChar1b | ifhia(...) oiha [432] |   453.764 ns |  2.3080 ns | 2.0460 ns |
          ReverseChar2 | ifhia(...) oiha [432] |   400.077 ns |  1.0022 ns | 0.7824 ns |
 ReverseStringBuilders | ifhia(...) oiha [432] | 1,630.961 ns |  6.1210 ns | 5.4261 ns |

Note: never used BenchmarkDotNet before... hopefully I've not misused/misunderstood it in any way (please comment if I have), and hopefully it is good at it's job.

Commentary

Performance is not everything. The linq method is the most compact, and the hardest to get wrong, which is very good. However, if performance is important, than you need to profile the method as realistically as possible. The results above may not generalise. However, I'd be very surprised if the StringBuilder and Linq methods out-performed any of the char-array based methods ever, because they just incur a fair amount of overhead (i.e. probably a dynamic array, and probably a second copy in the LINQ case (not to mention the general enumeration overhead)).

Personally, I have no issue with your second piece of code. It may not be the most obvious implementation ever, but it doesn't take long to work out, and it's not a method whose job is going to change any time soon, so I'd worry much more about its API than its internals. That said, the API is a problem, as Adriano Repetti has mentioned: the behaviour of this method is going to create problems as soon as you start trying to reverse non-trivial Unicode. Simply, 'reverses a string' is a deficient contract.

\$\endgroup\$
  • \$\begingroup\$ Wow!! Thanks for the details.. \$\endgroup\$ – AKdeBerg Jan 21 at 10:52
  • 2
    \$\begingroup\$ The OP's approach #2 is pretty close to the usual in-place reversal (walk two pointers or indices in from the ends until they cross), just with a new destination instead of doing it in-place. It's probably no more efficient than a single read-backward / write-forward loop (or the reverse), though. It's kind of like unrolling a one-way loop by going both directions at once. For large inputs, hardware prefetching on Intel CPUs can track one forward stream and one backward stream per 4k page for prefetch into L2 cache. \$\endgroup\$ – Peter Cordes Jan 21 at 14:09
  • 1
    \$\begingroup\$ Of course for performance you'd want it to auto-vectorize with x86 SSSE3 pshufb, to load/store 16 bytes at once and reverse them in chunks of 2 bytes (.NET chars). That's maybe more likely without the meet-in-the-middle behaviour. (I think I have it right that a char in .NET is a fixed-width 16-bit type (Char size in .net is not as expected?), so even the scalar implementation breaks UTF-16 surrogate pairs forming one Unicode codepoint, as well as strings containing a reverse-text-direction character or whatever.) \$\endgroup\$ – Peter Cordes Jan 21 at 14:14
  • 1
    \$\begingroup\$ @PeterCordes indeed; the other 2 things I tested were a one-way reversal; I thought maybe it would play better with the optimisation, but apparently not. Yeah, char is like wchar; one UTF-16 code point. You're right, this is by no means the most aggressive approach for performance (further optimisation will quickly increase complexity), but a factor of 10 is probably worth getting the right way round ;) - I've just had a quick look at the assembly produced, and nothing exciting jumps out at me, so it's not doing anything too smart underneath. \$\endgroup\$ – VisualMelon Jan 21 at 14:41
  • 1
    \$\begingroup\$ *code unit; not code point! \$\endgroup\$ – VisualMelon Jan 21 at 14:48
10
\$\begingroup\$

Clarity of Approaches

With the first approach, I look at it and I can tell straight away that you are reversing a string. With the second approach, I need to study it for a minute or two to work out what you're doing.

Unnecessary Code

In the first approach, the check for an empty string is not necessary. In this case, your logic will not even enter the for loop, resulting in an empty string being returned anyway.

Performance

As you may know, strings are immutable objects in .Net. It is good practice to use a StringBuilder to create strings in this way, like so:

var reversedString = new StringBuilder(input.Length);
for (int i = input.Length - 1; i >= 0; i--)
{
    reversedString.Append(input[i]);
}
return reversedString.ToString();
\$\endgroup\$
  • 9
    \$\begingroup\$ Can't you tell your string builder to expect to hold input.Length characters? \$\endgroup\$ – einpoklum Jan 20 at 23:08
  • 3
    \$\begingroup\$ Honestly, if I see a method called ReverseString.Reverse(string input) I'd have a fair idea of what it's doing regardless of the method body :) \$\endgroup\$ – Steven Eccles Jan 21 at 9:50
  • \$\begingroup\$ @einpoklum Thanks for the suggestion. I've edited accordingly. \$\endgroup\$ – Joe C Jan 21 at 20:14
  • \$\begingroup\$ @JoeC: And I don't even know C#.... :-P \$\endgroup\$ – einpoklum Jan 21 at 20:35
  • \$\begingroup\$ @einpoklum I've not used it for half a decade either. I had to look up whether such a thing existed in .Net (I'm normally a Java developer). \$\endgroup\$ – Joe C Jan 21 at 20:37
9
\$\begingroup\$

I would recommend neither of the approaches. Strings in .NET are a rather unfortunate data structure, they consist of UTF-16 units. This unfortunately exposes the peculiarities of the UTF-16 encoding to the programmer, which will in particular cause problems if your string contains characters from the Unicode astral planes (code points U+10000 and up). These are expressed as pairs of two surrogates, which when reversed will be invalid. There are also issues with combining diacritics: simply reversing the order of code points may result in a combining diacritic being associated with a different letter, or even no letter at all.

Since reversing a sequence of UTF-16 units is not a meaningful operation for textual data, the approach I would take is to use the built-in functionality to slice strings by text elements. This can be done using the System.Globalization.StringInfo class:

public static string Reverse(string source)
{
    var info = new StringInfo(source);
    var sb = new StringBuilder(source.Length);
    for (var i = info.LengthInTextElements; i-- > 0;)
    {
        sb.Append(info.SubstringByTextElements(i, 1));
    }

    return sb.ToString();
}

As noted in the comments, Unicode also supports control structures like bidirectional overrides and interlinear annotations that would end up with their delimiters in the wrong order after this routine. This would require further parsing of the output to switch the start and end characters for these control structures (in particular, the bidirectional characters can represent nested levels of LTR and RTL ordering).

Edit 23.01.19: another thing to note is that some scripts have specific rules about the characters depending on where they are in the word. For example the Greek lowercase letter sigma has a different shape if it is at the end of the word, and is encoded with a different code point in each scenario (U+03C3 GREEK SMALL LETTER SIGMA vs U+03C2 GREEK SMALL LETTER FINAL SIGMA). This will not be taken into account by the above routine, e.g. if you reverse the word "στάσις" you will end up with "ςισάτσ" not "σισάτς". If you require the reversal to take this kind of thing into account you are up for a very large challenge!

Moral of the story: Unicode is hard. This is not Unicode's fault: it is a consequence of the fact that text is hard.

\$\endgroup\$
  • 2
    \$\begingroup\$ That is StringInfo use is cool, I didn't know that was a thing; but even so if the string has a right-to-left-override marker in it - in PowerShell terms "first$([char]8238)second" | Set-Clipboard to make one (PS strings are .Net strings too), then paste it into a browser, it renders as firstdnoces so when reversed it "should" look like secondtsrif but instead the RTL marker applies to the "wrong" thing and it renders as dnocestsrif \$\endgroup\$ – TessellatingHeckler Jan 21 at 20:24
  • \$\begingroup\$ @TessellatingHeckler - good point about the bidirectional overrides. They make things rather more complicated! \$\endgroup\$ – mistertribs Jan 21 at 20:28
  • 1
    \$\begingroup\$ Welcome to CR! Excellent contribution, thanks for chipping in! So... this reverses unicode astral-plane happy-face emojis into frown-face emojis? \$\endgroup\$ – Mathieu Guindon Jan 21 at 20:54
  • \$\begingroup\$ @MathieuGuindon - reversing the mood of the emojis would take quite a bit more work! There seems to be an ever-increasing number of them to take care of... \$\endgroup\$ – mistertribs Jan 21 at 21:47
8
\$\begingroup\$

I like the char[] approach, since it allocates the memory all at once and only makes one string. However using the LINQ extension method(return new string(input.Reverse().ToArray());) seems to do the same job in a fraction of the time according the .net profiler.

\$\endgroup\$
  • \$\begingroup\$ Fast and a readable one-liner? sounds good to me. \$\endgroup\$ – Baldrickk Jan 21 at 10:31
  • \$\begingroup\$ @VisualMelon's microbenchmark results indicate that this performs horribly, like an order of magnitude worse than the OP's version #2 meet-in-the-middle copy into a new array. If that's correct, you'd only want to use this in cases where performance doesn't matter, unfortunately. \$\endgroup\$ – Peter Cordes Jan 21 at 14:20

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.