С++ наиболее эффективный способ преобразования строки в int (быстрее, чем atoi)

Ответ 1

Я экспериментировал с решениями, используя таблицы поиска, но обнаружил, что они чреваты проблемами, и на самом деле не очень быстро. Самое быстрое решение оказалось наименее изобретательным:

int fast_atoi( const char * str )
{
    int val = 0;
    while( *str ) {
        val = val*10 + (*str++ - '0');
    }
    return val;
}

Запуск теста с миллионом произвольно сгенерированных строк:

fast_atoi : 0.0097 seconds
atoi      : 0.0414 seconds

Чтобы быть справедливым, я также тестировал эту функцию, заставляя компилятор не встраивать его. Результаты были хорошими:

fast_atoi : 0.0104 seconds
atoi      : 0.0426 seconds

Если ваши данные соответствуют требованиям функции fast_atoi, это довольно разумная производительность. Требования:

• Строка ввода содержит только числовые символы или пуста
• Строка ввода представляет собой число от 0 до INT_MAX

Ответ 2

atoi может быть значительно улучшена при определенных предположениях. Это было продемонстрировано мощно в презентации Андрея Александреску на конференции С++ и Beyond 2012. Привет, сменная замена циклов и ALU parallelism для достижения заказов в совершенстве. У меня нет его материалов, но эта ссылка использует подобный метод: http://tombarta.wordpress.com/2008/04/23/specializing-atoi/

Ответ 3

Эта страница сравнивает скорость преобразования между различными функциями string- > int с использованием разных компиляторов. Наивная функция, которая не предлагает проверки ошибок, предлагает скорости примерно в два раза быстрее, чем atoi(), в соответствии с представленными результатами.

// Taken from http://tinodidriksen.com/uploads/code/cpp/speed-string-to-int.cpp
int naive(const char *p) {
    int x = 0;
    bool neg = false;
    if (*p == '-') {
        neg = true;
        ++p;
    }
    while (*p >= '0' && *p <= '9') {
        x = (x*10) + (*p - '0');
        ++p;
    }
    if (neg) {
        x = -x;
    }
    return x;
}

он всегда положителен

Удалите отрицательные проверки в приведенном выше коде для микро оптимизации.

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

while (*p >= '0' && *p <= '9') {

к

while (*p != '\0' ) {

Что оставляет вас с

unsigned int naive(const char *p) {
    unsigned int x = 0;
    while (*p != '\0') {
        x = (x*10) + (*p - '0');
        ++p;
    }
    return x;
}

Ответ 4

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

Циклы преобразования часто записываются для выполнения трех разных действий с каждым символом:

• выдается, если это символ конца строки
• выйдите, если это не цифра
• преобразовать его из своей кодовой точки в фактическое значение цифры

Первое наблюдение: нет необходимости проверять символ конца строки отдельно, так как это не цифра. Следовательно, проверка на "достоверность" неявно охватывает условие EOS.

Второе наблюдение: двойные условия для тестирования диапазона, как в (c >= '0' && c <= '9'), могут быть преобразованы в одно условие теста с использованием неподписанного типа и привязки диапазона к нулю; таким образом, не может быть никаких нежелательных значений ниже начала диапазона, все нежелательные значения отображаются в диапазоне выше верхнего предела: (uint8_t(c - '0') <= 9)

Так получилось, что c - '0' нужно все равно вычислить...

Следовательно, внутренний цикл преобразования может быть уменьшен до

uint64_t n = digit_value(*p);
unsigned d;

while ((d = digit_value(*++p)) <= 9)
{
   n = n * 10 + d;
}

Здесь вызывается код с предварительным условием, что p указывается на цифру, поэтому первая цифра извлекается без дополнительной суматохи (что также позволяет избежать избыточного MUL).

Это предварительное условие менее диковинное, чем может показаться на первый взгляд, поскольку p, указывающее на цифру, является причиной того, почему этот код вызывается парсером в первую очередь. В моем коде все это выглядит так (утверждения и другие шумы производственного качества устранены):

unsigned digit_value (char c)
{
   return unsigned(c - '0');
}

bool is_digit (char c)
{
   return digit_value(c) <= 9;
}

uint64_t extract_uint64 (char const **read_ptr)
{
   char const *p = *read_ptr;
   uint64_t n = digit_value(*p);
   unsigned d;

   while ((d = digit_value(*++p)) <= 9)
   {
      n = n * 10 + d;
   }

   *read_ptr = p;

   return n;
}

Первый вызов digit_value() часто исключается компилятором, если код становится inlined, а вызывающий код уже вычислил это значение, вызвав is_digit().

n * 10 происходит быстрее, чем ручное изменение (например, n = (n << 3) + (n << 1) + d), по крайней мере на моей машине с gcc 4.8.1 и VС++ 2013. Я предполагаю, что оба компилятора используют LEA с масштабированием индекса для сложения до трех значений за один раз и масштабирования одного из них на 2, 4 или 8.

В любом случае, точно так, как это должно быть: мы пишем чистый чистый код в отдельных функциях и выражаем желаемую логику (n * 10, x% CHAR_BIT, что угодно), а компилятор преобразует ее в перенос, маскирование, LEAing и т.д. on, вставляет все в большую петлю плохого парсера и заботится обо всех необходимых беспорядках под капотом, чтобы быстро все исправить. Нам даже не нужно больше придерживаться inline. Если что-то тогда, мы должны сделать обратное, используя __declspec(noinline) разумно, когда компиляторы перегружаются.

Я использую вышеуказанный код в программе, которая читает миллиарды чисел из текстовых файлов и труб; он преобразует 115 миллионов uint в секунду, если длина составляет 9..10 цифр и 60 миллионов/с для длины 19..20 цифр (gcc 4.8.1). Это более чем в десять раз быстрее, чем strtoull() (и просто для моих целей достаточно, но я отвлекаюсь...). Это время для преобразования текстовых блоков, содержащих 10 миллионов номеров каждый (100.200 МБ), что означает, что тайминги памяти делают эти цифры немного хуже, чем они были бы в синтетическом тесте, который запускается из кеша.

Ответ 5

Почему бы не использовать stringstream? Я не уверен в его особых накладных расходах, но вы можете определить:

int myInt; 
string myString = "1561";
stringstream ss;
ss(myString);
ss >> myInt;

Конечно, вам нужно

#include <stringstream> 

Ответ 6

Реализация Paddy fast_atoi быстрее atoi - без тени сомнения - однако она работает только для целых без знака... p >

Ниже я поставил оценочную версию Paddy fast_atoi, которая также допускает только целые числа без знака, но ускоряет преобразование даже больше, заменив дорогостоящую операцию * на +

unsigned int fast_atou(const char *str)
{
    unsigned int val = 0;
    while(*str) {
        val = (val << 1) + (val << 3) + *(str++) - 48;
    }
    return val;
}

Здесь я помещаю полную версию fast_atoi(), которую я иногда использую, которая также преобразует сложенные целые числа:

int fast_atoi(const char *buff)
{
    int c = 0, sign = 0, x = 0;
    const char *p = buff;

    for(c = *(p++); (c < 48 || c > 57); c = *(p++)) {if (c == 45) {sign = 1; c = *(p++); break;}}; // eat whitespaces and check sign
    for(; c > 47 && c < 58; c = *(p++)) x = (x << 1) + (x << 3) + c - 48;

    return sign ? -x : x;
} 

Ответ 7

Здесь вся функция atoi в gcc:

long atoi(const char *str)
{
    long num = 0;
    int neg = 0;
    while (isspace(*str)) str++;
    if (*str == '-')
    {
        neg=1;
        str++;
    }
    while (isdigit(*str))
    {
        num = 10*num + (*str - '0');
        str++;
    }
    if (neg)
        num = -num;
    return num;
 }

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

isdigit почти наверняка встроен, так что вы не стоите в любое время.

Я действительно не вижу места для улучшения здесь.

Ответ 8

Единственным окончательным ответом является проверка с вашим компилятором, вашими реальными данными.

Что-то, что я попробую (даже если он использует доступ к памяти, поэтому он может быть медленным в зависимости от кэширования)

int value = t1[s[n-1]];
if (n > 1) value += t10[s[n-2]]; else return value;
if (n > 2) value += t100[s[n-3]]; else return value;
if (n > 3) value += t1000[s[n-4]]; else return value;
... continuing for how many digits you need to handle ...

если t1, t10 и т.д. статически распределены и постоянны, компилятор не должен бояться какого-либо сглаживания, а сгенерированный машинный код должен быть вполне приличным.

Ответ 9

Вот мой. Атои - самый быстрый, с которым я мог бы придумать. Я скомпилирован с msvc 2010, поэтому можно было бы объединить оба шаблона. В msvc 2010, когда я комбинировал шаблоны, это делало случай, когда вы предоставляете аргумент cb медленнее.

Atoi обрабатывает почти все специальные случаи atoi и работает так же быстро или быстрее, чем это:

int val = 0;
while( *str ) 
    val = val*10 + (*str++ - '0');

Вот код:

#define EQ1(a,a1) (BYTE(a) == BYTE(a1))
#define EQ1(a,a1,a2) (BYTE(a) == BYTE(a1) && EQ1(a,a2))
#define EQ1(a,a1,a2,a3) (BYTE(a) == BYTE(a1) && EQ1(a,a2,a3))

// Atoi is 4x faster than atoi.  There is also an overload that takes a cb argument.
template <typename T> 
T Atoi(LPCSTR sz) {
    T n = 0;
    bool fNeg = false;  // for unsigned T, this is removed by optimizer
    const BYTE* p = (const BYTE*)sz;
    BYTE ch;
    // test for most exceptions in the leading chars.  Most of the time
    // this test is skipped.  Note we skip over leading zeros to avoid the 
    // useless math in the second loop.  We expect leading 0 to be the most 
    // likely case, so we test it first, however the cpu might reorder that.
    for ( ; (ch=*p-'1') >= 9 ; ++p) { // unsigned trick for range compare
      // ignore leading 0's, spaces, and '+'
      if (EQ1(ch, '0'-'1', ' '-'1', '+'-'1'))
        continue;
      // for unsigned T this is removed by optimizer
      if (!((T)-1 > 0) && ch==BYTE('-'-'1')) {
        fNeg = !fNeg;
        continue;
      }
      // atoi ignores these.  Remove this code for a small perf increase.
      if (BYTE(*p-9) > 4)  // \t, \n, 11, 12, \r. unsigned trick for range compare
        break;
    }
    // deal with rest of digits, stop loop on non digit.
    for ( ; (ch=*p-'0') <= 9 ; ++p) // unsigned trick for range compare
      n = n*10 + ch; 
    // for unsigned T, (fNeg) test is removed by optimizer
    return (fNeg) ? -n : n;
}

// you could go with a single template that took a cb argument, but I could not
// get the optimizer to create good code when both the cb and !cb case were combined.
// above code contains the comments.
template <typename T>
T Atoi(LPCSTR sz, BYTE cb) {
    T n = 0;
    bool fNeg = false; 
    const BYTE* p = (const BYTE*)sz;
    const BYTE* p1 = p + cb;
    BYTE ch;
    for ( ; p<p1 && (ch=*p-'1') >= 9 ; ++p) {
      if (EQ1(ch,BYTE('0'-'1'),BYTE(' '-'1'),BYTE('+'-'1')))
        continue;
      if (!((T)-1 > 0) && ch == BYTE('-'-'1')) {
        fNeg = !fNeg;
        continue;
      }
      if (BYTE(*p-9) > 4)  // \t, \n, 11, 12, \r
        break;
    }
    for ( ; p<p1 && (ch=*p-'0') <= 9 ; ++p)
      n = n*10 + ch; 
    return (fNeg) ? -n : n;
}