Especialização em Sistemas com Python & POO com Type Hints • Capítulo 06

🗺️ Mapa Conceitual do Tópico

flowchart TD
    subgraph MEM_MODEL["Arquitetura de Memória do CPython"]
        PYOBJ["Estrutura Base PyObject\nob_refcnt (Contador) · ob_type (Tipo)"]
        PYMALLOC["Alocador PyMalloc\nArenas (256KB) · Pools (4KB) · Blocos (8-512B)"]
        GC["Garbage Collector Híbrido\nReference Counting (Imediato) + Ciclos (Gerações 0, 1, 2)"]
    end

    subgraph SEQUENCES["Coleções Sequenciais Indexadas"]
        LIST["list[T]: Array Dinâmico de Ponteiros\nOver-allocation · append() O(1) · insert(0) O(N)"]
        TUPLE["tuple[T, ...]: Array Estático Imutável\nFree-lists do CPython · Hashable · Chave de Dict"]
        COPY["Semântica de Cópia\nShallow Copy (Fatiamento) vs Deep Copy (Recursivo)"]
    end

    subgraph MATRICES["Matrizes Multidimensionais (list[list[T]])"]
        GRID["Representação em Grade 2D\nlist comprehension aninhada vs Armadilha da Referência"]
        TRANSPOSE["Transposição Elegante via zip(*matriz)"]
    end

    PYOBJ --> SEQUENCES
    PYMALLOC --> LIST
    SEQUENCES --> MATRICES

    style MEM_MODEL fill:#ede7f6,stroke:#512da8,stroke-width:2px
    style SEQUENCES fill:#e1f5fe,stroke:#0288d1,stroke-width:2px
    style MATRICES fill:#e8f5e9,stroke:#2e7d32,stroke-width:2px

🧠 1. Gestão de Memória no CPython: PyObject e PyMalloc

Toda entidade manipulada pelo interpretador CPython é representada internamente como uma estrutura em linguagem C chamada PyObject (ou PyVarObject para coleções de tamanho variável).

Anatomia Interna do PyObject

// Representação simplificada do header nativo em CPython:
typedef struct _object {
    _PyObject_HEAD_EXTRA // Ponteiros de encadeamento duplo para auditoria
    Py_ssize_t ob_refcnt; // Contador de referências ativas (64 bits)
    struct _typeobject *ob_type; // Ponteiro para o tipo da classe
} PyObject;
  1. Contagem de Referências (Reference Counting): Toda atribuição (a = b), passagem como argumento ou inclusão em listas incrementa ob_refcnt. Quando uma variável sai de escopo ou é deletada (del), o contador decrementa. Atingindo zero, o bloco de memória é devolvido imediatamente à PVM sem pausa perceptível.
  2. Coletor de Lixo Cíclico (Cyclic Garbage Collector): Objetos que mantêm referências circulares mútuas (a.filho = b; b.pai = a) nunca atingem zero sozinhos. O módulo gc roda em segundo plano dividindo os objetos em três gerações (Gen 0, Gen 1, Gen 2), inspecionando e rompendo grafos isolados de referências inalcançáveis.
  3. PyMalloc: Para evitar sobrecarga de chamadas de sistema (malloc do SO) para milhares de pequenos objetos, o Python gerencia internamente blocos de memória divididos em Arenas (256 KB) e Pools (4 KB).

📋 2. Listas e Tuplas: Mecânica Interna e Complexidade

Coleção Mutabilidade Estrutura de Dados em C Complexidade append Complexidade insert(0) Hashable?
list 🔓 Mutável Array dinâmico de ponteiros contíguos (PyObject**) $O(1)$ amortizado $O(N)$ (desloca memória) ❌ Não
tuple 🔒 Imutável Array estático de ponteiros de tamanho fixo N/A (imutável) N/A (imutável) 🟢 Sim (se itens forem hashable)

A Estratégia de Sobrealocação (Over-allocation)

Quando você executa repetidos append(), o CPython não aloca memória elemento por elemento. Ele emprega uma fórmula de crescimento exponencial amortizado:

\[\text{nova\_capacidade} = \text{tamanho} + (\text{tamanho} \gg 3) + (\text{tamanho} < 9 \ ? \ 3 : 6)\]

Isso garante que 90% das adições sejam imediatas ($O(1)$), exigindo realocação de bloco apenas esporadicamente.

Armadilha da Cópia Rasa (Shallow) vs Profunda (Deep)

  • Cópia Rasa (copia = original.copy() ou original[:]): Cria um novo container externo, mas os elementos internos continuam apontando para os mesmos endereços do Heap.
  • Cópia Profunda (copy.deepcopy(original)): Percorre todo o grafo de objetos e duplica recursivamente cada instância.
import copy

orig = [[1, 2], [3, 4]]
rasa = orig.copy()
profunda = copy.deepcopy(orig)

orig[0][0] = 99
print(rasa[0][0])      # 99 (Modificado! Compartilha a sublista)
print(profunda[0][0])  # 1  (Preservado! Endereço de memória isolado)

🔲 3. Matrizes Multidimensionais e a Armadilha da Multiplicação

Matrizes em Python são estruturas de listas aninhadas (list[list[T]]).

⚠️ A Armadilha Clássica da Matriz: matriz = [[0] * 3] * 3 NÃO cria uma grade 3x3 independente. Ela cria uma única sublista [0, 0, 0] repetida três vezes. Alterar matriz[0][0] = 5 altera a primeira coluna de todas as linhas!

Criação Canônica via Comprehension Aninhada

# Correto: Três listas totalmente independentes em memória
linhas, colunas = 4, 3
matriz_correta: list[list[int]] = [
    [0 for _ in range(colunas)]
    for _ in range(linhas)
]

Transposição Elegante de Matrizes com zip(*matriz)

Para transformar linhas em colunas sem laços indexados prolixos, o Python oferece o idioma funcional do desempacotamento de matrizes com zip:

grade: list[list[int]] = [
    [1, 2, 3],
    [4, 5, 6]
]

# Transposição para grade 3x2:
transposta: list[list[int]] = [list(coluna) for coluna in zip(*grade)]
# Resultado: [[1, 4], [2, 5], [3, 6]]

🔬 4. Benchmark Algorítmico das Coleções

Operação Lista (list) Tupla (tuple) Deque (collections.deque)
Acesso por Índice (col[i]) $O(1)$ $O(1)$ $O(N)$ (otimizado nas pontas)
Adição ao Final (append) $O(1)$ amortizado N/A $O(1)$ garantido
Adição no Início (prepend/appendleft) $O(N)$ N/A $O(1)$ garantido
Busca por Valor (x in col) $O(N)$ $O(N)$ $O(N)$
Consumo de Memória Base Maior (over-allocation) Mínimo absoluto Médio (blocos encadeados)