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

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

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

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

Answer 2

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

от 48 до 57 десятичных знаков

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

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

Answer 3

Память Prefetch

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

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

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

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

Профилирующая обратная связь

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

Answer 4

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

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

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

Answer 5

Я могу ошибаться, но может быть более быстрый путь.

Быстрая сортировка строки.

В последовательном поиске наилучшее время O (1), среднее значение O (1 / 2n) и худшее значение O (n).

Быстрая сортировка имеет лучшее значение O (log n), среднее значение O (nlog n), худшее значение O (n ^ 2).

Дело в том, что вы можете выйти из быстрой сортировки, как только увидите цифру . Если быстрая сортировка фактически завершилась, цифра будет в начале отсортированной строки, поэтому вы найдете ее в O (1).

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

Answer 6

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

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