Considere uma matriz M[R][C] de registros armazenada em memória no formato row-major. Em um algoritmo que…

Questão

Considere uma matriz M[R][C] de registros armazenada em memória no formato row-major. Em um algoritmo que percorre M com laços aninhados, qual ordem de iteração (linha externa, coluna interna OU coluna externa, linha interna) oferece melhor localidade de dados e por quê?

1. A) Utilizar um laço único que percorre todos os elementos.
2. B) Iterar aleatoriamente por linhas e colunas.
3. C) Laço externo sobre linhas e laço interno sobre colunas (iterar por linha, depois por coluna) para aproveitar a localidade em row-major.
4. D) Devemos percorrer a matriz na ordem inversa (C[0][0] -> C[R-1][C-1]).
5. E) Laço interno sobre linhas e externo sobre colunas.

✅ Resposta correta: alternativa C

Resolução passo a passo

1. Em row-major, os elementos de uma mesma linha ficam em posições consecutivas da memória. Assim, a matriz M[R][C] é guardada como M[0][0], M[0][1], ..., M[0][C-1], depois M[1][0], e assim por diante.
2. Para aproveitar a localidade espacial (o cache carrega blocos contíguos de memória), o acesso sucessivo deve seguir essa mesma ordem. Isso significa que o laço externo percorre as linhas e o laço interno percorre as colunas, como descrito na alternativa C.
3. Com essa ordem, cada bloco trazido para o cache é totalmente usado antes de ser substituído, reduzindo falhas de cache (cache misses).
4. A alternativa A está errada, pois um laço único não define a ordem de acesso às posições de uma matriz bidimensional e não resolve o problema de localidade por si só; além disso, a questão pergunta sobre laços aninhados.
5. A alternativa B está errada, pois acessos aleatórios destroem a localidade espacial, em vez de melhorá-la.
6. A alternativa D está errada, pois a ordem inversa ainda percorre a matriz de forma contígua apenas no sentido decrescente; a questão compara linha externa com coluna interna, e a ordem inversa não é a resposta pedida pelo enunciado.
7. A alternativa E está errada, pois colocar as linhas no laço interno faz o acesso saltar de C em C posições na memória, o que piora a localidade.
8. Conclusão: a resposta correta é a C, que coincide com o gabarito oficial.

💡 Dica: Considere a estrutura de armazenamento da matriz ao responder.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Ao implementar um algoritmo que percorre uma matriz de registros 'dados' armazenada em memória row-major, qual ordem de…
• Dada uma matriz de registros M com R linhas e C colunas (indexação base 0), qual fórmula calcula o índice linear do…
• Como uma estrutura de dados como uma matriz pode otimizar um programa?
• Um algoritmo aninhado percorre uma matriz M de tamanho n×n com dois loops: para i de 1 até n e para j de 1 até n. Se a…
• Projete um algoritmo em pseudocódigo que, dada uma matriz M com m linhas e n colunas de inteiros, determine quantos…
• Em um algoritmo que percorre uma matriz de registros 'matrizDados' usando variáveis índice i e j para acessar elementos…

Todas as questões de Matrizes e registros