Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 86, средняя оценка - 4.76
Zilon
5 / 5 / 1
Регистрация: 05.11.2010
Сообщений: 60
#1

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

05.11.2010, 04:43. Просмотров 13440. Ответов 84
Метки нет (Все метки)

На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки.
Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ.
Так какое же у этой простой задачки может быть оригинальное решение?
http://www.cyberforum.ru/cpp-beginners/thread864422.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2010, 04:43
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Функция реверса строки (C++):

Написание программы реверса строки
Не могу понять в чем ошибка выдаёт (2 3 3 3 3 3 3 3 3 3) Прошу помощи в...

Программа реверса строки: почему на экран выводится мусор, вместо нужного текста?
Пишу программу реверса строки (меняет местами первый символ и последний, второй...

Реализация реверса массива
Первый и последний элемент массива трогать не надо. Как его толком перевернуть?...

Функция: поместить все цифры в начало строки, а буквы в конец строки
Дана строка, состоящая из букв и цифр. Написать функцию, которая помещает все...

Функция перезаписывает символы строки заданным количеством символов другой строки
Программа работает. Но не совсем правильно. В конечной строке появляются...

84
Kastaneda
Jesus loves me
Эксперт С++
4760 / 2963 / 340
Регистрация: 12.12.2009
Сообщений: 7,523
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 13:34 #21
Genius Ignat, возможно мы говорим немного о разных вещах. Я по поводу ваших слов "XOR не всегда быстрая операция", не понимаю как так "не всегда". Это быстрая операция, но это не значит, что она самая быстрая из команд процессора x86 и ею нужно заменять все подряд. Если reverse из STL написан не через XOR, значит на то есть причины) Снимки, которые я выложил - это справочник по ассемблеру (правда для 16 бит), там видно, что XOR и MOV выполняются за абсолютно равное время, так что реализации реверса через XOR и через Temp (теоретически, смотря какой код сгенерирует компилятор) абсолютно равны по скорости! Использовать XOR или Temp - это дело автора кода.

Добавлено через 1 минуту
А вот про какую еще оптимизацию говорит ТС, я прям не знаю.
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 13:56 #22
Kastaneda:
Вот и не будем, спорить, тем более, тема не особа интересна.

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

Добавлено через 17 минут
Извиняюсь, по поводу STL ступил,
потому как reverse из STL обобщенная реализация для любых типов,
а XOR работает только со стандартными.
0
Zilon
5 / 5 / 1
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 14:01  [ТС] #23
Не массив указателей.
0
slice
63 / 78 / 6
Регистрация: 04.11.2010
Сообщений: 249
05.11.2010, 14:41 #24
Так что ле обменивать переменные надо:
C++
1
a ^= (b ^= (a ^= b));
?
0
Zilon
5 / 5 / 1
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 14:44  [ТС] #25
Кажется да.
Собственно так я это решение и нашел. Мы с другом соревновались кто за меньшее количество строчек это напишет.
0
Kastaneda
Jesus loves me
Эксперт С++
4760 / 2963 / 340
Регистрация: 12.12.2009
Сообщений: 7,523
Записей в блоге: 2
Завершенные тесты: 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 минут
заморочился с компилятором, похоже я привел не самый удачный пример(, но общий смысл в том, что разное кол-во строк кода на С/С++ могут компилироваться в одинаковое кол-во ассемблерного кода)

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

Добавлено через 3 минуты
По поводу строк. Речь шла о строках С++. И хоть 3 ксора компилер развернет, но в одной строчке свап смотрится немного дико, что не может не внушать оптимизма . А 3 приравнивания в одну строку не впихнешь(запетые не в счет).
0
Kastaneda
Jesus loves me
Эксперт С++
4760 / 2963 / 340
Регистрация: 12.12.2009
Сообщений: 7,523
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 15:29 #28
Может уже решение в студию??)
0
Zilon
5 / 5 / 1
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 15:46  [ТС] #29
Ок, досмотрю фильм и налабаю. Может кто-то за полтора часа и придумает.
А вы если подобные задачки знаете - выкладывайте, не стесняйтесь
0
slice
63 / 78 / 6
Регистрация: 04.11.2010
Сообщений: 249
05.11.2010, 16:01 #30
Цитата Сообщение от Zilon Посмотреть сообщение
досмотрю фильм
что смотришь?
0
Kastaneda
Jesus loves me
Эксперт С++
4760 / 2963 / 340
Регистрация: 12.12.2009
Сообщений: 7,523
Записей в блоге: 2
Завершенные тесты: 1
05.11.2010, 16:20 #31
Цитата Сообщение от Zilon Посмотреть сообщение
А вы если подобные задачки знаете - выкладывайте, не стесняйтесь
Вообще-то есть тема http://www.cyberforum.ru/cpp-beginners/thread153746.html , помимо того, что выделенно в первом посте, там еще много чего (типа того, что здесь обсуждается)
0
Zilon
5 / 5 / 1
Регистрация: 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--);
    }
}
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:17 #33
Zilon:
В чем прикол, использование арифметики указателей?? или что??.
0
Zilon
5 / 5 / 1
Регистрация: 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;
    }
и деление в цикле (хотя компилер скорей всего его вынес за цикл.)
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:44 #35
Zilon:
Ну и чем хотел меня удивить, надо было мне в начале, с арифметикой сделать, и вопрос был бы решен.
0
Zilon
5 / 5 / 1
Регистрация: 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)
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:45 #37
Zilon:
Ну и чему тут можно удивиться,
надо было мне в начале, с арифметикой сделать, и вопрос был бы решен.
0
Zilon
5 / 5 / 1
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:48  [ТС] #38
Цитата Сообщение от Genius Ignat Посмотреть сообщение
надо было мне в начале, с арифметикой сделать, и вопрос был бы решен
Что ты имеешь ввиду?
0
Genius Ignat
1241 / 779 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:51 #39
Zilon:
То, что переделывать было уже нечего, разве что XOR припаять.
0
Zilon
5 / 5 / 1
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 18:54  [ТС] #40
Удивляться или нет - это личное дело каждого.
Мы говорили о варианте более оптимизированном по скорости чем те что были выложены. Вот он. Обоснование я уже выложил, но по моему это и так видно. А как я писал ранее - оптимизация будет не столько алгоритмическая сколько на уровне реализации. Хотя работая с такими атомарными вещами они алгоритм сливается с реализацией.
0
05.11.2010, 18:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2010, 18:54
Привет! Вот еще темы с решениями:

Функция разделения строки в массив отдельных частей этой строки
Помогите написать функцию, которая на вход принимает строку типа String и...

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

функция и строки
Составить функцию, которая позволяет определить позицию первого вхождения в...

Функция, Указатели, Строки
Уважаемые програмисты требуется помощ в решении задач . По теме &lt;&lt;Функция&gt;&gt;...


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru