Что состоит в том, чтобы решить самый быстрый путь, появляется ли цифра в строке?

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

Book Series - 
Book Title  - Distributed Computing
Chapter Title  - On the Impact of Fast Failure Detectors on Real-Time Fault-Tolerant Systems
First Page  - 354
Last Page  - 369
Copyright  - 2002
Author  - Marcos K. Aguilera
Author  - Gérard Le Lann
Author  - Sam Toueg
DOI  - 10.1007/3-540-36108-1_24
Link  - http://www.springerlink.com/content/e03yf4etbnle9728

Book Title  - Distributed Algorithms
Chapter Title  - Heartbeat: A timeout-free failure detector for quiescent reliable communication
First Page  - 126
Last Page  - 140
Copyright  - 1997
Author  - Marcos Kawazoe Aguilera
Author  - Wei Chen
Author  - Sam Toueg
DOI  - 10.1007/BFb0030680
Link  - http://www.springerlink.com/content/dj5n71hl17841416

Кроме того, из вопроса не ясно, но если речь идет о Java, отличный ресурс по этой теме: Введение в надежное распределенное программирование , с множеством отличных примеров кода.

Профилирование обратной связи

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

Конечно, вы можете пожертвовать точностью ради скорости:

int digit_exists_in(const char* s)
{
    return 0;
}

Этот алгоритм имеет сложность O (1) и приблизительная величина O ((246/256) ^ N).

I may be wrong, but there may be a faster way.

Quicksort the string.

The serial search has a best time of O(1), a mean of O(1/2n) and worse case of O(n).

Quicksort has best O(log n), mean O(nlog n), worse case O(n^2).

The thing is, you can bail out of the quicksort as soon as you see a digit. If the quicksort actually completes, the digit will be at the beginning of the sorted string, so you'll find it then in O(1).

The achievement here it to shift the best, mean and worse case behaviours. A quicksort will have worse worst case behaviour, but better mean behaviour.

Посмотрите на это по-человечески. Люди могут сделать это за O (1) время, у нас НАМНОГО больше размеров слова, чем даже современные процессоры.

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

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

      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 будет достаточно.

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

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

Как уже говорили другие, вы не можете опускаться ниже O (N).

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

если вы действительно хотите сократить накладные расходы и не возражаете сделать их специфичными для char, то вы можете проверьте значения ASCII от 0 до 9 включительно.

Десятичное число от 48 до 57.

Это удаляет вызов стека.

Я должен был также сказать таблицу поиска ...

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

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

Не существует более быстрого алгоритма, но вы можете посмотреть на значение полного регистра в байтах на инструкцию или использовать 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

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

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

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

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

Я предполагаю, что isdigit уже довольно эффективен.

Я бы начал с использования соответствующей библиотечной функции, 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;
}

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

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

 // 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

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