Сонный металюга
46 / 46 / 13
Регистрация: 10.05.2009
Сообщений: 295
1

Оптимизация простой функции

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

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

Функцию написал- нет проблем.. протестил на строках длинной порядка 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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.02.2012, 10:38
Ответы с готовыми решениями:

Оптимизация простой программы
Суть задачи такова: программа должна вычислить сумму цифр которые делятся на a или b и цифры должны...

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

Типы оптимизация: черная оптимизация, серая оптимизация и белая оптимизация
Много много лет назад, на заре становления профессии "оптимизатора" в какой то умной книжке был...

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

9
Эксперт С++
2924 / 1274 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
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
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12454 / 7479 / 1752
Регистрация: 25.07.2009
Сообщений: 13,750
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
Сонный металюга
46 / 46 / 13
Регистрация: 10.05.2009
Сообщений: 295
13.02.2012, 15:10  [ТС] 6
Спасибо! у easybudda более красивое решение=) Правда тут встает вопрос- что быстрее срабатывает - работа с индексами или арифметика с указателями при перемещении по стоке. Т.к. strlen вызывается и в вашем и в моем варианте - ее не учитываем с точки зрения оптимизации.
Обращений к памяти получается примерно одинаково вроде.
0
Higher
1953 / 1219 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
13.02.2012, 15:23 7
Цитата Сообщение от Акелла Посмотреть сообщение
Спасибо! у easybudda более красивое решение=)
Во втором посте самое быстрое из всех возможных.
Ну или для std::string можно идти с конца до первого непробельного символа.

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

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

А это один проход по строке, просто для того, чтобы узнать ее длину. А можно за один проход сделать все необходимое, как предложил CheshireCat.
Спасибо большое! оценил=)
0
Заблокирован
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
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12454 / 7479 / 1752
Регистрация: 25.07.2009
Сообщений: 13,750
13.02.2012, 20:00 10

Не по теме:

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


В один проход, но так сравнений больше, да и длиннее как-то...
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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.02.2012, 20:00
Помогаю со студенческими работами здесь

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

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

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

Оптимизация функции
$(document).ready(function() { $('#info1').on('click', () =&gt; { ...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru