Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > оптимизировать код

Автор: ИванМ 15.4.2010, 23:52

Есть такой код. На входе число в формате xxxEyyy, на выходе xxx000..... Как его можно оптимизировать?

Код


string replace_e(string str)
{
    for(size_t i=0;i<str.length();i++)
    {
        if(str[i]=='e' || str[i]=='E')
        {
            stringstream s(str.substr(i+1));
            int n;
            s>>n;
            str.reserve(i+n);
            str.resize(i);
            s.clear();
            s.str("");
            s.fill('0');
            s.width(n);
            s<<"0";
            str.append(s.str());
            break;
        }
    }
    return str;
}

Автор: djamshud 16.4.2010, 00:06

Число или все же строка? Или в коде строка только потому, что не можете с числом?

Автор: ИванМ 16.4.2010, 00:07

djamshud, строка. Число нельзя потому что может быть любая размерность.

Автор: djamshud 16.4.2010, 00:20

Код


char str[]={"1234E1265"};
char *pos=strpbrk(str,"eE");
if(pos!=0)
memset(pos,'0',strlen(str)-(pos-str));
printf("%s\n",str);

Вроде бы std::string позволяет работать напрямую с char*-данными. Тогда еще и strlen заменится на оптимальный str.length().

Автор: jonie 16.4.2010, 00:21

не, ну если просто заменять то зачем парсить в int n что-то? банальный алгоритм какой-то такой:

Код


int pos=s.find_first_of('E');
string result = s.substr(0, pos);
result.append(s.size() - pos, '0'); //используй string& append ( size_t n, char c );  Appends a string formed by the repetition n times of character c.

UPD:
кстати:

Код


string& replace ( size_t pos1, size_t n1, size_t n2, char c );
string& replace ( iterator i1, iterator i2, size_t n2, char c );
    The section is replaced by a repetition of character c, n2 times.

заюзать стоит

Автор: ИванМ 16.4.2010, 00:22

djamshud, а нельзя C++ средствами? Не люблю я Си.

Автор: jonie 16.4.2010, 00:23

djamshud, не факт что можно делать memcpy в возращенный указатель, т.е. надо почитать, не возращает ли он константный указатель, а-то малоли как там внутри stl сделано...(возможно в некоторых реализациях вам будут давать например копию буфера, надо читать)

Автор: djamshud 16.4.2010, 00:26

ИванМ, а я не умею stl. Но тот пример можно пропатчить на предмет std::string и он будет наверное крайне оптимальным.

Добавлено через 1 минуту и 19 секунд
jonie, если в std::string есть способ получить возможность работы напряму с внутренним буфером, то проблем не будет, т.к. изменения его размеров не происходит.

Автор: jonie 16.4.2010, 00:34

djamshud, прочти еще разок что я написал, в частности про теневую копию, а еще бывает copy-on-write и вы можете своей записью по указателю заколбасить заодно и ссылаемые строки... в общем ябы почитал что можно, а что низя ...

Автор: djamshud 16.4.2010, 00:42

jonie, я внимательно читал, не сыпьте терминами. А сейчас прочитал описание этой строки, там предусмотрен доступ только для чтения (char const*). С ним работать опасно.

Автор: mes 16.4.2010, 00:43

решение в лоб, чтоб долго не думать :

Код


std::string replace_e (const std::string& str)
{  
    std::string s;
    s.reserve (str.size()-1);

    std::string::const_iterator it =  str.begin ();
    std::string::const_iterator end = str.end ();

    for (; it != end && (*it !='e' && *it != 'E'); ++it) 
      s.push_back (*it);

    for (++it; it != end; ++it ) 
      s.push_back('0');
   
    return s;
}

Автор: ИванМ 16.4.2010, 00:46

jonie,

Цитата(jonie @ 16.4.2010, 00:21

)

не, ну если просто заменять то зачем парсить в int n что-то? банальный алгоритм какой-то такой:

Не рабочий ваш код.
И если не парсить в int, то как мы узнаем количество символов? По любому надо переводить из string в int (а лучше конечно в size_t для моего случая).
string::replace только заменяет уже имеющиеся данные, которых у меня нет.
Вот с append(size_t, char) можно сократить код.
find_first_of тоже нельзя использовать, потому что может быть как 'e', так и 'E'.

djamshud, на сколько я знаю, нельзя работать в string с внутренним буфером.

mes,

Цитата(mes @ 16.4.2010, 00:43

)

for (++it; it != end; ++it )
s.push_back('0');

Это очень медленно будет работать.
И, кстати, ваш код тоже не рабочий.

Пока так сделал:

Код


string replace_e(string str)
{
    for(size_t i=0;i<str.length();i++)
    {
        if(str[i]=='e' || str[i]=='E')
        {
            stringstream s(str.substr(i+1));
            int n;
            s>>n;
            str.reserve(i+n);
            str.resize(i);
            str.append(n, '0');
            break;
        }
    }
    return str;
}

Может я как то не так задачу описал.
Например, если строка=1e4, то должно быть на выходе: 10000.

Автор: jonie 16.4.2010, 00:48

djamshud, эт не термины - эт реальная жизнь.
Для тех кто не вкурсе что такое copy-on-write это методика, когда например вы делаете копию строки, но реально буфер остается тот же самый, а вы по сути получаете пустышку, с буфером указывающим на буфер другой строки + для каждой ссылаемой сущьности проставляется признак "есть ссылка". Когда вы начинаете что-то менять в строке, тог проверяется этот признак, и, если он установлен, то производится создание нового буфера, копирование в него старого и изменение уже его (нового). Типа "копирование при записи". Эффективно экономит память, добавляет сложности при программировании, сложности отладки при перезаписи чужих данных, зачастую скорость падает...

Автор: mes 16.4.2010, 00:50

Цитата(ИванМ @ 15.4.2010, 23:46

)

Это очень медленно будет работать.

подправляю :

Код


std::string replace_e (const std::string& str)
{  
    std::string s;
    s.reserve (str.size()-1);

    std::string::const_iterator it =  str.begin ();
    std::string::const_iterator end = str.end ();

    for (; it != end && (*it !='e' && *it != 'E'); ++it) 
      s.push_back (*it);

    s.resize (str.size()-1,'0');
 
    return s;
}

Автор: jonie 16.4.2010, 00:53

ИванМ, у меня не код, а псевдокод.

Цитата

string::replace только заменяет уже имеющиеся данные, которых у меня нет.

в исходной строке есть.

Цитата

find_first_of тоже нельзя использовать, потому что может быть как 'e', так и 'E'.

в исходном задании таких условий не было. кроме того, find_first_of работает так:

Цитата

Searches the string for any of the characters that are part of either str, s or c, and returns the position of the first occurrence in the string.

туда можно прередать "eE".

Цитата

И если не парсить в int, то как мы узнаем количество символов? По любому надо переводить из string в int (а лучше конечно в size_t для моего случая).

эт я слабо понял. из задания нужно заменить все начиная (и включая) символ E до конца. Может и не так..

Автор: mes 16.4.2010, 00:56

Цитата(ИванМ @ 15.4.2010, 23:46

)

Может я как то не так задачу описал.
Например, если строка=1e4, то должно быть на выходе: 10000.

ну так

тут совсем другое :

Цитата(ИванМ @ 15.4.2010, 22:52

)

xxxEyyy, на выходе xxx000

Автор: djamshud 16.4.2010, 00:56

jonie, я сейчас матом буду ругаться. Повторяю, я думал в std::string есть char*-доступ. Посмотрел API, узнал, что только char const*, признал, что был не прав. Вы, судя по всему зная этот API, вместо того, чтобы показать на него, начали и продолжаете сыпать терминами. Уймитесь наконец.

И да, в std::string есть C-o-W, но само по себе это не означает, что не может быть предоставлен прямой доступ к данным. Важно, что нет интерфейса получения этого доступа.

Автор: ИванМ 16.4.2010, 00:58

Пример работы программы:
replace_e("1e4") -> "10000"
replace_e("12e2") -> "1200"
Вы видимо меня не поняли.

Цитата(jonie @ 16.4.2010, 00:53

)

в исходном задании таких условий не было. кроме того, find_first_of работает так:
Цитата
Searches the string for any of the characters that are part of either str, s or c, and returns the position of the first occurrence in the string.
туда можно прередать "eE".

тогда так перепишу:

Код


string replace_e(string str)
{
    size_t i=str.find_first_of("eE");
    if(i==string::npos)
        return str;

    stringstream s(str.substr(i+1));
    int n;
    s>>n;
    str.reserve(i+n);
    str.resize(i);
    str.append(n, '0');

    return str;
}

Добавлено через 57 секунд
mes, прастите. Плохо сформулировал задачу.

Автор: mes 16.4.2010, 01:02

Цитата(ИванМ @ 15.4.2010, 23:58

)

string replace_e(string str)

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

Автор: jonie 16.4.2010, 01:04

если вам нужна скорость, то вот это

Код


    stringstream s(str.substr(i+1));
    int n;
    s>>n;

вероятно можно заменить на

Код


int n=atoi(str.c_str()+i);

....
в общем подумать можно и еще, но поздно.

ЗЫ: подумайте насчет передачи строки в функцию по ссылке, если у вас не c++0x, то копирования избежите...
UPD: mes опередил)

UPD2:

Код


    str.reserve(i+n);
    str.resize(i);

нет смысла делать reserve.

UPD3:
делайте void resize ( size_t n, char c ); вот и пропал append ...

Автор: ИванМ 16.4.2010, 01:19

Цитата(jonie @ 16.4.2010, 01:04

)

нет смысла делать reserve.

Почему? Разве resize изменяет физический объем буфера?

На счет константной ссылки согласен.

Код


string replace_e(const string& str)
{
    size_t i=str.find_first_of("eE");
    if(i==string::npos)
        return str;

    string str1=str.substr(i+1);
    stringstream s(str1);
    int n;
    s>>n;
    
    str1.resize(i+n, '0');

    return str1;
}

Цитата(jonie @ 16.4.2010, 01:04

)

вероятно можно заменить на
int n=atoi(str.c_str()+i);

Скорость хорошо, но пользоваться сишной библиотекой не хочу категорически.

Автор: W4FhLF 16.4.2010, 05:22

Я правильно понял, что строку в которой представлено число в формате exponential надо перевести в строку в которой представлено число в формате fixed?

Автор: jonie 16.4.2010, 07:35

Цитата

Скорость хорошо, но пользоваться сишной библиотекой не хочу категорически.

ИванМ, boost::lexical_cast<int> ....

W4FhLF, да, как потом выяснилось именно это и хотел автор

Автор: ИванМ 16.4.2010, 15:47

Цитата(W4FhLF @ 16.4.2010, 05:22

)

Почти. Может быть только такой вид: xxxEyyy.
xxxE+yyy и xxxE-yyy не допускается.

Цитата(jonie @ 16.4.2010, 07:35

)

boost::lexical_cast<int> ....

Нельзя, числа могут быть неограниченной размерности

Автор: W4FhLF 16.4.2010, 16:35

Цитата(ИванМ @ 16.4.2010, 15:47

)

Нельзя, числа могут быть неограниченной размерности

n тут представляет количество нулей грубо говоря. Ты же сам юзаешь такую же конструкцию:

Код


stringstream s(str.substr(i+1));
    int n;
    s>>n;

Если будет переполнение int'a (при количестве нулей больше 0x7FFFFFFF), то оно будет и в твоём случае (я что-то сомневаюсь, что ты будешь хранит строки по 2.5 гига хранить на число.). Но boost::lexical_cast более лаконичный и быстрый способ.

Автор: ИванМ 16.4.2010, 16:38

W4FhLF, не так понял, прошу прощения. Я думал, мне предлагают исходное число перевести. А так да, воспользуюсь lexical_cast, если он быстрее.

Код


string replace_e(const string& str)
{
    size_t i=str.find_first_of("eE");
    if(i==string::npos)
        return str;

    string str1=str.substr(i+1);
    str1.resize(i+boost::lexical_cast<int>(str1), '0');
    return str1;
}

Вот уже код сократился в несколько раз)

Автор: ИванМ 16.4.2010, 20:06

Если больше нечего предложить, тему закрываю. Всем спасибо.