Aprofundando a resposta do @Maniero, na questão de complexidade.
Complexidade assintótica é muita coisa, mas não é tudo. Complexidade assintótica depende de variáveis, ela é anotada de acordo com a entrada. Então, esse valor pode ser "falsificado" dependendo de como você pega essa variável.
Peguemos o seguinte laço, que lê as propriedades de um cubo:
elementos = d*d*d;
for (i = 0; i < elementos; i++) {
x = i % d;
y = (i/d)%d;
z = (i/d)/d;
imprime(cubo[x][y][z]);
}
Então o seu algoritmo roda em tempo linear, correto? Bem, roda linear sobre a variável elementos
, mas como você recebe um cubo, é muito mais provável que sua preocupação seja com d^3
.
Aqui, um algoritmo que seja quadrático na quantidade de elementos (como um algoritmo ordenação mais simples) tornaria a vida do programa que percorre o cubo de dados muito mais complicado.
O que aconteceu aqui foi que a complexidade foi "falsificada" para se assemelhar a ser linear. Algumas pessoas acabam fazendo coisas semelhantes para reduzir a "complexidade aparente" da operação.
No caso, o @Maniero demonstrou na resposta que, para cada elemento percorrido, você faz o(1)
operações. Isso significa que, no conjunto de elementos de tamanho n
é um algoritmo linear. Porém, analisando sob a perspectiva de dados armazenados num cubo de informação, o tamanho n
é o(d^3)
.
Para se ter uma ideia de como olhar para a variável distinta afeta a complexidade, olha esse exemplo:
some dois números (base arbitrária), N
e M
, cada um com n
dígitos
A soma tem complexidade o(n)
, mas também o(log N)
. ( Fonte: https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations )
Como aqui o número de dígitos para representar um número é o logaritmo desse número na base sendo representada, isso deve ser levada em consideração. Fica muito mais sincero e visível você falar que o custo da soma é linear na quantidade de dígitos.
Você pode obter ganhos consideráveis usando a localidade espacial. Não sei como foi implementado essa sua matriz, mas se ela foi implementada como um jagged array (um vetor, que por sua vez cada elemento contém um vetor, este último contendo cada elemento um vetor de números, cada um com seu tamanho individual), é de se esperar que esses dados não estão contíguos. Se não estão contíguos, então eles podem estar espalhados na memória de memória aleatória, e isso não é bom.
Por que não é bom? Porque você terá uma garantia menor do uso da localidade espacial das suas variáveis. Como uma otimização do processador que usa caches em diversos níveis, normalmente são carregadas para o cache as últimas variáveis usadas (localidade temporal) e suas vizinhas (localidade espacial), já que é muito provável usar uma região de memória próxima. E o que possivelmente eu não tenho com jagged arrays? Regiões de memória próximas entre os dados.
Para tentar ter um ganho significativo em relação a isso, poderíamos iterar na matriz da seguinte forma:
for ($i=0; $i < 10; $i++) {
for ($j=0; $j < 20; $j++) {
for ($p=0; $p < 40; $p++) {
echo $vaar[$i*20*40 + $j*40 + $p];
}
}
}
Ou então:
for ($i=0; $i < 10*20*50; $i++) {
echo $vaar[$i];
}
Nesse caso aqui, linearizamos a matriz. Assintoticamente essa iteração continua sendo cúbica, pois é impossível algo mais rápido que percorra todos os elementos de um cubo. Porém, agora, estamos lidando com dados consecutivos, dados que estarão contíguos na memória.
Como os dados estão contíguos, ao carregar para a cache L1 o vetor na posição, digamos, 10, o processador pode colocar logo na cache os valores do vetor entre 5 e 14 (inclusive). Assim, a quantidade de acessos à memória principal diminui. Com menos acessos à memória principal, rodamos mais rápido. Sem falar que a quantidade de desreferenciamento é menor.
Em um jagged array, cada olhada no índice da matriz é um desreferenciamento, e desreferenciamento é carregar a variável para a memória e pedir para o processador carregar a região apontada por ela.
Por exemplo, para fazer $vaar[$i][$j][$p]
:
- pegue o endereço apontado por
$vaar
(carregar variável em memória)
- pegue o valor
$i
(carregar variável em memória)
- adicione
$i
casas a $vaar
- carregue o valor em memória obtido na soma
(desreferenciamento de endereço)
- pegue o valor
$j
(carregar variável em memória)
- adicione
$j
casas à variável carregada da memória anteriormente
- carregue o valor em memória pelo endereço obtido por essa nova soma
(desreferenciamento de endereço)
- pegue
$p
(carregar variável em memória)
- adicionar
$p
casas à variável carregada da memória
- carregue o valor em memória obtido pelo endereço obtido nessa nova soma
(desreferenciamento de endereço)
Como as variáveis estão no mesmo contexto, temos que é muito provável que, por localidade temporal, carregar essas variáveis não envolva acessar a memória principal. Mesmo assim, para cada $i
ou j
diferente, será necessário carregar o novo vetor de vetor que está sendo referenciado. É provável que eles estejam espalhadas na memória.
Compre com a iteração mais simples da linearização da matriz: $vaar[$i]
- pegue o endereço apontado por
$vaar
(carregar variável em memória)
- pegue o valor
$i
(carregar variável em memória)
- adicione
$i
casas a $vaar
- carregue o valor em memória obtido na soma
(desreferenciamento de endereço)
Pronto, com apenas um único desreferenciamento, a variável está carregada em memória agora. E como estamos lidando com uma informação contígua, o próximo número estará próximo e portanto operável rapidamente.
Se for fazer algo do tipo, lembre-se de que:
- para acessar a posição
$i,$j,$p
do cubo, faça a seguinte conta: $vaar[$i*20*40 + $j*40 + $p];
- sua equipe de manutenção terá facilidade de ler esse código?
- caso não, talvez o ganho de performance não compense a nova possível "ilegibilidade" do código
for
mesmo, não tem outro jeito.