Otimizando um algoritmo de busca em C

Question

O desempenho deste algoritmo de busca sequencial (retirado deA prática da programação) ser melhorado usando qualquer um dos utilitários nativos do C, por exemplo.se eu definir a variável i como uma variável de registro?

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

Sim, mas apenas muito ligeiramente.Uma melhoria de desempenho muito maior pode ser alcançada usando algoritmos melhores (por exemplo, mantendo a lista ordenada e fazendo uma pesquisa binária).

Em geral, otimizar um determinado algoritmo só leva você até certo ponto.Escolher um algoritmo melhor (mesmo que não esteja completamente otimizado) pode proporcionar uma melhoria considerável (em ordem de grandeza) de desempenho.

Answer 2

Acho que não fará muita diferença.O compilador já irá otimizá-lo nessa direção.

Além disso, a variável i não tem muito impacto, a palavra permanece constante durante toda a função e o restante é grande demais para caber em qualquer registro.É apenas uma questão de quão grande é o cache e se todo o array cabe nele.

As comparações de strings são bastante caras computacionalmente.

Você pode usar algum tipo de hash para o array antes de pesquisar?

Answer 3

Existe uma técnica bem conhecida como método sentinela.Para usar o método sentinal, você deve saber o comprimento de "array[]".Você pode remover "array[i] != NULL" comparando usando 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

Se você estiver lendo o TPOP, verá a seguir como eles tornam essa pesquisa muito mais rápida com diferentes estruturas de dados e algoritmos.

Mas você pode tornar as coisas um pouco mais rápidas substituindo coisas como

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

com

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

Se houver um valor conhecido no final da matriz (por exemploNULL) você pode eliminar o contador de loop:

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

Boa sorte, é um ótimo livro!

Answer 5

Para otimizar esse código, a melhor aposta seria reescrever a rotina strcmp, pois você está apenas verificando a igualdade e não precisa avaliar a palavra inteira.

Fora isso você não pode fazer muito mais.Você não pode classificar porque parece que está procurando texto dentro de um texto maior.A pesquisa binária também não funcionará, pois é improvável que o texto seja classificado.

Meu 2p (C-psuedocódigo):

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

Marcos Harrison:Seu loop for nunca terminará!(++p está recuado, mas na verdade não está dentro do for :-)

Além disso, alternar entre ponteiros e indexação geralmente não terá efeito no desempenho, nem adicionar palavras-chave de registro (como já mencionado) - o compilador é inteligente o suficiente para aplicar essas transformações quando apropriado, e se você contar o suficiente sobre o arco da sua CPU , ele fará um trabalho melhor do que pseudo-micro-otimizações manuais.

Answer 7

Uma maneira mais rápida de combinar strings seria armazená-las no estilo Pascal.Se você não precisar de mais de 255 caracteres por string, armazene-os mais ou menos assim, com a contagem no primeiro byte:

char s[] = "\x05Hello";

Então você pode fazer:

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

E para ficar realmente rápido, adicione dicas de pré-busca de memória para o início da string + 64, + 128 e o início da próxima string.Mas isso é uma loucura.:-)

Answer 8

Outra maneira rápida de fazer isso é fazer com que seu compilador use um memcmp otimizado para SSE2.Use matrizes de caracteres de comprimento fixo e alinhe para que a string comece em um alinhamento de 64 bytes.Então acredito que você pode obter boas funções memcmp se passar const char match[64] em vez de const char *match na função ou strncpy match em uma matriz de 64.128.256, qualquer que seja o byte.

Pensando um pouco mais sobre isso, essas funções de correspondência SSE2 podem fazer parte de pacotes como as bibliotecas aceleradoras da Intel e da AMD.Confira.

Answer 9

Realisticamente, definir I como uma variável de registro não fará nada que o compilador já não fizesse.

Se você estiver disposto a gastar algum tempo pré-processando a matriz de referência, você deve pesquisar no Google "O programa Scrabble mais rápido do mundo" e implementá-lo.Spoiler:é um DAG otimizado para pesquisas de personagens.

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