что делает reverse c
Array. Reverse Метод
Определение
Некоторые сведения относятся к предварительной версии продукта, в которую до выпуска могут быть внесены существенные изменения. Майкрософт не предоставляет никаких гарантий, явных или подразумеваемых, относительно приведенных здесь сведений.
Изменяет порядок элементов в одномерном массиве Array или в части массива Array на обратный.
Перегрузки
Изменяет порядок подмножества элементов в одномерном массиве Array на обратный.
Изменяет порядок элементов во всем одномерном массиве Array на обратный.
Изменяет порядок последовательности элементов в одномерном общем массиве на обратный.
Изменяет порядок последовательности подмножества элементов в одномерном общем массиве на обратный.
Reverse(Array, Int32, Int32)
Изменяет порядок подмножества элементов в одномерном массиве Array на обратный.
Параметры
Одномерный массив Array, порядок элементов которого нужно изменить на обратный.
Начальный индекс той части массива, порядок элементов которой необходимо изменить на обратный.
Число элементов в части массива, порядок которых нужно изменить на обратный.
Исключения
Массив array является многомерным.
Значение параметра length меньше нуля.
Примеры
Комментарии
ReverseМетод можно использовать для отмены массива массивов.
Применяется к
Reverse(Array)
Изменяет порядок элементов во всем одномерном массиве Array на обратный.
Параметры
Одномерный массив Array, порядок элементов которого нужно изменить на обратный.
Исключения
Массив array является многомерным.
Примеры
Комментарии
Как показано в следующем примере, Reverse метод можно использовать для отмены массива массивов. Он инициализирует массив массива с одним элементом для каждого месяца текущего года в календаре текущего языка и региональных параметров. Каждый элемент содержит массив с количеством элементов, число которых в этом месяце — дней. В примере выводится содержимое массива, вызывается Reverse метод, а затем отображается содержимое обращенного массива.
Под катом приведен сравнительный анализ быстродействия разных методов переворачивания строки.
Кхрр-р-р… — сказала бензопила.
Тююю… — сказали мужики.
© Старый анекдот.
Ну что ж, начнем. Все реализации проверялись на быстродействие с одной строкой размером 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 нужного размера и идем по строке в обратном порядке, добавляя символы в новую строку.
Пробуем, запускаем, да… Как-то медленно работает это все, будем копать дальше.
2. ReverseArrayFramework
Ха! Так этот билдер же обставлен проверками для обеспечения потокобезопасности со всех сторон, не, нам такое не надо. Но строка — это ведь массив сиволов. Так давайте его и перевернем, а результат преобразуем обратно в строку:
Совсем другое дело, получилось в 3.5 раза быстрее. Хм, а может можно еще лучше?
3. ReverseArrayManual
Так, думаем. Во-первых у нас данные копируются дважы: сначала из строки в массив, потом внутри массива. Во-вторых Array.Reverse — библиотечный метод, значит в нем есть проверки входных данных. Более того, для атомарных типов он явно реализован в виде native метода, а это дополнительное переключение контекста выполнения. Попробуем перевернуть строку в массив вручную:
4. ReverseManualHalf
Идем дальше. У нас же действия симметричны относительно середины строки, значит можно пустить два индекса навстречу и ученьшить количество итераций вдвое:
Хм… Что-то пошло не так, на системе с медленной памятью скорость упала в полтора раза. Учитывая специфику конфигураций и реализации, можем предположить, что виноваты скорость памяти и кэш процессора: раньше мы работали с двумя отдаленными областями памяти одновременно, теперь их стало четыре, соответсвенно подхват данных выполняется чаще.
LINQ и метод Reverse
Есть еще относительно красивый и короткий способ с LINQ, но он не выдерживает никакой критики в плане производительности — работает в 3-3.5 раза медленнее метода на базе StringBuilder. Виной тому прокачивание данных через IEnumerable и виртуальный вызов на каждую итерацию. Для желающих, ниже приведена реализация:
Использование памяти
Проблема не столь критичная в большинстве случаев, но все «быстрые» из рассмотренных методов делают промежуточную копию строки в виде массива символов. На синтетических тестах это проявляется в том, что обернуть строку размером 512МБ смог только первый метод, остальные свалились по System.OutOfMemoryException. Также, не следует забывать, что лишние временные объекты повышают частоту срабатывания GC, а он хоть и оптимизирован до ужаса, но все-равно время кушает. В следующей части будем кроме скоростных оптимизаций также искать решение этой проблемы.
Часть вторая: когда хочется быстрее и эффективнее, или unsafe code.
Использование unsafe кода дает нам одно интересное преимущество: строки, которые раньше были immutable, теперь можно менять, но нужно быть предельно осторожным и изменять только копии строк — библиотека минимизирует количество копий одной строки, а вместе с интернированием строк это может привести к печальным последствиями для приложения.
Вооружившись этими знаниями пишем следующие две реализации.
5. ReverseUnsafeFill
Делаем строку из пробелов и заполняем ее в обратном порядке:
6. ReverseUnsafeCopy
Копируем и переворачиваем строку:
Как показали замеры, вторая версия работает заметно быстрее на медленной памяти и слегка медленнее на быстрой 🙂 Причин видимо несколько: оперирование двумя отдаленными областями памяти вместо четырех и различие в скорости копирования блока памяти и простого его заполнения в цикле. Желающие могут попробовать сделать версию ReverseUnsafeFill с полным проходом (это может уменьшить число захватов данных из памяти в кэш) и испытать ее на медленной памяти, однако у меня есть основания считать, что это будет все-равно медленнее ReverseUnsafeCopy (хотя могу и ошибаться).
7. ReverseUnsafeXorCopy
А что дальше? Ходят слухи, что обмен при помощи оператора XOR работает быстрее копирования через третью переменную (кстати в плюсах это еще и смотрится довольно красиво: «a ^= b ^= a ^= b;», в C#, увы, такая строка не cработает). Ну что, давайте проверим на деле.
В итоге получается в 1.2-1.5 раза медленнее обмена копированием. Трюк, работавший для быстрого обмена значений на регистрах, для переменных себя не оправдал (что характено, во многих компиляторах С/С++ он тоже выиграша не дает).
В поисках объяснения этого факта полезем внутрь приложения и почитаем результирующий CIL код.
Почему обмен через XOR оказался хуже
Для получения ответа на этот вопрос стоит посмотреть на CIL-код, сгенерированный для двух способов обмена. Чтоб эти инструкции казались понятнее, поясню их назначение: ldloc.N — загружает на стек локальную переменную под номером N, stloc.N — считывает верхушку стека в локальную переменную номер N, xor — вычисляет значение операции XOR для двух значений наверху стека и загружает результат на стек вместо них.
Алгоритм reverse()
template class BidirectionalIterator
reverse( BidirectionalIterator first,
Читайте также
8.1.1 Алгоритм
8.1.1 Алгоритм Сразу после переключения контекста ядро запускает алгоритм планирования выполнения процессов (Рисунок 8.1), выбирая на выполнение процесс с наивысшим приоритетом среди процессов, находящихся в состояниях «резервирования» и «готовности к выполнению, будучи
Расположить в обратном порядке (Reverse)
Расположить в обратном порядке (Reverse) template ‹class BidirectionalIterator›void reverse(BidirectionalIterator first, BidirectionalIterator last);Для каждого неотрицательного целого числа i‹=(last-first)/2 функция reverse применяет перестановку ко всем парам итераторов first+i, (last-i)-1. Выполняется точно (last-first)/2 перестановок.template
Обратные итераторы (Reverse iterators)
Обратные итераторы (Reverse iterators) Двунаправленные итераторы и итераторы произвольного доступа имеют соответствующие адаптеры обратных итераторов, которые выполняют итерации через структуру данных в противоположном направлении.Они имеют те же самые сигнатуры, как и
12.6.4. Операция list::reverse()
12.6.4. Операция list::reverse() void list::reverse();Операция reverse() изменяет порядок следования элементов списка на
Алгоритм max()
Алгоритм min()
Алгоритм mismatch()
Алгоритм mismatch() template class InputIterator1, class InputIterator2 pairInputIterator1, InputIterator2mismatch( InputIterator1 first,InputIterator1 last, InputIterator2 first2 );template class InputIterator1, class InputIterator2,class BinaryPredicate pairInputIterator1, InputIterator2mismatch( InputIterator1 first, InputIterator1 last,InputIterator2 first2, BinaryPredicate pred );mismatch() сравнивает две последовательности и находит
Алгоритм nth_element()
Алгоритм nth_element() template class RandomAccessIterator voidnth_element( RandomAccessIterator first,RandomAccessIterator nth,RandomAccessIterator last );template class RandomAccessIterator, class Compare voidnth_element( RandomAccessIterator first,RandomAccessIterator nth,RandomAccessIterator last, Compare comp );nth_element() переупорядочивает последовательность, ограниченную диапазоном [first,last), так что все
Алгоритм partial_sort()
Алгоритм partial_sort() template class RandomAccessIterator voidpartial_sort( RandomAccessIterator first,RandomAccessIterator middle,RandomAccessIterator last );templatepartial_sort() сортирует часть последовательности, укладывающуюся в диапазон [first,middle). Элементы в диапазоне [middle,last) остаются неотсортированными. Например, если дан массивint ia[] =
Алгоритм partial_sum()
Алгоритм partial_sum() template class InputIterator, class OutputIterator OutputIteratorpartial_sum(InputIterator first, InputIterator last,OutputIterator result );template class InputIterator, class OutputIterator,class BinaryOperation OutputIteratorpartial_sum(InputIterator first, InputIterator last,OutputIterator result, BinaryOperation op );Первый вариант partial_sum() создает из последовательности, ограниченной
Алгоритм partition()
Алгоритм partition() template class BidirectionalIterator, class UnaryPredicate BidirectionalIteratorpartition(BidirectionalIterator first,BidirectionalIterator last, UnaryPredicate pred );partition() переупорядочивает элементы в диапазоне [first,last). Все элементы, для которых предикат pred равен true, помещаются перед элементами, для которых он равен false.
Алгоритм random_shuffle()
Алгоритм random_shuffle() template class RandomAccessIterator voidrandom_shuffle( RandomAccessIterator first,RandomAccessIterator last );template class RandomAccessIterator,class RandomNumberGenerator voidrandom_shuffle( RandomAccessIterator first,RandomAccessIterator last,RandomNumberGenerator rand);random_shuffle() переставляет элементы из диапазона [first,last) в случайном порядке. Во втором варианте можно
Метод Reverse
Метод Reverse Описание методовМетоды приведены для последовательности sequence of T. function Reverse(): sequence of T; Возвращает инвертированную
Что делает reverse c
К сожалению, класс String в C# не содержит метода Reverse(), поэтому вот три способа как можно реверсировать строку:
1. Ручное реверсирование
Самый очевидный способ это реверсировать строку с помощью ручного прохода по ее символам и формирования новой строки:
Учтите, что если вы воспользуетесь этим подходом в серьезной программе, вы должны использовать StringBuilder вместо String, так как в вышеприведенном коде новая временная строка создается каждый раз когда вы добавляете отдельный символ в выходную строку.
2. Array.Reverse()
Вторым способ с помощью которого мы можем реверсировать строку является статический метод Array.Reverse():
Сначала мы конвертируем строку в массив символов, затем реверсируем массив, и наконец формируем новую строку из масиива.
3. LINQ
LINQ позволяет нам сократить реверсирование строки в одну линию:
Сначала строка снова конвертируется в массив символов. Массив (Array) реализует интерфейс IEnumerable, так что мы можем вызвать LINQ метод Reverse() на нем. С помощью вызова метода ToArray() результирующий IEnumerable снова конвертируется в массив символов, которы используется в конструкторе строки.
Для максимального удобства мы можем создать метод расширения (extension method) для класса String чтобы выполнять реверсирование:
С помощью этого класса в нашем коде мы теперь можем с легкостью реверсировать любую строку:
Однако учтите, что все методы для реверсирования строки приведенные выше работают только с 16 битными символами Unicode, которые помещаются в одну символьную переменную. Если вам необходимо реверсировать строки которые содержат расширенные символы Unicode, например chinese kanji, смотрите здесь.