Оптимизация алгоритма поиска на 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

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

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

Сравнение строк требует больших вычислительных затрат.

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

Answer 3

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

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

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

Мой 2p (C-псевдокод):

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

Answer 6

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

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

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

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

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

Answer 9

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

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

Answer 10

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