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

@Zilon · Регистрация: 05.11.2010

Author24 — интернет-сервис помощи студентам

На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки.
Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ.
Так какое же у этой простой задачки может быть оригинальное решение?

@Kastaneda · 05.11.2010, 13:34

Genius Ignat, возможно мы говорим немного о разных вещах. Я по поводу ваших слов "XOR не всегда быстрая операция", не понимаю как так "не всегда". Это быстрая операция, но это не значит, что она самая быстрая из команд процессора x86 и ею нужно заменять все подряд. Если reverse из STL написан не через XOR, значит на то есть причины) Снимки, которые я выложил - это справочник по ассемблеру (правда для 16 бит), там видно, что XOR и MOV выполняются за абсолютно равное время, так что реализации реверса через XOR и через Temp (теоретически, смотря какой код сгенерирует компилятор) абсолютно равны по скорости! Использовать XOR или Temp - это дело автора кода.

Добавлено через 1 минуту
А вот про какую еще оптимизацию говорит ТС, я прям не знаю.

@Ignat · 05.11.2010, 13:56

Kastaneda:
Вот и не будем, спорить, тем более, тема не особа интересна.

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

Добавлено через 17 минут
Извиняюсь, по поводу STL ступил,
потому как reverse из STL обобщенная реализация для любых типов,
а XOR работает только со стандартными.

@Zilon · 05.11.2010, 14:01 **[ТС]**

Не массив указателей.

@slice · 05.11.2010, 14:41

Так что ле обменивать переменные надо:

C++

1	a ^= (b ^= (a ^= b));

?

@Zilon · 05.11.2010, 14:44 **[ТС]**

Кажется да.
Собственно так я это решение и нашел. Мы с другом соревновались кто за меньшее количество строчек это напишет.

@Kastaneda · 05.11.2010, 15:17

slice, оптимизации здесь нет (я ж такой же код написал)

Не по теме:

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

Добавлено через 41 секунду

Сообщение от Zilon

Кажется да.
Собственно так я это решение и нашел. Мы с другом соревновались кто за меньшее количество строчек это напишет.

Так ЭТО по вашему оптимизация???

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

Не по теме:

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

C++

1
2
3

int foo(){
   return 100;
}

а еще есть такой:

C++

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 · 05.11.2010, 15:26 **[ТС]**

Kastaneda все верно. Это 2 формы одного и того же.
Это не та 2-я оптимизация. За оптимизацию по скорости не волнуйтесь, она там есть. А ксоры, как я уже говорил, просто фишка.

Добавлено через 3 минуты
По поводу строк. Речь шла о строках С++. И хоть 3 ксора компилер развернет, но в одной строчке свап смотрится немного дико, что не может не внушать оптимизма

. А 3 приравнивания в одну строку не впихнешь(запетые не в счет).

@Kastaneda · 05.11.2010, 15:29

Может уже решение в студию??)

@Zilon · 05.11.2010, 15:46 **[ТС]**

Ок, досмотрю фильм и налабаю. Может кто-то за полтора часа и придумает.
А вы если подобные задачки знаете - выкладывайте, не стесняйтесь

@slice · 05.11.2010, 16:01

Сообщение от Zilon

досмотрю фильм

что смотришь?

@Kastaneda · 05.11.2010, 16:20

Сообщение от Zilon

А вы если подобные задачки знаете - выкладывайте, не стесняйтесь

Вообще-то есть тема https://www.cyberforum.ru/cpp-... 53746.html , помимо того, что выделенно в первом посте, там еще много чего (типа того, что здесь обсуждается)

@Zilon · 05.11.2010, 18:12 **[ТС]**

Только что досмотрел "V значит вендетта". Ух-ты! Вот какой фильм. Год вокруг него ходил, сморя на постер, решил что это отстой. Оказалось нет.
Минут через 10 выложу решение.

Добавлено через 10 минут
Вот полное решение:

C++

void revert(int arr[], int N)
{
    int* left = arr;
    int* right = &arr[N - 1];
 
    while(left < right)
    {
        *left ^= *right;
        *right ^= *left;
        *(left++) ^= *(right--);
    }
}

@Ignat · 05.11.2010, 18:17

Zilon:
В чем прикол, использование арифметики указателей?? или что??.

@Zilon · 05.11.2010, 18:33 **[ТС]**

По пунктам.
1. ушел i--; +1 операция
2. пришло left++ и right-- -1 операция
Что такое arr[i]? Согласно стандарту arr[i] = *(arr + i);
В этом вареанте

C++

while( j > i ){
  tmp = str[i];
  str[i] = str[j];
  str[j] = tmp;
  i++;
  j--;
}

наименьшее количество лишних суммирований (4 лишних), хотя мы так же имеем 2 итератора.
3. Итого если сравневать с самым быстрым из выложенных (Genius Ignat) имеем выиграш 4 суммирования. Учитывая что количество операций невелико (помоему меньше 15) то теперь имеем 11. Позже могу посмотреть асм. код.
А ведь исходный вариант имел еще больше сумирований:

C++

    for(i = 0; i < num / 2; i++)
        {
        temp = arr[i];
        arr[i] = arr[num - i - 1];
        arr[num - i - 1] = temp;
    }

и деление в цикле (хотя компилер скорей всего его вынес за цикл.)

@Ignat · 05.11.2010, 18:44

Zilon:
Ну и чем хотел меня удивить, надо было мне в начале, с арифметикой сделать, и вопрос был бы решен.

@Zilon · 05.11.2010, 18:45 **[ТС]**

Вот во что Visual Studia превратила вариант с указателями:

Assembler

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

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

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)

@Ignat · 05.11.2010, 18:45

Zilon:
Ну и чему тут можно удивиться,
надо было мне в начале, с арифметикой сделать, и вопрос был бы решен.

@Zilon · 05.11.2010, 18:48 **[ТС]**

Сообщение от Genius Ignat

надо было мне в начале, с арифметикой сделать, и вопрос был бы решен

Что ты имеешь ввиду?

@Ignat · 05.11.2010, 18:51

Zilon:
То, что переделывать было уже нечего, разве что XOR припаять.

@Zilon · 05.11.2010, 18:54 **[ТС]**

Удивляться или нет - это личное дело каждого.
Мы говорили о варианте более оптимизированном по скорости чем те что были выложены. Вот он. Обоснование я уже выложил, но по моему это и так видно. А как я писал ранее - оптимизация будет не столько алгоритмическая сколько на уровне реализации. Хотя работая с такими атомарными вещами они алгоритм сливается с реализацией.

@Kastaneda 5231 / 3204 / 362 Регистрация: 12.12.2009 Сообщений: 8,116 Записей в блоге: 2
	05.11.2010, 13:34	21
	Genius Ignat, возможно мы говорим немного о разных вещах. Я по поводу ваших слов "XOR не всегда быстрая операция", не понимаю как так "не всегда". Это быстрая операция, но это не значит, что она самая быстрая из команд процессора x86 и ею нужно заменять все подряд. Если reverse из STL написан не через XOR, значит на то есть причины) Снимки, которые я выложил - это справочник по ассемблеру (правда для 16 бит), там видно, что XOR и MOV выполняются за абсолютно равное время, так что реализации реверса через XOR и через Temp (теоретически, смотря какой код сгенерирует компилятор) абсолютно равны по скорости! Использовать XOR или Temp - это дело автора кода. Добавлено через 1 минуту А вот про какую еще оптимизацию говорит ТС, я прям не знаю. 0

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	05.11.2010, 13:56	22
	Kastaneda: Вот и не будем, спорить, тем более, тема не особа интересна. По поводу, обменов, могу предложить использовать массив указателей, моя идея в сторону оптимизации, Правда, для символов не какой оптимизации не будет, а для больших объектов такая оптимизация существенна. Добавлено через 17 минут Извиняюсь, по поводу STL ступил, потому как reverse из STL обобщенная реализация для любых типов, а XOR работает только со стандартными. 0

@Zilon 6 / 6 / 0 Регистрация: 05.11.2010 Сообщений: 60
	05.11.2010, 14:01 [ТС]	23
	Не массив указателей. 0

@Zilon 6 / 6 / 0 Регистрация: 05.11.2010 Сообщений: 60
	05.11.2010, 14:44 [ТС]	25
	Кажется да. Собственно так я это решение и нашел. Мы с другом соревновались кто за меньшее количество строчек это напишет. 0

@Zilon 6 / 6 / 0 Регистрация: 05.11.2010 Сообщений: 60
	05.11.2010, 15:26 [ТС]	27
	Kastaneda все верно. Это 2 формы одного и того же. Это не та 2-я оптимизация. За оптимизацию по скорости не волнуйтесь, она там есть. А ксоры, как я уже говорил, просто фишка. Добавлено через 3 минуты По поводу строк. Речь шла о строках С++. И хоть 3 ксора компилер развернет, но в одной строчке свап смотрится немного дико, что не может не внушать оптимизма . А 3 приравнивания в одну строку не впихнешь(запетые не в счет). 0

@Zilon 6 / 6 / 0 Регистрация: 05.11.2010 Сообщений: 60
		1
	Функция реверса строки 05.11.2010, 04:43. Показов 44438. Ответов 85 Метки нет (Все метки) На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки. Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ. Так какое же у этой простой задачки может быть оригинальное решение? 0

@Kastaneda 5231 / 3204 / 362 Регистрация: 12.12.2009 Сообщений: 8,116 Записей в блоге: 2
	05.11.2010, 15:29	28
	Может уже решение в студию??) 0

@Zilon 6 / 6 / 0 Регистрация: 05.11.2010 Сообщений: 60
	05.11.2010, 15:46 [ТС]	29
	Ок, досмотрю фильм и налабаю. Может кто-то за полтора часа и придумает. А вы если подобные задачки знаете - выкладывайте, не стесняйтесь 0

@slice 79 / 78 / 6 Регистрация: 04.11.2010 Сообщений: 249
	05.11.2010, 16:01	30
	Сообщение от Zilon досмотрю фильм что смотришь? 0

@Kastaneda 5231 / 3204 / 362 Регистрация: 12.12.2009 Сообщений: 8,116 Записей в блоге: 2
	05.11.2010, 16:20	31
	Сообщение от Zilon А вы если подобные задачки знаете - выкладывайте, не стесняйтесь Вообще-то есть тема https://www.cyberforum.ru/cpp-... 53746.html , помимо того, что выделенно в первом посте, там еще много чего (типа того, что здесь обсуждается) 0

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	05.11.2010, 18:17	33
	Zilon: В чем прикол, использование арифметики указателей?? или что??. 0

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	05.11.2010, 18:44	35
	Zilon: Ну и чем хотел меня удивить, надо было мне в начале, с арифметикой сделать, и вопрос был бы решен. 0

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	05.11.2010, 18:45	37
	Zilon: Ну и чему тут можно удивиться, надо было мне в начале, с арифметикой сделать, и вопрос был бы решен. 0

@Zilon 6 / 6 / 0 Регистрация: 05.11.2010 Сообщений: 60
	05.11.2010, 18:48 [ТС]	38
	Сообщение от Genius Ignat надо было мне в начале, с арифметикой сделать, и вопрос был бы решен Что ты имеешь ввиду? 0

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	05.11.2010, 18:51	39
	Zilon: То, что переделывать было уже нечего, разве что XOR припаять. 0

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