Как мой вариант решения задачи топика "SRC: реализация atoi

Автор: Flamer
Дата: 28.08.02

" предлагаю такое (усовершенствования/замечания — сюда). Рассматривается как исходник :

//---------------------------------------------------------------------------
int new_atoi(const char* string)
{
 if(!string) return 0;
 int result = 0;

 //пропускаем пробельные символы
 while(*string == ' ' || *string == '\t' ) string++;

 // получаем знак числа
 bool bNegativeSign = (*string == '-');

 if(bNegativeSign || *string=='+') string++;

 while(*string) {
   if( (*string < '0' || *string> '9') ) break;
   result = result * 10 + (*string - '0');
   string++;
 }
return ( bNegativeSign ? -result : result );
}
//---------------------------------------------------------------------------

Здравствуйте Flamer, Вы писали:

F>Как мой вариант решения задачи топика "SRC: реализация atoi

Автор: Flamer
Дата: 28.08.02

" предлагаю такое (усовершенствования/замечания — сюда). Рассматривается как исходник :

Имхо много лишних телодвижений

Код

int new_atoi(const char *s)
{
    int sign=1, val=0;
    if (s) while ((*s == ' ' || *s == '\t') && *(++s)); else return 0;
    sign*=(*s == '-' && s++)?-1:((*s == '+' && s++),1);
    while (*s>='0' && *s<='9') { val*=10; val+=*s++ - '0'; }
    return val*sign;
}

Комментарии:
1. Используется то, что if (a && b) expr; эквивалентно if (a) if (b) expr; т.е. при a==false выражение b не вычисляется
2. Используется то, что if (a || b) expr; эквивалентно if (a) expr; else if (b) expr; т.е. при a==true выражение b не вычисляется
3. Все пишут while (*s) { ... } зачем? Ведь условие *s>='0' && *s<='9' уже обрабатывает такой случай (ибо 0 < '0')

Подробные комментарии к разбору знака:

    sign*=(*s == '-' && s++)?-1:((*s == '+' && s++),1);

1. Вычисляется *s == '-', если true, то вычисляется s++ (пропускаем '-'), указатель приводится к bool (поскольку он не NULL, то к true), значение && итого true, sign умножается на -1 и получается -1
2. Если не '-', то s++ не вычисляется и переходим ко второй части ?:
3. Аналогично вычисляем надо ли пропускать знак '+', операция запятая всегда даст нам 1, ибо знак положительный по умолчанию

Замеры времени:
Код писался 3 минуты
Пост писался 7 минут

Здравствуйте orangy, Вы писали:


[все покоцано]


Не тестил, но по визуальному прогону — 5 баллов! Да здравствует мощь языка С!

Здравствуйте orangy, Вы писали:

O>Здравствуйте Flamer, Вы писали:

F>>Как мой вариант решения задачи топика "SRC: реализация atoi

Автор: Flamer
Дата: 28.08.02

" предлагаю такое (усовершенствования/замечания — сюда). Рассматривается как исходник :

O>Имхо много лишних телодвижений

O>Код
O>

O>int new_atoi(const char *s)
O>{
O>    int sign=1, val=0;
O>    if (s) while ((*s == ' ' || *s == '\t') && *(++s)); else return 0;
O>    sign*=(*s == '-' && s++)?-1:((*s == '+' && s++),1);
O>    while (*s>='0' && *s<='9') { val*=10; val+=*s++ - '0'; }
O>    return val*sign;
O>}
O>

O>Комментарии:
O>1. Используется то, что if (a && b) expr; эквивалентно if (a) if (b) expr; т.е. при a==false выражение b не вычисляется
O>2. Используется то, что if (a || b) expr; эквивалентно if (a) expr; else if (b) expr; т.е. при a==true выражение b не вычисляется
O>3. Все пишут while (*s) { ... } зачем? Ведь условие *s>='0' && *s<='9' уже обрабатывает такой случай (ибо 0 < '0')

O>Подробные комментарии к разбору знака:
O>

O>    sign*=(*s == '-' && s++)?-1:((*s == '+' && s++),1);
O>

O>1. Вычисляется *s == '-', если true, то вычисляется s++ (пропускаем '-'), указатель приводится к bool (поскольку он не NULL, то к true), значение && итого true, sign умножается на -1 и получается -1
O>2. Если не '-', то s++ не вычисляется и переходим ко второй части ?:
O>3. Аналогично вычисляем надо ли пропускать знак '+', операция запятая всегда даст нам 1, ибо знак положительный по умолчанию

O>Замеры времени:
O>Код писался 3 минуты
O>Пост писался 7 минут

преклоняюсь...

Здравствуйте orangy, Вы писали:

O>3. Все пишут while (*s) { ... } зачем? Ведь условие *s>='0' && *s<='9' уже обрабатывает такой случай (ибо 0 < '0')

Для лучшего понимания читающими программу, т. к. логически это особый случай. Естественно, любой мало-мальски оптимизирующий компилятор лишнюю проверку отбросит.

Здравствуйте achp, Вы писали:

O>>3. Все пишут while (*s) { ... } зачем? Ведь условие *s>='0' && *s<='9' уже обрабатывает такой случай (ибо 0 < '0')

A>Для лучшего понимания читающими программу, т. к. логически это особый случай. Естественно, любой мало-мальски оптимизирующий компилятор лишнюю проверку отбросит.

Ты не совсем прав. Дело в том, что код годится и для итератора по char (легко изменить и для wchar_t), при этом не факт, что любой компилятор выбросит лишний вызов operator*()

Здравствуйте orangy, Вы писали:

O>Ты не совсем прав. Дело в том, что код годится и для итератора по char (легко изменить и для wchar_t), при этом не факт, что любой компилятор выбросит лишний вызов operator*()

Поправлю сам себя — с итераторами есть проблемка... Не додумал, s++ создаёт лишние временные объекты
для итераторов выглядит так:

template<typename iterator>
int new_atoi(iterator s)
{
    int sign=1, val=0;
    if (s) while ((*s == ' ' || *s == '\t') && *(++s)); else return 0;
    sign*=(*s == '-' && ++s)?-1:((*s == '+' && ++s),1);
    while (*s>='0' && *s<='9') { val*=10; val+=*s - '0'; ++s; }
    return val*sign;
}

Естественно, этот же шаблон годится и для указателей.

Здравствуйте Flamer, Вы писали:

F>вариант решения задачи

Для сравнения, код из CRT VC7, multithreaded code skipped

long __cdecl _tstol(const _TCHAR *nptr)
{
        int c;              /* current char */
        long total;         /* current total */
        int sign;           /* if '-', then negative, otherwise positive */
        while ( _istspace((int)(_TUCHAR)*nptr) )
            ++nptr;

        c = (int)(_TUCHAR)*nptr++;
        sign = c;           /* save sign indication */
        if (c == _T('-') || c == _T('+'))
            c = (int)(_TUCHAR)*nptr++;    /* skip sign */

        total = 0;

        while ( (c = _tchartodigit(c)) != -1 ) {
            total = 10 * total + c;     /* accumulate digit */
            c = (_TUCHAR)*nptr++;    /* get next char */
        }

        if (sign == '-')
            return -total;
        else
            return total;   /* return result, negated if necessary */
}

А во что компилится, сравнивали?

Slicer

Здравствуйте, Slicer [Wirkwood], Вы писали:

SW>А во что компилится, сравнивали?

да уж наверняка быстрее в пару раз получится. Мы недавно в проекте избавились от большинства CRT-строковых операций. Посмотрите, например, на реализацию isspace из CRT VC7.1 — это просто тихий ужас (времени не хватило, что ли, нормально сделать?). Когда я смотрел на результаты профайлинга — глазам своим не верил, пока не залез в исходники.

Извините за оффтоп, накипело

Здравствуйте, orangy, Вы писали:

Круто написал! Но у тебя два лишних умножения.

int new_atoi(const char *s)
{
    int sign=1, val=0;
    if (s) while ((*s == ' ' || *s == '\t') && *(++s)); else return 0;

//здесь
    sign*=(*s == '-' && s++)?-1:((*s == '+' && s++),1);

    while (*s>='0' && *s<='9') { val*=10; val+=*s++ - '0'; }

//и здесь
    return val*sign;
}

Лучше так

int new_atoi(const char *s)
{
    int negsign, val=0;
    if (s) while ((*s == ' ' || *s == '\t') && *(++s)); else return 0;

    negsign=(*s == '-' && s++)?1:((*s == '+' && s++),0);

    while (*s>='0' && *s<='9') { val*=10; val+=*s++ - '0'; }

    return negsign ? -val : val;
}

Здравствуйте, Andy77, Вы писали:

A>Здравствуйте, Slicer [Wirkwood], Вы писали:

SW>>А во что компилится, сравнивали?

A>да уж наверняка быстрее в пару раз получится. Мы недавно в проекте избавились от большинства CRT-строковых операций. Посмотрите, например, на реализацию isspace из CRT VC7.1 — это просто тихий ужас (времени не хватило, что ли, нормально сделать?). Когда я смотрел на результаты профайлинга — глазам своим не верил, пока не залез в исходники.

A>Извините за оффтоп, накипело :)

А приведенная реализация будет корректно работать со всякими извращенными кодировками, когда на символ может идти больше одного байта?
Такое встречается, если мне не изменяет память, в корейском языке. Так что, если Ваше приложение претендует на корейский рынок, то лучше не тратить время на написание собственных версий isspace. Проверка на пробел как (c == ' ') в любом случае некорректна.
Критика crt от Microsoft неуместна абсолютно, т. к. их crt обрабатывает все возможные варианты.

PS. Для unicode проверка (wc == L' ') также некорректна, т. к. существуют surrogates, когда используется по 4 байта на символ.

Здравствуйте, Flamer, Вы писали:

<skipped>

если кому интересно, то вот мой вариант:

dec2dwA proc String:DWORD

    push esi
    push edi

    xor eax, eax
    mov esi, [String]
    xor ecx, ecx
    xor edx, edx
    mov al, [esi]
    inc esi
    cmp al, 2D
    jne proceed
    mov al, byte ptr [esi]
    not edx
    inc esi
    jmp proceed

  @@: 
    sub al, 30h
    lea ecx, dword ptr [ecx+4*ecx]
    lea ecx, dword ptr [eax+2*ecx]
    mov al, byte ptr [esi]
    inc esi

  proceed:
    or al, al
    jne @B
    lea eax, dword ptr [edx+ecx]
    xor eax, edx

    pop edi
    pop esi

    ret

dec2dwA endp

если я неошибаюсь, это atol(...) в С/С++ (не силён я в crt, да и не люблю его за медлительность)

O>Замеры времени:
O>Код писался 3 минуты
O>Пост писался 7 минут

врешь (как пить дать)

F>Как мой вариант решения задачи топика "[url=http://www.rsdn.ru/forum/message.asp?mid=91717&amp;only

Автор: Flamer
Дата: 28.08.02

]SRC: реализация

вот бы супер быстрый и компактный variant вокруг базовых типов (char, int , long int , etc)
и к нему такие же шустрые функции конвертирования..

Здравствуйте, dad, Вы писали:

F>>Как мой вариант решения задачи топика "[url=http://www.rsdn.ru/forum/message.asp?mid=91717&amp;only

Автор: Flamer
Дата: 28.08.02

]SRC: реализация

dad>вот бы супер быстрый и компактный variant вокруг базовых типов (char, int , long int , etc)
dad>и к нему такие же шустрые функции конвертирования..

вот класс value из нашей tool библиотеки (Templated Object Oriented Library)

namespace tool
{

  class value 
  {
   public:
    enum types 
    {
      t_undefined,
      t_null,
      t_int,
      t_double,
      t_string,
      t_ustring,
      t_enum
    };

    struct enum_t 
    {
      dword enum_typeid;
      dword enum_value;
    };
  
    value()         :_type(t_undefined) { v.li = 0; }
    value(int i)    :_type(t_int) { v.i = i; }
    value(double d) :_type(t_double) { v.d = d; }
    value(const string& s) :_type(t_string) { v.s = s.get_data(); }
    value(const ustring& us) :_type(t_ustring) { v.us = us.get_data(); }

    value(const value& cv) { copy(cv); }

    void copy(const value& cv)
    { 
      clear();
      _type = cv._type; 
      v.li = cv.v.li;
      if(_type == t_string)
        v.s->add_ref();
      else if(_type == t_ustring)
        v.us->add_ref();
    }


    ~value() { clear(); }

    value& operator = (const value& cv) {  copy(cv); return *this; }

    value& operator = (int i) {  clear(); _type = t_int; v.i = i; return *this; }
    value& operator = (double d) {  clear(); _type = t_double; v.d = d; return *this;  }
    value& operator = (const string& s) {  clear(); _type = t_string; v.s = s.get_data(); return *this;  }
    value& operator = (const ustring& s) {  clear(); _type = t_ustring; v.us = s.get_data(); return *this; }

    word  type() const { return _type; }

    //to_string()
    bool  is_undefined() const { return _type == t_undefined; }
    bool  is_null() const { return _type == t_null; }
    bool  is_int() const { return _type == t_int; }
    bool  is_double() const { return _type == t_double; }
    bool  is_string() const { return _type == t_string; }
    bool  is_ustring() const { return _type == t_ustring; }
    
    operator int() const { assert(_type == t_int); return v.i; }
    operator dword() const { assert(_type == t_int); return v.i; }
    operator word() const { assert(_type == t_int); return v.i; }
    operator double() const { assert(_type == t_double); return v.d; }
    operator string() const { assert(_type == t_string); return string(v.s); }
    operator ustring() const { assert(_type == t_ustring); return ustring(v.us); }

    string to_string() const 
    { 
      switch(_type) 
      {
      //case t_null:
      //  return "{undefined}";
      case t_null:
        return string();
      case t_int:
        return string::format("%d",v.i);
      case t_double:
        return string::format("%f",v.d);
      case t_string:
        return string(v.s);
      case t_ustring:
        return string(ustring(v.us));
      case t_enum:
      default:
        assert(false); //not yet!
        return "value::to_string() error";
      }
    }

    int to_int() const 
    { 
      switch(_type) 
      {
        case t_int:
          return v.i;
        case t_double:
          return (int)v.d;
        default:
          return 0;
      }
    }

    ustring to_ustring() const 
    { 
      switch(_type) 
      {
      case t_null:
        return ustring();
      case t_int:
        return ustring::format(L"%d",v.i);
      case t_double:
        return ustring::format(L"%f",v.d);
      case t_string:
        return ustring(string(v.s));
      case t_ustring:
        return ustring(v.us);
      case t_enum:
      default:
        assert(false); //not yet!
        return "value::to_ustring() error";
      }
    }

    void clear() 
    { 
      if(_type == t_string)
        string::release_data(v.s);
      else if(_type == t_ustring)
        ustring::release_data(v.us);
      _type = t_null;
      v.li = 0;
    }
    
    static value null() { value t; t._type = t_null; return t; }
    static const value undefined;

  private:
    word _type;
    union v
    {
      int             i;
      double          d;
      string::data*   s;
      ustring::data*  us;
      enum_t          e;
      int64           li;
     }v;
  };

} //namespace

для хранения строковых значений используется знание того что
tool::string это обертка вокруг ссылки на буфер character c reference counter (string::data) ...

Поэтому операция типа value v = some_string; выполняется тривиальным иннкрементированием счетчика суть быстро.