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

Question

Может ли производительность этого алгоритма последовательного поиска (взято из Практика программирования ) может быть улучшена с помощью любых собственных утилит C, например, если я установлю переменную i как переменную регистра?

int lookup(char *word, char*array[])
{
    int i

    for (i = 0; array[i] != NULL; i++)
        if (strcmp(word, array[i]) == 0)
            return i;

    return -1;
}

Answer 1

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

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

Answer 2

Существует хорошо известная техника, как дозорный метод. Чтобы использовать метод 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;
}

Answer 3

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

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

Сравнение строк довольно дорого в вычислительном отношении.

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

Answer 4

Если вы читаете 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)

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

Answer 5

/* 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;
}

Answer 6

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

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

Answer 7

Более быстрый способ сопоставления строк - хранить их в стиле 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;
    }
}

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

Answer 8

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

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

Answer 9

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

Если вы готовы потратить некоторое время на предварительную обработку массива ссылок, вам нужно зайти в Google «Самая быстрая в мире программа скрэббл» и реализовать ее. Спойлер: это DAG, оптимизированная для поиска персонажей.

Answer 10

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

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

My 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++;
}