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

Question

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

Это самое простое решение, о котором я мог подумать:

int containsStringAnInt(char* strg){
  for (int i =0; i < strlen(strg); i++) {if (strg[i]=='.') return 0;}
  return 1;
}

Но это решение действительно медленное, когда строка длинная ... Есть предложения по оптимизации? Любая помощь будет принята с благодарностью!

Answer 1

Каков синтаксис ваших реальных чисел?

1e-6 является допустимым C ++ для литерала, но ваш тест будет передан как целое число.

Answer 2

Длина вашей строки - сотни символов? В противном случае, не волнуйтесь о возможных проблемах производительности. Единственная неэффективность заключается в том, что вы используете strlen () неправильно, что означает много итераций над строкой (внутри strlen). Для более простого решения, с той же временной сложностью (O (n)), но, возможно, немного быстрее, используйте strchr ().

Answer 3

Вы используете strlen, что означает, что вы не беспокоитесь о юникоде. В этом случае зачем использовать strlen или strchr, просто проверьте '\ 0' (Null char)

int containsStringAnInt(char* strg){ 

  for (int i =0;strg[i]!='\0'; i++) {
      if (strg[i]=='.') return 0;}   
  return 1; }

Только один разбор строки, чем разбор строки в каждой итерации цикла.

Answer 4

Ваша функция не учитывает экспоненциальную запись действительных чисел (1E7, 1E-7 - двойные)

Используйте strtol (), чтобы сначала попытаться преобразовать строку в целое число; он также вернет первую позицию в строке, где синтаксический анализ не удался (это будет «.», если число является действительным). Если синтаксический анализ остановился на «.», Используйте strtod (), чтобы попытаться преобразовать в double. Опять же, функция вернет позицию в строке, где анализ был остановлен.

Не беспокойтесь о производительности, пока вы не профилируете программу. В противном случае для максимально быстрого кода создайте регулярное выражение, описывающее приемлемый синтаксис чисел, и вручную преобразуйте его сначала в FSM, а затем в высоко оптимизированный код.

Answer 5

Итак, стандартная заметка, пожалуйста, не беспокойтесь о производительности, если она еще не профилирована:)

Я не уверен насчет ручного цикла и проверки точки. Два выпуска

• В зависимости от локали, точка на самом деле может быть и "," (здесь, в Германии, это так:)
• Как уже отмечалось, существует проблема с числами вроде 1e7

Ранее у меня была версия с использованием sscanf здесь. Но измерение производительности показало, что sscanf значительно медленнее для больших наборов данных. Поэтому сначала я покажу более быстрое решение (ну, это также намного проще. У меня было несколько ошибок в версии sscanf, пока я не заработал, в то время как версия strto [ld] работала с первой попытки):

enum {
    REAL,
    INTEGER,
    NEITHER_NOR
};

int what(char const* strg){ 
    char *endp;
    strtol(strg, &endp, 10);
    if(*strg && !*endp)
        return INTEGER;
    strtod(strg, &endp);
    if(*strg && !*endp)
        return REAL;
    return NEITHER_NOR;
}

_{Просто для удовольствия, вот версия с использованием sscanf:}

int what(char const* strg) {
    // test for int
    { 
        int d;     // converted value
        int n = 0; // number of chars read
        int rd = std::sscanf(strg, "%d %n", &d, &n);
        if(!strg[n] && rd == 1) {
            return INTEGER;
        }
    }
    // test for double
    { 
        double v;     // converted value
        int n = 0; // number of chars read
        int rd = std::sscanf(strg, "%lf %n", &v, &n);
        if(!strg[n] && rd == 1) {
            return REAL;
        }
    }
    return NEITHER_NOR;
}

Я думаю, это должно сработать. Повеселись.

Тест был выполнен путем преобразования тестовых строк (маленьких) случайным образом 10000000 раз в цикле:

• 6,6 с для sscanf
• 1,7 с для strto[dl]
• 0,5 с для manual looping до "."

Чистый выигрыш для strto[ld], учитывая, что он будет правильно разбирать числа, я буду хвалить его как победителя над ручным зацикливанием. В любом случае, разница в 1,2 с / 10000000 = 0,00000012 примерно для одной конверсии не так уж велика.

Answer 6

#include <stdlib.h>
int containsStringAnInt(char* strg){ 
    if (atof(strg) == atoi(strg))
        return 1;
    return 0;
}

Answer 7

@ Аарон, своим путем ты тоже пересекаешь строку. Один раз в Стрлен, и еще раз в течение цикла. Лучший способ обхода строки ASCII в цикле for - проверять наличие нулевого символа в цикле, который он сам. Посмотрите на мой ответ, который анализирует строку только один раз в цикле for, и может быть частичным анализом, если он находит '.' до конца. таким образом, если строка похожа на 0.01xxx (еще 100 символов), вам не нужно идти до конца, чтобы найти длину.

Answer 8

Стрлен проходит строку, чтобы найти длину строки.

Вы вызываете strlen с каждым проходом цикла. Следовательно, вы идете по струне намного больше, чем необходимо. Это крошечное изменение должно дать вам огромное улучшение производительности:

int containsStringAnInt(char* strg){
  int len = strlen(strg);
  for (int i =0; i < len; i++) {if (strg[i]=='.') return 0;}
  return 1;
}

Обратите внимание, что все, что я сделал, это нашел длину строки один раз в начале функции и неоднократно обращался к этому значению в цикле.

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