Get best of the week

PHP: array_key_exists pesquisa 500 vezes mais rápido que in_array

Em 2014, eles já escreveram sobre a pesquisa da matriz , mas quase ninguém entendeu.

Desde então, muitas versões do PHP foram lançadas e não foram corrigidas, o que significa que o feedback é ruim e poucas pessoas sabem disso. No python, é o mesmo e em 3 * pior que no 2.7.

Às vezes, você precisa encontrar uma string em uma matriz de strings - uma operação muito frequente em algoritmos diferentes, e se a matriz for pequena e parecer um pouco e não em um loop, o in_array é normal, não afeta a velocidade geral, mas se você precisar de big data e procurar uma matriz de um bilhão de linhas e um bilhão de vezes , isso é crítico: hora melhor em vez de semana.

Um teste simples mostra:

in_array procura ideone.com/Yb1mDa 6600msem 6-9 segundos
e array_key_exists procura a mesma coisa, mas mais rápido que 250 (php5.6 / py3. *) 400+ vezes (php7.3 / py2.7) ideone .com / gwSmFc(o ciclo aumentou 100 vezes) 12ms (6600/12 = 550 vezes + -10% de spread devido à carga e ao cache)

Por que isso está acontecendo? Considere em detalhes:

1) Encontrar seqüências de caracteres em puro assembler (s) é classificar uma matriz de seqüências de caracteres (rápida ou bolha) e, em seguida, pesquisa binária.

O número de etapas em um log de pesquisa binária (n) vezes depende do tamanho da matriz e é muito menor que uma pesquisa simples.

Você pode classificar uma matriz de seqüências antecipadamente, uma vez, e armazenar em cache e, em seguida, fazer um bilhão de pesquisas. Mas isso não ajuda.

Por padrão, a classificação acontece novamente, embora eles tenham escrito que melhoraram na 7.2 in_array por meio de um hash, mas não muito.

2) Pesquise índice / chave (como uma sequência) na associação. array / dicionário ocorre por hash de strings e processamento de colisão. (erros de pesquisa de hash). Um hash é o índice numérico da matriz e a busca dela como (endereço do elemento zero) + deslocamento * o tamanho do ponteiro para a matriz de cadeias com esse hash) em 2 etapas. + colisões de força bruta, etapas em média inferiores à pesquisa binária.
O hash do índice é feito automaticamente uma vez com antecedência ao criar o elemento de dicionário $ m [key] = val e é armazenado em cache.

O tamanho do hash, o algoritmo de hash é costurado no mecanismo PCP e não pode ser alterado, embora o código-fonte esteja aberto, você pode fazer o download para alterar e compilar o servidor.

Você não pode ler mais, altere in_array para array_combine + array_key_exists e é isso.

O número de etapas ao pesquisar por hash depende do número de colisões e do número de linhas com o mesmo hash. Eles precisam ser classificados ou também classificados e pesquisa binária.

Para reduzir colisões, você pode alocar mais memória, se for possível que agora não seja um problema como há 50 anos, quando 1 kb de memória em bobinas magnéticas custam como um avião. E foi então que todos os algoritmos básicos foram inventados: sort / zip / gif / jpg / etc. - eles não precisam de muita memória, mas são ruins, agora são muito melhores, mas precisam de muita memória de 1 a 16 MB. Sim, existem servidores com 256 MB e cada um tem um fluxo separado e 16 MB já é muito, mas no dispositivo do usuário médio de 1 GB, pelo menos 16 MB é uma queda no balde.

Você pode obter ainda mais efeito se substituir a chamada para a função array_key_exists pela construção isset ($ m [key]), não limpa a fila de comandos e o cache, não usa a pilha e é mais rápida em cerca de 20%.

Você também pode acelerar se criar uma matriz das 2 primeiras letras - 4 * 16kb e observar primeiro o deslocamento (índice = código do 1º caractere + 2º * 256), um ponteiro para a matriz de hash pelo resto da linha e procurar uma pequena matriz de "caudas" de strings e colisões são muito menores.

Requer ainda mais memória e o algoritmo é mais complicado, mas a pesquisa é 30 vezes mais rápida. Mas isso não é implementado no php, você pode escrever sua biblioteca so / dll e chamá-la ou pedir aos desenvolvedores para adicioná-la na 7.5.

Você pode pesquisar no mySQL, mas precisa agrupar consultas e ainda será mais lento.

PS: Esse método foi encontrado acidentalmente por digitação, intuição e experiência quando acelerei um grande site lento, existem muitas sutilezas e truques, consegui exportar os dados de 40 segundos para 0,8 segundos, listas de saída com classificação e filtros e muitos outros coisas em que truques, estruturas e estruturas padrão fazem tudo muito devagar, embora obviamente sejam convenientes e acelerem o desenvolvimento.

More articles:


All Articles