O enigma que motiva a aula
Computar é acessar memória: toda instrução lê operandos, escreve resultados, e a própria instrução é lida da memória. Um programa em execução é uma sequência de endereços visitados.
| Operação | Tempo típico |
|---|---|
| Ciclo da CPU | \(\approx 0{,}3\) ns |
| Acesso à memória RAM | \(\approx 80\) ns |
Se cada acesso fosse à RAM, a CPU esperaria \(\approx 250\) ciclos por acesso e os programas seriam dezenas de vezes mais lentos. Não são porque não acessam a memória de forma aleatória. O nome dessa regularidade é localidade de referência, e o hardware inteiro é projetado em torno dela.
Mapa de acesso à memória
Gráfico em que cada ponto é um acesso: eixo \(X\) é o tempo, eixo \(Y\) é o endereço. Três palavras leem qualquer mapa:
- Conjunto de localidade — endereços acessados num curto intervalo; no mapa, faixas horizontais.
- Fase — intervalo em que o conjunto não muda; as mesmas faixas persistem.
- Transição — mudança abrupta do conjunto; as faixas “pulam”.
Faixa horizontal é reuso dos mesmos endereços; diagonal é percurso sequencial por vizinhos. O mapa nunca é aleatório, e são essas duas formas que o hardware explora.
Formalmente (Denning, 2005), um programa distribui suas referências de forma não uniforme, muda lentamente a frequência de cada região, e exibe alta correlação entre passado e futuro imediatos. A causa é banal: laços revisitam o mesmo código e as mesmas variáveis, funções concentram a ação nos seus locais, vetores são percorridos em ordem.
Localidade temporal e espacial
Temporal: acessar uma posição aumenta a probabilidade de acessá-la de novo em breve. Palavra-chave: reuso.
Espacial: acessar uma posição aumenta a probabilidade de acessar posições próximas em seguida. Palavra-chave: vizinhança.
Num enunciado só: um acesso a \(X\) no tempo \(T\) torna mais provável um acesso a \(X+dX\) em \(T+dT\) conforme \(dX\to0\) e \(dT\to0\). Com \(dX=0\) é a temporal; com \(dX\) pequeno, a espacial.
soma = 0;for (i = 0; i < n; i++)soma += v[i];
Temporal: soma e i são lidas e escritas a cada iteração, e o mesmo código roda \(n\) vezes. Espacial: depois de v[0] vem v[1], endereços contíguos, e a próxima instrução está no endereço seguinte.
No mapa, a temporal é uma faixa horizontal — um laço; a espacial é uma diagonal — um vetor sendo percorrido.
Conjunto de trabalho
\(W(t,T)\) é o conjunto de endereços acessados na janela de duração \(T\) que termina em \(t\) — o que o programa está usando agora. E \(|W(t,T)|\) diz quanta memória rápida ele precisa.
| \(t\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| acesso | a | b | a | c | b | a | d | d | a | e |
\(t=4\): os 4 últimos são \(a,b,a,c\), 3 distintos \(\Rightarrow W(4,4)=\{a,b,c\}\).
\(t=7\): \(c,b,a,d\) \(\Rightarrow W(7,4)=\{a,b,c,d\}\); cresceu.
\(t=10\): \(d,d,a,e\) \(\Rightarrow W(10,4)=\{a,d,e\}\); \(b\) e \(c\) saíram — transição.
4 posições de memória rápida bastariam para esse programa.
Hierarquia, blocos e LRU
Em cima, memória pequena, rápida e cara (registradores, caches L1/L2/L3); embaixo, grande, lenta e barata (RAM, SSD, disco). Cada nível guarda uma cópia de parte do nível abaixo. Para escala: se 1 ciclo da CPU durasse 1 segundo, a L1 levaria alguns segundos, a RAM \(\approx4\) minutos e o disco \(\approx1\) ano.
- A memória é dividida em blocos de tamanho fixo — tipicamente 64 bytes.
- Um acesso traz o bloco inteiro: um acesso a
m[5]trazm[4..7], e om[6]seguinte é acerto;m[9]é falha e busca outro bloco. - Cache cheia, algum bloco é expulso — o menos recentemente usado (LRU).
- Cada falha desce um degrau — L1 \(\sim1\) ns, L2 \(\sim4\), L3 \(\sim15\), RAM \(\sim80\) — e o bloco que volta fica copiado em todos os níveis.
A cache guarda uma fração minúscula dos dados; se os acessos fossem uniformes, quase todo acesso erraria. Funciona porque a temporal mantém lá o que foi usado há pouco e a espacial traz os vizinhos de graça. Daí também o compromisso do tamanho de bloco: com os mesmos 16 KB, um bloco de 16 KB maximiza a espacial mas só cabe uma região; 16 blocos de 1 KB deixam 16 regiões coexistirem. Caches reais ficam no meio, com muitos blocos de 64 bytes.
Quanto custa, em média, um acesso
em que \(p\) é a taxa de falha.
| \(p\) | Conta | \(T_{\text{médio}}\) |
|---|---|---|
| 20% | \(1 + 0{,}20\times 80\) | 17 ns |
| 5% | \(1 + 0{,}05\times 80\) | 5 ns |
| 1% | \(1 + 0{,}01\times 80\) | 1,8 ns |
Cair de 5% para 1% quase triplica a velocidade efetiva da memória.
A taxa de falha depende da cache e do programa. A cache não muda; o programa, sim — por isso o resto da aula é sobre medir a localidade de um algoritmo.
Checkpoint: que localidade cada trecho tem?
// (a) for (i = 0; i < n; i++) s += v[i];// (b) for (i = 0; i < n; i++) s += v[rand() % n];// (c) while (p != NULL) p = p->prox;// (d) for (j = 0; j < n; j++)for (i = 0; i < n; i++) s += m[i][j];
| Trecho | Diagnóstico |
|---|---|
| (a) | espacial em v, temporal em s e i. Ótima. |
| (b) | índice aleatório: sem espacial; temporal só em s e i. |
| (c) | depende de onde os nós foram alocados: contíguos, bom; espalhados pelo heap, um salto por nó. |
| (d) | percorre por coluna: em C, a mesma coluna está a \(n\) posições de distância. Espacial ruim — é o caso da Parte 5. |
A pilha LRU e a definição
O mapa serve para ver; queremos quantificar. A pergunta, a cada acesso: há quanto tempo este endereço foi usado — não em segundos, mas em quantos outros endereços distintos passaram desde então.
Na pilha LRU, todo endereço acessado vai para o topo (removido de onde estava, se já lá). Ela fica sempre ordenada do mais recente ao menos recente.
A distância de pilha \(d(t)\) do acesso \(r(t)\) é o número de endereços distintos acessados desde o acesso anterior a \(r(t)\) — quantos estavam acima dele na pilha.
- \(d(t)={-}\): nunca acessado antes, falha compulsória;
- \(d(t)=0\): o mesmo endereço do acesso anterior;
- \(d(t)\) grande: muita coisa passou desde a última vez.
Exemplo: 5 endereços, 12 acessos
| \(t\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(r(t)\) | 1 | 2 | 3 | 4 | 1 | 2 | 5 | 1 | 2 | 3 | 4 | 5 |
| \(d(t)\) | – | – | – | – | 3 | 3 | – | 2 | 2 | 4 | 4 | 4 |
Em \(t=5\), desde o 1 de \(t=1\) passaram 2, 3 e 4 \(\Rightarrow d=3\). Em \(t=10\), o 3 estava na base com 4 acima \(\Rightarrow d=4\).
Contando quantos acessos tiveram cada distância — \(c(2)=2\), \(c(3)=2\), \(c(4)=3\) e 5 primeiros acessos — sai a distância total:
$$DP=\sum_k k\cdot c(k) = 2\cdot 2 + 3\cdot 2 + 4\cdot 3 = 22$$Primeiros acessos não entram: não há reuso a medir.
O histograma de \(c(k)\) é a assinatura do algoritmo: massa à esquerda é reuso rápido, poucas falhas mesmo com cache pequena; massa à direita é falha garantida.
A regra de ouro
Em cache LRU de \(C\) posições, o acesso \(r(t)\) é acerto se e somente se \(d(t)<C\) — havia \(d(t)\) distintos mais recentes que ele, e a cache guarda \(C\). As falhas são os primeiros acessos mais os de \(d\ge C\).
| \(C\) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| falhas | 12 | 12 | 10 | 8 | 5 |
| acertos | 0 | 0 | 2 | 4 | 7 |
Uma única passada prevê as falhas para todos os tamanhos de cache.
Isso vale pela propriedade de inclusão: os primeiros \(m\) elementos da pilha LRU são exatamente o conteúdo de uma cache de tamanho \(m\), e são sempre um subconjunto dos primeiros \(m+1\). Consequência: com LRU, cache maior nunca tem mais falhas que cache menor — o que não vale para qualquer política. Algoritmos assim se chamam algoritmos de pilha (Mattson et al., 1970).
Os três tipos de falha
| Tipo | Quando ocorre | No modelo |
|---|---|---|
| Compulsória | primeiro acesso ao bloco | \(d={-}\) |
| Capacidade | o bloco esteve na cache, mas muitos outros passaram e ele foi expulso | \(d \ge C\) |
| Conflito | havia espaço, mas a regra de mapeamento forçou a expulsão | fora do modelo LRU ideal |
A distância de pilha captura as compulsórias e as de capacidade — as que dependem do algoritmo. As de conflito dependem do hardware e ficam fora da disciplina. Daí a alavanca da aula: reduzir falhas de capacidade é reduzir distâncias de pilha, que é melhorar a localidade do algoritmo.
Sua vez: calcule
Sequência de acessos: \(a, b, a, c, b, a\).
| Pergunta | Resposta |
|---|---|
| Distância de cada acesso | \(d = -,\,-,\,1,\,-,\,2,\,2\) |
| Distância total | \(DP = 1+2+2 = 5\) |
| Acertos com \(C=2\) | só \(t=3\) (\(d=1<2\)): 1 em 6 |
| Acertos com \(C=3\) | \(t=3,5,6\): 3 em 6 |
Conferindo \(t=5\): desde o \(b\) de \(t=2\) passaram \(a\) e \(c\) — 2 distintos.
O problema e os dados
Uma empresa está em dúvida entre páginas de 2 ou de 3 registros. Com base numa carga de trabalho, dizer qual dá menor custo de acesso à memória secundária.
| Dado | Valor |
|---|---|
| Custo de trazer uma página | 1 ms de latência \(+\) 0,5 ms por registro |
| Página de 2 / de 3 registros | 2 ms / 2,5 ms |
| Registro cuja página já está em memória | custo 0 |
| Registros | 12, numerados de 1 a 12, distribuídos em ordem |
| Memória principal | 6 registros — 3 páginas de 2, ou 2 páginas de 3 |
| Substituição | LRU |
Carga de trabalho, 22 acessos — primeira linha \(t=1\) a \(11\), segunda \(t=12\) a \(22\):
$$1,\,3,\,4,\,5,\,7,\,9,\,11,\,12,\,2,\,3,\,4$$ $$7,\,8,\,9,\,10,\,11,\,12,\,7,\,8,\,10,\,11,\,12$$Páginas de 2 registros
| página | a | b | c | d | e | f |
|---|---|---|---|---|---|---|
| registros | 1, 2 | 3, 4 | 5, 6 | 7, 8 | 9, 10 | 11, 12 |
| \(t\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| registro | 1 | 3 | 4 | 5 | 7 | 9 | 11 | 12 | 2 | 3 | 4 |
| página | a | b | b | c | d | e | f | f | a | b | b |
| \(d\) | – | – | 0 | – | – | – | – | 0 | 5 | 5 | 0 |
| \(t\) | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| registro | 7 | 8 | 9 | 10 | 11 | 12 | 7 | 8 | 10 | 11 | 12 |
| página | d | d | e | e | f | f | d | d | e | f | f |
| \(d\) | 4 | 0 | 4 | 0 | 4 | 0 | 2 | 0 | 2 | 2 | 0 |
| \(d\) | 0 | 2 | 4 | 5 | – |
|---|---|---|---|---|---|
| quantos | 8 | 3 | 3 | 2 | 6 |
| \(C=3\) | acerto | acerto | falha | falha | falha |
\(DP = 2\cdot3 + 4\cdot3 + 5\cdot2 = 28\). Acertos: \(8+3=11\). Falhas: \(3+2+6=11\).
$$11 \text{ falhas} \times 2\text{ ms} = 22\text{ ms}$$Páginas de 3 registros
| página | a | b | c | d |
|---|---|---|---|---|
| registros | 1, 2, 3 | 4, 5, 6 | 7, 8, 9 | 10, 11, 12 |
Cabem menos páginas e cada falha custa 2,5 ms — mas cada página traz mais vizinhos.
| \(t\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| registro | 1 | 3 | 4 | 5 | 7 | 9 | 11 | 12 | 2 | 3 | 4 |
| página | a | a | b | b | c | c | d | d | a | a | b |
| \(d\) | – | 0 | – | 0 | – | 0 | – | 0 | 3 | 0 | 3 |
| \(t\) | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| registro | 7 | 8 | 9 | 10 | 11 | 12 | 7 | 8 | 10 | 11 | 12 |
| página | c | c | c | d | d | d | c | c | d | d | d |
| \(d\) | 3 | 0 | 0 | 3 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
Repare em quantos zeros a mais apareceram.
| \(d\) | 0 | 1 | 3 | – |
|---|---|---|---|---|
| quantos | 12 | 2 | 4 | 4 |
| \(C=2\) | acerto | acerto | falha | falha |
\(DP = 1\cdot2 + 3\cdot4 = 14\). Acertos: \(12+2=14\). Falhas: \(4+4=8\).
$$8 \text{ falhas} \times 2{,}5\text{ ms} = 20\text{ ms}$$A recomendação
| páginas de 2 | páginas de 3 | |
|---|---|---|
| páginas em memória | 3 | 2 |
| custo por falha | 2 ms | 2,5 ms |
| acertos / falhas | 11 / 11 | 14 / 8 |
| distância de pilha total | 28 | 14 |
| custo total | 22 ms | 20 ms |
Páginas de 3 registros — 20 ms contra 22 ms, apesar de cada falha ser mais cara e de caberem menos páginas.
As três ferramentas
| Ferramenta | Responde | Procure por |
|---|---|---|
| Mapa de acesso | qual é o padrão? | diagonais, faixas, saltos |
| Histograma de DP | quão boa é a localidade? | massa à esquerda × à direita |
| Evolução da DP | quando piora? | rajadas, platôs, tendências |
O método é sempre o mesmo: prever o padrão lendo o código, conferir, reescrever, conferir de novo. Os números daqui em diante vêm da instrumentação de programas reais, em instâncias pequenas — o que importa é o padrão, que se mantém em escala.
Como a matriz vive na memória
As linhas ficam uma após a outra: o endereço de \(A[i][j]\) é \(i\cdot N + j\). Vizinhos na mesma linha são vizinhos na memória; na mesma coluna, estão a \(N\) posições.
| 0 | 1 | 2 | 3 |
| 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 |
A linha 1 é 4, 5, 6, 7 — passo 1. A coluna 2 é 2, 6, 10, 14 — passo \(N=4\). Um bloco de 64 bytes cabe 8 double: por linha ele atende 8 acessos; por coluna, cada acesso cai em outro bloco e o resto é desperdiçado.
O laço ingênuo ijk
O produto \(C[i][j]=\sum_k A[i][k]\cdot B[k][j]\) custa \(\Theta(N^3)\) qualquer que seja a ordem dos laços — mas a ordem muda toda a sequência de endereços.
for (i = 0; i < N; i++)for (j = 0; j < N; j++)for (k = 0; k < N; k++)C[i][j] += A[i][k] * B[k][j];
| Acesso | Passo na memória | Localidade | DP média |
|---|---|---|---|
| \(A[i][k]\) | 1 — a linha \(i\) | espacial boa | 5,60 |
| \(B[k][j]\) | \(N\) — a coluna \(j\) | espacial ruim | 12,35 |
| \(C[i][j]\) | 0 — sempre o mesmo | temporal ótima | — |
Em \(A\) a maioria dos acessos tem \(d=4\) (reuso da linha a cada \(j\)); em \(B\), \(d=16\) — todos os outros elementos passaram antes do reuso, o tempo todo. O alvo da reescrita é \(B\).
Troca de laços e azulejamento
for (i = 0; i < N; i++)for (k = 0; k < N; k++) {a = A[i][k]; // fixo, em registradorfor (j = 0; j < N; j++)C[i][j] += a * B[k][j];}
Com \(j\) no laço interno, \(B[k][j]\) e \(C[i][j]\) percorrem linhas, passo 1: nenhum acesso com passo \(N\). Sem mudar uma conta, a ikj é várias vezes mais rápida que a ijk para \(N\) grande.
Dividir as matrizes em blocos \(B_s\times B_s\) e multiplicar bloco por bloco, acumulando no bloco de \(C\). Enquanto se trabalha num par de blocos, só eles precisam estar na cache — e são reutilizados \(B_s\) vezes. Escolhe-se \(B_s\) para que três blocos caibam em L1:
$$3\cdot B_s^{2}\cdot 8 \text{ bytes} \le \text{tamanho de L1}$$Na prática, três laços externos avançam de BLK_SZ em BLK_SZ escolhendo os blocos, e os três internos fazem a multiplicação pequena dentro deles.
A DP média de \(B\) cai de 12,35 para 7,65 (\(-38\%\)): a massa em \(d=16\) cai de 55 para 24 acessos e surge um pico em \(d=4\), o reuso dentro do bloco. A de \(A\) vai de 5,60 a 5,50 — já era boa.
Quicksort, heapsort e inserção
Na teoria o heapsort é \(O(N\log N)\) garantido e o quicksort pode degradar para \(O(N^2)\). Na prática o quicksort é 2 a 3 vezes mais rápido, e o motivo é como cada um caminha pelo vetor:
| Algoritmo | Como caminha | acessos | DP total |
|---|---|---|---|
| quicksort | “V”s — os dois ponteiros da partição convergem com passo 1, e a recursão trabalha em sub-vetores contíguos | 448 | 3056 |
| heapsort | leque — o sift-down visita \(2i\), \(4i\)…, cada salto o dobro do anterior, e o heap é refeito \(N\) vezes | 768 | 4735 |
| inserção | faixa — desliza vizinhos, puramente sequencial, mas \(O(N^2)\) | 512 | 4255 |
| quick + inserção | “V”s grandes + faixa: quicksort até a partição ficar pequena, inserção termina (Sedgewick) | 335 | 2752 |
Para \(N=10^6\), o último salto de um sift-down é de \(\approx500\,000\) posições — uma falha por nível. No quicksort, o prefetcher reconhece o passo 1 e carrega os blocos antes de serem pedidos. O híbrido corta 25% dos acessos porque as partições pequenas deixam de gerar chamadas recursivas.
E o merge sort?
| Pergunta | Resposta |
|---|---|
| Como a intercalação percorre os dois sub-vetores? | sequencialmente, passo 1 em cada |
| E o vetor auxiliar? | escrito sequencialmente |
| Onde está o custo escondido? | \(N\) posições extras — o conjunto de trabalho dobra |
| Como seria o mapa de acesso? | três diagonais paralelas por nível; \(\log N\) níveis |
Boa localidade espacial, conjunto de trabalho maior — por isso ele brilha em memória externa, onde o sequencial é tudo.
Grafos: lista de adjacência × CSR
Grafos reais são irregulares, e BFS, DFS, Dijkstra e PageRank passam a maior parte do tempo esperando memória. Na lista de adjacência, cada vizinho é um nó alocado onde houver espaço no heap: cada salto é imprevisível e, pior, o endereço do próximo só é conhecido depois de ler o atual — as falhas são serializadas. Para \(10^6\) arestas, \(\approx80\) ms só esperando.
Todos os vizinhos de todos os vértices num único vetor contíguo viz, ordenados por vértice, e um vetor offset com \(n+1\) posições dizendo onde começa cada lista. Os vizinhos de \(v\) são viz[offset[v]] até viz[offset[v+1] - 1]. Nenhum ponteiro, nenhum malloc por aresta.
Vizinhos: \(0\to\) 1,2 · \(1\to\) 0,2,3 · \(2\to\) 0,1,4 · \(3\to\) 1,4 · \(4\to\) 2,3.
| posição | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
viz | 1 | 2 | 0 | 2 | 3 | 0 | 1 | 4 | 1 | 4 | 2 | 3 |
| \(v\) | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
offset | 0 | 2 | 5 | 8 | 10 | 12 |
Vizinhos de 0 nas posições 0–1, então offset[0]=0; os de 1 nas posições 2–4, então offset[1]=2. A sentinela offset[5]=12 é o total. Conferindo \(v=2\): viz[5..7] \(=0,1,4\).
Percorrer é um for de offset[v] a offset[v+1]-1: tudo lado a lado, o prefetcher antecipa. Num grafo de 100 000 vértices, visitar todos os vizinhos leva 0,036 s com lista e 0,010 s com CSR — \(3{,}52\times\).
viz e atualizar offset: \(O(m)\), contra \(O(1)\) da lista. O CSR é estático. A regra prática: construir com a estrutura flexível e converter para CSR antes da fase de consultas pesadas.Padrões e o desempate
| Padrão | O bom | O ruim |
|---|---|---|
| Vetor × lista encadeada | vetor: \(\approx n/8\) falhas | lista: \(\approx n\) falhas — mesma classe, uma ordem de grandeza de diferença |
| Ordem dos laços | por linha, passo 1 | por coluna, passo \(n\) — até \(10\times\) mais lento |
| AoS × SoA | SoA: 8 valores de x por bloco, todos usados | AoS: 1 campo em 4 usado — 75% da banda desperdiçada |
- Percorra em ordem. Passo 1 é o padrão que o hardware ama.
- Reuse enquanto está quente. Todo o trabalho com um dado antes de passar ao próximo.
- Compacte. Estrutura menor \(=\) mais dados por bloco \(=\) conjunto de trabalho menor.
- Prefira vetores a ponteiros no que é percorrido com frequência.
- Meça. A intuição erra; a medição não.
Nenhuma muda a complexidade assintótica. Todas mudam o tempo real.
É o desempate que faltava à A2: a análise assintótica escolhe a classe, a de localidade escolhe dentro da classe. Um \(\Theta(n^2)\) com ótima localidade pode vencer um \(\Theta(n\log n)\) com localidade péssima — até certo \(n\). Depois, a assintótica sempre ganha.
Checklist da A5
Se você consegue responder tudo abaixo sem consultar, a aula está fechada.
| Pergunta | Onde está |
|---|---|
| Distinguir localidade temporal de espacial num trecho de código | Checkpoint: quatro trechos |
| Calcular \(W(t,T)\) para uma sequência e apontar a transição | Conjunto de trabalho |
| Calcular o tempo médio de acesso a partir da taxa de falha | Quanto custa um acesso |
| Calcular a distância de pilha de cada acesso e a distância total | Exemplo: 12 acessos |
| Contar acertos e falhas para um dado \(C\) pela regra \(d<C\) | A regra de ouro |
| Classificar uma falha em compulsória, de capacidade ou de conflito | Os três tipos de falha |
| Escolher o tamanho de página: mapear, medir, contar, somar o custo | Parte 4 inteira |
| Dizer qual matriz tem localidade ruim em \(C=A\times B\) e por quê | O laço ingênuo ijk |
| Explicar o que a troca de laços e o azulejamento corrigem, cada um | Troca de laços e azulejamento |
| Justificar por que o quicksort bate o heapsort na prática | Quicksort, heapsort e inserção |
Montar offset e viz do CSR de um grafo dado | Lista de adjacência × CSR |