Лучший способ перевернуть строку
Мне просто нужно было написать функцию обратного преобразования строк в C# 2.0 (т. Е. LINQ недоступен) и придумал это:
public string Reverse(string text)
{
char[] cArray = text.ToCharArray();
string reverse = String.Empty;
for (int i = cArray.Length - 1; i > -1; i--)
{
reverse += cArray[i];
}
return reverse;
}
Лично я не в восторге от этой функции и уверен, что есть лучший способ сделать это. Есть?
53 ответа
public static string Reverse( string s )
{
char[] charArray = s.ToCharArray();
Array.Reverse( charArray );
return new string( charArray );
}
Здесь решение, которое правильно переворачивает строку "Les Mise\u0301rables" как "selbare\u0301siM seL", Это должно сделать так же, как selbarésiM seLне selbaŕesiM seL (обратите внимание на положение акцента), как и результат большинства реализаций, основанных на единицах кода (Array.Reverseи т. д.) или даже кодовые точки (обращая особое внимание на суррогатные пары).
using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
public static class Test
{
private static IEnumerable<string> GraphemeClusters(this string s) {
var enumerator = StringInfo.GetTextElementEnumerator(s);
while(enumerator.MoveNext()) {
yield return (string)enumerator.Current;
}
}
private static string ReverseGraphemeClusters(this string s) {
return string.Join("", s.GraphemeClusters().Reverse().ToArray());
}
public static void Main()
{
var s = "Les Mise\u0301rables";
var r = s.ReverseGraphemeClusters();
Console.WriteLine(r);
}
}
(И живой пример здесь: https://ideone.com/DqAeMJ)
Он просто использует.NET API для итерации кластера графемы, который был там с тех пор, но кажется немного "скрытым" от глаз.
Это оказывается удивительно сложным вопросом.
Я бы порекомендовал использовать Array.Reverse для большинства случаев, так как он изначально закодирован и его очень просто поддерживать и понимать.
Кажется, он превосходит StringBuilder во всех случаях, которые я тестировал.
public string Reverse(string text)
{
if (text == null) return null;
// this was posted by petebob as well
char[] array = text.ToCharArray();
Array.Reverse(array);
return new String(array);
}
Существует второй подход, который может быть быстрее для определенных длин строк, который использует Xor.
public static string ReverseXor(string s)
{
if (s == null) return null;
char[] charArray = s.ToCharArray();
int len = s.Length - 1;
for (int i = 0; i < len; i++, len--)
{
charArray[i] ^= charArray[len];
charArray[len] ^= charArray[i];
charArray[i] ^= charArray[len];
}
return new string(charArray);
}
Примечание. Если вы хотите поддерживать полную кодировку Unicode UTF16, прочтите это. И используйте реализацию там вместо этого. Он может быть дополнительно оптимизирован с помощью одного из приведенных выше алгоритмов и выполнения строки, чтобы очистить ее после обращения символов.
Вот сравнение производительности между методами StringBuilder, Array.Reverse и Xor.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace ConsoleApplication4
{
class Program
{
delegate string StringDelegate(string s);
static void Benchmark(string description, StringDelegate d, int times, string text)
{
Stopwatch sw = new Stopwatch();
sw.Start();
for (int j = 0; j < times; j++)
{
d(text);
}
sw.Stop();
Console.WriteLine("{0} Ticks {1} : called {2} times.", sw.ElapsedTicks, description, times);
}
public static string ReverseXor(string s)
{
char[] charArray = s.ToCharArray();
int len = s.Length - 1;
for (int i = 0; i < len; i++, len--)
{
charArray[i] ^= charArray[len];
charArray[len] ^= charArray[i];
charArray[i] ^= charArray[len];
}
return new string(charArray);
}
public static string ReverseSB(string text)
{
StringBuilder builder = new StringBuilder(text.Length);
for (int i = text.Length - 1; i >= 0; i--)
{
builder.Append(text[i]);
}
return builder.ToString();
}
public static string ReverseArray(string text)
{
char[] array = text.ToCharArray();
Array.Reverse(array);
return (new string(array));
}
public static string StringOfLength(int length)
{
Random random = new Random();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < length; i++)
{
sb.Append(Convert.ToChar(Convert.ToInt32(Math.Floor(26 * random.NextDouble() + 65))));
}
return sb.ToString();
}
static void Main(string[] args)
{
int[] lengths = new int[] {1,10,15,25,50,75,100,1000,100000};
foreach (int l in lengths)
{
int iterations = 10000;
string text = StringOfLength(l);
Benchmark(String.Format("String Builder (Length: {0})", l), ReverseSB, iterations, text);
Benchmark(String.Format("Array.Reverse (Length: {0})", l), ReverseArray, iterations, text);
Benchmark(String.Format("Xor (Length: {0})", l), ReverseXor, iterations, text);
Console.WriteLine();
}
Console.Read();
}
}
}
Вот результаты:
26251 Ticks String Builder (Length: 1) : called 10000 times.
33373 Ticks Array.Reverse (Length: 1) : called 10000 times.
20162 Ticks Xor (Length: 1) : called 10000 times.
51321 Ticks String Builder (Length: 10) : called 10000 times.
37105 Ticks Array.Reverse (Length: 10) : called 10000 times.
23974 Ticks Xor (Length: 10) : called 10000 times.
66570 Ticks String Builder (Length: 15) : called 10000 times.
26027 Ticks Array.Reverse (Length: 15) : called 10000 times.
24017 Ticks Xor (Length: 15) : called 10000 times.
101609 Ticks String Builder (Length: 25) : called 10000 times.
28472 Ticks Array.Reverse (Length: 25) : called 10000 times.
35355 Ticks Xor (Length: 25) : called 10000 times.
161601 Ticks String Builder (Length: 50) : called 10000 times.
35839 Ticks Array.Reverse (Length: 50) : called 10000 times.
51185 Ticks Xor (Length: 50) : called 10000 times.
230898 Ticks String Builder (Length: 75) : called 10000 times.
40628 Ticks Array.Reverse (Length: 75) : called 10000 times.
78906 Ticks Xor (Length: 75) : called 10000 times.
312017 Ticks String Builder (Length: 100) : called 10000 times.
52225 Ticks Array.Reverse (Length: 100) : called 10000 times.
110195 Ticks Xor (Length: 100) : called 10000 times.
2970691 Ticks String Builder (Length: 1000) : called 10000 times.
292094 Ticks Array.Reverse (Length: 1000) : called 10000 times.
846585 Ticks Xor (Length: 1000) : called 10000 times.
305564115 Ticks String Builder (Length: 100000) : called 10000 times.
74884495 Ticks Array.Reverse (Length: 100000) : called 10000 times.
125409674 Ticks Xor (Length: 100000) : called 10000 times.
Кажется, что Xor может быть быстрее для коротких строк.
Сверху 3.5 рамки
public string ReverseString(string srtVarable)
{
return new string(srtVarable.Reverse().ToArray());
}
Если строка содержит данные Unicode (строго говоря, не-BMP-символы), другие опубликованные методы повредят ее, потому что вы не можете поменять местами порядковые единицы высокого и низкого суррогатного кода при обращении строки. (Более подробную информацию об этом можно найти в моем блоге.)
Следующий пример кода правильно перевернет строку, содержащую символы, отличные от BMP, например, "\U00010380\U00010381" (Ugaritic Letter Alpa, Ugaritic Letter Beta).
public static string Reverse(this string input)
{
if (input == null)
throw new ArgumentNullException("input");
// allocate a buffer to hold the output
char[] output = new char[input.Length];
for (int outputIndex = 0, inputIndex = input.Length - 1; outputIndex < input.Length; outputIndex++, inputIndex--)
{
// check for surrogate pair
if (input[inputIndex] >= 0xDC00 && input[inputIndex] <= 0xDFFF &&
inputIndex > 0 && input[inputIndex - 1] >= 0xD800 && input[inputIndex - 1] <= 0xDBFF)
{
// preserve the order of the surrogate pair code units
output[outputIndex + 1] = input[inputIndex];
output[outputIndex] = input[inputIndex - 1];
outputIndex++;
inputIndex--;
}
else
{
output[outputIndex] = input[inputIndex];
}
}
return new string(output);
}
Хорошо, в интересах "не повторяйся" я предлагаю следующее решение:
public string Reverse(string text)
{
return Microsoft.VisualBasic.Strings.StrReverse(text);
}
Насколько я понимаю, эта реализация, доступная по умолчанию в VB.NET, правильно обрабатывает символы Юникода.
Начиная с.NET Core 2.1, появился новый способ обратить строку, используя string.Create метод.
Обратите внимание, что это решение не обрабатывает Юникод, комбинирующий символы и т. Д. Правильно, так как "Les Mise\u0301rables" будет преобразован в "selbarésiM seL". Другие ответы для лучшего решения.
public static string Reverse(string input)
{
return string.Create<string>(input.Length, input, (chars, state) =>
{
state.AsSpan().CopyTo(chars);
chars.Reverse();
});
}
Это по сути копирует персонажей input на новую строку и переворачивает новую строку на месте.
Почему string.Create полезно?
Когда мы создаем строку из существующего массива, выделяется новый внутренний массив и значения копируются. В противном случае можно было бы изменить строку после ее создания (в безопасной среде). То есть в следующем фрагменте мы должны выделить массив длиной 10 дважды, один в качестве буфера и один в качестве внутреннего массива строки.
var chars = new char[10];
// set array values
var str = new string(chars);
string.Create по существу, позволяет нам манипулировать внутренним массивом во время создания строки. Это значит, что нам больше не нужен буфер, и поэтому мы можем избежать выделения этого одного массива символов.
Стив Гордон написал об этом более подробно здесь. Также есть статья на MSDN.
Как пользоваться string.Create?
public static string Create<TState>(int length, TState state, SpanAction<char, TState> action);
Метод принимает три параметра:
- Длина строки для создания,
- данные, которые вы хотите использовать для динамического создания новой строки,
- и делегат, который создает последнюю строку из данных, где первый параметр указывает на внутренний
charмассив новой строки, а второй - данные (состояние), которые вы передалиstring.Create,
Внутри делегата мы можем указать, как новая строка создается из данных. В нашем случае мы просто копируем символы входной строки в Span используется новой строкой. Затем мы обращаем Span и, следовательно, вся строка перевернута.
Ориентиры
Чтобы сравнить предложенный мной способ обращения строки с принятым ответом, я написал два теста, используя BenchmarkDotNet.
public class StringExtensions
{
public static string ReverseWithArray(string input)
{
var charArray = input.ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}
public static string ReverseWithStringCreate(string input)
{
return string.Create(input.Length, input, (chars, state) =>
{
state.AsSpan().CopyTo(chars);
chars.Reverse();
});
}
}
[MemoryDiagnoser]
public class StringReverseBenchmarks
{
private string input;
[Params(10, 100, 1000)]
public int InputLength { get; set; }
[GlobalSetup]
public void SetInput()
{
// Creates a random string of the given length
this.input = RandomStringGenerator.GetString(InputLength);
}
[Benchmark(Baseline = true)]
public string WithReverseArray() => StringExtensions.ReverseWithArray(input);
[Benchmark]
public string WithStringCreate() => StringExtensions.ReverseWithStringCreate(input);
}
Вот результаты на моей машине:
| Method | InputLength | Mean | Error | StdDev | Gen 0 | Allocated |
| ---------------- | ----------- | -----------: | ---------: | --------: | -----: | --------: |
| WithReverseArray | 10 | 45.464 ns | 0.4836 ns | 0.4524 ns | 0.0610 | 96 B |
| WithStringCreate | 10 | 39.749 ns | 0.3206 ns | 0.2842 ns | 0.0305 | 48 B |
| | | | | | | |
| WithReverseArray | 100 | 175.162 ns | 2.8766 ns | 2.2458 ns | 0.2897 | 456 B |
| WithStringCreate | 100 | 125.284 ns | 2.4657 ns | 2.0590 ns | 0.1473 | 232 B |
| | | | | | | |
| WithReverseArray | 1000 | 1,523.544 ns | 9.8808 ns | 8.7591 ns | 2.5768 | 4056 B |
| WithStringCreate | 1000 | 1,078.957 ns | 10.2948 ns | 9.6298 ns | 1.2894 | 2032 B |
Как вы можете видеть, с ReverseWithStringCreate мы выделяем только половину памяти, используемой ReverseWithArray метод.
Посмотрите на запись в Википедии здесь. Они реализуют метод расширения String.Reverse. Это позволяет вам писать код так:
string s = "olleh";
s.Reverse();
Они также используют комбинацию ToCharArray/Reverse, которую предлагают другие ответы на этот вопрос. Исходный код выглядит так:
public static string Reverse(this string input)
{
char[] chars = input.ToCharArray();
Array.Reverse(chars);
return new String(chars);
}
Грег Бук опубликовал unsafe опция, которая действительно так быстро, как она получает (это разворот на месте); но, как он указал в своем ответе, это совершенно катастрофическая идея.
Тем не менее, я удивлен, что есть так много консенсуса, что Array.Reverse самый быстрый метод. Там еще есть unsafe Подход, который возвращает перевернутую копию строки (без изменений на месте) значительно быстрее, чем Array.Reverse метод для небольших строк:
public static unsafe string Reverse(string text)
{
int len = text.Length;
// Why allocate a char[] array on the heap when you won't use it
// outside of this method? Use the stack.
char* reversed = stackalloc char[len];
// Avoid bounds-checking performance penalties.
fixed (char* str = text)
{
int i = 0;
int j = i + len - 1;
while (i < len)
{
reversed[i++] = str[j--];
}
}
// Need to use this overload for the System.String constructor
// as providing just the char* pointer could result in garbage
// at the end of the string (no guarantee of null terminator).
return new string(reversed, 0, len);
}
Вот некоторые результаты тестов.
Вы можете видеть, что прирост производительности уменьшается, а затем исчезает по сравнению с Array.Reverse метод, как строки становятся больше. Однако для струн малого и среднего размера этот метод трудно обойти.
Если вы хотите играть в действительно опасную игру, то это самый быстрый способ (примерно в четыре раза быстрее, чем Array.Reverse метод). Это обратный вариант с использованием указателей.
Обратите внимание, что я действительно никогда не рекомендую это для какого-либо использования ( посмотрите здесь по некоторым причинам, почему вы не должны использовать этот метод), но просто интересно посмотреть, что это можно сделать, и что строки на самом деле не являются неизменяемыми как только вы включите небезопасный код.
public static unsafe string Reverse(string text)
{
if (string.IsNullOrEmpty(text))
{
return text;
}
fixed (char* pText = text)
{
char* pStart = pText;
char* pEnd = pText + text.Length - 1;
for (int i = text.Length / 2; i >= 0; i--)
{
char temp = *pStart;
*pStart++ = *pEnd;
*pEnd-- = temp;
}
return text;
}
}
Простой и приятный ответ - использование метода расширения:
static class ExtentionMethodCollection
{
public static string Inverse(this string @base)
{
return new string(@base.Reverse().ToArray());
}
}
и вот вывод:
string Answer = "12345".Inverse(); // = "54321"
Во-первых, вам не нужно звонить ToCharArray поскольку строка уже может быть проиндексирована как массив символов, так что это сэкономит вам выделение.
Следующая оптимизация заключается в использовании StringBuilder чтобы предотвратить ненужные выделения (поскольку строки являются неизменяемыми, их объединение делает копию строки каждый раз). Для дальнейшей оптимизации мы заранее установили длину StringBuilder поэтому ему не нужно будет расширять свой буфер.
public string Reverse(string text)
{
if (string.IsNullOrEmpty(text))
{
return text;
}
StringBuilder builder = new StringBuilder(text.Length);
for (int i = text.Length - 1; i >= 0; i--)
{
builder.Append(text[i]);
}
return builder.ToString();
}
Изменить: данные о производительности
Я проверил эту функцию и функцию, используя Array.Reverse с помощью следующей простой программы, где Reverse1 это одна функция и Reverse2 другой:
static void Main(string[] args)
{
var text = "abcdefghijklmnopqrstuvwxyz";
// pre-jit
text = Reverse1(text);
text = Reverse2(text);
// test
var timer1 = Stopwatch.StartNew();
for (var i = 0; i < 10000000; i++)
{
text = Reverse1(text);
}
timer1.Stop();
Console.WriteLine("First: {0}", timer1.ElapsedMilliseconds);
var timer2 = Stopwatch.StartNew();
for (var i = 0; i < 10000000; i++)
{
text = Reverse2(text);
}
timer2.Stop();
Console.WriteLine("Second: {0}", timer2.ElapsedMilliseconds);
Console.ReadLine();
}
Оказывается, что для коротких струн Array.Reverse Метод примерно в два раза быстрее, чем приведенный выше, и для более длинных строк разница еще более выражена. Итак, учитывая, что Array.Reverse метод проще и быстрее, я бы порекомендовал вам использовать его, а не этот. Я оставляю это здесь, чтобы показать, что это не так, как вы должны это делать (к моему большому удивлению!)
Попробуйте использовать Array.Reverse
public string Reverse(string str)
{
char[] array = str.ToCharArray();
Array.Reverse(array);
return new string(array);
}
"Лучший" может зависеть от многих вещей, но вот несколько коротких альтернатив, упорядоченных от быстрого к медленному:
string s = "z̽a̎l͘g̈o̓", pattern = @"(?s).(?<=(?:.(?=.*$(?<=((\P{M}\p{C}?\p{M}*)\1?))))*)";
string s1 = string.Concat(s.Reverse()); // "☐☐̓ög͘l̎a̽z"
string s2 = Microsoft.VisualBasic.Strings.StrReverse(s); // "o̓g̈l͘a̎̽z"
string s3 = string.Concat(StringInfo.ParseCombiningCharacters(s).Reverse()
.Select(i => StringInfo.GetNextTextElement(s, i))); // "o̓g̈l͘a̎z̽"
string s4 = Regex.Replace(s, pattern, "$2").Remove(s.Length); // "o̓g̈l͘a̎z̽"
public static string Reverse(string input)
{
return string.Concat(Enumerable.Reverse(input));
}
Конечно, вы можете расширить класс строки с помощью метода Reverse
public static class StringExtensions
{
public static string Reverse(this string input)
{
return string.Concat(Enumerable.Reverse(input));
}
}
Не беспокойтесь о функции, просто сделайте это на месте. Примечание: вторая строка вызовет исключение аргумента в окне Immediate некоторых версий VS.
string s = "Blah";
s = new string(s.ToCharArray().Reverse().ToArray());
Извините за длинный пост, но это может быть интересно
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
public static string ReverseUsingArrayClass(string text)
{
char[] chars = text.ToCharArray();
Array.Reverse(chars);
return new string(chars);
}
public static string ReverseUsingCharacterBuffer(string text)
{
char[] charArray = new char[text.Length];
int inputStrLength = text.Length - 1;
for (int idx = 0; idx <= inputStrLength; idx++)
{
charArray[idx] = text[inputStrLength - idx];
}
return new string(charArray);
}
public static string ReverseUsingStringBuilder(string text)
{
if (string.IsNullOrEmpty(text))
{
return text;
}
StringBuilder builder = new StringBuilder(text.Length);
for (int i = text.Length - 1; i >= 0; i--)
{
builder.Append(text[i]);
}
return builder.ToString();
}
private static string ReverseUsingStack(string input)
{
Stack<char> resultStack = new Stack<char>();
foreach (char c in input)
{
resultStack.Push(c);
}
StringBuilder sb = new StringBuilder();
while (resultStack.Count > 0)
{
sb.Append(resultStack.Pop());
}
return sb.ToString();
}
public static string ReverseUsingXOR(string text)
{
char[] charArray = text.ToCharArray();
int length = text.Length - 1;
for (int i = 0; i < length; i++, length--)
{
charArray[i] ^= charArray[length];
charArray[length] ^= charArray[i];
charArray[i] ^= charArray[length];
}
return new string(charArray);
}
static void Main(string[] args)
{
string testString = string.Join(";", new string[] {
new string('a', 100),
new string('b', 101),
new string('c', 102),
new string('d', 103),
});
int cycleCount = 100000;
Stopwatch stopwatch = new Stopwatch();
stopwatch.Start();
for (int i = 0; i < cycleCount; i++)
{
ReverseUsingCharacterBuffer(testString);
}
stopwatch.Stop();
Console.WriteLine("ReverseUsingCharacterBuffer: " + stopwatch.ElapsedMilliseconds + "ms");
stopwatch.Reset();
stopwatch.Start();
for (int i = 0; i < cycleCount; i++)
{
ReverseUsingArrayClass(testString);
}
stopwatch.Stop();
Console.WriteLine("ReverseUsingArrayClass: " + stopwatch.ElapsedMilliseconds + "ms");
stopwatch.Reset();
stopwatch.Start();
for (int i = 0; i < cycleCount; i++)
{
ReverseUsingStringBuilder(testString);
}
stopwatch.Stop();
Console.WriteLine("ReverseUsingStringBuilder: " + stopwatch.ElapsedMilliseconds + "ms");
stopwatch.Reset();
stopwatch.Start();
for (int i = 0; i < cycleCount; i++)
{
ReverseUsingStack(testString);
}
stopwatch.Stop();
Console.WriteLine("ReverseUsingStack: " + stopwatch.ElapsedMilliseconds + "ms");
stopwatch.Reset();
stopwatch.Start();
for (int i = 0; i < cycleCount; i++)
{
ReverseUsingXOR(testString);
}
stopwatch.Stop();
Console.WriteLine("ReverseUsingXOR: " + stopwatch.ElapsedMilliseconds + "ms");
}
}
}
Результаты:
- ReverseUsingCharacterBuffer: 346мс
- ReverseUsingArrayClass: 87мс
- ReverseUsingStringBuilder: 824 мс
- ReverseUsingStack: 2086мс
- ReverseUsingXOR: 319мс
public string Reverse(string input)
{
char[] output = new char[input.Length];
int forwards = 0;
int backwards = input.Length - 1;
do
{
output[forwards] = input[backwards];
output[backwards] = input[forwards];
}while(++forwards <= --backwards);
return new String(output);
}
public string DotNetReverse(string input)
{
char[] toReverse = input.ToCharArray();
Array.Reverse(toReverse);
return new String(toReverse);
}
public string NaiveReverse(string input)
{
char[] outputArray = new char[input.Length];
for (int i = 0; i < input.Length; i++)
{
outputArray[i] = input[input.Length - 1 - i];
}
return new String(outputArray);
}
public string RecursiveReverse(string input)
{
return RecursiveReverseHelper(input, 0, input.Length - 1);
}
public string RecursiveReverseHelper(string input, int startIndex , int endIndex)
{
if (startIndex == endIndex)
{
return "" + input[startIndex];
}
if (endIndex - startIndex == 1)
{
return "" + input[endIndex] + input[startIndex];
}
return input[endIndex] + RecursiveReverseHelper(input, startIndex + 1, endIndex - 1) + input[startIndex];
}
void Main()
{
int[] sizes = new int[] { 10, 100, 1000, 10000 };
for(int sizeIndex = 0; sizeIndex < sizes.Length; sizeIndex++)
{
string holaMundo = "";
for(int i = 0; i < sizes[sizeIndex]; i+= 5)
{
holaMundo += "ABCDE";
}
string.Format("\n**** For size: {0} ****\n", sizes[sizeIndex]).Dump();
string odnuMaloh = DotNetReverse(holaMundo);
var stopWatch = Stopwatch.StartNew();
string result = NaiveReverse(holaMundo);
("Naive Ticks: " + stopWatch.ElapsedTicks).Dump();
stopWatch.Restart();
result = Reverse(holaMundo);
("Efficient linear Ticks: " + stopWatch.ElapsedTicks).Dump();
stopWatch.Restart();
result = RecursiveReverse(holaMundo);
("Recursive Ticks: " + stopWatch.ElapsedTicks).Dump();
stopWatch.Restart();
result = DotNetReverse(holaMundo);
("DotNet Reverse Ticks: " + stopWatch.ElapsedTicks).Dump();
}
}
Выход
Для размера: 10
Naive Ticks: 1
Efficient linear Ticks: 0
Recursive Ticks: 2
DotNet Reverse Ticks: 1
Для размера: 100
Naive Ticks: 2
Efficient linear Ticks: 1
Recursive Ticks: 12
DotNet Reverse Ticks: 1
Для размера: 1000
Naive Ticks: 5
Efficient linear Ticks: 2
Recursive Ticks: 358
DotNet Reverse Ticks: 9
Для размера: 10000
Naive Ticks: 32
Efficient linear Ticks: 28
Recursive Ticks: 84808
DotNet Reverse Ticks: 33
Я сделал порт C# из Microsoft.VisualBasic.Strings. Я не уверен, почему они хранят такие полезные функции (из VB) вне System.String в Framework, но все еще в Microsoft.VisualBasic. Тот же сценарий для финансовых функций (например, Microsoft.VisualBasic.Financial.Pmt()).
public static string StrReverse(this string expression)
{
if ((expression == null))
return "";
int srcIndex;
var length = expression.Length;
if (length == 0)
return "";
//CONSIDER: Get System.String to add a surrogate aware Reverse method
//Detect if there are any graphemes that need special handling
for (srcIndex = 0; srcIndex <= length - 1; srcIndex++)
{
var ch = expression[srcIndex];
var uc = char.GetUnicodeCategory(ch);
if (uc == UnicodeCategory.Surrogate || uc == UnicodeCategory.NonSpacingMark || uc == UnicodeCategory.SpacingCombiningMark || uc == UnicodeCategory.EnclosingMark)
{
//Need to use special handling
return InternalStrReverse(expression, srcIndex, length);
}
}
var chars = expression.ToCharArray();
Array.Reverse(chars);
return new string(chars);
}
///<remarks>This routine handles reversing Strings containing graphemes
/// GRAPHEME: a text element that is displayed as a single character</remarks>
private static string InternalStrReverse(string expression, int srcIndex, int length)
{
//This code can only be hit one time
var sb = new StringBuilder(length) { Length = length };
var textEnum = StringInfo.GetTextElementEnumerator(expression, srcIndex);
//Init enumerator position
if (!textEnum.MoveNext())
{
return "";
}
var lastSrcIndex = 0;
var destIndex = length - 1;
//Copy up the first surrogate found
while (lastSrcIndex < srcIndex)
{
sb[destIndex] = expression[lastSrcIndex];
destIndex -= 1;
lastSrcIndex += 1;
}
//Now iterate through the text elements and copy them to the reversed string
var nextSrcIndex = textEnum.ElementIndex;
while (destIndex >= 0)
{
srcIndex = nextSrcIndex;
//Move to next element
nextSrcIndex = (textEnum.MoveNext()) ? textEnum.ElementIndex : length;
lastSrcIndex = nextSrcIndex - 1;
while (lastSrcIndex >= srcIndex)
{
sb[destIndex] = expression[lastSrcIndex];
destIndex -= 1;
lastSrcIndex -= 1;
}
}
return sb.ToString();
}
Самый простой способ:
string reversed = new string(text.Reverse().ToArray());
Пришлось представить рекурсивный пример:
private static string Reverse(string str)
{
if (str.IsNullOrEmpty(str) || str.Length == 1)
return str;
else
return str[str.Length - 1] + Reverse(str.Substring(0, str.Length - 1));
}
Так как мне нравится пара ответов - один для использования string.Create и, следовательно, высокая производительность и низкое распределение, а другой для правильности - с использованием StringInfo класс, я решил, что нужен комбинированный подход. Это основной метод обращения строк:)
private static string ReverseString(string str)
{
return string.Create(str.Length, str, (chars, state) =>
{
var enumerator = StringInfo.GetTextElementEnumerator(state);
var position = state.Length;
while (enumerator.MoveNext())
{
var cluster = ((string)enumerator.Current).AsSpan();
cluster.CopyTo(chars.Slice(position - cluster.Length));
position -= cluster.Length;
}
});
}
Есть еще лучший способ использования метода класса StringInfo, который пропускает большое количество выделенных строк перечислителем, возвращая только индексы.
private static string ReverseString(string str)
{
return string.Create(str.Length, str, (chars, state) =>
{
var position = 0;
var indexes = StringInfo.ParseCombiningCharacters(state); // skips string creation
var stateSpan = state.AsSpan();
for (int len = indexes.Length, i = len - 1; i >= 0; i--)
{
var index = indexes[i];
var spanLength = i == len - 1 ? state.Length - index : indexes[i + 1] - index;
stateSpan.Slice(index, spanLength).CopyTo(chars.Slice(position));
position += spanLength;
}
});
}
Некоторые тесты по сравнению с решением LINQ:
String length 20:
LINQ Mean: 2,355.5 ns Allocated: 1440 B
string.Create Mean: 851.0 ns Allocated: 720 B
string.Create with indexes Mean: 466.4 ns Allocated: 168 B
String length 450:
LINQ Mean: 34.33 us Allocated: 22.98 KB
string.Create Mean: 19.13 us Allocated: 14.98 KB
string.Create with indexes Mean: 10.32 us Allocated: 2.69 KB
Как насчет:
private string Reverse(string stringToReverse)
{
char[] rev = stringToReverse.Reverse().ToArray();
return new string(rev);
}
Стек на основе решения.
public static string Reverse(string text)
{
var stack = new Stack<char>(text);
var array = new char[stack.Count];
int i = 0;
while (stack.Count != 0)
{
array[i++] = stack.Pop();
}
return new string(array);
}
Или же
public static string Reverse(string text)
{
var stack = new Stack<char>(text);
return string.Join("", stack);
}
"Лучший путь" зависит от того, что для вас важнее в вашей ситуации, производительности, элегантности, ремонтопригодности и т. Д.
В любом случае, вот подход с использованием Array.Reverse:
string inputString="The quick brown fox jumps over the lazy dog.";
char[] charArray = inputString.ToCharArray();
Array.Reverse(charArray);
string reversed = new string(charArray);
Если это когда-нибудь появилось в интервью, и вам сказали, что вы не можете использовать Array.Reverse, я думаю, что это может быть одним из самых быстрых. Он не создает новые строки и повторяет только более половины массива (т.е. O(n/2) итераций)
public static string ReverseString(string stringToReverse)
{
char[] charArray = stringToReverse.ToCharArray();
int len = charArray.Length-1;
int mid = len / 2;
for (int i = 0; i < mid; i++)
{
char tmp = charArray[i];
charArray[i] = charArray[len - i];
charArray[len - i] = tmp;
}
return new string(charArray);
}
Извините за публикацию в этой старой теме. Я практикую код для интервью.
Это было то, что я придумал для C#. Моя первая версия до рефакторинга была ужасной.
static String Reverse2(string str)
{
int strLen = str.Length, elem = strLen - 1;
char[] charA = new char[strLen];
for (int i = 0; i < strLen; i++)
{
charA[elem] = str[i];
elem--;
}
return new String(charA);
}
В отличие от Array.Reverse Приведенный ниже метод выглядит быстрее с 12 или менее символами в строке. После 13 символов Array.Reverse начинает становиться быстрее, и это в конечном итоге довольно сильно доминирует на скорости. Я просто хотел указать приблизительно, где скорость начинает меняться.
static String Reverse(string str)
{
char[] charA = str.ToCharArray();
Array.Reverse(charA);
return new String(charA);
}
При 100 символах в строке это быстрее, чем моя версия х 4. Однако, если бы я знал, что строки всегда будут меньше чем 13 символов, я бы использовал тот, который я сделал.
Тестирование было сделано с Stopwatch и 5000000 итераций. Кроме того, я не уверен, что моя версия обрабатывает суррогаты или комбинированные ситуации персонажей с Unicode кодирование.
Есть несколько правильных ответов, где используется StringInfo.GetTextElementEnumerator() .Слава вам!
Теперь давайте найдем наиболее эффективный способ использования этого метода. Во-первых, большинство ответов связаны с вызовом Reverse() и ToArray() , что является большим запретом на горячих путях. Для оптимальной производительности мы хотим избежать выделения мусора. Например, временные строки, распределители, массивы и т. д.
Оптимизированное обращение строки
- Пониженное давление ГХ. то есть нет
LINQперечислители, без массивов. - Использование диапазона
- Использование String.Создать()
using System.Globalization;
public static class StringExtensions
{
public static string AsReversed(this string s)
{
return string.Create(s.Length, s, (chars, state) =>
{
int i = 0;
var enumerator = StringInfo.GetTextElementEnumerator(s);
while (enumerator.MoveNext())
{
var element = enumerator.GetTextElement();
i += element.Length;
element.CopyTo(chars[^i..]);
}
});
}
}
Обратите внимание, чтоGetTextElementEnumerator()API содержит ошибку в.NET Core 3.1и ранее. Обязательно запустите
.NET 5или позже! Наконец, обязательно ознакомьтесь с выпуском № 19423 , в котором обсуждаются улучшения API.
public static string reverse(string s)
{
string r = "";
for (int i = s.Length; i > 0; i--) r += s[i - 1];
return r;
}
Прежде всего, вы должны понять, что str+= изменит размер вашей строковой памяти, чтобы освободить место для 1 дополнительного символа. Это хорошо, но если у вас есть, скажем, книга с 1000 страницами, которую вы хотите перевернуть, это займет очень много времени.
Решение, которое некоторые люди могут предложить, - это использовать StringBuilder. Что делает строитель строк, когда вы выполняете + =, так это то, что он выделяет гораздо большие куски памяти для хранения нового символа, так что ему не нужно выполнять перераспределение каждый раз, когда вы добавляете символ.
Если вы действительно хотите быстрое и минимальное решение, я бы предложил следующее:
char[] chars = new char[str.Length];
for (int i = str.Length - 1, j = 0; i >= 0; --i, ++j)
{
chars[j] = str[i];
}
str = new String(chars);
В этом решении есть одно начальное распределение памяти, когда инициализируется char[], и одно выделение, когда строковый конструктор строит строку из массива char.
В моей системе я провел для вас тест, который переворачивает строку из 2 750 000 символов. Вот результаты для 10 казней:
StringBuilder: 190K - 200K тиков
Char Char Array: 130K - 160K тиков
Я также запустил тест на нормальный тип String +=, но я отказался от него через 10 минут без вывода.
Тем не менее, я также заметил, что для небольших строк StringBuilder работает быстрее, поэтому вам придется выбирать реализацию на основе входных данных.
ура