Какой самый быстрый способ определить, появляется ли цифра в строке?

Question

Это простое решение быстро пришло мне в голову.

#include <ctype.h>

int digit_exists_in
(
    const char *s
)
{
    while (*s)
    {
        if (isdigit(*s))
        {
            return 1;
        }
        else
        {
            s++;
        }
    }

    return 0;
}

int main(void)
{
    int foundDigit = digit_exists_in("abcdefg9ijklmn");

    return 0;
}

Какие еще приемы можно применить для повышения скорости?

Фактические искомые строки имеют переменную длину, а сами символы ASCII, а не полный набор символов. Строки заканчиваются NUL.

Answer 1

liw.fi правильно, кстати. Я был немного удивлен этим, поскольку strcspn должен решать гораздо более общую проблему, чем подход isdigit (), но, похоже, это так:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>

#define NTESTS 10000
#define TESTSIZE 10000

char stest1[TESTSIZE];
char stest2[TESTSIZE];

int test_isdigit(char *s) {
    while (*s) {
        if (isdigit(*s)) return 1;
        s++;
    }
    return 0;
}

int test_range(char *s) {
    while (*s) {
        if ((*s >= '0') && (*s <= '9')) return 1;
        s++;
    }
    return 0;
}

int test_strcspn(char *s) {
    return s[strcspn(s, "0123456789")] != '\0';
}

int main(int argc, char **argv) {
    long int i;
    for (i=0; i<TESTSIZE; i++) {
        stest1[i] = stest2[i] = 'A' + i % 26;
    }
    stest2[TESTSIZE-1] = '5';

    int alg = atoi(argv[1]);

    switch (alg) {
        case 0:        
            printf("Testing strcspn\n");
            for (i=0; i<NTESTS; i++) {
                assert(test_strcspn(stest1) == 0);
                assert(test_strcspn(stest2) != 0);
            }
            break;
        case 1:
            printf("Testing isdigit() loop\n");
            for (i=0; i<NTESTS; i++) {
                assert(test_isdigit(stest1) == 0);
                assert(test_isdigit(stest2) != 0);
            }
            break;
        case 2:
            printf("Testing <= => loop\n");
            for (i=0; i<NTESTS; i++) {
                assert(test_range(stest1) == 0);
                assert(test_range(stest2) != 0);
            }
            break;
        default:
            printf("eh?\n");
            exit(1);
    }    

    return 0;
}

Очень сложно побить стандартные библиотеки в их собственной игре ... (применяются обычные предостережения - YMMV) * ​​1006 *

$ gcc -O6 -Wall -o strcspn strcspn.c 

$ time ./strcspn 0
Testing strcspn

real    0m0.085s
user    0m0.090s
sys 0m0.000s

$ time ./strcspn 1
Testing isdigit() loop

real    0m0.753s
user    0m0.750s
sys 0m0.000s

$ time ./strcspn 2
Testing <= => loop

real    0m0.247s
user    0m0.250s
sys 0m0.000s

---

ОБНОВЛЕНИЕ: Ради интереса я добавил версию для поиска растровых изображений, основанную на ответе Майка Данлави:

char bitmap[256] = {
        /* 0x00 */ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        /* 0x10 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        /* 0x20 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        /* 0x30 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
};

int test_bitmap(char *s) {
    while (!bitmap[*(unsigned char *)s]) s++;
    return (*s);
}

Что немного превосходит другие (~ .170s), но все еще не может коснуться strcspn!

Answer 2

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

#include <string.h>
#include <stdio.h>

int digit_exists_in(const char *s)
{
    return s[strcspn(s, "0123456789")] != '\0';
}

int main(void)
{
    printf("%d\n", digit_exists_in("foobar"));
    printf("%d\n", digit_exists_in("foobar1"));
    return 0;
}

Если библиотека недостаточно оптимизирована, было бы неплохо поместите оптимизацию в библиотеку, чтобы каждый мог извлечь выгоду. (У вас есть источник, не так ли?)

Answer 3

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

Так, например, вы можете сделать что-то вроде:

byte buffer[8] = { 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30, 0x30 };
uint64 *mask = (uint64 *) buffer; //this is just for clarity

if (*((uint64 *) s) & *mask) == 0)
    //You now don't need to do the < '0' test for the next 8 bytes in s

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

Вам лучше сравнить ТОННУ байтов, чтобы подумать об оптимизации на этом уровне.

Answer 4

Любой алгоритм будет O (N).

Полагаю, isdigit уже достаточно эффективен.

Answer 5

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

Answer 6

Просто для удовольствия, может быть, что-то вроде:

 // accumulator
unsigned char thereIsADigit = 0;
// lookup table
unsigned char IsDigit[256] = {0,0,0 ..., 1,1,1,1,1,1,1,1,1,0,0,0 ...};

// an unrolled loop, something like:
thereIsADigit |= IsDigit[s[0]];
thereIsADigit |= IsDigit[s[1]];
thereIsADigit |= IsDigit[s[2]];
thereIsADigit |= IsDigit[s[3]];
thereIsADigit |= IsDigit[s[4]];
thereIsADigit |= IsDigit[s[5]];
thereIsADigit |= IsDigit[s[6]];
thereIsADigit |= IsDigit[s[7]];
if (thereIsADigit) break;
s += 8;

На IBM 360 существовала инструкция "перевод" , которая могла сделать это за один шаг.

ОК, ОК, Ответ Кристофера Смита заставил меня задуматься. Предположим, вы используете только 7-битный ASCII. Вот способ сделать SIMD с помощью целочисленной арифметики.

Предположим, C - это 32-битное слово, содержащее 4 символа.

 // compare by subtracting in 8-bit 2s complement arithmetic
( (C + ((0x3a3a3a3a ^ 0x7f7f7f7f) + 0x01010101)) // set high bit for any char <= '9'
  &
  (0x2f2f2f2f + ((C ^ 0x7f7f7f7f) + 0x01010101)) // set high bit for any char >= '0'
) // high bit is set for any char <= '9' and >= '0'
& 0x80808080 // look only at the high-order bits
// if any of these 4 bits is 1, there is a digit in C
// if the result is zero, there are no digits in C

Это зависит от того, что старший бит каждого символа изначально равен нулю, поэтому перенос в этот бит не будет распространяться. (Я уверен, что это можно упростить.)

Answer 7

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

Answer 8

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

Answer 9

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

      Count      %   % with           Time   Statement
                      child
-----------------------------------------------------------------------------------------------
                                             int test_isdigit(char *s)   
     20,000    0.0    0.0          2,160.4   {   
199,990,000   13.2    9.5     14,278,460.7       while (*s)  
                                                 {   
199,980,000   69.8   49.9     75,243,524.7            if (isdigit(*s)) return 1;  
199,970,000   17.0   12.1     18,312,971.5            s++;    
                                                 }   

     10,000    0.0    0.0          1,151.4       return 0;   
                                             }   

                                             int test_range(char *s)     
     20,000    0.0    0.0          1,734.2   {   
199,990,000   33.6    9.4     14,114,309.7       while (*s)  
                                                 {
199,980,000   32.2    9.0     13,534,938.6           if ((*s >= '0') && 
                                                        (*s <= '9')) return 1;   
199,970,000   34.2    9.5     14,367,161.9           s++;    
                                                 }   

     10,000    0.0    0.0          1,122.2       return 0;   
                                             }   

                                             int test_strcspn(char *s)   
     20,000    0.2    0.0          1,816.6   {   
     20,000   99.8    0.6        863,113.2       return s[strcspn(s, "0123456789")] 
                                                          == '0'; 
                                             }   

strcspn делает работу достаточно хорошо. Глядя на код asm для него, я вижу, что он создает растровое изображение размером 256, устанавливает биты на основе символов поиска, а затем обрабатывает строку.

Битовая карта создается в стеке один раз для каждого вызова.

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

Другой подход заключается в параллельном выполнении операций с использованием методов, которые Крис Смит говорил о.

На данный момент strcspn будет достаточно.

Answer 10

Вот версия, которая может быть или не быть быстрее, но она обрабатывает нулевой указатель ...

int digit_exists_in(const char *s)
{
    if (!s)
        return (0);
    while (*s)
        if (isdigit(*s++))
            return (1);
    return (0);
}