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

Можно ли улучшить производительность этого алгоритма последовательного поиска (взятого из «Практики программирования» ), используя любую из собственных утилит 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;
}
19.08.2008 07:28:31
Прошу прощения за дождь на вашем параде, но в 85-м году я услышал шутку о том, что есть три типа компиляторов Си register: действительно тупые, которые игнорируют это; тупые, которые резервируют некоторые регистры для registerиспользования; умные, которые игнорируют это (потому что они лучше распределяют значения по регистрам, чем когда-либо мог сделать прогаммер).
vonbrand 1.02.2013 20:20:25
10 ОТВЕТОВ
РЕШЕНИЕ

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

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

24
19.08.2008 07:33:20

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

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

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

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

2
19.08.2008 07:36:47

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

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

1
19.08.2008 08:05:16

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

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

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

Мой 2р (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++;
}
0
19.08.2008 12:46:12

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

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

0
3.07.2012 15:00:26

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

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

0
16.09.2008 12:26:39

Более быстрый способ сопоставления строк - хранить их в стиле 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 и начала следующей строки. Но это просто безумие. :-)

0
31.10.2008 04:57:47

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

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

0
31.10.2008 05:09:57
/* 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;
}
-1
21.11.2013 09:13:50
Таким образом, единственное отличие заключается в перемещении приращения указателя в условие завершения цикла for вместо неявного выполнения с помощью array[i]. Вы ничего не улучшили и затруднили чтение кода. Отлично сработано.
Thomas 21.11.2013 09:47:50