Оптимизация алгоритма поиска в C

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

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

Я думаю, что это не будет иметь большого значения. Компилятор уже оптимизирует его в этом направлении.

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

Сравнение строк является довольно дорогостоящим вычислительным процессом.

Может быть, вы можете использовать какой-то вид хэширования для массива перед поиском?

Есть известный метод, как способ магистраль. Чтобы использовать sentinal метод, вы должны знать о длине "array[]". Вы можете удалить "array[i] != NULL " сравнение с помощью sentinal.

int lookup(char *word, char*array[], int array_len)
{
    int i = 0;
    array[array_len] = word;
    for (;; ++i)
        if (strcmp(word, array[i]) == 0) 
            break;
    array[array_len] = NULL;
    return (i != array_len) ? i : -1;
}

Если Вы читаете TPOP, вы увидите, как они делают этот поиск во много раз быстрее с помощью различных структур данных и алгоритмов.

Но вы можете сделать все немного быстрее, заменив такие вещи, как

for (i = 0; i < n; ++i)
    foo(a[i]);

с

char **p = a;
for (i = 0; i < n; ++i)
    foo(*p);
    ++p;

Если в конце массива есть известное значение (например, NULL), то можно исключить счетчик циклов:

for (p = a; *p != NULL; ++p)
    foo(*p)

Удачи, это отличная книга!

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

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

Мой 2p (C-psuedocode):

wrd_end = wrd_ptr + wrd_len;
arr_end = arr_ptr - wrd_len;
while (arr_ptr < arr_end)
{
    wrd_beg = wrd_ptr; arr_beg = arr_ptr;
    while (wrd_ptr == arr_ptr)
    {
        wrd_ptr++; arr_ptr++;
        if (wrd_ptr == wrd_en)
            return wrd_beg;
    }
    wrd_ptr++;
}

Реально, установка I в качестве переменной регистра не сделает ничего такого, чего бы уже не сделал компилятор.

Если вы хотите потратить некоторое время на предварительную предварительную обработку ссылочного массива, вам следует google "The World's Fastest Scrabble Program" и реализовать это. Спойлер: это DAG, оптимизированный для поиска персонажей.

Марк Харрисон: ваш цикл for никогда не закончится! (++p имеет отступ, но на самом деле не находится в пределах for :-)

Кроме того, переключение между указателями и индексацией обычно не влияет на производительность, равно как и добавление ключевых слов регистра (как уже упоминал Мэт) - компилятор достаточно умен, чтобы применить эти преобразования там, где это необходимо, и если вы достаточно расскажете ему о своей cpu-арке, он сделает это лучше, чем ручной psuedo-micro-optimizations.

Более быстрым способом сопоставления строк было бы их хранение в стиле Pascal. Если вам не нужно больше 255 символов на строку, храните их примерно так, с количеством в первом байте:

char s[] = "\x05Hello";

Тогда вы можете сделать:

for(i=0; i<len; ++i) {
    s_len = strings[i][0];
    if(
        s_len == match_len
        && strings[i][s_len] == match[s_len-1]
        && 0 == memcmp(strings[i]+1, match, s_len-1)
    ) {
        return 1;
    }
}

И чтобы получить действительно быстро, добавьте подсказки предварительной выборки памяти для строки start + 64, + 128 и начала следующей строки. Но это просто безумие. :-)

Еще один быстрый способ сделать это-заставить ваш компилятор использовать оптимизированный для SSE2 memcmp. Используйте массивы символов фиксированной длины и выровняйте так, чтобы строка начиналась с 64-байтового выравнивания. Тогда я считаю, что вы можете получить хорошие функции memcmp, если вы передадите const char match[64] вместо const char *match в функцию или strncpy match в 64,128,256, какой угодно байтовый массив.

Подумав немного больше об этом, эти функции соответствия SSE2 могут быть частью пакетов, таких как библиотеки ускорителей Intel и AMD. Проверить их.

/* there is no more quick  */
int lookup(char *word, char*array[])
{
    int i;
    for(i=0; *(array++) != NULL;i++)
        if (strcmp(word, *array) == 0)
            return i;
    return -1;
}