Forem: Gissandro Gama

Desafio Final e o Segredo do O(N) (Dois Ponteiros)

Gissandro Gama — Sun, 30 Nov 2025 00:39:13 +0000

Pensando Linear: Resolvendo Problemas Complexos em O(N) e o Segredo do O(1) de Elixir 🔑

Chegamos ao final da nossa jornada pela Complexidade de Algoritmos! Vimos o poder do Merge Sort O(N log N) e a velocidade da Busca Binária O(log N).

Neste post final, vamos:

Aplicar o conhecimento de O(N) em um desafio avançado (o "problema dos quadrados").
Revelar o segredo técnico por trás da promessa de O(1) dos Mapas de Elixir.

Desafio O(N) Avançado: A Técnica dos Dois Ponteiros

Revisite o problema: Dada uma lista já ordenada nums, retorne o lista dos quadrados dos números, também ordenado.

Entrada (`nums`)	Quadrados	Resultado Ordenado
`[-4, -1, 0, 3, 10]`	`[16, 1, 0, 9, 100]`	`[0, 1, 9, 16, 100]`

A solução ingênua seria elevar ao quadrado O(N) e depois ordenar O(N log N), totalizando O(N log N).

O truque é usar a informação de que a entrada já está ordenada. Os maiores quadrados estarão sempre nas pontas do list de entrada, devido aos números negativos com alto valor absoluto.

A solução O(N) usa a técnica dos Dois Ponteiros para construir o resultado de trás para frente (do maior para o menor):

Um ponteiro (l) no início (-4).
Um ponteiro (r) no fim (10).
Comparamos os quadrados nas pontas. O maior quadrado é colocado na lista de resultados.
O ponteiro correspondente se move para dentro.

Código Elixir: Solução `O(N)`

Em Elixir, usamos o Enum.reduce para simular o movimento dos ponteiros e o [square | acc] (prepend) para construir o resultado de trás para frente em O(1) por passo.

defmodule SortedSquares do
  @doc "Solução O(N) com Dois Ponteiros, construindo o resultado em ordem inversa."
  def sorted_squares(nums) do
    # l: ponteiro esquerdo (0), r: ponteiro direito (N-1)
    {result_reversed, _} =
      0..(length(nums) - 1)
      |> Enum.reduce({[], {0, length(nums) - 1}}, fn _, {acc, {l, r}} ->
        left_square = Enum.at(nums, l) * Enum.at(nums, l)
        right_square = Enum.at(nums, r) * Enum.at(nums, r)

        if left_square > right_square do
          # Se o da esquerda for maior, movemos o ponteiro l
          {[left_square | acc], {l + 1, r}}
        else
          # Se o da direita for maior (ou igual), movemos o ponteiro r
          {[right_square | acc], {l, r - 1}}
        end
      end)

    result_reversed
  end
end

Conclusão: A técnica dos Dois Ponteiros garante que visitamos cada elemento exatamente uma vez O(N), evitando o O(N log N) da ordenação final.

O Segredo Final: Por Que `O(1)` não é mágica?

Ao longo desta série, prometemos que a busca/inserção em Map e MapSet de Elixir é O(1). Por que é tão rápido e, mais importante, como o Elixir consegue fazer isso garantindo a imutabilidade?

A resposta está na estrutura de dados que a Erlang/Elixir utiliza: as Hash Array Mapped Tries (HAMT).

HAMT: O Motor Imutável do `O(1)`

Hashing: Quando você insere uma chave (ex: :user), ela é transformada em um Hash Code (um número).
Trie (Árvore Digital): Esse hash code é usado como um caminho para navegar em uma árvore de alta ramificação (a Trie). O HAMT só precisa descer alguns níveis da árvore para encontrar o endereço exato do valor.
Array Mapped: Em cada nível, em vez de ter muitos ponteiros, há um pequeno array (o "mapa") que é usado para buscar o próximo ramo.

Vantagem da Imutabilidade: Quando você atualiza um MapSet em Elixir, o sistema não precisa copiar toda a estrutura. Ele reutiliza os ramos antigos da árvore (nós) que não foram alterados e apenas cria novos nós para o caminho que foi modificado. Isso é conhecido como Compartilhamento Estrutural (Structural Sharing).

Graças ao HAMT, a promessa de O(1) (tempo constante) para busca e inserção é mantida, e o código Elixir permanece rápido e seguro para concorrência na BEAM.

Parabéns! Fim da Série.

Você agora tem uma compreensão sólida das classes de complexidade, sabe identificar os gargalos O(N^2) e possui as ferramentas de Elixir (Merge Sort, MapSet, e Reduções) para escrever código que não apenas funciona, mas que escala de forma eficiente.

O Padrão Ouro da Ordenação: O(N log N)

Gissandro Gama — Sun, 30 Nov 2025 00:37:04 +0000

O Melhor dos Dois Mundos: Entendendo a Complexidade O(N log N) do Merge Sort 🥇

Nos posts anteriores, conquistamos a velocidade da Busca Binária O(log N) e a eficiência Linear O(N). Agora, vamos ao padrão-ouro para o Ordenação: a complexidade O(N log N) (Linearithmic).

Todo algoritmo de ordenação que precisa escalar para grandes volumes de dados (como Merge Sort ou Quick Sort) mira nessa complexidade, pois ela combina o poder de dividir o problema log N com a eficiência de processar os resultados de forma linear N.

A Lógica do Merge Sort: Divisão e Mesclagem

O Merge Sort (Ordenação por Mesclagem) é um exemplo perfeito de Divide and Conquer (Dividir para Conquistar). Ele funciona em duas fases, que correspondem diretamente à sua complexidade O(N log N):

1. Fase de Divisão (log N) 🌳

O algoritmo divide recursivamente a lista em metades, continuando a divisão até que restem apenas listas de um único elemento (que, por definição, estão ordenadas).

Se você tem 1.000.000 de itens, você só precisa de 20 divisões (log_2 1.000.000 ≈ 20) para chegar ao caso base.
O log N é a altura da árvore de recursão.

2. Fase de Mesclagem N 🔗

É aqui que o trabalho pesado é feito. Em cada nível da recursão (os log N níveis), o algoritmo mescla (combina) as listas ordenadas de volta em uma única lista maior e também ordenada.

Para mesclar duas listas que, juntas, somam N elementos, o algoritmo precisa fazer, no máximo, N comparações para garantir que a saída esteja em ordem.
Esta operação de mesclagem é intrinsecamente O(N) (Linear).

Como realizamos o trabalho O(N) em cada um dos log N níveis, a complexidade final é O(N log N).

O Coração `O(N)` em Elixir: A Função `merge`

A chave para um Merge Sort eficiente é garantir que a função de mesclagem seja rigorosamente O(N). Em Elixir, isso significa nunca usar o operador de concatenação lenta (++) e trabalhar apenas nas cabeças das listas.

Nosso código de mesclagem faz exatamente isso, comparando as cabeças (h_a e h_b) e movendo o menor elemento para o resultado recursivamente.

# --- O CORAÇÃO O(N) DA MESCLAGEM ---

# Casos base para quando uma das listas se esgota:
defp merge([], list_b), do: list_b
defp merge(list_a, []), do: list_a

# Cláusula Recursiva Principal
defp merge([h_a | t_a] = list_a, [h_b | t_b] = list_b) do
  if h_a <= h_b do
    # h_a é menor: Coloca na frente do resultado e continua a recursão
    # usando a CAUDA de A (t_a) e a LISTA B COMPLETA (list_b).
    [h_a | merge(t_a, list_b)]
  else
    # h_b é menor: Coloca na frente do resultado e continua a recursão
    # usando a LISTA A COMPLETA (list_a) e a CAUDA de B (t_b).
    [h_b | merge(list_a, t_b)]
  end
end

Código Final: O Merge Sort Completo

Este código encapsula a filosofia O(N log N):

defmodule MergeSort do
  @doc "Implementação do Merge Sort em Elixir (O(N log N))."
  def sort(list) do
    case list do
      [] -> []; [_] -> list # Caso Base
      _ ->
        # 1. DIVISÃO: Agora a função está definida.
        {low, high} = split_list(list) 

        # 2. RECURSÃO
        sorted_low = sort(low)
        sorted_high = sort(high)

        # 3. MESCLAGEM
        merge(sorted_low, sorted_high)
    end
  end

  ## 🛠️ FUNÇÃO AUXILIAR DE DIVISÃO (Adicionada para Corrigir o Erro)
  # O(N) para encontrar o comprimento e dividir a lista ligada.
  defp split_list(list) do
    # Encontrar o ponto médio da lista
    len = length(list)
    split_point = trunc(len / 2)

    # Enum.split faz a divisão no ponto (O(N) por varrer a lista)
    Enum.split(list, split_point)
  end

 # Adicionar o código da acima
end

Análise: O Merge Sort é o melhor que podemos fazer para ordenação genérica. Ele garante a performance O(N log N) em todos os casos (pior, médio e melhor), o que o torna incrivelmente estável e confiável.

Próxima Parada: O Desafio Final

No próximo e último post da série, faremos uma aplicação avançada do O(N). Veremos como usar a técnica dos Dois Ponteiros para resolver o problema Squares of a Sorted Array (que já exploramos), transformando a necessidade de uma ordenação O(N log N) final em um único e elegante passo O(N)! Além disso, revelaremos o segredo do O(1) dos Mapas de Elixir (a estrutura HAMT).

A Santa Graal da Busca: O(log N)

Gissandro Gama — Sat, 29 Nov 2025 23:47:20 +0000

Acelerando a Busca: Por que o O(log N) (Busca Binária) é mais rápido que a Luz? ✨

Vimos nos posts anteriores como migrar de O(N^2) para O(N). Mas e se pudéssemos ser ainda mais rápidos?

A complexidade O(log N) (Logarítmica) é o padrão-ouro para qualquer algoritmo de busca. A grande diferença é a taxa de crescimento:

Tamanho da Entrada (N)	O(N) (Linear)	O(log N) (Logarítmico)
1.000	1.000 passos	10 passos
1.000.000	1.000.000 passos	20 passos
1.000.000.000	1 bilhão de passos	aproximadamente 30 passos

O tempo de execução é quase indiferente ao tamanho da entrada.

O Segredo: Dividir para Conquistar 🔪

O algoritmo que atinge essa velocidade é a Busca Binária (Binary Search). A lógica é simples: em cada passo, você consegue descartar metade do espaço de busca.

Pré-requisito Obrigatório

Para que a Busca Binária funcione, a estrutura de dados DEVE estar ordenada.

Você verifica o elemento central (mid).
Se o valor central for menor que seu alvo, você descarta toda a metade esquerda.
Se for maior, descarta toda a metade direita.

Isso se repete recursivamente, dividindo o problema ao meio (log2) a cada iteração.

O Desafio O(N) em Elixir 💥

Aqui está a pegadinha para quem programa em Elixir:

Como a Lista Ligada padrão só sabe onde a cabeça está, se você tentar acessar o elemento central (o índice N/2) em uma lista de Elixir, o sistema é forçado a percorrer os N/2 elementos, tornando essa operação O(N).

Se a cada passo da sua busca O(log N) você gasta O(N) para encontrar o meio, a complexidade final se torna O(N log N) no melhor dos casos, o que anula o ganho da Busca Binária!

A Solução em Elixir: Tuplas O(1)

Para realizar a Busca Binária corretamente em O(log N), precisamos de uma estrutura que permita acesso por índice em O(1). No ecossistema Erlang/Elixir, usamos Tuplas para essa finalidade.

Com o acesso O(1) garantido, podemos implementar a lógica recursiva:

defmodule BinarySearch do
  @doc "Inicia a Busca Binária O(log N)."
  def search(list, target) do
    # Conversão para Tupla para simular o acesso O(1) por índice
    array = List.to_tuple(list)
    # Inicializa a recursão: low=0, high=N-1
    binary_search_recursive(array, target, 0, tuple_size(array) - 1)
  end

  # Condição de Falha: low cruzou high. Target não existe.
  defp binary_search_recursive(_array, _target, low, high) when low > high do
    :not_found
  end

  # Condição Recursiva Principal
  defp binary_search_recursive(array, target, low, high) do
    # 1. Calcular o índice central (mid)
    mid = floor((low + high) / 2)

    # 2. Obter o valor central (acesso O(1) na tupla)
    # Tuplas em Erlang são base 1, por isso o + 1
    current_value = :erlang.element(mid + 1, array) 

    # 3. Condição de Sucesso
    if current_value == target do
      mid # Retorna o índice

    # 4. Alvo é MAIOR: Descartamos a esquerda, movemos low
    else if current_value < target do
      binary_search_recursive(array, target, mid + 1, high)

    # 5. Alvo é MENOR: Descartamos a direita, movemos high
    else 
      binary_search_recursive(array, target, low, mid - 1)
    end
   end
  end
end

A beleza dessa função é que ela demonstra a complexidade O(log N) de forma perfeita, pois as chamadas recursivas sempre reduzem o espaço de busca pela metade.

Próxima Parada: O Padrão Ouro

Se O(log N) é o melhor para a busca, qual é o melhor para a Ordenação?

No próximo post, exploraremos a complexidade O(N log N) (Linearithmic), o padrão-ouro dos algoritmos de ordenação, e desvendaremos o Merge Sort, que combina o poder logarítmico de dividir problemas com o trabalho linear de mesclá-los de volta.

A Migração de O(N^2) para O(N): O Poder do O(1)

Gissandro Gama — Sat, 29 Nov 2025 23:45:35 +0000

Domando o Crescimento: Como Transformar O(N^2) em O(N) com Estruturas de Dados Elixir

No Post 1 - O que é Big O? e o Vilão O(N^2), vimos que a complexidade O(N^2) é causada por um laço aninhado que obriga o sistema a varrer a lista inteira (N) para cada elemento (N). Se um algoritmo tem que fazer N x N operações, ele não vai escalar.

A chave para migrar de O(N^2) para O(N) (Linear) é garantir que cada elemento da entrada seja visitado um número constante de vezes.

Objetivo: Transformar a operação de "procurar um elemento na lista" de O(N) para O(1).

O Segredo O(1): Mapas e Conjuntos

Para obter uma busca ou inserção em tempo constante O(1), não podemos usar a lista padrão de Elixir. Precisamos de uma estrutura que responda "Este item já existe?" de forma instantânea, sem precisar iterar.

Em Elixir, essa estrutura é o MapSet (Conjunto) ou o Map (Mapa). Eles utilizam uma técnica chamada Hashing para transformar a chave em um endereço de memória previsível.

Estrutura	Operação	Complexidade
Lista	Procurar um elemento	O(N)
MapSet	Procurar um elemento	O(1)

A Solução O(N) em Elixir: Reduce e MapSet

Para resolver o problema de duplicatas em tempo O(N), usaremos uma técnica de programação funcional chamada Acumulação. Vamos percorrer a lista apenas uma vez (Enum.reduce_while), usando um MapSet como nosso acumulador para rastrear os elementos já vistos.

Código Elixir: Duplicata Rápida


defmodule OptimizedDuplicationCheck do

  def contains_duplicate_fast(list) do
    # 1. Acumulador: Iniciamos com um MapSet vazio.
    initial_set = MapSet.new()

    list # Usamos reduce_while para otimizar, parando assim que a duplicata for achada.
    |> Enum.reduce_while(initial_set, fn element, seen_elements ->
      # Checagem O(1)
      if MapSet.member?(seen_elements, element) do
        # 🟢 Sucesso no Melhor Caso (O(1)): Encontrado! Paramos.
        {:halt, true} 
      else
        # Atualização O(1): Adiciona o elemento e continua.
        new_set = MapSet.put(seen_elements, element)
        {:cont, new_set}
      end
    end) # Trata o resultado: se foi halt, retorna true; se percorreu tudo, retorna false.
    |> (&(&1 == true)).() 
  end

end

📈 Análise de Complexidade

Operação	Frequência	Complexidade
`Enum.reduce_while`	N vezes	O(N)
`MapSet.member?`	N vezes (dentro do reduce)	O(1)
`MapSet.put`	N vezes (dentro do reduce)	O(1)
Complexidade Total	N \times (O(1) + O(1))	O(N)

Ao trocar a busca interna de O(N) para O(1), eliminamos o fator N extra, garantindo que o algoritmo escale linearmente.

Além disso, o uso de Enum.reduce_while nos dá uma otimização no Melhor Caso: se a duplicata for o primeiro elemento, a execução é interrompida em O(1)!

Próxima Parada: O O(log N)

Se O(N) é excelente, imagine um algoritmo que requer apenas =~ 24 passos para encontrar um item em uma lista de 10 milhões de elementos.

No próximo post, exploraremos a Busca Binária e a complexidade O(log N) (Logarítmica), a verdadeira "Santa Graal" da velocidade de busca. Veremos por que a lista deve estar ordenada para que isso funcione e qual estrutura de dados de Elixir precisamos usar para implementá-la corretamente.

O que é Big O? e o Vilão O(N^2)

Gissandro Gama — Sat, 29 Nov 2025 23:45:14 +0000

Complexidade de Algoritmos com Elixir: Entendendo o O(N^2) e Por que sua lista é tão lenta?

Se você programa em Elixir ou qualquer outra linguagem e já viu seu código funcionar perfeitamente com 10 itens, mas travar com 10.000, você esbarrou na Complexidade de Algoritmos.

A Notação Big O O(...) não mede o tempo em segundos, mas sim a regra de crescimento do tempo de execução em relação ao tamanho da entrada (N). É a ferramenta mais importante para escrever código que escala.

Acelerando e Desacelerando: O(1) vs. O(N)

Em Elixir, a estrutura de dados mais fundamental é a Lista Ligada Simples (Singly Linked List). Entender como ela funciona nos dá a base para o O(1) e o O(N).

🟢 O(1): Complexidade Constante

O tempo de execução é sempre o mesmo, não importa se sua lista tem 10 elementos ou 1 milhão.

Exemplo Elixir: Colocar um novo elemento no início (prepend) da lista.

# O(1): Cria um novo nó que aponta para a lista antiga.
new_list = [novo_item | lista_antiga]

# O(1): Acesso à Cabeça
[head | _] = new_list

Essa é a operação mais comum em código funcional e a razão pela qual a criação de listas em Elixir é tão rápida.

🟡 O(N): Complexidade Linear

O tempo de execução cresce proporcionalmente ao tamanho da entrada. Se a lista dobra de tamanho, o tempo dobra.

Exemplo Elixir: Varrer a lista (map, reduce) ou anexar um item no final.

# O(N): Percorre CADA elemento da lista
sum = Enum.reduce(list, 0, &(&1 + &2))

# O(N): Para anexar no final, o sistema deve percorrer a lista inteira.
list = list ++ [item_no_fim]

🔥 O(N^2): O Vilão Quadrático

A complexidade O(N^2) é o seu pior inimigo para escalabilidade. Se a entrada (N) dobra de tamanho, o tempo de execução quadruplica (2^2 = 4).

Causa: A presença de laços de repetição aninhados (um loop dentro de outro loop) onde o loop interno depende do tamanho total da entrada.

Exemplo Prático: Checagem Ingênua de Duplicatas

Imagine que queremos verificar se há duplicatas em uma lista. Se usarmos a abordagem ingênua, acabamos com O(N^2):

def check_duplicate_slow(list) do
  # Enum.any? itera pela lista: N vezes
  Enum.any?(list, fn current_element ->
    # Para cada current_element, essa linha varre a lista INTEIRA novamente: N vezes
    list
    |> Enum.filter(&(&1 == current_element))
    |> Enum.count() > 1
  end)
end

Análise:

O Enum.any? externo executa N vezes.
Para cada execução, o Enum.filter interno varre toda a lista (N elementos).
Total de operações =~ N x N = O(N^2).

Se N = 10.000, o algoritmo fará 100.000.000 de operações (cem milhões). Um crescimento insustentável!

Próxima Parada: O Salto para $O(N)$

A solução O(N^2)$ é fácil de escrever, mas destrói a performance. Existe uma forma de resolver o problema de duplicatas visitando cada elemento apenas uma vez, transformando o algoritmo em um rápido O(N)?

No próximo post, exploraremos a técnica que usa estruturas de dados O(1) para eliminar o laço interno, transformando o código de lento e quadratico em rápido e linear. Não perca a Migração de O(N^2) para O(N) !

Desvendando os Superpoderes do Elixir: Concorrência e Tolerância a Falhas

Gissandro Gama — Wed, 05 Nov 2025 23:38:26 +0000

Se você já ouviu falar que o Elixir é ideal para sistemas escaláveis, distribuídos e tolerantes a falhas, mas nunca entendeu exatamente o porquê, este post é para você. Vamos mergulhar nos fundamentos que o Elixir herda da plataforma Erlang (BEAM) e que permitem a construção de aplicações robustas, capazes de lidar com milhões de conexões simultâneas.

1. O Coração de Tudo: Processos Leves e o Modelo Ator

A base da concorrência em Elixir não são threads do sistema operacional, mas sim processos extremamente leves gerenciados pela própria máquina virtual (BEAM).

Milhões de Processos: É perfeitamente viável executar milhares ou até milhões desses processos concorrentemente na mesma máquina. Cada um deles é incrivelmente pequeno e eficiente.
Isolamento Total: Cada processo tem sua própria memória e seu próprio Garbage Collector. A falha de um processo não leva à falha de outros. O isolamento é crucial, pois simplifica o código (eliminando a necessidade de mecanismos complexos de sincronização como locks ou mutexes) e aumenta a estabilidade geral do sistema.
Comunicação por Mensagens: Os processos não compartilham memória. A única forma de se comunicarem é através da troca de mensagens. Enviar uma mensagem a outro processo resulta em uma cópia profunda (deep copy) do conteúdo, garantindo que a memória permaneça isolada.

Cada processo funciona como um "ator" independente. Ele possui uma "caixa de correio" (mailbox) e processa uma mensagem por vez. Isso o torna um ponto de sincronização eficaz, garantindo a consistência de seu estado interno, mesmo que receba múltiplas requisições concorrentes.

Exemplo na Prática: Criando um Processo

Vamos criar um processo simples que espera uma mensagem, imprime uma saudação e depois termina.

# Defina um módulo com a função que o processo irá executar
defmodule Greeter do
  def start do
    # A função receive espera por uma mensagem que corresponda a um dos padrões
    receive do
      {:greet, name} -> IO.puts("Olá, #{name}!")
      _ -> IO.puts("Não entendi a mensagem.")
    end
  end
end

# Inicie uma sessão IEx (iex -S mix) para testar

# Crie um novo processo executando a função Greeter.start/0
# A função spawn retorna o PID (Process Identifier)
iex> pid = spawn(Greeter, :start, [])
#PID<0.150.0>

# Envie uma mensagem para o processo usando seu PID
iex> send(pid, {:greet, "Mundo"})
Olá, Mundo!
{:greet, "Mundo"}

Neste exemplo, spawn criou um ator, e send colocou uma mensagem em sua caixa de correio. O processo a consumiu, executou a ação e terminou, tudo isso sem interferir em mais nada no sistema.

2. "Justiça para Todos": O Agendador Preemptivo (Scheduler)

Como a BEAM gerencia milhões de processos sem que um deles "trave" todo o sistema? A resposta é o agendamento preemptivo.

Cada processo recebe uma pequena janela de tempo de execução (historicamente, cerca de 2.000 chamadas de função, ou "reduções"). Após esgotar essa fatia de tempo, o agendador pausa o processo e dá a vez para o próximo da fila.

Isso impede que uma única tarefa de longa duração bloqueie todo o sistema, garantindo que a aplicação como um todo permaneça responsiva.

3. A Filosofia "Let It Crash": Construindo Sistemas que se Curam

Em vez de programar defensivamente com incontáveis blocos try/catch para prever todos os erros possíveis, a filosofia em Elixir é "deixar falhar" (let it crash).

O modelo de concorrência do Erlang fornece as ferramentas para que os sistemas se autocurem e recuperem de erros inesperados. A causa de erros imprevisíveis é frequentemente um estado corrompido, e ao falhar e ser reiniciado, o processo retorna a um estado inicial limpo e consistente.

Isso é possível graças a dois mecanismos principais: Links e Monitores, orquestrados por Supervisores.

Links: Falhando em Conjunto

Quando dois processos são "linkados", eles formam um pacto: se um deles morrer de forma anormal, ele enviará um sinal de saída (exit signal) para o outro, que, por padrão, também morrerá.

Exemplo na Prática:

# Inicie uma sessão IEx

# Crie um processo que simplesmente falha e o linke ao processo do IEx
iex> spawn_link(fn -> raise "Oops, algo deu errado!" end)
** (RuntimeError) Oops, algo deu errado!
    (stdlib) erl_eval.erl:680: :erl_eval.do_apply/6

iex> # O seu terminal IEx pode fechar ou mostrar um erro, pois ele estava linkado ao processo que falhou!

Monitores: Observando de Longe

E se você quiser saber quando um processo morre, mas não quer morrer junto com ele? Para isso, usamos monitores.

O processo observador recebe uma mensagem {:DOWN, ...} se o processo monitorado falhar, mas o observador não é derrubado. Monitores são a ferramenta ideal quando não se deseja que a falha se propague.

Exemplo na Prática:

# Inicie uma sessão IEx

# Crie um processo que falha, mas desta vez, apenas o monitore
iex> {_pid, monitor_ref} = spawn_monitor(fn -> raise "Falha controlada" end)
{#PID<0.154.0>, #Reference<...>}

# O processo do IEx continua vivo. Vamos checar sua caixa de correio
iex> flush()
{:DOWN, #Reference<...>, :process, #PID<0.154.0>, {%RuntimeError{message: "Falha controlada"}, [...]}}
:ok

A mensagem :DOWN nos informa sobre a falha, permitindo que nosso processo tome uma ação (como tentar reiniciar o trabalhador) sem ser afetado.

Supervisores: A Rede de Segurança

Supervisores são processos especiais cujo único trabalho é monitorar outros processos (seus "filhos") e reiniciá-los quando eles falham. Eles são a implementação prática da filosofia "let it crash".

Eles formam uma árvore de supervisão, o que permite a isolação de erros em grão fino. Se um erro ocorre em um trabalhador, tenta-se resolvê-lo localmente (pelo supervisor imediato). Se o supervisor falhar, o erro se propaga para o supervisor pai, que tentará reiniciar uma parte maior do sistema. Isso garante que a falha seja contida na menor subestrutura possível.

Exemplo na Prática: Um Supervisor Simples

O Trabalhador (Worker): Um GenServer que mantém um estado.

defmodule MyApp.Worker do
  use GenServer

  # API Pública
  def start_link(initial_state) do
    GenServer.start_link(__MODULE__, initial_state, name: __MODULE__)
  end

  def crash, do: GenServer.cast(__MODULE__, :crash)

  # Callbacks do GenServer
  @impl true
  def init(initial_state) do
    IO.puts("Worker iniciado com estado: #{inspect(initial_state)}")
    {:ok, initial_state}
  end

  @impl true
  def handle_cast(:crash, state) do
    IO.puts("Recebi uma ordem para falhar! Adeus, estado: #{inspect(state)}")
    raise "Falha intencional"
    # O GenServer irá travar aqui
  end
end

O Supervisor:

defmodule MyApp.Supervisor do
  use Supervisor

  def start_link(init_arg) do
    Supervisor.start_link(__MODULE__, init_arg, name: __MODULE__)
  end

  @impl true
  def init(_init_arg) do
    children = [
      # Define o nosso worker como um filho
      {MyApp.Worker, 0} # O argumento `0` será passado para o start_link do Worker
    ]

    # A estratégia :one_for_one reinicia apenas o processo que falhou
    Supervisor.init(children, strategy: :one_for_one)
  end
end

Testando no IEx:

# Inicie o supervisor
iex> {:ok, sup_pid} = MyApp.Supervisor.start_link([])
Worker iniciado com estado: 0
{:ok, #PID<0.165.0>}

# Vamos forçar o worker a falhar
iex> MyApp.Worker.crash()
Recebi uma ordem para falhar! Adeus, estado: 0
:ok

# O supervisor detecta a falha e reinicia o worker imediatamente!
# A saída abaixo aparece automaticamente no seu terminal:
Worker iniciado com estado: 0

# O processo foi reiniciado com um estado limpo, como se nada tivesse acontecido.
# O sistema se curou sozinho!

4. Bônus: Abstração de Dados com Structs e Módulos

A filosofia de código limpo em Elixir também se beneficia da imutabilidade. Funções não modificam dados; elas retornam novas versões dos dados.

Isso é facilitado pelo uso de módulos e structs. Um módulo é uma coleção de funções que operam sobre um tipo de dado específico. Structs fornecem campos nomeados e valores padrão, impondo contratos de dados mais rígidos que mapas genéricos.

A convenção é que a estrutura de dados seja sempre o primeiro argumento das funções, o que permite o uso elegante do operador pipeline (|>).

Exemplo na Prática:

defmodule User do
  # Define a estrutura de dados
  defstruct [:name, :email, active: false]

  # Funções que operam sobre a estrutura User
  def new(name, email) do
    %User{name: name, email: email}
  end

  def activate(%User{} = user) do
    %User{user | active: true} # Retorna uma *nova* struct com o campo `active` alterado
  end

  def change_email(%User{} = user, new_email) do
    %User{user | email: new_email} # Retorna uma *nova* struct
  end
end

# Testando no IEx
iex> user = User.new("Gama", "gama@example.com")
%User{name: "Gama", email: "gama@example.com", active: false}

iex> user |> User.activate() |> User.change_email("elixir.dev@example.com")
%User{name: "Gama", email: "elixir.dev@example.com", active: true}

Conclusão

Os "superpoderes" do Elixir não são mágica. Eles são o resultado de um conjunto de princípios de design testados e aprovados ao longo de décadas com o Erlang:

Processos leves e isolados para uma concorrência massiva.
Comunicação explícita por mensagens para evitar o caos de memória compartilhada.
Supervisores que constroem sistemas que se curam sozinhos.
Imutabilidade e abstração de dados que tornam o código previsível e fácil de manter.

Ao abraçar esses conceitos, você começa a pensar não apenas em escrever código que funciona, mas em construir sistemas que são projetados para continuar funcionando, não importa o que aconteça.

Forem: Gissandro Gama

Desafio Final e o Segredo do O(N) (Dois Ponteiros)

Pensando Linear: Resolvendo Problemas Complexos em O(N) e o Segredo do O(1) de Elixir 🔑

Desafio O(N) Avançado: A Técnica dos Dois Ponteiros

Código Elixir: Solução O(N)

O Segredo Final: Por Que O(1) não é mágica?

HAMT: O Motor Imutável do O(1)

Parabéns! Fim da Série.

O Padrão Ouro da Ordenação: O(N log N)

O Melhor dos Dois Mundos: Entendendo a Complexidade O(N log N) do Merge Sort 🥇

A Lógica do Merge Sort: Divisão e Mesclagem

1. Fase de Divisão (log N) 🌳

2. Fase de Mesclagem N 🔗

O Coração O(N) em Elixir: A Função merge

Código Final: O Merge Sort Completo

Próxima Parada: O Desafio Final

A Santa Graal da Busca: O(log N)

Acelerando a Busca: Por que o O(log N) (Busca Binária) é mais rápido que a Luz? ✨

O Segredo: Dividir para Conquistar 🔪

Pré-requisito Obrigatório

O Desafio O(N) em Elixir 💥

A Solução em Elixir: Tuplas O(1)

Próxima Parada: O Padrão Ouro

A Migração de O(N^2) para O(N): O Poder do O(1)

Domando o Crescimento: Como Transformar O(N^2) em O(N) com Estruturas de Dados Elixir

O Segredo O(1): Mapas e Conjuntos

A Solução O(N) em Elixir: Reduce e MapSet

Código Elixir: Duplicata Rápida

📈 Análise de Complexidade

Próxima Parada: O O(log N)

O que é Big O? e o Vilão O(N^2)

Complexidade de Algoritmos com Elixir: Entendendo o O(N^2) e Por que sua lista é tão lenta?

Acelerando e Desacelerando: O(1) vs. O(N)

🟢 O(1): Complexidade Constante

🟡 O(N): Complexidade Linear

🔥 O(N^2): O Vilão Quadrático

Exemplo Prático: Checagem Ingênua de Duplicatas

Próxima Parada: O Salto para $O(N)$

Desvendando os Superpoderes do Elixir: Concorrência e Tolerância a Falhas

1. O Coração de Tudo: Processos Leves e o Modelo Ator

Exemplo na Prática: Criando um Processo

2. "Justiça para Todos": O Agendador Preemptivo (Scheduler)

3. A Filosofia "Let It Crash": Construindo Sistemas que se Curam

Links: Falhando em Conjunto

Exemplo na Prática:

Monitores: Observando de Longe

Exemplo na Prática:

Supervisores: A Rede de Segurança

Exemplo na Prática: Um Supervisor Simples

4. Bônus: Abstração de Dados com Structs e Módulos

Exemplo na Prática:

Conclusão

Código Elixir: Solução `O(N)`

O Segredo Final: Por Que `O(1)` não é mágica?

HAMT: O Motor Imutável do `O(1)`

O Coração `O(N)` em Elixir: A Função `merge`