Matrix

Categoria: Linear

O problema

O T[][] nativo do Java não é de fato uma única estrutura 2D — é um array de referências para arrays de linha alocados de forma independente. Nada garante que essas linhas fiquem lado a lado na memória, cada linha é seu próprio objeto no heap com seu próprio cabeçalho, e nada impede que as linhas tenham tamanhos diferentes (um array "jagged"/irregular), o que às vezes é desejado, mas muitas vezes é só uma pegadinha quando o que se precisa de verdade é uma grade de formato fixo, com layout de memória e custo de acesso previsíveis.

A solução

Apoie a grade inteira em um único array 1D plano, e calcule o índice plano de (row, col) com aritmética row-major: index = row * cols + col. Essa única alocação garante que a matriz inteira seja um bloco contíguo de memória, o que transforma get/set em aritmética direta — e, igualmente importante, torna a ordem do percurso um custo real e mensurável: percorrer o array na mesma ordem em que ele está disposto (row-major) permanece favorável ao cache, enquanto percorrê-lo na ordem "errada" (column-major, pulando cols posições a cada passo) não é, mesmo que ambos visitem exatamente as mesmas células, exatamente o mesmo número de vezes.

flowchart LR
    subgraph "logical grid (2 rows x 3 cols)"
        direction LR
        A00["(0,0)"] --- A01["(0,1)"] --- A02["(0,2)"]
        A10["(1,0)"] --- A11["(1,1)"] --- A12["(1,2)"]
    end
    subgraph "flat backing array, row-major"
        direction LR
        F0["[0]=(0,0)"] --- F1["[1]=(0,1)"] --- F2["[2]=(0,2)"] --- F3["[3]=(1,0)"] --- F4["[4]=(1,1)"] --- F5["[5]=(1,2)"]
    end

Exemplo clássico

classic/Matrix é apoiado por um único Object[] de tamanho rows * cols — sem T[][] do Java. get/set calculam o índice plano com a mesma fórmula row-major, e ambos verificam limites de linha e coluna de forma independente antes de tocar o array. MatrixTest cobre o ciclo completo de get/set, que as células permanecem independentes entre linhas e colunas (a verificação direta de que a aritmética de índice não está acidentalmente transposta ou se sobrepondo), toda combinação de linha/coluna fora dos limites tanto para get quanto para set, e as duas proteções do construtor contra dimensões não positivas.

Exemplo aplicado: grade de tarifação de prêmio de seguro

applied/PremiumRatingGrid modela uma tabela atuarial de tarifação exatamente no formato em que ela já é publicada: as linhas são faixas etárias, as colunas são zonas de risco, e cada célula guarda o multiplicador de taxa que a subscrição aplica para aquela combinação. Resolver o multiplicador de uma cotação vira então uma única busca indexada O(1) — multiplierFor(ageBracket, riskZone) — em vez de uma cadeia de verificações de intervalo ou uma lista de regras varrida linearmente. Consultar uma célula que nunca foi registrada falha de forma escancarada (IllegalStateException) em vez de silenciosamente retornar um multiplicador padrão que poderia subprecificar uma apólice. PremiumRatingGridTest cobre o ciclo completo de um multiplicador, independência entre células, o caso de falha de célula não definida, um multiplicador não positivo rejeitado, e uma busca fora do intervalo propagando a verificação de limites subjacente.

Benchmark

./gradlew :linear:matrix:jmh

Execução real nesta máquina (JMH 1.37, JDK 26.0.2, 2 iterações de aquecimento + 3 de medição, 1 fork). Percurso completo (soma de todas as células) de uma matriz quadrada, em ordem row-major (mesma ordem de armazenamento do array subjacente) vs. ordem column-major (mesma quantidade de elementos, pulando dimension posições a cada passo):

Mesma quantidade de elementos, mesma operação, as duas ordens — a diferença é puramente um efeito do padrão de acesso à memória. No menor tamanho (10 mil células, pequeno o suficiente para caber confortavelmente no cache independentemente da ordem), column-major é só ~1,8x mais lento. Essa diferença se abre bruscamente conforme a matriz cresce: ~5,1x mais lento em 250 mil células, ~15,7x mais lento em 1 milhão de células — exatamente o formato que um efeito de localidade de cache produz assim que o working set deixa de caber no cache e os saltos de dimension posições do column-major começam a errar linhas de cache que a varredura sequencial do row-major nunca erra. O intervalo de confiança em dimension=500 é largo (ruído de JVM/GC na casa de milissegundos de um único dígito nessa contagem de iterações) — a tendência de abertura ao longo dos três tamanhos é o sinal confiável aqui, não qualquer número isolado.

Quando não usar

• Precisa de uma estrutura jagged/irregular em que as linhas têm tamanhos diferentes, ou precisa adicionar/remover linhas ou colunas depois de construída? Esta Matrix tem formato fixo por design — uma List<List<T>> (ou simplesmente uma nova Matrix com outro tamanho) se encaixa melhor para linhas de tamanho variável.
• O working set é pequeno o suficiente para sempre caber confortavelmente no cache independentemente da ordem de acesso? O benchmark acima mostra que a diferença row-vs-column é real, mas modesta até a matriz ultrapassar o cache — menos de 2x em dimension=100, não compensa reestruturar código por causa disso.
• Precisa de armazenamento genuinamente esparso — uma grade lógica enorme em que quase toda célula está vazia? Esta Matrix aloca todas as células antecipadamente (rows * cols posições), independentemente de quantas realmente estão definidas. Uma representação esparsa (por exemplo, uma hash table indexada por (row, col)) troca o acesso denso O(1) desta Matrix por memória proporcional ao número de células não vazias, em vez da grade inteira.

Cobertura de testes

100% de cobertura de instruções, 100% de cobertura de branches (JaCoCo). Reproduza você mesmo:

./gradlew :linear:matrix:jacocoTestReport

Relatório em linear/matrix/build/reports/jacoco/test/html/index.html.

Testes unitários

package com.datastructures.linear.matrix.classic;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class MatrixTest {

    @Test
    void reportsTheDimensionsItWasConstructedWith() {
        Matrix<String> matrix = new Matrix<>(3, 5);

        assertThat(matrix.rows()).isEqualTo(3);
        assertThat(matrix.cols()).isEqualTo(5);
    }

    @Test
    void everyCellStartsUnset() {
        Matrix<String> matrix = new Matrix<>(2, 2);

        assertThat(matrix.get(0, 0)).isNull();
        assertThat(matrix.get(1, 1)).isNull();
    }

    @Test
    void setThenGetReturnsTheStoredValue() {
        Matrix<String> matrix = new Matrix<>(2, 2);

        matrix.set(1, 0, "value");

        assertThat(matrix.get(1, 0)).isEqualTo("value");
    }

    @Test
    void setReturnsThePreviousValueAtThatCell() {
        Matrix<String> matrix = new Matrix<>(2, 2);
        matrix.set(0, 0, "original");

        String previous = matrix.set(0, 0, "replaced");

        assertThat(previous).isEqualTo("original");
        assertThat(matrix.get(0, 0)).isEqualTo("replaced");
    }

    @Test
    void cellsAreIndependentAcrossRowsAndColumns() {
        Matrix<Integer> matrix = new Matrix<>(3, 3);

        for (int row = 0; row < 3; row++) {
            for (int col = 0; col < 3; col++) {
                matrix.set(row, col, row * 10 + col);
            }
        }

        for (int row = 0; row < 3; row++) {
            for (int col = 0; col < 3; col++) {
                assertThat(matrix.get(row, col)).isEqualTo(row * 10 + col);
            }
        }
    }

    @Test
    void getRejectsAnOutOfBoundsRowOrColumn() {
        Matrix<String> matrix = new Matrix<>(2, 2);

        assertThatThrownBy(() -> matrix.get(-1, 0)).isInstanceOf(IndexOutOfBoundsException.class);
        assertThatThrownBy(() -> matrix.get(2, 0)).isInstanceOf(IndexOutOfBoundsException.class);
        assertThatThrownBy(() -> matrix.get(0, -1)).isInstanceOf(IndexOutOfBoundsException.class);
        assertThatThrownBy(() -> matrix.get(0, 2)).isInstanceOf(IndexOutOfBoundsException.class);
    }

    @Test
    void setRejectsAnOutOfBoundsRowOrColumn() {
        Matrix<String> matrix = new Matrix<>(2, 2);

        assertThatThrownBy(() -> matrix.set(-1, 0, "x")).isInstanceOf(IndexOutOfBoundsException.class);
        assertThatThrownBy(() -> matrix.set(0, 2, "x")).isInstanceOf(IndexOutOfBoundsException.class);
    }

    @Test
    void constructorRejectsNonPositiveRows() {
        assertThatThrownBy(() -> new Matrix<String>(0, 3)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> new Matrix<String>(-1, 3)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void constructorRejectsNonPositiveCols() {
        assertThatThrownBy(() -> new Matrix<String>(3, 0)).isInstanceOf(IllegalArgumentException.class);
    }
}

package com.datastructures.linear.matrix.applied;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class PremiumRatingGridTest {

    @Test
    void setMultiplierThenMultiplierForReturnsIt() {
        PremiumRatingGrid grid = new PremiumRatingGrid(3, 4);

        grid.setMultiplier(1, 2, 1.35);

        assertThat(grid.multiplierFor(1, 2)).isEqualTo(1.35);
    }

    @Test
    void differentCellsHoldIndependentMultipliers() {
        PremiumRatingGrid grid = new PremiumRatingGrid(2, 2);

        grid.setMultiplier(0, 0, 1.0);
        grid.setMultiplier(0, 1, 1.2);
        grid.setMultiplier(1, 0, 1.5);
        grid.setMultiplier(1, 1, 2.0);

        assertThat(grid.multiplierFor(0, 0)).isEqualTo(1.0);
        assertThat(grid.multiplierFor(0, 1)).isEqualTo(1.2);
        assertThat(grid.multiplierFor(1, 0)).isEqualTo(1.5);
        assertThat(grid.multiplierFor(1, 1)).isEqualTo(2.0);
    }

    @Test
    void multiplierForOnAnUnsetCellThrows() {
        PremiumRatingGrid grid = new PremiumRatingGrid(2, 2);

        assertThatThrownBy(() -> grid.multiplierFor(0, 0)).isInstanceOf(IllegalStateException.class);
    }

    @Test
    void setMultiplierRejectsAZeroOrNegativeMultiplier() {
        PremiumRatingGrid grid = new PremiumRatingGrid(2, 2);

        assertThatThrownBy(() -> grid.setMultiplier(0, 0, 0.0)).isInstanceOf(IllegalArgumentException.class);
        assertThatThrownBy(() -> grid.setMultiplier(0, 0, -1.0)).isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void multiplierForOnAnOutOfRangeCellPropagatesTheUnderlyingBoundsCheck() {
        PremiumRatingGrid grid = new PremiumRatingGrid(2, 2);

        assertThatThrownBy(() -> grid.multiplierFor(5, 0)).isInstanceOf(IndexOutOfBoundsException.class);
    }
}

Ver relatório completo de cobertura JaCoCo →