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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 86, средняя оценка - 4.76
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
#1

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

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

На собеседовании в одну компанию меня попросили на бумажке написать функцию реверса строки.
Буквально парой дней раньше я услышал о том что на собеседованиях частенько просят решить именно эту задачу. Ее простота насторожила меня и заставила искать наиболее красивое/оптимизированное/необычное решение. И я его таки нашел и малость перестарался. Как я узнал позже интервьюер решил что я дал неверный ответ.
Так какое же у этой простой задачки может быть оригинальное решение?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2010, 04:43     Функция реверса строки
Посмотрите здесь:

ф-ция реверса строки - C++
был вчера на собеседовании, попросили написать ф-цию реверса строки (поменять местами 1й и последний символы, 2й и предпоследний и т.д.),...

Написание программы реверса строки - C++
Не могу понять в чем ошибка выдаёт (2 3 3 3 3 3 3 3 3 3) Прошу помощи в нахождении ошибки. #include "stdafx.h" #include <stdio.h> ...

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

Реализация реверса массива - C++
Первый и последний элемент массива трогать не надо. Как его толком перевернуть? По-разному пробовал уже, не хотят циферки по серединке...

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

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

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 18:56     Функция реверса строки #41
Zilon:
А если язык программирования, не позволяет так шалить с адресами,
где тогда оптимизации.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:02  [ТС]     Функция реверса строки #42
Тебе не видна разница между arr[i] и *left?
первое - это *(arr + i) второе не меняется *left.
4 лишних суммирования.

Добавлено через 4 минуты
Мы в разделе с/с++.
Я решил не уточнять язык исполнения.
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 19:03     Функция реверса строки #43
Zilon:
Такое ощущение, что ты мне экзамен устроил.
Если бы я писал решение через арифметику указателя, тогда индексация отсутствовала,
потому как ее применение было не уместно.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:07  [ТС]     Функция реверса строки #44
Если что сорри, не хотел тебя задеть.
Однако ясно же сказал "оптимизированное по скорости" и про то что "не алгоритмом единым...", т.е. дело в реализации.
Если бы я начал наводить людей на мысли то в чем тогда смысл головоломки?
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 19:12     Функция реверса строки #45
Zilon:
Ладно, если уж хочешь развития темы, тогда приведи, еще какой нибудь алгоритм
решения данной задачи,
просто ради интереса, я знаю еще три решения, правда, они менее эффективны
чем рассмотренный вариант.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:16  [ТС]     Функция реверса строки #46
Еще 3 решения? Насколько принципиальны их отличия?
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 19:19     Функция реверса строки #47
Zilon:
на много, возможно ты додумаешься, может даже четвертое придумаешь.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:24  [ТС]     Функция реверса строки #48
А вариантов может быть много, но все похожи - можно выделить память и 2 раза скопировать данные в разных направлениях, можно с середины начать и пр. Это все в принципе одно и то же. Друге варианты в голову не приходят. Так что там за варианты?

Добавлено через 2 минуты
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Zilon:
на много, возможно ты додумаешься, может даже четвертое придумаешь.
Отличия более принципиальны нежели я назвал?
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 19:25     Функция реверса строки #49
Друге варианты в голову не приходят. Так что там за варианты?
Сначала подумай сам, потом выложу решения(если ни чего не придумаешь),

Если я сейчас выложу, то это читерство получается.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:30  [ТС]     Функция реверса строки #50
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Если я сейчас выложу, то это читерство получается.
Эти алгоритмы делаю такой же реверс строки, и при этом являются не абсурдными, без всякого читерства вроде вызова библиотечных функций и при этом значительно (то есть отличимо) отличаются алгоритмом от всего здесь написанного? А это вообще реально?
Genius Ignat
1235 / 773 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
05.11.2010, 19:33     Функция реверса строки #51
Zilon:
Все реально.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 19:49  [ТС]     Функция реверса строки #52
И соблюдены все условия? Если да, то я хочу пива. Под пивко раньше алгоритмами занимался.

Добавлено через 13 минут
Из идей только есть только варианты перестановок в разных порядках.
1. начинаем с середины и идем к краям.
2. проходимся змейкой по схеме 1 : n, n-1 : 2, 3 : n - 2, и т.д.
3. Создаем буфер такого же размера, линейно копируем элементы от n-го до 1-го (в обратном порядке) затем мемкопи.

Добавлено через 1 минуту
Но все это (кроме варианта 3) как то похоже.
KpeHDeJIb
56 / 56 / 3
Регистрация: 31.10.2010
Сообщений: 103
05.11.2010, 20:35     Функция реверса строки #53
Мне одному кажется странным что в функции переворачивания строки используется указатель на int, но при этом нигде не проверяется что хвост строки укладывается в sizeof(int)?

И вот уже приведенный вариант используется и у меня, примерно также:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <string.h>
 
inline static void swappchar(char *a, char *b)
{
    char tmp = *a;
    *a = *b;
    *b = tmp;
}
 
char *revert(char *string)
{
    size_t len = strlen(string);
    char   *begin = string, *end = string + len - 1;
 
    while (begin < end)
        swappchar(begin++, end--);
 
    return string;
}
 
int main()
{
    char string[] = "Hello, World! 1234";
    printf("Original string %s\n", string);
    printf("Reverted string %s\n", revert(string));
    return 0;
}
Kastaneda
Форумчанин
Эксперт С++
4489 / 2851 / 227
Регистрация: 12.12.2009
Сообщений: 7,245
Записей в блоге: 1
Завершенные тесты: 1
05.11.2010, 20:42     Функция реверса строки #54
Цитата Сообщение от Zilon Посмотреть сообщение
Вот во что Visual Studia превратила вариант с указателями:
Assembler
1
АСМ код
так в чем выигрыш вашего примера??? Он длиннее всех получился, соответственно занимает больше байт в экзешнике. Разве, что по тактам посчитать, но и то врядли будет быстрее.
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 22:32  [ТС]     Функция реверса строки #55
Цитата Сообщение от KpeHDeJIb Посмотреть сообщение
Мне одному кажется странным что в функции переворачивания строки используется указатель на int
В начале темы было оговорено что для данной задачи можна игнорить '\0'. Пусть это будет просто массив.

Добавлено через 9 минут
Цитата Сообщение от Kastaneda Посмотреть сообщение
так в чем выигрыш вашего примера??? Он длиннее всех получился, соответственно занимает больше байт в экзешнике. Разве, что по тактам посчитать, но и то врядли будет быстрее.
Да, он длиннее. На одну строку. Но я уже не застал те времена когда ради 100 кб размера экзешника готов был бы платить хотя бы 3% скорости. А тут проигаш аж на 4 - 8 байт. Теперь по поводу скорости:
Это:

Assembler
1
2
3
4
5
6
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
на мой суровый взгляд исполняется быстрее чем это:

Assembler
1
2
3
4
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
Поскольку здесь на каждый мув еще считается "esp+ecx*4+8"
KpeHDeJIb
56 / 56 / 3
Регистрация: 31.10.2010
Сообщений: 103
05.11.2010, 23:19     Функция реверса строки #56
Цитата Сообщение от Zilon Посмотреть сообщение
Поскольку здесь на каждый мув еще считается "esp+ecx*4+8"
Опять на спичках экономите. Теперь покажите мне хоть одну программу, где бы функция разворачивания строки была бы bottleneck
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
05.11.2010, 23:54  [ТС]     Функция реверса строки #57
О, да. Поскольку именно эти спички являются темой нашей беседы
KpeHDeJIb
56 / 56 / 3
Регистрация: 31.10.2010
Сообщений: 103
06.11.2010, 01:18     Функция реверса строки #58
Цитата Сообщение от Zilon Посмотреть сообщение
О, да. Поскольку именно эти спички являются темой нашей беседы
Просто это спор из разряда "с какой стороны лучше яйцо разбивать, с тупой или с острой".
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
06.11.2010, 01:40     Функция реверса строки #59
KpeHDeJIb, С тупой
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.11.2010, 01:52     Функция реверса строки
Еще ссылки по теме:

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

Функция и реверс строки - C++
1. Составить программу, которая реверсирует каждое слово строки str. 2. Написать и протестировать функцию STRP(str1, str2), которая...

функция символьной строки - C++
Дана символьная строка.Написать программу, которая оставляет в исходной строке латинские буквы. Обработку строки оформить в виде функции,...

Функция копирования строки - C++
Есть строка,написать программу с ф-цией,которая формирует строку-копию.

Функция для считывания строки - C++
Требуется написать функция для считывания строки, используя динамическое выделения памяти? Как это по лучше сделать подскажите? Было бы...


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

Или воспользуйтесь поиском по форуму:
Zilon
5 / 5 / 0
Регистрация: 05.11.2010
Сообщений: 60
06.11.2010, 01:52  [ТС]     Функция реверса строки #60
Вобщем то начинали мы с интересных вариантов реализации.
А что оптимизирование - это уже частное мнение каждого.
Наконец подводя черту под тем что быстрее выкладываю результаты "критерия истины":

Эксперимент был проведен на таком коде:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <locale.h>
 
 
void revertArray(int arr[], int N);
void revertPointer(int arr[], int N);
void revertEqu(int arr[], int N);
 
 
int main (void)
{
    clock_t start, finish;
    int i;
    int N = 1024 * 1024 * 4;
 
    int* arr = (int*) calloc(1, N * sizeof(int));
    if(NULL == arr)
    {
        printf("Allocation memory error\n");
        system("pause");
        return 1;
    }
 
    system("pause");
 
    srand(5);
    for(i = 0; i < N; i++)
        arr[i] = rand();
    
    //array
    printf("array\n");
    start = clock();
 
    for(i = 0; i < 200; i++)
        revertArray(arr, N);
 
    finish = clock();
    printf("for array       time left - %d\n", (int) (finish-start));
 
    //pointers_XOR
    printf("pointers_XOR\n");
    start = clock();
    
    for(i = 0; i < 200; i++)
        revertPointer(arr, N);
 
    finish = clock();
    printf("for pointers_XOR   time left - %d\n", (int) (finish-start));
 
    //pointers_=
    printf("pointers_=\n");
    start = clock();
    
    for(i = 0; i < 200; i++)
        revertEqu(arr, N);
 
    finish = clock();
    printf("for pointers_=    time left - %d\n", (int) (finish-start));
 
    free(arr);
 
    system("pause");
    return 0;
}
 
void revertPointer(int arr[], int N)
{
        int* left = arr;
        int* right = &arr[N - 1];
 
        while(left < right)
        {
                *left ^= *right;
                *right ^= *left;
                *(left++) ^= *(right--);
        }
}
 
void revertEqu(int arr[], int N)
{
        int* left = arr;
        int* right = &arr[N - 1];
        int temp;
 
        while(left < right)
        {
            temp = *left;
            *left++ = *right;
            *right-- = temp;
        }
}
 
 
void revertArray(int arr[], int N)
{
    int tmp;
    int i = 0;
    int j = N - 1;
 
    while( j > i ){
        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
 
        i++;
        j--;
    }
}
Параметры и результаты в картинках ниже:
Миниатюры
Функция реверса строки   Функция реверса строки  
Yandex
Объявления
06.11.2010, 01:52     Функция реверса строки
Ответ Создать тему
Опции темы

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