c - 确定数字是否出现在字符串中的最快方法是什么？

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)

$ 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

---

更新:为了好玩，我添加了一个基于 Mike Dunlavey 回答的位图查找版本:

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!