Форум программистов, компьютерный форум, киберфорум
Наши страницы

C для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 5.00
Акелла
Сонный металюга
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
#1

Оптимизация простой функции - C (СИ)

13.02.2012, 10:38. Просмотров 1573. Ответов 9
Метки нет (Все метки)

Задача- Напишите функцию, которая обрезает пробелы в конце переданной ей строки. Функция должна быть написана в расчёте на работу с очень длинными строками с очень большим количеством пробелов, оптимизирована по количеству обращений к памяти.

Функцию написал- нет проблем.. протестил на строках длинной порядка 1000 символов.
Думаю тут ограничение только на размер типа unsigned int.

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

Вот, решил проконсультироваться. Заранее спс!
C
1
2
3
4
5
6
7
8
9
10
11
12
void TrimRight( char *str )
{
    unsigned int nStrLen =  strlen(str);
 
    while(str[nStrLen-1] == ' ') 
        nStrLen--;
 
    if(str[nStrLen-1] != ' ') 
        str[nStrLen] = 0;
    else 
        str[nStrLen-1] = 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.02.2012, 10:38
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Оптимизация простой функции (C (СИ)):

Оптимизация функции нужна помощь - C (СИ)
#include <stdio.h> #include <stdlib.h> int TLConst; int find( int budget, int *table, int tableLen ){ int i, temp, k, max, l1,...

Оптимизация кода - C (СИ)
Есть задача: Есть абсолютно верное решение: #include <stdio.h> #include <stdlib.h> inline int simple(int N) { int...

Оптимизация кода - C (СИ)
Нужно оптимизировать код, т.к. при сдаче работы есть ограничение по времени - 1с, а к сожалению работа занимает дольше 1 секунды.Подозреваю...

Оптимизация простой программы - C++
Суть задачи такова: программа должна вычислить сумму цифр которые делятся на a или b и цифры должны быть меньше n. Максимальное число n =...

Простой project-manager: оптимизация разграничения прав - Ruby on Rails
Начал изучать RoR около месяца назад, написав простенький блог решил перейти к чему-то более сложному. Поступило предложение создать...

.NET 4.x Оптимизация кода, функции и методы как параметры функции - C#
Грубо говоря - есть множество циклов которые привязаны к проверочным функциям, поскольку сами по себе тела циклов в принципе идентичны,...

9
CheshireCat
Эксперт С++
2907 / 1256 / 81
Регистрация: 27.05.2008
Сообщений: 3,449
13.02.2012, 11:28 #2
Функция strlen() сканирует строку до конца, просматривая все символы, пока не встретится '\0' - это один проход по строке. Затем ты в своем цикле while просматриваешь символы с конца, пока очередной символ равен пробелу - это второй проход.

Вот как можно сделать все в один проход (одно обращение к памяти):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void TrimRight(char* str)
{
        unsigned int nStrLen = 0;
        unsigned int lastSpace = -1;
        char         ch;
 
        while(ch = str[nStrLen])
        {
            if (ch == ' ')
            {
                if (lastSpace == -1)
                    lastSpace = nStrLen;
            }
            else
                lastSpace = -1;
            ++nStrLen;
        }
        // обрезаем строку:
        if (lastSpace > 0)
            str[lastSpace] = '\0';
}
Считать ли это оптимизацией???

(код я не проверял! написано навскидку, но идею, думаю, ты понял....)
2
-=ЮрА=-
Заблокирован
Автор FAQ
13.02.2012, 13:29 #3
Цитата Сообщение от Акелла Посмотреть сообщение
Вопрос - ее как то еще можно оптимизировать на ваш взгляд?
ИМХО - все обращения к памяти это вычисление длинны строки стандартной функцией и просмотр элементов строки с конца.
- можно сделать вот так и не ломать себе голову
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
#include <stdio.h>
#include <conio.h>
#include <string.h>
 
char * strtrim(char * text)
{
    long i   = 0;
    char * s = strrchr(text,' ');//ГЌГ*øëè ïîñëåäГ*ГЁГ© ïðîáåë îò ГЄГ®Г*Г¶Г*
    while((s - i)[0] == ' ')
        i = i + 1;
    text[strlen(text) - i] = '\0';//ÎáðåçГ*ëè ïðîáåëû
    return text;
}
 
int main()
{
    char text[2048] = {0};//Гџ Г*ГҐ ñèëüГ*Г® Г§Г*ìîðГ*Г·ГЁГўГ*ëñÿ Г*Г*Г¤ îðãГ*Г*ГЁГ§Г*öèåé ââîäГ*
    printf("Enter text : ");
    scanf("%[^\n]",text);
    printf("Your input [%s]\n",text);
    printf("Trim space [%s]\n",strtrim(text));
    printf("Press any key to continue\n");
    getch();
    return 0;
}
0
Миниатюры
Оптимизация простой функции  
-=ЮрА=-
Заблокирован
Автор FAQ
13.02.2012, 13:32 #4
PS:Внутри
Цитата Сообщение от -=ЮрА=- Посмотреть сообщение
char * strtrim(char * text)
не делал проверок типа s != NULL, вызов функции лежит на плечах программиста, который перед использованием функции должен проверить а есть ли в строке пробелы + не находится ли последний справа пробел перед каким то символом или словом, делается всё легко, поэтому решил на этом не заморачиваться...
1
easybudda
Модератор
Эксперт CЭксперт С++
10020 / 5943 / 1004
Регистрация: 25.07.2009
Сообщений: 11,230
13.02.2012, 13:49 #5
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <string.h>
#include <ctype.h>
 
char * rtrim(char * s){
    char * t = s + strlen(s) - 1;
    
    while ( t >= s && isspace(*t) )
        *t-- = 0;
    
    return s;
}
 
int main(void){
    char buf[BUFSIZ];
    
    while ( printf("String: ") && fgets(buf, BUFSIZ, stdin) && *buf != '\n' )
        printf("Result: \"%s\"\n", rtrim(buf));
        
    return 0;
}
2
Акелла
Сонный металюга
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
13.02.2012, 15:10  [ТС] #6
Спасибо! у easybudda более красивое решение=) Правда тут встает вопрос- что быстрее срабатывает - работа с индексами или арифметика с указателями при перемещении по стоке. Т.к. strlen вызывается и в вашем и в моем варианте - ее не учитываем с точки зрения оптимизации.
Обращений к памяти получается примерно одинаково вроде.
0
diagon
Higher
1936 / 1202 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.02.2012, 15:23 #7
Цитата Сообщение от Акелла Посмотреть сообщение
Спасибо! у easybudda более красивое решение=)
Во втором посте самое быстрое из всех возможных.
Ну или для std::string можно идти с конца до первого непробельного символа.

Цитата Сообщение от Акелла Посмотреть сообщение
Правда тут встает вопрос- что быстрее срабатывает - работа с индексами или арифметика с указателями при перемещении по стоке.
По времени - одинаково, если верить Страуструпу.

Цитата Сообщение от Акелла Посмотреть сообщение
Т.к. strlen вызывается и в вашем и в моем варианте - ее не учитываем с точки зрения оптимизации.
А это один проход по строке, просто для того, чтобы узнать ее длину. А можно за один проход сделать все необходимое, как предложил CheshireCat.
1
Акелла
Сонный металюга
45 / 45 / 6
Регистрация: 10.05.2009
Сообщений: 295
13.02.2012, 15:53  [ТС] #8
Цитата Сообщение от diagon Посмотреть сообщение

А это один проход по строке, просто для того, чтобы узнать ее длину. А можно за один проход сделать все необходимое, как предложил CheshireCat.
Спасибо большое! оценил=)
0
Bers
Заблокирован
13.02.2012, 20:00 #9
Оптимизация алгоритма поиска за счет сокращения количества итераций циклов.

Рецепт: анализировать большую длинную строку не по 1 байту, а сразу кусками. Настолько длинными, насколько позволяет местная архитектура процессора.

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
//функция вернёт позицию символа отличного от символа-цели. 
//Поиск осуществляется с конца строки.
//Если вся строка состоит из символов-цели - вернёт -1
template<typename T>
int FindFromEnd(const char* s, const char target)
{
    int len=strlen(s), i=len; 
    const size_t sm=sizeof(T);                  //смещение на каждой итерации цикла
    #define ET std::string(sm, target).c_str()  //строка эталон 
    
    const T etalon = *((T*)ET); //закэшируем числовое значение эталона
    T* ptr=(T*)(s+len);         //получим адрес куска строки  
 
    #define Requirement i>=sm && etalon==(*ptr) //условие выполнения цикла
    #define Action i-=sm,--ptr                  //подготовка к очередной итерации
    while( (Action, Requirement) );  //отмотаем кусками строку назад с шагом sm
    
    if(!i) return -1; 
    i +=sm;
    
    #define Requirement1 s[i]==target  //условие выполнения цикла
    while( (--i,Requirement1) );    //отмотаем оставшийся хвостик
    return i;
 
    //приберемся за собой
    
    #undef ET
    #undef Action        
    #undef Requirement
    #undef Requirement1
}
 
template<> int FindFromEnd<char>(const char* s, const char target)
{
    const char * ptr = s + strlen(s);
 
    #define Requirement ptr>=s && *ptr==target  //условие выполнения цикла
    while (  (--ptr ,Requirement)  ); //отматываем назад по 1 байту
    #undef  Requirement 
 
    return ptr-s;
}
 
 
int main()
{
    STD;  char* str = "     s      s    "; //для тестов
 
    int i;
    i= FindFromEnd<char>(str, ' ');
    i==-1 ? cout<< "все символы строки - пробелы" : 
        cout<< "позиция первого не_пробельного символа с конца: "<<i;
    cout<<endl;
 
    i= FindFromEnd<int>(str, ' ');
    i==-1 ? cout<< "все символы строки - пробелы" : 
        cout<< "позиция первого не_пробельного символа с конца: "<<i;
    cout<<endl;
 
 
    i= FindFromEnd<LONGLONG>(str, ' ');
    i==-1 ? cout<< "все символы строки - пробелы" : 
        cout<< "позиция первого не_пробельного символа с конца: "<<i;
    cout<<endl;
}
/ps Возможно содержит ошибки, ибо с коленки и не проверял. Но суть идеи понятна.
К тому же в самой функции отсутствует проверка ошибок.

Добавлено через 45 минут
Если объединить идею из #9 поста с идеей из #2 поста, можно будит избавиться от strlen, и ещё ускорить процесс.
0
easybudda
Модератор
Эксперт CЭксперт С++
10020 / 5943 / 1004
Регистрация: 25.07.2009
Сообщений: 11,230
13.02.2012, 20:00 #10

Не по теме:

Цитата Сообщение от Bers Посмотреть сообщение
Оптимизация алгоритма
Первое место однозначно!


В один проход, но так сравнений больше, да и длиннее как-то...
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
#include <stdio.h>
#include <string.h>
#include <ctype.h>
 
/*
char * rtrim(char * s){
    char * t = s + strlen(s) - 1;
    
    while ( t >= s && isspace(*t) )
        *t-- = 0;
    
    return s;
}
*/
 
char * rtrim(char * s){
    char * pStr = s, * pSpc = NULL;
    
    for ( ; *pStr; ++pStr ){
        if ( isspace(*pStr) ){
            if ( !pSpc )
                pSpc = pStr;
        }
        else
            pSpc = NULL;
    }
    
    if ( pSpc )
        *pSpc = '\0';
    
    return s;
}
 
int main(void){
    char buf[BUFSIZ];
    
    while ( printf("String: ") && fgets(buf, BUFSIZ, stdin) && *buf != '\n' )
        printf("Result: \"%s\"\n", rtrim(buf));
        
    return 0;
}
0
13.02.2012, 20:00
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.02.2012, 20:00
Привет! Вот еще темы с ответами:

Оптимизация функции - Assembler
Просто ради интереса собрал функцию на ассемблере которая создаёт список всех файлов, в данном случае на диске С .Только пока получилось...

Оптимизация функции - C++
Здравствуйте, каким образом(кроме switch) можно оптимизировать эту функцию(Нужен самый оптимизированный вариант): void blabla() { ...

Оптимизация функции - Python
Всем привет. Нужна ваша помощь, чтобы исправить ошибку. Буду рад любой помощи. https://glot.io/snippets/er2muuidny

Оптимизация функции - Matlab
Всем привет! Начал вспоминать(осваивать) Matlab, последний раз имел дело лет 10 назад в универе. По долгу службы необходимо решить...


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

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

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