Как вывести строку в обратном порядке c

Как выполнить реверс строки в C++

При разработке на C++ иногда возникает необходимость перевернуть строку. Это может быть как простой вывод перевернутой строки, так и постоянный реверс строки по её адресу.

Как решить обе эти задачи, вы узнаете в данном мануале. Здесь мы будем работать с разными стандартными и пользовательскими функциями.

Реверс строки – это операция, которая инвертирует порядок символов в строке. ПРедположим, что у нас есть переменная, которая содержит строку «JournalDev».

После реверса ‘str’ содержимое будет отображаться в обратном порядке. То есть, теперь ‘str’ будет содержать строку «veDlanruoJ».

Давайте посмотрим, какие существуют способы перевернуть строку в C++.

Функция reverse()

Встроенная функция reverse() выводит строку в обратном порядке. При этом в качестве аргументов выступают двунаправленные начальные и конечные итераторы.

Эта функция определена в алгоритме заголовочного файла. Приведенный ниже код показывает применение функции reverse():

Вывод будет выглядеть так:

Функция strrev()

strrev() — это встроенная функция C++, определенная внутри заголовочного файла cstring.h. Этот метод широко применяют для реверса C-строк (массивов символов).

Эта функция принимает только базовый адрес строки как аргумента и переворачивает ее соответствующим образом. Давайте посмотрим на примере, как перевернуть строку с помощью функции strlen() в C++.

Приведенный выше код показывает работу функции strrev().

Вывод строки в обратном порядке

В отдельных случаях нам может понадобиться вывести строку в обратном порядке, а не изменять её. Например, это касается постоянных строк, которые в принципе нельзя изменить. Используя цикл, мы можем вывести любую строку в обратном порядке. Давайте посмотрим, как это делается.

Вывод будет выглядеть так:

• В приведенном выше коде мы сначала инициализировали строку ‘str’.
• Обратите внимание, что внутри цикла for при выводе строки мы инициализировали итератор ‘i’ со значением str.length()-1. Это значит, что строку нужно вывести в обратном порядке, начиная с последнего индекса.
• Обратите внимание: length() возвращает длину строки. То есть, для вывода строки в обратном порядке мы должны учитывать последний индекс, который должен быть length()-1, так как в массиве символов индексация начинается с 0.

Создание пользовательской функции реверса строки

Ранее мы уже разобрали, как выводить строку в обратном порядке, а также реверсировать её с помощью встроенных функций.

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode

Реверсирование строки в C#

Рассмотрим один из способов реверсирования строк в языке программирования C# средствами .NET Framefork.

Реверсирование — изменение прямого порядка на обратный.

У класса string нет метода, который изменял бы порядок элементов в строке на обратный, но у класса Array такой метод имеется. Поэтому необходимо сначала преобразовать строку в символьный массив, затем выполнить реверсирование массива и этот массив преобразовать в строку. Нужно сделать следующее:

О разворачивании строк в .Net/C# и не только

Давайте поговорим о строках, точнее об их переворачивании средствами .Net/C#. Так уж сложилось, что в стандартной библиотеке соответсвующей функции не наблюдается. И как мне подсказывают, написание функции обращения строки довольно популярный вопрос на собеседованиях при приеме на работу. Давайте посмотрим, как можно эффективно перевернуть строку средствами данной платформы.

Под катом приведен сравнительный анализ быстродействия разных методов переворачивания строки.

Кхрр-р-р… — сказала бензопила.
Тююю… — сказали мужики.
© Старый анекдот.

Ну что ж, начнем. Все реализации проверялись на быстродействие с одной строкой размером 256 мегабайт (128×1024×1024 символа) и 1024×1024 строками размером 256 байт (128 символов). Перед каждым замером форсировалась сборка мусора (что важно при таком размере тестовых данных), замер проводился 50 раз, 20 крайних отбрасывались, остальные значения усреднялись. Условными попугаями было выбрано количество тиков, выдаваемое объектом класса Stopwatch.

Тест проводился на двух компьютерах: Athlon64 x2 4200+, 2GB Dual-Channel DDR2 RAM и Pentium4 HT 3GHz, 3GB DDR RAM. Главным отличием между конфигурациями в данном тесте является быстродействие связки память-кэш — вторая система в этом отношении заметно медленнее.

С техническими формальностями покончено, теперь перейдем к собственно реализациям. Для большей наглядности, здесь не учтены unicode surrogate code points. Рассматривать подходы будем в порядке логичности и «красивости» реализации в контексте окружающей ее «экосистемы».

Сравнительные результаты замеров находятся в последней части этой заметки. Оптимальной в общем случае оказалась функция ReverseUnsafeCopy, если же ограничиваться только safe code — ReverseArrayManual. Если необходим safe code и огромные строки — прийдется мучаться с ReverseStringBuilder.

Часть первая: «нормальные» методы.

1. ReverseStringBuilder

Будем следовать рекомендациям и для построения «большой» строки возьмем специальный инструмент — класс StringBuilder. Идея проста до ужаса: создаем builder нужного размера и идем по строке в обратном порядке, добавляя символы в новую строку.

1. static string ReverseStringBuilder( string str)
2. <
3. StringBuilder sb = new StringBuilder (str.Length);
4. for ( int i = str.Length; i— != 0 ; )
5. sb.Append(str[i]);
6. return sb.ToString();
7. >

Пробуем, запускаем, да… Как-то медленно работает это все, будем копать дальше.

2. ReverseArrayFramework

Ха! Так этот билдер же обставлен проверками для обеспечения потокобезопасности со всех сторон, не, нам такое не надо. Но строка — это ведь массив сиволов. Так давайте его и перевернем, а результат преобразуем обратно в строку:

1. static string ReverseArrayFramework( string str)
2. <
3. char [] arr = str.ToCharArray();
4. Array .Reverse(arr);
5. return new String (arr);
6. >

Совсем другое дело, получилось в 3.5 раза быстрее. Хм, а может можно еще лучше?

3. ReverseArrayManual

Так, думаем. Во-первых у нас данные копируются дважы: сначала из строки в массив, потом внутри массива. Во-вторых Array.Reverse — библиотечный метод, значит в нем есть проверки входных данных. Более того, для атомарных типов он явно реализован в виде native метода, а это дополнительное переключение контекста выполнения. Попробуем перевернуть строку в массив вручную:

1. static string ReverseArrayManual( string originalString)
2. <
3. char [] reversedCharArray = new char [originalString.Length];
4. for ( int i = originalString.Length — 1 ; i > — 1 ; i—)
5. reversedCharArray[originalString.Length — i — 1 ] = originalString[i];
6. return new string (reversedCharArray);
7. >

4. ReverseManualHalf

Идем дальше. У нас же действия симметричны относительно середины строки, значит можно пустить два индекса навстречу и ученьшить количество итераций вдвое:

1. static string ReverseManualHalf( string originalString)
2. <
3. char [] reversedCharArray = new char [originalString.Length];
4. int i = 0 ;
5. int j = originalString.Length — 1 ;
6. while (i <= j)
7. <
8. reversedCharArray[i] = originalString[j];
9. reversedCharArray[j] = originalString[i];
10. i++; j—;
11. >
12. return new string (reversedCharArray);
13. >

Хм… Что-то пошло не так, на системе с медленной памятью скорость упала в полтора раза. Учитывая специфику конфигураций и реализации, можем предположить, что виноваты скорость памяти и кэш процессора: раньше мы работали с двумя отдаленными областями памяти одновременно, теперь их стало четыре, соответсвенно подхват данных выполняется чаще.

LINQ и метод Reverse

Есть еще относительно красивый и короткий способ с LINQ, но он не выдерживает никакой критики в плане производительности — работает в 3-3.5 раза медленнее метода на базе StringBuilder. Виной тому прокачивание данных через IEnumerable и виртуальный вызов на каждую итерацию. Для желающих, ниже приведена реализация:

1. static string ReverseStringLinq( string originalString)
2. <
3. return new string (originalString.Reverse().ToArray());
4. >

Использование памяти

Проблема не столь критичная в большинстве случаев, но все «быстрые» из рассмотренных методов делают промежуточную копию строки в виде массива символов. На синтетических тестах это проявляется в том, что обернуть строку размером 512МБ смог только первый метод, остальные свалились по System.OutOfMemoryException. Также, не следует забывать, что лишние временные объекты повышают частоту срабатывания GC, а он хоть и оптимизирован до ужаса, но все-равно время кушает. В следующей части будем кроме скоростных оптимизаций также искать решение этой проблемы.

Часть вторая: когда хочется быстрее и эффективнее, или unsafe code.

Использование unsafe кода дает нам одно интересное преимущество: строки, которые раньше были immutable, теперь можно менять, но нужно быть предельно осторожным и изменять только копии строк — библиотека минимизирует количество копий одной строки, а вместе с интернированием строк это может привести к печальным последствиями для приложения.

Итак, создав новую строку нужного размера, мы можем смотреть на нее, как на массив и заполнить нужными данными. Ну и не стоит забывать об отстутствии проверок на валидность индексов, что тоже ускорит работу кода. Однако в силу специфики строк в .Net, мы не можем вот так просто создать строку нужной длины. Можно либо сделать строку из повторяющегося символа (например проблела) при помощи конструктора String(char, int), либо скопировать исходную строку используя String.Copy(String).

Вооружившись этими знаниями пишем следующие две реализации.

5. ReverseUnsafeFill

Делаем строку из пробелов и заполняем ее в обратном порядке:

1. static unsafe string ReverseUnsafeFill( string str)
2. <
3. if (str.Length <= 1 ) return str;
4. String copy = new String ( ‘ ‘ , str.Length);
5. fixed ( char * buf_copy = copy)
6. <
7. fixed ( char * buf = str)
8. <
9. int i = 0 ;
10. int j = str.Length — 1 ;
11. while (i <= j)
12. <
13. buf_copy[i] = buf[j];
14. buf_copy[j] = buf[i];
15. i++; j—;
16. >
17. >
18. >
19. return copy;
20. >

6. ReverseUnsafeCopy

Копируем и переворачиваем строку:

1. static unsafe string ReverseUnsafeCopy( string str)
2. <
3. if (str.Length <= 1 ) return str;
4. char tmp;
5. String copy = String .Copy(str);
6. fixed ( char * buf = copy)
7. <
8. char * p = buf;
9. char * q = buf + str.Length — 1 ;
10. while (p < q)
11. <
12. tmp = *p;
13. *p = *q;
14. *q = tmp;
15. p++; q—;
16. >
17. >
18. return copy;
19. >

Как показали замеры, вторая версия работает заметно быстрее на медленной памяти и слегка медленнее на быстрой 🙂 Причин видимо несколько: оперирование двумя отдаленными областями памяти вместо четырех и различие в скорости копирования блока памяти и простого его заполнения в цикле. Желающие могут попробовать сделать версию ReverseUnsafeFill с полным проходом (это может уменьшить число захватов данных из памяти в кэш) и испытать ее на медленной памяти, однако у меня есть основания считать, что это будет все-равно медленнее ReverseUnsafeCopy (хотя могу и ошибаться).

7. ReverseUnsafeXorCopy

А что дальше? Ходят слухи, что обмен при помощи оператора XOR работает быстрее копирования через третью переменную (кстати в плюсах это еще и смотрится довольно красиво: «a ^= b ^= a ^= b;», в C#, увы, такая строка не cработает). Ну что, давайте проверим на деле.

1. static unsafe string ReverseUnsafeXorCopy( string str)
2. <
3. if (str.Length <= 1 ) return str;
4. String copy = String .Copy(str);
5. fixed ( char * buf = copy)
6. <
7. char * p = buf;
8. char * q = buf + str.Length — 1 ;
9. while (p < q)
10. <
11. *p ^= *q;
12. *q ^= *p;
13. *p ^= *q;
14. p++; q—;
15. >
16. >
17. return copy;
18. >

В итоге получается в 1.2-1.5 раза медленнее обмена копированием. Трюк, работавший для быстрого обмена значений на регистрах, для переменных себя не оправдал (что характено, во многих компиляторах С/С++ он тоже выиграша не дает).

В поисках объяснения этого факта полезем внутрь приложения и почитаем результирующий CIL код.

Часть третья: лезем в CIL и коды библиотек .Net.

Почему обмен через XOR оказался хуже

Для получения ответа на этот вопрос стоит посмотреть на CIL-код, сгенерированный для двух способов обмена. Чтоб эти инструкции казались понятнее, поясню их назначение: ldloc.N — загружает на стек локальную переменную под номером N, stloc.N — считывает верхушку стека в локальную переменную номер N, xor — вычисляет значение операции XOR для двух значений наверху стека и загружает результат на стек вместо них.

1. int a, b;
2. int tmp = a;
3. a = b;
4. b = tmp;

1. int a, b;
2. a ^= b;
3. b ^= a;
4. a ^= b;

Как работает Array.Reverse?

Ну и пока мы смотрим на внутренности сборок рефлектором, есть смысл взглянуть на реализацию библиотечных методов, использованных в первой части. Особняком здесь стоит Array.Reverse, который опирается на некую функцию Array.TrySZReverse, реализованную в виде native метода. Итак качаем Shared Source Common Language Infrastructure 2.0 — исходник .net 2.0 и смотрим, что ж это за зверь такой 🙂 После недолгих поисков, в файле «sscli20\clr\src\vm\comarrayhelpers.h» находится шаблонная функция Reverse (в данном случае KIND будет соответствовать UINT16), которая (сюрприз!) до ужаса похожа на реализацию ReverseUnsafeCopy.

1. static void Reverse( KIND array[], UNIT32 index, UNIT32 count) <
2. LEAF_CONTRACT;
3. _ASSERTE(array != NULL);
4. if (count == 0) <
5. return ;
6. >
7. UNIT32 i = index;
8. UNIT32 j = index + count — 1 ;
9. while (i < j) <
10. KIND temp = array[i];
11. array[i] = array[j];
12. array[j] = temp;
13. i++;
14. j—;
15. >
16. >

Часть четвертая: результаты бинарного марафона.

Анализ результатов замеров приведен в первых двух частях, здесь же изображены лишь сравнительные диаграммы отображающие отношение быстродействия рассмотренных выше функций. Точные числа в «ticks» слишком зависят от конфигурации и вряд-ли представляют особый интерес, все желающие могут самостоятельно замерить быстродействие используя предоставленные куски кода.

Сравнение лучших методов из первых двух частей

На быстрой памяти

На медленной памяти

Сравнение всех методов в Debug и Release конфигурациях на быстрой памяти

Большие строки

Короткие строки

Сравнение всех методов в Debug и Release конфигурациях на медленной памяти

Большие строки

Короткие строки

Как перевернуть строку в C?

Программирование и разработка

В строковом кодировании реверсирование строк является важной темой. Существует также несколько методов переворота строки, каждый из которых имеет свою логику. Эта статья покажет вам, как правильно перевернуть строку, чтобы использовать несколько различных подходов и рассуждений с и без использования каких-либо предустановленных функций. Всякий раз, когда обращение строковой техники применяется к конкретной уникальной входной строке, текст, который потребитель предоставит в определенном порядке, будет полностью перевернут. В приведенном ниже примере использовались различные альтернативы переворачивания струны с помощью C.

При реализации этого руководства мы работали над системой Ubuntu 20.04 Linux, настроенной на Virtual Box. Во время работы в системе Linux мы обычно выполняли большинство установок и запросов в оболочке терминала. Следовательно, откройте оболочку терминала с помощью сочетания клавиш «Ctrl + Alt + T» или выполните поиск в строке поиска приложения в области «Активность» рабочего стола Ubuntu. Сначала необходимо обновить вашу систему с помощью подходящего запроса на обновление. Он запросит у вас текущий пароль пользователя для запуска обновления. Следовательно, добавьте пароль и нажмите кнопку Enter.

Поскольку мы использовали язык программирования C для разработки концепции реверсирования строк в системе Ubuntu 20.04, в их системе Ubuntu должен быть установлен компилятор C. Поэтому обязательно установите компилятор GCC в вашей системе с помощью следующего запроса.

Пример 01: Использование цикла For

После установки и настройки компилятора GCC и обновления пакета «apt» он создает новый файл. Этот файл должен быть типа C; поэтому используйте сенсорную команду для создания файла «new.c», как показано ниже. Этот файл будет использоваться в нашем коде с этого момента при реализации программ с обратными строками.

Теперь вы можете открыть этот файл для редактирования или кодирования с помощью редактора Nano, встроенного в вашу систему Ubuntu 20.04 Linux. Поэтому попробуйте сделать это в своей оболочке с помощью приведенной ниже инструкции.