Форум программистов, компьютерный форум CyberForum.ru

Функция реверса строки - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 86, средняя оценка - 4.76
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 04:43     Функция реверса строки #1
На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки.
Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ.
Так какое же у этой простой задачки может быть оригинальное решение?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 13:34     Функция реверса строки #21
Genius Ignat, возможно мы говорим немного о разных вещах. Я по поводу ваших слов "XOR не всегда быстрая операция", не понимаю как так "не всегда". Это быстрая операция, но это не значит, что она самая быстрая из команд процессора x86 и ею нужно заменять все подряд. Если reverse из STL написан не через XOR, значит на то есть причины) Снимки, которые я выложил - это справочник по ассемблеру (правда для 16 бит), там видно, что XOR и MOV выполняются за абсолютно равное время, так что реализации реверса через XOR и через Temp (теоретически, смотря какой код сгенерирует компилятор) абсолютно равны по скорости! Использовать XOR или Temp - это дело автора кода.

Добавлено через 1 минуту
А вот про какую еще оптимизацию говорит ТС, я прям не знаю.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:56     Функция реверса строки #22
Kastaneda:
Вот и не будем, спорить, тем более, тема не особа интересна.

По поводу, обменов, могу предложить использовать массив указателей,
моя идея в сторону оптимизации,
Правда, для символов не какой оптимизации не будет,
а для больших объектов такая оптимизация существенна.

Добавлено через 17 минут
Извиняюсь, по поводу STL ступил,
потому как reverse из STL обобщенная реализация для любых типов,
а XOR работает только со стандартными.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 14:01  [ТС]     Функция реверса строки #23
Не массив указателей.
slice
32 / 75 / 4
Регистрация: 04.11.2010
Сообщений: 249
05.11.2010, 14:41     Функция реверса строки #24
Так что ле обменивать переменные надо:
C++
1
a ^= (b ^= (a ^= b));
?
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 14:44  [ТС]     Функция реверса строки #25
Кажется да.
Собственно так я это решение и нашел. Мы с другом соревновались кто за меньшее количество строчек это напишет.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 15:17     Функция реверса строки #26
slice, оптимизации здесь нет (я ж такой же код написал)

Не по теме:

к вечеру окажется, что ТС имел ввиду какую-нибудь фигню, не имеющую к оптимизации ни какого отношения)))



Добавлено через 41 секунду
Цитата Сообщение от Zilon Посмотреть сообщение
Кажется да.
Собственно так я это решение и нашел. Мы с другом соревновались кто за меньшее количество строчек это напишет.
Так ЭТО по вашему оптимизация???

Добавлено через 11 минут

Не по теме:

Хочется вставить свои 5 копеек)))
например есть такой код:

C++
1
2
3
int foo(){
   return 100;
}
а еще есть такой:
C++
1
2
3
4
5
int foo(){
   int x;
   x=100;
   return x;
}
казалось бы первый код короче и выполнится быстрее, но на деле компилятор сгенерирует одинаковый код, что-то типа:
Assembler
1
2
3
mov eax,[some adress] ;пишу сходу , но
mov eax,100 ; можно заморочится и проверить компилятором
mov [some adress],eax
т.е. обе вышепреведенные ф-ции займут одинаковое кол-во байт в программе и выполнятся за одинаковое кол-во тактов.
Нужно понимать, что есть оптимизация.



Не по теме:

Добавлено через 18 минут
заморочился с компилятором, похоже я привел не самый удачный пример(, но общий смысл в том, что разное кол-во строк кода на С/С++ могут компилироваться в одинаковое кол-во ассемблерного кода)

Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 15:26  [ТС]     Функция реверса строки #27
Kastaneda все верно. Это 2 формы одного и того же.
Это не та 2-я оптимизация. За оптимизацию по скорости не волнуйтесь, она там есть. А ксоры, как я уже говорил, просто фишка.

Добавлено через 3 минуты
По поводу строк. Речь шла о строках С++. И хоть 3 ксора компилер развернет, но в одной строчке свап смотрится немного дико, что не может не внушать оптимизма . А 3 приравнивания в одну строку не впихнешь(запетые не в счет).
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 15:29     Функция реверса строки #28
Может уже решение в студию??)
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 15:46  [ТС]     Функция реверса строки #29
Ок, досмотрю фильм и налабаю. Может кто-то за полтора часа и придумает.
А вы если подобные задачки знаете - выкладывайте, не стесняйтесь
slice
32 / 75 / 4
Регистрация: 04.11.2010
Сообщений: 249
05.11.2010, 16:01     Функция реверса строки #30
Цитата Сообщение от Zilon Посмотреть сообщение
досмотрю фильм
что смотришь?
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 16:20     Функция реверса строки #31
Цитата Сообщение от Zilon Посмотреть сообщение
А вы если подобные задачки знаете - выкладывайте, не стесняйтесь
Вообще-то есть тема http://www.cyberforum.ru/cpp-beginne...ead153746.html , помимо того, что выделенно в первом посте, там еще много чего (типа того, что здесь обсуждается)
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:12  [ТС]     Функция реверса строки #32
Только что досмотрел "V значит вендетта". Ух-ты! Вот какой фильм. Год вокруг него ходил, сморя на постер, решил что это отстой. Оказалось нет.
Минут через 10 выложу решение.

Добавлено через 10 минут
Вот полное решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
void revert(int arr[], int N)
{
    int* left = arr;
    int* right = &arr[N - 1];
 
    while(left < right)
    {
        *left ^= *right;
        *right ^= *left;
        *(left++) ^= *(right--);
    }
}
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:17     Функция реверса строки #33
Zilon:
В чем прикол, использование арифметики указателей?? или что??.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:33  [ТС]     Функция реверса строки #34
По пунктам.
1. ушел i--; +1 операция
2. пришло left++ и right-- -1 операция
Что такое arr[i]? Согласно стандарту arr[i] = *(arr + i);
В этом вареанте
C++
1
2
3
4
5
6
7
while( j > i ){
  tmp = str[i];
  str[i] = str[j];
  str[j] = tmp;
  i++;
  j--;
}
наименьшее количество лишних суммирований (4 лишних), хотя мы так же имеем 2 итератора.
3. Итого если сравневать с самым быстрым из выложенных (Genius Ignat) имеем выиграш 4 суммирования. Учитывая что количество операций невелико (помоему меньше 15) то теперь имеем 11. Позже могу посмотреть асм. код.
А ведь исходный вариант имел еще больше сумирований:
C++
1
2
3
4
5
6
    for(i = 0; i < num / 2; i++)
        {
        temp = arr[i];
        arr[i] = arr[num - i - 1];
        arr[num - i - 1] = temp;
    }
и деление в цикле (хотя компилер скорей всего его вынес за цикл.)
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:44     Функция реверса строки #35
Zilon:
Ну и чем хотел меня удивить, надо было мне в начале, с арифметикой сделать, и вопрос был бы решен.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:45  [ТС]     Функция реверса строки #36
Вот во что Visual Studia превратила вариант с указателями:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
00401081  lea         eax,[esp+8] 
00401085  lea         ecx,[esp+20h] 
00401089  lea         esp,[esp] 
00401090  mov         edx,dword ptr [ecx] 
00401092  xor         dword ptr [eax],edx 
00401094  mov         edx,dword ptr [eax] 
00401096  xor         dword ptr [ecx],edx 
00401098  mov         edx,dword ptr [ecx] 
0040109A  xor         dword ptr [eax],edx 
0040109C  sub         ecx,4 
0040109F  add         eax,4 
004010A2  cmp         eax,ecx 
004010A4  jb          revertTest+70h (401090h)
Вот решение Genius Ignat:

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
00401084  xor         eax,eax 
00401086  mov         ecx,6 
0040108B  jmp         revertTest+70h (401090h) 
0040108D  lea         ecx,[ecx] 
00401090  mov         esi,dword ptr [esp+ecx*4+8] 
00401094  mov         edx,dword ptr [esp+eax*4+8] 
00401098  mov         dword ptr [esp+eax*4+8],esi 
0040109C  mov         dword ptr [esp+ecx*4+8],edx 
004010A0  inc         eax  
004010A1  dec         ecx  
004010A2  cmp         ecx,eax 
004010A4  jg          revertTest+70h (401090h)
А вот исходное:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
00401081  xor         eax,eax 
00401083  lea         ecx,[esp+20h] 
00401087  jmp         revertTest+70h (401090h) 
00401089  lea         esp,[esp] 
00401090  mov         esi,dword ptr [ecx] 
00401092  mov         edx,dword ptr [esp+eax*4+8] 
00401096  mov         dword ptr [esp+eax*4+8],esi 
0040109A  mov         dword ptr [ecx],edx 
0040109C  inc         eax  
0040109D  sub         ecx,4 
004010A0  cmp         eax,3 
004010A3  jl          revertTest+70h (401090h)
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:45     Функция реверса строки #37
Zilon:
Ну и чему тут можно удивиться,
надо было мне в начале, с арифметикой сделать, и вопрос был бы решен.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:48  [ТС]     Функция реверса строки #38
Цитата Сообщение от Genius Ignat Посмотреть сообщение
надо было мне в начале, с арифметикой сделать, и вопрос был бы решен
Что ты имеешь ввиду?
Genius Ignat
1233 / 771 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:51     Функция реверса строки #39
Zilon:
То, что переделывать было уже нечего, разве что XOR припаять.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2010, 18:54     Функция реверса строки
Еще ссылки по теме:

C++ Функция удаления подстроки из строки
C++ ф-ция реверса строки
C++ Функция перезаписывает символы строки заданным количеством символов другой строки

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:54  [ТС]     Функция реверса строки #40
Удивляться или нет - это личное дело каждого.
Мы говорили о варианте более оптимизированном по скорости чем те что были выложены. Вот он. Обоснование я уже выложил, но по моему это и так видно. А как я писал ранее - оптимизация будет не столько алгоритмическая сколько на уровне реализации. Хотя работая с такими атомарными вещами они алгоритм сливается с реализацией.
Yandex
Объявления
05.11.2010, 18:54     Функция реверса строки
Ответ Создать тему
Опции темы

Текущее время: 15:19. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru