Lista de funções Big-O para PHP

345

Depois de usar o PHP há algum tempo, notei que nem todas as funções embutidas do PHP são tão rápidas quanto o esperado. Considere estas duas implementações possíveis de uma função que descobre se um número é primo usando uma matriz de números primos em cache.

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $prime_array => $number ) {
    $result_array[$number] = in_array( $number, $large_prime_array );
}

//speed is much less dependent on size of $prime_array, and runs much faster.
$prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL,
                       11 => NULL, 13 => NULL, .... 104729 => NULL, ... );
foreach( $prime_array => $number ) {
    $result_array[$number] = array_key_exists( $number, $large_prime_array );
}

Isso ocorre porque in_arrayé implementado com uma pesquisa linear O (n) que diminui linearmente à medida que $prime_arraycresce. Onde a array_key_existsfunção é implementada com uma pesquisa de hash O (1), que não diminui a velocidade, a menos que a tabela de hash seja extremamente preenchida (nesse caso, é apenas O (n)).

Até agora, tive que descobrir os grandes Os por tentativa e erro, e ocasionalmente olhando o código-fonte . Agora, a pergunta ...

Existe uma lista dos grandes tempos teóricos (ou práticos) para todas as * funções embutidas do PHP?

* ou pelo menos os interessantes

Por exemplo, acho que é muito difícil prever o grande O de funções listadas porque a possível implementação depende de estruturas de dados do núcleo desconhecido do PHP: array_merge, array_merge_recursive, array_reverse, array_intersect, array_combine,str_replace (com entradas de matriz), etc.

Kendall Hopkins
fonte
31
Totalmente fora do tópico, mas 1 não é primo.
Jason Punyon
24
Matrizes em PHP são hashtables. Isso deve dizer tudo o que você precisa saber. Procurando por uma chave em uma tabela de hash é O (1). A pesquisa de um valor é O (n) - que você não pode superar em um conjunto não classificado. A maioria das funções que lhe interessam provavelmente são O (n). Claro, se você realmente quer saber, pode ler a fonte: cvs.php.net/viewvc.cgi/php-src/ext/standard/…
Frank Farmer
11
Para o registro, a implementação mais rápida do que você está tentando fazer seria (em vez de usar NULL para seus valores) usar truee, em seguida, testar a presença isset($large_prime_array[$number]). Se bem me lembro, é da ordem de centenas de vezes mais rápido que a in_arrayfunção.
mattbasta
3
A notação Big O não é sobre velocidade. É sobre limitar o comportamento.
Gumbo
3
@ Kendall não estou comparando array_key_exists, estou comparando a in_array.in_arrayitera cada item da matriz e compara o valor à agulha que você passa para ela. Se você alternar os valores para a chave (e apenas substituir cada um deles por um valor fictício como true, usar isseté muitas vezes mais rápido. Isso ocorre porque as chaves de uma matriz são indexadas pelo PHP (como uma hashtable)). uma matriz dessa maneira pode ter uma melhoria significativa na velocidade. #
mattbasta

Respostas:

649

Como não parece que alguém tenha feito isso antes, pensei que seria uma boa ideia tê-lo como referência em algum lugar. Eu fui embora e via benchmark ou skimming de código para caracterizar oarray_* funções. Eu tentei colocar o Big-O mais interessante perto do topo. Está lista não está completa.

Nota: Todo o Big-O foi calculado assumindo uma pesquisa de hash é O (1), embora seja realmente O (n). O coeficiente de n é tão baixo que a sobrecarga de memória RAM de armazenar uma matriz grande o suficiente o prejudicaria antes que as características da pesquisa Big-O começassem a surtir efeito. Por exemplo, a diferença entre uma chamada paraarray_key_exists N = 1 e N = 1.000.000 é de aproximadamente 50% de aumento de tempo.

Pontos interessantes :

  1. isset/ array_key_existsé muito mais rápido que in_arrayearray_search
  2. +(união) é um pouco mais rápido que array_merge(e parece melhor). Mas funciona de maneira diferente, portanto, lembre-se disso.
  3. shuffle está no mesmo nível Big-O que array_rand
  4. array_pop/array_push é mais rápido que array_shift/ array_unshiftdevido à re-indexação da penalidade

Pesquisas :

array_key_existsO (n), mas realmente próximo de O (1) - isso ocorre por causa de pesquisas lineares em colisões, mas como a chance de colisões é muito pequena, o coeficiente também é muito pequeno. Acho que você trata as pesquisas de hash como O (1) para fornecer um big-O mais realista. Por exemplo, a diferença entre N = 1000 e N = 100000 é apenas cerca de 50% mais lenta.

isset( $array[$index] )O (n), mas realmente próximo de O (1) - ele usa a mesma pesquisa que array_key_exists. Como é uma construção de idioma, a pesquisa será armazenada em cache se a chave for codificada, resultando em aceleração nos casos em que a mesma chave for usada repetidamente.

in_array O (n) - isso ocorre porque ele faz uma pesquisa linear pela matriz até encontrar o valor.

array_search O (n) - usa a mesma função principal que in_array, mas retorna valor.

Funções de fila :

array_push O (∑ var_i, para todos os i)

array_pop O (1)

array_shift O (n) - ele precisa reindexar todas as chaves

array_unshift O (n + ∑ var_i, para todos os i) - ele precisa reindexar todas as chaves

Intersecção, União, Subtração da Matriz :

array_intersect_key se a interseção 100% fizer O (Max (param_i_size) * ∑param_i_count, para todos os i), se a interseção 0% interceptar O (∑param_i_size, para todos os i)

array_intersect se a interseção 100% fizer O (n ^ 2 * amparam_i_count, para todos os i), se a interseção 0% interceptar O (n ^ 2)

array_intersect_assoc se a interseção 100% fizer O (Max (param_i_size) * ∑param_i_count, para todos os i), se a interseção 0% interceptar O (∑param_i_size, para todos os i)

array_diff O (π param_i_size, para todos os i) - Esse é o produto de todos os param_sizes

array_diff_key O (∑ param_i_size, para i! = 1) - isso ocorre porque não precisamos iterar sobre a primeira matriz.

array_merge O (∑ matriz_i, i! = 1) - não precisa iterar sobre a primeira matriz

+ (union) O (n), onde n é o tamanho da segunda matriz (ou seja, array_first + array_second) - menos sobrecarga que array_merge, pois não precisa renumerar

array_replace O (∑ matriz_i, para todos os i)

Aleatório :

shuffle Em)

array_rand O (n) - Requer uma pesquisa linear.

Big-O óbvio :

array_fill Em)

array_fill_keys Em)

range Em)

array_splice O (deslocamento + comprimento)

array_slice O (deslocamento + comprimento) ou O (n) se comprimento = NULL

array_keys Em)

array_values Em)

array_reverse Em)

array_pad O (tamanho do bloco)

array_flip Em)

array_sum Em)

array_product Em)

array_reduce Em)

array_filter Em)

array_map Em)

array_chunk Em)

array_combine Em)

Gostaria de agradecer à Eureqa por facilitar a localização do Big-O das funções. É um programa gratuito incrível que pode encontrar a melhor função de ajuste para dados arbitrários.

EDITAR:

Para aqueles que duvidam que as pesquisas de matriz PHP sejam O(N), escrevi uma referência para testar isso (elas ainda são efetivamente O(1)para os valores mais realistas).

gráfico de pesquisa de matriz php

$tests = 1000000;
$max = 5000001;


for( $i = 1; $i <= $max; $i += 10000 ) {
    //create lookup array
    $array = array_fill( 0, $i, NULL );

    //build test indexes
    $test_indexes = array();
    for( $j = 0; $j < $tests; $j++ ) {
        $test_indexes[] = rand( 0, $i-1 );
    }

    //benchmark array lookups
    $start = microtime( TRUE );
    foreach( $test_indexes as $test_index ) {
        $value = $array[ $test_index ];
        unset( $value );
    }
    $stop = microtime( TRUE );
    unset( $array, $test_indexes, $test_index );

    printf( "%d,%1.15f\n", $i, $stop - $start ); //time per 1mil lookups
    unset( $stop, $start );
}
Kendall Hopkins
fonte
5
@ Kendall: Obrigado! Eu li um pouco e o PHP usa hashtables 'aninhadas' para colisões. Ou seja, em vez de uma estrutura de logn para colisões, ela simplesmente usa outra hashtable. E eu entendo que, na prática, as hashtables PHP oferecem desempenho O (1), ou pelo menos O (1) em média - é para isso que servem as hashtables. Eu estava curioso para saber por que você disse que eles são "realmente O (n)" e não "realmente O (logn)". Ótimo post por sinal!
Cam
10
Complexidades de tempo devem ser incluídas na documentação! Escolher a função correta pode economizar muito tempo ou pedir para você evitar o que planejava: p Obrigado por esta lista já!
Samuel
41
Eu sei que isso é velho ... mas o que? Essa curva não mostra O (n), mostra O (log n), en.wikipedia.org/wiki/Logarithm . O que também é preciso com o que você esperaria de mapas de hash aninhados.
Andreas
5
Qual é o Big-O de unset em um elemento de uma matriz?
Chandrew
12
Embora as hashtables tenham, de fato, a pior complexidade de pesquisa de O (n), o caso médio é O (1) e o caso particular que seu benchmark está testando é ainda garantido O (1), pois é uma base zero, contínua e indexada numericamente array, que nunca terá colisões de hash. A razão pela qual você ainda está vendo uma dependência do tamanho da matriz não tem nada a ver com a complexidade algorítmica, é causada pelos efeitos do cache da CPU. Quanto maior a matriz, maior a probabilidade de as pesquisas de acesso aleatório resultarem em erros de cache (e em cache mais altos na hierarquia).
NikiC 28/01
5

A explicação para o caso que você descreve especificamente é que matrizes associativas são implementadas como tabelas de hash - portanto, procure por chave (e, correspondentemente, array_key_exists ) é O (1). No entanto, matrizes não são indexadas por valor, portanto, a única maneira de descobrir se existe um valor na matriz é uma pesquisa linear. Não há nenhuma surpresa lá.

Eu não acho que exista documentação abrangente específica da complexidade algorítmica dos métodos PHP. No entanto, se é uma preocupação grande o suficiente para justificar o esforço, você sempre pode procurar no código-fonte .

Dathan
fonte
Esta não é realmente uma resposta. Como afirmei na pergunta, já tentei examinar o código-fonte PHP. Como o PHP é implementado, ele é escrito em C, usando macros complexas, que às vezes dificultam "ver" o grande O subjacente das funções.
Kendall Hopkins
@ Kendall Eu ignorei sua referência a mergulhar no código fonte. No entanto, há uma resposta na minha resposta: "Não acho que exista documentação abrangente específica da complexidade algorítmica dos métodos PHP". "Não" é uma resposta perfeitamente válida. (c:
Dathan
4

Você quase sempre deseja usar em issetvez de array_key_exists. Não estou olhando para os internos, mas tenho certeza de que array_key_existsé O (N) porque itera sobre todas as chaves da matriz, enquantoisset tenta acessar o elemento usando o mesmo algoritmo de hash usado quando você acessa um índice de matriz. Isso deve ser O (1).

Um "truque" a ser observado é o seguinte:

$search_array = array('first' => null, 'second' => 4);

// returns false
isset($search_array['first']);

// returns true
array_key_exists('first', $search_array);

Fiquei curioso, por isso comparei a diferença:

<?php

$bigArray = range(1,100000);

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    isset($bigArray[50000]);
}

echo 'is_set:', microtime(true) - $start, ' seconds', '<br>';

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    array_key_exists(50000, $bigArray);
}

echo 'array_key_exists:', microtime(true) - $start, ' seconds';
?>

is_set:0.132308959961 segundos
array_key_exists:2.33202195168 segundos

Obviamente, isso não mostra a complexidade do tempo, mas mostra como as duas funções se comparam.

Para testar a complexidade do tempo, compare a quantidade de tempo necessária para executar uma dessas funções na primeira e na última chave.

ryeguy
fonte
9
Isto está errado. Estou 100% certo de que array_key_exists não precisa repetir cada chave. Se você não acredita, dê uma olhada no link abaixo. O motivo pelo qual o isset é muito mais rápido é que é uma construção de linguagem. O que significa que ele não tem a sobrecarga de fazer uma chamada de função. Além disso, acho que pode estar armazenando em cache a pesquisa, por causa disso. Além disso, esta não é uma resposta para a PERGUNTA! Eu gostaria de uma lista de Big (O) para funções PHP (como a pergunta indica). Nem uma única referência dos meus exemplos. svn.php.net/repository/php/php-src/branches/PHP_5_3/ext/...
Kendall Hopkins
Se você ainda não acredita em mim, criei uma pequena referência para demonstrar o ponto. pastebin.com/BdKpNvkE
Kendall Hopkins
O que há de errado com o seu benchmark é que você precisa desativar o xdebug. =)
Guilherme Blanco
3
Há dois motivos críticos pelos quais você deseja usar o isset sobre array_key_exists. Primeiro, isset é uma construção de linguagem que reduz o custo de uma chamada de função. Isso é semelhante ao argumento $arrray[] = $appendvs. array_push($array, $append)Segundo, array_key_exists também diferencia entre valores não definidos e nulos. Para$a = array('fred' => null); array_key_exists('fred', $a) retornará verdadeiro, enquanto isset($['fred'])retornará falso. Esta etapa extra não é trivial e aumentará bastante o tempo de execução.
orca 29/01
0

Se as pessoas estivessem enfrentando problemas na prática com colisões importantes, implementariam contêineres com uma pesquisa secundária de hash ou uma árvore equilibrada. A árvore balanceada daria O (log n) ao pior caso e O (1) avg. case (o próprio hash). A sobrecarga não vale a pena na maioria das aplicações práticas em memória, mas talvez haja bancos de dados que implementem essa forma de estratégia mista como seu caso padrão.

Josh Stern
fonte